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"
36 struct DictionaryElement
*root
, *head
, *tail
;
44 static rb_dlink_list dictionary_list
= {NULL
, NULL
, 0};
47 * irc_dictionary_create(const char *name, DCF compare_cb)
49 * Dictionary object factory.
53 * - function to use for comparing two entries in the dtree
56 * - on success, a new dictionary object.
59 * - if services runs out of memory and cannot allocate the object,
60 * the program will abort.
62 struct Dictionary
*irc_dictionary_create(const char *name
,
65 struct Dictionary
*dtree
= (struct Dictionary
*) rb_malloc(sizeof(struct Dictionary
));
67 dtree
->compare_cb
= compare_cb
;
68 dtree
->id
= rb_strdup(name
);
70 rb_dlinkAdd(dtree
, &dtree
->node
, &dictionary_list
);
76 * irc_dictionary_set_comparator_func(struct Dictionary *dict,
79 * Resets the comparator function used by the dictionary code for
80 * updating the DTree structure.
84 * - new comparator function (passed as functor)
90 * - the dictionary comparator function is reset.
92 void irc_dictionary_set_comparator_func(struct Dictionary
*dict
,
95 s_assert(dict
!= NULL
);
96 s_assert(compare_cb
!= NULL
);
98 dict
->compare_cb
= compare_cb
;
102 * irc_dictionary_get_comparator_func(struct Dictionary *dict)
104 * Returns the current comparator function used by the dictionary.
107 * - dictionary object
110 * - comparator function (returned as functor)
116 irc_dictionary_get_comparator_func(struct Dictionary
*dict
)
118 s_assert(dict
!= NULL
);
120 return dict
->compare_cb
;
124 * irc_dictionary_get_linear_index(struct Dictionary *dict,
127 * Gets a linear index number for key.
130 * - dictionary tree object
134 * - position, from zero.
137 * - rebuilds the linear index if the tree is marked as dirty.
140 irc_dictionary_get_linear_index(struct Dictionary
*dict
, const void *key
)
142 struct DictionaryElement
*elem
;
144 s_assert(dict
!= NULL
);
145 s_assert(key
!= NULL
);
147 elem
= irc_dictionary_find(dict
, key
);
152 return elem
->position
;
155 struct DictionaryElement
*delem
;
158 for (delem
= dict
->head
, i
= 0; delem
!= NULL
; delem
= delem
->next
, i
++)
164 return elem
->position
;
168 * irc_dictionary_retune(struct Dictionary *dict, const void *key)
170 * Retunes the tree, self-optimizing for the element which belongs to key.
173 * - node to begin search from
179 * - a new root node is nominated.
182 irc_dictionary_retune(struct Dictionary
*dict
, const void *key
)
184 struct DictionaryElement n
, *tn
, *left
, *right
, *node
;
187 s_assert(dict
!= NULL
);
189 if (dict
->root
== NULL
)
193 * we initialize n with known values, since it's on stack
194 * memory. otherwise the dict would become corrupted.
196 * n is used for temporary storage while the tree is retuned.
199 n
.left
= n
.right
= NULL
;
202 /* this for(;;) loop is the main workhorse of the rebalancing */
203 for (node
= dict
->root
; ; )
205 if ((ret
= dict
->compare_cb(key
, node
->key
)) == 0)
210 if (node
->left
== NULL
)
213 if ((ret
= dict
->compare_cb(key
, node
->left
->key
)) < 0)
216 node
->left
= tn
->right
;
220 if (node
->left
== NULL
)
230 if (node
->right
== NULL
)
233 if ((ret
= dict
->compare_cb(key
, node
->right
->key
)) > 0)
236 node
->right
= tn
->left
;
240 if (node
->right
== NULL
)
250 left
->right
= node
->left
;
251 right
->left
= node
->right
;
253 node
->left
= n
.right
;
254 node
->right
= n
.left
;
260 * irc_dictionary_link(struct Dictionary *dict,
261 * struct DictionaryElement *delem)
263 * Links a dictionary tree element to the dictionary.
265 * When we add new nodes to the tree, it becomes the
266 * next nominated root. This is perhaps not a wise
267 * optimization because of automatic retuning, but
268 * it keeps the code simple.
272 * - dictionary tree element
278 * - a node is linked to the dictionary tree
281 irc_dictionary_link(struct Dictionary
*dict
,
282 struct DictionaryElement
*delem
)
284 s_assert(dict
!= NULL
);
285 s_assert(delem
!= NULL
);
291 if (dict
->root
== NULL
)
293 delem
->left
= delem
->right
= NULL
;
294 delem
->next
= delem
->prev
= NULL
;
295 dict
->head
= dict
->tail
= dict
->root
= delem
;
301 irc_dictionary_retune(dict
, delem
->key
);
303 if ((ret
= dict
->compare_cb(delem
->key
, dict
->root
->key
)) < 0)
305 delem
->left
= dict
->root
->left
;
306 delem
->right
= dict
->root
;
307 dict
->root
->left
= NULL
;
309 if (dict
->root
->prev
)
310 dict
->root
->prev
->next
= delem
;
314 delem
->prev
= dict
->root
->prev
;
315 delem
->next
= dict
->root
;
316 dict
->root
->prev
= delem
;
321 delem
->right
= dict
->root
->right
;
322 delem
->left
= dict
->root
;
323 dict
->root
->right
= NULL
;
325 if (dict
->root
->next
)
326 dict
->root
->next
->prev
= delem
;
330 delem
->next
= dict
->root
->next
;
331 delem
->prev
= dict
->root
;
332 dict
->root
->next
= delem
;
337 dict
->root
->key
= delem
->key
;
338 dict
->root
->data
= delem
->data
;
347 * irc_dictionary_unlink_root(struct Dictionary *dict)
349 * Unlinks the root dictionary tree element from the dictionary.
358 * - the root node is unlinked from the dictionary tree
361 irc_dictionary_unlink_root(struct Dictionary
*dict
)
363 struct DictionaryElement
*delem
, *nextnode
, *parentofnext
;
371 if (dict
->root
->left
== NULL
)
372 dict
->root
= dict
->root
->right
;
373 else if (dict
->root
->right
== NULL
)
374 dict
->root
= dict
->root
->left
;
377 /* Make the node with the next highest key the new root.
378 * This node has a NULL left pointer. */
379 nextnode
= delem
->next
;
380 s_assert(nextnode
->left
== NULL
);
381 if (nextnode
== delem
->right
)
383 dict
->root
= nextnode
;
384 dict
->root
->left
= delem
->left
;
388 parentofnext
= delem
->right
;
389 while (parentofnext
->left
!= NULL
&& parentofnext
->left
!= nextnode
)
390 parentofnext
= parentofnext
->left
;
391 s_assert(parentofnext
->left
== nextnode
);
392 parentofnext
->left
= nextnode
->right
;
393 dict
->root
= nextnode
;
394 dict
->root
->left
= delem
->left
;
395 dict
->root
->right
= delem
->right
;
400 if (delem
->prev
!= NULL
)
401 delem
->prev
->next
= delem
->next
;
403 if (dict
->head
== delem
)
404 dict
->head
= delem
->next
;
407 delem
->next
->prev
= delem
->prev
;
409 if (dict
->tail
== delem
)
410 dict
->tail
= delem
->prev
;
416 * irc_dictionary_destroy(struct Dictionary *dtree,
417 * void (*destroy_cb)(dictionary_elem_t *delem, void *privdata),
420 * Recursively destroys all nodes in a dictionary tree.
423 * - dictionary tree object
424 * - optional iteration callback
425 * - optional opaque/private data to pass to callback
431 * - on success, a dtree and optionally it's children are destroyed.
434 * - if this is called without a callback, the objects bound to the
435 * DTree will not be destroyed.
437 void irc_dictionary_destroy(struct Dictionary
*dtree
,
438 void (*destroy_cb
)(struct DictionaryElement
*delem
, void *privdata
),
441 struct DictionaryElement
*n
, *tn
;
443 s_assert(dtree
!= NULL
);
445 RB_DLINK_FOREACH_SAFE(n
, tn
, dtree
->head
)
447 if (destroy_cb
!= NULL
)
448 (*destroy_cb
)(n
, privdata
);
453 rb_dlinkDelete(&dtree
->node
, &dictionary_list
);
459 * irc_dictionary_foreach(struct Dictionary *dtree,
460 * void (*destroy_cb)(dictionary_elem_t *delem, void *privdata),
463 * Iterates over all entries in a DTree.
466 * - dictionary tree object
467 * - optional iteration callback
468 * - optional opaque/private data to pass to callback
474 * - on success, a dtree is iterated
476 void irc_dictionary_foreach(struct Dictionary
*dtree
,
477 int (*foreach_cb
)(struct DictionaryElement
*delem
, void *privdata
),
480 struct DictionaryElement
*n
, *tn
;
482 s_assert(dtree
!= NULL
);
484 RB_DLINK_FOREACH_SAFE(n
, tn
, dtree
->head
)
486 /* delem_t is a subclass of node_t. */
487 struct DictionaryElement
*delem
= (struct DictionaryElement
*) n
;
489 if (foreach_cb
!= NULL
)
490 (*foreach_cb
)(delem
, privdata
);
495 * irc_dictionary_search(struct Dictionary *dtree,
496 * void (*destroy_cb)(struct DictionaryElement *delem, void *privdata),
499 * Searches all entries in a DTree using a custom callback.
502 * - dictionary tree object
503 * - optional iteration callback
504 * - optional opaque/private data to pass to callback
507 * - on success, the requested object
508 * - on failure, NULL.
511 * - a dtree is iterated until the requested conditions are met
513 void *irc_dictionary_search(struct Dictionary
*dtree
,
514 void *(*foreach_cb
)(struct DictionaryElement
*delem
, void *privdata
),
517 struct DictionaryElement
*n
, *tn
;
520 s_assert(dtree
!= NULL
);
522 RB_DLINK_FOREACH_SAFE(n
, tn
, dtree
->head
)
524 /* delem_t is a subclass of node_t. */
525 struct DictionaryElement
*delem
= (struct DictionaryElement
*) n
;
527 if (foreach_cb
!= NULL
)
528 ret
= (*foreach_cb
)(delem
, privdata
);
538 * irc_dictionary_foreach_start(struct Dictionary *dtree,
539 * struct DictionaryIter *state);
541 * Initializes a static DTree iterator.
544 * - dictionary tree object
545 * - static DTree iterator
551 * - the static iterator, &state, is initialized.
553 void irc_dictionary_foreach_start(struct Dictionary
*dtree
,
554 struct DictionaryIter
*state
)
556 s_assert(dtree
!= NULL
);
557 s_assert(state
!= NULL
);
562 /* find first item */
563 state
->cur
= dtree
->head
;
565 if (state
->cur
== NULL
)
568 /* make state->cur point to first item and state->next point to
570 state
->next
= state
->cur
;
571 irc_dictionary_foreach_next(dtree
, state
);
575 * irc_dictionary_foreach_cur(struct Dictionary *dtree,
576 * struct DictionaryIter *state);
578 * Returns the data from the current node being iterated by the
582 * - dictionary tree object
583 * - static DTree iterator
586 * - reference to data in the current dtree node being iterated
591 void *irc_dictionary_foreach_cur(struct Dictionary
*dtree
,
592 struct DictionaryIter
*state
)
594 s_assert(dtree
!= NULL
);
595 s_assert(state
!= NULL
);
597 return state
->cur
!= NULL
? state
->cur
->data
: NULL
;
601 * irc_dictionary_foreach_next(struct Dictionary *dtree,
602 * struct DictionaryIter *state);
604 * Advances a static DTree iterator.
607 * - dictionary tree object
608 * - static DTree iterator
614 * - the static iterator, &state, is advanced to a new DTree node.
616 void irc_dictionary_foreach_next(struct Dictionary
*dtree
,
617 struct DictionaryIter
*state
)
619 s_assert(dtree
!= NULL
);
620 s_assert(state
!= NULL
);
622 if (state
->cur
== NULL
)
624 ilog(L_MAIN
, "irc_dictionary_foreach_next(): called again after iteration finished on dtree<%p>", (void *)dtree
);
628 state
->cur
= state
->next
;
630 if (state
->next
== NULL
)
633 state
->next
= state
->next
->next
;
637 * irc_dictionary_find(struct Dictionary *dtree, const void *key)
639 * Looks up a DTree node by name.
642 * - dictionary tree object
643 * - name of node to lookup
646 * - on success, the dtree node requested
652 struct DictionaryElement
*irc_dictionary_find(struct Dictionary
*dict
, const void *key
)
654 s_assert(dict
!= NULL
);
655 s_assert(key
!= NULL
);
657 /* retune for key, key will be the tree's root if it's available */
658 irc_dictionary_retune(dict
, key
);
660 if (dict
->root
&& !dict
->compare_cb(key
, dict
->root
->key
))
667 * irc_dictionary_add(struct Dictionary *dtree, const void *key, void *data)
669 * Creates a new DTree node and binds data to it.
672 * - dictionary tree object
673 * - name for new DTree node
674 * - data to bind to the new DTree node
677 * - on success, a new DTree node
681 * - data is inserted into the DTree.
683 struct DictionaryElement
*irc_dictionary_add(struct Dictionary
*dict
, const void *key
, void *data
)
685 struct DictionaryElement
*delem
;
687 s_assert(dict
!= NULL
);
688 s_assert(key
!= NULL
);
689 s_assert(data
!= NULL
);
690 s_assert(irc_dictionary_find(dict
, key
) == NULL
);
692 delem
= rb_malloc(sizeof(*delem
));
696 irc_dictionary_link(dict
, delem
);
702 * irc_dictionary_delete(struct Dictionary *dtree, const void *key)
704 * Deletes data from a dictionary tree.
707 * - dictionary tree object
708 * - name of DTree node to delete
711 * - on success, the remaining data that needs to be mowgli_freed
715 * - data is removed from the DTree.
718 * - the returned data needs to be mowgli_freed/released manually!
720 void *irc_dictionary_delete(struct Dictionary
*dtree
, const void *key
)
722 struct DictionaryElement
*delem
= irc_dictionary_find(dtree
, key
);
730 irc_dictionary_unlink_root(dtree
);
737 * irc_dictionary_retrieve(struct Dictionary *dtree, const void *key)
739 * Retrieves data from a dictionary.
742 * - dictionary tree object
743 * - name of node to lookup
746 * - on success, the data bound to the DTree node.
752 void *irc_dictionary_retrieve(struct Dictionary
*dtree
, const void *key
)
754 struct DictionaryElement
*delem
= irc_dictionary_find(dtree
, key
);
763 * irc_dictionary_size(struct Dictionary *dict)
765 * Returns the size of a dictionary.
768 * - dictionary tree object
771 * - size of dictionary
776 unsigned int irc_dictionary_size(struct Dictionary
*dict
)
778 s_assert(dict
!= NULL
);
783 /* returns the sum of the depths of the subtree rooted in delem at depth depth */
785 stats_recurse(struct DictionaryElement
*delem
, int depth
, int *pmaxdepth
)
789 if (depth
> *pmaxdepth
)
792 if (delem
&& delem
->left
)
793 result
+= stats_recurse(delem
->left
, depth
+ 1, pmaxdepth
);
794 if (delem
&& delem
->right
)
795 result
+= stats_recurse(delem
->right
, depth
+ 1, pmaxdepth
);
800 * irc_dictionary_stats(struct Dictionary *dict, void (*cb)(const char *line, void *privdata), void *privdata)
802 * Returns the size of a dictionary.
805 * - dictionary tree object
807 * - data for callback
813 * - callback called with stats text
815 void irc_dictionary_stats(struct Dictionary
*dict
, void (*cb
)(const char *line
, void *privdata
), void *privdata
)
820 s_assert(dict
!= NULL
);
825 sum
= stats_recurse(dict
->root
, 0, &maxdepth
);
826 rb_snprintf(str
, sizeof str
, "%s: Objects: %d, Depth sum: %d, Avg depth: %d, Max depth: %d.", dict
->id
, dict
->count
, sum
, sum
/ dict
->count
, maxdepth
);
830 rb_snprintf(str
, sizeof str
, "%s: Objects: 0, Depth sum: 0, Avg depth: 0, Max depth: 0.", dict
->id
);
836 void irc_dictionary_stats_walk(void (*cb
)(const char *line
, void *privdata
), void *privdata
)
840 RB_DLINK_FOREACH(ptr
, dictionary_list
.head
)
842 irc_dictionary_stats(ptr
->data
, cb
, privdata
);