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
);
142 elem
= rb_dictionary_find(dict
, key
);
147 return elem
->position
;
150 rb_dictionary_element
*delem
;
153 for (delem
= dict
->head
, i
= 0; delem
!= NULL
; delem
= delem
->next
, i
++)
159 return elem
->position
;
163 * rb_dictionary_retune(rb_dictionary *dict, const void *key)
165 * Retunes the tree, self-optimizing for the element which belongs to key.
168 * - node to begin search from
174 * - a new root node is nominated.
177 rb_dictionary_retune(rb_dictionary
*dict
, const void *key
)
179 rb_dictionary_element n
, *tn
, *left
, *right
, *node
;
182 lrb_assert(dict
!= NULL
);
184 if (dict
->root
== NULL
)
188 * we initialize n with known values, since it's on stack
189 * memory. otherwise the dict would become corrupted.
191 * n is used for temporary storage while the tree is retuned.
194 n
.left
= n
.right
= NULL
;
197 /* this for(;;) loop is the main workhorse of the rebalancing */
198 for (node
= dict
->root
; ; )
200 if ((ret
= dict
->compare_cb(key
, node
->key
)) == 0)
205 if (node
->left
== NULL
)
208 if ((ret
= dict
->compare_cb(key
, node
->left
->key
)) < 0)
211 node
->left
= tn
->right
;
215 if (node
->left
== NULL
)
225 if (node
->right
== NULL
)
228 if ((ret
= dict
->compare_cb(key
, node
->right
->key
)) > 0)
231 node
->right
= tn
->left
;
235 if (node
->right
== NULL
)
245 left
->right
= node
->left
;
246 right
->left
= node
->right
;
248 node
->left
= n
.right
;
249 node
->right
= n
.left
;
255 * rb_dictionary_link(rb_dictionary *dict,
256 * rb_dictionary_element *delem)
258 * Links a dictionary tree element to the dictionary.
260 * When we add new nodes to the tree, it becomes the
261 * next nominated root. This is perhaps not a wise
262 * optimization because of automatic retuning, but
263 * it keeps the code simple.
267 * - dictionary tree element
273 * - a node is linked to the dictionary tree
276 rb_dictionary_link(rb_dictionary
*dict
,
277 rb_dictionary_element
*delem
)
279 lrb_assert(dict
!= NULL
);
280 lrb_assert(delem
!= NULL
);
286 if (dict
->root
== NULL
)
288 delem
->left
= delem
->right
= NULL
;
289 delem
->next
= delem
->prev
= NULL
;
290 dict
->head
= dict
->tail
= dict
->root
= delem
;
296 rb_dictionary_retune(dict
, delem
->key
);
298 if ((ret
= dict
->compare_cb(delem
->key
, dict
->root
->key
)) < 0)
300 delem
->left
= dict
->root
->left
;
301 delem
->right
= dict
->root
;
302 dict
->root
->left
= NULL
;
304 if (dict
->root
->prev
)
305 dict
->root
->prev
->next
= delem
;
309 delem
->prev
= dict
->root
->prev
;
310 delem
->next
= dict
->root
;
311 dict
->root
->prev
= delem
;
316 delem
->right
= dict
->root
->right
;
317 delem
->left
= dict
->root
;
318 dict
->root
->right
= NULL
;
320 if (dict
->root
->next
)
321 dict
->root
->next
->prev
= delem
;
325 delem
->next
= dict
->root
->next
;
326 delem
->prev
= dict
->root
;
327 dict
->root
->next
= delem
;
332 dict
->root
->key
= delem
->key
;
333 dict
->root
->data
= delem
->data
;
342 * rb_dictionary_unlink_root(rb_dictionary *dict)
344 * Unlinks the root dictionary tree element from the dictionary.
353 * - the root node is unlinked from the dictionary tree
356 rb_dictionary_unlink_root(rb_dictionary
*dict
)
358 rb_dictionary_element
*delem
, *nextnode
, *parentofnext
;
366 if (dict
->root
->left
== NULL
)
367 dict
->root
= dict
->root
->right
;
368 else if (dict
->root
->right
== NULL
)
369 dict
->root
= dict
->root
->left
;
372 /* Make the node with the next highest key the new root.
373 * This node has a NULL left pointer. */
374 nextnode
= delem
->next
;
375 lrb_assert(nextnode
->left
== NULL
);
376 if (nextnode
== delem
->right
)
378 dict
->root
= nextnode
;
379 dict
->root
->left
= delem
->left
;
383 parentofnext
= delem
->right
;
384 while (parentofnext
->left
!= NULL
&& parentofnext
->left
!= nextnode
)
385 parentofnext
= parentofnext
->left
;
386 lrb_assert(parentofnext
->left
== nextnode
);
387 parentofnext
->left
= nextnode
->right
;
388 dict
->root
= nextnode
;
389 dict
->root
->left
= delem
->left
;
390 dict
->root
->right
= delem
->right
;
395 if (delem
->prev
!= NULL
)
396 delem
->prev
->next
= delem
->next
;
398 if (dict
->head
== delem
)
399 dict
->head
= delem
->next
;
402 delem
->next
->prev
= delem
->prev
;
404 if (dict
->tail
== delem
)
405 dict
->tail
= delem
->prev
;
411 * rb_dictionary_destroy(rb_dictionary *dtree,
412 * void (*destroy_cb)(dictionary_elem_t *delem, void *privdata),
415 * Recursively destroys all nodes in a dictionary tree.
418 * - dictionary tree object
419 * - optional iteration callback
420 * - optional opaque/private data to pass to callback
426 * - on success, a dtree and optionally it's children are destroyed.
429 * - if this is called without a callback, the objects bound to the
430 * DTree will not be destroyed.
432 void rb_dictionary_destroy(rb_dictionary
*dtree
,
433 void (*destroy_cb
)(rb_dictionary_element
*delem
, void *privdata
),
436 rb_dictionary_element
*n
, *tn
;
438 lrb_assert(dtree
!= NULL
);
440 RB_DLINK_FOREACH_SAFE(n
, tn
, dtree
->head
)
442 if (destroy_cb
!= NULL
)
443 (*destroy_cb
)(n
, privdata
);
448 rb_dlinkDelete(&dtree
->node
, &dictionary_list
);
454 * rb_dictionary_foreach(rb_dictionary *dtree,
455 * void (*destroy_cb)(dictionary_elem_t *delem, void *privdata),
458 * Iterates over all entries in a DTree.
461 * - dictionary tree object
462 * - optional iteration callback
463 * - optional opaque/private data to pass to callback
469 * - on success, a dtree is iterated
471 void rb_dictionary_foreach(rb_dictionary
*dtree
,
472 int (*foreach_cb
)(rb_dictionary_element
*delem
, void *privdata
),
475 rb_dictionary_element
*n
, *tn
;
477 lrb_assert(dtree
!= NULL
);
479 RB_DLINK_FOREACH_SAFE(n
, tn
, dtree
->head
)
481 /* delem_t is a subclass of node_t. */
482 rb_dictionary_element
*delem
= (rb_dictionary_element
*) n
;
484 if (foreach_cb
!= NULL
)
485 (*foreach_cb
)(delem
, privdata
);
490 * rb_dictionary_search(rb_dictionary *dtree,
491 * void (*destroy_cb)(rb_dictionary_element *delem, void *privdata),
494 * Searches all entries in a DTree using a custom callback.
497 * - dictionary tree object
498 * - optional iteration callback
499 * - optional opaque/private data to pass to callback
502 * - on success, the requested object
503 * - on failure, NULL.
506 * - a dtree is iterated until the requested conditions are met
508 void *rb_dictionary_search(rb_dictionary
*dtree
,
509 void *(*foreach_cb
)(rb_dictionary_element
*delem
, void *privdata
),
512 rb_dictionary_element
*n
, *tn
;
515 lrb_assert(dtree
!= NULL
);
517 RB_DLINK_FOREACH_SAFE(n
, tn
, dtree
->head
)
519 /* delem_t is a subclass of node_t. */
520 rb_dictionary_element
*delem
= (rb_dictionary_element
*) n
;
522 if (foreach_cb
!= NULL
)
523 ret
= (*foreach_cb
)(delem
, privdata
);
533 * rb_dictionary_foreach_start(rb_dictionary *dtree,
534 * rb_dictionary_iter *state);
536 * Initializes a static DTree iterator.
539 * - dictionary tree object
540 * - static DTree iterator
546 * - the static iterator, &state, is initialized.
548 void rb_dictionary_foreach_start(rb_dictionary
*dtree
,
549 rb_dictionary_iter
*state
)
551 lrb_assert(dtree
!= NULL
);
552 lrb_assert(state
!= NULL
);
557 /* find first item */
558 state
->cur
= dtree
->head
;
560 if (state
->cur
== NULL
)
563 /* make state->cur point to first item and state->next point to
565 state
->next
= state
->cur
;
566 rb_dictionary_foreach_next(dtree
, state
);
570 * rb_dictionary_foreach_cur(rb_dictionary *dtree,
571 * rb_dictionary_iter *state);
573 * Returns the data from the current node being iterated by the
577 * - dictionary tree object
578 * - static DTree iterator
581 * - reference to data in the current dtree node being iterated
586 void *rb_dictionary_foreach_cur(rb_dictionary
*dtree
,
587 rb_dictionary_iter
*state
)
589 lrb_assert(dtree
!= NULL
);
590 lrb_assert(state
!= NULL
);
592 return state
->cur
!= NULL
? state
->cur
->data
: NULL
;
596 * rb_dictionary_foreach_next(rb_dictionary *dtree,
597 * rb_dictionary_iter *state);
599 * Advances a static DTree iterator.
602 * - dictionary tree object
603 * - static DTree iterator
609 * - the static iterator, &state, is advanced to a new DTree node.
611 void rb_dictionary_foreach_next(rb_dictionary
*dtree
,
612 rb_dictionary_iter
*state
)
614 lrb_assert(dtree
!= NULL
);
615 lrb_assert(state
!= NULL
);
617 if (state
->cur
== NULL
)
619 rb_lib_log("rb_dictionary_foreach_next(): called again after iteration finished on dtree<%p>", (void *)dtree
);
623 state
->cur
= state
->next
;
625 if (state
->next
== NULL
)
628 state
->next
= state
->next
->next
;
632 * rb_dictionary_find(rb_dictionary *dtree, const void *key)
634 * Looks up a DTree node by name.
637 * - dictionary tree object
638 * - name of node to lookup
641 * - on success, the dtree node requested
647 rb_dictionary_element
*rb_dictionary_find(rb_dictionary
*dict
, const void *key
)
649 lrb_assert(dict
!= NULL
);
651 /* retune for key, key will be the tree's root if it's available */
652 rb_dictionary_retune(dict
, key
);
654 if (dict
->root
&& !dict
->compare_cb(key
, dict
->root
->key
))
661 * rb_dictionary_add(rb_dictionary *dtree, const void *key, void *data)
663 * Creates a new DTree node and binds data to it.
666 * - dictionary tree object
667 * - name for new DTree node
668 * - data to bind to the new DTree node
671 * - on success, a new DTree node
675 * - data is inserted into the DTree.
677 rb_dictionary_element
*rb_dictionary_add(rb_dictionary
*dict
, const void *key
, void *data
)
679 rb_dictionary_element
*delem
;
681 lrb_assert(dict
!= NULL
);
682 lrb_assert(data
!= NULL
);
683 lrb_assert(rb_dictionary_find(dict
, key
) == NULL
);
685 delem
= rb_malloc(sizeof(*delem
));
689 rb_dictionary_link(dict
, delem
);
695 * rb_dictionary_delete(rb_dictionary *dtree, const void *key)
697 * Deletes data from a dictionary tree.
700 * - dictionary tree object
701 * - name of DTree node to delete
704 * - on success, the remaining data that needs to be rb_freed
708 * - data is removed from the DTree.
711 * - the returned data needs to be rb_freed/released manually!
713 void *rb_dictionary_delete(rb_dictionary
*dtree
, const void *key
)
715 rb_dictionary_element
*delem
= rb_dictionary_find(dtree
, key
);
723 rb_dictionary_unlink_root(dtree
);
730 * rb_dictionary_retrieve(rb_dictionary *dtree, const void *key)
732 * Retrieves data from a dictionary.
735 * - dictionary tree object
736 * - name of node to lookup
739 * - on success, the data bound to the DTree node.
745 void *rb_dictionary_retrieve(rb_dictionary
*dtree
, const void *key
)
747 rb_dictionary_element
*delem
= rb_dictionary_find(dtree
, key
);
756 * rb_dictionary_size(rb_dictionary *dict)
758 * Returns the size of a dictionary.
761 * - dictionary tree object
764 * - size of dictionary
769 unsigned int rb_dictionary_size(rb_dictionary
*dict
)
771 lrb_assert(dict
!= NULL
);
776 /* returns the sum of the depths of the subtree rooted in delem at depth depth */
778 stats_recurse(rb_dictionary_element
*delem
, int depth
, int *pmaxdepth
)
782 if (depth
> *pmaxdepth
)
785 if (delem
&& delem
->left
)
786 result
+= stats_recurse(delem
->left
, depth
+ 1, pmaxdepth
);
787 if (delem
&& delem
->right
)
788 result
+= stats_recurse(delem
->right
, depth
+ 1, pmaxdepth
);
793 * rb_dictionary_stats(rb_dictionary *dict, void (*cb)(const char *line, void *privdata), void *privdata)
795 * Returns the size of a dictionary.
798 * - dictionary tree object
800 * - data for callback
806 * - callback called with stats text
808 void rb_dictionary_stats(rb_dictionary
*dict
, void (*cb
)(const char *line
, void *privdata
), void *privdata
)
813 lrb_assert(dict
!= NULL
);
818 sum
= stats_recurse(dict
->root
, 0, &maxdepth
);
819 snprintf(str
, sizeof str
, "%-30s %-15s %-10u %-10d %-10d %-10d", dict
->id
, "DICT", dict
->count
, sum
, sum
/ dict
->count
, maxdepth
);
823 snprintf(str
, sizeof str
, "%-30s %-15s %-10s %-10s %-10s %-10s", dict
->id
, "DICT", "0", "0", "0", "0");
829 void rb_dictionary_stats_walk(void (*cb
)(const char *line
, void *privdata
), void *privdata
)
833 RB_DLINK_FOREACH(ptr
, dictionary_list
.head
)
835 rb_dictionary_stats(ptr
->data
, cb
, privdata
);