]> jfr.im git - solanum.git/blob - librb/src/dictionary.c
charybdis 4-rc6
[solanum.git] / librb / src / dictionary.c
1 /*
2 * charybdis: an advanced ircd
3 * rb_dictionary.c: Dictionary-based information storage.
4 *
5 * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk>
6 * Copyright (c) 2007 Jilles Tjoelker <jilles -at- stack.nl>
7 *
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.
11 *
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.
23 */
24
25 #include <librb_config.h>
26 #include <rb_lib.h>
27 #include <rb_dictionary.h>
28
29 struct rb_dictionary
30 {
31 DCF compare_cb;
32 rb_dictionary_element *root, *head, *tail;
33 unsigned int count;
34 char *id;
35 unsigned int dirty:1;
36
37 rb_dlink_node node;
38 };
39
40 static rb_dlink_list dictionary_list = {NULL, NULL, 0};
41
42 /*
43 * rb_dictionary_create(const char *name, DCF compare_cb)
44 *
45 * Dictionary object factory.
46 *
47 * Inputs:
48 * - dictionary name
49 * - function to use for comparing two entries in the dtree
50 *
51 * Outputs:
52 * - on success, a new dictionary object.
53 *
54 * Side Effects:
55 * - if services runs out of memory and cannot allocate the object,
56 * the program will abort.
57 */
58 rb_dictionary *rb_dictionary_create(const char *name,
59 DCF compare_cb)
60 {
61 rb_dictionary *dtree = (rb_dictionary *) rb_malloc(sizeof(rb_dictionary));
62
63 dtree->compare_cb = compare_cb;
64 dtree->id = rb_strdup(name);
65
66 rb_dlinkAdd(dtree, &dtree->node, &dictionary_list);
67
68 return dtree;
69 }
70
71 /*
72 * rb_dictionary_set_comparator_func(rb_dictionary *dict,
73 * DCF compare_cb)
74 *
75 * Resets the comparator function used by the dictionary code for
76 * updating the DTree structure.
77 *
78 * Inputs:
79 * - dictionary object
80 * - new comparator function (passed as functor)
81 *
82 * Outputs:
83 * - nothing
84 *
85 * Side Effects:
86 * - the dictionary comparator function is reset.
87 */
88 void rb_dictionary_set_comparator_func(rb_dictionary *dict,
89 DCF compare_cb)
90 {
91 lrb_assert(dict != NULL);
92 lrb_assert(compare_cb != NULL);
93
94 dict->compare_cb = compare_cb;
95 }
96
97 /*
98 * rb_dictionary_get_comparator_func(rb_dictionary *dict)
99 *
100 * Returns the current comparator function used by the dictionary.
101 *
102 * Inputs:
103 * - dictionary object
104 *
105 * Outputs:
106 * - comparator function (returned as functor)
107 *
108 * Side Effects:
109 * - none
110 */
111 DCF
112 rb_dictionary_get_comparator_func(rb_dictionary *dict)
113 {
114 lrb_assert(dict != NULL);
115
116 return dict->compare_cb;
117 }
118
119 /*
120 * rb_dictionary_get_linear_index(rb_dictionary *dict,
121 * const void *key)
122 *
123 * Gets a linear index number for key.
124 *
125 * Inputs:
126 * - dictionary tree object
127 * - pointer to data
128 *
129 * Outputs:
130 * - position, from zero.
131 *
132 * Side Effects:
133 * - rebuilds the linear index if the tree is marked as dirty.
134 */
135 int
136 rb_dictionary_get_linear_index(rb_dictionary *dict, const void *key)
137 {
138 rb_dictionary_element *elem;
139
140 lrb_assert(dict != NULL);
141
142 elem = rb_dictionary_find(dict, key);
143 if (elem == NULL)
144 return -1;
145
146 if (!dict->dirty)
147 return elem->position;
148 else
149 {
150 rb_dictionary_element *delem;
151 int i;
152
153 for (delem = dict->head, i = 0; delem != NULL; delem = delem->next, i++)
154 delem->position = i;
155
156 dict->dirty = FALSE;
157 }
158
159 return elem->position;
160 }
161
162 /*
163 * rb_dictionary_retune(rb_dictionary *dict, const void *key)
164 *
165 * Retunes the tree, self-optimizing for the element which belongs to key.
166 *
167 * Inputs:
168 * - node to begin search from
169 *
170 * Outputs:
171 * - none
172 *
173 * Side Effects:
174 * - a new root node is nominated.
175 */
176 static void
177 rb_dictionary_retune(rb_dictionary *dict, const void *key)
178 {
179 rb_dictionary_element n, *tn, *left, *right, *node;
180 int ret;
181
182 lrb_assert(dict != NULL);
183
184 if (dict->root == NULL)
185 return;
186
187 /*
188 * we initialize n with known values, since it's on stack
189 * memory. otherwise the dict would become corrupted.
190 *
191 * n is used for temporary storage while the tree is retuned.
192 * -nenolod
193 */
194 n.left = n.right = NULL;
195 left = right = &n;
196
197 /* this for(;;) loop is the main workhorse of the rebalancing */
198 for (node = dict->root; ; )
199 {
200 if ((ret = dict->compare_cb(key, node->key)) == 0)
201 break;
202
203 if (ret < 0)
204 {
205 if (node->left == NULL)
206 break;
207
208 if ((ret = dict->compare_cb(key, node->left->key)) < 0)
209 {
210 tn = node->left;
211 node->left = tn->right;
212 tn->right = node;
213 node = tn;
214
215 if (node->left == NULL)
216 break;
217 }
218
219 right->left = node;
220 right = node;
221 node = node->left;
222 }
223 else
224 {
225 if (node->right == NULL)
226 break;
227
228 if ((ret = dict->compare_cb(key, node->right->key)) > 0)
229 {
230 tn = node->right;
231 node->right = tn->left;
232 tn->left = node;
233 node = tn;
234
235 if (node->right == NULL)
236 break;
237 }
238
239 left->right = node;
240 left = node;
241 node = node->right;
242 }
243 }
244
245 left->right = node->left;
246 right->left = node->right;
247
248 node->left = n.right;
249 node->right = n.left;
250
251 dict->root = node;
252 }
253
254 /*
255 * rb_dictionary_link(rb_dictionary *dict,
256 * rb_dictionary_element *delem)
257 *
258 * Links a dictionary tree element to the dictionary.
259 *
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.
264 *
265 * Inputs:
266 * - dictionary tree
267 * - dictionary tree element
268 *
269 * Outputs:
270 * - nothing
271 *
272 * Side Effects:
273 * - a node is linked to the dictionary tree
274 */
275 static void
276 rb_dictionary_link(rb_dictionary *dict,
277 rb_dictionary_element *delem)
278 {
279 lrb_assert(dict != NULL);
280 lrb_assert(delem != NULL);
281
282 dict->dirty = TRUE;
283
284 dict->count++;
285
286 if (dict->root == NULL)
287 {
288 delem->left = delem->right = NULL;
289 delem->next = delem->prev = NULL;
290 dict->head = dict->tail = dict->root = delem;
291 }
292 else
293 {
294 int ret;
295
296 rb_dictionary_retune(dict, delem->key);
297
298 if ((ret = dict->compare_cb(delem->key, dict->root->key)) < 0)
299 {
300 delem->left = dict->root->left;
301 delem->right = dict->root;
302 dict->root->left = NULL;
303
304 if (dict->root->prev)
305 dict->root->prev->next = delem;
306 else
307 dict->head = delem;
308
309 delem->prev = dict->root->prev;
310 delem->next = dict->root;
311 dict->root->prev = delem;
312 dict->root = delem;
313 }
314 else if (ret > 0)
315 {
316 delem->right = dict->root->right;
317 delem->left = dict->root;
318 dict->root->right = NULL;
319
320 if (dict->root->next)
321 dict->root->next->prev = delem;
322 else
323 dict->tail = delem;
324
325 delem->next = dict->root->next;
326 delem->prev = dict->root;
327 dict->root->next = delem;
328 dict->root = delem;
329 }
330 else
331 {
332 dict->root->key = delem->key;
333 dict->root->data = delem->data;
334 dict->count--;
335
336 rb_free(delem);
337 }
338 }
339 }
340
341 /*
342 * rb_dictionary_unlink_root(rb_dictionary *dict)
343 *
344 * Unlinks the root dictionary tree element from the dictionary.
345 *
346 * Inputs:
347 * - dictionary tree
348 *
349 * Outputs:
350 * - nothing
351 *
352 * Side Effects:
353 * - the root node is unlinked from the dictionary tree
354 */
355 static void
356 rb_dictionary_unlink_root(rb_dictionary *dict)
357 {
358 rb_dictionary_element *delem, *nextnode, *parentofnext;
359
360 dict->dirty = TRUE;
361
362 delem = dict->root;
363 if (delem == NULL)
364 return;
365
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;
370 else
371 {
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)
377 {
378 dict->root = nextnode;
379 dict->root->left = delem->left;
380 }
381 else
382 {
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;
391 }
392 }
393
394 /* linked list */
395 if (delem->prev != NULL)
396 delem->prev->next = delem->next;
397
398 if (dict->head == delem)
399 dict->head = delem->next;
400
401 if (delem->next)
402 delem->next->prev = delem->prev;
403
404 if (dict->tail == delem)
405 dict->tail = delem->prev;
406
407 dict->count--;
408 }
409
410 /*
411 * rb_dictionary_destroy(rb_dictionary *dtree,
412 * void (*destroy_cb)(dictionary_elem_t *delem, void *privdata),
413 * void *privdata);
414 *
415 * Recursively destroys all nodes in a dictionary tree.
416 *
417 * Inputs:
418 * - dictionary tree object
419 * - optional iteration callback
420 * - optional opaque/private data to pass to callback
421 *
422 * Outputs:
423 * - nothing
424 *
425 * Side Effects:
426 * - on success, a dtree and optionally it's children are destroyed.
427 *
428 * Notes:
429 * - if this is called without a callback, the objects bound to the
430 * DTree will not be destroyed.
431 */
432 void rb_dictionary_destroy(rb_dictionary *dtree,
433 void (*destroy_cb)(rb_dictionary_element *delem, void *privdata),
434 void *privdata)
435 {
436 rb_dictionary_element *n, *tn;
437
438 lrb_assert(dtree != NULL);
439
440 RB_DLINK_FOREACH_SAFE(n, tn, dtree->head)
441 {
442 if (destroy_cb != NULL)
443 (*destroy_cb)(n, privdata);
444
445 rb_free(n);
446 }
447
448 rb_dlinkDelete(&dtree->node, &dictionary_list);
449 rb_free(dtree->id);
450 rb_free(dtree);
451 }
452
453 /*
454 * rb_dictionary_foreach(rb_dictionary *dtree,
455 * void (*destroy_cb)(dictionary_elem_t *delem, void *privdata),
456 * void *privdata);
457 *
458 * Iterates over all entries in a DTree.
459 *
460 * Inputs:
461 * - dictionary tree object
462 * - optional iteration callback
463 * - optional opaque/private data to pass to callback
464 *
465 * Outputs:
466 * - nothing
467 *
468 * Side Effects:
469 * - on success, a dtree is iterated
470 */
471 void rb_dictionary_foreach(rb_dictionary *dtree,
472 int (*foreach_cb)(rb_dictionary_element *delem, void *privdata),
473 void *privdata)
474 {
475 rb_dictionary_element *n, *tn;
476
477 lrb_assert(dtree != NULL);
478
479 RB_DLINK_FOREACH_SAFE(n, tn, dtree->head)
480 {
481 /* delem_t is a subclass of node_t. */
482 rb_dictionary_element *delem = (rb_dictionary_element *) n;
483
484 if (foreach_cb != NULL)
485 (*foreach_cb)(delem, privdata);
486 }
487 }
488
489 /*
490 * rb_dictionary_search(rb_dictionary *dtree,
491 * void (*destroy_cb)(rb_dictionary_element *delem, void *privdata),
492 * void *privdata);
493 *
494 * Searches all entries in a DTree using a custom callback.
495 *
496 * Inputs:
497 * - dictionary tree object
498 * - optional iteration callback
499 * - optional opaque/private data to pass to callback
500 *
501 * Outputs:
502 * - on success, the requested object
503 * - on failure, NULL.
504 *
505 * Side Effects:
506 * - a dtree is iterated until the requested conditions are met
507 */
508 void *rb_dictionary_search(rb_dictionary *dtree,
509 void *(*foreach_cb)(rb_dictionary_element *delem, void *privdata),
510 void *privdata)
511 {
512 rb_dictionary_element *n, *tn;
513 void *ret = NULL;
514
515 lrb_assert(dtree != NULL);
516
517 RB_DLINK_FOREACH_SAFE(n, tn, dtree->head)
518 {
519 /* delem_t is a subclass of node_t. */
520 rb_dictionary_element *delem = (rb_dictionary_element *) n;
521
522 if (foreach_cb != NULL)
523 ret = (*foreach_cb)(delem, privdata);
524
525 if (ret)
526 break;
527 }
528
529 return ret;
530 }
531
532 /*
533 * rb_dictionary_foreach_start(rb_dictionary *dtree,
534 * rb_dictionary_iter *state);
535 *
536 * Initializes a static DTree iterator.
537 *
538 * Inputs:
539 * - dictionary tree object
540 * - static DTree iterator
541 *
542 * Outputs:
543 * - nothing
544 *
545 * Side Effects:
546 * - the static iterator, &state, is initialized.
547 */
548 void rb_dictionary_foreach_start(rb_dictionary *dtree,
549 rb_dictionary_iter *state)
550 {
551 lrb_assert(dtree != NULL);
552 lrb_assert(state != NULL);
553
554 state->cur = NULL;
555 state->next = NULL;
556
557 /* find first item */
558 state->cur = dtree->head;
559
560 if (state->cur == NULL)
561 return;
562
563 /* make state->cur point to first item and state->next point to
564 * second item */
565 state->next = state->cur;
566 rb_dictionary_foreach_next(dtree, state);
567 }
568
569 /*
570 * rb_dictionary_foreach_cur(rb_dictionary *dtree,
571 * rb_dictionary_iter *state);
572 *
573 * Returns the data from the current node being iterated by the
574 * static iterator.
575 *
576 * Inputs:
577 * - dictionary tree object
578 * - static DTree iterator
579 *
580 * Outputs:
581 * - reference to data in the current dtree node being iterated
582 *
583 * Side Effects:
584 * - none
585 */
586 void *rb_dictionary_foreach_cur(rb_dictionary *dtree,
587 rb_dictionary_iter *state)
588 {
589 lrb_assert(dtree != NULL);
590 lrb_assert(state != NULL);
591
592 return state->cur != NULL ? state->cur->data : NULL;
593 }
594
595 /*
596 * rb_dictionary_foreach_next(rb_dictionary *dtree,
597 * rb_dictionary_iter *state);
598 *
599 * Advances a static DTree iterator.
600 *
601 * Inputs:
602 * - dictionary tree object
603 * - static DTree iterator
604 *
605 * Outputs:
606 * - nothing
607 *
608 * Side Effects:
609 * - the static iterator, &state, is advanced to a new DTree node.
610 */
611 void rb_dictionary_foreach_next(rb_dictionary *dtree,
612 rb_dictionary_iter *state)
613 {
614 lrb_assert(dtree != NULL);
615 lrb_assert(state != NULL);
616
617 if (state->cur == NULL)
618 {
619 rb_lib_log("rb_dictionary_foreach_next(): called again after iteration finished on dtree<%p>", (void *)dtree);
620 return;
621 }
622
623 state->cur = state->next;
624
625 if (state->next == NULL)
626 return;
627
628 state->next = state->next->next;
629 }
630
631 /*
632 * rb_dictionary_find(rb_dictionary *dtree, const void *key)
633 *
634 * Looks up a DTree node by name.
635 *
636 * Inputs:
637 * - dictionary tree object
638 * - name of node to lookup
639 *
640 * Outputs:
641 * - on success, the dtree node requested
642 * - on failure, NULL
643 *
644 * Side Effects:
645 * - none
646 */
647 rb_dictionary_element *rb_dictionary_find(rb_dictionary *dict, const void *key)
648 {
649 lrb_assert(dict != NULL);
650
651 /* retune for key, key will be the tree's root if it's available */
652 rb_dictionary_retune(dict, key);
653
654 if (dict->root && !dict->compare_cb(key, dict->root->key))
655 return dict->root;
656
657 return NULL;
658 }
659
660 /*
661 * rb_dictionary_add(rb_dictionary *dtree, const void *key, void *data)
662 *
663 * Creates a new DTree node and binds data to it.
664 *
665 * Inputs:
666 * - dictionary tree object
667 * - name for new DTree node
668 * - data to bind to the new DTree node
669 *
670 * Outputs:
671 * - on success, a new DTree node
672 * - on failure, NULL
673 *
674 * Side Effects:
675 * - data is inserted into the DTree.
676 */
677 rb_dictionary_element *rb_dictionary_add(rb_dictionary *dict, const void *key, void *data)
678 {
679 rb_dictionary_element *delem;
680
681 lrb_assert(dict != NULL);
682 lrb_assert(data != NULL);
683 lrb_assert(rb_dictionary_find(dict, key) == NULL);
684
685 delem = rb_malloc(sizeof(*delem));
686 delem->key = key;
687 delem->data = data;
688
689 rb_dictionary_link(dict, delem);
690
691 return delem;
692 }
693
694 /*
695 * rb_dictionary_delete(rb_dictionary *dtree, const void *key)
696 *
697 * Deletes data from a dictionary tree.
698 *
699 * Inputs:
700 * - dictionary tree object
701 * - name of DTree node to delete
702 *
703 * Outputs:
704 * - on success, the remaining data that needs to be rb_freed
705 * - on failure, NULL
706 *
707 * Side Effects:
708 * - data is removed from the DTree.
709 *
710 * Notes:
711 * - the returned data needs to be rb_freed/released manually!
712 */
713 void *rb_dictionary_delete(rb_dictionary *dtree, const void *key)
714 {
715 rb_dictionary_element *delem = rb_dictionary_find(dtree, key);
716 void *data;
717
718 if (delem == NULL)
719 return NULL;
720
721 data = delem->data;
722
723 rb_dictionary_unlink_root(dtree);
724 rb_free(delem);
725
726 return data;
727 }
728
729 /*
730 * rb_dictionary_retrieve(rb_dictionary *dtree, const void *key)
731 *
732 * Retrieves data from a dictionary.
733 *
734 * Inputs:
735 * - dictionary tree object
736 * - name of node to lookup
737 *
738 * Outputs:
739 * - on success, the data bound to the DTree node.
740 * - on failure, NULL
741 *
742 * Side Effects:
743 * - none
744 */
745 void *rb_dictionary_retrieve(rb_dictionary *dtree, const void *key)
746 {
747 rb_dictionary_element *delem = rb_dictionary_find(dtree, key);
748
749 if (delem != NULL)
750 return delem->data;
751
752 return NULL;
753 }
754
755 /*
756 * rb_dictionary_size(rb_dictionary *dict)
757 *
758 * Returns the size of a dictionary.
759 *
760 * Inputs:
761 * - dictionary tree object
762 *
763 * Outputs:
764 * - size of dictionary
765 *
766 * Side Effects:
767 * - none
768 */
769 unsigned int rb_dictionary_size(rb_dictionary *dict)
770 {
771 lrb_assert(dict != NULL);
772
773 return dict->count;
774 }
775
776 /* returns the sum of the depths of the subtree rooted in delem at depth depth */
777 static int
778 stats_recurse(rb_dictionary_element *delem, int depth, int *pmaxdepth)
779 {
780 int result;
781
782 if (depth > *pmaxdepth)
783 *pmaxdepth = depth;
784 result = depth;
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);
789 return result;
790 }
791
792 /*
793 * rb_dictionary_stats(rb_dictionary *dict, void (*cb)(const char *line, void *privdata), void *privdata)
794 *
795 * Returns the size of a dictionary.
796 *
797 * Inputs:
798 * - dictionary tree object
799 * - callback
800 * - data for callback
801 *
802 * Outputs:
803 * - none
804 *
805 * Side Effects:
806 * - callback called with stats text
807 */
808 void rb_dictionary_stats(rb_dictionary *dict, void (*cb)(const char *line, void *privdata), void *privdata)
809 {
810 char str[256];
811 int sum, maxdepth;
812
813 lrb_assert(dict != NULL);
814
815 if (dict->count)
816 {
817 maxdepth = 0;
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);
820 }
821 else
822 {
823 snprintf(str, sizeof str, "%-30s %-15s %-10s %-10s %-10s %-10s", dict->id, "DICT", "0", "0", "0", "0");
824 }
825
826 cb(str, privdata);
827 }
828
829 void rb_dictionary_stats_walk(void (*cb)(const char *line, void *privdata), void *privdata)
830 {
831 rb_dlink_node *ptr;
832
833 RB_DLINK_FOREACH(ptr, dictionary_list.head)
834 {
835 rb_dictionary_stats(ptr->data, cb, privdata);
836 }
837 }