minor orb stuff

[polintos/scott/priv.git] / include / c++ / util / radix.h

diff --git a/include/c++/util/radix.h b/include/c++/util/radix.h
index b75d27e79a5c06fcc1fad556505da6b70f9bd539..be982a504d3b4a32df4fef4c33640349c26bf6ae 100644 (file)
--- a/include/c++/util/radix.h
+++ b/include/c++/util/radix.h
@@ -11,23 +11,22 @@
 #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 {
@@ -40,17 +39,16 @@ namespace Util {
                };
                
                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)
                        {
@@ -65,62 +63,67 @@ namespace Util {
                        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