include/c++/util/bmaptree.h

   1 // Bitmap Tree Allocator
   2 //
   3 // Written by Scott Wood <scott@buserror.net>.
   4 //
   5 // This software is provided 'as-is', without any express or implied warranty.
   6 // In no event will the authors or contributors be held liable for any damages
   7 // arising from the use of this software.
   8 //
   9 // This software is in the public domain.
  10
  11 #ifndef _UTIL_BMAPTREE_H
  12 #define _UTIL_BMAPTREE_H
  13
  14 #include <assert.h>
  15 #include <stddef.h>
  16 #include <stdint.h>
  17
  18 #include <lowlevel/types.h>
  19 #include <lowlevel/bitops.h>
  20
  21 #include <orb.h>
  22 #include <System/Exceptions.h>
  23
  24 namespace Util {
  25         // Key must be an unsigned integer type.
  26         template <typename Key>
  27         class BitmapTree {
  28                 enum {
  29                         node_size = sizeof(unsigned long) * 8,
  30                         radix_bits = _LL_LONG_LOGBYTES + 3,
  31                         key_bits = sizeof(Key) * 8,
  32                 };
  33
  34                 struct Node {
  35                         unsigned long index_bmap;
  36
  37                         Node() : index_bmap(0)
  38                         {
  39                         }
  40                 };
  41
  42                 struct DirNode : public Node {
  43                         Node *nodes[node_size];
  44
  45                         DirNode()
  46                         {
  47                                 memset(nodes, 0, sizeof(nodes));
  48                         }
  49                 };
  50
  51                 Node *toplevel;
  52                 int toplevel_shift;
  53
  54                 struct LeafNode : public Node {
  55                         unsigned long nodes[node_size];
  56
  57                         LeafNode()
  58                         {
  59                                 memset(nodes, 0, sizeof(nodes));
  60                         }
  61                 };
  62
  63                 static uint key_to_offset(Key key, int shift)
  64                 {
  65                         return (key >> shift) & (node_size - 1);
  66                 }
  67
  68         public:
  69                 // max_key must be positive.  Modifications must be synchronized with
  70                 // alloc() and free(), but are otherwise unrestricted (including
  71                 // reducing it below already allocated keys).
  72
  73                 Key max_key;
  74
  75         private:
  76                 Key rec_alloc(Node *node, int shift, bool *full)
  77                 {
  78                         assert(~node->index_bmap != 0);
  79                         int off = ll_ffs(!node->index_bmap);
  80                         Key key = ((Key)off) << shift;
  81
  82                         if (shift > radix_bits) {
  83                                 assert(shift >= radix_bits * 2);
  84
  85                                 if (key >= max_key)
  86                                         throw_idl(::System::Exceptions::Std::OutOfSpace,
  87                                                   ::System::RunTime::nullarray);
  88
  89                                 DirNode *dn = static_cast<DirNode *>(node);
  90                                 Node *new_node = dn->nodes[off];
  91
  92                                 if (unlikely(!new_node)) {
  93                                         if (shift == radix_bits * 2)
  94                                                 new_node = new LeafNode;
  95                                         else
  96                                                 new_node = new DirNode;
  97
  98                                         dn->nodes[off] = new_node;
  99                                 }
 100
 101                                 bool sub_full = false;
 102                                 key += rec_alloc(new_node, shift - radix_bits, &sub_full);
 103
 104                                 if (sub_full)
 105                                         dn->index_bmap |= 1UL << off;
 106                         } else {
 107                                 assert(shift == radix_bits);
 108
 109                                 LeafNode *ln = static_cast<LeafNode *>(node);
 110                                 assert(~ln->nodes[off] != 0);
 111
 112                                 int leaf_bit = ll_ffs(ln->nodes[off]);
 113                                 key |= ((Key)1) << leaf_bit;
 114
 115                                 if (key >= max_key)
 116                                         throw_idl(::System::Exceptions::Std::OutOfSpace,
 117                                                   ::System::RunTime::nullarray);
 118
 119                                 ln->nodes[off] |= 1UL << leaf_bit;
 120
 121                                 if (~ln->nodes[off] == 0)
 122                                         ln->index_bmap |= 1UL << off;
 123                         }
 124
 125                         if (~node->index_bmap == 0 && full)
 126                                 *full = true;
 127
 128                         return key;
 129                 }
 130
 131         public:
 132                 // Throws System::Exceptions::Std::OutOfSpace on failure
 133                 Key alloc()
 134                 {
 135                         if (unlikely(~toplevel->index_bmap == 0)) {
 136                                 int new_shift = toplevel_shift + radix_bits;
 137
 138                                 if (new_shift >= key_bits ||
 139                                     (((Key)1) << new_shift) >= max_key)
 140                                         throw_idl(::System::Exceptions::Std::OutOfSpace,
 141                                                   ::System::RunTime::nullarray);
 142
 143                                 DirNode *dn = new DirNode;
 144                                 dn->nodes[0] = toplevel;
 145                                 toplevel_shift = new_shift;
 146                                 toplevel = dn;
 147                         }
 148
 149                         return rec_alloc(toplevel, toplevel_shift, NULL);
 150                 }
 151
 152                 // Throws System::InvalidArgument if key is already free
 153                 void free(Key key)
 154                 {
 155                         Node *node = toplevel;
 156                         int shift = toplevel_shift;
 157                         int max_bits = toplevel_shift + radix_bits;
 158
 159                         if (max_bits < key_bits && key >= (((Key)1) << max_bits))
 160                                 throw_idl(::System::Exceptions::Std::InvalidArgument, 0,
 161                                           ::System::RunTime::nullarray);
 162
 163                         while (shift > radix_bits) {
 164                                 assert(shift >= radix_bits * 2);
 165
 166                                 int off = key_to_offset(key, shift);
 167                                 node->index_bmap &= ~(1UL << off);
 168
 169                                 DirNode *dn = static_cast<DirNode *>(node);
 170                                 node = dn->nodes[off];
 171                                 shift -= radix_bits;
 172                         }
 173
 174                         assert(shift == radix_bits);
 175
 176                         int off = key_to_offset(key, radix_bits);
 177                         node->index_bmap &= ~(1UL << off);
 178
 179                         LeafNode *ln = static_cast<LeafNode *>(node);
 180                         int bit = key_to_offset(key, 0);
 181
 182                         if (!(ln->nodes[off] & (1UL << bit)))
 183                                 throw_idl(::System::Exceptions::Std::InvalidArgument, 0,
 184                                           ::System::RunTime::nullarray);
 185
 186                         ln->nodes[off] &= ~(1UL << bit);
 187                 }
 188
 189                 BitmapTree()
 190                 {
 191                         max_key = ~(Key)0;
 192                         toplevel_shift = radix_bits;
 193                         toplevel = new LeafNode;
 194                 }
 195         };
 196 }
 197
 198 #endif