#ifndef _UTIL_RADIX_H
#define _UTIL_RADIX_H
-#include <assert.h>
#include <stddef.h>
#include <stdint.h>
-
#include <lowlevel/bitops.h>
namespace Util {
- // Each leaf node in the tree will contain 2**radix_bits handles.
+ // Each leaf node in the tree will contain 2**radix_bits nodes.
// Each directory node will contain 2**dir_bits pointers.
- template <typename T, int radix_bits, int dir_bits = radix_bits>
- class RadixTree {
- typedef unsigned int Key;
+ // Key must be an unsigned integer.
+ template <typename T, typename Key, int radix_bits,
+ int dir_bits = radix_bits>
+ class RadixTree {
enum {
node_size = 1 << radix_bits,
dir_size = 1 << dir_bits,
- long_bits = sizeof(unsigned long) * 8,
+ key_bits = sizeof(Key) * 8,
};
struct Node {
};
struct LeafNode : public Node {
- T handles[node_size];
+ T nodes[node_size];
LeafNode() : Node(0)
{
- shift = 0;
- memset(handles, 0, sizeof(handles));
+ memset(nodes, 0, sizeof(nodes));
}
};
struct DirNode : public Node {
- Node *ptrs[node_size];
+ Node *ptrs[dir_size];
DirNode(int shift) : Node(shift)
{
return (key >> shift) & (dir_size - 1);
}
- static uint key_to_offset(Key key)
+ static unsigned int key_to_offset(Key key)
{
return key & (node_size - 1);
}
-
+
public:
+ // The tree depth is contained in each node, and nodes are never
+ // removed from the tree, so lockless lookups are possible.
+ // Synchronization is required when add == true.
+
T *lookup(Key key, bool add = false)
{
- int next_shift = toplevel->shift == 0 ? radix_bits : dir_bits;
+ Node *node = toplevel;
+ int next_shift = node->shift ? node->shift + dir_bits : radix_bits;
- while (unlikely(key_to_dir_offset(key, toplevel->shift +
- next_shift) != 0))
+ while (unlikely(next_shift < key_bits && (key >> next_shift)))
{
if (!add)
return NULL;
- Node *new_node = new DirNode(toplevel->shift + next_shift);
- new_node->ptrs[0] = toplevel;
- toplevel = new_node;
- next_shift = dir_bits;
+ DirNode *dn = new DirNode(next_shift);
+ dn->ptrs[0] = node;
+ toplevel = dn;
+ next_shift += dir_bits;
}
- Node *node = toplevel;
+ node = toplevel;
- while (node->shift >= radix_bits) {
+ while (node->shift > 0) {
int off = key_to_dir_offset(key, node->shift);
- NodeBase *new_node = node[off];
-
- shift == 0 ? new LeafNode
- : new DirNode(shift);
- void *new_node = static_cast<void **>(node)[off];
+ DirNode *dn = static_cast<DirNode *>(node);
+ node = dn->ptrs[off];
- if (!new_node) {
+ if (!node) {
if (!add)
return NULL;
-
- new_node = Mem::alloc_pages(1);
- memset(new_node, 0, Arch::page_size);
- static_cast<void **>(node)[off] = new_node;
- }
- shift -= dir_shift;
- node = new_node;
+ if (dn->shift == radix_bits)
+ node = new LeafNode;
+ else
+ node = new DirNode(dn->shift == radix_bits ?
+ 0 : dn->shift - dir_bits);
+
+ dn->ptrs[off] = node;
+ }
}
- assert(shift == 0);
- return static_cast<T *>(node) + key_to_offset(key, 0);
+ LeafNode *ln = static_cast<LeafNode *>(node);
+ return &ln->nodes[key_to_offset(key)];
}
RadixTree()
{
+ // OPT: start with a NULL toplevel. Besides avoiding wasting
+ // memory for empty trees, it avoids the need for a stack of
+ // trees down the ptr[0] path if there are no small keys.
+
toplevel = new LeafNode;
- memset(toplevel, 0, Arch::page_size);
- depth = 0;
}
};
+
}
#endif