2 * Solanum: a slightly advanced ircd
3 * rb_radixtree.c: Dictionary-based information storage.
5 * Copyright (c) 2007-2016 Ariadne Conill <ariadne -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.
35 #include <librb_config.h>
37 #include <rb_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 rb_radixtree_elem
;
56 typedef union rb_radixtree_elem rb_radixtree_elem
;
58 /* Other typedefs are in rb_radixtree.h */
59 typedef struct rb_radixtree_node rb_radixtree_node
;
63 void (*canonize_cb
)(char *key
);
64 rb_radixtree_elem
*root
;
72 #define POINTERS_PER_NODE 16
73 #define NIBBLE_VAL(key, nibnum) (((key)[(nibnum) / 2] >> (((nibnum) & 1) ? 0 : 4)) & 0xF)
75 struct rb_radixtree_node
77 /* nibble to test (nibble NUM%2 of byte NUM/2) */
80 /* branches of the tree */
81 rb_radixtree_elem
*down
[POINTERS_PER_NODE
];
82 rb_radixtree_elem
*parent
;
87 struct rb_radixtree_leaf
89 /* -1 to indicate this is a leaf, not a node */
92 /* data associated with the key */
95 /* key (canonized copy) */
97 rb_radixtree_elem
*parent
;
102 union rb_radixtree_elem
105 rb_radixtree_node node
;
107 rb_radixtree_leaf leaf
;
110 #define IS_LEAF(elem) ((elem)->nibnum == -1)
112 /* Preserve compatibility with the old mowgli_patricia.h */
113 #define STATE_CUR(state) ((state)->pspare[0])
114 #define STATE_NEXT(state) ((state)->pspare[1])
119 * Find the smallest leaf hanging off a subtree.
122 * - element (may be leaf or node) heading subtree
125 * - lowest leaf in subtree
130 static rb_radixtree_elem
*
131 first_leaf(rb_radixtree_elem
*delem
)
135 while (!IS_LEAF(delem
))
137 for (val
= 0; val
< POINTERS_PER_NODE
; val
++)
138 if (delem
->node
.down
[val
] != NULL
)
140 delem
= delem
->node
.down
[val
];
149 * rb_radixtree_create_named(const char *name,
150 * void (*canonize_cb)(char *key))
152 * Dictionary object factory.
156 * - function to use for canonizing keys (for example, use
157 * a function that makes the string upper case to create
158 * a patricia with case-insensitive matching)
161 * - on success, a new patricia object.
164 * - if services runs out of memory and cannot allocate the object,
165 * the program will abort.
168 rb_radixtree_create(const char *name
, void (*canonize_cb
)(char *key
))
170 rb_radixtree
*dtree
= (rb_radixtree
*) rb_malloc(sizeof(rb_radixtree
));
172 dtree
->canonize_cb
= canonize_cb
;
173 dtree
->id
= rb_strdup(name
);
176 rb_dlinkAdd(dtree
, &dtree
->node
, &radixtree_list
);
182 * rb_radixtree_destroy(rb_radixtree *dtree,
183 * void (*destroy_cb)(const char *key, void *data, void *privdata),
186 * Recursively destroys all nodes in a patricia tree.
189 * - patricia tree object
190 * - optional iteration callback
191 * - optional opaque/private data to pass to callback
197 * - on success, a dtree and optionally it's children are destroyed.
200 * - if this is called without a callback, the objects bound to the
201 * DTree will not be destroyed.
204 rb_radixtree_destroy(rb_radixtree
*dtree
, void (*destroy_cb
)(const char *key
, void *data
, void *privdata
), void *privdata
)
206 rb_radixtree_iteration_state state
;
207 rb_radixtree_elem
*delem
;
211 lrb_assert(dtree
!= NULL
);
213 RB_RADIXTREE_FOREACH(entry
, &state
, dtree
)
215 delem
= STATE_CUR(&state
);
217 if (destroy_cb
!= NULL
)
218 (*destroy_cb
)(delem
->leaf
.key
, delem
->leaf
.data
,
221 rb_radixtree_delete(dtree
, delem
->leaf
.key
);
224 rb_dlinkDelete(&dtree
->node
, &radixtree_list
);
230 * rb_radixtree_foreach(rb_radixtree *dtree,
231 * int (*foreach_cb)(const char *key, void *data, void *privdata),
234 * Iterates over all entries in a DTree.
237 * - patricia tree object
238 * - optional iteration callback
239 * - optional opaque/private data to pass to callback
245 * - on success, a dtree is iterated
248 rb_radixtree_foreach(rb_radixtree
*dtree
, int (*foreach_cb
)(const char *key
, void *data
, void *privdata
), void *privdata
)
250 rb_radixtree_elem
*delem
, *next
;
254 lrb_assert(dtree
!= NULL
);
261 /* Only one element in the tree */
264 if (foreach_cb
!= NULL
)
265 (*foreach_cb
)(delem
->leaf
.key
, delem
->leaf
.data
, privdata
);
275 next
= delem
->node
.down
[val
++];
276 while (next
== NULL
&& val
< POINTERS_PER_NODE
);
282 if (foreach_cb
!= NULL
)
283 (*foreach_cb
)(next
->leaf
.key
, next
->leaf
.data
, privdata
);
292 while (val
>= POINTERS_PER_NODE
)
294 val
= delem
->node
.parent_val
;
295 delem
= delem
->node
.parent
;
302 } while (delem
!= NULL
);
306 * rb_radixtree_search(rb_radixtree *dtree,
307 * void *(*foreach_cb)(const char *key, void *data, void *privdata),
310 * Searches all entries in a DTree using a custom callback.
313 * - patricia tree object
314 * - optional iteration callback
315 * - optional opaque/private data to pass to callback
318 * - on success, the requested object
319 * - on failure, NULL.
322 * - a dtree is iterated until the requested conditions are met
325 rb_radixtree_search(rb_radixtree
*dtree
, void *(*foreach_cb
)(const char *key
, void *data
, void *privdata
), void *privdata
)
327 rb_radixtree_elem
*delem
, *next
;
332 lrb_assert(dtree
!= NULL
);
339 /* Only one element in the tree */
342 if (foreach_cb
!= NULL
)
343 return (*foreach_cb
)(delem
->leaf
.key
, delem
->leaf
.data
, privdata
);
353 next
= delem
->node
.down
[val
++];
354 while (next
== NULL
&& val
< POINTERS_PER_NODE
);
360 if (foreach_cb
!= NULL
)
361 ret
= (*foreach_cb
)(next
->leaf
.key
, next
->leaf
.data
, privdata
);
373 while (val
>= POINTERS_PER_NODE
)
375 val
= delem
->node
.parent_val
;
376 delem
= delem
->node
.parent
;
389 * rb_radixtree_foreach_start(rb_radixtree *dtree,
390 * rb_radixtree_iteration_state *state);
392 * Initializes a static DTree iterator.
395 * - patricia tree object
396 * - static DTree iterator
402 * - the static iterator, &state, is initialized.
405 rb_radixtree_foreach_start(rb_radixtree
*dtree
, rb_radixtree_iteration_state
*state
)
410 lrb_assert(state
!= NULL
);
412 if (dtree
->root
!= NULL
)
413 STATE_NEXT(state
) = first_leaf(dtree
->root
);
415 STATE_NEXT(state
) = NULL
;
417 STATE_CUR(state
) = STATE_NEXT(state
);
419 if (STATE_NEXT(state
) == NULL
)
422 /* make STATE_CUR point to first item and STATE_NEXT point to
424 rb_radixtree_foreach_next(dtree
, state
);
428 * rb_radixtree_foreach_cur(rb_radixtree *dtree,
429 * rb_radixtree_iteration_state *state);
431 * Returns the data from the current node being iterated by the
435 * - patricia tree object
436 * - static DTree iterator
439 * - reference to data in the current dtree node being iterated
445 rb_radixtree_foreach_cur(rb_radixtree
*dtree
, rb_radixtree_iteration_state
*state
)
450 lrb_assert(state
!= NULL
);
452 return STATE_CUR(state
) != NULL
?
453 ((rb_radixtree_leaf
*) STATE_CUR(state
))->data
: NULL
;
457 * rb_radixtree_foreach_next(rb_radixtree *dtree,
458 * rb_radixtree_iteration_state *state);
460 * Advances a static DTree iterator.
463 * - patricia tree object
464 * - static DTree iterator
470 * - the static iterator, &state, is advanced to a new DTree node.
473 rb_radixtree_foreach_next(rb_radixtree
*dtree
, rb_radixtree_iteration_state
*state
)
475 rb_radixtree_leaf
*leaf
;
477 rb_radixtree_elem
*delem
, *next
;
484 lrb_assert(state
!= NULL
);
486 if (STATE_CUR(state
) == NULL
)
489 STATE_CUR(state
) = STATE_NEXT(state
);
491 if (STATE_NEXT(state
) == NULL
)
494 leaf
= STATE_NEXT(state
);
495 delem
= leaf
->parent
;
496 val
= leaf
->parent_val
;
498 while (delem
!= NULL
)
501 next
= delem
->node
.down
[val
++];
502 while (next
== NULL
&& val
< POINTERS_PER_NODE
);
508 /* We will find the original leaf first. */
509 if (&next
->leaf
!= leaf
)
511 if (strcmp(next
->leaf
.key
, leaf
->key
) < 0)
513 STATE_NEXT(state
) = NULL
;
517 STATE_NEXT(state
) = next
;
528 while (val
>= POINTERS_PER_NODE
)
530 val
= delem
->node
.parent_val
;
531 delem
= delem
->node
.parent
;
540 STATE_NEXT(state
) = NULL
;
544 * rb_radixtree_elem_find(rb_radixtree *dtree, const char *key)
546 * Looks up a DTree node by name.
549 * - patricia tree object
550 * - name of node to lookup
551 * - whether to do a direct or fuzzy match
554 * - on success, the dtree node requested
561 rb_radixtree_elem_find(rb_radixtree
*dict
, const char *key
, int fuzzy
)
563 char ckey_store
[256];
565 char *ckey_buf
= NULL
;
567 rb_radixtree_elem
*delem
;
571 lrb_assert(dict
!= NULL
);
572 lrb_assert(key
!= NULL
);
574 keylen
= strlen(key
);
576 if (dict
->canonize_cb
== NULL
)
582 if (keylen
>= (int) sizeof(ckey_store
))
584 ckey_buf
= rb_strdup(key
);
585 dict
->canonize_cb(ckey_buf
);
590 rb_strlcpy(ckey_store
, key
, sizeof ckey_store
);
591 dict
->canonize_cb(ckey_store
);
598 while (delem
!= NULL
&& !IS_LEAF(delem
))
600 if (delem
->nibnum
/ 2 < keylen
)
601 val
= NIBBLE_VAL(ckey
, delem
->nibnum
);
605 delem
= delem
->node
.down
[val
];
608 /* Now, if the key is in the tree, delem contains it. */
609 if ((delem
!= NULL
) && !fuzzy
&& strcmp(delem
->leaf
.key
, ckey
))
612 if (ckey_buf
!= NULL
)
619 * rb_radixtree_foreach_start_from(rb_radixtree *dtree, rb_radixtree_iteration_state *state, const char *key)
621 * Starts iteration from a specified key, by wrapping rb_radixtree_elem_find().
624 * - patricia tree object
626 * - key to start from
632 * - the iterator's state is initialized at a specific point
635 rb_radixtree_foreach_start_from(rb_radixtree
*dtree
, rb_radixtree_iteration_state
*state
, const char *key
)
637 lrb_assert(dtree
!= NULL
);
638 lrb_assert(state
!= NULL
);
642 STATE_NEXT(state
) = rb_radixtree_elem_find(dtree
, key
, 1);
643 STATE_CUR(state
) = STATE_NEXT(state
);
645 /* make STATE_CUR point to selected item and STATE_NEXT point to
646 * next item in the tree */
647 rb_radixtree_foreach_next(dtree
, state
);
650 rb_radixtree_foreach_start(dtree
, state
);
654 * rb_radixtree_add(rb_radixtree *dtree, const char *key, void *data)
656 * Creates a new DTree node and binds data to it.
659 * - patricia tree object
660 * - name for new DTree node
661 * - data to bind to the new DTree node
665 * - on failure, FALSE
668 * - data is inserted into the DTree.
671 rb_radixtree_elem_add(rb_radixtree
*dict
, const char *key
, void *data
)
675 rb_radixtree_elem
*delem
, *prev
, *newnode
;
677 rb_radixtree_elem
**place1
;
682 lrb_assert(dict
!= NULL
);
683 lrb_assert(key
!= NULL
);
684 lrb_assert(data
!= NULL
);
686 keylen
= strlen(key
);
687 ckey
= rb_strdup(key
);
692 if (dict
->canonize_cb
!= NULL
)
693 dict
->canonize_cb(ckey
);
696 val
= POINTERS_PER_NODE
+ 2; /* trap value */
699 while (delem
!= NULL
&& !IS_LEAF(delem
))
703 if (delem
->nibnum
/ 2 < keylen
)
704 val
= NIBBLE_VAL(ckey
, delem
->nibnum
);
708 delem
= delem
->node
.down
[val
];
711 /* Now, if the key is in the tree, delem contains it. */
712 if ((delem
!= NULL
) && !strcmp(delem
->leaf
.key
, ckey
))
718 if ((delem
== NULL
) && (prev
!= NULL
))
719 /* Get a leaf to compare with. */
720 delem
= first_leaf(prev
);
724 lrb_assert(prev
== NULL
);
725 lrb_assert(dict
->count
== 0);
726 place1
= &dict
->root
;
727 *place1
= rb_malloc(sizeof(rb_radixtree_leaf
));
728 lrb_assert(*place1
!= NULL
);
729 (*place1
)->nibnum
= -1;
730 (*place1
)->leaf
.data
= data
;
731 (*place1
)->leaf
.key
= ckey
;
732 (*place1
)->leaf
.parent
= prev
;
733 (*place1
)->leaf
.parent_val
= val
;
735 return &(*place1
)->leaf
;
738 /* Find the first nibble where they differ. */
739 for (i
= 0; NIBBLE_VAL(ckey
, i
) == NIBBLE_VAL(delem
->leaf
.key
, i
); i
++)
742 /* Find where to insert the new node. */
743 while (prev
!= NULL
&& prev
->nibnum
> i
)
745 val
= prev
->node
.parent_val
;
746 prev
= prev
->node
.parent
;
749 if ((prev
== NULL
) || (prev
->nibnum
< i
))
751 /* Insert new node below prev */
752 newnode
= rb_malloc(sizeof(rb_radixtree_node
));
753 lrb_assert(newnode
!= NULL
);
755 newnode
->node
.parent
= prev
;
756 newnode
->node
.parent_val
= val
;
758 for (j
= 0; j
< POINTERS_PER_NODE
; j
++)
759 newnode
->node
.down
[j
] = NULL
;
763 newnode
->node
.down
[NIBBLE_VAL(delem
->leaf
.key
, i
)] = dict
->root
;
765 if (IS_LEAF(dict
->root
))
767 dict
->root
->leaf
.parent
= newnode
;
768 dict
->root
->leaf
.parent_val
= NIBBLE_VAL(delem
->leaf
.key
, i
);
772 lrb_assert(dict
->root
->nibnum
> i
);
773 dict
->root
->node
.parent
= newnode
;
774 dict
->root
->node
.parent_val
= NIBBLE_VAL(delem
->leaf
.key
, i
);
777 dict
->root
= newnode
;
781 newnode
->node
.down
[NIBBLE_VAL(delem
->leaf
.key
, i
)] = prev
->node
.down
[val
];
783 if (IS_LEAF(prev
->node
.down
[val
]))
785 prev
->node
.down
[val
]->leaf
.parent
= newnode
;
786 prev
->node
.down
[val
]->leaf
.parent_val
= NIBBLE_VAL(delem
->leaf
.key
, i
);
790 prev
->node
.down
[val
]->node
.parent
= newnode
;
791 prev
->node
.down
[val
]->node
.parent_val
= NIBBLE_VAL(delem
->leaf
.key
, i
);
794 prev
->node
.down
[val
] = newnode
;
799 /* This nibble is already checked. */
800 lrb_assert(prev
->nibnum
== i
);
804 val
= NIBBLE_VAL(ckey
, i
);
805 place1
= &newnode
->node
.down
[val
];
806 lrb_assert(*place1
== NULL
);
807 *place1
= rb_malloc(sizeof(rb_radixtree_leaf
));
808 lrb_assert(*place1
!= NULL
);
809 (*place1
)->nibnum
= -1;
810 (*place1
)->leaf
.data
= data
;
811 (*place1
)->leaf
.key
= ckey
;
812 (*place1
)->leaf
.parent
= newnode
;
813 (*place1
)->leaf
.parent_val
= val
;
815 return &(*place1
)->leaf
;
819 rb_radixtree_add(rb_radixtree
*dict
, const char *key
, void *data
)
821 return (rb_radixtree_elem_add(dict
, key
, data
) != NULL
);
825 * rb_radixtree_delete(rb_radixtree *dtree, const char *key)
827 * Deletes data from a patricia tree.
830 * - patricia tree object
831 * - name of DTree node to delete
834 * - on success, the remaining data that needs to be rb_freed
838 * - data is removed from the DTree.
841 * - the returned data needs to be rb_freed/released manually!
844 rb_radixtree_delete(rb_radixtree
*dict
, const char *key
)
847 rb_radixtree_leaf
*leaf
;
849 leaf
= rb_radixtree_elem_find(dict
, key
, 0);
855 rb_radixtree_elem_delete(dict
, leaf
);
860 rb_radixtree_elem_delete(rb_radixtree
*dict
, rb_radixtree_leaf
*leaf
)
862 rb_radixtree_elem
*delem
, *prev
, *next
;
866 lrb_assert(dict
!= NULL
);
867 lrb_assert(leaf
!= NULL
);
869 delem
= (rb_radixtree_elem
*) leaf
;
871 val
= delem
->leaf
.parent_val
;
872 prev
= delem
->leaf
.parent
;
874 rb_free(delem
->leaf
.key
);
879 prev
->node
.down
[val
] = NULL
;
881 /* Leaf is gone, now consider the node it was in. */
886 for (i
= 0; i
< POINTERS_PER_NODE
; i
++)
887 if (delem
->node
.down
[i
] != NULL
)
888 used
= used
== -1 ? i
: -2;
890 lrb_assert(used
== -2 || used
>= 0);
894 /* Only one pointer in this node, remove it.
895 * Replace the pointer that pointed to it by
896 * the sole pointer in it.
898 next
= delem
->node
.down
[used
];
899 val
= delem
->node
.parent_val
;
900 prev
= delem
->node
.parent
;
903 prev
->node
.down
[val
] = next
;
908 next
->leaf
.parent
= prev
, next
->leaf
.parent_val
= val
;
910 next
->node
.parent
= prev
, next
->node
.parent_val
= val
;
917 /* This was the last leaf. */
923 if (dict
->count
== 0)
925 lrb_assert(dict
->root
== NULL
);
931 * rb_radixtree_retrieve(rb_radixtree *dtree, const char *key)
933 * Retrieves data from a patricia.
936 * - patricia tree object
937 * - name of node to lookup
940 * - on success, the data bound to the DTree node.
947 rb_radixtree_retrieve(rb_radixtree
*dtree
, const char *key
)
949 rb_radixtree_leaf
*delem
= rb_radixtree_elem_find(dtree
, key
, 0);
958 rb_radixtree_elem_get_key(rb_radixtree_leaf
*leaf
)
960 lrb_assert(leaf
!= NULL
);
966 rb_radixtree_elem_set_data(rb_radixtree_leaf
*leaf
, void *data
)
968 lrb_assert(leaf
!= NULL
);
974 rb_radixtree_elem_get_data(rb_radixtree_leaf
*leaf
)
976 lrb_assert(leaf
!= NULL
);
982 * rb_radixtree_size(rb_radixtree *dict)
984 * Returns the size of a patricia.
987 * - patricia tree object
996 rb_radixtree_size(rb_radixtree
*dict
)
998 lrb_assert(dict
!= NULL
);
1003 /* returns the sum of the depths of the subtree rooted in delem at depth depth */
1004 /* there is no need for this to be recursive, but it is easier... */
1006 stats_recurse(rb_radixtree_elem
*delem
, int depth
, int *pmaxdepth
)
1010 rb_radixtree_elem
*next
;
1012 if (depth
> *pmaxdepth
)
1018 lrb_assert(delem
->leaf
.parent
== NULL
);
1021 lrb_assert(delem
->node
.parent
== NULL
);
1027 for (val
= 0; val
< POINTERS_PER_NODE
; val
++)
1029 next
= delem
->node
.down
[val
];
1034 result
+= stats_recurse(next
, depth
+ 1, pmaxdepth
);
1038 lrb_assert(next
->leaf
.parent
== delem
);
1039 lrb_assert(next
->leaf
.parent_val
== val
);
1043 lrb_assert(next
->node
.parent
== delem
);
1044 lrb_assert(next
->node
.parent_val
== val
);
1045 lrb_assert(next
->node
.nibnum
> delem
->node
.nibnum
);
1053 * rb_radixtree_stats(rb_radixtree *dict, void (*cb)(const char *line, void *privdata), void *privdata)
1055 * Returns the size of a patricia.
1058 * - patricia tree object
1060 * - data for callback
1066 * - callback called with stats text
1069 rb_radixtree_stats(rb_radixtree
*dict
, void (*cb
)(const char *line
, void *privdata
), void *privdata
)
1074 lrb_assert(dict
!= NULL
);
1077 if (dict
->count
> 0)
1079 sum
= stats_recurse(dict
->root
, 0, &maxdepth
);
1080 snprintf(str
, sizeof str
, "%-30s %-15s %-10u %-10d %-10d %-10d", dict
->id
, "RADIX", dict
->count
, sum
, sum
/ dict
->count
, maxdepth
);
1084 snprintf(str
, sizeof str
, "%-30s %-15s %-10s %-10s %-10s %-10s", dict
->id
, "RADIX", "0", "0", "0", "0");
1092 rb_radixtree_stats_walk(void (*cb
)(const char *line
, void *privdata
), void *privdata
)
1096 RB_DLINK_FOREACH(ptr
, radixtree_list
.head
)
1098 rb_radixtree_stats(ptr
->data
, cb
, privdata
);