]>
git.ipfire.org Git - thirdparty/e2fsprogs.git/blob - lib/support/dict.c
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_assert(x)
36 #define dict_assert(x) assert(x)
38 #define DICT_IMPLEMENTATION
42 static const char rcsid
[] = "$Id: dict.c,v 1.40.2.7 2000/11/13 01:36:44 kaz Exp $";
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!
57 #define left dict_left
58 #define right dict_right
59 #define parent dict_parent
60 #define color dict_color
62 #define data dict_data
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
73 #define dictptr dict_dictptr
75 #define dict_root(D) ((D)->nilnode.left)
76 #define dict_nil(D) (&(D)->nilnode)
77 #define DICT_DEPTH_MAX 64
79 static dnode_t
*dnode_alloc(void *context
);
80 static void dnode_free(dnode_t
*node
, void *context
);
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.
89 static void rotate_left(dnode_t
*upper
)
91 dnode_t
*lower
, *lowleft
, *upparent
;
94 upper
->right
= lowleft
= lower
->left
;
95 lowleft
->parent
= upper
;
97 lower
->parent
= upparent
= upper
->parent
;
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 */
102 if (upper
== upparent
->left
) {
103 upparent
->left
= lower
;
105 dict_assert (upper
== upparent
->right
);
106 upparent
->right
= lower
;
110 upper
->parent
= lower
;
114 * This operation is the ``mirror'' image of rotate_left. It is
115 * the same procedure, but with left and right interchanged.
118 static void rotate_right(dnode_t
*upper
)
120 dnode_t
*lower
, *lowright
, *upparent
;
123 upper
->left
= lowright
= lower
->right
;
124 lowright
->parent
= upper
;
126 lower
->parent
= upparent
= upper
->parent
;
128 if (upper
== upparent
->right
) {
129 upparent
->right
= lower
;
131 dict_assert (upper
== upparent
->left
);
132 upparent
->left
= lower
;
135 lower
->right
= upper
;
136 upper
->parent
= lower
;
140 * Do a postorder traversal of the tree rooted at the specified
141 * node and free everything under it. Used by dict_free().
144 static void free_nodes(dict_t
*dict
, dnode_t
*node
, dnode_t
*nil
)
148 free_nodes(dict
, node
->left
, nil
);
149 free_nodes(dict
, node
->right
, nil
);
150 dict
->freenode(node
, dict
->context
);
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.
162 static int verify_bintree(dict_t
*dict
)
164 dnode_t
*first
, *next
;
166 first
= dict_first(dict
);
169 while (first
&& (next
= dict_next(dict
, first
))) {
170 if (dict
->compare(first
->key
, next
->key
) > 0)
175 while (first
&& (next
= dict_next(dict
, first
))) {
176 if (dict
->compare(first
->key
, next
->key
) >= 0)
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.
197 static unsigned int verify_redblack(dnode_t
*nil
, dnode_t
*root
)
199 unsigned height_left
, height_right
;
202 height_left
= verify_redblack(nil
, root
->left
);
203 height_right
= verify_redblack(nil
, root
->right
);
204 if (height_left
== 0 || height_right
== 0)
206 if (height_left
!= height_right
)
208 if (root
->color
== dnode_red
) {
209 if (root
->left
->color
!= dnode_black
)
211 if (root
->right
->color
!= dnode_black
)
215 if (root
->color
!= dnode_black
)
217 return height_left
+ 1;
223 * Compute the actual count of nodes by traversing the tree and
224 * return it. This could be compared against the stored count to
228 static dictcount_t
verify_node_count(dnode_t
*nil
, dnode_t
*root
)
233 return 1 + verify_node_count(nil
, root
->left
)
234 + verify_node_count(nil
, root
->right
);
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.
245 static int verify_dict_has_node(dnode_t
*nil
, dnode_t
*root
, dnode_t
*node
)
249 || verify_dict_has_node(nil
, root
->left
, node
)
250 || verify_dict_has_node(nil
, root
->right
, node
);
256 #ifdef E2FSCK_NOTUSED
258 * Dynamically allocate and initialize a dictionary object.
261 dict_t
*dict_create(dictcount_t maxcount
, dict_comp_t comp
)
263 dict_t
*new = malloc(sizeof *new);
267 new->allocnode
= dnode_alloc
;
268 new->freenode
= dnode_free
;
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
;
280 #endif /* E2FSCK_NOTUSED */
283 * Select a different set of node allocator routines.
286 void dict_set_allocator(dict_t
*dict
, dnode_alloc_t al
,
287 dnode_free_t fr
, void *context
)
289 dict_assert (dict_count(dict
) == 0);
290 dict_assert ((al
== NULL
&& fr
== NULL
) || (al
!= NULL
&& fr
!= NULL
));
292 dict
->allocnode
= al
? al
: dnode_alloc
;
293 dict
->freenode
= fr
? fr
: dnode_free
;
294 dict
->context
= context
;
297 #ifdef E2FSCK_NOTUSED
299 * Free a dynamically allocated dictionary object. Removing the nodes
300 * from the tree before deleting it is required.
303 void dict_destroy(dict_t
*dict
)
305 dict_assert (dict_isempty(dict
));
311 * Free all the nodes in the dictionary by using the dictionary's
312 * installed free routine. The dictionary is emptied.
315 void dict_free_nodes(dict_t
*dict
)
317 dnode_t
*nil
= dict_nil(dict
), *root
= dict_root(dict
);
318 free_nodes(dict
, root
, nil
);
320 dict
->nilnode
.left
= &dict
->nilnode
;
321 dict
->nilnode
.right
= &dict
->nilnode
;
324 #ifdef E2FSCK_NOTUSED
326 * Obsolescent function, equivalent to dict_free_nodes
328 void dict_free(dict_t
*dict
)
330 #ifdef KAZLIB_OBSOLESCENT_DEBUG
331 dict_assert ("call to obsolescent function dict_free()" && 0);
333 dict_free_nodes(dict
);
338 * Initialize a user-supplied dictionary object.
341 dict_t
*dict_init(dict_t
*dict
, dictcount_t maxcount
, dict_comp_t comp
)
343 dict
->compare
= comp
;
344 dict
->allocnode
= dnode_alloc
;
345 dict
->freenode
= dnode_free
;
346 dict
->context
= NULL
;
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
;
357 #ifdef E2FSCK_NOTUSED
359 * Initialize a dictionary in the likeness of another dictionary
362 void dict_init_like(dict_t
*dict
, const dict_t
*template)
364 dict
->compare
= template->compare
;
365 dict
->allocnode
= template->allocnode
;
366 dict
->freenode
= template->freenode
;
367 dict
->context
= template->context
;
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
;
376 dict_assert (dict_similar(dict
, template));
380 * Remove all nodes from the dictionary (without freeing them in any way).
383 static void dict_clear(dict_t
*dict
)
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
);
391 #endif /* E2FSCK_NOTUSED */
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.
401 int dict_verify(dict_t
*dict
)
403 dnode_t
*nil
= dict_nil(dict
), *root
= dict_root(dict
);
405 /* check that the sentinel node and root node are black */
406 if (root
->color
!= dnode_black
)
408 if (nil
->color
!= dnode_black
)
410 if (nil
->right
!= nil
)
412 /* nil->left is the root node; check that its parent pointer is nil */
413 if (nil
->left
->parent
!= nil
)
415 /* perform a weak test that the tree is a binary search tree */
416 if (!verify_bintree(dict
))
418 /* verify that the tree is a red-black tree */
419 if (!verify_redblack(nil
, root
))
421 if (verify_node_count(nil
, root
) != dict_count(dict
))
425 #endif /* DICT_NODEBUG */
427 #ifdef E2FSCK_NOTUSED
429 * Determine whether two dictionaries are similar: have the same comparison and
430 * allocator functions, and same status as to whether duplicates are allowed.
432 int dict_similar(const dict_t
*left
, const dict_t
*right
)
434 if (left
->compare
!= right
->compare
)
437 if (left
->allocnode
!= right
->allocnode
)
440 if (left
->freenode
!= right
->freenode
)
443 if (left
->context
!= right
->context
)
446 if (left
->dupes
!= right
->dupes
)
451 #endif /* E2FSCK_NOTUSED */
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.
460 dnode_t
*dict_lookup(dict_t
*dict
, const void *key
)
462 dnode_t
*root
= dict_root(dict
);
463 dnode_t
*nil
= dict_nil(dict
);
467 /* simple binary search adapted for trees that contain duplicate keys */
469 while (root
!= nil
) {
470 result
= dict
->compare(key
, root
->key
);
476 if (!dict
->dupes
) { /* no duplicates, return match */
478 } else { /* could be dupes, find leftmost one */
482 while (root
!= nil
&& dict
->compare(key
, root
->key
))
484 } while (root
!= nil
);
493 #ifdef E2FSCK_NOTUSED
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.
499 dnode_t
*dict_lower_bound(dict_t
*dict
, const void *key
)
501 dnode_t
*root
= dict_root(dict
);
502 dnode_t
*nil
= dict_nil(dict
);
503 dnode_t
*tentative
= 0;
505 while (root
!= nil
) {
506 int result
= dict
->compare(key
, root
->key
);
510 } else if (result
< 0) {
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.
531 dnode_t
*dict_upper_bound(dict_t
*dict
, const void *key
)
533 dnode_t
*root
= dict_root(dict
);
534 dnode_t
*nil
= dict_nil(dict
);
535 dnode_t
*tentative
= 0;
537 while (root
!= nil
) {
538 int result
= dict
->compare(key
, root
->key
);
542 } else if (result
> 0) {
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).
567 void dict_insert(dict_t
*dict
, dnode_t
*node
, const void *key
)
569 dnode_t
*where
= dict_root(dict
), *nil
= dict_nil(dict
);
570 dnode_t
*parent
= nil
, *uncle
, *grandpa
;
575 dict_assert (!dict_isfull(dict
));
576 dict_assert (!dict_contains(dict
, node
));
577 dict_assert (!dnode_is_in_a_dict(node
));
579 /* basic binary tree insert */
581 while (where
!= nil
) {
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);
589 where
= where
->right
;
592 dict_assert (where
== nil
);
597 parent
->right
= node
;
599 node
->parent
= parent
;
605 /* red black adjustments */
607 node
->color
= dnode_red
;
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
;
618 parent
= grandpa
->parent
;
619 } else { /* red parent, black uncle */
620 if (node
== parent
->right
) {
623 dict_assert (grandpa
== parent
->parent
);
624 /* rotation between parent and child preserves grandpa */
626 parent
->color
= dnode_black
;
627 grandpa
->color
= dnode_red
;
628 rotate_right(grandpa
);
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
;
638 parent
= grandpa
->parent
;
640 if (node
== parent
->left
) {
641 rotate_right(parent
);
643 dict_assert (grandpa
== parent
->parent
);
645 parent
->color
= dnode_black
;
646 grandpa
->color
= dnode_red
;
647 rotate_left(grandpa
);
653 dict_root(dict
)->color
= dnode_black
;
655 dict_assert (dict_verify(dict
));
658 #ifdef E2FSCK_NOTUSED
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.
665 dnode_t
*dict_delete(dict_t
*dict
, dnode_t
*delete)
667 dnode_t
*nil
= dict_nil(dict
), *child
, *delparent
= delete->parent
;
671 dict_assert (!dict_isempty(dict
));
672 dict_assert (dict_contains(dict
, delete));
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.
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
;
691 dict_assert (next
!= nil
);
692 dict_assert (next
->parent
!= nil
);
693 dict_assert (next
->left
== nil
);
696 * First, splice out the successor from the tree completely, by
697 * moving up its right child into its place.
701 child
->parent
= nextparent
;
703 if (nextparent
->left
== next
) {
704 nextparent
->left
= child
;
706 dict_assert (nextparent
->right
== next
);
707 nextparent
->right
= child
;
711 * Now that the successor has been extricated from the tree, install it
712 * in place of the node that we want deleted.
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
;
723 if (delparent
->left
== delete) {
724 delparent
->left
= next
;
726 dict_assert (delparent
->right
== delete);
727 delparent
->right
= next
;
731 dict_assert (delete != nil
);
732 dict_assert (delete->left
== nil
|| delete->right
== nil
);
734 child
= (delete->left
!= nil
) ? delete->left
: delete->right
;
736 child
->parent
= delparent
= delete->parent
;
738 if (delete == delparent
->left
) {
739 delparent
->left
= child
;
741 dict_assert (delete == delparent
->right
);
742 delparent
->right
= child
;
746 delete->parent
= NULL
;
747 delete->right
= NULL
;
752 dict_assert (verify_bintree(dict
));
754 /* red-black adjustments */
756 if (delete->color
== dnode_black
) {
757 dnode_t
*parent
, *sister
;
759 dict_root(dict
)->color
= dnode_red
;
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
;
770 sister
= parent
->right
;
771 dict_assert (sister
!= nil
);
773 if (sister
->left
->color
== dnode_black
774 && sister
->right
->color
== dnode_black
) {
775 sister
->color
= dnode_red
;
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
);
786 sister
->color
= parent
->color
;
787 sister
->right
->color
= dnode_black
;
788 parent
->color
= dnode_black
;
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
);
803 if (sister
->right
->color
== dnode_black
804 && sister
->left
->color
== dnode_black
) {
805 sister
->color
= dnode_red
;
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
;
813 sister
= parent
->left
;
814 dict_assert (sister
!= nil
);
816 sister
->color
= parent
->color
;
817 sister
->left
->color
= dnode_black
;
818 parent
->color
= dnode_black
;
819 rotate_right(parent
);
825 child
->color
= dnode_black
;
826 dict_root(dict
)->color
= dnode_black
;
829 dict_assert (dict_verify(dict
));
833 #endif /* E2FSCK_NOTUSED */
836 * Allocate a node using the dictionary's allocator routine, give it
840 int dict_alloc_insert(dict_t
*dict
, const void *key
, void *data
)
842 dnode_t
*node
= dict
->allocnode(dict
->context
);
845 dnode_init(node
, data
);
846 dict_insert(dict
, node
, key
);
852 #ifdef E2FSCK_NOTUSED
853 void dict_delete_free(dict_t
*dict
, dnode_t
*node
)
855 dict_delete(dict
, node
);
856 dict
->freenode(node
, dict
->context
);
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.
865 dnode_t
*dict_first(dict_t
*dict
)
867 dnode_t
*nil
= dict_nil(dict
), *root
= dict_root(dict
), *left
;
870 while ((left
= root
->left
) != nil
)
873 return (root
== nil
) ? NULL
: root
;
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.
881 dnode_t
*dict_last(dict_t
*dict
)
883 dnode_t
*nil
= dict_nil(dict
), *root
= dict_root(dict
), *right
;
886 while ((right
= root
->right
) != nil
)
889 return (root
== nil
) ? NULL
: root
;
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
899 dnode_t
*dict_next(dict_t
*dict
, dnode_t
*curr
)
901 dnode_t
*nil
= dict_nil(dict
), *parent
, *left
;
903 if (curr
->right
!= nil
) {
905 while ((left
= curr
->left
) != nil
)
910 parent
= curr
->parent
;
912 while (parent
!= nil
&& curr
== parent
->right
) {
914 parent
= curr
->parent
;
917 return (parent
== nil
) ? NULL
: parent
;
921 * Return the given node's predecessor, in the key order.
922 * The nil sentinel node is returned if there is no predecessor.
925 dnode_t
*dict_prev(dict_t
*dict
, dnode_t
*curr
)
927 dnode_t
*nil
= dict_nil(dict
), *parent
, *right
;
929 if (curr
->left
!= nil
) {
931 while ((right
= curr
->right
) != nil
)
936 parent
= curr
->parent
;
938 while (parent
!= nil
&& curr
== parent
->left
) {
940 parent
= curr
->parent
;
943 return (parent
== nil
) ? NULL
: parent
;
946 void dict_allow_dupes(dict_t
*dict
)
958 dictcount_t
dict_count(dict_t
*dict
)
960 return dict
->nodecount
;
963 int dict_isempty(dict_t
*dict
)
965 return dict
->nodecount
== 0;
968 int dict_isfull(dict_t
*dict
)
970 return dict
->nodecount
== dict
->maxcount
;
973 int dict_contains(dict_t
*dict
, dnode_t
*node
)
975 return verify_dict_has_node(dict_nil(dict
), dict_root(dict
), node
);
978 static dnode_t
*dnode_alloc(void *context
EXT2FS_ATTR((unused
)))
980 return malloc(sizeof *dnode_alloc(NULL
));
983 static void dnode_free(dnode_t
*node
, void *context
EXT2FS_ATTR((unused
)))
988 dnode_t
*dnode_create(void *data
)
990 dnode_t
*new = malloc(sizeof *new);
1000 dnode_t
*dnode_init(dnode_t
*dnode
, void *data
)
1003 dnode
->parent
= NULL
;
1005 dnode
->right
= NULL
;
1009 void dnode_destroy(dnode_t
*dnode
)
1011 dict_assert (!dnode_is_in_a_dict(dnode
));
1015 void *dnode_get(dnode_t
*dnode
)
1020 const void *dnode_getkey(dnode_t
*dnode
)
1025 #ifdef E2FSCK_NOTUSED
1026 void dnode_put(dnode_t
*dnode
, void *data
)
1032 #ifndef DICT_NODEBUG
1033 int dnode_is_in_a_dict(dnode_t
*dnode
)
1035 return (dnode
->parent
&& dnode
->left
&& dnode
->right
);
1039 #ifdef E2FSCK_NOTUSED
1040 void dict_process(dict_t
*dict
, void *context
, dnode_process_t function
)
1042 dnode_t
*node
= dict_first(dict
), *next
;
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
);
1054 static void load_begin_internal(dict_load_t
*load
, dict_t
*dict
)
1056 load
->dictptr
= dict
;
1057 load
->nilnode
.left
= &load
->nilnode
;
1058 load
->nilnode
.right
= &load
->nilnode
;
1061 void dict_load_begin(dict_load_t
*load
, dict_t
*dict
)
1063 dict_assert (dict_isempty(dict
));
1064 load_begin_internal(load
, dict
);
1067 void dict_load_next(dict_load_t
*load
, dnode_t
*newnode
, const void *key
)
1069 dict_t
*dict
= load
->dictptr
;
1070 dnode_t
*nil
= &load
->nilnode
;
1072 dict_assert (!dnode_is_in_a_dict(newnode
));
1073 dict_assert (dict
->nodecount
< dict
->maxcount
);
1075 #ifndef DICT_NODEBUG
1076 if (dict
->nodecount
> 0) {
1078 dict_assert (dict
->compare(nil
->left
->key
, key
) <= 0);
1080 dict_assert (dict
->compare(nil
->left
->key
, key
) < 0);
1085 nil
->right
->left
= newnode
;
1086 nil
->right
= newnode
;
1087 newnode
->left
= nil
;
1091 void dict_load_end(dict_load_t
*load
)
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
;
1101 dict_assert (dnode_red
== 0 && dnode_black
== 1);
1103 while (fullcount
>= nodecount
&& fullcount
)
1106 botrowcount
= nodecount
- fullcount
;
1108 for (curr
= loadnil
->left
; curr
!= loadnil
; curr
= next
) {
1111 if (complete
== NULL
&& botrowcount
-- == 0) {
1112 dict_assert (baselevel
== 0);
1113 dict_assert (level
== 0);
1114 baselevel
= level
= 1;
1117 if (complete
!= 0) {
1119 complete
->right
= dictnil
;
1120 while (tree
[level
] != 0) {
1121 tree
[level
]->right
= complete
;
1122 complete
->parent
= tree
[level
];
1123 complete
= tree
[level
];
1129 if (complete
== NULL
) {
1130 curr
->left
= dictnil
;
1131 curr
->right
= dictnil
;
1132 curr
->color
= level
% 2;
1135 dict_assert (level
== baselevel
);
1136 while (tree
[level
] != 0) {
1137 tree
[level
]->right
= complete
;
1138 complete
->parent
= tree
[level
];
1139 complete
= tree
[level
];
1143 curr
->left
= complete
;
1144 curr
->color
= (level
+ 1) % 2;
1145 complete
->parent
= curr
;
1152 if (complete
== NULL
)
1155 for (i
= 0; i
< DICT_DEPTH_MAX
; i
++) {
1157 tree
[i
]->right
= complete
;
1158 complete
->parent
= tree
[i
];
1163 dictnil
->color
= dnode_black
;
1164 dictnil
->right
= dictnil
;
1165 complete
->parent
= dictnil
;
1166 complete
->color
= dnode_black
;
1167 dict_root(dict
) = complete
;
1169 dict_assert (dict_verify(dict
));
1172 void dict_merge(dict_t
*dest
, dict_t
*source
)
1175 dnode_t
*leftnode
= dict_first(dest
), *rightnode
= dict_first(source
);
1177 dict_assert (dict_similar(dest
, source
));
1182 dest
->nodecount
= 0;
1183 load_begin_internal(&load
, dest
);
1186 if (leftnode
!= NULL
&& rightnode
!= NULL
) {
1187 if (dest
->compare(leftnode
->key
, rightnode
->key
) < 0)
1191 } else if (leftnode
!= NULL
) {
1193 } else if (rightnode
!= NULL
) {
1196 dict_assert (leftnode
== NULL
&& rightnode
== NULL
);
1202 dnode_t
*next
= dict_next(dest
, leftnode
);
1203 #ifndef DICT_NODEBUG
1204 leftnode
->left
= NULL
; /* suppress assertion in dict_load_next */
1206 dict_load_next(&load
, leftnode
, leftnode
->key
);
1213 dnode_t
*next
= dict_next(source
, rightnode
);
1214 #ifndef DICT_NODEBUG
1215 rightnode
->left
= NULL
;
1217 dict_load_next(&load
, rightnode
, rightnode
->key
);
1224 dict_load_end(&load
);
1226 #endif /* E2FSCK_NOTUSED */
1228 #ifdef KAZLIB_TEST_MAIN
1235 typedef char input_t
[256];
1237 static int tokenize(char *string
, ...)
1243 va_start(arglist
, string
);
1244 tokptr
= va_arg(arglist
, char **);
1246 while (*string
&& isspace((unsigned char) *string
))
1251 while (*string
&& !isspace((unsigned char) *string
))
1253 tokptr
= va_arg(arglist
, char **);
1264 static int comparef(const void *key1
, const void *key2
)
1266 return strcmp(key1
, key2
);
1269 static char *dupstring(char *str
)
1271 int sz
= strlen(str
) + 1;
1272 char *new = malloc(sz
);
1274 memcpy(new, str
, sz
);
1278 static dnode_t
*new_node(void *c
)
1280 static dnode_t few
[5];
1284 return few
+ count
++;
1289 static void del_node(dnode_t
*n
, void *c
)
1293 static int prompt
= 0;
1295 static void construct(dict_t
*d
)
1301 char *tok1
, *tok2
, *val
;
1304 "p turn prompt on\n"
1305 "q finish construction\n"
1306 "a <key> <val> add new entry\n";
1308 if (!dict_isempty(d
))
1309 puts("warning: dictionary not empty!");
1311 dict_load_begin(&dl
, d
);
1318 if (!fgets(in
, sizeof(input_t
), stdin
))
1332 if (tokenize(in
+1, &tok1
, &tok2
, (char **) 0) != 2) {
1336 key
= dupstring(tok1
);
1337 val
= dupstring(tok2
);
1338 dn
= dnode_create(val
);
1340 if (!key
|| !val
|| !dn
) {
1341 puts("out of memory");
1348 dict_load_next(&dl
, dn
, key
);
1364 dict_t
*d
= &darray
[0];
1367 char *tok1
, *tok2
, *val
;
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"
1387 for (i
= 0; i
< sizeof darray
/ sizeof *darray
; i
++)
1388 dict_init(&darray
[i
], DICTCOUNT_T_MAX
, comparef
);
1395 if (!fgets(in
, sizeof(input_t
), stdin
))
1403 if (tokenize(in
+1, &tok1
, &tok2
, (char **) 0) != 2) {
1407 key
= dupstring(tok1
);
1408 val
= dupstring(tok2
);
1411 puts("out of memory");
1416 if (!dict_alloc_insert(d
, key
, val
)) {
1417 puts("dict_alloc_insert failed");
1424 if (tokenize(in
+1, &tok1
, (char **) 0) != 1) {
1428 dn
= dict_lookup(d
, tok1
);
1430 puts("dict_lookup failed");
1433 val
= dnode_get(dn
);
1434 key
= dnode_getkey(dn
);
1435 dict_delete_free(d
, dn
);
1446 if (tokenize(in
+1, &tok1
, (char **) 0) != 1) {
1453 dn
= dict_lookup(d
, tok1
);
1456 dn
= dict_lower_bound(d
, tok1
);
1459 dn
= dict_upper_bound(d
, tok1
);
1463 puts("lookup failed");
1466 val
= dnode_get(dn
);
1473 dict_allow_dupes(d
);
1476 printf("%lu\n", (unsigned long) dict_count(d
));
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
));
1493 dict_set_allocator(d
, new_node
, del_node
, NULL
);
1496 if (tokenize(in
+1, &tok1
, (char **) 0) != 1) {
1500 int dictnum
= atoi(tok1
);
1501 if (dictnum
< 0 || dictnum
> 9) {
1502 puts("invalid number");
1505 d
= &darray
[dictnum
];
1509 if (tokenize(in
+1, &tok1
, &tok2
, (char **) 0) != 2) {
1513 int dict1
= atoi(tok1
), dict2
= atoi(tok2
);
1514 if (dict1
< 0 || dict1
> 9 || dict2
< 0 || dict2
> 9) {
1515 puts("invalid number");
1518 dict_merge(&darray
[dict1
], &darray
[dict2
]);