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