1 // Generic radix trees, which supports mapping integer keys to objects.
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.
18 #include <lowlevel/bitops.h>
21 // Each leaf node in the tree will contain 2**radix_bits handles.
22 // Each directory node will contain 2**dir_bits pointers.
23 template <typename T, int radix_bits, int dir_bits = radix_bits>
25 typedef unsigned int Key;
28 node_size = 1 << radix_bits,
29 dir_size = 1 << dir_bits,
30 long_bits = sizeof(unsigned long) * 8,
37 Node(int SHIFT) : shift(SHIFT)
42 struct LeafNode : public Node {
48 memset(handles, 0, sizeof(handles));
52 struct DirNode : public Node {
53 Node *ptrs[node_size];
55 DirNode(int shift) : Node(shift)
57 memset(ptrs, 0, sizeof(ptrs));
63 static int key_to_dir_offset(Key key, int shift)
65 return (key >> shift) & (dir_size - 1);
68 static uint key_to_offset(Key key)
70 return key & (node_size - 1);
74 T *lookup(Key key, bool add = false)
76 int next_shift = toplevel->shift == 0 ? radix_bits : dir_bits;
78 while (unlikely(key_to_dir_offset(key, toplevel->shift +
84 Node *new_node = new DirNode(toplevel->shift + next_shift);
85 new_node->ptrs[0] = toplevel;
87 next_shift = dir_bits;
90 Node *node = toplevel;
92 while (node->shift >= radix_bits) {
93 int off = key_to_dir_offset(key, node->shift);
94 NodeBase *new_node = node[off];
96 shift == 0 ? new LeafNode
98 void *new_node = static_cast<void **>(node)[off];
104 new_node = Mem::alloc_pages(1);
105 memset(new_node, 0, Arch::page_size);
106 static_cast<void **>(node)[off] = new_node;
114 return static_cast<T *>(node) + key_to_offset(key, 0);
119 toplevel = new LeafNode;
120 memset(toplevel, 0, Arch::page_size);