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.
16 #include <lowlevel/bitops.h>
19 // Each leaf node in the tree will contain 2**radix_bits nodes.
20 // Each directory node will contain 2**dir_bits pointers.
21 // Key must be an unsigned integer.
23 template <typename T, typename Key, int radix_bits,
24 int dir_bits = radix_bits>
27 node_size = 1 << radix_bits,
28 dir_size = 1 << dir_bits,
29 key_bits = sizeof(Key) * 8,
36 Node(int SHIFT) : shift(SHIFT)
41 struct LeafNode : public Node {
46 memset(nodes, 0, sizeof(nodes));
50 struct DirNode : public Node {
53 DirNode(int shift) : Node(shift)
55 memset(ptrs, 0, sizeof(ptrs));
61 static int key_to_dir_offset(Key key, int shift)
63 return (key >> shift) & (dir_size - 1);
66 static unsigned int key_to_offset(Key key)
68 return key & (node_size - 1);
72 // The tree depth is contained in each node, and nodes are never
73 // removed from the tree, so lockless lookups are possible.
74 // Synchronization is required when add == true.
76 T *lookup(Key key, bool add = false)
78 Node *node = toplevel;
79 int next_shift = node->shift ? node->shift + dir_bits : radix_bits;
81 while (unlikely(next_shift < key_bits && (key >> next_shift)))
86 DirNode *dn = new DirNode(next_shift);
89 next_shift += dir_bits;
94 while (node->shift > 0) {
95 int off = key_to_dir_offset(key, node->shift);
96 DirNode *dn = static_cast<DirNode *>(node);
103 if (dn->shift == radix_bits)
106 node = new DirNode(dn->shift == radix_bits ?
107 0 : dn->shift - dir_bits);
109 dn->ptrs[off] = node;
113 LeafNode *ln = static_cast<LeafNode *>(node);
114 return &ln->nodes[key_to_offset(key)];
119 // OPT: start with a NULL toplevel. Besides avoiding wasting
120 // memory for empty trees, it avoids the need for a stack of
121 // trees down the ptr[0] path if there are no small keys.
123 toplevel = new LeafNode;