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