1//===-- Interface for freetrie --------------------------------------------===//
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_FREETRIE_H
10#define LLVM_LIBC_SRC___SUPPORT_FREETRIE_H
11
12#include "freelist.h"
13
14namespace LIBC_NAMESPACE_DECL {
15
16/// A trie of free lists.
17///
18/// This is an unusual little data structure originally from Doug Lea's malloc.
19/// Finding the best fit from a set of differently-sized free list typically
20/// required some kind of ordered map, and these are typically implemented using
21/// a self-balancing binary search tree. Those are notorious for having a
22/// relatively large number of special cases, while this trie has relatively
23/// few, which helps with code size.
24///
25/// Operations on the trie are logarithmic not on the number of nodes within it,
26/// but rather the fixed range of possible sizes that the trie can contain. This
27/// means that the data structure would likely actually perform worse than an
28/// e.g. red-black tree, but its implementation is still much simpler.
29///
30/// Each trie node's children subdivide the range of possible sizes into two
31/// halves: a lower and an upper. The node itself holds a free list of some size
32/// within its range. This makes it possible to summarily replace any node with
33/// any leaf within its subtrie, which makes it very straightforward to remove a
34/// node. Insertion is also simple; the only real complexity lies with finding
35/// the best fit. This can still be done in logarithmic time with only a few
36/// cases to consider.
37///
38/// The trie refers to, but does not own, the Nodes that comprise it.
39class FreeTrie {
40public:
41 /// A trie node that is also a free list. Only the head node of each list is
42 /// actually part of the trie. The subtrie contains a continous SizeRange of
43 /// free lists. The lower and upper subtrie's contain the lower and upper half
44 /// of the subtries range. There is no direct relationship between the size of
45 /// this node's free list and the contents of the lower and upper subtries.
46 class Node : public FreeList::Node {
47 /// The child subtrie covering the lower half of this subtrie's size range.
48 /// Undefined if this is not the head of the list.
49 Node *lower;
50 /// The child subtrie covering the upper half of this subtrie's size range.
51 /// Undefined if this is not the head of the list.
52 Node *upper;
53 /// The parent subtrie. nullptr if this is the root or not the head of the
54 /// list.
55 Node *parent;
56
57 friend class FreeTrie;
58 };
59
60 /// Power-of-two range of sizes covered by a subtrie.
61 struct SizeRange {
62 size_t min;
63 size_t width;
64
65 LIBC_INLINE constexpr SizeRange(size_t min, size_t width)
66 : min(min), width(width) {
67 LIBC_ASSERT(!(width & (width - 1)) && "width must be a power of two");
68 }
69
70 /// @returns The lower half of the size range.
71 LIBC_INLINE SizeRange lower() const { return {min, width / 2}; }
72
73 /// @returns The upper half of the size range.
74 LIBC_INLINE SizeRange upper() const { return {min + width / 2, width / 2}; }
75
76 /// @returns The largest size in this range.
77 LIBC_INLINE size_t max() const { return min + (width - 1); }
78
79 /// @returns Whether the range contains the given size.
80 LIBC_INLINE bool contains(size_t size) const {
81 return min <= size && size < min + width;
82 }
83 };
84
85 LIBC_INLINE constexpr FreeTrie() : FreeTrie(SizeRange{0, 0}) {}
86 LIBC_INLINE constexpr FreeTrie(SizeRange range) : range(range) {}
87
88 /// Sets the range of possible block sizes. This can only be called when the
89 /// trie is empty.
90 LIBC_INLINE void set_range(FreeTrie::SizeRange range) {
91 LIBC_ASSERT(empty() && "cannot change the range of a preexisting trie");
92 this->range = range;
93 }
94
95 /// @returns Whether the trie contains any blocks.
96 LIBC_INLINE bool empty() const { return !root; }
97
98 /// Push a block to the trie.
99 void push(Block *block);
100
101 /// Remove a node from this trie node's free list.
102 void remove(Node *node);
103
104 /// @returns A smallest node that can allocate the given size; otherwise
105 /// nullptr.
106 Node *find_best_fit(size_t size);
107
108private:
109 /// @returns Whether a node is the head of its containing freelist.
110 bool is_head(Node *node) const { return node->parent || node == root; }
111
112 /// Replaces references to one node with another (or nullptr) in all adjacent
113 /// parent and child nodes.
114 void replace_node(Node *node, Node *new_node);
115
116 Node *root = nullptr;
117 SizeRange range;
118};
119
120LIBC_INLINE void FreeTrie::push(Block *block) {
121 LIBC_ASSERT(block->inner_size_free() >= sizeof(Node) &&
122 "block too small to accomodate free trie node");
123 size_t size = block->inner_size();
124 LIBC_ASSERT(range.contains(size) && "requested size out of trie range");
125
126 // Find the position in the tree to push to.
127 Node **cur = &root;
128 Node *parent = nullptr;
129 SizeRange cur_range = range;
130 while (*cur && (*cur)->size() != size) {
131 LIBC_ASSERT(cur_range.contains(size) && "requested size out of trie range");
132 parent = *cur;
133 if (size <= cur_range.lower().max()) {
134 cur = &(*cur)->lower;
135 cur_range = cur_range.lower();
136 } else {
137 cur = &(*cur)->upper;
138 cur_range = cur_range.upper();
139 }
140 }
141
142 Node *node = new (block->usable_space()) Node;
143 FreeList list = *cur;
144 if (list.empty()) {
145 node->parent = parent;
146 node->lower = node->upper = nullptr;
147 } else {
148 node->parent = nullptr;
149 }
150 list.push(node);
151 *cur = static_cast<Node *>(list.begin());
152}
153
154LIBC_INLINE FreeTrie::Node *FreeTrie::find_best_fit(size_t size) {
155 if (empty() || range.max() < size)
156 return nullptr;
157
158 Node *cur = root;
159 SizeRange cur_range = range;
160 Node *best_fit = nullptr;
161 Node *deferred_upper_trie = nullptr;
162 FreeTrie::SizeRange deferred_upper_range{0, 0};
163
164 while (true) {
165 LIBC_ASSERT(cur_range.contains(cur->size()) &&
166 "trie node size out of range");
167 LIBC_ASSERT(cur_range.max() >= size &&
168 "range could not fit requested size");
169 LIBC_ASSERT((!best_fit || cur_range.min < best_fit->size()) &&
170 "range could not contain a best fit");
171
172 // If the current node is an exact fit, it is a best fit.
173 if (cur->size() == size)
174 return cur;
175
176 if (cur->size() > size && (!best_fit || cur->size() < best_fit->size())) {
177 // The current node is a better fit.
178 best_fit = cur;
179
180 // If there is a deferred upper subtrie, then the current node is
181 // somewhere in its lower sibling subtrie. That means that the new best
182 // fit is better than the best fit in the deferred subtrie.
183 LIBC_ASSERT(
184 (!deferred_upper_trie ||
185 deferred_upper_range.min > best_fit->size()) &&
186 "deferred upper subtrie should be outclassed by new best fit");
187 deferred_upper_trie = nullptr;
188 }
189
190 // Determine which subtries might contain the best fit.
191 bool lower_impossible = !cur->lower || cur_range.lower().max() < size;
192 bool upper_impossible =
193 !cur->upper ||
194 // If every node in the lower trie fits
195 (!lower_impossible && cur_range.min >= size) ||
196 // If every node in the upper trie is worse than the current best
197 (best_fit && cur_range.upper().min >= best_fit->size());
198
199 if (lower_impossible && upper_impossible) {
200 if (!deferred_upper_trie)
201 return best_fit;
202 // Scan the deferred upper subtrie and consider whether any element within
203 // provides a better fit.
204 //
205 // This can only ever be reached once. In a deferred upper subtrie, every
206 // node fits, so the higher of two subtries can never contain a best fit.
207 cur = deferred_upper_trie;
208 cur_range = deferred_upper_range;
209 deferred_upper_trie = nullptr;
210 continue;
211 }
212
213 if (lower_impossible) {
214 cur = cur->upper;
215 cur_range = cur_range.upper();
216 } else if (upper_impossible) {
217 cur = cur->lower;
218 cur_range = cur_range.lower();
219 } else {
220 // Both subtries might contain a better fit. Any fit in the lower subtrie
221 // is better than the any fit in the upper subtrie, so scan the lower
222 // and return to the upper only if no better fits were found. (Any better
223 // fit found clears the deferred upper subtrie.)
224 LIBC_ASSERT((!deferred_upper_trie ||
225 cur_range.upper().max() < deferred_upper_range.min) &&
226 "old deferred upper subtrie should be outclassed by new");
227 deferred_upper_trie = cur->upper;
228 deferred_upper_range = cur_range.upper();
229 cur = cur->lower;
230 cur_range = cur_range.lower();
231 }
232 }
233}
234
235} // namespace LIBC_NAMESPACE_DECL
236
237#endif // LLVM_LIBC_SRC___SUPPORT_FREETRIE_H
238

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