1 // Bitmap Tree Allocator
3 // Written by Scott Wood <scott@buserror.net>.
5 // This software is provided 'as-is', without any express or implied warranty.
6 // In no event will the authors or contributors be held liable for any damages
7 // arising from the use of this software.
9 // This software is in the public domain.
11 #ifndef _UTIL_BMAPTREE_H
12 #define _UTIL_BMAPTREE_H
18 #include <lowlevel/types.h>
19 #include <lowlevel/bitops.h>
22 #include <System/Exceptions.h>
25 // Key must be an unsigned integer type.
26 template <typename Key>
29 node_size = sizeof(unsigned long) * 8,
30 radix_bits = _LL_LONG_LOGBYTES + 3,
31 key_bits = sizeof(Key) * 8,
35 unsigned long index_bmap;
37 Node() : index_bmap(0)
42 struct DirNode : public Node {
43 Node *nodes[node_size];
47 memset(nodes, 0, sizeof(nodes));
54 struct LeafNode : public Node {
55 unsigned long nodes[node_size];
59 memset(nodes, 0, sizeof(nodes));
63 static uint key_to_offset(Key key, int shift)
65 return (key >> shift) & (node_size - 1);
69 // max_key must be positive. Modifications must be synchronized with
70 // alloc() and free(), but are otherwise unrestricted (including
71 // reducing it below already allocated keys).
76 Key rec_alloc(Node *node, int shift, bool *full)
78 assert(~node->index_bmap != 0);
79 int off = ll_ffs(!node->index_bmap);
80 Key key = ((Key)off) << shift;
82 if (shift > radix_bits) {
83 assert(shift >= radix_bits * 2);
86 throw_idl(::System::Exceptions::Std::OutOfSpace,
87 ::System::RunTime::nullarray);
89 DirNode *dn = static_cast<DirNode *>(node);
90 Node *new_node = dn->nodes[off];
92 if (unlikely(!new_node)) {
93 if (shift == radix_bits * 2)
94 new_node = new LeafNode;
96 new_node = new DirNode;
98 dn->nodes[off] = new_node;
101 bool sub_full = false;
102 key += rec_alloc(new_node, shift - radix_bits, &sub_full);
105 dn->index_bmap |= 1UL << off;
107 assert(shift == radix_bits);
109 LeafNode *ln = static_cast<LeafNode *>(node);
110 assert(~ln->nodes[off] != 0);
112 int leaf_bit = ll_ffs(ln->nodes[off]);
113 key |= ((Key)1) << leaf_bit;
116 throw_idl(::System::Exceptions::Std::OutOfSpace,
117 ::System::RunTime::nullarray);
119 ln->nodes[off] |= 1UL << leaf_bit;
121 if (~ln->nodes[off] == 0)
122 ln->index_bmap |= 1UL << off;
125 if (~node->index_bmap == 0 && full)
132 // Throws System::Exceptions::Std::OutOfSpace on failure
135 if (unlikely(~toplevel->index_bmap == 0)) {
136 int new_shift = toplevel_shift + radix_bits;
138 if (new_shift >= key_bits ||
139 (((Key)1) << new_shift) >= max_key)
140 throw_idl(::System::Exceptions::Std::OutOfSpace,
141 ::System::RunTime::nullarray);
143 DirNode *dn = new DirNode;
144 dn->nodes[0] = toplevel;
145 toplevel_shift = new_shift;
149 return rec_alloc(toplevel, toplevel_shift, NULL);
152 // Throws System::InvalidArgument if key is already free
155 Node *node = toplevel;
156 int shift = toplevel_shift;
157 int max_bits = toplevel_shift + radix_bits;
159 if (max_bits < key_bits && key >= (((Key)1) << max_bits))
160 throw_idl(::System::Exceptions::Std::InvalidArgument, 0,
161 ::System::RunTime::nullarray);
163 while (shift > radix_bits) {
164 assert(shift >= radix_bits * 2);
166 int off = key_to_offset(key, shift);
167 node->index_bmap &= ~(1UL << off);
169 DirNode *dn = static_cast<DirNode *>(node);
170 node = dn->nodes[off];
174 assert(shift == radix_bits);
176 int off = key_to_offset(key, radix_bits);
177 node->index_bmap &= ~(1UL << off);
179 LeafNode *ln = static_cast<LeafNode *>(node);
180 int bit = key_to_offset(key, 0);
182 if (!(ln->nodes[off] & (1UL << bit)))
183 throw_idl(::System::Exceptions::Std::InvalidArgument, 0,
184 ::System::RunTime::nullarray);
186 ln->nodes[off] &= ~(1UL << bit);
192 toplevel_shift = radix_bits;
193 toplevel = new LeafNode;