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