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