2 * Dictionary Abstract Data Type
3 * Copyright (C) 1997 Kaz Kylheku <kaz@ashi.footprints.net>
5 * Free Software License:
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.
17 * $Id: dict.c,v 1.40.2.7 2000/11/13 01:36:44 kaz Exp $
18 * $Name: kazlib_1_20 $
24 #define EXT2FS_ATTR(x) __attribute__(x)
26 #define EXT2FS_ATTR(x)
33 #define DICT_IMPLEMENTATION
37 static const char rcsid[] = "$Id: dict.c,v 1.40.2.7 2000/11/13 01:36:44 kaz Exp $";
41 * These macros provide short convenient names for structure members,
42 * which are embellished with dict_ prefixes so that they are
43 * properly confined to the documented namespace. It's legal for a
44 * program which uses dict to define, for instance, a macro called ``parent''.
45 * Such a macro would interfere with the dnode_t struct definition.
46 * In general, highly portable and reusable C modules which expose their
47 * structures need to confine structure member names to well-defined spaces.
48 * The resulting identifiers aren't necessarily convenient to use, nor
49 * readable, in the implementation, however!
52 #define left dict_left
53 #define right dict_right
54 #define parent dict_parent
55 #define color dict_color
57 #define data dict_data
59 #define nilnode dict_nilnode
60 #define nodecount dict_nodecount
61 #define maxcount dict_maxcount
62 #define compare dict_compare
63 #define allocnode dict_allocnode
64 #define freenode dict_freenode
65 #define context dict_context
66 #define dupes dict_dupes
68 #define dictptr dict_dictptr
70 #define dict_root(D) ((D)->nilnode.left)
71 #define dict_nil(D) (&(D)->nilnode)
72 #define DICT_DEPTH_MAX 64
74 static dnode_t *dnode_alloc(void *context);
75 static void dnode_free(dnode_t *node, void *context);
78 * Perform a ``left rotation'' adjustment on the tree. The given node P and
79 * its right child C are rearranged so that the P instead becomes the left
80 * child of C. The left subtree of C is inherited as the new right subtree
81 * for P. The ordering of the keys within the tree is thus preserved.
84 static void rotate_left(dnode_t *upper)
86 dnode_t *lower, *lowleft, *upparent;
89 upper->right = lowleft = lower->left;
90 lowleft->parent = upper;
92 lower->parent = upparent = upper->parent;
94 /* don't need to check for root node here because root->parent is
95 the sentinel nil node, and root->parent->left points back to root */
97 if (upper == upparent->left) {
98 upparent->left = lower;
100 assert (upper == upparent->right);
101 upparent->right = lower;
105 upper->parent = lower;
109 * This operation is the ``mirror'' image of rotate_left. It is
110 * the same procedure, but with left and right interchanged.
113 static void rotate_right(dnode_t *upper)
115 dnode_t *lower, *lowright, *upparent;
118 upper->left = lowright = lower->right;
119 lowright->parent = upper;
121 lower->parent = upparent = upper->parent;
123 if (upper == upparent->right) {
124 upparent->right = lower;
126 assert (upper == upparent->left);
127 upparent->left = lower;
130 lower->right = upper;
131 upper->parent = lower;
135 * Do a postorder traversal of the tree rooted at the specified
136 * node and free everything under it. Used by dict_free().
139 static void free_nodes(dict_t *dict, dnode_t *node, dnode_t *nil)
143 free_nodes(dict, node->left, nil);
144 free_nodes(dict, node->right, nil);
145 dict->freenode(node, dict->context);
149 * This procedure performs a verification that the given subtree is a binary
150 * search tree. It performs an inorder traversal of the tree using the
151 * dict_next() successor function, verifying that the key of each node is
152 * strictly lower than that of its successor, if duplicates are not allowed,
153 * or lower or equal if duplicates are allowed. This function is used for
154 * debugging purposes.
157 static int verify_bintree(dict_t *dict)
159 dnode_t *first, *next;
161 first = dict_first(dict);
164 while (first && (next = dict_next(dict, first))) {
165 if (dict->compare(first->key, next->key) > 0)
170 while (first && (next = dict_next(dict, first))) {
171 if (dict->compare(first->key, next->key) >= 0)
180 * This function recursively verifies that the given binary subtree satisfies
181 * three of the red black properties. It checks that every red node has only
182 * black children. It makes sure that each node is either red or black. And it
183 * checks that every path has the same count of black nodes from root to leaf.
184 * It returns the blackheight of the given subtree; this allows blackheights to
185 * be computed recursively and compared for left and right siblings for
186 * mismatches. It does not check for every nil node being black, because there
187 * is only one sentinel nil node. The return value of this function is the
188 * black height of the subtree rooted at the node ``root'', or zero if the
189 * subtree is not red-black.
192 static unsigned int verify_redblack(dnode_t *nil, dnode_t *root)
194 unsigned height_left, height_right;
197 height_left = verify_redblack(nil, root->left);
198 height_right = verify_redblack(nil, root->right);
199 if (height_left == 0 || height_right == 0)
201 if (height_left != height_right)
203 if (root->color == dnode_red) {
204 if (root->left->color != dnode_black)
206 if (root->right->color != dnode_black)
210 if (root->color != dnode_black)
212 return height_left + 1;
218 * Compute the actual count of nodes by traversing the tree and
219 * return it. This could be compared against the stored count to
223 static dictcount_t verify_node_count(dnode_t *nil, dnode_t *root)
228 return 1 + verify_node_count(nil, root->left)
229 + verify_node_count(nil, root->right);
234 * Verify that the tree contains the given node. This is done by
235 * traversing all of the nodes and comparing their pointers to the
236 * given pointer. Returns 1 if the node is found, otherwise
237 * returns zero. It is intended for debugging purposes.
240 static int verify_dict_has_node(dnode_t *nil, dnode_t *root, dnode_t *node)
244 || verify_dict_has_node(nil, root->left, node)
245 || verify_dict_has_node(nil, root->right, node);
251 #ifdef E2FSCK_NOTUSED
253 * Dynamically allocate and initialize a dictionary object.
256 dict_t *dict_create(dictcount_t maxcount, dict_comp_t comp)
258 dict_t *new = malloc(sizeof *new);
262 new->allocnode = dnode_alloc;
263 new->freenode = dnode_free;
266 new->maxcount = maxcount;
267 new->nilnode.left = &new->nilnode;
268 new->nilnode.right = &new->nilnode;
269 new->nilnode.parent = &new->nilnode;
270 new->nilnode.color = dnode_black;
275 #endif /* E2FSCK_NOTUSED */
278 * Select a different set of node allocator routines.
281 void dict_set_allocator(dict_t *dict, dnode_alloc_t al,
282 dnode_free_t fr, void *context)
284 assert (dict_count(dict) == 0);
285 assert ((al == NULL && fr == NULL) || (al != NULL && fr != NULL));
287 dict->allocnode = al ? al : dnode_alloc;
288 dict->freenode = fr ? fr : dnode_free;
289 dict->context = context;
292 #ifdef E2FSCK_NOTUSED
294 * Free a dynamically allocated dictionary object. Removing the nodes
295 * from the tree before deleting it is required.
298 void dict_destroy(dict_t *dict)
300 assert (dict_isempty(dict));
306 * Free all the nodes in the dictionary by using the dictionary's
307 * installed free routine. The dictionary is emptied.
310 void dict_free_nodes(dict_t *dict)
312 dnode_t *nil = dict_nil(dict), *root = dict_root(dict);
313 free_nodes(dict, root, nil);
315 dict->nilnode.left = &dict->nilnode;
316 dict->nilnode.right = &dict->nilnode;
319 #ifdef E2FSCK_NOTUSED
321 * Obsolescent function, equivalent to dict_free_nodes
323 void dict_free(dict_t *dict)
325 #ifdef KAZLIB_OBSOLESCENT_DEBUG
326 assert ("call to obsolescent function dict_free()" && 0);
328 dict_free_nodes(dict);
333 * Initialize a user-supplied dictionary object.
336 dict_t *dict_init(dict_t *dict, dictcount_t maxcount, dict_comp_t comp)
338 dict->compare = comp;
339 dict->allocnode = dnode_alloc;
340 dict->freenode = dnode_free;
341 dict->context = NULL;
343 dict->maxcount = maxcount;
344 dict->nilnode.left = &dict->nilnode;
345 dict->nilnode.right = &dict->nilnode;
346 dict->nilnode.parent = &dict->nilnode;
347 dict->nilnode.color = dnode_black;
352 #ifdef E2FSCK_NOTUSED
354 * Initialize a dictionary in the likeness of another dictionary
357 void dict_init_like(dict_t *dict, const dict_t *template)
359 dict->compare = template->compare;
360 dict->allocnode = template->allocnode;
361 dict->freenode = template->freenode;
362 dict->context = template->context;
364 dict->maxcount = template->maxcount;
365 dict->nilnode.left = &dict->nilnode;
366 dict->nilnode.right = &dict->nilnode;
367 dict->nilnode.parent = &dict->nilnode;
368 dict->nilnode.color = dnode_black;
369 dict->dupes = template->dupes;
371 assert (dict_similar(dict, template));
375 * Remove all nodes from the dictionary (without freeing them in any way).
378 static void dict_clear(dict_t *dict)
381 dict->nilnode.left = &dict->nilnode;
382 dict->nilnode.right = &dict->nilnode;
383 dict->nilnode.parent = &dict->nilnode;
384 assert (dict->nilnode.color == dnode_black);
389 * Verify the integrity of the dictionary structure. This is provided for
390 * debugging purposes, and should be placed in assert statements. Just because
391 * this function succeeds doesn't mean that the tree is not corrupt. Certain
392 * corruptions in the tree may simply cause undefined behavior.
395 int dict_verify(dict_t *dict)
398 dnode_t *nil = dict_nil(dict), *root = dict_root(dict);
400 /* check that the sentinel node and root node are black */
401 if (root->color != dnode_black)
403 if (nil->color != dnode_black)
405 if (nil->right != nil)
407 /* nil->left is the root node; check that its parent pointer is nil */
408 if (nil->left->parent != nil)
410 /* perform a weak test that the tree is a binary search tree */
411 if (!verify_bintree(dict))
413 /* verify that the tree is a red-black tree */
414 if (!verify_redblack(nil, root))
416 if (verify_node_count(nil, root) != dict_count(dict))
423 * Determine whether two dictionaries are similar: have the same comparison and
424 * allocator functions, and same status as to whether duplicates are allowed.
427 int dict_similar(const dict_t *left, const dict_t *right)
429 if (left->compare != right->compare)
432 if (left->allocnode != right->allocnode)
435 if (left->freenode != right->freenode)
438 if (left->context != right->context)
441 if (left->dupes != right->dupes)
446 #endif /* E2FSCK_NOTUSED */
449 * Locate a node in the dictionary having the given key.
450 * If the node is not found, a null a pointer is returned (rather than
451 * a pointer that dictionary's nil sentinel node), otherwise a pointer to the
452 * located node is returned.
455 dnode_t *dict_lookup(dict_t *dict, const void *key)
457 dnode_t *root = dict_root(dict);
458 dnode_t *nil = dict_nil(dict);
462 /* simple binary search adapted for trees that contain duplicate keys */
464 while (root != nil) {
465 result = dict->compare(key, root->key);
471 if (!dict->dupes) { /* no duplicates, return match */
473 } else { /* could be dupes, find leftmost one */
477 while (root != nil && dict->compare(key, root->key))
479 } while (root != nil);
488 #ifdef E2FSCK_NOTUSED
490 * Look for the node corresponding to the lowest key that is equal to or
491 * greater than the given key. If there is no such node, return null.
494 dnode_t *dict_lower_bound(dict_t *dict, const void *key)
496 dnode_t *root = dict_root(dict);
497 dnode_t *nil = dict_nil(dict);
498 dnode_t *tentative = 0;
500 while (root != nil) {
501 int result = dict->compare(key, root->key);
505 } else if (result < 0) {
522 * Look for the node corresponding to the greatest key that is equal to or
523 * lower than the given key. If there is no such node, return null.
526 dnode_t *dict_upper_bound(dict_t *dict, const void *key)
528 dnode_t *root = dict_root(dict);
529 dnode_t *nil = dict_nil(dict);
530 dnode_t *tentative = 0;
532 while (root != nil) {
533 int result = dict->compare(key, root->key);
537 } else if (result > 0) {
555 * Insert a node into the dictionary. The node should have been
556 * initialized with a data field. All other fields are ignored.
557 * The behavior is undefined if the user attempts to insert into
558 * a dictionary that is already full (for which the dict_isfull()
559 * function returns true).
562 void dict_insert(dict_t *dict, dnode_t *node, const void *key)
564 dnode_t *where = dict_root(dict), *nil = dict_nil(dict);
565 dnode_t *parent = nil, *uncle, *grandpa;
570 assert (!dict_isfull(dict));
571 assert (!dict_contains(dict, node));
572 assert (!dnode_is_in_a_dict(node));
574 /* basic binary tree insert */
576 while (where != nil) {
578 result = dict->compare(key, where->key);
579 /* trap attempts at duplicate key insertion unless it's explicitly allowed */
580 assert (dict->dupes || result != 0);
584 where = where->right;
587 assert (where == nil);
592 parent->right = node;
594 node->parent = parent;
600 /* red black adjustments */
602 node->color = dnode_red;
604 while (parent->color == dnode_red) {
605 grandpa = parent->parent;
606 if (parent == grandpa->left) {
607 uncle = grandpa->right;
608 if (uncle->color == dnode_red) { /* red parent, red uncle */
609 parent->color = dnode_black;
610 uncle->color = dnode_black;
611 grandpa->color = dnode_red;
613 parent = grandpa->parent;
614 } else { /* red parent, black uncle */
615 if (node == parent->right) {
618 assert (grandpa == parent->parent);
619 /* rotation between parent and child preserves grandpa */
621 parent->color = dnode_black;
622 grandpa->color = dnode_red;
623 rotate_right(grandpa);
626 } else { /* symmetric cases: parent == parent->parent->right */
627 uncle = grandpa->left;
628 if (uncle->color == dnode_red) {
629 parent->color = dnode_black;
630 uncle->color = dnode_black;
631 grandpa->color = dnode_red;
633 parent = grandpa->parent;
635 if (node == parent->left) {
636 rotate_right(parent);
638 assert (grandpa == parent->parent);
640 parent->color = dnode_black;
641 grandpa->color = dnode_red;
642 rotate_left(grandpa);
648 dict_root(dict)->color = dnode_black;
650 assert (dict_verify(dict));
653 #ifdef E2FSCK_NOTUSED
655 * Delete the given node from the dictionary. If the given node does not belong
656 * to the given dictionary, undefined behavior results. A pointer to the
657 * deleted node is returned.
660 dnode_t *dict_delete(dict_t *dict, dnode_t *delete)
662 dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent;
666 assert (!dict_isempty(dict));
667 assert (dict_contains(dict, delete));
670 * If the node being deleted has two children, then we replace it with its
671 * successor (i.e. the leftmost node in the right subtree.) By doing this,
672 * we avoid the traditional algorithm under which the successor's key and
673 * value *only* move to the deleted node and the successor is spliced out
674 * from the tree. We cannot use this approach because the user may hold
675 * pointers to the successor, or nodes may be inextricably tied to some
676 * other structures by way of embedding, etc. So we must splice out the
677 * node we are given, not some other node, and must not move contents from
678 * one node to another behind the user's back.
681 if (delete->left != nil && delete->right != nil) {
682 dnode_t *next = dict_next(dict, delete);
683 dnode_t *nextparent = next->parent;
684 dnode_color_t nextcolor = next->color;
686 assert (next != nil);
687 assert (next->parent != nil);
688 assert (next->left == nil);
691 * First, splice out the successor from the tree completely, by
692 * moving up its right child into its place.
696 child->parent = nextparent;
698 if (nextparent->left == next) {
699 nextparent->left = child;
701 assert (nextparent->right == next);
702 nextparent->right = child;
706 * Now that the successor has been extricated from the tree, install it
707 * in place of the node that we want deleted.
710 next->parent = delparent;
711 next->left = delete->left;
712 next->right = delete->right;
713 next->left->parent = next;
714 next->right->parent = next;
715 next->color = delete->color;
716 delete->color = nextcolor;
718 if (delparent->left == delete) {
719 delparent->left = next;
721 assert (delparent->right == delete);
722 delparent->right = next;
726 assert (delete != nil);
727 assert (delete->left == nil || delete->right == nil);
729 child = (delete->left != nil) ? delete->left : delete->right;
731 child->parent = delparent = delete->parent;
733 if (delete == delparent->left) {
734 delparent->left = child;
736 assert (delete == delparent->right);
737 delparent->right = child;
741 delete->parent = NULL;
742 delete->right = NULL;
747 assert (verify_bintree(dict));
749 /* red-black adjustments */
751 if (delete->color == dnode_black) {
752 dnode_t *parent, *sister;
754 dict_root(dict)->color = dnode_red;
756 while (child->color == dnode_black) {
757 parent = child->parent;
758 if (child == parent->left) {
759 sister = parent->right;
760 assert (sister != nil);
761 if (sister->color == dnode_red) {
762 sister->color = dnode_black;
763 parent->color = dnode_red;
765 sister = parent->right;
766 assert (sister != nil);
768 if (sister->left->color == dnode_black
769 && sister->right->color == dnode_black) {
770 sister->color = dnode_red;
773 if (sister->right->color == dnode_black) {
774 assert (sister->left->color == dnode_red);
775 sister->left->color = dnode_black;
776 sister->color = dnode_red;
777 rotate_right(sister);
778 sister = parent->right;
779 assert (sister != nil);
781 sister->color = parent->color;
782 sister->right->color = dnode_black;
783 parent->color = dnode_black;
787 } else { /* symmetric case: child == child->parent->right */
788 assert (child == parent->right);
789 sister = parent->left;
790 assert (sister != nil);
791 if (sister->color == dnode_red) {
792 sister->color = dnode_black;
793 parent->color = dnode_red;
794 rotate_right(parent);
795 sister = parent->left;
796 assert (sister != nil);
798 if (sister->right->color == dnode_black
799 && sister->left->color == dnode_black) {
800 sister->color = dnode_red;
803 if (sister->left->color == dnode_black) {
804 assert (sister->right->color == dnode_red);
805 sister->right->color = dnode_black;
806 sister->color = dnode_red;
808 sister = parent->left;
809 assert (sister != nil);
811 sister->color = parent->color;
812 sister->left->color = dnode_black;
813 parent->color = dnode_black;
814 rotate_right(parent);
820 child->color = dnode_black;
821 dict_root(dict)->color = dnode_black;
824 assert (dict_verify(dict));
828 #endif /* E2FSCK_NOTUSED */
831 * Allocate a node using the dictionary's allocator routine, give it
835 int dict_alloc_insert(dict_t *dict, const void *key, void *data)
837 dnode_t *node = dict->allocnode(dict->context);
840 dnode_init(node, data);
841 dict_insert(dict, node, key);
847 #ifdef E2FSCK_NOTUSED
848 void dict_delete_free(dict_t *dict, dnode_t *node)
850 dict_delete(dict, node);
851 dict->freenode(node, dict->context);
856 * Return the node with the lowest (leftmost) key. If the dictionary is empty
857 * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
860 dnode_t *dict_first(dict_t *dict)
862 dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *left;
865 while ((left = root->left) != nil)
868 return (root == nil) ? NULL : root;
872 * Return the node with the highest (rightmost) key. If the dictionary is empty
873 * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
876 dnode_t *dict_last(dict_t *dict)
878 dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *right;
881 while ((right = root->right) != nil)
884 return (root == nil) ? NULL : root;
888 * Return the given node's successor node---the node which has the
889 * next key in the the left to right ordering. If the node has
890 * no successor, a null pointer is returned rather than a pointer to
894 dnode_t *dict_next(dict_t *dict, dnode_t *curr)
896 dnode_t *nil = dict_nil(dict), *parent, *left;
898 if (curr->right != nil) {
900 while ((left = curr->left) != nil)
905 parent = curr->parent;
907 while (parent != nil && curr == parent->right) {
909 parent = curr->parent;
912 return (parent == nil) ? NULL : parent;
916 * Return the given node's predecessor, in the key order.
917 * The nil sentinel node is returned if there is no predecessor.
920 dnode_t *dict_prev(dict_t *dict, dnode_t *curr)
922 dnode_t *nil = dict_nil(dict), *parent, *right;
924 if (curr->left != nil) {
926 while ((right = curr->right) != nil)
931 parent = curr->parent;
933 while (parent != nil && curr == parent->left) {
935 parent = curr->parent;
938 return (parent == nil) ? NULL : parent;
941 void dict_allow_dupes(dict_t *dict)
953 dictcount_t dict_count(dict_t *dict)
955 return dict->nodecount;
958 int dict_isempty(dict_t *dict)
960 return dict->nodecount == 0;
963 int dict_isfull(dict_t *dict)
965 return dict->nodecount == dict->maxcount;
968 int dict_contains(dict_t *dict, dnode_t *node)
970 return verify_dict_has_node(dict_nil(dict), dict_root(dict), node);
973 static dnode_t *dnode_alloc(void *context EXT2FS_ATTR((unused)))
975 return malloc(sizeof *dnode_alloc(NULL));
978 static void dnode_free(dnode_t *node, void *context EXT2FS_ATTR((unused)))
983 dnode_t *dnode_create(void *data)
985 dnode_t *new = malloc(sizeof *new);
995 dnode_t *dnode_init(dnode_t *dnode, void *data)
998 dnode->parent = NULL;
1000 dnode->right = NULL;
1004 void dnode_destroy(dnode_t *dnode)
1006 assert (!dnode_is_in_a_dict(dnode));
1010 void *dnode_get(dnode_t *dnode)
1015 const void *dnode_getkey(dnode_t *dnode)
1020 #ifdef E2FSCK_NOTUSED
1021 void dnode_put(dnode_t *dnode, void *data)
1026 int dnode_is_in_a_dict(dnode_t *dnode)
1028 return (dnode->parent && dnode->left && dnode->right);
1031 void dict_process(dict_t *dict, void *context, dnode_process_t function)
1033 dnode_t *node = dict_first(dict), *next;
1035 while (node != NULL) {
1036 /* check for callback function deleting */
1037 /* the next node from under us */
1038 assert (dict_contains(dict, node));
1039 next = dict_next(dict, node);
1040 function(dict, node, context);
1045 static void load_begin_internal(dict_load_t *load, dict_t *dict)
1047 load->dictptr = dict;
1048 load->nilnode.left = &load->nilnode;
1049 load->nilnode.right = &load->nilnode;
1052 void dict_load_begin(dict_load_t *load, dict_t *dict)
1054 assert (dict_isempty(dict));
1055 load_begin_internal(load, dict);
1058 void dict_load_next(dict_load_t *load, dnode_t *newnode, const void *key)
1060 dict_t *dict = load->dictptr;
1061 dnode_t *nil = &load->nilnode;
1063 assert (!dnode_is_in_a_dict(newnode));
1064 assert (dict->nodecount < dict->maxcount);
1067 if (dict->nodecount > 0) {
1069 assert (dict->compare(nil->left->key, key) <= 0);
1071 assert (dict->compare(nil->left->key, key) < 0);
1076 nil->right->left = newnode;
1077 nil->right = newnode;
1078 newnode->left = nil;
1082 void dict_load_end(dict_load_t *load)
1084 dict_t *dict = load->dictptr;
1085 dnode_t *tree[DICT_DEPTH_MAX] = { 0 };
1086 dnode_t *curr, *dictnil = dict_nil(dict), *loadnil = &load->nilnode, *next;
1087 dnode_t *complete = 0;
1088 dictcount_t fullcount = DICTCOUNT_T_MAX, nodecount = dict->nodecount;
1089 dictcount_t botrowcount;
1090 unsigned baselevel = 0, level = 0, i;
1092 assert (dnode_red == 0 && dnode_black == 1);
1094 while (fullcount >= nodecount && fullcount)
1097 botrowcount = nodecount - fullcount;
1099 for (curr = loadnil->left; curr != loadnil; curr = next) {
1102 if (complete == NULL && botrowcount-- == 0) {
1103 assert (baselevel == 0);
1104 assert (level == 0);
1105 baselevel = level = 1;
1108 if (complete != 0) {
1110 complete->right = dictnil;
1111 while (tree[level] != 0) {
1112 tree[level]->right = complete;
1113 complete->parent = tree[level];
1114 complete = tree[level];
1120 if (complete == NULL) {
1121 curr->left = dictnil;
1122 curr->right = dictnil;
1123 curr->color = level % 2;
1126 assert (level == baselevel);
1127 while (tree[level] != 0) {
1128 tree[level]->right = complete;
1129 complete->parent = tree[level];
1130 complete = tree[level];
1134 curr->left = complete;
1135 curr->color = (level + 1) % 2;
1136 complete->parent = curr;
1143 if (complete == NULL)
1146 for (i = 0; i < DICT_DEPTH_MAX; i++) {
1148 tree[i]->right = complete;
1149 complete->parent = tree[i];
1154 dictnil->color = dnode_black;
1155 dictnil->right = dictnil;
1156 complete->parent = dictnil;
1157 complete->color = dnode_black;
1158 dict_root(dict) = complete;
1160 assert (dict_verify(dict));
1163 void dict_merge(dict_t *dest, dict_t *source)
1166 dnode_t *leftnode = dict_first(dest), *rightnode = dict_first(source);
1168 assert (dict_similar(dest, source));
1173 dest->nodecount = 0;
1174 load_begin_internal(&load, dest);
1177 if (leftnode != NULL && rightnode != NULL) {
1178 if (dest->compare(leftnode->key, rightnode->key) < 0)
1182 } else if (leftnode != NULL) {
1184 } else if (rightnode != NULL) {
1187 assert (leftnode == NULL && rightnode == NULL);
1193 dnode_t *next = dict_next(dest, leftnode);
1195 leftnode->left = NULL; /* suppress assertion in dict_load_next */
1197 dict_load_next(&load, leftnode, leftnode->key);
1204 dnode_t *next = dict_next(source, rightnode);
1206 rightnode->left = NULL;
1208 dict_load_next(&load, rightnode, rightnode->key);
1215 dict_load_end(&load);
1217 #endif /* E2FSCK_NOTUSED */
1219 #ifdef KAZLIB_TEST_MAIN
1226 typedef char input_t[256];
1228 static int tokenize(char *string, ...)
1234 va_start(arglist, string);
1235 tokptr = va_arg(arglist, char **);
1237 while (*string && isspace((unsigned char) *string))
1242 while (*string && !isspace((unsigned char) *string))
1244 tokptr = va_arg(arglist, char **);
1255 static int comparef(const void *key1, const void *key2)
1257 return strcmp(key1, key2);
1260 static char *dupstring(char *str)
1262 int sz = strlen(str) + 1;
1263 char *new = malloc(sz);
1265 memcpy(new, str, sz);
1269 static dnode_t *new_node(void *c)
1271 static dnode_t few[5];
1275 return few + count++;
1280 static void del_node(dnode_t *n, void *c)
1284 static int prompt = 0;
1286 static void construct(dict_t *d)
1292 char *tok1, *tok2, *val;
1295 "p turn prompt on\n"
1296 "q finish construction\n"
1297 "a <key> <val> add new entry\n";
1299 if (!dict_isempty(d))
1300 puts("warning: dictionary not empty!");
1302 dict_load_begin(&dl, d);
1309 if (!fgets(in, sizeof(input_t), stdin))
1323 if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) {
1327 key = dupstring(tok1);
1328 val = dupstring(tok2);
1329 dn = dnode_create(val);
1331 if (!key || !val || !dn) {
1332 puts("out of memory");
1339 dict_load_next(&dl, dn, key);
1355 dict_t *d = &darray[0];
1358 char *tok1, *tok2, *val;
1362 "a <key> <val> add value to dictionary\n"
1363 "d <key> delete value from dictionary\n"
1364 "l <key> lookup value in dictionary\n"
1365 "( <key> lookup lower bound\n"
1366 ") <key> lookup upper bound\n"
1367 "# <num> switch to alternate dictionary (0-9)\n"
1368 "j <num> <num> merge two dictionaries\n"
1369 "f free the whole dictionary\n"
1370 "k allow duplicate keys\n"
1371 "c show number of entries\n"
1372 "t dump whole dictionary in sort order\n"
1373 "m make dictionary out of sorted items\n"
1374 "p turn prompt on\n"
1375 "s switch to non-functioning allocator\n"
1378 for (i = 0; i < sizeof darray / sizeof *darray; i++)
1379 dict_init(&darray[i], DICTCOUNT_T_MAX, comparef);
1386 if (!fgets(in, sizeof(input_t), stdin))
1394 if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) {
1398 key = dupstring(tok1);
1399 val = dupstring(tok2);
1402 puts("out of memory");
1407 if (!dict_alloc_insert(d, key, val)) {
1408 puts("dict_alloc_insert failed");
1415 if (tokenize(in+1, &tok1, (char **) 0) != 1) {
1419 dn = dict_lookup(d, tok1);
1421 puts("dict_lookup failed");
1424 val = dnode_get(dn);
1425 key = dnode_getkey(dn);
1426 dict_delete_free(d, dn);
1437 if (tokenize(in+1, &tok1, (char **) 0) != 1) {
1444 dn = dict_lookup(d, tok1);
1447 dn = dict_lower_bound(d, tok1);
1450 dn = dict_upper_bound(d, tok1);
1454 puts("lookup failed");
1457 val = dnode_get(dn);
1464 dict_allow_dupes(d);
1467 printf("%lu\n", (unsigned long) dict_count(d));
1470 for (dn = dict_first(d); dn; dn = dict_next(d, dn)) {
1471 printf("%s\t%s\n", (char *) dnode_getkey(dn),
1472 (char *) dnode_get(dn));
1484 dict_set_allocator(d, new_node, del_node, NULL);
1487 if (tokenize(in+1, &tok1, (char **) 0) != 1) {
1491 int dictnum = atoi(tok1);
1492 if (dictnum < 0 || dictnum > 9) {
1493 puts("invalid number");
1496 d = &darray[dictnum];
1500 if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) {
1504 int dict1 = atoi(tok1), dict2 = atoi(tok2);
1505 if (dict1 < 0 || dict1 > 9 || dict2 < 0 || dict2 > 9) {
1506 puts("invalid number");
1509 dict_merge(&darray[dict1], &darray[dict2]);