libc/src/__support/freelist.h

//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
///
/// \file
/// Interface for freelist.
///
//===----------------------------------------------------------------------===//

#ifndef LLVM_LIBC_SRC___SUPPORT_FREELIST_H
#define LLVM_LIBC_SRC___SUPPORT_FREELIST_H

#include "block.h"
#include "src/__support/libc_assert.h"

namespace LIBC_NAMESPACE_DECL {

/// A circularly-linked FIFO list storing free Blocks. All Blocks on a list
/// are the same size. The blocks are referenced by Nodes in the list; the list
/// refers to these, but it does not own them.
///
/// Allocating free blocks in FIFO order maximizes the amount of time before a
/// free block is reused. This in turn maximizes the number of opportunities for
/// it to be coalesced with an adjacent block, which tends to reduce heap
/// fragmentation.
class FreeList {
public:
  class Node {
  public:
    /// @returns The block containing this node.
    LIBC_INLINE BlockRef block() const {
      return BlockRef::from_usable_space(this);
    }

    /// @returns The block containing this node.
    LIBC_INLINE BlockRef block() { return BlockRef::from_usable_space(this); }

    /// @returns The inner size of blocks in the list containing this node.
    LIBC_INLINE size_t size() const { return block().inner_size(); }

    /// @returns The next node in the list containing this node.
    LIBC_INLINE Node *next() const { return next_; }

  protected:
    LIBC_INLINE void integrity_check() const {
      LIBC_HEAP_INTEGRITY_CHECK(next_->prev_ == this,
                                "FreeList node corruption detected");
      LIBC_HEAP_INTEGRITY_CHECK(prev_->next_ == this,
                                "FreeList node corruption detected");
    }

  private:
    // Circularly linked pointers to adjacent nodes.
    Node *prev_;
    Node *next_;
    friend class FreeList;
  };

  LIBC_INLINE constexpr FreeList() : FreeList(nullptr) {}
  LIBC_INLINE constexpr FreeList(Node *begin) : begin_(begin) {}

  LIBC_INLINE bool empty() const { return !begin_; }

  /// @returns The inner size of blocks in the list.
  LIBC_INLINE size_t size() const {
    LIBC_ASSERT(begin_ && "empty lists have no size");
    return begin_->size();
  }

  /// @returns The first node in the list.
  LIBC_INLINE Node *begin() { return begin_; }

  /// @returns The first block in the list.
  LIBC_INLINE BlockRef front() { return begin_->block(); }

  /// Push a block to the back of the list.
  /// The block must be large enough to contain a node.
  LIBC_INLINE void push(BlockRef block) {
    LIBC_ASSERT(!block.used() &&
                "only free blocks can be placed on free lists");
    LIBC_ASSERT(block.inner_size_free() >= sizeof(FreeList) &&
                "block too small to accomodate free list node");
    push(new (block.usable_space()) Node);
  }

  /// Push an already-constructed node to the back of the list.
  /// This allows pushing derived node types with additional data.
  void push(Node *node);

  /// Pop the first node from the list.
  LIBC_INLINE void pop() { remove(begin_); }

  /// Remove an arbitrary node from the list.
  void remove(Node *node);

  /// Verify integrity of all nodes in the list.
  void integrity_check() const;

private:
  Node *begin_;
};

} // namespace LIBC_NAMESPACE_DECL

#endif // LLVM_LIBC_SRC___SUPPORT_FREELIST_H