From: Scott Wood Date: Wed, 11 Apr 2007 23:58:42 +0000 (-0500) Subject: bmaptree and radix fixes X-Git-Url: http://git.buserror.net/cgi-bin/gitweb.cgi?p=polintos%2Fscott%2Fpriv.git;a=commitdiff_plain;h=6ef00363db1c75274dfcc188c778cb437d896034 bmaptree and radix fixes --- diff --git a/include/c++/util/bmaptree.h b/include/c++/util/bmaptree.h index 2342295..56b3bfa 100644 --- a/include/c++/util/bmaptree.h +++ b/include/c++/util/bmaptree.h @@ -18,25 +18,32 @@ #include #include +#include +#include + namespace Util { - // Key must be an integer type + // Key must be an unsigned integer type. template class BitmapTree { enum { - node_size = sizeof(unsigned long) * 8; - radix_bits = _LL_LONG_LOGBYTES + 3; + node_size = sizeof(unsigned long) * 8, + radix_bits = _LL_LONG_LOGBYTES + 3, + key_bits = sizeof(Key) * 8, }; struct Node { unsigned long index_bmap; + + Node() : index_bmap(0) + { + } }; - struct DirNode { + struct DirNode : public Node { Node *nodes[node_size]; DirNode() { - index_bmap = 0; memset(nodes, 0, sizeof(nodes)); } }; @@ -44,12 +51,11 @@ namespace Util { Node *toplevel; int toplevel_shift; - struct LeafNode { + struct LeafNode : public Node { unsigned long nodes[node_size]; LeafNode() { - index_bmap = 0; memset(nodes, 0, sizeof(nodes)); } }; @@ -59,40 +65,132 @@ namespace Util { return (key >> shift) & (node_size - 1); } - public: - // Returns -1 if none found. - Key alloc(int shift = toplevel_shift) + public: + // max_key must be positive. Modifications must be synchronized with + // alloc() and free(), but are otherwise unrestricted (including + // reducing it below already allocated keys). + + Key max_key; + + private: + Key rec_alloc(Node *node, int shift, bool *full) { - Node *node = toplevel; - - if (shift > 0) { - assert (shift >= radix_bits); - - if (~node->index_bmap == 0) - return -1; + assert(~node->index_bmap != 0); + int off = ll_ffs(!node->index_bmap); + Key key = ((Key)off) << shift; + + if (shift > radix_bits) { + assert(shift >= radix_bits * 2); - int off = ll_ffs(!node->index_bmap); + if (key >= max_key) + throw_idl(::System::Exceptions::Std::OutOfSpace, + ::System::RunTime::nullarray); DirNode *dn = static_cast(node); - node = dn->nodes[off]; + Node *new_node = dn->nodes[off]; - if (!new_node) { - if (shift == radix_bits) - node = new LeafNode; + if (unlikely(!new_node)) { + if (shift == radix_bits * 2) + new_node = new LeafNode; else - node = new DirNode; + new_node = new DirNode; - dn->nodes[off] = node; + dn->nodes[off] = new_node; } - dn->index_bmap |= (1UL << off); + bool sub_full = false; + key += rec_alloc(new_node, shift - radix_bits, &sub_full); + + if (sub_full) + dn->index_bmap |= 1UL << off; + } else { + assert(shift == radix_bits); + + LeafNode *ln = static_cast(node); + assert(~ln->nodes[off] != 0); + + int leaf_bit = ll_ffs(ln->nodes[off]); + key |= ((Key)1) << leaf_bit; + + if (key >= max_key) + throw_idl(::System::Exceptions::Std::OutOfSpace, + ::System::RunTime::nullarray); + + ln->nodes[off] |= 1UL << leaf_bit; + + if (~ln->nodes[off] == 0) + ln->index_bmap |= 1UL << off; + } + + if (~node->index_bmap == 0 && full) + *full = true; + + return key; + } + + public: + // Throws System::Exceptions::Std::OutOfSpace on failure + Key alloc() + { + if (unlikely(~toplevel->index_bmap == 0)) { + int new_shift = toplevel_shift + radix_bits; + + if (new_shift >= key_bits || + (((Key)1) << new_shift) >= max_key) + throw_idl(::System::Exceptions::Std::OutOfSpace, + ::System::RunTime::nullarray); + + DirNode *dn = new DirNode; + dn->nodes[0] = toplevel; + toplevel_shift = new_shift; + toplevel = dn; + } + + return rec_alloc(toplevel, toplevel_shift, NULL); + } + + // Throws System::InvalidArgument if key is already free + void free(Key key) + { + Node *node = toplevel; + int shift = toplevel_shift; + int max_bits = toplevel_shift + radix_bits; + + if (max_bits < key_bits && key >= (((Key)1) << max_bits)) + throw_idl(::System::Exceptions::Std::InvalidArgument, 0, + ::System::RunTime::nullarray); + + while (shift > radix_bits) { + assert(shift >= radix_bits * 2); + + int off = key_to_offset(key, shift); + node->index_bmap &= ~(1UL << off); + + DirNode *dn = static_cast(node); + node = dn->nodes[off]; shift -= radix_bits; } - if (~index_bmap[0] == 0) - return -1; + assert(shift == radix_bits); + + int off = key_to_offset(key, radix_bits); + node->index_bmap &= ~(1UL << off); - return ll_ffs(~bmap[ll_ffs(~bmap[0]) + 1]); + LeafNode *ln = static_cast(node); + int bit = key_to_offset(key, 0); + + if (!(ln->nodes[off] & (1UL << bit))) + throw_idl(::System::Exceptions::Std::InvalidArgument, 0, + ::System::RunTime::nullarray); + + ln->nodes[off] &= ~(1UL << bit); + } + + BitmapTree() + { + max_key = ~(Key)0; + toplevel_shift = radix_bits; + toplevel = new LeafNode; } }; } diff --git a/include/c++/util/radix.h b/include/c++/util/radix.h index 48603f6..3dcaaaf 100644 --- a/include/c++/util/radix.h +++ b/include/c++/util/radix.h @@ -18,17 +18,17 @@ #include namespace Util { - // Each leaf node in the tree will contain 2**radix_bits handles. + // Each leaf node in the tree will contain 2**radix_bits nodes. // Each directory node will contain 2**dir_bits pointers. - - template - class RadixTree { - typedef unsigned int Key; + // Key must be an unsigned integer. + template + class RadixTree { enum { node_size = 1 << radix_bits, dir_size = 1 << dir_bits, - long_bits = sizeof(unsigned long) * 8, + key_bits = sizeof(Key) * 8, }; struct Node { @@ -41,17 +41,16 @@ namespace Util { }; struct LeafNode : public Node { - T handles[node_size]; + T nodes[node_size]; LeafNode() : Node(0) { - shift = 0; - memset(handles, 0, sizeof(handles)); + memset(nodes, 0, sizeof(nodes)); } }; struct DirNode : public Node { - Node *ptrs[node_size]; + Node *ptrs[dir_size]; DirNode(int shift) : Node(shift) { @@ -70,7 +69,7 @@ namespace Util { { return key & (node_size - 1); } - + public: // The tree depth is contained in each node, and nodes are never // removed from the tree, so lockless lookups are possible. @@ -78,52 +77,55 @@ namespace Util { T *lookup(Key key, bool add = false) { - int next_shift = toplevel->shift == 0 ? radix_bits : dir_bits; + Node *node = toplevel; + int next_shift = node->shift ? node->shift + dir_bits : radix_bits; - while (unlikely(key_to_dir_offset(key, toplevel->shift + - next_shift) != 0)) + while (unlikely(next_shift < key_bits && (key >> next_shift))) { 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; + DirNode *dn = new DirNode(next_shift); + dn->ptrs[0] = node; + toplevel = dn; + next_shift += dir_bits; } - Node *node = toplevel; + node = toplevel; while (node->shift > 0) { - assert(node->shift >= radix_bits); - int off = key_to_dir_offset(key, node->shift); - NodeBase *new_node = node[off]; + DirNode *dn = static_cast(node); + node = dn->ptrs[off]; - if (!new_node) { + if (!node) { if (!add) return NULL; - if (node->shift == radix_bits) - new_node = new LeafNode; + if (dn->shift == radix_bits) + node = new LeafNode; else - new_node = new DirNode(node->shift - dir_shift); + node = new DirNode(dn->shift == radix_bits ? + 0 : dn->shift - dir_bits); - node[off] = new_node; + dn->ptrs[off] = node; } - - node = new_node; } - assert(node->shift == 0); - return node[key_to_offset(key)]; + LeafNode *ln = static_cast(node); + return &ln->nodes[key_to_offset(key)]; } RadixTree() { + // OPT: start with a NULL toplevel. Besides avoiding wasting + // memory for empty trees, it avoids the need for a stack of + // trees down the ptr[0] path if there are no small keys. + toplevel = new LeafNode; } }; + } #endif