src/irc_dictionary.c

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