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