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=0000000000000000000000000000000000000000;hb=58df1bd9b3448491714e5f6c1f571c4d1776d884;hp=b22648ee646ee94c8c0812068c4085dd848af67b;hpb=0c52a8435aa399781856869daa7ef30cef14fad5;p=polintos%2Fscott%2Fpriv.git

diff --git a/include/c++/util/handle.h b/include/c++/util/handle.h
deleted file mode 100644
index b22648e..0000000
--- a/include/c++/util/handle.h
+++ /dev/null
@@ -1,147 +0,0 @@
-// 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