]> git.buserror.net Git - polintos/scott/priv.git/blob - kernel/include/kern/radix.h
Random stuff.
[polintos/scott/priv.git] / kernel / include / kern / radix.h
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.
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 PageRadixTree {
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 == 0 || shift == RADIX_final_shift - dir_shift);
89                         return (T *)((unsigned long)node +
90                                      (key_to_offset(key) << RADIX_data_bits));
91                 }
92                 
93                 PageRadixTree()
94                 {
95                         toplevel = Mem::alloc_pages(1);
96                         bzero(toplevel, Arch::page_size);
97                         depth = 0;
98                 }
99         };
100 }
101
102 #undef RADIX_data_bits
103 #undef RADIX_node_size
104 #undef RADIX_final_shift
105 #undef RADIX_entries_per_table
106
107 #endif