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 // Key must be an integer type
23 template <typename Key>
26 node_size = sizeof(unsigned long) * 8;
27 radix_bits = _LL_LONG_LOGBYTES + 3;
31 unsigned long index_bmap;
35 Node *nodes[node_size];
40 memset(nodes, 0, sizeof(nodes));
48 unsigned long nodes[node_size];
53 memset(nodes, 0, sizeof(nodes));
57 static uint key_to_offset(Key key, int shift)
59 return (key >> shift) & (node_size - 1);
63 // Returns -1 if none found.
64 Key alloc(int shift = toplevel_shift)
66 Node *node = toplevel;
69 assert (shift >= radix_bits);
71 if (~node->index_bmap == 0)
74 int off = ll_ffs(!node->index_bmap);
76 DirNode *dn = static_cast<DirNode *>(node);
77 node = dn->nodes[off];
80 if (shift == radix_bits)
85 dn->nodes[off] = node;
88 dn->index_bmap |= (1UL << off);
92 if (~index_bmap[0] == 0)
95 return ll_ffs(~bmap[ll_ffs(~bmap[0]) + 1]);