isisd/dict.c

   1 /*
   2  * Dictionary Abstract Data Type
   3  * Copyright (C) 1997 Kaz Kylheku <kaz@ashi.footprints.net>
   4  *
   5  * Free Software License:
   6  *
   7  * All rights are reserved by the author, with the following exceptions:
   8  * Permission is granted to freely reproduce and distribute this software,
   9  * possibly in exchange for a fee, provided that this copyright notice appears
  10  * intact. Permission is also granted to adapt this software to produce
  11  * derivative works, as long as the modified versions carry this copyright
  12  * notice and additional notices stating that the work has been modified.
  13  * This source code may be translated into executable form and incorporated
  14  * into proprietary software; there is no requirement for such software to
  15  * contain a copyright notice related to this source.
  16  */
  17
  18 #include "zebra.h"
  19 #include "zassert.h"
  20 #include "memory.h"
  21 #include "dict.h"
  22
  23 /*
  24  * These macros provide short convenient names for structure members,
  25  * which are embellished with dict_ prefixes so that they are
  26  * properly confined to the documented namespace. It's legal for a
  27  * program which uses dict to define, for instance, a macro called ``parent''.
  28  * Such a macro would interfere with the dnode_t struct definition.
  29  * In general, highly portable and reusable C modules which expose their
  30  * structures need to confine structure member names to well-defined spaces.
  31  * The resulting identifiers aren't necessarily convenient to use, nor
  32  * readable, in the implementation, however!
  33  */
  34
  35 #define left dict_left
  36 #define right dict_right
  37 #define parent dict_parent
  38 #define color dict_color
  39 #define key dict_key
  40 #define data dict_data
  41
  42 #define nilnode dict_nilnode
  43 #define nodecount dict_nodecount
  44 #define maxcount dict_maxcount
  45 #define compare dict_compare
  46 #define allocnode dict_allocnode
  47 #define freenode dict_freenode
  48 #define context dict_context
  49 #define dupes dict_dupes
  50
  51 #define dictptr dict_dictptr
  52
  53 #define dict_root(D) ((D)->nilnode.left)
  54 #define dict_nil(D) (&(D)->nilnode)
  55 #define DICT_DEPTH_MAX 64
  56
  57 static dnode_t *dnode_alloc(void *context);
  58 static void dnode_free(dnode_t *node, void *context);
  59
  60 /*
  61  * Perform a ``left rotation'' adjustment on the tree.  The given node P and
  62  * its right child C are rearranged so that the P instead becomes the left
  63  * child of C.   The left subtree of C is inherited as the new right subtree
  64  * for P.  The ordering of the keys within the tree is thus preserved.
  65  */
  66
  67 static void rotate_left(dnode_t *upper)
  68 {
  69     dnode_t *lower, *lowleft, *upparent;
  70
  71     lower = upper->right;
  72     upper->right = lowleft = lower->left;
  73     lowleft->parent = upper;
  74
  75     lower->parent = upparent = upper->parent;
  76
  77     /* don't need to check for root node here because root->parent is
  78        the sentinel nil node, and root->parent->left points back to root */
  79
  80     if (upper == upparent->left) {
  81         upparent->left = lower;
  82     } else {
  83         assert (upper == upparent->right);
  84         upparent->right = lower;
  85     }
  86
  87     lower->left = upper;
  88     upper->parent = lower;
  89 }
  90
  91 /*
  92  * This operation is the ``mirror'' image of rotate_left. It is
  93  * the same procedure, but with left and right interchanged.
  94  */
  95
  96 static void rotate_right(dnode_t *upper)
  97 {
  98     dnode_t *lower, *lowright, *upparent;
  99
 100     lower = upper->left;
 101     upper->left = lowright = lower->right;
 102     lowright->parent = upper;
 103
 104     lower->parent = upparent = upper->parent;
 105
 106     if (upper == upparent->right) {
 107         upparent->right = lower;
 108     } else {
 109         assert (upper == upparent->left);
 110         upparent->left = lower;
 111     }
 112
 113     lower->right = upper;
 114     upper->parent = lower;
 115 }
 116
 117 /*
 118  * Do a postorder traversal of the tree rooted at the specified
 119  * node and free everything under it.  Used by dict_free().
 120  */
 121
 122 static void free_nodes(dict_t *dict, dnode_t *node, dnode_t *nil)
 123 {
 124     if (node == nil)
 125         return;
 126     free_nodes(dict, node->left, nil);
 127     free_nodes(dict, node->right, nil);
 128     dict->freenode(node, dict->context);
 129 }
 130
 131 /*
 132  * This procedure performs a verification that the given subtree is a binary
 133  * search tree. It performs an inorder traversal of the tree using the
 134  * dict_next() successor function, verifying that the key of each node is
 135  * strictly lower than that of its successor, if duplicates are not allowed,
 136  * or lower or equal if duplicates are allowed.  This function is used for
 137  * debugging purposes.
 138  */
 139
 140 static int verify_bintree(dict_t *dict)
 141 {
 142     dnode_t *first, *next;
 143
 144     first = dict_first(dict);
 145
 146     if (dict->dupes) {
 147         while (first && (next = dict_next(dict, first))) {
 148             if (dict->compare(first->key, next->key) > 0)
 149                 return 0;
 150             first = next;
 151         }
 152     } else {
 153         while (first && (next = dict_next(dict, first))) {
 154             if (dict->compare(first->key, next->key) >= 0)
 155                 return 0;
 156             first = next;
 157         }
 158     }
 159     return 1;
 160 }
 161
 162
 163 /*
 164  * This function recursively verifies that the given binary subtree satisfies
 165  * three of the red black properties. It checks that every red node has only
 166  * black children. It makes sure that each node is either red or black. And it
 167  * checks that every path has the same count of black nodes from root to leaf.
 168  * It returns the blackheight of the given subtree; this allows blackheights to
 169  * be computed recursively and compared for left and right siblings for
 170  * mismatches. It does not check for every nil node being black, because there
 171  * is only one sentinel nil node. The return value of this function is the
 172  * black height of the subtree rooted at the node ``root'', or zero if the
 173  * subtree is not red-black.
 174  */
 175
 176 static unsigned int verify_redblack(dnode_t *nil, dnode_t *root)
 177 {
 178     unsigned height_left, height_right;
 179
 180     if (root != nil) {
 181         height_left = verify_redblack(nil, root->left);
 182         height_right = verify_redblack(nil, root->right);
 183         if (height_left == 0 || height_right == 0)
 184             return 0;
 185         if (height_left != height_right)
 186             return 0;
 187         if (root->color == dnode_red) {
 188             if (root->left->color != dnode_black)
 189                 return 0;
 190             if (root->right->color != dnode_black)
 191                 return 0;
 192             return height_left;
 193         }
 194         if (root->color != dnode_black)
 195             return 0;
 196         return height_left + 1;
 197     }
 198     return 1;
 199 }
 200
 201 /*
 202  * Compute the actual count of nodes by traversing the tree and
 203  * return it. This could be compared against the stored count to
 204  * detect a mismatch.
 205  */
 206
 207 static dictcount_t verify_node_count(dnode_t *nil, dnode_t *root)
 208 {
 209     if (root == nil)
 210         return 0;
 211     else
 212         return 1 + verify_node_count(nil, root->left)
 213             + verify_node_count(nil, root->right);
 214 }
 215
 216 /*
 217  * Verify that the tree contains the given node. This is done by
 218  * traversing all of the nodes and comparing their pointers to the
 219  * given pointer. Returns 1 if the node is found, otherwise
 220  * returns zero. It is intended for debugging purposes.
 221  */
 222
 223 static int verify_dict_has_node(dnode_t *nil, dnode_t *root, dnode_t *node)
 224 {
 225     if (root != nil) {
 226         return root == node
 227                 || verify_dict_has_node(nil, root->left, node)
 228                 || verify_dict_has_node(nil, root->right, node);
 229     }
 230     return 0;
 231 }
 232
 233
 234 /*
 235  * Dynamically allocate and initialize a dictionary object.
 236  */
 237
 238 dict_t *dict_create(dictcount_t maxcount, dict_comp_t comp)
 239 {
 240     dict_t *new = XCALLOC(MTYPE_ISIS_DICT, sizeof(dict_t));
 241
 242     if (new) {
 243         new->compare = comp;
 244         new->allocnode = dnode_alloc;
 245         new->freenode = dnode_free;
 246         new->context = NULL;
 247         new->nodecount = 0;
 248         new->maxcount = maxcount;
 249         new->nilnode.left = &new->nilnode;
 250         new->nilnode.right = &new->nilnode;
 251         new->nilnode.parent = &new->nilnode;
 252         new->nilnode.color = dnode_black;
 253         new->dupes = 0;
 254     }
 255     return new;
 256 }
 257
 258 /*
 259  * Select a different set of node allocator routines.
 260  */
 261
 262 void dict_set_allocator(dict_t *dict, dnode_alloc_t al,
 263         dnode_free_t fr, void *context)
 264 {
 265     assert (dict_count(dict) == 0);
 266     assert ((al == NULL && fr == NULL) || (al != NULL && fr != NULL));
 267
 268     dict->allocnode = al ? al : dnode_alloc;
 269     dict->freenode = fr ? fr : dnode_free;
 270     dict->context = context;
 271 }
 272
 273 /*
 274  * Free a dynamically allocated dictionary object. Removing the nodes
 275  * from the tree before deleting it is required.
 276  */
 277
 278 void dict_destroy(dict_t *dict)
 279 {
 280     assert (dict_isempty(dict));
 281     XFREE(MTYPE_ISIS_DICT, dict);
 282 }
 283
 284 /*
 285  * Free all the nodes in the dictionary by using the dictionary's
 286  * installed free routine. The dictionary is emptied.
 287  */
 288
 289 void dict_free_nodes(dict_t *dict)
 290 {
 291     dnode_t *nil = dict_nil(dict), *root = dict_root(dict);
 292     free_nodes(dict, root, nil);
 293     dict->nodecount = 0;
 294     dict->nilnode.left = &dict->nilnode;
 295     dict->nilnode.right = &dict->nilnode;
 296 }
 297
 298 /*
 299  * Obsolescent function, equivalent to dict_free_nodes
 300  */
 301
 302 void dict_free(dict_t *dict)
 303 {
 304     dict_free_nodes(dict);
 305 }
 306
 307 /*
 308  * Initialize a user-supplied dictionary object.
 309  */
 310
 311 dict_t *dict_init(dict_t *dict, dictcount_t maxcount, dict_comp_t comp)
 312 {
 313     dict->compare = comp;
 314     dict->allocnode = dnode_alloc;
 315     dict->freenode = dnode_free;
 316     dict->context = NULL;
 317     dict->nodecount = 0;
 318     dict->maxcount = maxcount;
 319     dict->nilnode.left = &dict->nilnode;
 320     dict->nilnode.right = &dict->nilnode;
 321     dict->nilnode.parent = &dict->nilnode;
 322     dict->nilnode.color = dnode_black;
 323     dict->dupes = 0;
 324     return dict;
 325 }
 326
 327 /*
 328  * Initialize a dictionary in the likeness of another dictionary
 329  */
 330
 331 void dict_init_like(dict_t *dict, const dict_t *template)
 332 {
 333     dict->compare = template->compare;
 334     dict->allocnode = template->allocnode;
 335     dict->freenode = template->freenode;
 336     dict->context = template->context;
 337     dict->nodecount = 0;
 338     dict->maxcount = template->maxcount;
 339     dict->nilnode.left = &dict->nilnode;
 340     dict->nilnode.right = &dict->nilnode;
 341     dict->nilnode.parent = &dict->nilnode;
 342     dict->nilnode.color = dnode_black;
 343     dict->dupes = template->dupes;
 344
 345     assert (dict_similar(dict, template));
 346 }
 347
 348 /*
 349  * Remove all nodes from the dictionary (without freeing them in any way).
 350  */
 351
 352 static void dict_clear(dict_t *dict)
 353 {
 354     dict->nodecount = 0;
 355     dict->nilnode.left = &dict->nilnode;
 356     dict->nilnode.right = &dict->nilnode;
 357     dict->nilnode.parent = &dict->nilnode;
 358     assert (dict->nilnode.color == dnode_black);
 359 }
 360
 361
 362 /*
 363  * Verify the integrity of the dictionary structure.  This is provided for
 364  * debugging purposes, and should be placed in assert statements.   Just because
 365  * this function succeeds doesn't mean that the tree is not corrupt. Certain
 366  * corruptions in the tree may simply cause undefined behavior.
 367  */
 368
 369 int dict_verify(dict_t *dict)
 370 {
 371     dnode_t *nil = dict_nil(dict), *root = dict_root(dict);
 372
 373     /* check that the sentinel node and root node are black */
 374     if (root->color != dnode_black)
 375         return 0;
 376     if (nil->color != dnode_black)
 377         return 0;
 378     if (nil->right != nil)
 379         return 0;
 380     /* nil->left is the root node; check that its parent pointer is nil */
 381     if (nil->left->parent != nil)
 382         return 0;
 383     /* perform a weak test that the tree is a binary search tree */
 384     if (!verify_bintree(dict))
 385         return 0;
 386     /* verify that the tree is a red-black tree */
 387     if (!verify_redblack(nil, root))
 388         return 0;
 389     if (verify_node_count(nil, root) != dict_count(dict))
 390         return 0;
 391     return 1;
 392 }
 393
 394 /*
 395  * Determine whether two dictionaries are similar: have the same comparison and
 396  * allocator functions, and same status as to whether duplicates are allowed.
 397  */
 398
 399 int dict_similar(const dict_t *left, const dict_t *right)
 400 {
 401     if (left->compare != right->compare)
 402         return 0;
 403
 404     if (left->allocnode != right->allocnode)
 405         return 0;
 406
 407     if (left->freenode != right->freenode)
 408         return 0;
 409
 410     if (left->context != right->context)
 411         return 0;
 412
 413     if (left->dupes != right->dupes)
 414         return 0;
 415
 416     return 1;
 417 }
 418
 419 /*
 420  * Locate a node in the dictionary having the given key.
 421  * If the node is not found, a null a pointer is returned (rather than
 422  * a pointer that dictionary's nil sentinel node), otherwise a pointer to the
 423  * located node is returned.
 424  */
 425
 426 dnode_t *dict_lookup(dict_t *dict, const void *key)
 427 {
 428     dnode_t *root = dict_root(dict);
 429     dnode_t *nil = dict_nil(dict);
 430     dnode_t *saved;
 431     int result;
 432
 433     /* simple binary search adapted for trees that contain duplicate keys */
 434
 435     while (root != nil) {
 436         result = dict->compare(key, root->key);
 437         if (result < 0)
 438             root = root->left;
 439         else if (result > 0)
 440             root = root->right;
 441         else {
 442             if (!dict->dupes) { /* no duplicates, return match          */
 443                 return root;
 444             } else {            /* could be dupes, find leftmost one    */
 445                 do {
 446                     saved = root;
 447                     root = root->left;
 448                     while (root != nil && dict->compare(key, root->key))
 449                         root = root->right;
 450                 } while (root != nil);
 451                 return saved;
 452             }
 453         }
 454     }
 455
 456     return NULL;
 457 }
 458
 459 /*
 460  * Look for the node corresponding to the lowest key that is equal to or
 461  * greater than the given key.  If there is no such node, return null.
 462  */
 463
 464 dnode_t *dict_lower_bound(dict_t *dict, const void *key)
 465 {
 466     dnode_t *root = dict_root(dict);
 467     dnode_t *nil = dict_nil(dict);
 468     dnode_t *tentative = 0;
 469
 470     while (root != nil) {
 471         int result = dict->compare(key, root->key);
 472
 473         if (result > 0) {
 474             root = root->right;
 475         } else if (result < 0) {
 476             tentative = root;
 477             root = root->left;
 478         } else {
 479             if (!dict->dupes) {
 480                 return root;
 481             } else {
 482                 tentative = root;
 483                 root = root->left;
 484             }
 485         }
 486     }
 487
 488     return tentative;
 489 }
 490
 491 /*
 492  * Look for the node corresponding to the greatest key that is equal to or
 493  * lower than the given key.  If there is no such node, return null.
 494  */
 495
 496 dnode_t *dict_upper_bound(dict_t *dict, const void *key)
 497 {
 498     dnode_t *root = dict_root(dict);
 499     dnode_t *nil = dict_nil(dict);
 500     dnode_t *tentative = 0;
 501
 502     while (root != nil) {
 503         int result = dict->compare(key, root->key);
 504
 505         if (result < 0) {
 506             root = root->left;
 507         } else if (result > 0) {
 508             tentative = root;
 509             root = root->right;
 510         } else {
 511             if (!dict->dupes) {
 512                 return root;
 513             } else {
 514                 tentative = root;
 515                 root = root->right;
 516             }
 517         }
 518     }
 519
 520     return tentative;
 521 }
 522
 523 /*
 524  * Insert a node into the dictionary. The node should have been
 525  * initialized with a data field. All other fields are ignored.
 526  * The behavior is undefined if the user attempts to insert into
 527  * a dictionary that is already full (for which the dict_isfull()
 528  * function returns true).
 529  */
 530
 531 void dict_insert(dict_t *dict, dnode_t *node, const void *key)
 532 {
 533     dnode_t *where = dict_root(dict), *nil = dict_nil(dict);
 534     dnode_t *parent = nil, *uncle, *grandpa;
 535     int result = -1;
 536
 537     node->key = key;
 538
 539     assert (!dict_isfull(dict));
 540     assert (!dict_contains(dict, node));
 541     assert (!dnode_is_in_a_dict(node));
 542
 543     /* basic binary tree insert */
 544
 545     while (where != nil) {
 546         parent = where;
 547         result = dict->compare(key, where->key);
 548         /* trap attempts at duplicate key insertion unless it's explicitly allowed */
 549         assert (dict->dupes || result != 0);
 550         if (result < 0)
 551             where = where->left;
 552         else
 553             where = where->right;
 554     }
 555
 556     assert (where == nil);
 557
 558     if (result < 0)
 559         parent->left = node;
 560     else
 561         parent->right = node;
 562
 563     node->parent = parent;
 564     node->left = nil;
 565     node->right = nil;
 566
 567     dict->nodecount++;
 568
 569     /* red black adjustments */
 570
 571     node->color = dnode_red;
 572
 573     while (parent->color == dnode_red) {
 574         grandpa = parent->parent;
 575         if (parent == grandpa->left) {
 576             uncle = grandpa->right;
 577             if (uncle->color == dnode_red) {    /* red parent, red uncle */
 578                 parent->color = dnode_black;
 579                 uncle->color = dnode_black;
 580                 grandpa->color = dnode_red;
 581                 node = grandpa;
 582                 parent = grandpa->parent;
 583             } else {                            /* red parent, black uncle */
 584                 if (node == parent->right) {
 585                     rotate_left(parent);
 586                     parent = node;
 587                     assert (grandpa == parent->parent);
 588                     /* rotation between parent and child preserves grandpa */
 589                 }
 590                 parent->color = dnode_black;
 591                 grandpa->color = dnode_red;
 592                 rotate_right(grandpa);
 593                 break;
 594             }
 595         } else {        /* symmetric cases: parent == parent->parent->right */
 596             uncle = grandpa->left;
 597             if (uncle->color == dnode_red) {
 598                 parent->color = dnode_black;
 599                 uncle->color = dnode_black;
 600                 grandpa->color = dnode_red;
 601                 node = grandpa;
 602                 parent = grandpa->parent;
 603             } else {
 604                 if (node == parent->left) {
 605                     rotate_right(parent);
 606                     parent = node;
 607                     assert (grandpa == parent->parent);
 608                 }
 609                 parent->color = dnode_black;
 610                 grandpa->color = dnode_red;
 611                 rotate_left(grandpa);
 612                 break;
 613             }
 614         }
 615     }
 616
 617     dict_root(dict)->color = dnode_black;
 618
 619     assert (dict_verify(dict));
 620 }
 621
 622 /*
 623  * Delete the given node from the dictionary. If the given node does not belong
 624  * to the given dictionary, undefined behavior results.  A pointer to the
 625  * deleted node is returned.
 626  */
 627
 628 dnode_t *dict_delete(dict_t *dict, dnode_t *delete)
 629 {
 630     dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent;
 631
 632     /* basic deletion */
 633
 634     assert (!dict_isempty(dict));
 635     assert (dict_contains(dict, delete));
 636
 637     /*
 638      * If the node being deleted has two children, then we replace it with its
 639      * successor (i.e. the leftmost node in the right subtree.) By doing this,
 640      * we avoid the traditional algorithm under which the successor's key and
 641      * value *only* move to the deleted node and the successor is spliced out
 642      * from the tree. We cannot use this approach because the user may hold
 643      * pointers to the successor, or nodes may be inextricably tied to some
 644      * other structures by way of embedding, etc. So we must splice out the
 645      * node we are given, not some other node, and must not move contents from
 646      * one node to another behind the user's back.
 647      */
 648
 649     if (delete->left != nil && delete->right != nil) {
 650         dnode_t *next = dict_next(dict, delete);
 651         dnode_t *nextparent = next->parent;
 652         dnode_color_t nextcolor = next->color;
 653
 654         assert (next != nil);
 655         assert (next->parent != nil);
 656         assert (next->left == nil);
 657
 658         /*
 659          * First, splice out the successor from the tree completely, by
 660          * moving up its right child into its place.
 661          */
 662
 663         child = next->right;
 664         child->parent = nextparent;
 665
 666         if (nextparent->left == next) {
 667             nextparent->left = child;
 668         } else {
 669             assert (nextparent->right == next);
 670             nextparent->right = child;
 671         }
 672
 673         /*
 674          * Now that the successor has been extricated from the tree, install it
 675          * in place of the node that we want deleted.
 676          */
 677
 678         next->parent = delparent;
 679         next->left = delete->left;
 680         next->right = delete->right;
 681         next->left->parent = next;
 682         next->right->parent = next;
 683         next->color = delete->color;
 684         delete->color = nextcolor;
 685
 686         if (delparent->left == delete) {
 687             delparent->left = next;
 688         } else {
 689             assert (delparent->right == delete);
 690             delparent->right = next;
 691         }
 692
 693     } else {
 694         assert (delete != nil);
 695         assert (delete->left == nil || delete->right == nil);
 696
 697         child = (delete->left != nil) ? delete->left : delete->right;
 698
 699         child->parent = delparent = delete->parent;
 700
 701         if (delete == delparent->left) {
 702             delparent->left = child;
 703         } else {
 704             assert (delete == delparent->right);
 705             delparent->right = child;
 706         }
 707     }
 708
 709     delete->parent = NULL;
 710     delete->right = NULL;
 711     delete->left = NULL;
 712
 713     dict->nodecount--;
 714
 715     assert (verify_bintree(dict));
 716
 717     /* red-black adjustments */
 718
 719     if (delete->color == dnode_black) {
 720         dnode_t *parent, *sister;
 721
 722         dict_root(dict)->color = dnode_red;
 723
 724         while (child->color == dnode_black) {
 725             parent = child->parent;
 726             if (child == parent->left) {
 727                 sister = parent->right;
 728                 assert (sister != nil);
 729                 if (sister->color == dnode_red) {
 730                     sister->color = dnode_black;
 731                     parent->color = dnode_red;
 732                     rotate_left(parent);
 733                     sister = parent->right;
 734                     assert (sister != nil);
 735                 }
 736                 if (sister->left->color == dnode_black
 737                         && sister->right->color == dnode_black) {
 738                     sister->color = dnode_red;
 739                     child = parent;
 740                 } else {
 741                     if (sister->right->color == dnode_black) {
 742                         assert (sister->left->color == dnode_red);
 743                         sister->left->color = dnode_black;
 744                         sister->color = dnode_red;
 745                         rotate_right(sister);
 746                         sister = parent->right;
 747                         assert (sister != nil);
 748                     }
 749                     sister->color = parent->color;
 750                     sister->right->color = dnode_black;
 751                     parent->color = dnode_black;
 752                     rotate_left(parent);
 753                     break;
 754                 }
 755             } else {    /* symmetric case: child == child->parent->right */
 756                 assert (child == parent->right);
 757                 sister = parent->left;
 758                 assert (sister != nil);
 759                 if (sister->color == dnode_red) {
 760                     sister->color = dnode_black;
 761                     parent->color = dnode_red;
 762                     rotate_right(parent);
 763                     sister = parent->left;
 764                     assert (sister != nil);
 765                 }
 766                 if (sister->right->color == dnode_black
 767                         && sister->left->color == dnode_black) {
 768                     sister->color = dnode_red;
 769                     child = parent;
 770                 } else {
 771                     if (sister->left->color == dnode_black) {
 772                         assert (sister->right->color == dnode_red);
 773                         sister->right->color = dnode_black;
 774                         sister->color = dnode_red;
 775                         rotate_left(sister);
 776                         sister = parent->left;
 777                         assert (sister != nil);
 778                     }
 779                     sister->color = parent->color;
 780                     sister->left->color = dnode_black;
 781                     parent->color = dnode_black;
 782                     rotate_right(parent);
 783                     break;
 784                 }
 785             }
 786         }
 787
 788         child->color = dnode_black;
 789         dict_root(dict)->color = dnode_black;
 790     }
 791
 792     assert (dict_verify(dict));
 793
 794     return delete;
 795 }
 796
 797 /*
 798  * Allocate a node using the dictionary's allocator routine, give it
 799  * the data item.
 800  */
 801
 802 int dict_alloc_insert(dict_t *dict, const void *key, void *data)
 803 {
 804     dnode_t *node = dict->allocnode (dict->context);
 805
 806     if (node) {
 807         dnode_init(node, data);
 808         dict_insert(dict, node, key);
 809         return 1;
 810     }
 811     return 0;
 812 }
 813
 814 void dict_delete_free(dict_t *dict, dnode_t *node)
 815 {
 816     dict_delete(dict, node);
 817     dict->freenode(node, dict->context);
 818 }
 819
 820 /*
 821  * Return the node with the lowest (leftmost) key. If the dictionary is empty
 822  * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
 823  */
 824
 825 dnode_t *dict_first(dict_t *dict)
 826 {
 827     dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *left;
 828
 829     if (root != nil)
 830         while ((left = root->left) != nil)
 831             root = left;
 832
 833     return (root == nil) ? NULL : root;
 834 }
 835
 836 /*
 837  * Return the node with the highest (rightmost) key. If the dictionary is empty
 838  * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
 839  */
 840
 841 dnode_t *dict_last(dict_t *dict)
 842 {
 843     dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *right;
 844
 845     if (root != nil)
 846         while ((right = root->right) != nil)
 847             root = right;
 848
 849     return (root == nil) ? NULL : root;
 850 }
 851
 852 /*
 853  * Return the given node's successor node---the node which has the
 854  * next key in the the left to right ordering. If the node has
 855  * no successor, a null pointer is returned rather than a pointer to
 856  * the nil node.
 857  */
 858
 859 dnode_t *dict_next(dict_t *dict, dnode_t *curr)
 860 {
 861     dnode_t *nil = dict_nil(dict), *parent, *left;
 862
 863     if (curr->right != nil) {
 864         curr = curr->right;
 865         while ((left = curr->left) != nil)
 866             curr = left;
 867         return curr;
 868     }
 869
 870     parent = curr->parent;
 871
 872     while (parent != nil && curr == parent->right) {
 873         curr = parent;
 874         parent = curr->parent;
 875     }
 876
 877     return (parent == nil) ? NULL : parent;
 878 }
 879
 880 /*
 881  * Return the given node's predecessor, in the key order.
 882  * The nil sentinel node is returned if there is no predecessor.
 883  */
 884
 885 dnode_t *dict_prev(dict_t *dict, dnode_t *curr)
 886 {
 887     dnode_t *nil = dict_nil(dict), *parent, *right;
 888
 889     if (curr->left != nil) {
 890         curr = curr->left;
 891         while ((right = curr->right) != nil)
 892             curr = right;
 893         return curr;
 894     }
 895
 896     parent = curr->parent;
 897
 898     while (parent != nil && curr == parent->left) {
 899         curr = parent;
 900         parent = curr->parent;
 901     }
 902
 903     return (parent == nil) ? NULL : parent;
 904 }
 905
 906 void dict_allow_dupes(dict_t *dict)
 907 {
 908     dict->dupes = 1;
 909 }
 910
 911 #undef dict_count
 912 #undef dict_isempty
 913 #undef dict_isfull
 914 #undef dnode_get
 915 #undef dnode_put
 916 #undef dnode_getkey
 917
 918 dictcount_t dict_count(dict_t *dict)
 919 {
 920     return dict->nodecount;
 921 }
 922
 923 int dict_isempty(dict_t *dict)
 924 {
 925     return dict->nodecount == 0;
 926 }
 927
 928 int dict_isfull(dict_t *dict)
 929 {
 930     return dict->nodecount == dict->maxcount;
 931 }
 932
 933 int dict_contains(dict_t *dict, dnode_t *node)
 934 {
 935     return verify_dict_has_node(dict_nil(dict), dict_root(dict), node);
 936 }
 937
 938 static dnode_t *dnode_alloc(void *context)
 939 {
 940     return XCALLOC(MTYPE_ISIS_DICT_NODE, sizeof(dnode_t));
 941 }
 942
 943 static void dnode_free(dnode_t *node, void *context)
 944 {
 945     XFREE(MTYPE_ISIS_DICT_NODE, node);
 946 }
 947
 948 dnode_t *dnode_create(void *data)
 949 {
 950     dnode_t *new = XCALLOC(MTYPE_ISIS_DICT_NODE, sizeof(dnode_t));
 951     if (new) {
 952         new->data = data;
 953         new->parent = NULL;
 954         new->left = NULL;
 955         new->right = NULL;
 956     }
 957     return new;
 958 }
 959
 960 dnode_t *dnode_init(dnode_t *dnode, void *data)
 961 {
 962     dnode->data = data;
 963     dnode->parent = NULL;
 964     dnode->left = NULL;
 965     dnode->right = NULL;
 966     return dnode;
 967 }
 968
 969 void dnode_destroy(dnode_t *dnode)
 970 {
 971     assert (!dnode_is_in_a_dict(dnode));
 972     XFREE(MTYPE_ISIS_DICT_NODE, dnode);
 973 }
 974
 975 void *dnode_get(dnode_t *dnode)
 976 {
 977     return dnode->data;
 978 }
 979
 980 const void *dnode_getkey(dnode_t *dnode)
 981 {
 982     return dnode->key;
 983 }
 984
 985 void dnode_put(dnode_t *dnode, void *data)
 986 {
 987     dnode->data = data;
 988 }
 989
 990 int dnode_is_in_a_dict(dnode_t *dnode)
 991 {
 992     return (dnode->parent && dnode->left && dnode->right);
 993 }
 994
 995 void dict_process(dict_t *dict, void *context, dnode_process_t function)
 996 {
 997     dnode_t *node = dict_first(dict), *next;
 998
 999     while (node != NULL) {
1000         /* check for callback function deleting */
1001         /* the next node from under us          */
1002         assert (dict_contains(dict, node));
1003         next = dict_next(dict, node);
1004         function(dict, node, context);
1005         node = next;
1006     }
1007 }
1008
1009 static void load_begin_internal(dict_load_t *load, dict_t *dict)
1010 {
1011     load->dictptr = dict;
1012     load->nilnode.left = &load->nilnode;
1013     load->nilnode.right = &load->nilnode;
1014 }
1015
1016 void dict_load_begin(dict_load_t *load, dict_t *dict)
1017 {
1018     assert (dict_isempty(dict));
1019     load_begin_internal(load, dict);
1020 }
1021
1022 void dict_load_next(dict_load_t *load, dnode_t *newnode, const void *key)
1023 {
1024     dict_t *dict = load->dictptr;
1025     dnode_t *nil = &load->nilnode;
1026
1027     assert (!dnode_is_in_a_dict(newnode));
1028     assert (dict->nodecount < dict->maxcount);
1029
1030     #ifndef NDEBUG
1031     if (dict->nodecount > 0) {
1032         if (dict->dupes)
1033             assert (dict->compare(nil->left->key, key) <= 0);
1034         else
1035             assert (dict->compare(nil->left->key, key) < 0);
1036     }
1037     #endif
1038
1039     newnode->key = key;
1040     nil->right->left = newnode;
1041     nil->right = newnode;
1042     newnode->left = nil;
1043     dict->nodecount++;
1044 }
1045
1046 void dict_load_end(dict_load_t *load)
1047 {
1048     dict_t *dict = load->dictptr;
1049     dnode_t *tree[DICT_DEPTH_MAX] = { 0 };
1050     dnode_t *curr, *dictnil = dict_nil(dict), *loadnil = &load->nilnode, *next;
1051     dnode_t *complete = 0;
1052     dictcount_t fullcount = DICTCOUNT_T_MAX, nodecount = dict->nodecount;
1053     dictcount_t botrowcount;
1054     unsigned baselevel = 0, level = 0, i;
1055
1056     assert (dnode_red == 0 && dnode_black == 1);
1057
1058     while (fullcount >= nodecount && fullcount)
1059         fullcount >>= 1;
1060
1061     botrowcount = nodecount - fullcount;
1062
1063     for (curr = loadnil->left; curr != loadnil; curr = next) {
1064         next = curr->left;
1065
1066         if (complete == NULL && botrowcount-- == 0) {
1067             assert (baselevel == 0);
1068             assert (level == 0);
1069             baselevel = level = 1;
1070             complete = tree[0];
1071
1072             if (complete != 0) {
1073                 tree[0] = 0;
1074                 complete->right = dictnil;
1075                 while (tree[level] != 0) {
1076                     tree[level]->right = complete;
1077                     complete->parent = tree[level];
1078                     complete = tree[level];
1079                     tree[level++] = 0;
1080                 }
1081             }
1082         }
1083
1084         if (complete == NULL) {
1085             curr->left = dictnil;
1086             curr->right = dictnil;
1087             curr->color = level % 2;
1088             complete = curr;
1089
1090             assert (level == baselevel);
1091             while (tree[level] != 0) {
1092                 tree[level]->right = complete;
1093                 complete->parent = tree[level];
1094                 complete = tree[level];
1095                 tree[level++] = 0;
1096             }
1097         } else {
1098             curr->left = complete;
1099             curr->color = (level + 1) % 2;
1100             complete->parent = curr;
1101             tree[level] = curr;
1102             complete = 0;
1103             level = baselevel;
1104         }
1105     }
1106
1107     if (complete == NULL)
1108         complete = dictnil;
1109
1110     for (i = 0; i < DICT_DEPTH_MAX; i++) {
1111         if (tree[i] != 0) {
1112             tree[i]->right = complete;
1113             complete->parent = tree[i];
1114             complete = tree[i];
1115         }
1116     }
1117
1118     dictnil->color = dnode_black;
1119     dictnil->right = dictnil;
1120     complete->parent = dictnil;
1121     complete->color = dnode_black;
1122     dict_root(dict) = complete;
1123
1124     assert (dict_verify(dict));
1125 }
1126
1127 void dict_merge(dict_t *dest, dict_t *source)
1128 {
1129     dict_load_t load;
1130     dnode_t *leftnode = dict_first(dest), *rightnode = dict_first(source);
1131
1132     assert (dict_similar(dest, source));
1133
1134     if (source == dest)
1135         return;
1136
1137     dest->nodecount = 0;
1138     load_begin_internal(&load, dest);
1139
1140     for (;;) {
1141         if (leftnode != NULL && rightnode != NULL) {
1142             if (dest->compare(leftnode->key, rightnode->key) < 0)
1143                 goto copyleft;
1144             else
1145                 goto copyright;
1146         } else if (leftnode != NULL) {
1147             goto copyleft;
1148         } else if (rightnode != NULL) {
1149             goto copyright;
1150         } else {
1151             assert (leftnode == NULL && rightnode == NULL);
1152             break;
1153         }
1154
1155     copyleft:
1156         {
1157             dnode_t *next = dict_next(dest, leftnode);
1158             #ifndef NDEBUG
1159             leftnode->left = NULL;      /* suppress assertion in dict_load_next */
1160             #endif
1161             dict_load_next(&load, leftnode, leftnode->key);
1162             leftnode = next;
1163             continue;
1164         }
1165
1166     copyright:
1167         {
1168             dnode_t *next = dict_next(source, rightnode);
1169             #ifndef NDEBUG
1170             rightnode->left = NULL;
1171             #endif
1172             dict_load_next(&load, rightnode, rightnode->key);
1173             rightnode = next;
1174             continue;
1175         }
1176     }
1177
1178     dict_clear(source);
1179     dict_load_end(&load);
1180 }
1181
1182 #ifdef KAZLIB_TEST_MAIN
1183
1184 #include <stdio.h>
1185 #include <string.h>
1186 #include <ctype.h>
1187 #include <stdarg.h>
1188
1189 typedef char input_t[256];
1190
1191 static int tokenize(char *string, ...)
1192 {
1193     char **tokptr;
1194     va_list arglist;
1195     int tokcount = 0;
1196
1197     va_start(arglist, string);
1198     tokptr = va_arg(arglist, char **);
1199     while (tokptr) {
1200         while (*string && isspace((unsigned char) *string))
1201             string++;
1202         if (!*string)
1203             break;
1204         *tokptr = string;
1205         while (*string && !isspace((unsigned char) *string))
1206             string++;
1207         tokptr = va_arg(arglist, char **);
1208         tokcount++;
1209         if (!*string)
1210             break;
1211         *string++ = 0;
1212     }
1213     va_end(arglist);
1214
1215     return tokcount;
1216 }
1217
1218 static int comparef(const void *key1, const void *key2)
1219 {
1220     return strcmp(key1, key2);
1221 }
1222
1223 static char *dupstring(char *str)
1224 {
1225     int sz = strlen(str) + 1;
1226     char *new = XCALLOC(MTYPE_ISIS_TMP, sz);
1227     if (new)
1228         memcpy(new, str, sz);
1229     return new;
1230 }
1231
1232 static dnode_t *new_node(void *c)
1233 {
1234     static dnode_t few[5];
1235     static int count;
1236
1237     if (count < 5)
1238         return few + count++;
1239
1240     return NULL;
1241 }
1242
1243 static void del_node(dnode_t *n, void *c)
1244 {
1245 }
1246
1247 static int prompt = 0;
1248
1249 static void construct(dict_t *d)
1250 {
1251     input_t in;
1252     int done = 0;
1253     dict_load_t dl;
1254     dnode_t *dn;
1255     char *tok1, *tok2, *val;
1256     const char *key;
1257     char *help =
1258         "p                      turn prompt on\n"
1259         "q                      finish construction\n"
1260         "a <key> <val>          add new entry\n";
1261
1262     if (!dict_isempty(d))
1263         puts("warning: dictionary not empty!");
1264
1265     dict_load_begin(&dl, d);
1266
1267     while (!done) {
1268         if (prompt)
1269             putchar('>');
1270         fflush(stdout);
1271
1272         if (!fgets(in, sizeof(input_t), stdin))
1273             break;
1274
1275         switch (in[0]) {
1276             case '?':
1277                 puts(help);
1278                 break;
1279             case 'p':
1280                 prompt = 1;
1281                 break;
1282             case 'q':
1283                 done = 1;
1284                 break;
1285             case 'a':
1286                 if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) {
1287                     puts("what?");
1288                     break;
1289                 }
1290                 key = dupstring(tok1);
1291                 val = dupstring(tok2);
1292                 dn = dnode_create(val);
1293
1294                 if (!key || !val || !dn) {
1295                     puts("out of memory");
1296                     free((void *) key);
1297                     free(val);
1298                     if (dn)
1299                         dnode_destroy(dn);
1300                 }
1301
1302                 dict_load_next(&dl, dn, key);
1303                 break;
1304             default:
1305                 putchar('?');
1306                 putchar('\n');
1307                 break;
1308         }
1309     }
1310
1311     dict_load_end(&dl);
1312 }
1313
1314 int main(void)
1315 {
1316     input_t in;
1317     dict_t darray[10];
1318     dict_t *d = &darray[0];
1319     dnode_t *dn;
1320     int i;
1321     char *tok1, *tok2, *val;
1322     const char *key;
1323
1324     char *help =
1325         "a <key> <val>          add value to dictionary\n"
1326         "d <key>                delete value from dictionary\n"
1327         "l <key>                lookup value in dictionary\n"
1328         "( <key>                lookup lower bound\n"
1329         ") <key>                lookup upper bound\n"
1330         "# <num>                switch to alternate dictionary (0-9)\n"
1331         "j <num> <num>          merge two dictionaries\n"
1332         "f                      free the whole dictionary\n"
1333         "k                      allow duplicate keys\n"
1334         "c                      show number of entries\n"
1335         "t                      dump whole dictionary in sort order\n"
1336         "m                      make dictionary out of sorted items\n"
1337         "p                      turn prompt on\n"
1338         "s                      switch to non-functioning allocator\n"
1339         "q                      quit";
1340
1341     for (i = 0; i < 10; i++)
1342         dict_init(&darray[i], DICTCOUNT_T_MAX, comparef);
1343
1344     for (;;) {
1345         if (prompt)
1346             putchar('>');
1347         fflush(stdout);
1348
1349         if (!fgets(in, sizeof(input_t), stdin))
1350             break;
1351
1352         switch(in[0]) {
1353             case '?':
1354                 puts(help);
1355                 break;
1356             case 'a':
1357                 if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) {
1358                     puts("what?");
1359                     break;
1360                 }
1361                 key = dupstring(tok1);
1362                 val = dupstring(tok2);
1363
1364                 if (!key || !val) {
1365                     puts("out of memory");
1366                     free((void *) key);
1367                     free(val);
1368                 }
1369
1370                 if (!dict_alloc_insert(d, key, val)) {
1371                     puts("dict_alloc_insert failed");
1372                     free((void *) key);
1373                     free(val);
1374                     break;
1375                 }
1376                 break;
1377             case 'd':
1378                 if (tokenize(in+1, &tok1, (char **) 0) != 1) {
1379                     puts("what?");
1380                     break;
1381                 }
1382                 dn = dict_lookup(d, tok1);
1383                 if (!dn) {
1384                     puts("dict_lookup failed");
1385                     break;
1386                 }
1387                 val = dnode_get(dn);
1388                 key = dnode_getkey(dn);
1389                 dict_delete_free(d, dn);
1390
1391                 free(val);
1392                 free((void *) key);
1393                 break;
1394             case 'f':
1395                 dict_free(d);
1396                 break;
1397             case 'l':
1398             case '(':
1399             case ')':
1400                 if (tokenize(in+1, &tok1, (char **) 0) != 1) {
1401                     puts("what?");
1402                     break;
1403                 }
1404                 dn = 0;
1405                 switch (in[0]) {
1406                 case 'l':
1407                     dn = dict_lookup(d, tok1);
1408                     break;
1409                 case '(':
1410                     dn = dict_lower_bound(d, tok1);
1411                     break;
1412                 case ')':
1413                     dn = dict_upper_bound(d, tok1);
1414                     break;
1415                 }
1416                 if (!dn) {
1417                     puts("lookup failed");
1418                     break;
1419                 }
1420                 val = dnode_get(dn);
1421                 puts(val);
1422                 break;
1423             case 'm':
1424                 construct(d);
1425                 break;
1426             case 'k':
1427                 dict_allow_dupes(d);
1428                 break;
1429             case 'c':
1430                 printf("%lu\n", (unsigned long) dict_count(d));
1431                 break;
1432             case 't':
1433                 for (dn = dict_first(d); dn; dn = dict_next(d, dn)) {
1434                     printf("%s\t%s\n", (char *) dnode_getkey(dn),
1435                             (char *) dnode_get(dn));
1436                 }
1437                 break;
1438             case 'q':
1439                 exit(0);
1440                 break;
1441             case '\0':
1442                 break;
1443             case 'p':
1444                 prompt = 1;
1445                 break;
1446             case 's':
1447                 dict_set_allocator(d, new_node, del_node, NULL);
1448                 break;
1449             case '#':
1450                 if (tokenize(in+1, &tok1, (char **) 0) != 1) {
1451                     puts("what?");
1452                     break;
1453                 } else {
1454                     int dictnum = atoi(tok1);
1455                     if (dictnum < 0 || dictnum > 9) {
1456                         puts("invalid number");
1457                         break;
1458                     }
1459                     d = &darray[dictnum];
1460                 }
1461                 break;
1462             case 'j':
1463                 if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) {
1464                     puts("what?");
1465                     break;
1466                 } else {
1467                     int dict1 = atoi(tok1), dict2 = atoi(tok2);
1468                     if (dict1 < 0 || dict1 > 9 || dict2 < 0 || dict2 > 9) {
1469                         puts("invalid number");
1470                         break;
1471                     }
1472                     dict_merge(&darray[dict1], &darray[dict2]);
1473                 }
1474                 break;
1475             default:
1476                 putchar('?');
1477                 putchar('\n');
1478                 break;
1479         }
1480     }
1481
1482     return 0;
1483 }
1484
1485 #endif