]>
Commit | Line | Data |
---|---|---|
d6bda36d | 1 | /* |
a6f63a82 | 2 | * Solanum: a slightly advanced ircd |
a4bf26dd | 3 | * rb_dictionary.c: Dictionary-based information storage. |
d6bda36d AC |
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 | ||
a4bf26dd EM |
25 | #include <librb_config.h> |
26 | #include <rb_lib.h> | |
27 | #include <rb_dictionary.h> | |
d6bda36d | 28 | |
4177311e | 29 | struct rb_dictionary |
d6bda36d AC |
30 | { |
31 | DCF compare_cb; | |
4177311e | 32 | rb_dictionary_element *root, *head, *tail; |
d6bda36d AC |
33 | unsigned int count; |
34 | char *id; | |
35 | unsigned int dirty:1; | |
21d5a11c AC |
36 | |
37 | rb_dlink_node node; | |
d6bda36d AC |
38 | }; |
39 | ||
21d5a11c AC |
40 | static rb_dlink_list dictionary_list = {NULL, NULL, 0}; |
41 | ||
d6bda36d | 42 | /* |
a4bf26dd | 43 | * rb_dictionary_create(const char *name, DCF compare_cb) |
d6bda36d AC |
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 | */ | |
4177311e | 58 | rb_dictionary *rb_dictionary_create(const char *name, |
d6bda36d AC |
59 | DCF compare_cb) |
60 | { | |
4177311e | 61 | rb_dictionary *dtree = (rb_dictionary *) rb_malloc(sizeof(rb_dictionary)); |
d6bda36d AC |
62 | |
63 | dtree->compare_cb = compare_cb; | |
47a03750 | 64 | dtree->id = rb_strdup(name); |
d6bda36d | 65 | |
21d5a11c AC |
66 | rb_dlinkAdd(dtree, &dtree->node, &dictionary_list); |
67 | ||
d6bda36d AC |
68 | return dtree; |
69 | } | |
70 | ||
71 | /* | |
4177311e | 72 | * rb_dictionary_set_comparator_func(rb_dictionary *dict, |
d6bda36d AC |
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 | */ | |
4177311e | 88 | void rb_dictionary_set_comparator_func(rb_dictionary *dict, |
d6bda36d AC |
89 | DCF compare_cb) |
90 | { | |
a4bf26dd EM |
91 | lrb_assert(dict != NULL); |
92 | lrb_assert(compare_cb != NULL); | |
d6bda36d AC |
93 | |
94 | dict->compare_cb = compare_cb; | |
95 | } | |
96 | ||
97 | /* | |
4177311e | 98 | * rb_dictionary_get_comparator_func(rb_dictionary *dict) |
d6bda36d AC |
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 | |
4177311e | 112 | rb_dictionary_get_comparator_func(rb_dictionary *dict) |
d6bda36d | 113 | { |
a4bf26dd | 114 | lrb_assert(dict != NULL); |
d6bda36d AC |
115 | |
116 | return dict->compare_cb; | |
117 | } | |
118 | ||
119 | /* | |
4177311e | 120 | * rb_dictionary_get_linear_index(rb_dictionary *dict, |
45dfdf46 | 121 | * const void *key) |
d6bda36d AC |
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 | |
4177311e | 136 | rb_dictionary_get_linear_index(rb_dictionary *dict, const void *key) |
d6bda36d | 137 | { |
4177311e | 138 | rb_dictionary_element *elem; |
d6bda36d | 139 | |
a4bf26dd | 140 | lrb_assert(dict != NULL); |
d6bda36d | 141 | |
a4bf26dd | 142 | elem = rb_dictionary_find(dict, key); |
d6bda36d AC |
143 | if (elem == NULL) |
144 | return -1; | |
145 | ||
146 | if (!dict->dirty) | |
147 | return elem->position; | |
148 | else | |
149 | { | |
4177311e | 150 | rb_dictionary_element *delem; |
d6bda36d AC |
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 | /* | |
4177311e | 163 | * rb_dictionary_retune(rb_dictionary *dict, const void *key) |
d6bda36d AC |
164 | * |
165 | * Retunes the tree, self-optimizing for the element which belongs to key. | |
166 | * | |
d6bda36d AC |
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 | */ | |
2e819b6b | 176 | static void |
4177311e | 177 | rb_dictionary_retune(rb_dictionary *dict, const void *key) |
d6bda36d | 178 | { |
4177311e | 179 | rb_dictionary_element n, *tn, *left, *right, *node; |
d6bda36d AC |
180 | int ret; |
181 | ||
a4bf26dd | 182 | lrb_assert(dict != NULL); |
d6bda36d AC |
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 | /* | |
4177311e EM |
255 | * rb_dictionary_link(rb_dictionary *dict, |
256 | * rb_dictionary_element *delem) | |
d6bda36d AC |
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 | */ | |
1272b289 | 275 | static rb_dictionary_element * |
4177311e EM |
276 | rb_dictionary_link(rb_dictionary *dict, |
277 | rb_dictionary_element *delem) | |
d6bda36d | 278 | { |
a4bf26dd EM |
279 | lrb_assert(dict != NULL); |
280 | lrb_assert(delem != NULL); | |
d6bda36d AC |
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 | ||
a4bf26dd | 296 | rb_dictionary_retune(dict, delem->key); |
d6bda36d AC |
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 | ||
99b461bb | 336 | rb_free(delem); |
1272b289 | 337 | delem = dict->root; |
d6bda36d AC |
338 | } |
339 | } | |
1272b289 SA |
340 | |
341 | return delem; | |
d6bda36d AC |
342 | } |
343 | ||
344 | /* | |
4177311e | 345 | * rb_dictionary_unlink_root(rb_dictionary *dict) |
d6bda36d AC |
346 | * |
347 | * Unlinks the root dictionary tree element from the dictionary. | |
348 | * | |
349 | * Inputs: | |
350 | * - dictionary tree | |
351 | * | |
352 | * Outputs: | |
353 | * - nothing | |
354 | * | |
355 | * Side Effects: | |
356 | * - the root node is unlinked from the dictionary tree | |
357 | */ | |
2e819b6b | 358 | static void |
4177311e | 359 | rb_dictionary_unlink_root(rb_dictionary *dict) |
d6bda36d | 360 | { |
4177311e | 361 | rb_dictionary_element *delem, *nextnode, *parentofnext; |
d6bda36d AC |
362 | |
363 | dict->dirty = TRUE; | |
364 | ||
365 | delem = dict->root; | |
366 | if (delem == NULL) | |
367 | return; | |
368 | ||
369 | if (dict->root->left == NULL) | |
370 | dict->root = dict->root->right; | |
371 | else if (dict->root->right == NULL) | |
372 | dict->root = dict->root->left; | |
373 | else | |
374 | { | |
375 | /* Make the node with the next highest key the new root. | |
376 | * This node has a NULL left pointer. */ | |
377 | nextnode = delem->next; | |
a4bf26dd | 378 | lrb_assert(nextnode->left == NULL); |
d6bda36d AC |
379 | if (nextnode == delem->right) |
380 | { | |
381 | dict->root = nextnode; | |
382 | dict->root->left = delem->left; | |
383 | } | |
384 | else | |
385 | { | |
386 | parentofnext = delem->right; | |
387 | while (parentofnext->left != NULL && parentofnext->left != nextnode) | |
388 | parentofnext = parentofnext->left; | |
a4bf26dd | 389 | lrb_assert(parentofnext->left == nextnode); |
d6bda36d AC |
390 | parentofnext->left = nextnode->right; |
391 | dict->root = nextnode; | |
392 | dict->root->left = delem->left; | |
393 | dict->root->right = delem->right; | |
394 | } | |
395 | } | |
396 | ||
397 | /* linked list */ | |
398 | if (delem->prev != NULL) | |
399 | delem->prev->next = delem->next; | |
400 | ||
401 | if (dict->head == delem) | |
402 | dict->head = delem->next; | |
403 | ||
404 | if (delem->next) | |
405 | delem->next->prev = delem->prev; | |
406 | ||
407 | if (dict->tail == delem) | |
408 | dict->tail = delem->prev; | |
409 | ||
410 | dict->count--; | |
411 | } | |
412 | ||
413 | /* | |
4177311e | 414 | * rb_dictionary_destroy(rb_dictionary *dtree, |
d6bda36d AC |
415 | * void (*destroy_cb)(dictionary_elem_t *delem, void *privdata), |
416 | * void *privdata); | |
417 | * | |
418 | * Recursively destroys all nodes in a dictionary tree. | |
419 | * | |
420 | * Inputs: | |
421 | * - dictionary tree object | |
422 | * - optional iteration callback | |
423 | * - optional opaque/private data to pass to callback | |
424 | * | |
425 | * Outputs: | |
426 | * - nothing | |
427 | * | |
428 | * Side Effects: | |
429 | * - on success, a dtree and optionally it's children are destroyed. | |
430 | * | |
431 | * Notes: | |
432 | * - if this is called without a callback, the objects bound to the | |
433 | * DTree will not be destroyed. | |
434 | */ | |
4177311e EM |
435 | void rb_dictionary_destroy(rb_dictionary *dtree, |
436 | void (*destroy_cb)(rb_dictionary_element *delem, void *privdata), | |
d6bda36d AC |
437 | void *privdata) |
438 | { | |
4177311e | 439 | rb_dictionary_element *n, *tn; |
d6bda36d | 440 | |
a4bf26dd | 441 | lrb_assert(dtree != NULL); |
d6bda36d | 442 | |
5cefa1d6 | 443 | RB_DLINK_FOREACH_SAFE(n, tn, dtree->head) |
d6bda36d AC |
444 | { |
445 | if (destroy_cb != NULL) | |
446 | (*destroy_cb)(n, privdata); | |
447 | ||
99b461bb | 448 | rb_free(n); |
d6bda36d AC |
449 | } |
450 | ||
21d5a11c | 451 | rb_dlinkDelete(&dtree->node, &dictionary_list); |
55d5f797 | 452 | rb_free(dtree->id); |
637c4932 | 453 | rb_free(dtree); |
d6bda36d AC |
454 | } |
455 | ||
456 | /* | |
4177311e | 457 | * rb_dictionary_foreach(rb_dictionary *dtree, |
d6bda36d AC |
458 | * void (*destroy_cb)(dictionary_elem_t *delem, void *privdata), |
459 | * void *privdata); | |
460 | * | |
461 | * Iterates over all entries in a DTree. | |
462 | * | |
463 | * Inputs: | |
464 | * - dictionary tree object | |
465 | * - optional iteration callback | |
466 | * - optional opaque/private data to pass to callback | |
467 | * | |
468 | * Outputs: | |
469 | * - nothing | |
470 | * | |
471 | * Side Effects: | |
472 | * - on success, a dtree is iterated | |
473 | */ | |
4177311e EM |
474 | void rb_dictionary_foreach(rb_dictionary *dtree, |
475 | int (*foreach_cb)(rb_dictionary_element *delem, void *privdata), | |
d6bda36d AC |
476 | void *privdata) |
477 | { | |
4177311e | 478 | rb_dictionary_element *n, *tn; |
d6bda36d | 479 | |
a4bf26dd | 480 | lrb_assert(dtree != NULL); |
d6bda36d | 481 | |
5cefa1d6 | 482 | RB_DLINK_FOREACH_SAFE(n, tn, dtree->head) |
d6bda36d AC |
483 | { |
484 | /* delem_t is a subclass of node_t. */ | |
4177311e | 485 | rb_dictionary_element *delem = (rb_dictionary_element *) n; |
d6bda36d AC |
486 | |
487 | if (foreach_cb != NULL) | |
488 | (*foreach_cb)(delem, privdata); | |
489 | } | |
490 | } | |
491 | ||
492 | /* | |
4177311e EM |
493 | * rb_dictionary_search(rb_dictionary *dtree, |
494 | * void (*destroy_cb)(rb_dictionary_element *delem, void *privdata), | |
d6bda36d AC |
495 | * void *privdata); |
496 | * | |
497 | * Searches all entries in a DTree using a custom callback. | |
498 | * | |
499 | * Inputs: | |
500 | * - dictionary tree object | |
501 | * - optional iteration callback | |
502 | * - optional opaque/private data to pass to callback | |
503 | * | |
504 | * Outputs: | |
505 | * - on success, the requested object | |
506 | * - on failure, NULL. | |
507 | * | |
508 | * Side Effects: | |
509 | * - a dtree is iterated until the requested conditions are met | |
510 | */ | |
4177311e EM |
511 | void *rb_dictionary_search(rb_dictionary *dtree, |
512 | void *(*foreach_cb)(rb_dictionary_element *delem, void *privdata), | |
d6bda36d AC |
513 | void *privdata) |
514 | { | |
4177311e | 515 | rb_dictionary_element *n, *tn; |
d6bda36d AC |
516 | void *ret = NULL; |
517 | ||
a4bf26dd | 518 | lrb_assert(dtree != NULL); |
d6bda36d | 519 | |
5cefa1d6 | 520 | RB_DLINK_FOREACH_SAFE(n, tn, dtree->head) |
d6bda36d AC |
521 | { |
522 | /* delem_t is a subclass of node_t. */ | |
4177311e | 523 | rb_dictionary_element *delem = (rb_dictionary_element *) n; |
d6bda36d AC |
524 | |
525 | if (foreach_cb != NULL) | |
526 | ret = (*foreach_cb)(delem, privdata); | |
527 | ||
528 | if (ret) | |
529 | break; | |
530 | } | |
531 | ||
532 | return ret; | |
533 | } | |
534 | ||
535 | /* | |
4177311e EM |
536 | * rb_dictionary_foreach_start(rb_dictionary *dtree, |
537 | * rb_dictionary_iter *state); | |
d6bda36d AC |
538 | * |
539 | * Initializes a static DTree iterator. | |
540 | * | |
541 | * Inputs: | |
542 | * - dictionary tree object | |
543 | * - static DTree iterator | |
544 | * | |
545 | * Outputs: | |
546 | * - nothing | |
547 | * | |
548 | * Side Effects: | |
549 | * - the static iterator, &state, is initialized. | |
550 | */ | |
4177311e EM |
551 | void rb_dictionary_foreach_start(rb_dictionary *dtree, |
552 | rb_dictionary_iter *state) | |
d6bda36d | 553 | { |
a4bf26dd EM |
554 | lrb_assert(dtree != NULL); |
555 | lrb_assert(state != NULL); | |
d6bda36d AC |
556 | |
557 | state->cur = NULL; | |
558 | state->next = NULL; | |
559 | ||
560 | /* find first item */ | |
561 | state->cur = dtree->head; | |
562 | ||
563 | if (state->cur == NULL) | |
564 | return; | |
565 | ||
566 | /* make state->cur point to first item and state->next point to | |
567 | * second item */ | |
568 | state->next = state->cur; | |
a4bf26dd | 569 | rb_dictionary_foreach_next(dtree, state); |
d6bda36d AC |
570 | } |
571 | ||
572 | /* | |
4177311e EM |
573 | * rb_dictionary_foreach_cur(rb_dictionary *dtree, |
574 | * rb_dictionary_iter *state); | |
d6bda36d AC |
575 | * |
576 | * Returns the data from the current node being iterated by the | |
577 | * static iterator. | |
578 | * | |
579 | * Inputs: | |
580 | * - dictionary tree object | |
581 | * - static DTree iterator | |
582 | * | |
583 | * Outputs: | |
584 | * - reference to data in the current dtree node being iterated | |
585 | * | |
586 | * Side Effects: | |
587 | * - none | |
588 | */ | |
8679c0fe | 589 | void *rb_dictionary_foreach_cur(rb_dictionary *dtree __attribute__((unused)), |
4177311e | 590 | rb_dictionary_iter *state) |
d6bda36d | 591 | { |
a4bf26dd EM |
592 | lrb_assert(dtree != NULL); |
593 | lrb_assert(state != NULL); | |
d6bda36d AC |
594 | |
595 | return state->cur != NULL ? state->cur->data : NULL; | |
596 | } | |
597 | ||
598 | /* | |
4177311e EM |
599 | * rb_dictionary_foreach_next(rb_dictionary *dtree, |
600 | * rb_dictionary_iter *state); | |
d6bda36d AC |
601 | * |
602 | * Advances a static DTree iterator. | |
603 | * | |
604 | * Inputs: | |
605 | * - dictionary tree object | |
606 | * - static DTree iterator | |
607 | * | |
608 | * Outputs: | |
609 | * - nothing | |
610 | * | |
611 | * Side Effects: | |
612 | * - the static iterator, &state, is advanced to a new DTree node. | |
613 | */ | |
4177311e EM |
614 | void rb_dictionary_foreach_next(rb_dictionary *dtree, |
615 | rb_dictionary_iter *state) | |
d6bda36d | 616 | { |
a4bf26dd EM |
617 | lrb_assert(dtree != NULL); |
618 | lrb_assert(state != NULL); | |
d6bda36d AC |
619 | |
620 | if (state->cur == NULL) | |
621 | { | |
a4bf26dd | 622 | rb_lib_log("rb_dictionary_foreach_next(): called again after iteration finished on dtree<%p>", (void *)dtree); |
d6bda36d AC |
623 | return; |
624 | } | |
625 | ||
626 | state->cur = state->next; | |
627 | ||
628 | if (state->next == NULL) | |
629 | return; | |
630 | ||
631 | state->next = state->next->next; | |
632 | } | |
633 | ||
634 | /* | |
4177311e | 635 | * rb_dictionary_find(rb_dictionary *dtree, const void *key) |
d6bda36d AC |
636 | * |
637 | * Looks up a DTree node by name. | |
638 | * | |
639 | * Inputs: | |
640 | * - dictionary tree object | |
641 | * - name of node to lookup | |
642 | * | |
643 | * Outputs: | |
644 | * - on success, the dtree node requested | |
645 | * - on failure, NULL | |
646 | * | |
647 | * Side Effects: | |
648 | * - none | |
649 | */ | |
4177311e | 650 | rb_dictionary_element *rb_dictionary_find(rb_dictionary *dict, const void *key) |
d6bda36d | 651 | { |
a4bf26dd | 652 | lrb_assert(dict != NULL); |
d6bda36d AC |
653 | |
654 | /* retune for key, key will be the tree's root if it's available */ | |
a4bf26dd | 655 | rb_dictionary_retune(dict, key); |
d6bda36d AC |
656 | |
657 | if (dict->root && !dict->compare_cb(key, dict->root->key)) | |
658 | return dict->root; | |
659 | ||
660 | return NULL; | |
661 | } | |
662 | ||
663 | /* | |
4177311e | 664 | * rb_dictionary_add(rb_dictionary *dtree, const void *key, void *data) |
d6bda36d AC |
665 | * |
666 | * Creates a new DTree node and binds data to it. | |
667 | * | |
668 | * Inputs: | |
669 | * - dictionary tree object | |
670 | * - name for new DTree node | |
671 | * - data to bind to the new DTree node | |
672 | * | |
673 | * Outputs: | |
674 | * - on success, a new DTree node | |
675 | * - on failure, NULL | |
676 | * | |
677 | * Side Effects: | |
678 | * - data is inserted into the DTree. | |
679 | */ | |
4177311e | 680 | rb_dictionary_element *rb_dictionary_add(rb_dictionary *dict, const void *key, void *data) |
d6bda36d | 681 | { |
4177311e | 682 | rb_dictionary_element *delem; |
d6bda36d | 683 | |
a4bf26dd | 684 | lrb_assert(dict != NULL); |
a4bf26dd EM |
685 | lrb_assert(data != NULL); |
686 | lrb_assert(rb_dictionary_find(dict, key) == NULL); | |
d6bda36d | 687 | |
99b461bb | 688 | delem = rb_malloc(sizeof(*delem)); |
d6bda36d AC |
689 | delem->key = key; |
690 | delem->data = data; | |
691 | ||
1272b289 | 692 | return rb_dictionary_link(dict, delem); |
d6bda36d AC |
693 | } |
694 | ||
695 | /* | |
4177311e | 696 | * rb_dictionary_delete(rb_dictionary *dtree, const void *key) |
d6bda36d AC |
697 | * |
698 | * Deletes data from a dictionary tree. | |
699 | * | |
700 | * Inputs: | |
701 | * - dictionary tree object | |
702 | * - name of DTree node to delete | |
703 | * | |
704 | * Outputs: | |
731d1289 | 705 | * - on success, the remaining data that needs to be rb_freed |
d6bda36d AC |
706 | * - on failure, NULL |
707 | * | |
708 | * Side Effects: | |
709 | * - data is removed from the DTree. | |
710 | * | |
711 | * Notes: | |
731d1289 | 712 | * - the returned data needs to be rb_freed/released manually! |
d6bda36d | 713 | */ |
4177311e | 714 | void *rb_dictionary_delete(rb_dictionary *dtree, const void *key) |
d6bda36d | 715 | { |
4177311e | 716 | rb_dictionary_element *delem = rb_dictionary_find(dtree, key); |
d6bda36d AC |
717 | void *data; |
718 | ||
719 | if (delem == NULL) | |
720 | return NULL; | |
721 | ||
722 | data = delem->data; | |
723 | ||
a4bf26dd | 724 | rb_dictionary_unlink_root(dtree); |
99b461bb | 725 | rb_free(delem); |
d6bda36d AC |
726 | |
727 | return data; | |
728 | } | |
729 | ||
730 | /* | |
4177311e | 731 | * rb_dictionary_retrieve(rb_dictionary *dtree, const void *key) |
d6bda36d AC |
732 | * |
733 | * Retrieves data from a dictionary. | |
734 | * | |
735 | * Inputs: | |
736 | * - dictionary tree object | |
737 | * - name of node to lookup | |
738 | * | |
739 | * Outputs: | |
740 | * - on success, the data bound to the DTree node. | |
741 | * - on failure, NULL | |
742 | * | |
743 | * Side Effects: | |
744 | * - none | |
745 | */ | |
4177311e | 746 | void *rb_dictionary_retrieve(rb_dictionary *dtree, const void *key) |
d6bda36d | 747 | { |
4177311e | 748 | rb_dictionary_element *delem = rb_dictionary_find(dtree, key); |
d6bda36d AC |
749 | |
750 | if (delem != NULL) | |
751 | return delem->data; | |
752 | ||
753 | return NULL; | |
754 | } | |
755 | ||
756 | /* | |
4177311e | 757 | * rb_dictionary_size(rb_dictionary *dict) |
d6bda36d AC |
758 | * |
759 | * Returns the size of a dictionary. | |
760 | * | |
761 | * Inputs: | |
762 | * - dictionary tree object | |
763 | * | |
764 | * Outputs: | |
765 | * - size of dictionary | |
766 | * | |
767 | * Side Effects: | |
768 | * - none | |
769 | */ | |
4177311e | 770 | unsigned int rb_dictionary_size(rb_dictionary *dict) |
d6bda36d | 771 | { |
a4bf26dd | 772 | lrb_assert(dict != NULL); |
d6bda36d AC |
773 | |
774 | return dict->count; | |
775 | } | |
776 | ||
777 | /* returns the sum of the depths of the subtree rooted in delem at depth depth */ | |
778 | static int | |
4177311e | 779 | stats_recurse(rb_dictionary_element *delem, int depth, int *pmaxdepth) |
d6bda36d AC |
780 | { |
781 | int result; | |
782 | ||
783 | if (depth > *pmaxdepth) | |
784 | *pmaxdepth = depth; | |
785 | result = depth; | |
d99ff029 | 786 | if (delem && delem->left) |
d6bda36d | 787 | result += stats_recurse(delem->left, depth + 1, pmaxdepth); |
d99ff029 | 788 | if (delem && delem->right) |
d6bda36d AC |
789 | result += stats_recurse(delem->right, depth + 1, pmaxdepth); |
790 | return result; | |
791 | } | |
792 | ||
793 | /* | |
4177311e | 794 | * rb_dictionary_stats(rb_dictionary *dict, void (*cb)(const char *line, void *privdata), void *privdata) |
d6bda36d AC |
795 | * |
796 | * Returns the size of a dictionary. | |
797 | * | |
798 | * Inputs: | |
799 | * - dictionary tree object | |
800 | * - callback | |
801 | * - data for callback | |
802 | * | |
803 | * Outputs: | |
804 | * - none | |
805 | * | |
806 | * Side Effects: | |
807 | * - callback called with stats text | |
808 | */ | |
4177311e | 809 | void rb_dictionary_stats(rb_dictionary *dict, void (*cb)(const char *line, void *privdata), void *privdata) |
d6bda36d AC |
810 | { |
811 | char str[256]; | |
812 | int sum, maxdepth; | |
813 | ||
a4bf26dd | 814 | lrb_assert(dict != NULL); |
d6bda36d | 815 | |
d99ff029 AC |
816 | if (dict->count) |
817 | { | |
818 | maxdepth = 0; | |
819 | sum = stats_recurse(dict->root, 0, &maxdepth); | |
d8f0b5d7 | 820 | snprintf(str, sizeof str, "%-30s %-15s %-10u %-10d %-10d %-10d", dict->id, "DICT", dict->count, sum, sum / dict->count, maxdepth); |
d99ff029 AC |
821 | } |
822 | else | |
823 | { | |
8dacf9e9 | 824 | snprintf(str, sizeof str, "%-30s %-15s %-10s %-10s %-10s %-10s", dict->id, "DICT", "0", "0", "0", "0"); |
d99ff029 AC |
825 | } |
826 | ||
d6bda36d | 827 | cb(str, privdata); |
21d5a11c AC |
828 | } |
829 | ||
a4bf26dd | 830 | void rb_dictionary_stats_walk(void (*cb)(const char *line, void *privdata), void *privdata) |
21d5a11c AC |
831 | { |
832 | rb_dlink_node *ptr; | |
833 | ||
834 | RB_DLINK_FOREACH(ptr, dictionary_list.head) | |
835 | { | |
a4bf26dd | 836 | rb_dictionary_stats(ptr->data, cb, privdata); |
21d5a11c | 837 | } |
d6bda36d | 838 | } |