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 namespace Util {
  22         // Key must be an integer type
  23         template <typename Key>
  24         class BitmapTree {
  25                 enum {
  26                         node_size = sizeof(unsigned long) * 8;
  27                         radix_bits = _LL_LONG_LOGBYTES + 3;
  28                 };
  29
  30                 struct Node {
  31                         unsigned long index_bmap;
  32                 };
  33
  34                 struct DirNode {
  35                         Node *nodes[node_size];
  36
  37                         DirNode()
  38                         {
  39                                 index_bmap = 0;
  40                                 memset(nodes, 0, sizeof(nodes));
  41                         }
  42                 };
  43
  44                 Node *toplevel;
  45                 int toplevel_shift;
  46
  47                 struct LeafNode {
  48                         unsigned long nodes[node_size];
  49
  50                         LeafNode()
  51                         {
  52                                 index_bmap = 0;
  53                                 memset(nodes, 0, sizeof(nodes));
  54                         }
  55                 };
  56
  57                 static uint key_to_offset(Key key, int shift)
  58                 {
  59                         return (key >> shift) & (node_size - 1);
  60                 }
  61
  62         public:
  63                 // Returns -1 if none found.
  64                 Key alloc(int shift = toplevel_shift)
  65                 {
  66                         Node *node = toplevel;
  67
  68                         if (shift > 0) {
  69                                 assert (shift >= radix_bits);
  70
  71                                 if (~node->index_bmap == 0)
  72                                         return -1;
  73
  74                                 int off = ll_ffs(!node->index_bmap);
  75
  76                                 DirNode *dn = static_cast<DirNode *>(node);
  77                                 node = dn->nodes[off];
  78
  79                                 if (!new_node) {
  80                                         if (shift == radix_bits)
  81                                                 node = new LeafNode;
  82                                         else
  83                                                 node = new DirNode;
  84
  85                                         dn->nodes[off] = node;
  86                                 }
  87
  88                                 dn->index_bmap |= (1UL << off);
  89                                 shift -= radix_bits;
  90                         }
  91
  92                         if (~index_bmap[0] == 0)
  93                                 return -1;
  94
  95                         return ll_ffs(~bmap[ll_ffs(~bmap[0]) + 1]);
  96                 }
  97         };
  98 }
  99
 100 #endif