X-Git-Url: http://git.buserror.net/cgi-bin/gitweb.cgi?p=polintos%2Fscott%2Fpriv.git;a=blobdiff_plain;f=include%2Fc%2B%2B%2Futil%2Fradix.h;h=be982a504d3b4a32df4fef4c33640349c26bf6ae;hp=b75d27e79a5c06fcc1fad556505da6b70f9bd539;hb=b5cbe98949d5b279965d607c9618d404b26d4760;hpb=0c52a8435aa399781856869daa7ef30cef14fad5

diff --git a/include/c++/util/radix.h b/include/c++/util/radix.h
index b75d27e..be982a5 100644
--- 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