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.
17 #include <lowlevel/bitops.h>
20 // Each leaf node in the tree will contain 2**radix_bits nodes.
21 // Each directory node will contain 2**dir_bits pointers.
22 // Key must be an unsigned integer.
24 template <typename T, typename Key, int radix_bits,
25 int dir_bits = radix_bits>
28 node_size = 1 << radix_bits,
29 dir_size = 1 << dir_bits,
30 key_bits = sizeof(Key) * 8,
37 Node(int SHIFT) : shift(SHIFT)
42 struct LeafNode : public Node {
47 memset(nodes, 0, sizeof(nodes));
51 struct DirNode : public Node {
54 DirNode(int shift) : Node(shift)
56 memset(ptrs, 0, sizeof(ptrs));
62 static int key_to_dir_offset(Key key, int shift)
64 return (key >> shift) & (dir_size - 1);
67 static unsigned int key_to_offset(Key key)
69 return key & (node_size - 1);
73 // The tree depth is contained in each node, and nodes are never
74 // removed from the tree, so lockless lookups are possible.
75 // Synchronization is required when add == true.
77 T *lookup(Key key, bool add = false)
79 Node *node = toplevel;
80 int next_shift = node->shift ? node->shift + dir_bits : radix_bits;
82 while (unlikely(next_shift < key_bits && (key >> next_shift)))
87 DirNode *dn = new DirNode(next_shift);
90 next_shift += dir_bits;
95 while (node->shift > 0) {
96 int off = key_to_dir_offset(key, node->shift);
97 DirNode *dn = static_cast<DirNode *>(node);
104 if (dn->shift == radix_bits)
107 node = new DirNode(dn->shift == radix_bits ?
108 0 : dn->shift - dir_bits);
110 dn->ptrs[off] = node;
114 LeafNode *ln = static_cast<LeafNode *>(node);
115 return &ln->nodes[key_to_offset(key)];
120 // OPT: start with a NULL toplevel. Besides avoiding wasting
121 // memory for empty trees, it avoids the need for a stack of
122 // trees down the ptr[0] path if there are no small keys.
124 toplevel = new LeafNode;