2 * Solanum: a slightly 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
275 static rb_dictionary_element
*
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
;
345 * rb_dictionary_unlink_root(rb_dictionary *dict)
347 * Unlinks the root dictionary tree element from the dictionary.
356 * - the root node is unlinked from the dictionary tree
359 rb_dictionary_unlink_root(rb_dictionary
*dict
)
361 rb_dictionary_element
*delem
, *nextnode
, *parentofnext
;
369 if (dict
->root
->left
== NULL
)
370 dict
->root
= dict
->root
->right
;
371 else if (dict
->root
->right
== NULL
)
372 dict
->root
= dict
->root
->left
;
375 /* Make the node with the next highest key the new root.
376 * This node has a NULL left pointer. */
377 nextnode
= delem
->next
;
378 lrb_assert(nextnode
->left
== NULL
);
379 if (nextnode
== delem
->right
)
381 dict
->root
= nextnode
;
382 dict
->root
->left
= delem
->left
;
386 parentofnext
= delem
->right
;
387 while (parentofnext
->left
!= NULL
&& parentofnext
->left
!= nextnode
)
388 parentofnext
= parentofnext
->left
;
389 lrb_assert(parentofnext
->left
== nextnode
);
390 parentofnext
->left
= nextnode
->right
;
391 dict
->root
= nextnode
;
392 dict
->root
->left
= delem
->left
;
393 dict
->root
->right
= delem
->right
;
398 if (delem
->prev
!= NULL
)
399 delem
->prev
->next
= delem
->next
;
401 if (dict
->head
== delem
)
402 dict
->head
= delem
->next
;
405 delem
->next
->prev
= delem
->prev
;
407 if (dict
->tail
== delem
)
408 dict
->tail
= delem
->prev
;
414 * rb_dictionary_destroy(rb_dictionary *dtree,
415 * void (*destroy_cb)(dictionary_elem_t *delem, void *privdata),
418 * Recursively destroys all nodes in a dictionary tree.
421 * - dictionary tree object
422 * - optional iteration callback
423 * - optional opaque/private data to pass to callback
429 * - on success, a dtree and optionally it's children are destroyed.
432 * - if this is called without a callback, the objects bound to the
433 * DTree will not be destroyed.
435 void rb_dictionary_destroy(rb_dictionary
*dtree
,
436 void (*destroy_cb
)(rb_dictionary_element
*delem
, void *privdata
),
439 rb_dictionary_element
*n
, *tn
;
441 lrb_assert(dtree
!= NULL
);
443 RB_DLINK_FOREACH_SAFE(n
, tn
, dtree
->head
)
445 if (destroy_cb
!= NULL
)
446 (*destroy_cb
)(n
, privdata
);
451 rb_dlinkDelete(&dtree
->node
, &dictionary_list
);
457 * rb_dictionary_foreach(rb_dictionary *dtree,
458 * void (*destroy_cb)(dictionary_elem_t *delem, void *privdata),
461 * Iterates over all entries in a DTree.
464 * - dictionary tree object
465 * - optional iteration callback
466 * - optional opaque/private data to pass to callback
472 * - on success, a dtree is iterated
474 void rb_dictionary_foreach(rb_dictionary
*dtree
,
475 int (*foreach_cb
)(rb_dictionary_element
*delem
, void *privdata
),
478 rb_dictionary_element
*n
, *tn
;
480 lrb_assert(dtree
!= NULL
);
482 RB_DLINK_FOREACH_SAFE(n
, tn
, dtree
->head
)
484 /* delem_t is a subclass of node_t. */
485 rb_dictionary_element
*delem
= (rb_dictionary_element
*) n
;
487 if (foreach_cb
!= NULL
)
488 (*foreach_cb
)(delem
, privdata
);
493 * rb_dictionary_search(rb_dictionary *dtree,
494 * void (*destroy_cb)(rb_dictionary_element *delem, void *privdata),
497 * Searches all entries in a DTree using a custom callback.
500 * - dictionary tree object
501 * - optional iteration callback
502 * - optional opaque/private data to pass to callback
505 * - on success, the requested object
506 * - on failure, NULL.
509 * - a dtree is iterated until the requested conditions are met
511 void *rb_dictionary_search(rb_dictionary
*dtree
,
512 void *(*foreach_cb
)(rb_dictionary_element
*delem
, void *privdata
),
515 rb_dictionary_element
*n
, *tn
;
518 lrb_assert(dtree
!= NULL
);
520 RB_DLINK_FOREACH_SAFE(n
, tn
, dtree
->head
)
522 /* delem_t is a subclass of node_t. */
523 rb_dictionary_element
*delem
= (rb_dictionary_element
*) n
;
525 if (foreach_cb
!= NULL
)
526 ret
= (*foreach_cb
)(delem
, privdata
);
536 * rb_dictionary_foreach_start(rb_dictionary *dtree,
537 * rb_dictionary_iter *state);
539 * Initializes a static DTree iterator.
542 * - dictionary tree object
543 * - static DTree iterator
549 * - the static iterator, &state, is initialized.
551 void rb_dictionary_foreach_start(rb_dictionary
*dtree
,
552 rb_dictionary_iter
*state
)
554 lrb_assert(dtree
!= NULL
);
555 lrb_assert(state
!= NULL
);
560 /* find first item */
561 state
->cur
= dtree
->head
;
563 if (state
->cur
== NULL
)
566 /* make state->cur point to first item and state->next point to
568 state
->next
= state
->cur
;
569 rb_dictionary_foreach_next(dtree
, state
);
573 * rb_dictionary_foreach_cur(rb_dictionary *dtree,
574 * rb_dictionary_iter *state);
576 * Returns the data from the current node being iterated by the
580 * - dictionary tree object
581 * - static DTree iterator
584 * - reference to data in the current dtree node being iterated
589 void *rb_dictionary_foreach_cur(rb_dictionary
*dtree
__attribute__((unused
)),
590 rb_dictionary_iter
*state
)
592 lrb_assert(dtree
!= NULL
);
593 lrb_assert(state
!= NULL
);
595 return state
->cur
!= NULL
? state
->cur
->data
: NULL
;
599 * rb_dictionary_foreach_next(rb_dictionary *dtree,
600 * rb_dictionary_iter *state);
602 * Advances a static DTree iterator.
605 * - dictionary tree object
606 * - static DTree iterator
612 * - the static iterator, &state, is advanced to a new DTree node.
614 void rb_dictionary_foreach_next(rb_dictionary
*dtree
,
615 rb_dictionary_iter
*state
)
617 lrb_assert(dtree
!= NULL
);
618 lrb_assert(state
!= NULL
);
620 if (state
->cur
== NULL
)
622 rb_lib_log("rb_dictionary_foreach_next(): called again after iteration finished on dtree<%p>", (void *)dtree
);
626 state
->cur
= state
->next
;
628 if (state
->next
== NULL
)
631 state
->next
= state
->next
->next
;
635 * rb_dictionary_find(rb_dictionary *dtree, const void *key)
637 * Looks up a DTree node by name.
640 * - dictionary tree object
641 * - name of node to lookup
644 * - on success, the dtree node requested
650 rb_dictionary_element
*rb_dictionary_find(rb_dictionary
*dict
, const void *key
)
652 lrb_assert(dict
!= NULL
);
654 /* retune for key, key will be the tree's root if it's available */
655 rb_dictionary_retune(dict
, key
);
657 if (dict
->root
&& !dict
->compare_cb(key
, dict
->root
->key
))
664 * rb_dictionary_add(rb_dictionary *dtree, const void *key, void *data)
666 * Creates a new DTree node and binds data to it.
669 * - dictionary tree object
670 * - name for new DTree node
671 * - data to bind to the new DTree node
674 * - on success, a new DTree node
678 * - data is inserted into the DTree.
680 rb_dictionary_element
*rb_dictionary_add(rb_dictionary
*dict
, const void *key
, void *data
)
682 rb_dictionary_element
*delem
;
684 lrb_assert(dict
!= NULL
);
685 lrb_assert(data
!= NULL
);
686 lrb_assert(rb_dictionary_find(dict
, key
) == NULL
);
688 delem
= rb_malloc(sizeof(*delem
));
692 return rb_dictionary_link(dict
, delem
);
696 * rb_dictionary_delete(rb_dictionary *dtree, const void *key)
698 * Deletes data from a dictionary tree.
701 * - dictionary tree object
702 * - name of DTree node to delete
705 * - on success, the remaining data that needs to be rb_freed
709 * - data is removed from the DTree.
712 * - the returned data needs to be rb_freed/released manually!
714 void *rb_dictionary_delete(rb_dictionary
*dtree
, const void *key
)
716 rb_dictionary_element
*delem
= rb_dictionary_find(dtree
, key
);
724 rb_dictionary_unlink_root(dtree
);
731 * rb_dictionary_retrieve(rb_dictionary *dtree, const void *key)
733 * Retrieves data from a dictionary.
736 * - dictionary tree object
737 * - name of node to lookup
740 * - on success, the data bound to the DTree node.
746 void *rb_dictionary_retrieve(rb_dictionary
*dtree
, const void *key
)
748 rb_dictionary_element
*delem
= rb_dictionary_find(dtree
, key
);
757 * rb_dictionary_size(rb_dictionary *dict)
759 * Returns the size of a dictionary.
762 * - dictionary tree object
765 * - size of dictionary
770 unsigned int rb_dictionary_size(rb_dictionary
*dict
)
772 lrb_assert(dict
!= NULL
);
777 /* returns the sum of the depths of the subtree rooted in delem at depth depth */
779 stats_recurse(rb_dictionary_element
*delem
, int depth
, int *pmaxdepth
)
783 if (depth
> *pmaxdepth
)
786 if (delem
&& delem
->left
)
787 result
+= stats_recurse(delem
->left
, depth
+ 1, pmaxdepth
);
788 if (delem
&& delem
->right
)
789 result
+= stats_recurse(delem
->right
, depth
+ 1, pmaxdepth
);
794 * rb_dictionary_stats(rb_dictionary *dict, void (*cb)(const char *line, void *privdata), void *privdata)
796 * Returns the size of a dictionary.
799 * - dictionary tree object
801 * - data for callback
807 * - callback called with stats text
809 void rb_dictionary_stats(rb_dictionary
*dict
, void (*cb
)(const char *line
, void *privdata
), void *privdata
)
814 lrb_assert(dict
!= NULL
);
819 sum
= stats_recurse(dict
->root
, 0, &maxdepth
);
820 snprintf(str
, sizeof str
, "%-30s %-15s %-10u %-10d %-10d %-10d", dict
->id
, "DICT", dict
->count
, sum
, sum
/ dict
->count
, maxdepth
);
824 snprintf(str
, sizeof str
, "%-30s %-15s %-10s %-10s %-10s %-10s", dict
->id
, "DICT", "0", "0", "0", "0");
830 void rb_dictionary_stats_walk(void (*cb
)(const char *line
, void *privdata
), void *privdata
)
834 RB_DLINK_FOREACH(ptr
, dictionary_list
.head
)
836 rb_dictionary_stats(ptr
->data
, cb
, privdata
);