xref: /llvm-project/libc/src/__support/freelist.h (revision d121d71fc7fcb8c969959147f5f58b31f9c6b251)
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.
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 
83 private:
84   Node *begin_;
85 };
86 
87 } // namespace LIBC_NAMESPACE_DECL
88 
89 #endif // LLVM_LIBC_SRC___SUPPORT_FREELIST_H
90