xfer to desktop

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

diff --git a/include/c++/util/handle.h b/include/c++/util/handle.h
deleted file mode 100644 (file)
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