--- /dev/null
+// Bitmap Tree Allocator
+//
+// 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_BMAPTREE_H
+#define _UTIL_BMAPTREE_H
+
+#include <assert.h>
+#include <stddef.h>
+#include <stdint.h>
+
+#include <lowlevel/types.h>
+#include <lowlevel/bitops.h>
+
+namespace Util {
+ // Key must be an integer type
+ template <typename Key>
+ class BitmapTree {
+ enum {
+ node_size = sizeof(unsigned long) * 8;
+ radix_bits = _LL_LONG_LOGBYTES + 3;
+ };
+
+ struct Node {
+ unsigned long index_bmap;
+ };
+
+ struct DirNode {
+ Node *nodes[node_size];
+
+ DirNode()
+ {
+ index_bmap = 0;
+ memset(nodes, 0, sizeof(nodes));
+ }
+ };
+
+ Node *toplevel;
+ int toplevel_shift;
+
+ struct LeafNode {
+ unsigned long nodes[node_size];
+
+ LeafNode()
+ {
+ index_bmap = 0;
+ memset(nodes, 0, sizeof(nodes));
+ }
+ };
+
+ static uint key_to_offset(Key key, int shift)
+ {
+ return (key >> shift) & (node_size - 1);
+ }
+
+ public:
+ // Returns -1 if none found.
+ Key alloc(int shift = toplevel_shift)
+ {
+ Node *node = toplevel;
+
+ if (shift > 0) {
+ assert (shift >= radix_bits);
+
+ if (~node->index_bmap == 0)
+ return -1;
+
+ int off = ll_ffs(!node->index_bmap);
+
+ DirNode *dn = static_cast<DirNode *>(node);
+ node = dn->nodes[off];
+
+ if (!new_node) {
+ if (shift == radix_bits)
+ node = new LeafNode;
+ else
+ node = new DirNode;
+
+ dn->nodes[off] = node;
+ }
+
+ dn->index_bmap |= (1UL << off);
+ shift -= radix_bits;
+ }
+
+ if (~index_bmap[0] == 0)
+ return -1;
+
+ return ll_ffs(~bmap[ll_ffs(~bmap[0]) + 1]);
+ }
+ };
+}
+
+#endif
+++ /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
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;
}
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;
- 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;
}
};
}
projects / polintos / scott / priv.git / commitdiff