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"
42 * A radix trie that avoids one-way branching and redundant nodes.
44 * To find a node, the tree is traversed starting from the root. The
45 * nibnum in each node indicates which nibble of the key needs to be
46 * tested, and the appropriate branch is taken.
48 * The nibnum values are strictly increasing while going down the tree.
53 union irc_radixtree_elem
;
57 void (*canonize_cb
)(char *key
);
58 union irc_radixtree_elem
*root
;
64 #define POINTERS_PER_NODE 16
65 #define NIBBLE_VAL(key, nibnum) (((key)[(nibnum) / 2] >> ((nibnum) & 1 ? 0 : 4)) & 0xF)
67 struct irc_radixtree_node
69 /* nibble to test (nibble NUM%2 of byte NUM/2) */
72 /* branches of the tree */
73 union irc_radixtree_elem
*down
[POINTERS_PER_NODE
];
74 union irc_radixtree_elem
*parent
;
79 struct irc_radixtree_leaf
81 /* -1 to indicate this is a leaf, not a node */
84 /* data associated with the key */
87 /* key (canonized copy) */
89 union irc_radixtree_elem
*parent
;
94 union irc_radixtree_elem
97 struct irc_radixtree_node node
;
99 struct irc_radixtree_leaf leaf
;
102 #define IS_LEAF(elem) ((elem)->nibnum == -1)
104 /* Preserve compatibility with the old mowgli_patricia.h */
105 #define STATE_CUR(state) ((state)->pspare[0])
106 #define STATE_NEXT(state) ((state)->pspare[1])
111 * Find the smallest leaf hanging off a subtree.
114 * - element (may be leaf or node) heading subtree
117 * - lowest leaf in subtree
122 static union irc_radixtree_elem
*
123 first_leaf(union irc_radixtree_elem
*delem
)
127 while (!IS_LEAF(delem
))
129 for (val
= 0; val
< POINTERS_PER_NODE
; val
++)
130 if (delem
->node
.down
[val
] != NULL
)
132 delem
= delem
->node
.down
[val
];
141 * irc_radixtree_create(void (*canonize_cb)(char *key))
143 * Dictionary object factory.
146 * - function to use for canonizing keys (for example, use
147 * a function that makes the string upper case to create
148 * a patricia with case-insensitive matching)
151 * - on success, a new patricia object.
154 * - if services runs out of memory and cannot allocate the object,
155 * the program will abort.
157 struct irc_radixtree
*
158 irc_radixtree_create(void (*canonize_cb
)(char *key
))
160 struct irc_radixtree
*dtree
= (struct irc_radixtree
*) rb_malloc(sizeof(struct irc_radixtree
));
162 dtree
->canonize_cb
= canonize_cb
;
169 * irc_radixtree_create_named(const char *name,
170 * void (*canonize_cb)(char *key))
172 * Dictionary object factory.
176 * - function to use for canonizing keys (for example, use
177 * a function that makes the string upper case to create
178 * a patricia with case-insensitive matching)
181 * - on success, a new patricia object.
184 * - if services runs out of memory and cannot allocate the object,
185 * the program will abort.
187 struct irc_radixtree
*
188 irc_radixtree_create_named(const char *name
, void (*canonize_cb
)(char *key
))
190 struct irc_radixtree
*dtree
= (struct irc_radixtree
*) rb_malloc(sizeof(struct irc_radixtree
));
192 dtree
->canonize_cb
= canonize_cb
;
193 dtree
->id
= rb_strdup(name
);
200 * irc_radixtree_destroy(struct irc_radixtree *dtree,
201 * void (*destroy_cb)(const char *key, void *data, void *privdata),
204 * Recursively destroys all nodes in a patricia tree.
207 * - patricia tree object
208 * - optional iteration callback
209 * - optional opaque/private data to pass to callback
215 * - on success, a dtree and optionally it's children are destroyed.
218 * - if this is called without a callback, the objects bound to the
219 * DTree will not be destroyed.
222 irc_radixtree_destroy(struct irc_radixtree
*dtree
, void (*destroy_cb
)(const char *key
, void *data
, void *privdata
), void *privdata
)
224 struct irc_radixtree_iteration_state state
;
225 union irc_radixtree_elem
*delem
;
229 s_assert(dtree
!= NULL
);
231 IRC_RADIXTREE_FOREACH(entry
, &state
, dtree
)
233 delem
= STATE_CUR(&state
);
235 if (destroy_cb
!= NULL
)
236 (*destroy_cb
)(delem
->leaf
.key
, delem
->leaf
.data
,
239 irc_radixtree_delete(dtree
, delem
->leaf
.key
);
246 * irc_radixtree_foreach(struct irc_radixtree *dtree,
247 * int (*foreach_cb)(const char *key, void *data, void *privdata),
250 * Iterates over all entries in a DTree.
253 * - patricia tree object
254 * - optional iteration callback
255 * - optional opaque/private data to pass to callback
261 * - on success, a dtree is iterated
264 irc_radixtree_foreach(struct irc_radixtree
*dtree
, int (*foreach_cb
)(const char *key
, void *data
, void *privdata
), void *privdata
)
266 union irc_radixtree_elem
*delem
, *next
;
270 s_assert(dtree
!= NULL
);
277 /* Only one element in the tree */
280 if (foreach_cb
!= NULL
)
281 (*foreach_cb
)(delem
->leaf
.key
, delem
->leaf
.data
, privdata
);
291 next
= delem
->node
.down
[val
++];
292 while (next
== NULL
&& val
< POINTERS_PER_NODE
);
298 if (foreach_cb
!= NULL
)
299 (*foreach_cb
)(next
->leaf
.key
, next
->leaf
.data
, privdata
);
308 while (val
>= POINTERS_PER_NODE
)
310 val
= delem
->node
.parent_val
;
311 delem
= delem
->node
.parent
;
318 } while (delem
!= NULL
);
322 * irc_radixtree_search(struct irc_radixtree *dtree,
323 * void *(*foreach_cb)(const char *key, void *data, void *privdata),
326 * Searches all entries in a DTree using a custom callback.
329 * - patricia tree object
330 * - optional iteration callback
331 * - optional opaque/private data to pass to callback
334 * - on success, the requested object
335 * - on failure, NULL.
338 * - a dtree is iterated until the requested conditions are met
341 irc_radixtree_search(struct irc_radixtree
*dtree
, void *(*foreach_cb
)(const char *key
, void *data
, void *privdata
), void *privdata
)
343 union irc_radixtree_elem
*delem
, *next
;
348 s_assert(dtree
!= NULL
);
355 /* Only one element in the tree */
358 if (foreach_cb
!= NULL
)
359 return (*foreach_cb
)(delem
->leaf
.key
, delem
->leaf
.data
, privdata
);
369 next
= delem
->node
.down
[val
++];
370 while (next
== NULL
&& val
< POINTERS_PER_NODE
);
376 if (foreach_cb
!= NULL
)
377 ret
= (*foreach_cb
)(next
->leaf
.key
, next
->leaf
.data
, privdata
);
389 while (val
>= POINTERS_PER_NODE
)
391 val
= delem
->node
.parent_val
;
392 delem
= delem
->node
.parent
;
405 * irc_radixtree_foreach_start(struct irc_radixtree *dtree,
406 * struct irc_radixtree_iteration_state *state);
408 * Initializes a static DTree iterator.
411 * - patricia tree object
412 * - static DTree iterator
418 * - the static iterator, &state, is initialized.
421 irc_radixtree_foreach_start(struct irc_radixtree
*dtree
, struct irc_radixtree_iteration_state
*state
)
426 s_assert(state
!= NULL
);
428 if (dtree
->root
!= NULL
)
429 STATE_NEXT(state
) = first_leaf(dtree
->root
);
431 STATE_NEXT(state
) = NULL
;
433 STATE_CUR(state
) = STATE_NEXT(state
);
435 if (STATE_NEXT(state
) == NULL
)
438 /* make STATE_CUR point to first item and STATE_NEXT point to
440 irc_radixtree_foreach_next(dtree
, state
);
444 * irc_radixtree_foreach_cur(struct irc_radixtree *dtree,
445 * struct irc_radixtree_iteration_state *state);
447 * Returns the data from the current node being iterated by the
451 * - patricia tree object
452 * - static DTree iterator
455 * - reference to data in the current dtree node being iterated
461 irc_radixtree_foreach_cur(struct irc_radixtree
*dtree
, struct irc_radixtree_iteration_state
*state
)
466 s_assert(state
!= NULL
);
468 return STATE_CUR(state
) != NULL
?
469 ((struct irc_radixtree_leaf
*) STATE_CUR(state
))->data
: NULL
;
473 * irc_radixtree_foreach_next(struct irc_radixtree *dtree,
474 * struct irc_radixtree_iteration_state *state);
476 * Advances a static DTree iterator.
479 * - patricia tree object
480 * - static DTree iterator
486 * - the static iterator, &state, is advanced to a new DTree node.
489 irc_radixtree_foreach_next(struct irc_radixtree
*dtree
, struct irc_radixtree_iteration_state
*state
)
491 struct irc_radixtree_leaf
*leaf
;
493 union irc_radixtree_elem
*delem
, *next
;
500 s_assert(state
!= NULL
);
502 if (STATE_CUR(state
) == NULL
)
505 STATE_CUR(state
) = STATE_NEXT(state
);
507 if (STATE_NEXT(state
) == NULL
)
510 leaf
= STATE_NEXT(state
);
511 delem
= leaf
->parent
;
512 val
= leaf
->parent_val
;
514 while (delem
!= NULL
)
517 next
= delem
->node
.down
[val
++];
518 while (next
== NULL
&& val
< POINTERS_PER_NODE
);
524 /* We will find the original leaf first. */
525 if (&next
->leaf
!= leaf
)
527 if (strcmp(next
->leaf
.key
, leaf
->key
) < 0)
529 STATE_NEXT(state
) = NULL
;
533 STATE_NEXT(state
) = next
;
544 while (val
>= POINTERS_PER_NODE
)
546 val
= delem
->node
.parent_val
;
547 delem
= delem
->node
.parent
;
556 STATE_NEXT(state
) = NULL
;
560 * mowgli_radix_elem_find(struct irc_radixtree *dtree, const char *key)
562 * Looks up a DTree node by name.
565 * - patricia tree object
566 * - name of node to lookup
569 * - on success, the dtree node requested
575 struct irc_radixtree_leaf
*
576 mowgli_radix_elem_find(struct irc_radixtree
*dict
, const char *key
)
578 char ckey_store
[256];
580 char *ckey_buf
= NULL
;
582 union irc_radixtree_elem
*delem
;
586 s_assert(dict
!= NULL
);
587 s_assert(key
!= NULL
);
589 keylen
= strlen(key
);
591 if (dict
->canonize_cb
== NULL
)
597 if (keylen
>= (int) sizeof(ckey_store
))
599 ckey_buf
= rb_strdup(key
);
600 dict
->canonize_cb(ckey_buf
);
605 rb_strlcpy(ckey_store
, key
, sizeof ckey_store
);
606 dict
->canonize_cb(ckey_store
);
613 while (delem
!= NULL
&& !IS_LEAF(delem
))
615 if (delem
->nibnum
/ 2 < keylen
)
616 val
= NIBBLE_VAL(ckey
, delem
->nibnum
);
620 delem
= delem
->node
.down
[val
];
623 /* Now, if the key is in the tree, delem contains it. */
624 if ((delem
!= NULL
) && strcmp(delem
->leaf
.key
, ckey
))
627 if (ckey_buf
!= NULL
)
634 * irc_radixtree_add(struct irc_radixtree *dtree, const char *key, void *data)
636 * Creates a new DTree node and binds data to it.
639 * - patricia tree object
640 * - name for new DTree node
641 * - data to bind to the new DTree node
645 * - on failure, FALSE
648 * - data is inserted into the DTree.
650 struct irc_radixtree_leaf
*
651 mowgli_radix_elem_add(struct irc_radixtree
*dict
, const char *key
, void *data
)
655 union irc_radixtree_elem
*delem
, *prev
, *newnode
;
657 union irc_radixtree_elem
**place1
;
662 s_assert(dict
!= NULL
);
663 s_assert(key
!= NULL
);
664 s_assert(data
!= NULL
);
666 keylen
= strlen(key
);
667 ckey
= rb_strdup(key
);
672 if (dict
->canonize_cb
!= NULL
)
673 dict
->canonize_cb(ckey
);
676 val
= POINTERS_PER_NODE
+ 2; /* trap value */
679 while (delem
!= NULL
&& !IS_LEAF(delem
))
683 if (delem
->nibnum
/ 2 < keylen
)
684 val
= NIBBLE_VAL(ckey
, delem
->nibnum
);
688 delem
= delem
->node
.down
[val
];
691 /* Now, if the key is in the tree, delem contains it. */
692 if ((delem
!= NULL
) && !strcmp(delem
->leaf
.key
, ckey
))
698 if ((delem
== NULL
) && (prev
!= NULL
))
699 /* Get a leaf to compare with. */
700 delem
= first_leaf(prev
);
704 s_assert(prev
== NULL
);
705 s_assert(dict
->count
== 0);
706 place1
= &dict
->root
;
707 *place1
= rb_malloc(sizeof(struct irc_radixtree_leaf
));
708 s_assert(*place1
!= NULL
);
709 (*place1
)->nibnum
= -1;
710 (*place1
)->leaf
.data
= data
;
711 (*place1
)->leaf
.key
= ckey
;
712 (*place1
)->leaf
.parent
= prev
;
713 (*place1
)->leaf
.parent_val
= val
;
715 return &(*place1
)->leaf
;
718 /* Find the first nibble where they differ. */
719 for (i
= 0; NIBBLE_VAL(ckey
, i
) == NIBBLE_VAL(delem
->leaf
.key
, i
); i
++)
722 /* Find where to insert the new node. */
723 while (prev
!= NULL
&& prev
->nibnum
> i
)
725 val
= prev
->node
.parent_val
;
726 prev
= prev
->node
.parent
;
729 if ((prev
== NULL
) || (prev
->nibnum
< i
))
731 /* Insert new node below prev */
732 newnode
= rb_malloc(sizeof(struct irc_radixtree_node
));
733 s_assert(newnode
!= NULL
);
735 newnode
->node
.parent
= prev
;
736 newnode
->node
.parent_val
= val
;
738 for (j
= 0; j
< POINTERS_PER_NODE
; j
++)
739 newnode
->node
.down
[j
] = NULL
;
743 newnode
->node
.down
[NIBBLE_VAL(delem
->leaf
.key
, i
)] = dict
->root
;
745 if (IS_LEAF(dict
->root
))
747 dict
->root
->leaf
.parent
= newnode
;
748 dict
->root
->leaf
.parent_val
= NIBBLE_VAL(delem
->leaf
.key
, i
);
752 s_assert(dict
->root
->nibnum
> i
);
753 dict
->root
->node
.parent
= newnode
;
754 dict
->root
->node
.parent_val
= NIBBLE_VAL(delem
->leaf
.key
, i
);
757 dict
->root
= newnode
;
761 newnode
->node
.down
[NIBBLE_VAL(delem
->leaf
.key
, i
)] = prev
->node
.down
[val
];
763 if (IS_LEAF(prev
->node
.down
[val
]))
765 prev
->node
.down
[val
]->leaf
.parent
= newnode
;
766 prev
->node
.down
[val
]->leaf
.parent_val
= NIBBLE_VAL(delem
->leaf
.key
, i
);
770 prev
->node
.down
[val
]->node
.parent
= newnode
;
771 prev
->node
.down
[val
]->node
.parent_val
= NIBBLE_VAL(delem
->leaf
.key
, i
);
774 prev
->node
.down
[val
] = newnode
;
779 /* This nibble is already checked. */
780 s_assert(prev
->nibnum
== i
);
784 val
= NIBBLE_VAL(ckey
, i
);
785 place1
= &newnode
->node
.down
[val
];
786 s_assert(*place1
== NULL
);
787 *place1
= rb_malloc(sizeof(struct irc_radixtree_leaf
));
788 s_assert(*place1
!= NULL
);
789 (*place1
)->nibnum
= -1;
790 (*place1
)->leaf
.data
= data
;
791 (*place1
)->leaf
.key
= ckey
;
792 (*place1
)->leaf
.parent
= newnode
;
793 (*place1
)->leaf
.parent_val
= val
;
795 return &(*place1
)->leaf
;
799 irc_radixtree_add(struct irc_radixtree
*dict
, const char *key
, void *data
)
801 return (mowgli_radix_elem_add(dict
, key
, data
) != NULL
);
805 * irc_radixtree_delete(struct irc_radixtree *dtree, const char *key)
807 * Deletes data from a patricia tree.
810 * - patricia tree object
811 * - name of DTree node to delete
814 * - on success, the remaining data that needs to be rb_freed
818 * - data is removed from the DTree.
821 * - the returned data needs to be rb_freed/released manually!
824 irc_radixtree_delete(struct irc_radixtree
*dict
, const char *key
)
827 struct irc_radixtree_leaf
*leaf
;
829 leaf
= mowgli_radix_elem_find(dict
, key
);
835 irc_radixtree_elem_delete(dict
, leaf
);
840 irc_radixtree_elem_delete(struct irc_radixtree
*dict
, struct irc_radixtree_leaf
*leaf
)
842 union irc_radixtree_elem
*delem
, *prev
, *next
;
846 s_assert(dict
!= NULL
);
847 s_assert(leaf
!= NULL
);
849 delem
= (union irc_radixtree_elem
*) leaf
;
851 val
= delem
->leaf
.parent_val
;
852 prev
= delem
->leaf
.parent
;
854 rb_free(delem
->leaf
.key
);
859 prev
->node
.down
[val
] = NULL
;
861 /* Leaf is gone, now consider the node it was in. */
866 for (i
= 0; i
< POINTERS_PER_NODE
; i
++)
867 if (delem
->node
.down
[i
] != NULL
)
868 used
= used
== -1 ? i
: -2;
870 s_assert(used
== -2 || used
>= 0);
874 /* Only one pointer in this node, remove it.
875 * Replace the pointer that pointed to it by
876 * the sole pointer in it.
878 next
= delem
->node
.down
[used
];
879 val
= delem
->node
.parent_val
;
880 prev
= delem
->node
.parent
;
883 prev
->node
.down
[val
] = next
;
888 next
->leaf
.parent
= prev
, next
->leaf
.parent_val
= val
;
890 next
->node
.parent
= prev
, next
->node
.parent_val
= val
;
897 /* This was the last leaf. */
903 if (dict
->count
== 0)
905 s_assert(dict
->root
== NULL
);
911 * irc_radixtree_retrieve(struct irc_radixtree *dtree, const char *key)
913 * Retrieves data from a patricia.
916 * - patricia tree object
917 * - name of node to lookup
920 * - on success, the data bound to the DTree node.
927 irc_radixtree_retrieve(struct irc_radixtree
*dtree
, const char *key
)
929 struct irc_radixtree_leaf
*delem
= mowgli_radix_elem_find(dtree
, key
);
938 mowgli_radix_elem_get_key(struct irc_radixtree_leaf
*leaf
)
940 s_assert(leaf
!= NULL
);
946 mowgli_radix_elem_set_data(struct irc_radixtree_leaf
*leaf
, void *data
)
948 s_assert(leaf
!= NULL
);
954 mowgli_radix_elem_get_data(struct irc_radixtree_leaf
*leaf
)
956 s_assert(leaf
!= NULL
);
962 * irc_radixtree_size(struct irc_radixtree *dict)
964 * Returns the size of a patricia.
967 * - patricia tree object
976 irc_radixtree_size(struct irc_radixtree
*dict
)
978 s_assert(dict
!= NULL
);
983 /* returns the sum of the depths of the subtree rooted in delem at depth depth */
984 /* there is no need for this to be recursive, but it is easier... */
986 stats_recurse(union irc_radixtree_elem
*delem
, int depth
, int *pmaxdepth
)
990 union irc_radixtree_elem
*next
;
992 if (depth
> *pmaxdepth
)
998 s_assert(delem
->leaf
.parent
== NULL
);
1001 s_assert(delem
->node
.parent
== NULL
);
1007 for (val
= 0; val
< POINTERS_PER_NODE
; val
++)
1009 next
= delem
->node
.down
[val
];
1014 result
+= stats_recurse(next
, depth
+ 1, pmaxdepth
);
1018 s_assert(next
->leaf
.parent
== delem
);
1019 s_assert(next
->leaf
.parent_val
== val
);
1023 s_assert(next
->node
.parent
== delem
);
1024 s_assert(next
->node
.parent_val
== val
);
1025 s_assert(next
->node
.nibnum
> delem
->node
.nibnum
);
1033 * irc_radixtree_stats(struct irc_radixtree *dict, void (*cb)(const char *line, void *privdata), void *privdata)
1035 * Returns the size of a patricia.
1038 * - patricia tree object
1040 * - data for callback
1046 * - callback called with stats text
1049 irc_radixtree_stats(struct irc_radixtree
*dict
, void (*cb
)(const char *line
, void *privdata
), void *privdata
)
1054 s_assert(dict
!= NULL
);
1056 if (dict
->id
!= NULL
)
1057 snprintf(str
, sizeof str
, "Dictionary stats for %s (%d)",
1058 dict
->id
, dict
->count
);
1060 snprintf(str
, sizeof str
, "Dictionary stats for <%p> (%d)",
1061 (void *) dict
, dict
->count
);
1066 if (dict
->count
> 0)
1068 sum
= stats_recurse(dict
->root
, 0, &maxdepth
);
1069 snprintf(str
, sizeof str
, "Depth sum %d Avg depth %d Max depth %d", sum
, sum
/ dict
->count
, maxdepth
);
1073 snprintf(str
, sizeof str
, "Depth sum 0 Avg depth 0 Max depth 0");