2 * charybdis: an advanced ircd.
3 * irc_radixtree.c: Dictionary-based information storage.
5 * Copyright (c) 2007-2016 William Pitcock <nenolod -at- dereferenced.org>
6 * Copyright (c) 2007-2016 Jilles Tjoelker <jilles -at- stack.nl>
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions are
12 * 1. Redistributions of source code must retain the above copyright notice,
13 * this list of conditions and the following disclaimer.
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.
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.
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.
37 #include "irc_radixtree.h"
39 rb_dlink_list radixtree_list
= {NULL
, NULL
, 0};
44 * A radix trie that avoids one-way branching and redundant nodes.
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.
50 * The nibnum values are strictly increasing while going down the tree.
55 union irc_radixtree_elem
;
59 void (*canonize_cb
)(char *key
);
60 union irc_radixtree_elem
*root
;
68 #define POINTERS_PER_NODE 16
69 #define NIBBLE_VAL(key, nibnum) (((key)[(nibnum) / 2] >> ((nibnum) & 1 ? 0 : 4)) & 0xF)
71 struct irc_radixtree_node
73 /* nibble to test (nibble NUM%2 of byte NUM/2) */
76 /* branches of the tree */
77 union irc_radixtree_elem
*down
[POINTERS_PER_NODE
];
78 union irc_radixtree_elem
*parent
;
83 struct irc_radixtree_leaf
85 /* -1 to indicate this is a leaf, not a node */
88 /* data associated with the key */
91 /* key (canonized copy) */
93 union irc_radixtree_elem
*parent
;
98 union irc_radixtree_elem
101 struct irc_radixtree_node node
;
103 struct irc_radixtree_leaf leaf
;
106 #define IS_LEAF(elem) ((elem)->nibnum == -1)
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])
115 * Find the smallest leaf hanging off a subtree.
118 * - element (may be leaf or node) heading subtree
121 * - lowest leaf in subtree
126 static union irc_radixtree_elem
*
127 first_leaf(union irc_radixtree_elem
*delem
)
131 while (!IS_LEAF(delem
))
133 for (val
= 0; val
< POINTERS_PER_NODE
; val
++)
134 if (delem
->node
.down
[val
] != NULL
)
136 delem
= delem
->node
.down
[val
];
145 * irc_radixtree_create_named(const char *name,
146 * void (*canonize_cb)(char *key))
148 * Dictionary object factory.
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)
157 * - on success, a new patricia object.
160 * - if services runs out of memory and cannot allocate the object,
161 * the program will abort.
163 struct irc_radixtree
*
164 irc_radixtree_create(const char *name
, void (*canonize_cb
)(char *key
))
166 struct irc_radixtree
*dtree
= (struct irc_radixtree
*) rb_malloc(sizeof(struct irc_radixtree
));
168 dtree
->canonize_cb
= canonize_cb
;
169 dtree
->id
= rb_strdup(name
);
172 rb_dlinkAdd(dtree
, &dtree
->node
, &radixtree_list
);
178 * irc_radixtree_destroy(struct irc_radixtree *dtree,
179 * void (*destroy_cb)(const char *key, void *data, void *privdata),
182 * Recursively destroys all nodes in a patricia tree.
185 * - patricia tree object
186 * - optional iteration callback
187 * - optional opaque/private data to pass to callback
193 * - on success, a dtree and optionally it's children are destroyed.
196 * - if this is called without a callback, the objects bound to the
197 * DTree will not be destroyed.
200 irc_radixtree_destroy(struct irc_radixtree
*dtree
, void (*destroy_cb
)(const char *key
, void *data
, void *privdata
), void *privdata
)
202 struct irc_radixtree_iteration_state state
;
203 union irc_radixtree_elem
*delem
;
207 s_assert(dtree
!= NULL
);
209 IRC_RADIXTREE_FOREACH(entry
, &state
, dtree
)
211 delem
= STATE_CUR(&state
);
213 if (destroy_cb
!= NULL
)
214 (*destroy_cb
)(delem
->leaf
.key
, delem
->leaf
.data
,
217 irc_radixtree_delete(dtree
, delem
->leaf
.key
);
224 * irc_radixtree_foreach(struct irc_radixtree *dtree,
225 * int (*foreach_cb)(const char *key, void *data, void *privdata),
228 * Iterates over all entries in a DTree.
231 * - patricia tree object
232 * - optional iteration callback
233 * - optional opaque/private data to pass to callback
239 * - on success, a dtree is iterated
242 irc_radixtree_foreach(struct irc_radixtree
*dtree
, int (*foreach_cb
)(const char *key
, void *data
, void *privdata
), void *privdata
)
244 union irc_radixtree_elem
*delem
, *next
;
248 s_assert(dtree
!= NULL
);
255 /* Only one element in the tree */
258 if (foreach_cb
!= NULL
)
259 (*foreach_cb
)(delem
->leaf
.key
, delem
->leaf
.data
, privdata
);
269 next
= delem
->node
.down
[val
++];
270 while (next
== NULL
&& val
< POINTERS_PER_NODE
);
276 if (foreach_cb
!= NULL
)
277 (*foreach_cb
)(next
->leaf
.key
, next
->leaf
.data
, privdata
);
286 while (val
>= POINTERS_PER_NODE
)
288 val
= delem
->node
.parent_val
;
289 delem
= delem
->node
.parent
;
296 } while (delem
!= NULL
);
300 * irc_radixtree_search(struct irc_radixtree *dtree,
301 * void *(*foreach_cb)(const char *key, void *data, void *privdata),
304 * Searches all entries in a DTree using a custom callback.
307 * - patricia tree object
308 * - optional iteration callback
309 * - optional opaque/private data to pass to callback
312 * - on success, the requested object
313 * - on failure, NULL.
316 * - a dtree is iterated until the requested conditions are met
319 irc_radixtree_search(struct irc_radixtree
*dtree
, void *(*foreach_cb
)(const char *key
, void *data
, void *privdata
), void *privdata
)
321 union irc_radixtree_elem
*delem
, *next
;
326 s_assert(dtree
!= NULL
);
333 /* Only one element in the tree */
336 if (foreach_cb
!= NULL
)
337 return (*foreach_cb
)(delem
->leaf
.key
, delem
->leaf
.data
, privdata
);
347 next
= delem
->node
.down
[val
++];
348 while (next
== NULL
&& val
< POINTERS_PER_NODE
);
354 if (foreach_cb
!= NULL
)
355 ret
= (*foreach_cb
)(next
->leaf
.key
, next
->leaf
.data
, privdata
);
367 while (val
>= POINTERS_PER_NODE
)
369 val
= delem
->node
.parent_val
;
370 delem
= delem
->node
.parent
;
383 * irc_radixtree_foreach_start(struct irc_radixtree *dtree,
384 * struct irc_radixtree_iteration_state *state);
386 * Initializes a static DTree iterator.
389 * - patricia tree object
390 * - static DTree iterator
396 * - the static iterator, &state, is initialized.
399 irc_radixtree_foreach_start(struct irc_radixtree
*dtree
, struct irc_radixtree_iteration_state
*state
)
404 s_assert(state
!= NULL
);
406 if (dtree
->root
!= NULL
)
407 STATE_NEXT(state
) = first_leaf(dtree
->root
);
409 STATE_NEXT(state
) = NULL
;
411 STATE_CUR(state
) = STATE_NEXT(state
);
413 if (STATE_NEXT(state
) == NULL
)
416 /* make STATE_CUR point to first item and STATE_NEXT point to
418 irc_radixtree_foreach_next(dtree
, state
);
422 * irc_radixtree_foreach_cur(struct irc_radixtree *dtree,
423 * struct irc_radixtree_iteration_state *state);
425 * Returns the data from the current node being iterated by the
429 * - patricia tree object
430 * - static DTree iterator
433 * - reference to data in the current dtree node being iterated
439 irc_radixtree_foreach_cur(struct irc_radixtree
*dtree
, struct irc_radixtree_iteration_state
*state
)
444 s_assert(state
!= NULL
);
446 return STATE_CUR(state
) != NULL
?
447 ((struct irc_radixtree_leaf
*) STATE_CUR(state
))->data
: NULL
;
451 * irc_radixtree_foreach_next(struct irc_radixtree *dtree,
452 * struct irc_radixtree_iteration_state *state);
454 * Advances a static DTree iterator.
457 * - patricia tree object
458 * - static DTree iterator
464 * - the static iterator, &state, is advanced to a new DTree node.
467 irc_radixtree_foreach_next(struct irc_radixtree
*dtree
, struct irc_radixtree_iteration_state
*state
)
469 struct irc_radixtree_leaf
*leaf
;
471 union irc_radixtree_elem
*delem
, *next
;
478 s_assert(state
!= NULL
);
480 if (STATE_CUR(state
) == NULL
)
483 STATE_CUR(state
) = STATE_NEXT(state
);
485 if (STATE_NEXT(state
) == NULL
)
488 leaf
= STATE_NEXT(state
);
489 delem
= leaf
->parent
;
490 val
= leaf
->parent_val
;
492 while (delem
!= NULL
)
495 next
= delem
->node
.down
[val
++];
496 while (next
== NULL
&& val
< POINTERS_PER_NODE
);
502 /* We will find the original leaf first. */
503 if (&next
->leaf
!= leaf
)
505 if (strcmp(next
->leaf
.key
, leaf
->key
) < 0)
507 STATE_NEXT(state
) = NULL
;
511 STATE_NEXT(state
) = next
;
522 while (val
>= POINTERS_PER_NODE
)
524 val
= delem
->node
.parent_val
;
525 delem
= delem
->node
.parent
;
534 STATE_NEXT(state
) = NULL
;
538 * mowgli_radix_elem_find(struct irc_radixtree *dtree, const char *key)
540 * Looks up a DTree node by name.
543 * - patricia tree object
544 * - name of node to lookup
547 * - on success, the dtree node requested
553 struct irc_radixtree_leaf
*
554 mowgli_radix_elem_find(struct irc_radixtree
*dict
, const char *key
)
556 char ckey_store
[256];
558 char *ckey_buf
= NULL
;
560 union irc_radixtree_elem
*delem
;
564 s_assert(dict
!= NULL
);
565 s_assert(key
!= NULL
);
567 keylen
= strlen(key
);
569 if (dict
->canonize_cb
== NULL
)
575 if (keylen
>= (int) sizeof(ckey_store
))
577 ckey_buf
= rb_strdup(key
);
578 dict
->canonize_cb(ckey_buf
);
583 rb_strlcpy(ckey_store
, key
, sizeof ckey_store
);
584 dict
->canonize_cb(ckey_store
);
591 while (delem
!= NULL
&& !IS_LEAF(delem
))
593 if (delem
->nibnum
/ 2 < keylen
)
594 val
= NIBBLE_VAL(ckey
, delem
->nibnum
);
598 delem
= delem
->node
.down
[val
];
601 /* Now, if the key is in the tree, delem contains it. */
602 if ((delem
!= NULL
) && strcmp(delem
->leaf
.key
, ckey
))
605 if (ckey_buf
!= NULL
)
612 * irc_radixtree_add(struct irc_radixtree *dtree, const char *key, void *data)
614 * Creates a new DTree node and binds data to it.
617 * - patricia tree object
618 * - name for new DTree node
619 * - data to bind to the new DTree node
623 * - on failure, FALSE
626 * - data is inserted into the DTree.
628 struct irc_radixtree_leaf
*
629 mowgli_radix_elem_add(struct irc_radixtree
*dict
, const char *key
, void *data
)
633 union irc_radixtree_elem
*delem
, *prev
, *newnode
;
635 union irc_radixtree_elem
**place1
;
640 s_assert(dict
!= NULL
);
641 s_assert(key
!= NULL
);
642 s_assert(data
!= NULL
);
644 keylen
= strlen(key
);
645 ckey
= rb_strdup(key
);
650 if (dict
->canonize_cb
!= NULL
)
651 dict
->canonize_cb(ckey
);
654 val
= POINTERS_PER_NODE
+ 2; /* trap value */
657 while (delem
!= NULL
&& !IS_LEAF(delem
))
661 if (delem
->nibnum
/ 2 < keylen
)
662 val
= NIBBLE_VAL(ckey
, delem
->nibnum
);
666 delem
= delem
->node
.down
[val
];
669 /* Now, if the key is in the tree, delem contains it. */
670 if ((delem
!= NULL
) && !strcmp(delem
->leaf
.key
, ckey
))
676 if ((delem
== NULL
) && (prev
!= NULL
))
677 /* Get a leaf to compare with. */
678 delem
= first_leaf(prev
);
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
;
693 return &(*place1
)->leaf
;
696 /* Find the first nibble where they differ. */
697 for (i
= 0; NIBBLE_VAL(ckey
, i
) == NIBBLE_VAL(delem
->leaf
.key
, i
); i
++)
700 /* Find where to insert the new node. */
701 while (prev
!= NULL
&& prev
->nibnum
> i
)
703 val
= prev
->node
.parent_val
;
704 prev
= prev
->node
.parent
;
707 if ((prev
== NULL
) || (prev
->nibnum
< i
))
709 /* Insert new node below prev */
710 newnode
= rb_malloc(sizeof(struct irc_radixtree_node
));
711 s_assert(newnode
!= NULL
);
713 newnode
->node
.parent
= prev
;
714 newnode
->node
.parent_val
= val
;
716 for (j
= 0; j
< POINTERS_PER_NODE
; j
++)
717 newnode
->node
.down
[j
] = NULL
;
721 newnode
->node
.down
[NIBBLE_VAL(delem
->leaf
.key
, i
)] = dict
->root
;
723 if (IS_LEAF(dict
->root
))
725 dict
->root
->leaf
.parent
= newnode
;
726 dict
->root
->leaf
.parent_val
= NIBBLE_VAL(delem
->leaf
.key
, i
);
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
);
735 dict
->root
= newnode
;
739 newnode
->node
.down
[NIBBLE_VAL(delem
->leaf
.key
, i
)] = prev
->node
.down
[val
];
741 if (IS_LEAF(prev
->node
.down
[val
]))
743 prev
->node
.down
[val
]->leaf
.parent
= newnode
;
744 prev
->node
.down
[val
]->leaf
.parent_val
= NIBBLE_VAL(delem
->leaf
.key
, i
);
748 prev
->node
.down
[val
]->node
.parent
= newnode
;
749 prev
->node
.down
[val
]->node
.parent_val
= NIBBLE_VAL(delem
->leaf
.key
, i
);
752 prev
->node
.down
[val
] = newnode
;
757 /* This nibble is already checked. */
758 s_assert(prev
->nibnum
== i
);
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
;
773 return &(*place1
)->leaf
;
777 irc_radixtree_add(struct irc_radixtree
*dict
, const char *key
, void *data
)
779 return (mowgli_radix_elem_add(dict
, key
, data
) != NULL
);
783 * irc_radixtree_delete(struct irc_radixtree *dtree, const char *key)
785 * Deletes data from a patricia tree.
788 * - patricia tree object
789 * - name of DTree node to delete
792 * - on success, the remaining data that needs to be rb_freed
796 * - data is removed from the DTree.
799 * - the returned data needs to be rb_freed/released manually!
802 irc_radixtree_delete(struct irc_radixtree
*dict
, const char *key
)
805 struct irc_radixtree_leaf
*leaf
;
807 leaf
= mowgli_radix_elem_find(dict
, key
);
813 irc_radixtree_elem_delete(dict
, leaf
);
818 irc_radixtree_elem_delete(struct irc_radixtree
*dict
, struct irc_radixtree_leaf
*leaf
)
820 union irc_radixtree_elem
*delem
, *prev
, *next
;
824 s_assert(dict
!= NULL
);
825 s_assert(leaf
!= NULL
);
827 delem
= (union irc_radixtree_elem
*) leaf
;
829 val
= delem
->leaf
.parent_val
;
830 prev
= delem
->leaf
.parent
;
832 rb_free(delem
->leaf
.key
);
837 prev
->node
.down
[val
] = NULL
;
839 /* Leaf is gone, now consider the node it was in. */
844 for (i
= 0; i
< POINTERS_PER_NODE
; i
++)
845 if (delem
->node
.down
[i
] != NULL
)
846 used
= used
== -1 ? i
: -2;
848 s_assert(used
== -2 || used
>= 0);
852 /* Only one pointer in this node, remove it.
853 * Replace the pointer that pointed to it by
854 * the sole pointer in it.
856 next
= delem
->node
.down
[used
];
857 val
= delem
->node
.parent_val
;
858 prev
= delem
->node
.parent
;
861 prev
->node
.down
[val
] = next
;
866 next
->leaf
.parent
= prev
, next
->leaf
.parent_val
= val
;
868 next
->node
.parent
= prev
, next
->node
.parent_val
= val
;
875 /* This was the last leaf. */
881 if (dict
->count
== 0)
883 s_assert(dict
->root
== NULL
);
889 * irc_radixtree_retrieve(struct irc_radixtree *dtree, const char *key)
891 * Retrieves data from a patricia.
894 * - patricia tree object
895 * - name of node to lookup
898 * - on success, the data bound to the DTree node.
905 irc_radixtree_retrieve(struct irc_radixtree
*dtree
, const char *key
)
907 struct irc_radixtree_leaf
*delem
= mowgli_radix_elem_find(dtree
, key
);
916 mowgli_radix_elem_get_key(struct irc_radixtree_leaf
*leaf
)
918 s_assert(leaf
!= NULL
);
924 mowgli_radix_elem_set_data(struct irc_radixtree_leaf
*leaf
, void *data
)
926 s_assert(leaf
!= NULL
);
932 mowgli_radix_elem_get_data(struct irc_radixtree_leaf
*leaf
)
934 s_assert(leaf
!= NULL
);
940 * irc_radixtree_size(struct irc_radixtree *dict)
942 * Returns the size of a patricia.
945 * - patricia tree object
954 irc_radixtree_size(struct irc_radixtree
*dict
)
956 s_assert(dict
!= NULL
);
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... */
964 stats_recurse(union irc_radixtree_elem
*delem
, int depth
, int *pmaxdepth
)
968 union irc_radixtree_elem
*next
;
970 if (depth
> *pmaxdepth
)
976 s_assert(delem
->leaf
.parent
== NULL
);
979 s_assert(delem
->node
.parent
== NULL
);
985 for (val
= 0; val
< POINTERS_PER_NODE
; val
++)
987 next
= delem
->node
.down
[val
];
992 result
+= stats_recurse(next
, depth
+ 1, pmaxdepth
);
996 s_assert(next
->leaf
.parent
== delem
);
997 s_assert(next
->leaf
.parent_val
== val
);
1001 s_assert(next
->node
.parent
== delem
);
1002 s_assert(next
->node
.parent_val
== val
);
1003 s_assert(next
->node
.nibnum
> delem
->node
.nibnum
);
1011 * irc_radixtree_stats(struct irc_radixtree *dict, void (*cb)(const char *line, void *privdata), void *privdata)
1013 * Returns the size of a patricia.
1016 * - patricia tree object
1018 * - data for callback
1024 * - callback called with stats text
1027 irc_radixtree_stats(struct irc_radixtree
*dict
, void (*cb
)(const char *line
, void *privdata
), void *privdata
)
1032 s_assert(dict
!= NULL
);
1035 if (dict
->count
> 0)
1037 sum
= stats_recurse(dict
->root
, 0, &maxdepth
);
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
);
1042 snprintf(str
, sizeof str
, "%s: Objects: 0, Depth sum: 0, Avg depth: 0, Max depth: 0.", dict
->id
);
1050 irc_radixtree_stats_walk(void (*cb
)(const char *line
, void *privdata
), void *privdata
)
1054 RB_DLINK_FOREACH(ptr
, radixtree_list
.head
)
1056 irc_radixtree_stats(ptr
->data
, cb
, privdata
);