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=48603f6aa012e4994a40458fa1e330aa9ea1ae71;hp=b75d27e79a5c06fcc1fad556505da6b70f9bd539;hb=58df1bd9b3448491714e5f6c1f571c4d1776d884;hpb=0c52a8435aa399781856869daa7ef30cef14fad5

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