-// 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