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