]>
jfr.im git - solanum.git/blob - src/irc_dictionary.c
2 * charybdis: an advanced ircd
3 * irc_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.
29 #include "irc_dictionary.h"
33 static rb_bh
*elem_heap
= NULL
;
38 struct DictionaryElement
*root
, *head
, *tail
;
45 * irc_dictionary_create(DCF compare_cb)
47 * Dictionary object factory.
50 * - function to use for comparing two entries in the dtree
53 * - on success, a new dictionary object.
56 * - if services runs out of memory and cannot allocate the object,
57 * the program will abort.
59 struct Dictionary
*irc_dictionary_create(DCF compare_cb
)
61 struct Dictionary
*dtree
= (struct Dictionary
*) rb_malloc(sizeof(struct Dictionary
));
63 dtree
->compare_cb
= compare_cb
;
66 elem_heap
= rb_bh_create(sizeof(struct DictionaryElement
), 1024, "dictionary_elem_heap");
72 * irc_dictionary_create_named(const char *name,
75 * Dictionary object factory.
79 * - function to use for comparing two entries in the dtree
82 * - on success, a new dictionary object.
85 * - if services runs out of memory and cannot allocate the object,
86 * the program will abort.
88 struct Dictionary
*irc_dictionary_create_named(const char *name
,
91 struct Dictionary
*dtree
= (struct Dictionary
*) rb_malloc(sizeof(struct Dictionary
));
93 dtree
->compare_cb
= compare_cb
;
94 dtree
->id
= rb_strdup(name
);
97 elem_heap
= rb_bh_create(sizeof(struct DictionaryElement
), 1024, "dictionary_elem_heap");
103 * irc_dictionary_set_comparator_func(struct Dictionary *dict,
106 * Resets the comparator function used by the dictionary code for
107 * updating the DTree structure.
110 * - dictionary object
111 * - new comparator function (passed as functor)
117 * - the dictionary comparator function is reset.
119 void irc_dictionary_set_comparator_func(struct Dictionary
*dict
,
122 s_assert(dict
!= NULL
);
123 s_assert(compare_cb
!= NULL
);
125 dict
->compare_cb
= compare_cb
;
129 * irc_dictionary_get_comparator_func(struct Dictionary *dict)
131 * Returns the current comparator function used by the dictionary.
134 * - dictionary object
137 * - comparator function (returned as functor)
143 irc_dictionary_get_comparator_func(struct Dictionary
*dict
)
145 s_assert(dict
!= NULL
);
147 return dict
->compare_cb
;
151 * irc_dictionary_get_linear_index(struct Dictionary *dict,
154 * Gets a linear index number for key.
157 * - dictionary tree object
161 * - position, from zero.
164 * - rebuilds the linear index if the tree is marked as dirty.
167 irc_dictionary_get_linear_index(struct Dictionary
*dict
, const char *key
)
169 struct DictionaryElement
*elem
;
171 s_assert(dict
!= NULL
);
172 s_assert(key
!= NULL
);
174 elem
= irc_dictionary_find(dict
, key
);
179 return elem
->position
;
182 struct DictionaryElement
*delem
;
185 for (delem
= dict
->head
, i
= 0; delem
!= NULL
; delem
= delem
->next
, i
++)
191 return elem
->position
;
195 * irc_dictionary_retune(struct Dictionary *dict, const char *key)
197 * Retunes the tree, self-optimizing for the element which belongs to key.
200 * - node to begin search from
206 * - a new root node is nominated.
209 irc_dictionary_retune(struct Dictionary
*dict
, const char *key
)
211 struct DictionaryElement n
, *tn
, *left
, *right
, *node
;
214 s_assert(dict
!= NULL
);
216 if (dict
->root
== NULL
)
220 * we initialize n with known values, since it's on stack
221 * memory. otherwise the dict would become corrupted.
223 * n is used for temporary storage while the tree is retuned.
226 n
.left
= n
.right
= NULL
;
229 /* this for(;;) loop is the main workhorse of the rebalancing */
230 for (node
= dict
->root
; ; )
232 if ((ret
= dict
->compare_cb(key
, node
->key
)) == 0)
237 if (node
->left
== NULL
)
240 if ((ret
= dict
->compare_cb(key
, node
->left
->key
)) < 0)
243 node
->left
= tn
->right
;
247 if (node
->left
== NULL
)
257 if (node
->right
== NULL
)
260 if ((ret
= dict
->compare_cb(key
, node
->right
->key
)) > 0)
263 node
->right
= tn
->left
;
267 if (node
->right
== NULL
)
277 left
->right
= node
->left
;
278 right
->left
= node
->right
;
280 node
->left
= n
.right
;
281 node
->right
= n
.left
;
287 * irc_dictionary_link(struct Dictionary *dict,
288 * struct DictionaryElement *delem)
290 * Links a dictionary tree element to the dictionary.
292 * When we add new nodes to the tree, it becomes the
293 * next nominated root. This is perhaps not a wise
294 * optimization because of automatic retuning, but
295 * it keeps the code simple.
299 * - dictionary tree element
305 * - a node is linked to the dictionary tree
308 irc_dictionary_link(struct Dictionary
*dict
,
309 struct DictionaryElement
*delem
)
311 s_assert(dict
!= NULL
);
312 s_assert(delem
!= NULL
);
318 if (dict
->root
== NULL
)
320 delem
->left
= delem
->right
= NULL
;
321 delem
->next
= delem
->prev
= NULL
;
322 dict
->head
= dict
->tail
= dict
->root
= delem
;
328 irc_dictionary_retune(dict
, delem
->key
);
330 if ((ret
= dict
->compare_cb(delem
->key
, dict
->root
->key
)) < 0)
332 delem
->left
= dict
->root
->left
;
333 delem
->right
= dict
->root
;
334 dict
->root
->left
= NULL
;
336 if (dict
->root
->prev
)
337 dict
->root
->prev
->next
= delem
;
341 delem
->prev
= dict
->root
->prev
;
342 delem
->next
= dict
->root
;
343 dict
->root
->prev
= delem
;
348 delem
->right
= dict
->root
->right
;
349 delem
->left
= dict
->root
;
350 dict
->root
->right
= NULL
;
352 if (dict
->root
->next
)
353 dict
->root
->next
->prev
= delem
;
357 delem
->next
= dict
->root
->next
;
358 delem
->prev
= dict
->root
;
359 dict
->root
->next
= delem
;
364 dict
->root
->key
= delem
->key
;
365 dict
->root
->data
= delem
->data
;
368 rb_bh_free(elem_heap
, delem
);
374 * irc_dictionary_unlink_root(struct Dictionary *dict)
376 * Unlinks the root dictionary tree element from the dictionary.
385 * - the root node is unlinked from the dictionary tree
388 irc_dictionary_unlink_root(struct Dictionary
*dict
)
390 struct DictionaryElement
*delem
, *nextnode
, *parentofnext
;
398 if (dict
->root
->left
== NULL
)
399 dict
->root
= dict
->root
->right
;
400 else if (dict
->root
->right
== NULL
)
401 dict
->root
= dict
->root
->left
;
404 /* Make the node with the next highest key the new root.
405 * This node has a NULL left pointer. */
406 nextnode
= delem
->next
;
407 s_assert(nextnode
->left
== NULL
);
408 if (nextnode
== delem
->right
)
410 dict
->root
= nextnode
;
411 dict
->root
->left
= delem
->left
;
415 parentofnext
= delem
->right
;
416 while (parentofnext
->left
!= NULL
&& parentofnext
->left
!= nextnode
)
417 parentofnext
= parentofnext
->left
;
418 s_assert(parentofnext
->left
== nextnode
);
419 parentofnext
->left
= nextnode
->right
;
420 dict
->root
= nextnode
;
421 dict
->root
->left
= delem
->left
;
422 dict
->root
->right
= delem
->right
;
427 if (delem
->prev
!= NULL
)
428 delem
->prev
->next
= delem
->next
;
430 if (dict
->head
== delem
)
431 dict
->head
= delem
->next
;
434 delem
->next
->prev
= delem
->prev
;
436 if (dict
->tail
== delem
)
437 dict
->tail
= delem
->prev
;
443 * irc_dictionary_destroy(struct Dictionary *dtree,
444 * void (*destroy_cb)(dictionary_elem_t *delem, void *privdata),
447 * Recursively destroys all nodes in a dictionary tree.
450 * - dictionary tree object
451 * - optional iteration callback
452 * - optional opaque/private data to pass to callback
458 * - on success, a dtree and optionally it's children are destroyed.
461 * - if this is called without a callback, the objects bound to the
462 * DTree will not be destroyed.
464 void irc_dictionary_destroy(struct Dictionary
*dtree
,
465 void (*destroy_cb
)(struct DictionaryElement
*delem
, void *privdata
),
468 struct DictionaryElement
*n
, *tn
;
470 s_assert(dtree
!= NULL
);
472 RB_DLINK_FOREACH_SAFE(n
, tn
, dtree
->head
)
474 if (destroy_cb
!= NULL
)
475 (*destroy_cb
)(n
, privdata
);
477 rb_bh_free(elem_heap
, n
);
484 * irc_dictionary_foreach(struct Dictionary *dtree,
485 * void (*destroy_cb)(dictionary_elem_t *delem, void *privdata),
488 * Iterates over all entries in a DTree.
491 * - dictionary tree object
492 * - optional iteration callback
493 * - optional opaque/private data to pass to callback
499 * - on success, a dtree is iterated
501 void irc_dictionary_foreach(struct Dictionary
*dtree
,
502 int (*foreach_cb
)(struct DictionaryElement
*delem
, void *privdata
),
505 struct DictionaryElement
*n
, *tn
;
507 s_assert(dtree
!= NULL
);
509 RB_DLINK_FOREACH_SAFE(n
, tn
, dtree
->head
)
511 /* delem_t is a subclass of node_t. */
512 struct DictionaryElement
*delem
= (struct DictionaryElement
*) n
;
514 if (foreach_cb
!= NULL
)
515 (*foreach_cb
)(delem
, privdata
);
520 * irc_dictionary_search(struct Dictionary *dtree,
521 * void (*destroy_cb)(struct DictionaryElement *delem, void *privdata),
524 * Searches all entries in a DTree using a custom callback.
527 * - dictionary tree object
528 * - optional iteration callback
529 * - optional opaque/private data to pass to callback
532 * - on success, the requested object
533 * - on failure, NULL.
536 * - a dtree is iterated until the requested conditions are met
538 void *irc_dictionary_search(struct Dictionary
*dtree
,
539 void *(*foreach_cb
)(struct DictionaryElement
*delem
, void *privdata
),
542 struct DictionaryElement
*n
, *tn
;
545 s_assert(dtree
!= NULL
);
547 RB_DLINK_FOREACH_SAFE(n
, tn
, dtree
->head
)
549 /* delem_t is a subclass of node_t. */
550 struct DictionaryElement
*delem
= (struct DictionaryElement
*) n
;
552 if (foreach_cb
!= NULL
)
553 ret
= (*foreach_cb
)(delem
, privdata
);
563 * irc_dictionary_foreach_start(struct Dictionary *dtree,
564 * struct DictionaryIter *state);
566 * Initializes a static DTree iterator.
569 * - dictionary tree object
570 * - static DTree iterator
576 * - the static iterator, &state, is initialized.
578 void irc_dictionary_foreach_start(struct Dictionary
*dtree
,
579 struct DictionaryIter
*state
)
581 s_assert(dtree
!= NULL
);
582 s_assert(state
!= NULL
);
587 /* find first item */
588 state
->cur
= dtree
->head
;
590 if (state
->cur
== NULL
)
593 /* make state->cur point to first item and state->next point to
595 state
->next
= state
->cur
;
596 irc_dictionary_foreach_next(dtree
, state
);
600 * irc_dictionary_foreach_cur(struct Dictionary *dtree,
601 * struct DictionaryIter *state);
603 * Returns the data from the current node being iterated by the
607 * - dictionary tree object
608 * - static DTree iterator
611 * - reference to data in the current dtree node being iterated
616 void *irc_dictionary_foreach_cur(struct Dictionary
*dtree
,
617 struct DictionaryIter
*state
)
619 s_assert(dtree
!= NULL
);
620 s_assert(state
!= NULL
);
622 return state
->cur
!= NULL
? state
->cur
->data
: NULL
;
626 * irc_dictionary_foreach_next(struct Dictionary *dtree,
627 * struct DictionaryIter *state);
629 * Advances a static DTree iterator.
632 * - dictionary tree object
633 * - static DTree iterator
639 * - the static iterator, &state, is advanced to a new DTree node.
641 void irc_dictionary_foreach_next(struct Dictionary
*dtree
,
642 struct DictionaryIter
*state
)
644 s_assert(dtree
!= NULL
);
645 s_assert(state
!= NULL
);
647 if (state
->cur
== NULL
)
649 ilog(L_MAIN
, "irc_dictionary_foreach_next(): called again after iteration finished on dtree<%p>", (void *)dtree
);
653 state
->cur
= state
->next
;
655 if (state
->next
== NULL
)
658 state
->next
= state
->next
->next
;
662 * irc_dictionary_find(struct Dictionary *dtree, const char *key)
664 * Looks up a DTree node by name.
667 * - dictionary tree object
668 * - name of node to lookup
671 * - on success, the dtree node requested
677 struct DictionaryElement
*irc_dictionary_find(struct Dictionary
*dict
, const char *key
)
679 s_assert(dict
!= NULL
);
680 s_assert(key
!= NULL
);
682 /* retune for key, key will be the tree's root if it's available */
683 irc_dictionary_retune(dict
, key
);
685 if (dict
->root
&& !dict
->compare_cb(key
, dict
->root
->key
))
692 * irc_dictionary_add(struct Dictionary *dtree, const char *key, void *data)
694 * Creates a new DTree node and binds data to it.
697 * - dictionary tree object
698 * - name for new DTree node
699 * - data to bind to the new DTree node
702 * - on success, a new DTree node
706 * - data is inserted into the DTree.
708 struct DictionaryElement
*irc_dictionary_add(struct Dictionary
*dict
, const char *key
, void *data
)
710 struct DictionaryElement
*delem
;
712 s_assert(dict
!= NULL
);
713 s_assert(key
!= NULL
);
714 s_assert(data
!= NULL
);
715 s_assert(irc_dictionary_find(dict
, key
) == NULL
);
717 delem
= rb_bh_alloc(elem_heap
);
721 /* TBD: is this needed? --nenolod */
722 if (delem
->key
== NULL
)
724 rb_bh_free(elem_heap
, delem
);
728 irc_dictionary_link(dict
, delem
);
734 * irc_dictionary_delete(struct Dictionary *dtree, const char *key)
736 * Deletes data from a dictionary tree.
739 * - dictionary tree object
740 * - name of DTree node to delete
743 * - on success, the remaining data that needs to be mowgli_freed
747 * - data is removed from the DTree.
750 * - the returned data needs to be mowgli_freed/released manually!
752 void *irc_dictionary_delete(struct Dictionary
*dtree
, const char *key
)
754 struct DictionaryElement
*delem
= irc_dictionary_find(dtree
, key
);
762 irc_dictionary_unlink_root(dtree
);
763 rb_bh_free(elem_heap
, delem
);
769 * irc_dictionary_retrieve(struct Dictionary *dtree, const char *key)
771 * Retrieves data from a dictionary.
774 * - dictionary tree object
775 * - name of node to lookup
778 * - on success, the data bound to the DTree node.
784 void *irc_dictionary_retrieve(struct Dictionary
*dtree
, const char *key
)
786 struct DictionaryElement
*delem
= irc_dictionary_find(dtree
, key
);
795 * irc_dictionary_size(struct Dictionary *dict)
797 * Returns the size of a dictionary.
800 * - dictionary tree object
803 * - size of dictionary
808 unsigned int irc_dictionary_size(struct Dictionary
*dict
)
810 s_assert(dict
!= NULL
);
815 /* returns the sum of the depths of the subtree rooted in delem at depth depth */
817 stats_recurse(struct DictionaryElement
*delem
, int depth
, int *pmaxdepth
)
821 if (depth
> *pmaxdepth
)
825 result
+= stats_recurse(delem
->left
, depth
+ 1, pmaxdepth
);
827 result
+= stats_recurse(delem
->right
, depth
+ 1, pmaxdepth
);
832 * irc_dictionary_stats(struct Dictionary *dict, void (*cb)(const char *line, void *privdata), void *privdata)
834 * Returns the size of a dictionary.
837 * - dictionary tree object
839 * - data for callback
845 * - callback called with stats text
847 void irc_dictionary_stats(struct Dictionary
*dict
, void (*cb
)(const char *line
, void *privdata
), void *privdata
)
852 s_assert(dict
!= NULL
);
854 if (dict
->id
!= NULL
)
855 rb_snprintf(str
, sizeof str
, "Dictionary stats for %s (%d)",
856 dict
->id
, dict
->count
);
858 rb_snprintf(str
, sizeof str
, "Dictionary stats for <%p> (%d)",
859 (void *)dict
, dict
->count
);
862 sum
= stats_recurse(dict
->root
, 0, &maxdepth
);
863 rb_snprintf(str
, sizeof str
, "Depth sum %d Avg depth %d Max depth %d", sum
, sum
/ dict
->count
, maxdepth
);