]>
Commit | Line | Data |
---|---|---|
8e6ba6f9 AC |
1 | /* |
2 | * charybdis: an advanced ircd. | |
a4bf26dd | 3 | * rb_radixtree.c: Dictionary-based information storage. |
8e6ba6f9 AC |
4 | * |
5 | * Copyright (c) 2007-2016 William Pitcock <nenolod -at- dereferenced.org> | |
6 | * Copyright (c) 2007-2016 Jilles Tjoelker <jilles -at- stack.nl> | |
7 | * | |
8 | * Redistribution and use in source and binary forms, with or without | |
9 | * modification, are permitted provided that the following conditions are | |
10 | * met: | |
11 | * | |
12 | * 1. Redistributions of source code must retain the above copyright notice, | |
13 | * this list of conditions and the following disclaimer. | |
14 | * | |
15 | * 2. Redistributions in binary form must reproduce the above copyright | |
16 | * notice, this list of conditions and the following disclaimer in the | |
17 | * documentation and/or other materials provided with the distribution. | |
18 | * | |
19 | * 3. The name of the author may not be used to endorse or promote products | |
20 | * derived from this software without specific prior written permission. | |
21 | * | |
22 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR | |
23 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED | |
24 | * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE | |
25 | * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, | |
26 | * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES | |
27 | * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR | |
28 | * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
29 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, | |
30 | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING | |
31 | * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | |
32 | * POSSIBILITY OF SUCH DAMAGE. | |
33 | */ | |
34 | ||
a4bf26dd EM |
35 | #include <librb_config.h> |
36 | #include <rb_lib.h> | |
37 | #include <rb_radixtree.h> | |
8e6ba6f9 | 38 | |
325cc939 AC |
39 | rb_dlink_list radixtree_list = {NULL, NULL, 0}; |
40 | ||
8e6ba6f9 AC |
41 | /* |
42 | * Patricia tree. | |
43 | * | |
44 | * A radix trie that avoids one-way branching and redundant nodes. | |
45 | * | |
46 | * To find a node, the tree is traversed starting from the root. The | |
47 | * nibnum in each node indicates which nibble of the key needs to be | |
48 | * tested, and the appropriate branch is taken. | |
49 | * | |
50 | * The nibnum values are strictly increasing while going down the tree. | |
51 | * | |
52 | * -- jilles | |
53 | */ | |
54 | ||
a4bf26dd | 55 | union rb_radixtree_elem; |
2fc6772e EM |
56 | typedef union rb_radixtree_elem rb_radixtree_elem; |
57 | ||
58 | /* Other typedefs are in rb_radixtree.h */ | |
59 | typedef struct rb_radixtree_node rb_radixtree_node; | |
8e6ba6f9 | 60 | |
a4bf26dd | 61 | struct rb_radixtree |
8e6ba6f9 AC |
62 | { |
63 | void (*canonize_cb)(char *key); | |
2fc6772e | 64 | rb_radixtree_elem *root; |
8e6ba6f9 AC |
65 | |
66 | unsigned int count; | |
67 | char *id; | |
325cc939 AC |
68 | |
69 | rb_dlink_node node; | |
8e6ba6f9 AC |
70 | }; |
71 | ||
72 | #define POINTERS_PER_NODE 16 | |
73 | #define NIBBLE_VAL(key, nibnum) (((key)[(nibnum) / 2] >> ((nibnum) & 1 ? 0 : 4)) & 0xF) | |
74 | ||
a4bf26dd | 75 | struct rb_radixtree_node |
8e6ba6f9 AC |
76 | { |
77 | /* nibble to test (nibble NUM%2 of byte NUM/2) */ | |
78 | int nibnum; | |
79 | ||
80 | /* branches of the tree */ | |
2fc6772e EM |
81 | rb_radixtree_elem *down[POINTERS_PER_NODE]; |
82 | rb_radixtree_elem *parent; | |
8e6ba6f9 AC |
83 | |
84 | char parent_val; | |
85 | }; | |
86 | ||
a4bf26dd | 87 | struct rb_radixtree_leaf |
8e6ba6f9 AC |
88 | { |
89 | /* -1 to indicate this is a leaf, not a node */ | |
90 | int nibnum; | |
91 | ||
92 | /* data associated with the key */ | |
93 | void *data; | |
94 | ||
95 | /* key (canonized copy) */ | |
96 | char *key; | |
2fc6772e | 97 | rb_radixtree_elem *parent; |
8e6ba6f9 AC |
98 | |
99 | char parent_val; | |
100 | }; | |
101 | ||
a4bf26dd | 102 | union rb_radixtree_elem |
8e6ba6f9 AC |
103 | { |
104 | int nibnum; | |
2fc6772e | 105 | rb_radixtree_node node; |
8e6ba6f9 | 106 | |
2fc6772e | 107 | rb_radixtree_leaf leaf; |
8e6ba6f9 AC |
108 | }; |
109 | ||
110 | #define IS_LEAF(elem) ((elem)->nibnum == -1) | |
111 | ||
112 | /* Preserve compatibility with the old mowgli_patricia.h */ | |
113 | #define STATE_CUR(state) ((state)->pspare[0]) | |
114 | #define STATE_NEXT(state) ((state)->pspare[1]) | |
115 | ||
116 | /* | |
117 | * first_leaf() | |
118 | * | |
119 | * Find the smallest leaf hanging off a subtree. | |
120 | * | |
121 | * Inputs: | |
122 | * - element (may be leaf or node) heading subtree | |
123 | * | |
124 | * Outputs: | |
125 | * - lowest leaf in subtree | |
126 | * | |
127 | * Side Effects: | |
128 | * - none | |
129 | */ | |
2fc6772e EM |
130 | static rb_radixtree_elem * |
131 | first_leaf(rb_radixtree_elem *delem) | |
8e6ba6f9 AC |
132 | { |
133 | int val; | |
134 | ||
135 | while (!IS_LEAF(delem)) | |
136 | { | |
137 | for (val = 0; val < POINTERS_PER_NODE; val++) | |
138 | if (delem->node.down[val] != NULL) | |
139 | { | |
140 | delem = delem->node.down[val]; | |
141 | break; | |
142 | } | |
143 | } | |
144 | ||
145 | return delem; | |
146 | } | |
147 | ||
8e6ba6f9 | 148 | /* |
a4bf26dd | 149 | * rb_radixtree_create_named(const char *name, |
8e6ba6f9 AC |
150 | * void (*canonize_cb)(char *key)) |
151 | * | |
152 | * Dictionary object factory. | |
153 | * | |
154 | * Inputs: | |
155 | * - patricia name | |
156 | * - function to use for canonizing keys (for example, use | |
157 | * a function that makes the string upper case to create | |
158 | * a patricia with case-insensitive matching) | |
159 | * | |
160 | * Outputs: | |
161 | * - on success, a new patricia object. | |
162 | * | |
163 | * Side Effects: | |
164 | * - if services runs out of memory and cannot allocate the object, | |
165 | * the program will abort. | |
166 | */ | |
2fc6772e | 167 | rb_radixtree * |
a4bf26dd | 168 | rb_radixtree_create(const char *name, void (*canonize_cb)(char *key)) |
8e6ba6f9 | 169 | { |
2fc6772e | 170 | rb_radixtree *dtree = (rb_radixtree *) rb_malloc(sizeof(rb_radixtree)); |
8e6ba6f9 AC |
171 | |
172 | dtree->canonize_cb = canonize_cb; | |
173 | dtree->id = rb_strdup(name); | |
174 | dtree->root = NULL; | |
175 | ||
325cc939 AC |
176 | rb_dlinkAdd(dtree, &dtree->node, &radixtree_list); |
177 | ||
8e6ba6f9 AC |
178 | return dtree; |
179 | } | |
180 | ||
181 | /* | |
2fc6772e | 182 | * rb_radixtree_destroy(rb_radixtree *dtree, |
8e6ba6f9 AC |
183 | * void (*destroy_cb)(const char *key, void *data, void *privdata), |
184 | * void *privdata); | |
185 | * | |
186 | * Recursively destroys all nodes in a patricia tree. | |
187 | * | |
188 | * Inputs: | |
189 | * - patricia tree object | |
190 | * - optional iteration callback | |
191 | * - optional opaque/private data to pass to callback | |
192 | * | |
193 | * Outputs: | |
194 | * - nothing | |
195 | * | |
196 | * Side Effects: | |
197 | * - on success, a dtree and optionally it's children are destroyed. | |
198 | * | |
199 | * Notes: | |
200 | * - if this is called without a callback, the objects bound to the | |
201 | * DTree will not be destroyed. | |
202 | */ | |
203 | void | |
2fc6772e | 204 | rb_radixtree_destroy(rb_radixtree *dtree, void (*destroy_cb)(const char *key, void *data, void *privdata), void *privdata) |
8e6ba6f9 | 205 | { |
2fc6772e EM |
206 | rb_radixtree_iteration_state state; |
207 | rb_radixtree_elem *delem; | |
8e6ba6f9 AC |
208 | |
209 | void *entry; | |
210 | ||
a4bf26dd | 211 | lrb_assert(dtree != NULL); |
8e6ba6f9 | 212 | |
a4bf26dd | 213 | RB_RADIXTREE_FOREACH(entry, &state, dtree) |
8e6ba6f9 AC |
214 | { |
215 | delem = STATE_CUR(&state); | |
216 | ||
217 | if (destroy_cb != NULL) | |
218 | (*destroy_cb)(delem->leaf.key, delem->leaf.data, | |
219 | privdata); | |
220 | ||
a4bf26dd | 221 | rb_radixtree_delete(dtree, delem->leaf.key); |
8e6ba6f9 AC |
222 | } |
223 | ||
55d5f797 AC |
224 | rb_dlinkDelete(&dtree->node, &radixtree_list); |
225 | rb_free(dtree->id); | |
8e6ba6f9 AC |
226 | rb_free(dtree); |
227 | } | |
228 | ||
229 | /* | |
2fc6772e | 230 | * rb_radixtree_foreach(rb_radixtree *dtree, |
8e6ba6f9 AC |
231 | * int (*foreach_cb)(const char *key, void *data, void *privdata), |
232 | * void *privdata); | |
233 | * | |
234 | * Iterates over all entries in a DTree. | |
235 | * | |
236 | * Inputs: | |
237 | * - patricia tree object | |
238 | * - optional iteration callback | |
239 | * - optional opaque/private data to pass to callback | |
240 | * | |
241 | * Outputs: | |
242 | * - nothing | |
243 | * | |
244 | * Side Effects: | |
245 | * - on success, a dtree is iterated | |
246 | */ | |
247 | void | |
2fc6772e | 248 | rb_radixtree_foreach(rb_radixtree *dtree, int (*foreach_cb)(const char *key, void *data, void *privdata), void *privdata) |
8e6ba6f9 | 249 | { |
2fc6772e | 250 | rb_radixtree_elem *delem, *next; |
8e6ba6f9 AC |
251 | |
252 | int val; | |
253 | ||
a4bf26dd | 254 | lrb_assert(dtree != NULL); |
8e6ba6f9 AC |
255 | |
256 | delem = dtree->root; | |
257 | ||
258 | if (delem == NULL) | |
259 | return; | |
260 | ||
261 | /* Only one element in the tree */ | |
262 | if (IS_LEAF(delem)) | |
263 | { | |
264 | if (foreach_cb != NULL) | |
265 | (*foreach_cb)(delem->leaf.key, delem->leaf.data, privdata); | |
266 | ||
267 | return; | |
268 | } | |
269 | ||
270 | val = 0; | |
271 | ||
272 | do | |
273 | { | |
274 | do | |
275 | next = delem->node.down[val++]; | |
276 | while (next == NULL && val < POINTERS_PER_NODE); | |
277 | ||
278 | if (next != NULL) | |
279 | { | |
280 | if (IS_LEAF(next)) | |
281 | { | |
282 | if (foreach_cb != NULL) | |
283 | (*foreach_cb)(next->leaf.key, next->leaf.data, privdata); | |
284 | } | |
285 | else | |
286 | { | |
287 | delem = next; | |
288 | val = 0; | |
289 | } | |
290 | } | |
291 | ||
292 | while (val >= POINTERS_PER_NODE) | |
293 | { | |
294 | val = delem->node.parent_val; | |
295 | delem = delem->node.parent; | |
296 | ||
297 | if (delem == NULL) | |
298 | break; | |
299 | ||
300 | val++; | |
301 | } | |
302 | } while (delem != NULL); | |
303 | } | |
304 | ||
305 | /* | |
2fc6772e | 306 | * rb_radixtree_search(rb_radixtree *dtree, |
8e6ba6f9 AC |
307 | * void *(*foreach_cb)(const char *key, void *data, void *privdata), |
308 | * void *privdata); | |
309 | * | |
310 | * Searches all entries in a DTree using a custom callback. | |
311 | * | |
312 | * Inputs: | |
313 | * - patricia tree object | |
314 | * - optional iteration callback | |
315 | * - optional opaque/private data to pass to callback | |
316 | * | |
317 | * Outputs: | |
318 | * - on success, the requested object | |
319 | * - on failure, NULL. | |
320 | * | |
321 | * Side Effects: | |
322 | * - a dtree is iterated until the requested conditions are met | |
323 | */ | |
324 | void * | |
2fc6772e | 325 | rb_radixtree_search(rb_radixtree *dtree, void *(*foreach_cb)(const char *key, void *data, void *privdata), void *privdata) |
8e6ba6f9 | 326 | { |
2fc6772e | 327 | rb_radixtree_elem *delem, *next; |
8e6ba6f9 AC |
328 | |
329 | int val; | |
330 | void *ret = NULL; | |
331 | ||
a4bf26dd | 332 | lrb_assert(dtree != NULL); |
8e6ba6f9 AC |
333 | |
334 | delem = dtree->root; | |
335 | ||
336 | if (delem == NULL) | |
337 | return NULL; | |
338 | ||
339 | /* Only one element in the tree */ | |
340 | if (IS_LEAF(delem)) | |
341 | { | |
342 | if (foreach_cb != NULL) | |
343 | return (*foreach_cb)(delem->leaf.key, delem->leaf.data, privdata); | |
344 | ||
345 | return NULL; | |
346 | } | |
347 | ||
348 | val = 0; | |
349 | ||
350 | for (;;) | |
351 | { | |
352 | do | |
353 | next = delem->node.down[val++]; | |
354 | while (next == NULL && val < POINTERS_PER_NODE); | |
355 | ||
356 | if (next != NULL) | |
357 | { | |
358 | if (IS_LEAF(next)) | |
359 | { | |
360 | if (foreach_cb != NULL) | |
361 | ret = (*foreach_cb)(next->leaf.key, next->leaf.data, privdata); | |
362 | ||
363 | if (ret != NULL) | |
364 | break; | |
365 | } | |
366 | else | |
367 | { | |
368 | delem = next; | |
369 | val = 0; | |
370 | } | |
371 | } | |
372 | ||
373 | while (val >= POINTERS_PER_NODE) | |
374 | { | |
375 | val = delem->node.parent_val; | |
376 | delem = delem->node.parent; | |
377 | ||
378 | if (delem == NULL) | |
379 | break; | |
380 | ||
381 | val++; | |
382 | } | |
383 | } | |
384 | ||
385 | return ret; | |
386 | } | |
387 | ||
388 | /* | |
2fc6772e EM |
389 | * rb_radixtree_foreach_start(rb_radixtree *dtree, |
390 | * rb_radixtree_iteration_state *state); | |
8e6ba6f9 AC |
391 | * |
392 | * Initializes a static DTree iterator. | |
393 | * | |
394 | * Inputs: | |
395 | * - patricia tree object | |
396 | * - static DTree iterator | |
397 | * | |
398 | * Outputs: | |
399 | * - nothing | |
400 | * | |
401 | * Side Effects: | |
402 | * - the static iterator, &state, is initialized. | |
403 | */ | |
404 | void | |
2fc6772e | 405 | rb_radixtree_foreach_start(rb_radixtree *dtree, rb_radixtree_iteration_state *state) |
8e6ba6f9 AC |
406 | { |
407 | if (dtree == NULL) | |
408 | return; | |
409 | ||
a4bf26dd | 410 | lrb_assert(state != NULL); |
8e6ba6f9 AC |
411 | |
412 | if (dtree->root != NULL) | |
413 | STATE_NEXT(state) = first_leaf(dtree->root); | |
414 | else | |
415 | STATE_NEXT(state) = NULL; | |
416 | ||
417 | STATE_CUR(state) = STATE_NEXT(state); | |
418 | ||
419 | if (STATE_NEXT(state) == NULL) | |
420 | return; | |
421 | ||
422 | /* make STATE_CUR point to first item and STATE_NEXT point to | |
423 | * second item */ | |
a4bf26dd | 424 | rb_radixtree_foreach_next(dtree, state); |
8e6ba6f9 AC |
425 | } |
426 | ||
427 | /* | |
2fc6772e EM |
428 | * rb_radixtree_foreach_cur(rb_radixtree *dtree, |
429 | * rb_radixtree_iteration_state *state); | |
8e6ba6f9 AC |
430 | * |
431 | * Returns the data from the current node being iterated by the | |
432 | * static iterator. | |
433 | * | |
434 | * Inputs: | |
435 | * - patricia tree object | |
436 | * - static DTree iterator | |
437 | * | |
438 | * Outputs: | |
439 | * - reference to data in the current dtree node being iterated | |
440 | * | |
441 | * Side Effects: | |
442 | * - none | |
443 | */ | |
444 | void * | |
2fc6772e | 445 | rb_radixtree_foreach_cur(rb_radixtree *dtree, rb_radixtree_iteration_state *state) |
8e6ba6f9 AC |
446 | { |
447 | if (dtree == NULL) | |
448 | return NULL; | |
449 | ||
a4bf26dd | 450 | lrb_assert(state != NULL); |
8e6ba6f9 AC |
451 | |
452 | return STATE_CUR(state) != NULL ? | |
2fc6772e | 453 | ((rb_radixtree_leaf *) STATE_CUR(state))->data : NULL; |
8e6ba6f9 AC |
454 | } |
455 | ||
456 | /* | |
2fc6772e EM |
457 | * rb_radixtree_foreach_next(rb_radixtree *dtree, |
458 | * rb_radixtree_iteration_state *state); | |
8e6ba6f9 AC |
459 | * |
460 | * Advances a static DTree iterator. | |
461 | * | |
462 | * Inputs: | |
463 | * - patricia tree object | |
464 | * - static DTree iterator | |
465 | * | |
466 | * Outputs: | |
467 | * - nothing | |
468 | * | |
469 | * Side Effects: | |
470 | * - the static iterator, &state, is advanced to a new DTree node. | |
471 | */ | |
472 | void | |
2fc6772e | 473 | rb_radixtree_foreach_next(rb_radixtree *dtree, rb_radixtree_iteration_state *state) |
8e6ba6f9 | 474 | { |
2fc6772e | 475 | rb_radixtree_leaf *leaf; |
8e6ba6f9 | 476 | |
2fc6772e | 477 | rb_radixtree_elem *delem, *next; |
8e6ba6f9 AC |
478 | |
479 | int val; | |
480 | ||
481 | if (dtree == NULL) | |
482 | return; | |
483 | ||
a4bf26dd | 484 | lrb_assert(state != NULL); |
8e6ba6f9 AC |
485 | |
486 | if (STATE_CUR(state) == NULL) | |
487 | return; | |
488 | ||
489 | STATE_CUR(state) = STATE_NEXT(state); | |
490 | ||
491 | if (STATE_NEXT(state) == NULL) | |
492 | return; | |
493 | ||
494 | leaf = STATE_NEXT(state); | |
495 | delem = leaf->parent; | |
496 | val = leaf->parent_val; | |
497 | ||
498 | while (delem != NULL) | |
499 | { | |
500 | do | |
501 | next = delem->node.down[val++]; | |
502 | while (next == NULL && val < POINTERS_PER_NODE); | |
503 | ||
504 | if (next != NULL) | |
505 | { | |
506 | if (IS_LEAF(next)) | |
507 | { | |
508 | /* We will find the original leaf first. */ | |
509 | if (&next->leaf != leaf) | |
510 | { | |
511 | if (strcmp(next->leaf.key, leaf->key) < 0) | |
512 | { | |
513 | STATE_NEXT(state) = NULL; | |
514 | return; | |
515 | } | |
516 | ||
517 | STATE_NEXT(state) = next; | |
518 | return; | |
519 | } | |
520 | } | |
521 | else | |
522 | { | |
523 | delem = next; | |
524 | val = 0; | |
525 | } | |
526 | } | |
527 | ||
528 | while (val >= POINTERS_PER_NODE) | |
529 | { | |
530 | val = delem->node.parent_val; | |
531 | delem = delem->node.parent; | |
532 | ||
533 | if (delem == NULL) | |
534 | break; | |
535 | ||
536 | val++; | |
537 | } | |
538 | } | |
539 | ||
540 | STATE_NEXT(state) = NULL; | |
541 | } | |
542 | ||
543 | /* | |
2fc6772e | 544 | * rb_radixtree_elem_find(rb_radixtree *dtree, const char *key) |
8e6ba6f9 AC |
545 | * |
546 | * Looks up a DTree node by name. | |
547 | * | |
548 | * Inputs: | |
549 | * - patricia tree object | |
550 | * - name of node to lookup | |
704697b6 | 551 | * - whether to do a direct or fuzzy match |
8e6ba6f9 AC |
552 | * |
553 | * Outputs: | |
554 | * - on success, the dtree node requested | |
555 | * - on failure, NULL | |
556 | * | |
557 | * Side Effects: | |
558 | * - none | |
559 | */ | |
2fc6772e EM |
560 | rb_radixtree_leaf * |
561 | rb_radixtree_elem_find(rb_radixtree *dict, const char *key, int fuzzy) | |
8e6ba6f9 AC |
562 | { |
563 | char ckey_store[256]; | |
564 | ||
565 | char *ckey_buf = NULL; | |
566 | const char *ckey; | |
2fc6772e | 567 | rb_radixtree_elem *delem; |
8e6ba6f9 AC |
568 | |
569 | int val, keylen; | |
570 | ||
a4bf26dd EM |
571 | lrb_assert(dict != NULL); |
572 | lrb_assert(key != NULL); | |
8e6ba6f9 AC |
573 | |
574 | keylen = strlen(key); | |
575 | ||
576 | if (dict->canonize_cb == NULL) | |
577 | { | |
578 | ckey = key; | |
579 | } | |
580 | else | |
581 | { | |
582 | if (keylen >= (int) sizeof(ckey_store)) | |
583 | { | |
584 | ckey_buf = rb_strdup(key); | |
585 | dict->canonize_cb(ckey_buf); | |
586 | ckey = ckey_buf; | |
587 | } | |
588 | else | |
589 | { | |
590 | rb_strlcpy(ckey_store, key, sizeof ckey_store); | |
591 | dict->canonize_cb(ckey_store); | |
592 | ckey = ckey_store; | |
593 | } | |
594 | } | |
595 | ||
596 | delem = dict->root; | |
597 | ||
598 | while (delem != NULL && !IS_LEAF(delem)) | |
599 | { | |
600 | if (delem->nibnum / 2 < keylen) | |
601 | val = NIBBLE_VAL(ckey, delem->nibnum); | |
602 | else | |
603 | val = 0; | |
604 | ||
605 | delem = delem->node.down[val]; | |
606 | } | |
607 | ||
608 | /* Now, if the key is in the tree, delem contains it. */ | |
704697b6 | 609 | if ((delem != NULL) && !fuzzy && strcmp(delem->leaf.key, ckey)) |
8e6ba6f9 AC |
610 | delem = NULL; |
611 | ||
612 | if (ckey_buf != NULL) | |
613 | rb_free(ckey_buf); | |
614 | ||
615 | return &delem->leaf; | |
616 | } | |
617 | ||
0d9a72de | 618 | /* |
2fc6772e | 619 | * rb_radixtree_foreach_start_from(rb_radixtree *dtree, rb_radixtree_iteration_state *state, const char *key) |
0d9a72de | 620 | * |
a4bf26dd | 621 | * Starts iteration from a specified key, by wrapping rb_radixtree_elem_find(). |
0d9a72de AC |
622 | * |
623 | * Inputs: | |
624 | * - patricia tree object | |
625 | * - iterator | |
626 | * - key to start from | |
627 | * | |
628 | * Outputs: | |
629 | * - none | |
630 | * | |
631 | * Side Effects: | |
632 | * - the iterator's state is initialized at a specific point | |
633 | */ | |
634 | void | |
2fc6772e | 635 | rb_radixtree_foreach_start_from(rb_radixtree *dtree, rb_radixtree_iteration_state *state, const char *key) |
0d9a72de | 636 | { |
a4bf26dd EM |
637 | lrb_assert(dtree != NULL); |
638 | lrb_assert(state != NULL); | |
0d9a72de AC |
639 | |
640 | if (key != NULL) | |
641 | { | |
642 | STATE_CUR(state) = NULL; | |
a4bf26dd | 643 | STATE_NEXT(state) = rb_radixtree_elem_find(dtree, key, 1); |
0d9a72de AC |
644 | |
645 | /* make STATE_CUR point to selected item and STATE_NEXT point to | |
646 | * next item in the tree */ | |
a4bf26dd | 647 | rb_radixtree_foreach_next(dtree, state); |
0d9a72de AC |
648 | } |
649 | else | |
a4bf26dd | 650 | rb_radixtree_foreach_start(dtree, state); |
0d9a72de AC |
651 | } |
652 | ||
8e6ba6f9 | 653 | /* |
2fc6772e | 654 | * rb_radixtree_add(rb_radixtree *dtree, const char *key, void *data) |
8e6ba6f9 AC |
655 | * |
656 | * Creates a new DTree node and binds data to it. | |
657 | * | |
658 | * Inputs: | |
659 | * - patricia tree object | |
660 | * - name for new DTree node | |
661 | * - data to bind to the new DTree node | |
662 | * | |
663 | * Outputs: | |
664 | * - on success, TRUE | |
665 | * - on failure, FALSE | |
666 | * | |
667 | * Side Effects: | |
668 | * - data is inserted into the DTree. | |
669 | */ | |
2fc6772e EM |
670 | rb_radixtree_leaf * |
671 | rb_radixtree_elem_add(rb_radixtree *dict, const char *key, void *data) | |
8e6ba6f9 AC |
672 | { |
673 | char *ckey; | |
674 | ||
2fc6772e | 675 | rb_radixtree_elem *delem, *prev, *newnode; |
8e6ba6f9 | 676 | |
2fc6772e | 677 | rb_radixtree_elem **place1; |
8e6ba6f9 AC |
678 | |
679 | int val, keylen; | |
680 | int i, j; | |
681 | ||
a4bf26dd EM |
682 | lrb_assert(dict != NULL); |
683 | lrb_assert(key != NULL); | |
684 | lrb_assert(data != NULL); | |
8e6ba6f9 AC |
685 | |
686 | keylen = strlen(key); | |
687 | ckey = rb_strdup(key); | |
688 | ||
689 | if (ckey == NULL) | |
690 | return NULL; | |
691 | ||
692 | if (dict->canonize_cb != NULL) | |
693 | dict->canonize_cb(ckey); | |
694 | ||
695 | prev = NULL; | |
696 | val = POINTERS_PER_NODE + 2; /* trap value */ | |
697 | delem = dict->root; | |
698 | ||
699 | while (delem != NULL && !IS_LEAF(delem)) | |
700 | { | |
701 | prev = delem; | |
702 | ||
703 | if (delem->nibnum / 2 < keylen) | |
704 | val = NIBBLE_VAL(ckey, delem->nibnum); | |
705 | else | |
706 | val = 0; | |
707 | ||
708 | delem = delem->node.down[val]; | |
709 | } | |
710 | ||
711 | /* Now, if the key is in the tree, delem contains it. */ | |
712 | if ((delem != NULL) && !strcmp(delem->leaf.key, ckey)) | |
713 | { | |
714 | rb_free(ckey); | |
715 | return NULL; | |
716 | } | |
717 | ||
718 | if ((delem == NULL) && (prev != NULL)) | |
719 | /* Get a leaf to compare with. */ | |
720 | delem = first_leaf(prev); | |
721 | ||
722 | if (delem == NULL) | |
723 | { | |
a4bf26dd EM |
724 | lrb_assert(prev == NULL); |
725 | lrb_assert(dict->count == 0); | |
8e6ba6f9 | 726 | place1 = &dict->root; |
2fc6772e | 727 | *place1 = rb_malloc(sizeof(rb_radixtree_leaf)); |
a4bf26dd | 728 | lrb_assert(*place1 != NULL); |
8e6ba6f9 AC |
729 | (*place1)->nibnum = -1; |
730 | (*place1)->leaf.data = data; | |
731 | (*place1)->leaf.key = ckey; | |
732 | (*place1)->leaf.parent = prev; | |
733 | (*place1)->leaf.parent_val = val; | |
734 | dict->count++; | |
735 | return &(*place1)->leaf; | |
736 | } | |
737 | ||
738 | /* Find the first nibble where they differ. */ | |
739 | for (i = 0; NIBBLE_VAL(ckey, i) == NIBBLE_VAL(delem->leaf.key, i); i++) | |
740 | ; | |
741 | ||
742 | /* Find where to insert the new node. */ | |
743 | while (prev != NULL && prev->nibnum > i) | |
744 | { | |
745 | val = prev->node.parent_val; | |
746 | prev = prev->node.parent; | |
747 | } | |
748 | ||
749 | if ((prev == NULL) || (prev->nibnum < i)) | |
750 | { | |
751 | /* Insert new node below prev */ | |
2fc6772e | 752 | newnode = rb_malloc(sizeof(rb_radixtree_node)); |
a4bf26dd | 753 | lrb_assert(newnode != NULL); |
8e6ba6f9 AC |
754 | newnode->nibnum = i; |
755 | newnode->node.parent = prev; | |
756 | newnode->node.parent_val = val; | |
757 | ||
758 | for (j = 0; j < POINTERS_PER_NODE; j++) | |
759 | newnode->node.down[j] = NULL; | |
760 | ||
761 | if (prev == NULL) | |
762 | { | |
763 | newnode->node.down[NIBBLE_VAL(delem->leaf.key, i)] = dict->root; | |
764 | ||
765 | if (IS_LEAF(dict->root)) | |
766 | { | |
767 | dict->root->leaf.parent = newnode; | |
768 | dict->root->leaf.parent_val = NIBBLE_VAL(delem->leaf.key, i); | |
769 | } | |
770 | else | |
771 | { | |
a4bf26dd | 772 | lrb_assert(dict->root->nibnum > i); |
8e6ba6f9 AC |
773 | dict->root->node.parent = newnode; |
774 | dict->root->node.parent_val = NIBBLE_VAL(delem->leaf.key, i); | |
775 | } | |
776 | ||
777 | dict->root = newnode; | |
778 | } | |
779 | else | |
780 | { | |
781 | newnode->node.down[NIBBLE_VAL(delem->leaf.key, i)] = prev->node.down[val]; | |
782 | ||
783 | if (IS_LEAF(prev->node.down[val])) | |
784 | { | |
785 | prev->node.down[val]->leaf.parent = newnode; | |
786 | prev->node.down[val]->leaf.parent_val = NIBBLE_VAL(delem->leaf.key, i); | |
787 | } | |
788 | else | |
789 | { | |
790 | prev->node.down[val]->node.parent = newnode; | |
791 | prev->node.down[val]->node.parent_val = NIBBLE_VAL(delem->leaf.key, i); | |
792 | } | |
793 | ||
794 | prev->node.down[val] = newnode; | |
795 | } | |
796 | } | |
797 | else | |
798 | { | |
799 | /* This nibble is already checked. */ | |
a4bf26dd | 800 | lrb_assert(prev->nibnum == i); |
8e6ba6f9 AC |
801 | newnode = prev; |
802 | } | |
803 | ||
804 | val = NIBBLE_VAL(ckey, i); | |
805 | place1 = &newnode->node.down[val]; | |
a4bf26dd | 806 | lrb_assert(*place1 == NULL); |
2fc6772e | 807 | *place1 = rb_malloc(sizeof(rb_radixtree_leaf)); |
a4bf26dd | 808 | lrb_assert(*place1 != NULL); |
8e6ba6f9 AC |
809 | (*place1)->nibnum = -1; |
810 | (*place1)->leaf.data = data; | |
811 | (*place1)->leaf.key = ckey; | |
812 | (*place1)->leaf.parent = newnode; | |
813 | (*place1)->leaf.parent_val = val; | |
814 | dict->count++; | |
815 | return &(*place1)->leaf; | |
816 | } | |
817 | ||
818 | int | |
2fc6772e | 819 | rb_radixtree_add(rb_radixtree *dict, const char *key, void *data) |
8e6ba6f9 | 820 | { |
a4bf26dd | 821 | return (rb_radixtree_elem_add(dict, key, data) != NULL); |
8e6ba6f9 AC |
822 | } |
823 | ||
824 | /* | |
2fc6772e | 825 | * rb_radixtree_delete(rb_radixtree *dtree, const char *key) |
8e6ba6f9 AC |
826 | * |
827 | * Deletes data from a patricia tree. | |
828 | * | |
829 | * Inputs: | |
830 | * - patricia tree object | |
831 | * - name of DTree node to delete | |
832 | * | |
833 | * Outputs: | |
834 | * - on success, the remaining data that needs to be rb_freed | |
835 | * - on failure, NULL | |
836 | * | |
837 | * Side Effects: | |
838 | * - data is removed from the DTree. | |
839 | * | |
840 | * Notes: | |
841 | * - the returned data needs to be rb_freed/released manually! | |
842 | */ | |
843 | void * | |
2fc6772e | 844 | rb_radixtree_delete(rb_radixtree *dict, const char *key) |
8e6ba6f9 AC |
845 | { |
846 | void *data; | |
2fc6772e | 847 | rb_radixtree_leaf *leaf; |
8e6ba6f9 | 848 | |
a4bf26dd | 849 | leaf = rb_radixtree_elem_find(dict, key, 0); |
8e6ba6f9 AC |
850 | |
851 | if (leaf == NULL) | |
852 | return NULL; | |
853 | ||
854 | data = leaf->data; | |
a4bf26dd | 855 | rb_radixtree_elem_delete(dict, leaf); |
8e6ba6f9 AC |
856 | return data; |
857 | } | |
858 | ||
859 | void | |
2fc6772e | 860 | rb_radixtree_elem_delete(rb_radixtree *dict, rb_radixtree_leaf *leaf) |
8e6ba6f9 | 861 | { |
2fc6772e | 862 | rb_radixtree_elem *delem, *prev, *next; |
8e6ba6f9 AC |
863 | |
864 | int val, i, used; | |
865 | ||
a4bf26dd EM |
866 | lrb_assert(dict != NULL); |
867 | lrb_assert(leaf != NULL); | |
8e6ba6f9 | 868 | |
2fc6772e | 869 | delem = (rb_radixtree_elem *) leaf; |
8e6ba6f9 AC |
870 | |
871 | val = delem->leaf.parent_val; | |
872 | prev = delem->leaf.parent; | |
873 | ||
874 | rb_free(delem->leaf.key); | |
875 | rb_free(delem); | |
876 | ||
877 | if (prev != NULL) | |
878 | { | |
879 | prev->node.down[val] = NULL; | |
880 | ||
881 | /* Leaf is gone, now consider the node it was in. */ | |
882 | delem = prev; | |
883 | ||
884 | used = -1; | |
885 | ||
886 | for (i = 0; i < POINTERS_PER_NODE; i++) | |
887 | if (delem->node.down[i] != NULL) | |
888 | used = used == -1 ? i : -2; | |
889 | ||
a4bf26dd | 890 | lrb_assert(used == -2 || used >= 0); |
8e6ba6f9 AC |
891 | |
892 | if (used >= 0) | |
893 | { | |
894 | /* Only one pointer in this node, remove it. | |
895 | * Replace the pointer that pointed to it by | |
896 | * the sole pointer in it. | |
897 | */ | |
898 | next = delem->node.down[used]; | |
899 | val = delem->node.parent_val; | |
900 | prev = delem->node.parent; | |
901 | ||
902 | if (prev != NULL) | |
903 | prev->node.down[val] = next; | |
904 | else | |
905 | dict->root = next; | |
906 | ||
907 | if (IS_LEAF(next)) | |
908 | next->leaf.parent = prev, next->leaf.parent_val = val; | |
909 | else | |
910 | next->node.parent = prev, next->node.parent_val = val; | |
911 | ||
912 | rb_free(delem); | |
913 | } | |
914 | } | |
915 | else | |
916 | { | |
917 | /* This was the last leaf. */ | |
918 | dict->root = NULL; | |
919 | } | |
920 | ||
921 | dict->count--; | |
922 | ||
923 | if (dict->count == 0) | |
924 | { | |
a4bf26dd | 925 | lrb_assert(dict->root == NULL); |
8e6ba6f9 AC |
926 | dict->root = NULL; |
927 | } | |
928 | } | |
929 | ||
930 | /* | |
2fc6772e | 931 | * rb_radixtree_retrieve(rb_radixtree *dtree, const char *key) |
8e6ba6f9 AC |
932 | * |
933 | * Retrieves data from a patricia. | |
934 | * | |
935 | * Inputs: | |
936 | * - patricia tree object | |
937 | * - name of node to lookup | |
938 | * | |
939 | * Outputs: | |
940 | * - on success, the data bound to the DTree node. | |
941 | * - on failure, NULL | |
942 | * | |
943 | * Side Effects: | |
944 | * - none | |
945 | */ | |
946 | void * | |
2fc6772e | 947 | rb_radixtree_retrieve(rb_radixtree *dtree, const char *key) |
8e6ba6f9 | 948 | { |
2fc6772e | 949 | rb_radixtree_leaf *delem = rb_radixtree_elem_find(dtree, key, 0); |
8e6ba6f9 AC |
950 | |
951 | if (delem != NULL) | |
952 | return delem->data; | |
953 | ||
954 | return NULL; | |
955 | } | |
956 | ||
957 | const char * | |
2fc6772e | 958 | rb_radixtree_elem_get_key(rb_radixtree_leaf *leaf) |
8e6ba6f9 | 959 | { |
a4bf26dd | 960 | lrb_assert(leaf != NULL); |
8e6ba6f9 AC |
961 | |
962 | return leaf->key; | |
963 | } | |
964 | ||
965 | void | |
2fc6772e | 966 | rb_radixtree_elem_set_data(rb_radixtree_leaf *leaf, void *data) |
8e6ba6f9 | 967 | { |
a4bf26dd | 968 | lrb_assert(leaf != NULL); |
8e6ba6f9 AC |
969 | |
970 | leaf->data = data; | |
971 | } | |
972 | ||
973 | void * | |
2fc6772e | 974 | rb_radixtree_elem_get_data(rb_radixtree_leaf *leaf) |
8e6ba6f9 | 975 | { |
a4bf26dd | 976 | lrb_assert(leaf != NULL); |
8e6ba6f9 AC |
977 | |
978 | return leaf->data; | |
979 | } | |
980 | ||
981 | /* | |
2fc6772e | 982 | * rb_radixtree_size(rb_radixtree *dict) |
8e6ba6f9 AC |
983 | * |
984 | * Returns the size of a patricia. | |
985 | * | |
986 | * Inputs: | |
987 | * - patricia tree object | |
988 | * | |
989 | * Outputs: | |
990 | * - size of patricia | |
991 | * | |
992 | * Side Effects: | |
993 | * - none | |
994 | */ | |
995 | unsigned int | |
2fc6772e | 996 | rb_radixtree_size(rb_radixtree *dict) |
8e6ba6f9 | 997 | { |
a4bf26dd | 998 | lrb_assert(dict != NULL); |
8e6ba6f9 AC |
999 | |
1000 | return dict->count; | |
1001 | } | |
1002 | ||
1003 | /* returns the sum of the depths of the subtree rooted in delem at depth depth */ | |
1004 | /* there is no need for this to be recursive, but it is easier... */ | |
1005 | static int | |
2fc6772e | 1006 | stats_recurse(rb_radixtree_elem *delem, int depth, int *pmaxdepth) |
8e6ba6f9 AC |
1007 | { |
1008 | int result = 0; | |
1009 | int val; | |
2fc6772e | 1010 | rb_radixtree_elem *next; |
8e6ba6f9 AC |
1011 | |
1012 | if (depth > *pmaxdepth) | |
1013 | *pmaxdepth = depth; | |
1014 | ||
1015 | if (depth == 0) | |
1016 | { | |
1017 | if (IS_LEAF(delem)) | |
a4bf26dd | 1018 | lrb_assert(delem->leaf.parent == NULL); |
8e6ba6f9 AC |
1019 | |
1020 | else | |
a4bf26dd | 1021 | lrb_assert(delem->node.parent == NULL); |
8e6ba6f9 AC |
1022 | } |
1023 | ||
1024 | if (IS_LEAF(delem)) | |
1025 | return depth; | |
1026 | ||
1027 | for (val = 0; val < POINTERS_PER_NODE; val++) | |
1028 | { | |
1029 | next = delem->node.down[val]; | |
1030 | ||
1031 | if (next == NULL) | |
1032 | continue; | |
1033 | ||
1034 | result += stats_recurse(next, depth + 1, pmaxdepth); | |
1035 | ||
1036 | if (IS_LEAF(next)) | |
1037 | { | |
a4bf26dd EM |
1038 | lrb_assert(next->leaf.parent == delem); |
1039 | lrb_assert(next->leaf.parent_val == val); | |
8e6ba6f9 AC |
1040 | } |
1041 | else | |
1042 | { | |
a4bf26dd EM |
1043 | lrb_assert(next->node.parent == delem); |
1044 | lrb_assert(next->node.parent_val == val); | |
1045 | lrb_assert(next->node.nibnum > delem->node.nibnum); | |
8e6ba6f9 AC |
1046 | } |
1047 | } | |
1048 | ||
1049 | return result; | |
1050 | } | |
1051 | ||
1052 | /* | |
2fc6772e | 1053 | * rb_radixtree_stats(rb_radixtree *dict, void (*cb)(const char *line, void *privdata), void *privdata) |
8e6ba6f9 AC |
1054 | * |
1055 | * Returns the size of a patricia. | |
1056 | * | |
1057 | * Inputs: | |
1058 | * - patricia tree object | |
1059 | * - callback | |
1060 | * - data for callback | |
1061 | * | |
1062 | * Outputs: | |
1063 | * - none | |
1064 | * | |
1065 | * Side Effects: | |
1066 | * - callback called with stats text | |
1067 | */ | |
1068 | void | |
2fc6772e | 1069 | rb_radixtree_stats(rb_radixtree *dict, void (*cb)(const char *line, void *privdata), void *privdata) |
8e6ba6f9 AC |
1070 | { |
1071 | char str[256]; | |
1072 | int sum, maxdepth; | |
1073 | ||
a4bf26dd | 1074 | lrb_assert(dict != NULL); |
8e6ba6f9 | 1075 | |
8e6ba6f9 | 1076 | maxdepth = 0; |
8e6ba6f9 AC |
1077 | if (dict->count > 0) |
1078 | { | |
1079 | sum = stats_recurse(dict->root, 0, &maxdepth); | |
8dacf9e9 | 1080 | snprintf(str, sizeof str, "%-30s %-15s %-10d %-10d %-10d %-10d", dict->id, "RADIX", dict->count, sum, sum / dict->count, maxdepth); |
8e6ba6f9 AC |
1081 | } |
1082 | else | |
1083 | { | |
8dacf9e9 | 1084 | snprintf(str, sizeof str, "%-30s %-15s %-10s %-10s %-10s %-10s", dict->id, "RADIX", "0", "0", "0", "0"); |
8e6ba6f9 AC |
1085 | } |
1086 | ||
1087 | cb(str, privdata); | |
1088 | return; | |
1089 | } | |
325cc939 AC |
1090 | |
1091 | void | |
a4bf26dd | 1092 | rb_radixtree_stats_walk(void (*cb)(const char *line, void *privdata), void *privdata) |
325cc939 AC |
1093 | { |
1094 | rb_dlink_node *ptr; | |
1095 | ||
1096 | RB_DLINK_FOREACH(ptr, radixtree_list.head) | |
1097 | { | |
a4bf26dd | 1098 | rb_radixtree_stats(ptr->data, cb, privdata); |
325cc939 AC |
1099 | } |
1100 | } | |
db891ac3 | 1101 |