--- /dev/null
+// 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
--- /dev/null
+// 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
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);
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);
};
}
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;
}
}
projects / polintos / scott / priv.git / commitdiff