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;h=56b3bfabf2defc2cfb96995fc55970e3eb601e3c;hp=234229573aeb933050fec18805db47137b5200c3;hb=6ef00363db1c75274dfcc188c778cb437d896034;hpb=b23d2e75df5a92922637d3195ed38c5f06a0f68a

diff --git a/include/c++/util/bmaptree.h b/include/c++/util/bmaptree.h
index 2342295..56b3bfa 100644
--- 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 <orb.h>
+#include <System/Exceptions.h>
+
 namespace Util {
-	// Key must be an integer type
+	// Key must be an unsigned integer type.
 	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;
+			
+			Node() : index_bmap(0)
+			{
+			}
 		};
 		
-		struct DirNode {
+		struct DirNode : public Node {
 			Node *nodes[node_size];
 			
 			DirNode()
 			{
-				index_bmap = 0;
 				memset(nodes, 0, sizeof(nodes));
 			}
 		};
@@ -44,12 +51,11 @@ namespace Util {
 		Node *toplevel;
 		int toplevel_shift;
 		
-		struct LeafNode {
+		struct LeafNode : public Node {
 			unsigned long nodes[node_size];
 			
 			LeafNode()
 			{
-				index_bmap = 0;
 				memset(nodes, 0, sizeof(nodes));
 			}
 		};
@@ -59,40 +65,132 @@ namespace Util {
 			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);
-				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
-						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;
 			}
 			
-			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;
 		}
 	};
 }