bmaptree and radix fixes

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 <lowlevel/types.h>
 #include <lowlevel/bitops.h>
 

+#include <orb.h>
+#include <System/Exceptions.h>
+

 namespace Util {
 namespace Util {

-       // Key must be an integer type
+       // Key must be an unsigned integer type.

        template <typename Key>
        class BitmapTree {
                enum {
        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;
                };
                
                struct Node {
                        unsigned long index_bmap;

+                       
+                       Node() : index_bmap(0)
+                       {
+                       }

                };
                
                };
                

-               struct DirNode {
+               struct DirNode : public Node {

                        Node *nodes[node_size];
                        
                        DirNode()
                        {
                        Node *nodes[node_size];
                        
                        DirNode()
                        {

-                               index_bmap = 0;

                                memset(nodes, 0, sizeof(nodes));
                        }
                };
                                memset(nodes, 0, sizeof(nodes));
                        }
                };


@@ -44,12 +51,11 @@ namespace Util {
                Node *toplevel;
                int toplevel_shift;
                
                Node *toplevel;
                int toplevel_shift;
                

-               struct LeafNode {
+               struct LeafNode : public Node {

                        unsigned long nodes[node_size];
                        
                        LeafNode()
                        {
                        unsigned long nodes[node_size];
                        
                        LeafNode()
                        {

-                               index_bmap = 0;

                                memset(nodes, 0, sizeof(nodes));
                        }
                };
                                memset(nodes, 0, sizeof(nodes));
                        }
                };


@@ -59,40 +65,132 @@ namespace Util {
                        return (key >> shift) & (node_size - 1);
                }
 
                        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);
                                
                                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
                                        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;
                        }
                        
                                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;

                }
        };
 }
                }
        };
 }

diff --git a/include/c++/util/radix.h b/include/c++/util/radix.h
index 48603f6aa012e4994a40458fa1e330aa9ea1ae71..3dcaaaf993a156099a968b76517215449ac2d910 100644 (file)
--- a/include/c++/util/radix.h
+++ b/include/c++/util/radix.h
@@ -18,17 +18,17 @@
 #include <lowlevel/bitops.h>
 
 namespace Util {
 #include <lowlevel/bitops.h>
 
 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.
        // 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;
+       // Key must be an unsigned integer.

 
 

+       template <typename T, typename Key, int radix_bits,
+                 int dir_bits = radix_bits>
+       class RadixTree {

                enum {
                        node_size = 1 << radix_bits,
                        dir_size = 1 << dir_bits,
                enum {
                        node_size = 1 << radix_bits,
                        dir_size = 1 << dir_bits,

-                       long_bits = sizeof(unsigned long) * 8,
+                       key_bits = sizeof(Key) * 8,

                };
                
                struct Node {
                };
                
                struct Node {


@@ -41,17 +41,16 @@ namespace Util {
                };
                
                struct LeafNode : public Node {
                };
                
                struct LeafNode : public Node {

-                       T handles[node_size];
+                       T nodes[node_size];

                        
                        LeafNode() : Node(0)
                        {
                        
                        LeafNode() : Node(0)
                        {

-                               shift = 0;
-                               memset(handles, 0, sizeof(handles));
+                               memset(nodes, 0, sizeof(nodes));

                        }
                };
                
                struct DirNode : public Node {
                        }
                };
                
                struct DirNode : public Node {

-                       Node *ptrs[node_size];
+                       Node *ptrs[dir_size];

 
                        DirNode(int shift) : Node(shift)
                        {
 
                        DirNode(int shift) : Node(shift)
                        {


@@ -70,7 +69,7 @@ namespace Util {
                {
                        return key & (node_size - 1);
                }
                {
                        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. 
        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)
                {
                
                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;
                                
                        {
                                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) {
                        
                        while (node->shift > 0) {

-                               assert(node->shift >= radix_bits);
-                       

                                int off = key_to_dir_offset(key, node->shift);
                                int off = key_to_dir_offset(key, node->shift);

-                               NodeBase *new_node = node[off];
+                               DirNode *dn = static_cast<DirNode *>(node);
+                               node = dn->ptrs[off];

                                
                                

-                               if (!new_node) {
+                               if (!node) {

                                        if (!add)
                                                return NULL;
                                
                                        if (!add)
                                                return NULL;
                                

-                                       if (node->shift == radix_bits)
-                                               new_node = new LeafNode;
+                                       if (dn->shift == radix_bits)
+                                               node = new LeafNode;

                                        else
                                        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<LeafNode *>(node);
+                       return &ln->nodes[key_to_offset(key)];

                }
                
                RadixTree()
                {
                }
                
                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;
                }
        };
                        toplevel = new LeafNode;
                }
        };

+

 }
 
 #endif
 }
 
 #endif