bmaptree and radix fixes

[polintos/scott/priv.git] / include / c++ / util / bmaptree.h

diff --git a/include/c++/util/bmaptree.h b/include/c++/util/bmaptree.h
index 234229573aeb933050fec18805db47137b5200c3..56b3bfabf2defc2cfb96995fc55970e3eb601e3c 100644 (file)
--- a/include/c++/util/bmaptree.h
+++ b/include/c++/util/bmaptree.h
@@ -18,25 +18,32 @@
 #include <lowlevel/types.h>
 #include <lowlevel/bitops.h>
 
+#include <orb.h>
+#include <System/Exceptions.h>
+
 namespace Util {
-       // Key must be an integer type
+       // Key must be an unsigned integer type.
        template <typename Key>
        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<DirNode *>(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<LeafNode *>(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<DirNode *>(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<LeafNode *>(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;
                }
        };
 }