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