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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef LLVM_LIBC_SRC___SUPPORT_FREELIST_H 10 #define LLVM_LIBC_SRC___SUPPORT_FREELIST_H 11 12 #include "block.h" 13 14 namespace LIBC_NAMESPACE_DECL { 15 16 /// A circularly-linked FIFO list storing free Blocks. All Blocks on a list 17 /// are the same size. The blocks are referenced by Nodes in the list; the list 18 /// refers to these, but it does not own them. 19 /// 20 /// Allocating free blocks in FIFO order maximizes the amount of time before a 21 /// free block is reused. This in turn maximizes the number of opportunities for 22 /// it to be coalesced with an adjacent block, which tends to reduce heap 23 /// fragmentation. 24 class FreeList { 25 public: 26 class Node { 27 public: 28 /// @returns The block containing this node. block()29 LIBC_INLINE const Block *block() const { 30 return Block::from_usable_space(this); 31 } 32 33 /// @returns The block containing this node. block()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. size()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 FreeList()46 LIBC_INLINE constexpr FreeList() : FreeList(nullptr) {} FreeList(Node * begin)47 LIBC_INLINE constexpr FreeList(Node *begin) : begin_(begin) {} 48 empty()49 LIBC_INLINE bool empty() const { return !begin_; } 50 51 /// @returns The inner size of blocks in the list. size()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. begin()58 LIBC_INLINE Node *begin() { return begin_; } 59 60 /// @returns The first block in the list. front()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. push(Block * block)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. pop()78 LIBC_INLINE void pop() { remove(begin_); } 79 80 /// Remove an arbitrary node from the list. 81 void remove(Node *node); 82 83 private: 84 Node *begin_; 85 }; 86 87 } // namespace LIBC_NAMESPACE_DECL 88 89 #endif // LLVM_LIBC_SRC___SUPPORT_FREELIST_H 90