include/c++/util/handle.h

   1 // Radix trees.  Supports mapping from integer keys to objects, and optionally
   2 //
   3   To allow
   4 // lockless lookups, the radix tree nodes are only added, never removed.  The
   5 // caller must ensure the synchronization of allocation and deallocation.
   6 //
   7 // Written by Scott Wood <scott@buserror.net>.
   8 //
   9 // This software is provided 'as-is', without any express or implied warranty.
  10 // In no event will the authors or contributors be held liable for any damages
  11 // arising from the use of this software.
  12 //
  13 // This software is in the public domain.
  14
  15 #ifndef _UTIL_RADIX_H
  16 #define _UTIL_RADIX_H
  17
  18 #include <assert.h>
  19 #include <stddef.h>
  20 #include <stdint.h>
  21
  22 #include <lowlevel/bitops.h>
  23
  24 namespace Util {
  25         template <typename T>
  26         struct Handle {
  27                 T *ptr;
  28         };
  29
  30         template <typename T>
  31         struct RefHandle : public Handle<T> {
  32                 unsigned int ref;
  33         };
  34
  35         // Each node in the tree will contain 2**radix_bits handles.
  36         template <typename T, int radix_bits>
  37         class RadixTree {
  38                 typedef unsigned int Key;
  39
  40                 enum {
  41                         node_size = 1 << radix_bits,
  42                         long_bits = sizeof(unsigned long) * 8;
  43                         bitmap_len = (node_size - 1) / long_bits + 1,
  44                         twolevel_bitmap = bitmap_len > 4
  45                 };
  46
  47                 struct NodeBase {
  48                         int shift;
  49                         unsigned long bmap[bitmap_len + twolevel_bitmap];
  50
  51                         NodeBase()
  52                         {
  53                                 memset(bmap, 0, sizeof(bmap));
  54                         }
  55
  56                         // Find the first free entry in this node.
  57                         // Returns -1 if none found.
  58                         int find_first()
  59                         {
  60                                 if (twolevel_bitmap) {
  61                                         if (~bmap[0] == 0)
  62                                                 return -1;
  63
  64                                         return ll_ffs(~bmap[ll_ffs(~bmap[0]) + 1]);
  65                                 }
  66
  67                                 return ll_multiword_ffc(bmap, 0, node_size);
  68                         }
  69                 };
  70
  71                 struct Node : public NodeBase {
  72                         T handles[node_size];
  73
  74                         Node()
  75                         {
  76                                 shift = 0;
  77                                 memset(handles, 0, sizeof(handles));
  78                         }
  79                 };
  80
  81                 struct DirNode : public NodeBase {
  82                         void *ptrs[node_size];
  83
  84                         DirNode(int SHIFT) : shift(SHIFT)
  85                         {
  86                                 memset(ptrs, 0, sizeof(ptrs));
  87                         }
  88                 };
  89
  90                 NodeBase *toplevel;
  91
  92                 static int key_to_offset(Key key, int shift)
  93                 {
  94                         return (key >> shift) & (node_size - 1);
  95                 }
  96
  97         public:
  98                 T *lookup(Key key, bool add = false)
  99                 {
 100                         Node *node = toplevel;
 101
 102                         while (unlikely(!toplevel || key_to_offset(key, toplevel->shift +
 103                                                                    radix_bits) != 0))
 104                         {
 105                                 if (!add)
 106                                         return NULL;
 107
 108                                 if (!toplevel) {
 109                                         toplevel = new Node;
 110                                 } else {
 111                                         Node *new_node = new DirNode(toplevel->shift + radix_bits);
 112                                         new_node->ptrs[0] = toplevel;
 113                                         toplevel = new_node;
 114                                 }
 115                         }
 116
 117                         while (shift >= radix_bits) {
 118                                 int off = key_to_offset(key, shift);
 119                                 void *new_node = static_cast<void **>(node)[off];
 120
 121                                 if (!new_node) {
 122                                         if (!add)
 123                                                 return NULL;
 124
 125                                         new_node = Mem::alloc_pages(1);
 126                                         memset(new_node, 0, Arch::page_size);
 127                                         static_cast<void **>(node)[off] = new_node;
 128                                 }
 129
 130                                 shift -= dir_shift;
 131                                 node = new_node;
 132                         }
 133
 134                         assert(shift == 0);
 135                         return static_cast<T *>(node) + key_to_offset(key, 0);
 136                 }
 137
 138                 RadixTree()
 139                 {
 140                         toplevel = Mem::alloc_pages(1);
 141                         memset(toplevel, 0, Arch::page_size);
 142                         depth = 0;
 143                 }
 144         };
 145 }
 146
 147 #endif