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 36static 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 73static dnode_t *dnode_alloc(void *context); 74static 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 83static 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 112static 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 138static 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 156static 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 191static 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 222static 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 239static 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 255dict_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 280void 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 297void 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 309void 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 */ 322void 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 335dict_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 356void 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 377static 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 394int 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 426int 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 454dnode_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 493dnode_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 525dnode_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 561void 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 659dnode_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 834int 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 847void 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 859dnode_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 875dnode_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 893dnode_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 919dnode_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 940void 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 952dictcount_t dict_count(dict_t *dict) 953{ 954 return dict->nodecount; 955} 956 957int dict_isempty(dict_t *dict) 958{ 959 return dict->nodecount == 0; 960} 961 962int dict_isfull(dict_t *dict) 963{ 964 return dict->nodecount == dict->maxcount; 965} 966 967int dict_contains(dict_t *dict, dnode_t *node) 968{ 969 return verify_dict_has_node(dict_nil(dict), dict_root(dict), node); 970} 971 972static dnode_t *dnode_alloc(void *context EXT2FS_ATTR((unused))) 973{ 974 return malloc(sizeof *dnode_alloc(NULL)); 975} 976 977static void dnode_free(dnode_t *node, void *context EXT2FS_ATTR((unused))) 978{ 979 free(node); 980} 981 982dnode_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 994dnode_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 1003void dnode_destroy(dnode_t *dnode) 1004{ 1005 assert (!dnode_is_in_a_dict(dnode)); 1006 free(dnode); 1007} 1008 1009void *dnode_get(dnode_t *dnode) 1010{ 1011 return dnode->data; 1012} 1013 1014const void *dnode_getkey(dnode_t *dnode) 1015{ 1016 return dnode->key; 1017} 1018 1019#ifdef E2FSCK_NOTUSED 1020void dnode_put(dnode_t *dnode, void *data) 1021{ 1022 dnode->data = data; 1023} 1024 1025int dnode_is_in_a_dict(dnode_t *dnode) 1026{ 1027 return (dnode->parent && dnode->left && dnode->right); 1028} 1029 1030void 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 1044static 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 1051void dict_load_begin(dict_load_t *load, dict_t *dict) 1052{ 1053 assert (dict_isempty(dict)); 1054 load_begin_internal(load, dict); 1055} 1056 1057void 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 1081void 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 1162void 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 1225typedef char input_t[256]; 1226 1227static 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 1254static int comparef(const void *key1, const void *key2) 1255{ 1256 return strcmp(key1, key2); 1257} 1258 1259static 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 1268static 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 1279static void del_node(dnode_t *n, void *c) 1280{ 1281} 1282 1283static int prompt = 0; 1284 1285static 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 1350int 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 1522