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