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.
24 template <typename T, int radix_bits, int dir_bits = radix_bits>
26 typedef unsigned int Key;
29 node_size = 1 << radix_bits,
30 dir_size = 1 << dir_bits,
31 long_bits = sizeof(unsigned long) * 8,
38 Node(int SHIFT) : shift(SHIFT)
43 struct LeafNode : public Node {
49 memset(handles, 0, sizeof(handles));
53 struct DirNode : public Node {
54 Node *ptrs[node_size];
56 DirNode(int shift) : Node(shift)
58 memset(ptrs, 0, sizeof(ptrs));
64 static int key_to_dir_offset(Key key, int shift)
66 return (key >> shift) & (dir_size - 1);
69 static uint key_to_offset(Key key)
71 return key & (node_size - 1);
75 // The tree depth is contained in each node, and nodes are never
76 // removed from the tree, so lockless lookups are possible.
77 // Synchronization is required when add == true.
79 T *lookup(Key key, bool add = false)
81 int next_shift = toplevel->shift == 0 ? radix_bits : dir_bits;
83 while (unlikely(key_to_dir_offset(key, toplevel->shift +
89 Node *new_node = new DirNode(toplevel->shift + next_shift);
90 new_node->ptrs[0] = toplevel;
92 next_shift = dir_bits;
95 Node *node = toplevel;
97 while (node->shift > 0) {
98 assert(node->shift >= radix_bits);
100 int off = key_to_dir_offset(key, node->shift);
101 NodeBase *new_node = node[off];
107 if (node->shift == radix_bits)
108 new_node = new LeafNode;
110 new_node = new DirNode(node->shift - dir_shift);
112 node[off] = new_node;
118 assert(node->shift == 0);
119 return node[key_to_offset(key)];
124 toplevel = new LeafNode;