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 nodes.
22 // Each directory node will contain 2**dir_bits pointers.
23 // Key must be an unsigned integer.
25 template <typename T, typename Key, int radix_bits,
26 int dir_bits = radix_bits>
29 node_size = 1 << radix_bits,
30 dir_size = 1 << dir_bits,
31 key_bits = sizeof(Key) * 8,
38 Node(int SHIFT) : shift(SHIFT)
43 struct LeafNode : public Node {
48 memset(nodes, 0, sizeof(nodes));
52 struct DirNode : public Node {
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 // The tree depth is contained in each node, and nodes are never
75 // removed from the tree, so lockless lookups are possible.
76 // Synchronization is required when add == true.
78 T *lookup(Key key, bool add = false)
80 Node *node = toplevel;
81 int next_shift = node->shift ? node->shift + dir_bits : radix_bits;
83 while (unlikely(next_shift < key_bits && (key >> next_shift)))
88 DirNode *dn = new DirNode(next_shift);
91 next_shift += dir_bits;
96 while (node->shift > 0) {
97 int off = key_to_dir_offset(key, node->shift);
98 DirNode *dn = static_cast<DirNode *>(node);
105 if (dn->shift == radix_bits)
108 node = new DirNode(dn->shift == radix_bits ?
109 0 : dn->shift - dir_bits);
111 dn->ptrs[off] = node;
115 LeafNode *ln = static_cast<LeafNode *>(node);
116 return &ln->nodes[key_to_offset(key)];
121 // OPT: start with a NULL toplevel. Besides avoiding wasting
122 // memory for empty trees, it avoids the need for a stack of
123 // trees down the ptr[0] path if there are no small keys.
125 toplevel = new LeafNode;