2 * charybdis: an advanced ircd
3 * rb_dictionary.c: Dictionary-based information storage.
5 * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk>
6 * Copyright (c) 2007 Jilles Tjoelker <jilles -at- stack.nl>
8 * Permission to use, copy, modify, and/or distribute this software for any
9 * purpose with or without fee is hereby granted, provided that the above
10 * copyright notice and this permission notice is present in all copies.
12 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
13 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
14 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
15 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
16 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
17 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
18 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
19 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
20 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
21 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
22 * POSSIBILITY OF SUCH DAMAGE.
25 #include <librb_config.h>
27 #include <rb_dictionary.h>
32 rb_dictionary_element
*root
, *head
, *tail
;
40 static rb_dlink_list dictionary_list
= {NULL
, NULL
, 0};
43 * rb_dictionary_create(const char *name, DCF compare_cb)
45 * Dictionary object factory.
49 * - function to use for comparing two entries in the dtree
52 * - on success, a new dictionary object.
55 * - if services runs out of memory and cannot allocate the object,
56 * the program will abort.
58 rb_dictionary
*rb_dictionary_create(const char *name
,
61 rb_dictionary
*dtree
= (rb_dictionary
*) rb_malloc(sizeof(rb_dictionary
));
63 dtree
->compare_cb
= compare_cb
;
64 dtree
->id
= rb_strdup(name
);
66 rb_dlinkAdd(dtree
, &dtree
->node
, &dictionary_list
);
72 * rb_dictionary_set_comparator_func(rb_dictionary *dict,
75 * Resets the comparator function used by the dictionary code for
76 * updating the DTree structure.
80 * - new comparator function (passed as functor)
86 * - the dictionary comparator function is reset.
88 void rb_dictionary_set_comparator_func(rb_dictionary
*dict
,
91 lrb_assert(dict
!= NULL
);
92 lrb_assert(compare_cb
!= NULL
);
94 dict
->compare_cb
= compare_cb
;
98 * rb_dictionary_get_comparator_func(rb_dictionary *dict)
100 * Returns the current comparator function used by the dictionary.
103 * - dictionary object
106 * - comparator function (returned as functor)
112 rb_dictionary_get_comparator_func(rb_dictionary
*dict
)
114 lrb_assert(dict
!= NULL
);
116 return dict
->compare_cb
;
120 * rb_dictionary_get_linear_index(rb_dictionary *dict,
123 * Gets a linear index number for key.
126 * - dictionary tree object
130 * - position, from zero.
133 * - rebuilds the linear index if the tree is marked as dirty.
136 rb_dictionary_get_linear_index(rb_dictionary
*dict
, const void *key
)
138 rb_dictionary_element
*elem
;
140 lrb_assert(dict
!= NULL
);
141 lrb_assert(key
!= NULL
);
143 elem
= rb_dictionary_find(dict
, key
);
148 return elem
->position
;
151 rb_dictionary_element
*delem
;
154 for (delem
= dict
->head
, i
= 0; delem
!= NULL
; delem
= delem
->next
, i
++)
160 return elem
->position
;
164 * rb_dictionary_retune(rb_dictionary *dict, const void *key)
166 * Retunes the tree, self-optimizing for the element which belongs to key.
169 * - node to begin search from
175 * - a new root node is nominated.
178 rb_dictionary_retune(rb_dictionary
*dict
, const void *key
)
180 rb_dictionary_element n
, *tn
, *left
, *right
, *node
;
183 lrb_assert(dict
!= NULL
);
185 if (dict
->root
== NULL
)
189 * we initialize n with known values, since it's on stack
190 * memory. otherwise the dict would become corrupted.
192 * n is used for temporary storage while the tree is retuned.
195 n
.left
= n
.right
= NULL
;
198 /* this for(;;) loop is the main workhorse of the rebalancing */
199 for (node
= dict
->root
; ; )
201 if ((ret
= dict
->compare_cb(key
, node
->key
)) == 0)
206 if (node
->left
== NULL
)
209 if ((ret
= dict
->compare_cb(key
, node
->left
->key
)) < 0)
212 node
->left
= tn
->right
;
216 if (node
->left
== NULL
)
226 if (node
->right
== NULL
)
229 if ((ret
= dict
->compare_cb(key
, node
->right
->key
)) > 0)
232 node
->right
= tn
->left
;
236 if (node
->right
== NULL
)
246 left
->right
= node
->left
;
247 right
->left
= node
->right
;
249 node
->left
= n
.right
;
250 node
->right
= n
.left
;
256 * rb_dictionary_link(rb_dictionary *dict,
257 * rb_dictionary_element *delem)
259 * Links a dictionary tree element to the dictionary.
261 * When we add new nodes to the tree, it becomes the
262 * next nominated root. This is perhaps not a wise
263 * optimization because of automatic retuning, but
264 * it keeps the code simple.
268 * - dictionary tree element
274 * - a node is linked to the dictionary tree
277 rb_dictionary_link(rb_dictionary
*dict
,
278 rb_dictionary_element
*delem
)
280 lrb_assert(dict
!= NULL
);
281 lrb_assert(delem
!= NULL
);
287 if (dict
->root
== NULL
)
289 delem
->left
= delem
->right
= NULL
;
290 delem
->next
= delem
->prev
= NULL
;
291 dict
->head
= dict
->tail
= dict
->root
= delem
;
297 rb_dictionary_retune(dict
, delem
->key
);
299 if ((ret
= dict
->compare_cb(delem
->key
, dict
->root
->key
)) < 0)
301 delem
->left
= dict
->root
->left
;
302 delem
->right
= dict
->root
;
303 dict
->root
->left
= NULL
;
305 if (dict
->root
->prev
)
306 dict
->root
->prev
->next
= delem
;
310 delem
->prev
= dict
->root
->prev
;
311 delem
->next
= dict
->root
;
312 dict
->root
->prev
= delem
;
317 delem
->right
= dict
->root
->right
;
318 delem
->left
= dict
->root
;
319 dict
->root
->right
= NULL
;
321 if (dict
->root
->next
)
322 dict
->root
->next
->prev
= delem
;
326 delem
->next
= dict
->root
->next
;
327 delem
->prev
= dict
->root
;
328 dict
->root
->next
= delem
;
333 dict
->root
->key
= delem
->key
;
334 dict
->root
->data
= delem
->data
;
343 * rb_dictionary_unlink_root(rb_dictionary *dict)
345 * Unlinks the root dictionary tree element from the dictionary.
354 * - the root node is unlinked from the dictionary tree
357 rb_dictionary_unlink_root(rb_dictionary
*dict
)
359 rb_dictionary_element
*delem
, *nextnode
, *parentofnext
;
367 if (dict
->root
->left
== NULL
)
368 dict
->root
= dict
->root
->right
;
369 else if (dict
->root
->right
== NULL
)
370 dict
->root
= dict
->root
->left
;
373 /* Make the node with the next highest key the new root.
374 * This node has a NULL left pointer. */
375 nextnode
= delem
->next
;
376 lrb_assert(nextnode
->left
== NULL
);
377 if (nextnode
== delem
->right
)
379 dict
->root
= nextnode
;
380 dict
->root
->left
= delem
->left
;
384 parentofnext
= delem
->right
;
385 while (parentofnext
->left
!= NULL
&& parentofnext
->left
!= nextnode
)
386 parentofnext
= parentofnext
->left
;
387 lrb_assert(parentofnext
->left
== nextnode
);
388 parentofnext
->left
= nextnode
->right
;
389 dict
->root
= nextnode
;
390 dict
->root
->left
= delem
->left
;
391 dict
->root
->right
= delem
->right
;
396 if (delem
->prev
!= NULL
)
397 delem
->prev
->next
= delem
->next
;
399 if (dict
->head
== delem
)
400 dict
->head
= delem
->next
;
403 delem
->next
->prev
= delem
->prev
;
405 if (dict
->tail
== delem
)
406 dict
->tail
= delem
->prev
;
412 * rb_dictionary_destroy(rb_dictionary *dtree,
413 * void (*destroy_cb)(dictionary_elem_t *delem, void *privdata),
416 * Recursively destroys all nodes in a dictionary tree.
419 * - dictionary tree object
420 * - optional iteration callback
421 * - optional opaque/private data to pass to callback
427 * - on success, a dtree and optionally it's children are destroyed.
430 * - if this is called without a callback, the objects bound to the
431 * DTree will not be destroyed.
433 void rb_dictionary_destroy(rb_dictionary
*dtree
,
434 void (*destroy_cb
)(rb_dictionary_element
*delem
, void *privdata
),
437 rb_dictionary_element
*n
, *tn
;
439 lrb_assert(dtree
!= NULL
);
441 RB_DLINK_FOREACH_SAFE(n
, tn
, dtree
->head
)
443 if (destroy_cb
!= NULL
)
444 (*destroy_cb
)(n
, privdata
);
449 rb_dlinkDelete(&dtree
->node
, &dictionary_list
);
455 * rb_dictionary_foreach(rb_dictionary *dtree,
456 * void (*destroy_cb)(dictionary_elem_t *delem, void *privdata),
459 * Iterates over all entries in a DTree.
462 * - dictionary tree object
463 * - optional iteration callback
464 * - optional opaque/private data to pass to callback
470 * - on success, a dtree is iterated
472 void rb_dictionary_foreach(rb_dictionary
*dtree
,
473 int (*foreach_cb
)(rb_dictionary_element
*delem
, void *privdata
),
476 rb_dictionary_element
*n
, *tn
;
478 lrb_assert(dtree
!= NULL
);
480 RB_DLINK_FOREACH_SAFE(n
, tn
, dtree
->head
)
482 /* delem_t is a subclass of node_t. */
483 rb_dictionary_element
*delem
= (rb_dictionary_element
*) n
;
485 if (foreach_cb
!= NULL
)
486 (*foreach_cb
)(delem
, privdata
);
491 * rb_dictionary_search(rb_dictionary *dtree,
492 * void (*destroy_cb)(rb_dictionary_element *delem, void *privdata),
495 * Searches all entries in a DTree using a custom callback.
498 * - dictionary tree object
499 * - optional iteration callback
500 * - optional opaque/private data to pass to callback
503 * - on success, the requested object
504 * - on failure, NULL.
507 * - a dtree is iterated until the requested conditions are met
509 void *rb_dictionary_search(rb_dictionary
*dtree
,
510 void *(*foreach_cb
)(rb_dictionary_element
*delem
, void *privdata
),
513 rb_dictionary_element
*n
, *tn
;
516 lrb_assert(dtree
!= NULL
);
518 RB_DLINK_FOREACH_SAFE(n
, tn
, dtree
->head
)
520 /* delem_t is a subclass of node_t. */
521 rb_dictionary_element
*delem
= (rb_dictionary_element
*) n
;
523 if (foreach_cb
!= NULL
)
524 ret
= (*foreach_cb
)(delem
, privdata
);
534 * rb_dictionary_foreach_start(rb_dictionary *dtree,
535 * rb_dictionary_iter *state);
537 * Initializes a static DTree iterator.
540 * - dictionary tree object
541 * - static DTree iterator
547 * - the static iterator, &state, is initialized.
549 void rb_dictionary_foreach_start(rb_dictionary
*dtree
,
550 rb_dictionary_iter
*state
)
552 lrb_assert(dtree
!= NULL
);
553 lrb_assert(state
!= NULL
);
558 /* find first item */
559 state
->cur
= dtree
->head
;
561 if (state
->cur
== NULL
)
564 /* make state->cur point to first item and state->next point to
566 state
->next
= state
->cur
;
567 rb_dictionary_foreach_next(dtree
, state
);
571 * rb_dictionary_foreach_cur(rb_dictionary *dtree,
572 * rb_dictionary_iter *state);
574 * Returns the data from the current node being iterated by the
578 * - dictionary tree object
579 * - static DTree iterator
582 * - reference to data in the current dtree node being iterated
587 void *rb_dictionary_foreach_cur(rb_dictionary
*dtree
,
588 rb_dictionary_iter
*state
)
590 lrb_assert(dtree
!= NULL
);
591 lrb_assert(state
!= NULL
);
593 return state
->cur
!= NULL
? state
->cur
->data
: NULL
;
597 * rb_dictionary_foreach_next(rb_dictionary *dtree,
598 * rb_dictionary_iter *state);
600 * Advances a static DTree iterator.
603 * - dictionary tree object
604 * - static DTree iterator
610 * - the static iterator, &state, is advanced to a new DTree node.
612 void rb_dictionary_foreach_next(rb_dictionary
*dtree
,
613 rb_dictionary_iter
*state
)
615 lrb_assert(dtree
!= NULL
);
616 lrb_assert(state
!= NULL
);
618 if (state
->cur
== NULL
)
620 rb_lib_log("rb_dictionary_foreach_next(): called again after iteration finished on dtree<%p>", (void *)dtree
);
624 state
->cur
= state
->next
;
626 if (state
->next
== NULL
)
629 state
->next
= state
->next
->next
;
633 * rb_dictionary_find(rb_dictionary *dtree, const void *key)
635 * Looks up a DTree node by name.
638 * - dictionary tree object
639 * - name of node to lookup
642 * - on success, the dtree node requested
648 rb_dictionary_element
*rb_dictionary_find(rb_dictionary
*dict
, const void *key
)
650 lrb_assert(dict
!= NULL
);
651 lrb_assert(key
!= NULL
);
653 /* retune for key, key will be the tree's root if it's available */
654 rb_dictionary_retune(dict
, key
);
656 if (dict
->root
&& !dict
->compare_cb(key
, dict
->root
->key
))
663 * rb_dictionary_add(rb_dictionary *dtree, const void *key, void *data)
665 * Creates a new DTree node and binds data to it.
668 * - dictionary tree object
669 * - name for new DTree node
670 * - data to bind to the new DTree node
673 * - on success, a new DTree node
677 * - data is inserted into the DTree.
679 rb_dictionary_element
*rb_dictionary_add(rb_dictionary
*dict
, const void *key
, void *data
)
681 rb_dictionary_element
*delem
;
683 lrb_assert(dict
!= NULL
);
684 lrb_assert(key
!= NULL
);
685 lrb_assert(data
!= NULL
);
686 lrb_assert(rb_dictionary_find(dict
, key
) == NULL
);
688 delem
= rb_malloc(sizeof(*delem
));
692 rb_dictionary_link(dict
, delem
);
698 * rb_dictionary_delete(rb_dictionary *dtree, const void *key)
700 * Deletes data from a dictionary tree.
703 * - dictionary tree object
704 * - name of DTree node to delete
707 * - on success, the remaining data that needs to be rb_freed
711 * - data is removed from the DTree.
714 * - the returned data needs to be rb_freed/released manually!
716 void *rb_dictionary_delete(rb_dictionary
*dtree
, const void *key
)
718 rb_dictionary_element
*delem
= rb_dictionary_find(dtree
, key
);
726 rb_dictionary_unlink_root(dtree
);
733 * rb_dictionary_retrieve(rb_dictionary *dtree, const void *key)
735 * Retrieves data from a dictionary.
738 * - dictionary tree object
739 * - name of node to lookup
742 * - on success, the data bound to the DTree node.
748 void *rb_dictionary_retrieve(rb_dictionary
*dtree
, const void *key
)
750 rb_dictionary_element
*delem
= rb_dictionary_find(dtree
, key
);
759 * rb_dictionary_size(rb_dictionary *dict)
761 * Returns the size of a dictionary.
764 * - dictionary tree object
767 * - size of dictionary
772 unsigned int rb_dictionary_size(rb_dictionary
*dict
)
774 lrb_assert(dict
!= NULL
);
779 /* returns the sum of the depths of the subtree rooted in delem at depth depth */
781 stats_recurse(rb_dictionary_element
*delem
, int depth
, int *pmaxdepth
)
785 if (depth
> *pmaxdepth
)
788 if (delem
&& delem
->left
)
789 result
+= stats_recurse(delem
->left
, depth
+ 1, pmaxdepth
);
790 if (delem
&& delem
->right
)
791 result
+= stats_recurse(delem
->right
, depth
+ 1, pmaxdepth
);
796 * rb_dictionary_stats(rb_dictionary *dict, void (*cb)(const char *line, void *privdata), void *privdata)
798 * Returns the size of a dictionary.
801 * - dictionary tree object
803 * - data for callback
809 * - callback called with stats text
811 void rb_dictionary_stats(rb_dictionary
*dict
, void (*cb
)(const char *line
, void *privdata
), void *privdata
)
816 lrb_assert(dict
!= NULL
);
821 sum
= stats_recurse(dict
->root
, 0, &maxdepth
);
822 snprintf(str
, sizeof str
, "%-30s %-15s %-10d %-10d %-10d %-10d", dict
->id
, "DICT", dict
->count
, sum
, sum
/ dict
->count
, maxdepth
);
826 snprintf(str
, sizeof str
, "%-30s %-15s %-10s %-10s %-10s %-10s", dict
->id
, "DICT", "0", "0", "0", "0");
832 void rb_dictionary_stats_walk(void (*cb
)(const char *line
, void *privdata
), void *privdata
)
836 RB_DLINK_FOREACH(ptr
, dictionary_list
.head
)
838 rb_dictionary_stats(ptr
->data
, cb
, privdata
);