1#include <stdlib.h>
2#include <string.h>
3#include <btrie.h>
4
5#define PAGE_SIZE 4096
6
7
8static btrie_node_t *
9btrie_alloc(btrie_t *tree)
10{
11 btrie_node_t *p;
12
13 if (tree->free) {
14 p = tree->free;
15 tree->free = tree->free->right;
16 return p;
17 }
18
19 if (tree->size < sizeof(btrie_node_t)) {
20 tree->start = (char *) calloc(sizeof(char), PAGE_SIZE);
21 if (tree->start == NULL) {
22 return NULL;
23 }
24
25 tree->pools[tree->len++] = tree->start;
26 tree->size = PAGE_SIZE;
27 }
28
29 p = (btrie_node_t *) tree->start;
30
31 tree->start += sizeof(btrie_node_t);
32 tree->size -= sizeof(btrie_node_t);
33
34 return p;
35}
36
37
38btrie_t *
39btrie_create()
40{
41 btrie_t *tree = (btrie_t *) malloc(sizeof(btrie_t));
42 if (tree == NULL) {
43 return NULL;
44 }
45
46 tree->free = NULL;
47 tree->start = NULL;
48 tree->size = 0;
49 memset(tree->pools, 0, sizeof(btrie_t *) * BTRIE_MAX_PAGES);
50 tree->len = 0;
51
52 tree->root = btrie_alloc(tree);
53 if (tree->root == NULL) {
54 return NULL;
55 }
56
57 tree->root->right = NULL;
58 tree->root->left = NULL;
59 tree->root->parent = NULL;
60 tree->root->value = BTRIE_NULL;
61
62 return tree;
63}
64
65static size_t
66subtree_weight(btrie_node_t *node)
67{
68 size_t weight = 1;
69 if (node->left) {
70 weight += subtree_weight(node->left);
71 }
72 if (node->right) {
73 weight += subtree_weight(node->right);
74 }
75 return weight;
76}
77
78size_t
79btrie_count(btrie_t *tree)
80{
81 if (tree->root == NULL) {
82 return 0;
83 }
84
85 return subtree_weight(tree->root);
86}
87
88size_t
89btrie_allocated(btrie_t *tree)
90{
91 return tree->len * PAGE_SIZE;
92}
93
94
95int
96btrie_insert(btrie_t *tree, uint32_t key, uint32_t mask,
97 uintptr_t value)
98{
99 uint32_t bit;
100 btrie_node_t *node, *next;
101
102 bit = 0x80000000;
103
104 node = tree->root;
105 next = tree->root;
106
107 while (bit & mask) {
108 if (key & bit) {
109 next = node->right;
110
111 } else {
112 next = node->left;
113 }
114
115 if (next == NULL) {
116 break;
117 }
118
119 bit >>= 1;
120 node = next;
121 }
122
123 if (next) {
124 if (node->value != BTRIE_NULL) {
125 return -1;
126 }
127
128 node->value = value;
129 return 0;
130 }
131
132 while (bit & mask) {
133 next = btrie_alloc(tree);
134 if (next == NULL) {
135 return -1;
136 }
137
138 next->right = NULL;
139 next->left = NULL;
140 next->parent = node;
141 next->value = BTRIE_NULL;
142
143 if (key & bit) {
144 node->right = next;
145
146 } else {
147 node->left = next;
148 }
149
150 bit >>= 1;
151 node = next;
152 }
153
154 node->value = value;
155
156 return 0;
157}
158
159
160int
161btrie_delete(btrie_t *tree, uint32_t key, uint32_t mask)
162{
163 uint32_t bit;
164 btrie_node_t *node;
165
166 bit = 0x80000000;
167 node = tree->root;
168
169 while (node && (bit & mask)) {
170 if (key & bit) {
171 node = node->right;
172
173 } else {
174 node = node->left;
175 }
176
177 bit >>= 1;
178 }
179
180 if (node == NULL) {
181 return -1;
182 }
183
184 if (node->right || node->left) {
185 if (node->value != BTRIE_NULL) {
186 node->value = BTRIE_NULL;
187 return 0;
188 }
189
190 return -1;
191 }
192
193 for ( ;; ) {
194 if (node->parent->right == node) {
195 node->parent->right = NULL;
196
197 } else {
198 node->parent->left = NULL;
199 }
200
201 node->right = tree->free;
202 tree->free = node;
203
204 node = node->parent;
205
206 if (node->right || node->left) {
207 break;
208 }
209
210 if (node->value != BTRIE_NULL) {
211 break;
212 }
213
214 if (node->parent == NULL) {
215 break;
216 }
217 }
218
219 return 0;
220}
221
222
223uintptr_t
224btrie_find(btrie_t *tree, uint32_t key)
225{
226 uint32_t bit;
227 uintptr_t value;
228 btrie_node_t *node;
229
230 bit = 0x80000000;
231 value = BTRIE_NULL;
232 node = tree->root;
233
234 while (node) {
235 if (node->value != BTRIE_NULL) {
236 value = node->value;
237 }
238
239 if (key & bit) {
240 node = node->right;
241
242 } else {
243 node = node->left;
244 }
245
246 bit >>= 1;
247 }
248
249 return value;
250}
251
252
253int
254btrie_insert_a6(btrie_t *tree, const uint8_t *key, const uint8_t *mask,
255 uintptr_t value)
256{
257 uint8_t bit;
258 unsigned int i;
259 btrie_node_t *node, *next;
260
261 i = 0;
262 bit = 0x80;
263
264 node = tree->root;
265 next = tree->root;
266
267 while (bit & mask[i]) {
268 if (key[i] & bit) {
269 next = node->right;
270
271 } else {
272 next = node->left;
273 }
274
275 if (next == NULL) {
276 break;
277 }
278
279 bit >>= 1;
280 node = next;
281
282 if (bit == 0) {
283 if (++i == 16) {
284 break;
285 }
286
287 bit = 0x80;
288 }
289 }
290
291 if (next) {
292 if (node->value != BTRIE_NULL) {
293 return -1;
294 }
295
296 node->value = value;
297 return 0;
298 }
299
300 while (bit & mask[i]) {
301 next = btrie_alloc(tree);
302 if (next == NULL) {
303 return -1;
304 }
305
306 next->right = NULL;
307 next->left = NULL;
308 next->parent = node;
309 next->value = BTRIE_NULL;
310
311 if (key[i] & bit) {
312 node->right = next;
313
314 } else {
315 node->left = next;
316 }
317
318 bit >>= 1;
319 node = next;
320
321 if (bit == 0) {
322 if (++i == 16) {
323 break;
324 }
325
326 bit = 0x80;
327 }
328 }
329
330 node->value = value;
331
332 return 0;
333}
334
335
336int
337btrie_delete_a6(btrie_t *tree, const uint8_t *key, const uint8_t *mask)
338{
339 uint8_t bit;
340 unsigned int i;
341 btrie_node_t *node;
342
343 i = 0;
344 bit = 0x80;
345 node = tree->root;
346
347 while (node && (bit & mask[i])) {
348 if (key[i] & bit) {
349 node = node->right;
350
351 } else {
352 node = node->left;
353 }
354
355 bit >>= 1;
356
357 if (bit == 0) {
358 if (++i == 16) {
359 break;
360 }
361
362 bit = 0x80;
363 }
364 }
365
366 if (node == NULL) {
367 return -1;
368 }
369
370 if (node->right || node->left) {
371 if (node->value != BTRIE_NULL) {
372 node->value = BTRIE_NULL;
373 return 0;
374 }
375
376 return -1;
377 }
378
379 for ( ;; ) {
380 if (node->parent->right == node) {
381 node->parent->right = NULL;
382
383 } else {
384 node->parent->left = NULL;
385 }
386
387 node->right = tree->free;
388 tree->free = node;
389
390 node = node->parent;
391
392 if (node->right || node->left) {
393 break;
394 }
395
396 if (node->value != BTRIE_NULL) {
397 break;
398 }
399
400 if (node->parent == NULL) {
401 break;
402 }
403 }
404
405 return 0;
406}
407
408
409uintptr_t
410btrie_find_a6(btrie_t *tree, const uint8_t *key)
411{
412 uint8_t bit;
413 uintptr_t value;
414 unsigned int i;
415 btrie_node_t *node;
416
417 i = 0;
418 bit = 0x80;
419 value = BTRIE_NULL;
420 node = tree->root;
421
422 while (node) {
423 if (node->value != BTRIE_NULL) {
424 value = node->value;
425 }
426
427 if (key[i] & bit) {
428 node = node->right;
429
430 } else {
431 node = node->left;
432 }
433
434 bit >>= 1;
435
436 if (bit == 0) {
437 i++;
438 bit = 0x80;
439 }
440 }
441
442 return value;
443}
444
445
446int
447btrie_destroy(btrie_t *tree)
448{
449 size_t i;
450
451
452 /* free memory pools */
453 for (i = 0; i < tree->len; i++) {
454 free(tree->pools[i]);
455 }
456
457 free(tree);
458
459 return 0;
460}
461