xfer to laptop
authorScott Wood <scott@buserror.net>
Tue, 20 Mar 2007 13:35:22 +0000 (08:35 -0500)
committerScott Wood <scott@buserror.net>
Tue, 20 Mar 2007 13:35:22 +0000 (08:35 -0500)
include/c++/util/handle.h [new file with mode: 0644]
include/c++/util/radix.h [new file with mode: 0644]
include/c/std/string.h
kernel/include/kern/orb.h
kernel/orb/invoke.cc

diff --git a/include/c++/util/handle.h b/include/c++/util/handle.h
new file mode 100644 (file)
index 0000000..b22648e
--- /dev/null
@@ -0,0 +1,147 @@
+// Radix trees.  Supports mapping from integer keys to objects, and optionally
+// 
+  To allow
+// lockless lookups, the radix tree nodes are only added, never removed.  The
+// caller must ensure the synchronization of allocation and deallocation.
+//
+// Written by Scott Wood <scott@buserror.net>.
+// 
+// This software is provided 'as-is', without any express or implied warranty.
+// In no event will the authors or contributors be held liable for any damages
+// arising from the use of this software.
+// 
+// This software is in the public domain.
+
+#ifndef _UTIL_RADIX_H
+#define _UTIL_RADIX_H
+
+#include <assert.h>
+#include <stddef.h>
+#include <stdint.h>
+
+#include <lowlevel/bitops.h>
+
+namespace Util {
+       template <typename T>
+       struct Handle {
+               T *ptr;
+       };
+
+       template <typename T>
+       struct RefHandle : public Handle<T> {
+               unsigned int ref;
+       };
+
+       // Each node in the tree will contain 2**radix_bits handles.
+       template <typename T, int radix_bits>
+       class RadixTree {
+               typedef unsigned int Key;
+
+               enum {
+                       node_size = 1 << radix_bits,
+                       long_bits = sizeof(unsigned long) * 8;
+                       bitmap_len = (node_size - 1) / long_bits + 1,
+                       twolevel_bitmap = bitmap_len > 4
+               };
+               
+               struct NodeBase {
+                       int shift;
+                       unsigned long bmap[bitmap_len + twolevel_bitmap];
+                       
+                       NodeBase()
+                       {
+                               memset(bmap, 0, sizeof(bmap));
+                       }
+                       
+                       // Find the first free entry in this node.
+                       // Returns -1 if none found.
+                       int find_first()
+                       {
+                               if (twolevel_bitmap) {
+                                       if (~bmap[0] == 0)
+                                               return -1;
+                               
+                                       return ll_ffs(~bmap[ll_ffs(~bmap[0]) + 1]);
+                               }
+
+                               return ll_multiword_ffc(bmap, 0, node_size);
+                       }
+               };
+               
+               struct Node : public NodeBase {
+                       T handles[node_size];
+                       
+                       Node()
+                       {
+                               shift = 0;
+                               memset(handles, 0, sizeof(handles));
+                       }
+               };
+               
+               struct DirNode : public NodeBase {
+                       void *ptrs[node_size];
+
+                       DirNode(int SHIFT) : shift(SHIFT)
+                       {
+                               memset(ptrs, 0, sizeof(ptrs));
+                       }
+               };
+       
+               NodeBase *toplevel;
+               
+               static int key_to_offset(Key key, int shift)
+               {
+                       return (key >> shift) & (node_size - 1);
+               }
+
+       public:
+               T *lookup(Key key, bool add = false)
+               {
+                       Node *node = toplevel;
+                       
+                       while (unlikely(!toplevel || key_to_offset(key, toplevel->shift +
+                                                                  radix_bits) != 0))
+                       {
+                               if (!add)
+                                       return NULL;
+                               
+                               if (!toplevel) {
+                                       toplevel = new Node;
+                               } else {
+                                       Node *new_node = new DirNode(toplevel->shift + radix_bits);
+                                       new_node->ptrs[0] = toplevel;
+                                       toplevel = new_node;
+                               }
+                       }
+
+                       while (shift >= radix_bits) {
+                               int off = key_to_offset(key, 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;
+                               }
+                               
+                               shift -= dir_shift;
+                               node = new_node;
+                       }
+                       
+                       assert(shift == 0);
+                       return static_cast<T *>(node) + key_to_offset(key, 0);
+               }
+               
+               RadixTree()
+               {
+                       toplevel = Mem::alloc_pages(1);
+                       memset(toplevel, 0, Arch::page_size);
+                       depth = 0;
+               }
+       };
+}
+
+#endif
diff --git a/include/c++/util/radix.h b/include/c++/util/radix.h
new file mode 100644 (file)
index 0000000..b75d27e
--- /dev/null
@@ -0,0 +1,126 @@
+// Generic radix trees, which supports mapping integer keys to objects.
+//
+// Written by Scott Wood <scott@buserror.net>.
+// 
+// This software is provided 'as-is', without any express or implied warranty.
+// In no event will the authors or contributors be held liable for any damages
+// arising from the use of this software.
+// 
+// This software is in the public domain.
+
+#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 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;
+
+               enum {
+                       node_size = 1 << radix_bits,
+                       dir_size = 1 << dir_bits,
+                       long_bits = sizeof(unsigned long) * 8,
+               };
+               
+               struct Node {
+                       const int shift;
+                       
+               protected:
+                       Node(int SHIFT) : shift(SHIFT)
+                       {
+                       }
+               };
+               
+               struct LeafNode : public Node {
+                       T handles[node_size];
+                       
+                       LeafNode() : Node(0)
+                       {
+                               shift = 0;
+                               memset(handles, 0, sizeof(handles));
+                       }
+               };
+               
+               struct DirNode : public Node {
+                       Node *ptrs[node_size];
+
+                       DirNode(int shift) : Node(shift)
+                       {
+                               memset(ptrs, 0, sizeof(ptrs));
+                       }
+               };
+       
+               Node *toplevel;
+               
+               static int key_to_dir_offset(Key key, int shift)
+               {
+                       return (key >> shift) & (dir_size - 1);
+               }
+
+               static uint key_to_offset(Key key)
+               {
+                       return key & (node_size - 1);
+               }
+
+       public:
+               T *lookup(Key key, bool add = false)
+               {
+                       int next_shift = toplevel->shift == 0 ? radix_bits : dir_bits;
+                       
+                       while (unlikely(key_to_dir_offset(key, toplevel->shift +
+                                                              next_shift) != 0))
+                       {
+                               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;
+                       }
+                       
+                       Node *node = toplevel;
+                       
+                       while (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;
+                               }
+                               
+                               shift -= dir_shift;
+                               node = new_node;
+                       }
+                       
+                       assert(shift == 0);
+                       return static_cast<T *>(node) + key_to_offset(key, 0);
+               }
+               
+               RadixTree()
+               {
+                       toplevel = new LeafNode;
+                       memset(toplevel, 0, Arch::page_size);
+                       depth = 0;
+               }
+       };
+}
+
+#endif
index 33cd4a717a1a302d5e0e83dd21520f57be0bac6b..31323c6419fc782c4fe6dddd0b309de7229e0507 100644 (file)
@@ -7,6 +7,7 @@
 extern "C" {
 #endif
 
+void *memset(void *block, int count, size_t len);
 int memcmp(const void *b1, const void *b2, size_t len);
 size_t strlen(const char *s);
 
index b00d758fbcf1c671e4a297d933a0136d5e7e28f8..e420fc77e11f72e10597797808a6146b36288f49 100644 (file)
@@ -81,11 +81,11 @@ namespace ORB {
 
        class IDSpace {
                // Reverse mapping of object pointers to local IDs
-               IDRMap id_rmap;
+               IDRMap idrmap;
        
        public:
                Object *lookup(u32 id);
-               u32 rlookup(Object *obj);
+               ObjectHdr *get_local_hdr(Object *obj);
        };
 }
 
index 2e1440f57fea9029db0a90851de5cce4683eaab3..27a1ebe1612a2a1a1ffc7e2fec0f8888c38ff5b7 100644 (file)
@@ -47,17 +47,14 @@ namespace ORB {
                return &hdr->frames[++thread->orbstack_top];
        }
        
-       u32 IDSpace::rlookup(Object *obj)
+       ObjectHdr *IDSpace::get_local_hdr(Object *obj)
        {
-#if 0
-               ObjectHdr *hdr = idtree.find(obj);
+               ObjectHdr *hdr = idrmap.lookup(obj->id);
                
                if (!hdr)
                        return 0;
                
                return hdr->id;
-#endif
-               return 0;
        }
 }