kernel/include/kern/radix.h

   1 // Generic radix tree implementation.  It's only kernel-specific because
   2 // it uses the kernel page allocator; each node takes up one page.  The
   3 // depth of the tree is dynamically growable (but not currently
   4 // shrinkable).
   5
   6 #ifndef _KERN_RADIX_H
   7 #define _KERN_RADIX_H
   8
   9 #include <kern/types.h>
  10 #include <kern/pagealloc.h>
  11 #include <kern/compiler.h>
  12
  13 #include <arch/paging.h>
  14
  15 #include <lowlevel/bitops.h>
  16
  17 namespace Util {
  18         // Key must be an integer.
  19         template <typename T, typename Key>
  20         class RadixTree {
  21                 void *toplevel;
  22                 uint depth; // in bits
  23
  24                 enum {
  25                         // Yuck...  C++ doesn't allow function results to be used
  26                         // in constants, even if the function can be evaluated
  27                         // at compile time.
  28
  29                         #define RADIX_data_bits (ll_get_order_round_up(sizeof(T)))
  30                         #define RADIX_node_size (1 << RADIX_data_bits)
  31
  32                         #define RADIX_final_shift (Arch::page_shift - RADIX_data_bits)
  33                         #define RADIX_entries_per_table (Arch::page_size / RADIX_node_size)
  34
  35                         dir_shift = Arch::page_shift - _LL_LONG_LOGBYTES,
  36                         entries_per_dir = Arch::page_size / sizeof(void *)
  37                 };
  38
  39                 static uint key_to_dir_offset(Key key, int shift)
  40                 {
  41                         return (key >> shift) & (entries_per_dir - 1);
  42                 }
  43
  44                 static uint key_to_offset(Key key)
  45                 {
  46                         return key & (RADIX_entries_per_table - 1);
  47                 }
  48
  49         public:
  50                 T *lookup(Key key, bool add = false)
  51                 {
  52                         int shift = depth;
  53                         void *node = toplevel;
  54                         int new_shift = depth == 0 ? RADIX_final_shift : dir_shift;
  55
  56                         while (unlikely(key_to_dir_offset(key, shift + new_shift) != 0)) {
  57                                 if (!add)
  58                                         return NULL;
  59
  60                                 toplevel = Mem::alloc_pages(1);
  61                                 bzero(toplevel, Arch::page_size);
  62
  63                                 static_cast<void **>(toplevel)[0] = node;
  64                                 node = toplevel;
  65
  66                                 shift += new_shift;
  67                                 depth += new_shift;
  68                                 new_shift = dir_shift;
  69                         }
  70
  71                         while (shift >= RADIX_final_shift) {
  72                                 int off = key_to_dir_offset(key, shift);
  73                                 void *new_node = static_cast<void **>(node)[off];
  74
  75                                 if (!new_node) {
  76                                         if (!add)
  77                                                 return NULL;
  78
  79                                         new_node = Mem::alloc_pages(1);
  80                                         bzero(new_node, Arch::page_size);
  81                                         static_cast<void **>(node)[off] = new_node;
  82                                 }
  83
  84                                 shift -= dir_shift;
  85                                 node = new_node;
  86                         }
  87
  88                         assert(shift == RADIX_final_shift - dir_shift);
  89                         return static_cast<T *>(node) + key_to_offset(key);
  90                 }
  91
  92                 RadixTree()
  93                 {
  94                         toplevel = Mem::alloc_pages(1);
  95                         bzero(toplevel, Arch::page_size);
  96                         depth = 0;
  97                 }
  98         };
  99 }
 100
 101 #undef RADIX_data_bits
 102 #undef RADIX_node_size
 103 #undef RADIX_final_shift
 104 #undef RADIX_entries_per_table
 105
 106 #endif