From 58df1bd9b3448491714e5f6c1f571c4d1776d884 Mon Sep 17 00:00:00 2001 From: Scott Wood Date: Mon, 26 Mar 2007 22:39:45 -0500 Subject: [PATCH 1/1] xfer to desktop --- include/c++/util/bmaptree.h | 100 ++++++++++++++++++++++++ include/c++/util/handle.h | 147 ------------------------------------ include/c++/util/radix.h | 31 ++++---- 3 files changed, 117 insertions(+), 161 deletions(-) create mode 100644 include/c++/util/bmaptree.h delete mode 100644 include/c++/util/handle.h 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 . +// +// 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 +#include +#include + +#include +#include + +namespace Util { + // Key must be an integer type + template + 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(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 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 . -// -// 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 -#include -#include - -#include - -namespace Util { - template - struct Handle { - T *ptr; - }; - - template - struct RefHandle : public Handle { - unsigned int ref; - }; - - // Each node in the tree will contain 2**radix_bits handles. - template - 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(node)[off]; - - if (!new_node) { - if (!add) - return NULL; - - new_node = Mem::alloc_pages(1); - memset(new_node, 0, Arch::page_size); - static_cast(node)[off] = new_node; - } - - shift -= dir_shift; - node = new_node; - } - - assert(shift == 0); - return static_cast(node) + key_to_offset(key, 0); - } - - RadixTree() - { - toplevel = Mem::alloc_pages(1); - memset(toplevel, 0, Arch::page_size); - depth = 0; - } - }; -} - -#endif diff --git a/include/c++/util/radix.h b/include/c++/util/radix.h index b75d27e..48603f6 100644 --- a/include/c++/util/radix.h +++ b/include/c++/util/radix.h @@ -20,6 +20,7 @@ namespace Util { // Each leaf node in the tree will contain 2**radix_bits handles. // Each directory node will contain 2**dir_bits pointers. + template class RadixTree { typedef unsigned int Key; @@ -71,6 +72,10 @@ namespace Util { } public: + // The tree depth is contained in each node, and nodes are never + // removed from the tree, so lockless lookups are possible. + // Synchronization is required when add == true. + T *lookup(Key key, bool add = false) { int next_shift = toplevel->shift == 0 ? radix_bits : dir_bits; @@ -89,36 +94,34 @@ namespace Util { Node *node = toplevel; - while (node->shift >= radix_bits) { + while (node->shift > 0) { + assert(node->shift >= radix_bits); + int off = key_to_dir_offset(key, node->shift); NodeBase *new_node = node[off]; - shift == 0 ? new LeafNode - : new DirNode(shift); - void *new_node = static_cast(node)[off]; - if (!new_node) { if (!add) return NULL; - - new_node = Mem::alloc_pages(1); - memset(new_node, 0, Arch::page_size); - static_cast(node)[off] = new_node; + + if (node->shift == radix_bits) + new_node = new LeafNode; + else + new_node = new DirNode(node->shift - dir_shift); + + node[off] = new_node; } - shift -= dir_shift; node = new_node; } - assert(shift == 0); - return static_cast(node) + key_to_offset(key, 0); + assert(node->shift == 0); + return node[key_to_offset(key)]; } RadixTree() { toplevel = new LeafNode; - memset(toplevel, 0, Arch::page_size); - depth = 0; } }; } -- 2.39.2