90 lines · c
1//===-- Interface for freelist --------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LLVM_LIBC_SRC___SUPPORT_FREELIST_H10#define LLVM_LIBC_SRC___SUPPORT_FREELIST_H11 12#include "block.h"13 14namespace LIBC_NAMESPACE_DECL {15 16/// A circularly-linked FIFO list storing free Blocks. All Blocks on a list17/// are the same size. The blocks are referenced by Nodes in the list; the list18/// refers to these, but it does not own them.19///20/// Allocating free blocks in FIFO order maximizes the amount of time before a21/// free block is reused. This in turn maximizes the number of opportunities for22/// it to be coalesced with an adjacent block, which tends to reduce heap23/// fragmentation.24class FreeList {25public:26 class Node {27 public:28 /// @returns The block containing this node.29 LIBC_INLINE const Block *block() const {30 return Block::from_usable_space(this);31 }32 33 /// @returns The block containing this node.34 LIBC_INLINE Block *block() { return Block::from_usable_space(this); }35 36 /// @returns The inner size of blocks in the list containing this node.37 LIBC_INLINE size_t size() const { return block()->inner_size(); }38 39 private:40 // Circularly linked pointers to adjacent nodes.41 Node *prev;42 Node *next;43 friend class FreeList;44 };45 46 LIBC_INLINE constexpr FreeList() : FreeList(nullptr) {}47 LIBC_INLINE constexpr FreeList(Node *begin) : begin_(begin) {}48 49 LIBC_INLINE bool empty() const { return !begin_; }50 51 /// @returns The inner size of blocks in the list.52 LIBC_INLINE size_t size() const {53 LIBC_ASSERT(begin_ && "empty lists have no size");54 return begin_->size();55 }56 57 /// @returns The first node in the list.58 LIBC_INLINE Node *begin() { return begin_; }59 60 /// @returns The first block in the list.61 LIBC_INLINE Block *front() { return begin_->block(); }62 63 /// Push a block to the back of the list.64 /// The block must be large enough to contain a node.65 LIBC_INLINE void push(Block *block) {66 LIBC_ASSERT(!block->used() &&67 "only free blocks can be placed on free lists");68 LIBC_ASSERT(block->inner_size_free() >= sizeof(FreeList) &&69 "block too small to accomodate free list node");70 push(new (block->usable_space()) Node);71 }72 73 /// Push an already-constructed node to the back of the list.74 /// This allows pushing derived node types with additional data.75 void push(Node *node);76 77 /// Pop the first node from the list.78 LIBC_INLINE void pop() { remove(begin_); }79 80 /// Remove an arbitrary node from the list.81 void remove(Node *node);82 83private:84 Node *begin_;85};86 87} // namespace LIBC_NAMESPACE_DECL88 89#endif // LLVM_LIBC_SRC___SUPPORT_FREELIST_H90