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