1 // This is like RadixTree, but it uses the kernel page allocator; each
2 // node takes up one page. The depth of the tree is dynamically growable
3 // (but not currently shrinkable). It also auto-guesses radix_bits based
4 // on the size of T, so as to fit a page.
9 #include <kern/types.h>
10 #include <kern/pagealloc.h>
11 #include <kern/compiler.h>
13 #include <arch/paging.h>
15 #include <lowlevel/bitops.h>
18 // Key must be an integer.
19 template <typename T, typename Key>
22 uint depth; // in bits
25 // Yuck... C++ doesn't allow function results to be used
26 // in constants, even if the function can be evaluated
29 #define RADIX_data_bits (ll_get_order_round_up(sizeof(T)))
30 #define RADIX_node_size (1 << RADIX_data_bits)
32 #define RADIX_final_shift (Arch::page_shift - RADIX_data_bits)
33 #define RADIX_entries_per_table (Arch::page_size / RADIX_node_size)
35 dir_shift = Arch::page_shift - _LL_LONG_LOGBYTES,
36 entries_per_dir = Arch::page_size / sizeof(void *)
39 static uint key_to_dir_offset(Key key, int shift)
41 return (key >> shift) & (entries_per_dir - 1);
44 static uint key_to_offset(Key key)
46 return key & (RADIX_entries_per_table - 1);
50 T *lookup(Key key, bool add = false)
53 void *node = toplevel;
54 int new_shift = depth == 0 ? RADIX_final_shift : dir_shift;
56 while (unlikely(key_to_dir_offset(key, shift + new_shift) != 0)) {
60 toplevel = Mem::alloc_pages(1);
61 bzero(toplevel, Arch::page_size);
63 static_cast<void **>(toplevel)[0] = node;
68 new_shift = dir_shift;
71 while (shift >= RADIX_final_shift) {
72 int off = key_to_dir_offset(key, shift);
73 void *new_node = static_cast<void **>(node)[off];
79 new_node = Mem::alloc_pages(1);
80 bzero(new_node, Arch::page_size);
81 static_cast<void **>(node)[off] = new_node;
88 assert(shift == 0 || shift == RADIX_final_shift - dir_shift);
89 return (T *)((unsigned long)node +
90 (key_to_offset(key) << RADIX_data_bits));
95 toplevel = Mem::alloc_pages(1);
96 bzero(toplevel, Arch::page_size);
102 #undef RADIX_data_bits
103 #undef RADIX_node_size
104 #undef RADIX_final_shift
105 #undef RADIX_entries_per_table