random kernel stuff

[polintos/scott/priv.git] / kernel / include / kern / radix.h

diff --git a/kernel/include/kern/radix.h b/kernel/include/kern/radix.h
index 1399356b589bc9167cb5e21247e49d8551452560..f596fea6f4b46403a6448a01d191511fb4b9ce7f 100644 (file)
--- a/kernel/include/kern/radix.h
+++ b/kernel/include/kern/radix.h
@@ -1,7 +1,7 @@
-// Generic radix tree implementation.  It's only kernel-specific because
-// it uses the kernel page allocator; each node takes up one page.  The
-// depth of the tree is dynamically growable (but not currently
-// shrinkable).
+// This is like RadixTree, but it uses the kernel page allocator; each
+// node takes up one page.  The depth of the tree is dynamically growable
+// (but not currently shrinkable).  It also auto-guesses radix_bits based
+// on the size of T, so as to fit a page.
 
 #ifndef _KERN_RADIX_H
 #define _KERN_RADIX_H
@@ -17,7 +17,7 @@
 namespace Util {
        // Key must be an integer.
        template <typename T, typename Key>
-       class RadixTree {
+       class PageRadixTree {
                void *toplevel;
                uint depth; // in bits
                
@@ -85,11 +85,12 @@ namespace Util {
                                node = new_node;
                        }
                        
-                       assert(shift == RADIX_final_shift - dir_shift);
-                       return static_cast<T *>(node) + key_to_offset(key);
+                       assert(shift == 0 || shift == RADIX_final_shift - dir_shift);
+                       return (T *)((unsigned long)node +
+                                    (key_to_offset(key) << RADIX_data_bits));
                }
                
-               RadixTree()
+               PageRadixTree()
                {
                        toplevel = Mem::alloc_pages(1);
                        bzero(toplevel, Arch::page_size);