1 // Radix trees. Supports mapping from integer keys to objects, and optionally
4 // lockless lookups, the radix tree nodes are only added, never removed. The
5 // caller must ensure the synchronization of allocation and deallocation.
7 // Written by Scott Wood <scott@buserror.net>.
9 // This software is provided 'as-is', without any express or implied warranty.
10 // In no event will the authors or contributors be held liable for any damages
11 // arising from the use of this software.
13 // This software is in the public domain.
22 #include <lowlevel/bitops.h>
31 struct RefHandle : public Handle<T> {
35 // Each node in the tree will contain 2**radix_bits handles.
36 template <typename T, int radix_bits>
38 typedef unsigned int Key;
41 node_size = 1 << radix_bits,
42 long_bits = sizeof(unsigned long) * 8;
43 bitmap_len = (node_size - 1) / long_bits + 1,
44 twolevel_bitmap = bitmap_len > 4
49 unsigned long bmap[bitmap_len + twolevel_bitmap];
53 memset(bmap, 0, sizeof(bmap));
56 // Find the first free entry in this node.
57 // Returns -1 if none found.
60 if (twolevel_bitmap) {
64 return ll_ffs(~bmap[ll_ffs(~bmap[0]) + 1]);
67 return ll_multiword_ffc(bmap, 0, node_size);
71 struct Node : public NodeBase {
77 memset(handles, 0, sizeof(handles));
81 struct DirNode : public NodeBase {
82 void *ptrs[node_size];
84 DirNode(int SHIFT) : shift(SHIFT)
86 memset(ptrs, 0, sizeof(ptrs));
92 static int key_to_offset(Key key, int shift)
94 return (key >> shift) & (node_size - 1);
98 T *lookup(Key key, bool add = false)
100 Node *node = toplevel;
102 while (unlikely(!toplevel || key_to_offset(key, toplevel->shift +
111 Node *new_node = new DirNode(toplevel->shift + radix_bits);
112 new_node->ptrs[0] = toplevel;
117 while (shift >= radix_bits) {
118 int off = key_to_offset(key, shift);
119 void *new_node = static_cast<void **>(node)[off];
125 new_node = Mem::alloc_pages(1);
126 memset(new_node, 0, Arch::page_size);
127 static_cast<void **>(node)[off] = new_node;
135 return static_cast<T *>(node) + key_to_offset(key, 0);
140 toplevel = Mem::alloc_pages(1);
141 memset(toplevel, 0, Arch::page_size);