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
14namespace 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.
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(node: 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_DECL
88
89#endif // LLVM_LIBC_SRC___SUPPORT_FREELIST_H
90

source code of libc/src/__support/freelist.h