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