xfer to desktop

[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..48603f6aa012e4994a40458fa1e330aa9ea1ae71 100644 (file)
--- a/include/c++/util/radix.h
+++ b/include/c++/util/radix.h
@@ -20,6 +20,7 @@
 namespace Util {
        // Each leaf node in the tree will contain 2**radix_bits handles.
        // 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;
@@ -71,6 +72,10 @@ namespace Util {
                }
 
        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;
@@ -89,36 +94,34 @@ namespace Util {
                        
                        Node *node = toplevel;
                        
-                       while (node->shift >= radix_bits) {
+                       while (node->shift > 0) {
+                               assert(node->shift >= radix_bits);
+                       
                                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];
-                               
                                if (!new_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;
+                               
+                                       if (node->shift == radix_bits)
+                                               new_node = new LeafNode;
+                                       else
+                                               new_node = new DirNode(node->shift - dir_shift);
+
+                                       node[off] = new_node;
                                }
                                
-                               shift -= dir_shift;
                                node = new_node;
                        }
                        
-                       assert(shift == 0);
-                       return static_cast<T *>(node) + key_to_offset(key, 0);
+                       assert(node->shift == 0);
+                       return node[key_to_offset(key)];
                }
                
                RadixTree()
                {
                        toplevel = new LeafNode;
-                       memset(toplevel, 0, Arch::page_size);
-                       depth = 0;
                }
        };
 }