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

diff --git a/include/c++/util/handle.h b/include/c++/util/handle.h
new file mode 100644
index 0000000..b22648e
--- /dev/null
+++ b/include/c++/util/handle.h
@@ -0,0 +1,147 @@
+// Radix trees.  Supports mapping from integer keys to objects, and optionally
+// 
+  To allow
+// lockless lookups, the radix tree nodes are only added, never removed.  The
+// caller must ensure the synchronization of allocation and deallocation.
+//
+// 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_RADIX_H
+#define _UTIL_RADIX_H
+
+#include <assert.h>
+#include <stddef.h>
+#include <stdint.h>
+
+#include <lowlevel/bitops.h>
+
+namespace Util {
+	template <typename T>
+	struct Handle {
+		T *ptr;
+	};
+
+	template <typename T>
+	struct RefHandle : public Handle<T> {
+		unsigned int ref;
+	};
+
+	// Each node in the tree will contain 2**radix_bits handles.
+	template <typename T, int radix_bits>
+	class RadixTree {
+		typedef unsigned int Key;
+
+		enum {
+			node_size = 1 << radix_bits,
+			long_bits = sizeof(unsigned long) * 8;
+			bitmap_len = (node_size - 1) / long_bits + 1,
+			twolevel_bitmap = bitmap_len > 4
+		};
+		
+		struct NodeBase {
+			int shift;
+			unsigned long bmap[bitmap_len + twolevel_bitmap];
+			
+			NodeBase()
+			{
+				memset(bmap, 0, sizeof(bmap));
+			}
+			
+			// Find the first free entry in this node.
+			// Returns -1 if none found.
+			int find_first()
+			{
+				if (twolevel_bitmap) {
+					if (~bmap[0] == 0)
+						return -1;
+				
+					return ll_ffs(~bmap[ll_ffs(~bmap[0]) + 1]);
+				}
+
+				return ll_multiword_ffc(bmap, 0, node_size);
+			}
+		};
+		
+		struct Node : public NodeBase {
+			T handles[node_size];
+			
+			Node()
+			{
+				shift = 0;
+				memset(handles, 0, sizeof(handles));
+			}
+		};
+		
+		struct DirNode : public NodeBase {
+			void *ptrs[node_size];
+
+			DirNode(int SHIFT) : shift(SHIFT)
+			{
+				memset(ptrs, 0, sizeof(ptrs));
+			}
+		};
+	
+		NodeBase *toplevel;
+		
+		static int key_to_offset(Key key, int shift)
+		{
+			return (key >> shift) & (node_size - 1);
+		}
+
+	public:
+		T *lookup(Key key, bool add = false)
+		{
+			Node *node = toplevel;
+			
+			while (unlikely(!toplevel || key_to_offset(key, toplevel->shift +
+			                                           radix_bits) != 0))
+			{
+				if (!add)
+					return NULL;
+				
+				if (!toplevel) {
+					toplevel = new Node;
+				} else {
+					Node *new_node = new DirNode(toplevel->shift + radix_bits);
+					new_node->ptrs[0] = toplevel;
+					toplevel = new_node;
+				}
+			}
+
+			while (shift >= radix_bits) {
+				int off = key_to_offset(key, shift);
+				void *new_node = static_cast<void **>(node)[off];
+				
+				if (!new_node) {
+					if (!add)
+						return NULL;
+					
+					new_node = Mem::alloc_pages(1);
+					memset(new_node, 0, Arch::page_size);
+					static_cast<void **>(node)[off] = new_node;
+				}
+				
+				shift -= dir_shift;
+				node = new_node;
+			}
+			
+			assert(shift == 0);
+			return static_cast<T *>(node) + key_to_offset(key, 0);
+		}
+		
+		RadixTree()
+		{
+			toplevel = Mem::alloc_pages(1);
+			memset(toplevel, 0, Arch::page_size);
+			depth = 0;
+		}
+	};
+}
+
+#endif