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.
38 #include "irc_radixtree.h"
40 rb_dlink_list radixtree_list
= {NULL
, NULL
, 0};
45 * A radix trie that avoids one-way branching and redundant nodes.
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.
51 * The nibnum values are strictly increasing while going down the tree.
56 union irc_radixtree_elem
;
60 void (*canonize_cb
)(char *key
);
61 union irc_radixtree_elem
*root
;
69 #define POINTERS_PER_NODE 16
70 #define NIBBLE_VAL(key, nibnum) (((key)[(nibnum) / 2] >> ((nibnum) & 1 ? 0 : 4)) & 0xF)
72 struct irc_radixtree_node
74 /* nibble to test (nibble NUM%2 of byte NUM/2) */
77 /* branches of the tree */
78 union irc_radixtree_elem
*down
[POINTERS_PER_NODE
];
79 union irc_radixtree_elem
*parent
;
84 struct irc_radixtree_leaf
86 /* -1 to indicate this is a leaf, not a node */
89 /* data associated with the key */
92 /* key (canonized copy) */
94 union irc_radixtree_elem
*parent
;
99 union irc_radixtree_elem
102 struct irc_radixtree_node node
;
104 struct irc_radixtree_leaf leaf
;
107 #define IS_LEAF(elem) ((elem)->nibnum == -1)
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])
116 * Find the smallest leaf hanging off a subtree.
119 * - element (may be leaf or node) heading subtree
122 * - lowest leaf in subtree
127 static union irc_radixtree_elem
*
128 first_leaf(union irc_radixtree_elem
*delem
)
132 while (!IS_LEAF(delem
))
134 for (val
= 0; val
< POINTERS_PER_NODE
; val
++)
135 if (delem
->node
.down
[val
] != NULL
)
137 delem
= delem
->node
.down
[val
];
146 * irc_radixtree_create_named(const char *name,
147 * void (*canonize_cb)(char *key))
149 * Dictionary object factory.
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)
158 * - on success, a new patricia object.
161 * - if services runs out of memory and cannot allocate the object,
162 * the program will abort.
164 struct irc_radixtree
*
165 irc_radixtree_create(const char *name
, void (*canonize_cb
)(char *key
))
167 struct irc_radixtree
*dtree
= (struct irc_radixtree
*) rb_malloc(sizeof(struct irc_radixtree
));
169 dtree
->canonize_cb
= canonize_cb
;
170 dtree
->id
= rb_strdup(name
);
173 rb_dlinkAdd(dtree
, &dtree
->node
, &radixtree_list
);
179 * irc_radixtree_destroy(struct irc_radixtree *dtree,
180 * void (*destroy_cb)(const char *key, void *data, void *privdata),
183 * Recursively destroys all nodes in a patricia tree.
186 * - patricia tree object
187 * - optional iteration callback
188 * - optional opaque/private data to pass to callback
194 * - on success, a dtree and optionally it's children are destroyed.
197 * - if this is called without a callback, the objects bound to the
198 * DTree will not be destroyed.
201 irc_radixtree_destroy(struct irc_radixtree
*dtree
, void (*destroy_cb
)(const char *key
, void *data
, void *privdata
), void *privdata
)
203 struct irc_radixtree_iteration_state state
;
204 union irc_radixtree_elem
*delem
;
208 s_assert(dtree
!= NULL
);
210 IRC_RADIXTREE_FOREACH(entry
, &state
, dtree
)
212 delem
= STATE_CUR(&state
);
214 if (destroy_cb
!= NULL
)
215 (*destroy_cb
)(delem
->leaf
.key
, delem
->leaf
.data
,
218 irc_radixtree_delete(dtree
, delem
->leaf
.key
);
221 rb_dlinkDelete(&dtree
->node
, &radixtree_list
);
227 * irc_radixtree_foreach(struct irc_radixtree *dtree,
228 * int (*foreach_cb)(const char *key, void *data, void *privdata),
231 * Iterates over all entries in a DTree.
234 * - patricia tree object
235 * - optional iteration callback
236 * - optional opaque/private data to pass to callback
242 * - on success, a dtree is iterated
245 irc_radixtree_foreach(struct irc_radixtree
*dtree
, int (*foreach_cb
)(const char *key
, void *data
, void *privdata
), void *privdata
)
247 union irc_radixtree_elem
*delem
, *next
;
251 s_assert(dtree
!= NULL
);
258 /* Only one element in the tree */
261 if (foreach_cb
!= NULL
)
262 (*foreach_cb
)(delem
->leaf
.key
, delem
->leaf
.data
, privdata
);
272 next
= delem
->node
.down
[val
++];
273 while (next
== NULL
&& val
< POINTERS_PER_NODE
);
279 if (foreach_cb
!= NULL
)
280 (*foreach_cb
)(next
->leaf
.key
, next
->leaf
.data
, privdata
);
289 while (val
>= POINTERS_PER_NODE
)
291 val
= delem
->node
.parent_val
;
292 delem
= delem
->node
.parent
;
299 } while (delem
!= NULL
);
303 * irc_radixtree_search(struct irc_radixtree *dtree,
304 * void *(*foreach_cb)(const char *key, void *data, void *privdata),
307 * Searches all entries in a DTree using a custom callback.
310 * - patricia tree object
311 * - optional iteration callback
312 * - optional opaque/private data to pass to callback
315 * - on success, the requested object
316 * - on failure, NULL.
319 * - a dtree is iterated until the requested conditions are met
322 irc_radixtree_search(struct irc_radixtree
*dtree
, void *(*foreach_cb
)(const char *key
, void *data
, void *privdata
), void *privdata
)
324 union irc_radixtree_elem
*delem
, *next
;
329 s_assert(dtree
!= NULL
);
336 /* Only one element in the tree */
339 if (foreach_cb
!= NULL
)
340 return (*foreach_cb
)(delem
->leaf
.key
, delem
->leaf
.data
, privdata
);
350 next
= delem
->node
.down
[val
++];
351 while (next
== NULL
&& val
< POINTERS_PER_NODE
);
357 if (foreach_cb
!= NULL
)
358 ret
= (*foreach_cb
)(next
->leaf
.key
, next
->leaf
.data
, privdata
);
370 while (val
>= POINTERS_PER_NODE
)
372 val
= delem
->node
.parent_val
;
373 delem
= delem
->node
.parent
;
386 * irc_radixtree_foreach_start(struct irc_radixtree *dtree,
387 * struct irc_radixtree_iteration_state *state);
389 * Initializes a static DTree iterator.
392 * - patricia tree object
393 * - static DTree iterator
399 * - the static iterator, &state, is initialized.
402 irc_radixtree_foreach_start(struct irc_radixtree
*dtree
, struct irc_radixtree_iteration_state
*state
)
407 s_assert(state
!= NULL
);
409 if (dtree
->root
!= NULL
)
410 STATE_NEXT(state
) = first_leaf(dtree
->root
);
412 STATE_NEXT(state
) = NULL
;
414 STATE_CUR(state
) = STATE_NEXT(state
);
416 if (STATE_NEXT(state
) == NULL
)
419 /* make STATE_CUR point to first item and STATE_NEXT point to
421 irc_radixtree_foreach_next(dtree
, state
);
425 * irc_radixtree_foreach_cur(struct irc_radixtree *dtree,
426 * struct irc_radixtree_iteration_state *state);
428 * Returns the data from the current node being iterated by the
432 * - patricia tree object
433 * - static DTree iterator
436 * - reference to data in the current dtree node being iterated
442 irc_radixtree_foreach_cur(struct irc_radixtree
*dtree
, struct irc_radixtree_iteration_state
*state
)
447 s_assert(state
!= NULL
);
449 return STATE_CUR(state
) != NULL
?
450 ((struct irc_radixtree_leaf
*) STATE_CUR(state
))->data
: NULL
;
454 * irc_radixtree_foreach_next(struct irc_radixtree *dtree,
455 * struct irc_radixtree_iteration_state *state);
457 * Advances a static DTree iterator.
460 * - patricia tree object
461 * - static DTree iterator
467 * - the static iterator, &state, is advanced to a new DTree node.
470 irc_radixtree_foreach_next(struct irc_radixtree
*dtree
, struct irc_radixtree_iteration_state
*state
)
472 struct irc_radixtree_leaf
*leaf
;
474 union irc_radixtree_elem
*delem
, *next
;
481 s_assert(state
!= NULL
);
483 if (STATE_CUR(state
) == NULL
)
486 STATE_CUR(state
) = STATE_NEXT(state
);
488 if (STATE_NEXT(state
) == NULL
)
491 leaf
= STATE_NEXT(state
);
492 delem
= leaf
->parent
;
493 val
= leaf
->parent_val
;
495 while (delem
!= NULL
)
498 next
= delem
->node
.down
[val
++];
499 while (next
== NULL
&& val
< POINTERS_PER_NODE
);
505 /* We will find the original leaf first. */
506 if (&next
->leaf
!= leaf
)
508 if (strcmp(next
->leaf
.key
, leaf
->key
) < 0)
510 STATE_NEXT(state
) = NULL
;
514 STATE_NEXT(state
) = next
;
525 while (val
>= POINTERS_PER_NODE
)
527 val
= delem
->node
.parent_val
;
528 delem
= delem
->node
.parent
;
537 STATE_NEXT(state
) = NULL
;
541 * irc_radixtree_elem_find(struct irc_radixtree *dtree, const char *key)
543 * Looks up a DTree node by name.
546 * - patricia tree object
547 * - name of node to lookup
548 * - whether to do a direct or fuzzy match
551 * - on success, the dtree node requested
557 struct irc_radixtree_leaf
*
558 irc_radixtree_elem_find(struct irc_radixtree
*dict
, const char *key
, int fuzzy
)
560 char ckey_store
[256];
562 char *ckey_buf
= NULL
;
564 union irc_radixtree_elem
*delem
;
568 s_assert(dict
!= NULL
);
569 s_assert(key
!= NULL
);
571 keylen
= strlen(key
);
573 if (dict
->canonize_cb
== NULL
)
579 if (keylen
>= (int) sizeof(ckey_store
))
581 ckey_buf
= rb_strdup(key
);
582 dict
->canonize_cb(ckey_buf
);
587 rb_strlcpy(ckey_store
, key
, sizeof ckey_store
);
588 dict
->canonize_cb(ckey_store
);
595 while (delem
!= NULL
&& !IS_LEAF(delem
))
597 if (delem
->nibnum
/ 2 < keylen
)
598 val
= NIBBLE_VAL(ckey
, delem
->nibnum
);
602 delem
= delem
->node
.down
[val
];
605 /* Now, if the key is in the tree, delem contains it. */
606 if ((delem
!= NULL
) && !fuzzy
&& strcmp(delem
->leaf
.key
, ckey
))
609 if (ckey_buf
!= NULL
)
616 * irc_radixtree_foreach_start_from(struct irc_radixtree *dtree, struct irc_radixtree_iteration_state *state, const char *key)
618 * Starts iteration from a specified key, by wrapping irc_radixtree_elem_find().
621 * - patricia tree object
623 * - key to start from
629 * - the iterator's state is initialized at a specific point
632 irc_radixtree_foreach_start_from(struct irc_radixtree
*dtree
, struct irc_radixtree_iteration_state
*state
, const char *key
)
634 s_assert(dtree
!= NULL
);
635 s_assert(state
!= NULL
);
639 STATE_CUR(state
) = NULL
;
640 STATE_NEXT(state
) = irc_radixtree_elem_find(dtree
, key
, 1);
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
);
647 irc_radixtree_foreach_start(dtree
, state
);
651 * irc_radixtree_add(struct irc_radixtree *dtree, const char *key, void *data)
653 * Creates a new DTree node and binds data to it.
656 * - patricia tree object
657 * - name for new DTree node
658 * - data to bind to the new DTree node
662 * - on failure, FALSE
665 * - data is inserted into the DTree.
667 struct irc_radixtree_leaf
*
668 irc_radixtree_elem_add(struct irc_radixtree
*dict
, const char *key
, void *data
)
672 union irc_radixtree_elem
*delem
, *prev
, *newnode
;
674 union irc_radixtree_elem
**place1
;
679 s_assert(dict
!= NULL
);
680 s_assert(key
!= NULL
);
681 s_assert(data
!= NULL
);
683 keylen
= strlen(key
);
684 ckey
= rb_strdup(key
);
689 if (dict
->canonize_cb
!= NULL
)
690 dict
->canonize_cb(ckey
);
693 val
= POINTERS_PER_NODE
+ 2; /* trap value */
696 while (delem
!= NULL
&& !IS_LEAF(delem
))
700 if (delem
->nibnum
/ 2 < keylen
)
701 val
= NIBBLE_VAL(ckey
, delem
->nibnum
);
705 delem
= delem
->node
.down
[val
];
708 /* Now, if the key is in the tree, delem contains it. */
709 if ((delem
!= NULL
) && !strcmp(delem
->leaf
.key
, ckey
))
715 if ((delem
== NULL
) && (prev
!= NULL
))
716 /* Get a leaf to compare with. */
717 delem
= first_leaf(prev
);
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
;
732 return &(*place1
)->leaf
;
735 /* Find the first nibble where they differ. */
736 for (i
= 0; NIBBLE_VAL(ckey
, i
) == NIBBLE_VAL(delem
->leaf
.key
, i
); i
++)
739 /* Find where to insert the new node. */
740 while (prev
!= NULL
&& prev
->nibnum
> i
)
742 val
= prev
->node
.parent_val
;
743 prev
= prev
->node
.parent
;
746 if ((prev
== NULL
) || (prev
->nibnum
< i
))
748 /* Insert new node below prev */
749 newnode
= rb_malloc(sizeof(struct irc_radixtree_node
));
750 s_assert(newnode
!= NULL
);
752 newnode
->node
.parent
= prev
;
753 newnode
->node
.parent_val
= val
;
755 for (j
= 0; j
< POINTERS_PER_NODE
; j
++)
756 newnode
->node
.down
[j
] = NULL
;
760 newnode
->node
.down
[NIBBLE_VAL(delem
->leaf
.key
, i
)] = dict
->root
;
762 if (IS_LEAF(dict
->root
))
764 dict
->root
->leaf
.parent
= newnode
;
765 dict
->root
->leaf
.parent_val
= NIBBLE_VAL(delem
->leaf
.key
, i
);
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
);
774 dict
->root
= newnode
;
778 newnode
->node
.down
[NIBBLE_VAL(delem
->leaf
.key
, i
)] = prev
->node
.down
[val
];
780 if (IS_LEAF(prev
->node
.down
[val
]))
782 prev
->node
.down
[val
]->leaf
.parent
= newnode
;
783 prev
->node
.down
[val
]->leaf
.parent_val
= NIBBLE_VAL(delem
->leaf
.key
, i
);
787 prev
->node
.down
[val
]->node
.parent
= newnode
;
788 prev
->node
.down
[val
]->node
.parent_val
= NIBBLE_VAL(delem
->leaf
.key
, i
);
791 prev
->node
.down
[val
] = newnode
;
796 /* This nibble is already checked. */
797 s_assert(prev
->nibnum
== i
);
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
;
812 return &(*place1
)->leaf
;
816 irc_radixtree_add(struct irc_radixtree
*dict
, const char *key
, void *data
)
818 return (irc_radixtree_elem_add(dict
, key
, data
) != NULL
);
822 * irc_radixtree_delete(struct irc_radixtree *dtree, const char *key)
824 * Deletes data from a patricia tree.
827 * - patricia tree object
828 * - name of DTree node to delete
831 * - on success, the remaining data that needs to be rb_freed
835 * - data is removed from the DTree.
838 * - the returned data needs to be rb_freed/released manually!
841 irc_radixtree_delete(struct irc_radixtree
*dict
, const char *key
)
844 struct irc_radixtree_leaf
*leaf
;
846 leaf
= irc_radixtree_elem_find(dict
, key
, 0);
852 irc_radixtree_elem_delete(dict
, leaf
);
857 irc_radixtree_elem_delete(struct irc_radixtree
*dict
, struct irc_radixtree_leaf
*leaf
)
859 union irc_radixtree_elem
*delem
, *prev
, *next
;
863 s_assert(dict
!= NULL
);
864 s_assert(leaf
!= NULL
);
866 delem
= (union irc_radixtree_elem
*) leaf
;
868 val
= delem
->leaf
.parent_val
;
869 prev
= delem
->leaf
.parent
;
871 rb_free(delem
->leaf
.key
);
876 prev
->node
.down
[val
] = NULL
;
878 /* Leaf is gone, now consider the node it was in. */
883 for (i
= 0; i
< POINTERS_PER_NODE
; i
++)
884 if (delem
->node
.down
[i
] != NULL
)
885 used
= used
== -1 ? i
: -2;
887 s_assert(used
== -2 || used
>= 0);
891 /* Only one pointer in this node, remove it.
892 * Replace the pointer that pointed to it by
893 * the sole pointer in it.
895 next
= delem
->node
.down
[used
];
896 val
= delem
->node
.parent_val
;
897 prev
= delem
->node
.parent
;
900 prev
->node
.down
[val
] = next
;
905 next
->leaf
.parent
= prev
, next
->leaf
.parent_val
= val
;
907 next
->node
.parent
= prev
, next
->node
.parent_val
= val
;
914 /* This was the last leaf. */
920 if (dict
->count
== 0)
922 s_assert(dict
->root
== NULL
);
928 * irc_radixtree_retrieve(struct irc_radixtree *dtree, const char *key)
930 * Retrieves data from a patricia.
933 * - patricia tree object
934 * - name of node to lookup
937 * - on success, the data bound to the DTree node.
944 irc_radixtree_retrieve(struct irc_radixtree
*dtree
, const char *key
)
946 struct irc_radixtree_leaf
*delem
= irc_radixtree_elem_find(dtree
, key
, 0);
955 irc_radixtree_elem_get_key(struct irc_radixtree_leaf
*leaf
)
957 s_assert(leaf
!= NULL
);
963 irc_radixtree_elem_set_data(struct irc_radixtree_leaf
*leaf
, void *data
)
965 s_assert(leaf
!= NULL
);
971 irc_radixtree_elem_get_data(struct irc_radixtree_leaf
*leaf
)
973 s_assert(leaf
!= NULL
);
979 * irc_radixtree_size(struct irc_radixtree *dict)
981 * Returns the size of a patricia.
984 * - patricia tree object
993 irc_radixtree_size(struct irc_radixtree
*dict
)
995 s_assert(dict
!= NULL
);
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... */
1003 stats_recurse(union irc_radixtree_elem
*delem
, int depth
, int *pmaxdepth
)
1007 union irc_radixtree_elem
*next
;
1009 if (depth
> *pmaxdepth
)
1015 s_assert(delem
->leaf
.parent
== NULL
);
1018 s_assert(delem
->node
.parent
== NULL
);
1024 for (val
= 0; val
< POINTERS_PER_NODE
; val
++)
1026 next
= delem
->node
.down
[val
];
1031 result
+= stats_recurse(next
, depth
+ 1, pmaxdepth
);
1035 s_assert(next
->leaf
.parent
== delem
);
1036 s_assert(next
->leaf
.parent_val
== val
);
1040 s_assert(next
->node
.parent
== delem
);
1041 s_assert(next
->node
.parent_val
== val
);
1042 s_assert(next
->node
.nibnum
> delem
->node
.nibnum
);
1050 * irc_radixtree_stats(struct irc_radixtree *dict, void (*cb)(const char *line, void *privdata), void *privdata)
1052 * Returns the size of a patricia.
1055 * - patricia tree object
1057 * - data for callback
1063 * - callback called with stats text
1066 irc_radixtree_stats(struct irc_radixtree
*dict
, void (*cb
)(const char *line
, void *privdata
), void *privdata
)
1071 s_assert(dict
!= NULL
);
1074 if (dict
->count
> 0)
1076 sum
= stats_recurse(dict
->root
, 0, &maxdepth
);
1077 snprintf(str
, sizeof str
, "%-30s %-15s %-10d %-10d %-10d %-10d", dict
->id
, "RADIX", dict
->count
, sum
, sum
/ dict
->count
, maxdepth
);
1081 snprintf(str
, sizeof str
, "%-30s %-15s %-10s %-10s %-10s %-10s", dict
->id
, "RADIX", "0", "0", "0", "0");
1089 irc_radixtree_stats_walk(void (*cb
)(const char *line
, void *privdata
), void *privdata
)
1093 RB_DLINK_FOREACH(ptr
, radixtree_list
.head
)
1095 irc_radixtree_stats(ptr
->data
, cb
, privdata
);
1099 void irc_radixtree_irccasecanon(char *str
)
1103 *str
= ToUpper(*str
);
1109 void irc_radixtree_strcasecanon(char *str
)
1113 *str
= toupper((unsigned char)*str
);