]>
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.
26 #include "sprintf_irc.h"
27 #include "irc_string.h"
30 #include "irc_dictionary.h"
32 static rb_bh
*elem_heap
= NULL
;
37 struct DictionaryElement
*root
, *head
, *tail
;
44 * irc_dictionary_create(DCF compare_cb)
46 * 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 struct Dictionary
*irc_dictionary_create(DCF compare_cb
)
60 struct Dictionary
*dtree
= (struct Dictionary
*) rb_malloc(sizeof(struct Dictionary
));
62 dtree
->compare_cb
= compare_cb
;
65 elem_heap
= rb_bh_create(sizeof(struct DictionaryElement
), 1024, "dictionary_elem_heap");
71 * irc_dictionary_create_named(const char *name,
74 * Dictionary object factory.
78 * - function to use for comparing two entries in the dtree
81 * - on success, a new dictionary object.
84 * - if services runs out of memory and cannot allocate the object,
85 * the program will abort.
87 struct Dictionary
*irc_dictionary_create_named(const char *name
,
90 struct Dictionary
*dtree
= (struct Dictionary
*) rb_malloc(sizeof(struct Dictionary
));
92 dtree
->compare_cb
= compare_cb
;
93 dtree
->id
= rb_strdup(name
);
96 elem_heap
= rb_bh_create(sizeof(struct DictionaryElement
), 1024, "dictionary_elem_heap");
102 * irc_dictionary_set_comparator_func(struct Dictionary *dict,
105 * Resets the comparator function used by the dictionary code for
106 * updating the DTree structure.
109 * - dictionary object
110 * - new comparator function (passed as functor)
116 * - the dictionary comparator function is reset.
118 void irc_dictionary_set_comparator_func(struct Dictionary
*dict
,
121 s_assert(dict
!= NULL
);
122 s_assert(compare_cb
!= NULL
);
124 dict
->compare_cb
= compare_cb
;
128 * irc_dictionary_get_comparator_func(struct Dictionary *dict)
130 * Returns the current comparator function used by the dictionary.
133 * - dictionary object
136 * - comparator function (returned as functor)
142 irc_dictionary_get_comparator_func(struct Dictionary
*dict
)
144 s_assert(dict
!= NULL
);
146 return dict
->compare_cb
;
150 * irc_dictionary_get_linear_index(struct Dictionary *dict,
153 * Gets a linear index number for key.
156 * - dictionary tree object
160 * - position, from zero.
163 * - rebuilds the linear index if the tree is marked as dirty.
166 irc_dictionary_get_linear_index(struct Dictionary
*dict
, const char *key
)
168 struct DictionaryElement
*elem
;
170 s_assert(dict
!= NULL
);
171 s_assert(key
!= NULL
);
173 elem
= irc_dictionary_find(dict
, key
);
178 return elem
->position
;
181 struct DictionaryElement
*delem
;
184 for (delem
= dict
->head
, i
= 0; delem
!= NULL
; delem
= delem
->next
, i
++)
190 return elem
->position
;
194 * irc_dictionary_retune(struct Dictionary *dict, const char *key)
196 * Retunes the tree, self-optimizing for the element which belongs to key.
199 * - node to begin search from
205 * - a new root node is nominated.
208 irc_dictionary_retune(struct Dictionary
*dict
, const char *key
)
210 struct DictionaryElement n
, *tn
, *left
, *right
, *node
;
213 s_assert(dict
!= NULL
);
215 if (dict
->root
== NULL
)
219 * we initialize n with known values, since it's on stack
220 * memory. otherwise the dict would become corrupted.
222 * n is used for temporary storage while the tree is retuned.
225 n
.left
= n
.right
= NULL
;
228 /* this for(;;) loop is the main workhorse of the rebalancing */
229 for (node
= dict
->root
; ; )
231 if ((ret
= dict
->compare_cb(key
, node
->key
)) == 0)
236 if (node
->left
== NULL
)
239 if ((ret
= dict
->compare_cb(key
, node
->left
->key
)) < 0)
242 node
->left
= tn
->right
;
246 if (node
->left
== NULL
)
256 if (node
->right
== NULL
)
259 if ((ret
= dict
->compare_cb(key
, node
->right
->key
)) > 0)
262 node
->right
= tn
->left
;
266 if (node
->right
== NULL
)
276 left
->right
= node
->left
;
277 right
->left
= node
->right
;
279 node
->left
= n
.right
;
280 node
->right
= n
.left
;
286 * irc_dictionary_link(struct Dictionary *dict,
287 * struct DictionaryElement *delem)
289 * Links a dictionary tree element to the dictionary.
291 * When we add new nodes to the tree, it becomes the
292 * next nominated root. This is perhaps not a wise
293 * optimization because of automatic retuning, but
294 * it keeps the code simple.
298 * - dictionary tree element
304 * - a node is linked to the dictionary tree
307 irc_dictionary_link(struct Dictionary
*dict
,
308 struct DictionaryElement
*delem
)
310 s_assert(dict
!= NULL
);
311 s_assert(delem
!= NULL
);
317 if (dict
->root
== NULL
)
319 delem
->left
= delem
->right
= NULL
;
320 delem
->next
= delem
->prev
= NULL
;
321 dict
->head
= dict
->tail
= dict
->root
= delem
;
327 irc_dictionary_retune(dict
, delem
->key
);
329 if ((ret
= dict
->compare_cb(delem
->key
, dict
->root
->key
)) < 0)
331 delem
->left
= dict
->root
->left
;
332 delem
->right
= dict
->root
;
333 dict
->root
->left
= NULL
;
335 if (dict
->root
->prev
)
336 dict
->root
->prev
->next
= delem
;
340 delem
->prev
= dict
->root
->prev
;
341 delem
->next
= dict
->root
;
342 dict
->root
->prev
= delem
;
347 delem
->right
= dict
->root
->right
;
348 delem
->left
= dict
->root
;
349 dict
->root
->right
= NULL
;
351 if (dict
->root
->next
)
352 dict
->root
->next
->prev
= delem
;
356 delem
->next
= dict
->root
->next
;
357 delem
->prev
= dict
->root
;
358 dict
->root
->next
= delem
;
363 dict
->root
->key
= delem
->key
;
364 dict
->root
->data
= delem
->data
;
367 rb_bh_free(elem_heap
, delem
);
373 * irc_dictionary_unlink_root(struct Dictionary *dict)
375 * Unlinks the root dictionary tree element from the dictionary.
384 * - the root node is unlinked from the dictionary tree
387 irc_dictionary_unlink_root(struct Dictionary
*dict
)
389 struct DictionaryElement
*delem
, *nextnode
, *parentofnext
;
397 if (dict
->root
->left
== NULL
)
398 dict
->root
= dict
->root
->right
;
399 else if (dict
->root
->right
== NULL
)
400 dict
->root
= dict
->root
->left
;
403 /* Make the node with the next highest key the new root.
404 * This node has a NULL left pointer. */
405 nextnode
= delem
->next
;
406 s_assert(nextnode
->left
== NULL
);
407 if (nextnode
== delem
->right
)
409 dict
->root
= nextnode
;
410 dict
->root
->left
= delem
->left
;
414 parentofnext
= delem
->right
;
415 while (parentofnext
->left
!= NULL
&& parentofnext
->left
!= nextnode
)
416 parentofnext
= parentofnext
->left
;
417 s_assert(parentofnext
->left
== nextnode
);
418 parentofnext
->left
= nextnode
->right
;
419 dict
->root
= nextnode
;
420 dict
->root
->left
= delem
->left
;
421 dict
->root
->right
= delem
->right
;
426 if (delem
->prev
!= NULL
)
427 delem
->prev
->next
= delem
->next
;
429 if (dict
->head
== delem
)
430 dict
->head
= delem
->next
;
433 delem
->next
->prev
= delem
->prev
;
435 if (dict
->tail
== delem
)
436 dict
->tail
= delem
->prev
;
442 * irc_dictionary_destroy(struct Dictionary *dtree,
443 * void (*destroy_cb)(dictionary_elem_t *delem, void *privdata),
446 * Recursively destroys all nodes in a dictionary tree.
449 * - dictionary tree object
450 * - optional iteration callback
451 * - optional opaque/private data to pass to callback
457 * - on success, a dtree and optionally it's children are destroyed.
460 * - if this is called without a callback, the objects bound to the
461 * DTree will not be destroyed.
463 void irc_dictionary_destroy(struct Dictionary
*dtree
,
464 void (*destroy_cb
)(struct DictionaryElement
*delem
, void *privdata
),
467 struct DictionaryElement
*n
, *tn
;
469 s_assert(dtree
!= NULL
);
471 RB_DLINK_FOREACH_SAFE(n
, tn
, dtree
->head
)
473 if (destroy_cb
!= NULL
)
474 (*destroy_cb
)(n
, privdata
);
476 rb_bh_free(elem_heap
, n
);
483 * irc_dictionary_foreach(struct Dictionary *dtree,
484 * void (*destroy_cb)(dictionary_elem_t *delem, void *privdata),
487 * Iterates over all entries in a DTree.
490 * - dictionary tree object
491 * - optional iteration callback
492 * - optional opaque/private data to pass to callback
498 * - on success, a dtree is iterated
500 void irc_dictionary_foreach(struct Dictionary
*dtree
,
501 int (*foreach_cb
)(struct DictionaryElement
*delem
, void *privdata
),
504 struct DictionaryElement
*n
, *tn
;
506 s_assert(dtree
!= NULL
);
508 RB_DLINK_FOREACH_SAFE(n
, tn
, dtree
->head
)
510 /* delem_t is a subclass of node_t. */
511 struct DictionaryElement
*delem
= (struct DictionaryElement
*) n
;
513 if (foreach_cb
!= NULL
)
514 (*foreach_cb
)(delem
, privdata
);
519 * irc_dictionary_search(struct Dictionary *dtree,
520 * void (*destroy_cb)(struct DictionaryElement *delem, void *privdata),
523 * Searches all entries in a DTree using a custom callback.
526 * - dictionary tree object
527 * - optional iteration callback
528 * - optional opaque/private data to pass to callback
531 * - on success, the requested object
532 * - on failure, NULL.
535 * - a dtree is iterated until the requested conditions are met
537 void *irc_dictionary_search(struct Dictionary
*dtree
,
538 void *(*foreach_cb
)(struct DictionaryElement
*delem
, void *privdata
),
541 struct DictionaryElement
*n
, *tn
;
544 s_assert(dtree
!= NULL
);
546 RB_DLINK_FOREACH_SAFE(n
, tn
, dtree
->head
)
548 /* delem_t is a subclass of node_t. */
549 struct DictionaryElement
*delem
= (struct DictionaryElement
*) n
;
551 if (foreach_cb
!= NULL
)
552 ret
= (*foreach_cb
)(delem
, privdata
);
562 * irc_dictionary_foreach_start(struct Dictionary *dtree,
563 * struct DictionaryIter *state);
565 * Initializes a static DTree iterator.
568 * - dictionary tree object
569 * - static DTree iterator
575 * - the static iterator, &state, is initialized.
577 void irc_dictionary_foreach_start(struct Dictionary
*dtree
,
578 struct DictionaryIter
*state
)
580 s_assert(dtree
!= NULL
);
581 s_assert(state
!= NULL
);
586 /* find first item */
587 state
->cur
= dtree
->head
;
589 if (state
->cur
== NULL
)
592 /* make state->cur point to first item and state->next point to
594 state
->next
= state
->cur
;
595 irc_dictionary_foreach_next(dtree
, state
);
599 * irc_dictionary_foreach_cur(struct Dictionary *dtree,
600 * struct DictionaryIter *state);
602 * Returns the data from the current node being iterated by the
606 * - dictionary tree object
607 * - static DTree iterator
610 * - reference to data in the current dtree node being iterated
615 void *irc_dictionary_foreach_cur(struct Dictionary
*dtree
,
616 struct DictionaryIter
*state
)
618 s_assert(dtree
!= NULL
);
619 s_assert(state
!= NULL
);
621 return state
->cur
!= NULL
? state
->cur
->data
: NULL
;
625 * irc_dictionary_foreach_next(struct Dictionary *dtree,
626 * struct DictionaryIter *state);
628 * Advances a static DTree iterator.
631 * - dictionary tree object
632 * - static DTree iterator
638 * - the static iterator, &state, is advanced to a new DTree node.
640 void irc_dictionary_foreach_next(struct Dictionary
*dtree
,
641 struct DictionaryIter
*state
)
643 s_assert(dtree
!= NULL
);
644 s_assert(state
!= NULL
);
646 if (state
->cur
== NULL
)
648 ilog(L_MAIN
, "irc_dictionary_foreach_next(): called again after iteration finished on dtree<%p>", dtree
);
652 state
->cur
= state
->next
;
654 if (state
->next
== NULL
)
657 state
->next
= state
->next
->next
;
661 * irc_dictionary_find(struct Dictionary *dtree, const char *key)
663 * Looks up a DTree node by name.
666 * - dictionary tree object
667 * - name of node to lookup
670 * - on success, the dtree node requested
676 struct DictionaryElement
*irc_dictionary_find(struct Dictionary
*dict
, const char *key
)
678 s_assert(dict
!= NULL
);
679 s_assert(key
!= NULL
);
681 /* retune for key, key will be the tree's root if it's available */
682 irc_dictionary_retune(dict
, key
);
684 if (dict
->root
&& !dict
->compare_cb(key
, dict
->root
->key
))
691 * irc_dictionary_add(struct Dictionary *dtree, const char *key, void *data)
693 * Creates a new DTree node and binds data to it.
696 * - dictionary tree object
697 * - name for new DTree node
698 * - data to bind to the new DTree node
701 * - on success, a new DTree node
705 * - data is inserted into the DTree.
707 struct DictionaryElement
*irc_dictionary_add(struct Dictionary
*dict
, char *key
, void *data
)
709 struct DictionaryElement
*delem
;
711 s_assert(dict
!= NULL
);
712 s_assert(key
!= NULL
);
713 s_assert(data
!= NULL
);
714 s_assert(irc_dictionary_find(dict
, key
) == NULL
);
716 delem
= rb_bh_alloc(elem_heap
);
720 /* TBD: is this needed? --nenolod */
721 if (delem
->key
== NULL
)
723 rb_bh_free(elem_heap
, delem
);
727 irc_dictionary_link(dict
, delem
);
733 * irc_dictionary_delete(struct Dictionary *dtree, const char *key)
735 * Deletes data from a dictionary tree.
738 * - dictionary tree object
739 * - name of DTree node to delete
742 * - on success, the remaining data that needs to be mowgli_freed
746 * - data is removed from the DTree.
749 * - the returned data needs to be mowgli_freed/released manually!
751 void *irc_dictionary_delete(struct Dictionary
*dtree
, const char *key
)
753 struct DictionaryElement
*delem
= irc_dictionary_find(dtree
, key
);
761 irc_dictionary_unlink_root(dtree
);
762 rb_bh_free(elem_heap
, delem
);
768 * irc_dictionary_retrieve(struct Dictionary *dtree, const char *key)
770 * Retrieves data from a dictionary.
773 * - dictionary tree object
774 * - name of node to lookup
777 * - on success, the data bound to the DTree node.
783 void *irc_dictionary_retrieve(struct Dictionary
*dtree
, const char *key
)
785 struct DictionaryElement
*delem
= irc_dictionary_find(dtree
, key
);
794 * irc_dictionary_size(struct Dictionary *dict)
796 * Returns the size of a dictionary.
799 * - dictionary tree object
802 * - size of dictionary
807 unsigned int irc_dictionary_size(struct Dictionary
*dict
)
809 s_assert(dict
!= NULL
);
814 /* returns the sum of the depths of the subtree rooted in delem at depth depth */
816 stats_recurse(struct DictionaryElement
*delem
, int depth
, int *pmaxdepth
)
820 if (depth
> *pmaxdepth
)
824 result
+= stats_recurse(delem
->left
, depth
+ 1, pmaxdepth
);
826 result
+= stats_recurse(delem
->right
, depth
+ 1, pmaxdepth
);
831 * irc_dictionary_stats(struct Dictionary *dict, void (*cb)(const char *line, void *privdata), void *privdata)
833 * Returns the size of a dictionary.
836 * - dictionary tree object
838 * - data for callback
844 * - callback called with stats text
846 void irc_dictionary_stats(struct Dictionary
*dict
, void (*cb
)(const char *line
, void *privdata
), void *privdata
)
851 s_assert(dict
!= NULL
);
853 if (dict
->id
!= NULL
)
854 snprintf(str
, sizeof str
, "Dictionary stats for %s (%d)",
855 dict
->id
, dict
->count
);
857 snprintf(str
, sizeof str
, "Dictionary stats for <%p> (%d)",
861 sum
= stats_recurse(dict
->root
, 0, &maxdepth
);
862 snprintf(str
, sizeof str
, "Depth sum %d Avg depth %d Max depth %d", sum
, sum
/ dict
->count
, maxdepth
);