X-Git-Url: http://git.buserror.net/cgi-bin/gitweb.cgi?p=polintos%2Fscott%2Fpriv.git;a=blobdiff_plain;f=include%2Fc%2B%2B%2Futil%2Fbmaptree.h;fp=include%2Fc%2B%2B%2Futil%2Fbmaptree.h;h=234229573aeb933050fec18805db47137b5200c3;hp=0000000000000000000000000000000000000000;hb=58df1bd9b3448491714e5f6c1f571c4d1776d884;hpb=0c52a8435aa399781856869daa7ef30cef14fad5

diff --git a/include/c++/util/bmaptree.h b/include/c++/util/bmaptree.h
new file mode 100644
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