xfer to desktop

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

diff --git a/include/c++/util/bmaptree.h b/include/c++/util/bmaptree.h
new file mode 100644 (file)
index 0000000..2342295
--- /dev/null
+++ b/include/c++/util/bmaptree.h
@@ -0,0 +1,100 @@
+// Bitmap Tree Allocator
+//
+// Written by Scott Wood <scott@buserror.net>.
+// 
+// This software is provided 'as-is', without any express or implied warranty.
+// In no event will the authors or contributors be held liable for any damages
+// arising from the use of this software.
+// 
+// This software is in the public domain.
+
+#ifndef _UTIL_BMAPTREE_H
+#define _UTIL_BMAPTREE_H
+
+#include <assert.h>
+#include <stddef.h>
+#include <stdint.h>
+
+#include <lowlevel/types.h>
+#include <lowlevel/bitops.h>
+
+namespace Util {
+       // Key must be an integer type
+       template <typename Key>
+       class BitmapTree {
+               enum {
+                       node_size = sizeof(unsigned long) * 8;
+                       radix_bits = _LL_LONG_LOGBYTES + 3;
+               };
+               
+               struct Node {
+                       unsigned long index_bmap;
+               };
+               
+               struct DirNode {
+                       Node *nodes[node_size];
+                       
+                       DirNode()
+                       {
+                               index_bmap = 0;
+                               memset(nodes, 0, sizeof(nodes));
+                       }
+               };
+
+               Node *toplevel;
+               int toplevel_shift;
+               
+               struct LeafNode {
+                       unsigned long nodes[node_size];
+                       
+                       LeafNode()
+                       {
+                               index_bmap = 0;
+                               memset(nodes, 0, sizeof(nodes));
+                       }
+               };
+
+               static uint key_to_offset(Key key, int shift)
+               {
+                       return (key >> shift) & (node_size - 1);
+               }
+
+       public:         
+               // Returns -1 if none found.
+               Key alloc(int shift = toplevel_shift)
+               {
+                       Node *node = toplevel;
+                       
+                       if (shift > 0) {
+                               assert (shift >= radix_bits);
+                               
+                               if (~node->index_bmap == 0)
+                                       return -1;
+                               
+                               int off = ll_ffs(!node->index_bmap);
+                               
+                               DirNode *dn = static_cast<DirNode *>(node);
+                               node = dn->nodes[off];
+                               
+                               if (!new_node) {
+                                       if (shift == radix_bits)
+                                               node = new LeafNode;
+                                       else
+                                               node = new DirNode;
+                                       
+                                       dn->nodes[off] = node;
+                               }
+
+                               dn->index_bmap |= (1UL << off);
+                               shift -= radix_bits;
+                       }
+                       
+                       if (~index_bmap[0] == 0)
+                               return -1;
+                       
+                       return ll_ffs(~bmap[ll_ffs(~bmap[0]) + 1]);
+               }
+       };
+}
+
+#endif