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