]>
git.proxmox.com Git - mirror_frr.git/blob - isisd/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.
22 #define DICT_IMPLEMENTATION
26 static const char rcsid
[] = "Id: dict.c,v 1.40.2.7 2000/11/13 01:36:44 kaz";
30 * These macros provide short convenient names for structure members,
31 * which are embellished with dict_ prefixes so that they are
32 * properly confined to the documented namespace. It's legal for a
33 * program which uses dict to define, for instance, a macro called ``parent''.
34 * Such a macro would interfere with the dnode_t struct definition.
35 * In general, highly portable and reusable C modules which expose their
36 * structures need to confine structure member names to well-defined spaces.
37 * The resulting identifiers aren't necessarily convenient to use, nor
38 * readable, in the implementation, however!
41 #define left dict_left
42 #define right dict_right
43 #define parent dict_parent
44 #define color dict_color
46 #define data dict_data
48 #define nilnode dict_nilnode
49 #define nodecount dict_nodecount
50 #define maxcount dict_maxcount
51 #define compare dict_compare
52 #define allocnode dict_allocnode
53 #define freenode dict_freenode
54 #define context dict_context
55 #define dupes dict_dupes
57 #define dictptr dict_dictptr
59 #define dict_root(D) ((D)->nilnode.left)
60 #define dict_nil(D) (&(D)->nilnode)
61 #define DICT_DEPTH_MAX 64
63 static dnode_t
*dnode_alloc(void *context
);
64 static void dnode_free(dnode_t
*node
, void *context
);
67 * Perform a ``left rotation'' adjustment on the tree. The given node P and
68 * its right child C are rearranged so that the P instead becomes the left
69 * child of C. The left subtree of C is inherited as the new right subtree
70 * for P. The ordering of the keys within the tree is thus preserved.
73 static void rotate_left(dnode_t
*upper
)
75 dnode_t
*lower
, *lowleft
, *upparent
;
78 upper
->right
= lowleft
= lower
->left
;
79 lowleft
->parent
= upper
;
81 lower
->parent
= upparent
= upper
->parent
;
83 /* don't need to check for root node here because root->parent is
84 the sentinel nil node, and root->parent->left points back to root */
86 if (upper
== upparent
->left
) {
87 upparent
->left
= lower
;
89 assert (upper
== upparent
->right
);
90 upparent
->right
= lower
;
94 upper
->parent
= lower
;
98 * This operation is the ``mirror'' image of rotate_left. It is
99 * the same procedure, but with left and right interchanged.
102 static void rotate_right(dnode_t
*upper
)
104 dnode_t
*lower
, *lowright
, *upparent
;
107 upper
->left
= lowright
= lower
->right
;
108 lowright
->parent
= upper
;
110 lower
->parent
= upparent
= upper
->parent
;
112 if (upper
== upparent
->right
) {
113 upparent
->right
= lower
;
115 assert (upper
== upparent
->left
);
116 upparent
->left
= lower
;
119 lower
->right
= upper
;
120 upper
->parent
= lower
;
124 * Do a postorder traversal of the tree rooted at the specified
125 * node and free everything under it. Used by dict_free().
128 static void free_nodes(dict_t
*dict
, dnode_t
*node
, dnode_t
*nil
)
132 free_nodes(dict
, node
->left
, nil
);
133 free_nodes(dict
, node
->right
, nil
);
134 dict
->freenode(node
, dict
->context
);
138 * This procedure performs a verification that the given subtree is a binary
139 * search tree. It performs an inorder traversal of the tree using the
140 * dict_next() successor function, verifying that the key of each node is
141 * strictly lower than that of its successor, if duplicates are not allowed,
142 * or lower or equal if duplicates are allowed. This function is used for
143 * debugging purposes.
146 static int verify_bintree(dict_t
*dict
)
148 dnode_t
*first
, *next
;
150 first
= dict_first(dict
);
153 while (first
&& (next
= dict_next(dict
, first
))) {
154 if (dict
->compare(first
->key
, next
->key
) > 0)
159 while (first
&& (next
= dict_next(dict
, first
))) {
160 if (dict
->compare(first
->key
, next
->key
) >= 0)
170 * This function recursively verifies that the given binary subtree satisfies
171 * three of the red black properties. It checks that every red node has only
172 * black children. It makes sure that each node is either red or black. And it
173 * checks that every path has the same count of black nodes from root to leaf.
174 * It returns the blackheight of the given subtree; this allows blackheights to
175 * be computed recursively and compared for left and right siblings for
176 * mismatches. It does not check for every nil node being black, because there
177 * is only one sentinel nil node. The return value of this function is the
178 * black height of the subtree rooted at the node ``root'', or zero if the
179 * subtree is not red-black.
182 static unsigned int verify_redblack(dnode_t
*nil
, dnode_t
*root
)
184 unsigned height_left
, height_right
;
187 height_left
= verify_redblack(nil
, root
->left
);
188 height_right
= verify_redblack(nil
, root
->right
);
189 if (height_left
== 0 || height_right
== 0)
191 if (height_left
!= height_right
)
193 if (root
->color
== dnode_red
) {
194 if (root
->left
->color
!= dnode_black
)
196 if (root
->right
->color
!= dnode_black
)
200 if (root
->color
!= dnode_black
)
202 return height_left
+ 1;
208 * Compute the actual count of nodes by traversing the tree and
209 * return it. This could be compared against the stored count to
213 static dictcount_t
verify_node_count(dnode_t
*nil
, dnode_t
*root
)
218 return 1 + verify_node_count(nil
, root
->left
)
219 + verify_node_count(nil
, root
->right
);
223 * Verify that the tree contains the given node. This is done by
224 * traversing all of the nodes and comparing their pointers to the
225 * given pointer. Returns 1 if the node is found, otherwise
226 * returns zero. It is intended for debugging purposes.
229 static int verify_dict_has_node(dnode_t
*nil
, dnode_t
*root
, dnode_t
*node
)
233 || verify_dict_has_node(nil
, root
->left
, node
)
234 || verify_dict_has_node(nil
, root
->right
, node
);
241 * Dynamically allocate and initialize a dictionary object.
244 dict_t
*dict_create(dictcount_t maxcount
, dict_comp_t comp
)
246 dict_t
*new = malloc(sizeof *new);
250 new->allocnode
= dnode_alloc
;
251 new->freenode
= dnode_free
;
254 new->maxcount
= maxcount
;
255 new->nilnode
.left
= &new->nilnode
;
256 new->nilnode
.right
= &new->nilnode
;
257 new->nilnode
.parent
= &new->nilnode
;
258 new->nilnode
.color
= dnode_black
;
265 * Select a different set of node allocator routines.
268 void dict_set_allocator(dict_t
*dict
, dnode_alloc_t al
,
269 dnode_free_t fr
, void *context
)
271 assert (dict_count(dict
) == 0);
272 assert ((al
== NULL
&& fr
== NULL
) || (al
!= NULL
&& fr
!= NULL
));
274 dict
->allocnode
= al
? al
: dnode_alloc
;
275 dict
->freenode
= fr
? fr
: dnode_free
;
276 dict
->context
= context
;
280 * Free a dynamically allocated dictionary object. Removing the nodes
281 * from the tree before deleting it is required.
284 void dict_destroy(dict_t
*dict
)
286 assert (dict_isempty(dict
));
291 * Free all the nodes in the dictionary by using the dictionary's
292 * installed free routine. The dictionary is emptied.
295 void dict_free_nodes(dict_t
*dict
)
297 dnode_t
*nil
= dict_nil(dict
), *root
= dict_root(dict
);
298 free_nodes(dict
, root
, nil
);
300 dict
->nilnode
.left
= &dict
->nilnode
;
301 dict
->nilnode
.right
= &dict
->nilnode
;
305 * Obsolescent function, equivalent to dict_free_nodes
308 void dict_free(dict_t
*dict
)
310 #ifdef KAZLIB_OBSOLESCENT_DEBUG
311 assert ("call to obsolescent function dict_free()" && 0);
313 dict_free_nodes(dict
);
317 * Initialize a user-supplied dictionary object.
320 dict_t
*dict_init(dict_t
*dict
, dictcount_t maxcount
, dict_comp_t comp
)
322 dict
->compare
= comp
;
323 dict
->allocnode
= dnode_alloc
;
324 dict
->freenode
= dnode_free
;
325 dict
->context
= NULL
;
327 dict
->maxcount
= maxcount
;
328 dict
->nilnode
.left
= &dict
->nilnode
;
329 dict
->nilnode
.right
= &dict
->nilnode
;
330 dict
->nilnode
.parent
= &dict
->nilnode
;
331 dict
->nilnode
.color
= dnode_black
;
337 * Initialize a dictionary in the likeness of another dictionary
340 void dict_init_like(dict_t
*dict
, const dict_t
*template)
342 dict
->compare
= template->compare
;
343 dict
->allocnode
= template->allocnode
;
344 dict
->freenode
= template->freenode
;
345 dict
->context
= template->context
;
347 dict
->maxcount
= template->maxcount
;
348 dict
->nilnode
.left
= &dict
->nilnode
;
349 dict
->nilnode
.right
= &dict
->nilnode
;
350 dict
->nilnode
.parent
= &dict
->nilnode
;
351 dict
->nilnode
.color
= dnode_black
;
352 dict
->dupes
= template->dupes
;
354 assert (dict_similar(dict
, template));
358 * Remove all nodes from the dictionary (without freeing them in any way).
361 static void dict_clear(dict_t
*dict
)
364 dict
->nilnode
.left
= &dict
->nilnode
;
365 dict
->nilnode
.right
= &dict
->nilnode
;
366 dict
->nilnode
.parent
= &dict
->nilnode
;
367 assert (dict
->nilnode
.color
== dnode_black
);
372 * Verify the integrity of the dictionary structure. This is provided for
373 * debugging purposes, and should be placed in assert statements. Just because
374 * this function succeeds doesn't mean that the tree is not corrupt. Certain
375 * corruptions in the tree may simply cause undefined behavior.
378 int dict_verify(dict_t
*dict
)
380 dnode_t
*nil
= dict_nil(dict
), *root
= dict_root(dict
);
382 /* check that the sentinel node and root node are black */
383 if (root
->color
!= dnode_black
)
385 if (nil
->color
!= dnode_black
)
387 if (nil
->right
!= nil
)
389 /* nil->left is the root node; check that its parent pointer is nil */
390 if (nil
->left
->parent
!= nil
)
392 /* perform a weak test that the tree is a binary search tree */
393 if (!verify_bintree(dict
))
395 /* verify that the tree is a red-black tree */
396 if (!verify_redblack(nil
, root
))
398 if (verify_node_count(nil
, root
) != dict_count(dict
))
404 * Determine whether two dictionaries are similar: have the same comparison and
405 * allocator functions, and same status as to whether duplicates are allowed.
408 int dict_similar(const dict_t
*left
, const dict_t
*right
)
410 if (left
->compare
!= right
->compare
)
413 if (left
->allocnode
!= right
->allocnode
)
416 if (left
->freenode
!= right
->freenode
)
419 if (left
->context
!= right
->context
)
422 if (left
->dupes
!= right
->dupes
)
429 * Locate a node in the dictionary having the given key.
430 * If the node is not found, a null a pointer is returned (rather than
431 * a pointer that dictionary's nil sentinel node), otherwise a pointer to the
432 * located node is returned.
435 dnode_t
*dict_lookup(dict_t
*dict
, const void *key
)
437 dnode_t
*root
= dict_root(dict
);
438 dnode_t
*nil
= dict_nil(dict
);
442 /* simple binary search adapted for trees that contain duplicate keys */
444 while (root
!= nil
) {
445 result
= dict
->compare(key
, root
->key
);
451 if (!dict
->dupes
) { /* no duplicates, return match */
453 } else { /* could be dupes, find leftmost one */
457 while (root
!= nil
&& dict
->compare(key
, root
->key
))
459 } while (root
!= nil
);
469 * Look for the node corresponding to the lowest key that is equal to or
470 * greater than the given key. If there is no such node, return null.
473 dnode_t
*dict_lower_bound(dict_t
*dict
, const void *key
)
475 dnode_t
*root
= dict_root(dict
);
476 dnode_t
*nil
= dict_nil(dict
);
477 dnode_t
*tentative
= 0;
479 while (root
!= nil
) {
480 int result
= dict
->compare(key
, root
->key
);
484 } else if (result
< 0) {
501 * Look for the node corresponding to the greatest key that is equal to or
502 * lower than the given key. If there is no such node, return null.
505 dnode_t
*dict_upper_bound(dict_t
*dict
, const void *key
)
507 dnode_t
*root
= dict_root(dict
);
508 dnode_t
*nil
= dict_nil(dict
);
509 dnode_t
*tentative
= 0;
511 while (root
!= nil
) {
512 int result
= dict
->compare(key
, root
->key
);
516 } else if (result
> 0) {
533 * Insert a node into the dictionary. The node should have been
534 * initialized with a data field. All other fields are ignored.
535 * The behavior is undefined if the user attempts to insert into
536 * a dictionary that is already full (for which the dict_isfull()
537 * function returns true).
540 void dict_insert(dict_t
*dict
, dnode_t
*node
, const void *key
)
542 dnode_t
*where
= dict_root(dict
), *nil
= dict_nil(dict
);
543 dnode_t
*parent
= nil
, *uncle
, *grandpa
;
548 assert (!dict_isfull(dict
));
549 assert (!dict_contains(dict
, node
));
550 assert (!dnode_is_in_a_dict(node
));
552 /* basic binary tree insert */
554 while (where
!= nil
) {
556 result
= dict
->compare(key
, where
->key
);
557 /* trap attempts at duplicate key insertion unless it's explicitly allowed */
558 assert (dict
->dupes
|| result
!= 0);
562 where
= where
->right
;
565 assert (where
== nil
);
570 parent
->right
= node
;
572 node
->parent
= parent
;
578 /* red black adjustments */
580 node
->color
= dnode_red
;
582 while (parent
->color
== dnode_red
) {
583 grandpa
= parent
->parent
;
584 if (parent
== grandpa
->left
) {
585 uncle
= grandpa
->right
;
586 if (uncle
->color
== dnode_red
) { /* red parent, red uncle */
587 parent
->color
= dnode_black
;
588 uncle
->color
= dnode_black
;
589 grandpa
->color
= dnode_red
;
591 parent
= grandpa
->parent
;
592 } else { /* red parent, black uncle */
593 if (node
== parent
->right
) {
596 assert (grandpa
== parent
->parent
);
597 /* rotation between parent and child preserves grandpa */
599 parent
->color
= dnode_black
;
600 grandpa
->color
= dnode_red
;
601 rotate_right(grandpa
);
604 } else { /* symmetric cases: parent == parent->parent->right */
605 uncle
= grandpa
->left
;
606 if (uncle
->color
== dnode_red
) {
607 parent
->color
= dnode_black
;
608 uncle
->color
= dnode_black
;
609 grandpa
->color
= dnode_red
;
611 parent
= grandpa
->parent
;
613 if (node
== parent
->left
) {
614 rotate_right(parent
);
616 assert (grandpa
== parent
->parent
);
618 parent
->color
= dnode_black
;
619 grandpa
->color
= dnode_red
;
620 rotate_left(grandpa
);
626 dict_root(dict
)->color
= dnode_black
;
628 assert (dict_verify(dict
));
632 * Delete the given node from the dictionary. If the given node does not belong
633 * to the given dictionary, undefined behavior results. A pointer to the
634 * deleted node is returned.
637 dnode_t
*dict_delete(dict_t
*dict
, dnode_t
*delete)
639 dnode_t
*nil
= dict_nil(dict
), *child
, *delparent
= delete->parent
;
643 assert (!dict_isempty(dict
));
644 assert (dict_contains(dict
, delete));
647 * If the node being deleted has two children, then we replace it with its
648 * successor (i.e. the leftmost node in the right subtree.) By doing this,
649 * we avoid the traditional algorithm under which the successor's key and
650 * value *only* move to the deleted node and the successor is spliced out
651 * from the tree. We cannot use this approach because the user may hold
652 * pointers to the successor, or nodes may be inextricably tied to some
653 * other structures by way of embedding, etc. So we must splice out the
654 * node we are given, not some other node, and must not move contents from
655 * one node to another behind the user's back.
658 if (delete->left
!= nil
&& delete->right
!= nil
) {
659 dnode_t
*next
= dict_next(dict
, delete);
660 dnode_t
*nextparent
= next
->parent
;
661 dnode_color_t nextcolor
= next
->color
;
663 assert (next
!= nil
);
664 assert (next
->parent
!= nil
);
665 assert (next
->left
== nil
);
668 * First, splice out the successor from the tree completely, by
669 * moving up its right child into its place.
673 child
->parent
= nextparent
;
675 if (nextparent
->left
== next
) {
676 nextparent
->left
= child
;
678 assert (nextparent
->right
== next
);
679 nextparent
->right
= child
;
683 * Now that the successor has been extricated from the tree, install it
684 * in place of the node that we want deleted.
687 next
->parent
= delparent
;
688 next
->left
= delete->left
;
689 next
->right
= delete->right
;
690 next
->left
->parent
= next
;
691 next
->right
->parent
= next
;
692 next
->color
= delete->color
;
693 delete->color
= nextcolor
;
695 if (delparent
->left
== delete) {
696 delparent
->left
= next
;
698 assert (delparent
->right
== delete);
699 delparent
->right
= next
;
703 assert (delete != nil
);
704 assert (delete->left
== nil
|| delete->right
== nil
);
706 child
= (delete->left
!= nil
) ? delete->left
: delete->right
;
708 child
->parent
= delparent
= delete->parent
;
710 if (delete == delparent
->left
) {
711 delparent
->left
= child
;
713 assert (delete == delparent
->right
);
714 delparent
->right
= child
;
718 delete->parent
= NULL
;
719 delete->right
= NULL
;
724 assert (verify_bintree(dict
));
726 /* red-black adjustments */
728 if (delete->color
== dnode_black
) {
729 dnode_t
*parent
, *sister
;
731 dict_root(dict
)->color
= dnode_red
;
733 while (child
->color
== dnode_black
) {
734 parent
= child
->parent
;
735 if (child
== parent
->left
) {
736 sister
= parent
->right
;
737 assert (sister
!= nil
);
738 if (sister
->color
== dnode_red
) {
739 sister
->color
= dnode_black
;
740 parent
->color
= dnode_red
;
742 sister
= parent
->right
;
743 assert (sister
!= nil
);
745 if (sister
->left
->color
== dnode_black
746 && sister
->right
->color
== dnode_black
) {
747 sister
->color
= dnode_red
;
750 if (sister
->right
->color
== dnode_black
) {
751 assert (sister
->left
->color
== dnode_red
);
752 sister
->left
->color
= dnode_black
;
753 sister
->color
= dnode_red
;
754 rotate_right(sister
);
755 sister
= parent
->right
;
756 assert (sister
!= nil
);
758 sister
->color
= parent
->color
;
759 sister
->right
->color
= dnode_black
;
760 parent
->color
= dnode_black
;
764 } else { /* symmetric case: child == child->parent->right */
765 assert (child
== parent
->right
);
766 sister
= parent
->left
;
767 assert (sister
!= nil
);
768 if (sister
->color
== dnode_red
) {
769 sister
->color
= dnode_black
;
770 parent
->color
= dnode_red
;
771 rotate_right(parent
);
772 sister
= parent
->left
;
773 assert (sister
!= nil
);
775 if (sister
->right
->color
== dnode_black
776 && sister
->left
->color
== dnode_black
) {
777 sister
->color
= dnode_red
;
780 if (sister
->left
->color
== dnode_black
) {
781 assert (sister
->right
->color
== dnode_red
);
782 sister
->right
->color
= dnode_black
;
783 sister
->color
= dnode_red
;
785 sister
= parent
->left
;
786 assert (sister
!= nil
);
788 sister
->color
= parent
->color
;
789 sister
->left
->color
= dnode_black
;
790 parent
->color
= dnode_black
;
791 rotate_right(parent
);
797 child
->color
= dnode_black
;
798 dict_root(dict
)->color
= dnode_black
;
801 assert (dict_verify(dict
));
807 * Allocate a node using the dictionary's allocator routine, give it
811 int dict_alloc_insert(dict_t
*dict
, const void *key
, void *data
)
813 dnode_t
*node
= dict
->allocnode(dict
->context
);
816 dnode_init(node
, data
);
817 dict_insert(dict
, node
, key
);
823 void dict_delete_free(dict_t
*dict
, dnode_t
*node
)
825 dict_delete(dict
, node
);
826 dict
->freenode(node
, dict
->context
);
830 * Return the node with the lowest (leftmost) key. If the dictionary is empty
831 * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
834 dnode_t
*dict_first(dict_t
*dict
)
836 dnode_t
*nil
= dict_nil(dict
), *root
= dict_root(dict
), *left
;
839 while ((left
= root
->left
) != nil
)
842 return (root
== nil
) ? NULL
: root
;
846 * Return the node with the highest (rightmost) key. If the dictionary is empty
847 * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
850 dnode_t
*dict_last(dict_t
*dict
)
852 dnode_t
*nil
= dict_nil(dict
), *root
= dict_root(dict
), *right
;
855 while ((right
= root
->right
) != nil
)
858 return (root
== nil
) ? NULL
: root
;
862 * Return the given node's successor node---the node which has the
863 * next key in the the left to right ordering. If the node has
864 * no successor, a null pointer is returned rather than a pointer to
868 dnode_t
*dict_next(dict_t
*dict
, dnode_t
*curr
)
870 dnode_t
*nil
= dict_nil(dict
), *parent
, *left
;
872 if (curr
->right
!= nil
) {
874 while ((left
= curr
->left
) != nil
)
879 parent
= curr
->parent
;
881 while (parent
!= nil
&& curr
== parent
->right
) {
883 parent
= curr
->parent
;
886 return (parent
== nil
) ? NULL
: parent
;
890 * Return the given node's predecessor, in the key order.
891 * The nil sentinel node is returned if there is no predecessor.
894 dnode_t
*dict_prev(dict_t
*dict
, dnode_t
*curr
)
896 dnode_t
*nil
= dict_nil(dict
), *parent
, *right
;
898 if (curr
->left
!= nil
) {
900 while ((right
= curr
->right
) != nil
)
905 parent
= curr
->parent
;
907 while (parent
!= nil
&& curr
== parent
->left
) {
909 parent
= curr
->parent
;
912 return (parent
== nil
) ? NULL
: parent
;
915 void dict_allow_dupes(dict_t
*dict
)
927 dictcount_t
dict_count(dict_t
*dict
)
929 return dict
->nodecount
;
932 int dict_isempty(dict_t
*dict
)
934 return dict
->nodecount
== 0;
937 int dict_isfull(dict_t
*dict
)
939 return dict
->nodecount
== dict
->maxcount
;
942 int dict_contains(dict_t
*dict
, dnode_t
*node
)
944 return verify_dict_has_node(dict_nil(dict
), dict_root(dict
), node
);
947 static dnode_t
*dnode_alloc(void *context
)
949 return malloc(sizeof *dnode_alloc(NULL
));
952 static void dnode_free(dnode_t
*node
, void *context
)
957 dnode_t
*dnode_create(void *data
)
959 dnode_t
*new = malloc(sizeof *new);
969 dnode_t
*dnode_init(dnode_t
*dnode
, void *data
)
972 dnode
->parent
= NULL
;
978 void dnode_destroy(dnode_t
*dnode
)
980 assert (!dnode_is_in_a_dict(dnode
));
984 void *dnode_get(dnode_t
*dnode
)
989 const void *dnode_getkey(dnode_t
*dnode
)
994 void dnode_put(dnode_t
*dnode
, void *data
)
999 int dnode_is_in_a_dict(dnode_t
*dnode
)
1001 return (dnode
->parent
&& dnode
->left
&& dnode
->right
);
1004 void dict_process(dict_t
*dict
, void *context
, dnode_process_t function
)
1006 dnode_t
*node
= dict_first(dict
), *next
;
1008 while (node
!= NULL
) {
1009 /* check for callback function deleting */
1010 /* the next node from under us */
1011 assert (dict_contains(dict
, node
));
1012 next
= dict_next(dict
, node
);
1013 function(dict
, node
, context
);
1018 static void load_begin_internal(dict_load_t
*load
, dict_t
*dict
)
1020 load
->dictptr
= dict
;
1021 load
->nilnode
.left
= &load
->nilnode
;
1022 load
->nilnode
.right
= &load
->nilnode
;
1025 void dict_load_begin(dict_load_t
*load
, dict_t
*dict
)
1027 assert (dict_isempty(dict
));
1028 load_begin_internal(load
, dict
);
1031 void dict_load_next(dict_load_t
*load
, dnode_t
*newnode
, const void *key
)
1033 dict_t
*dict
= load
->dictptr
;
1034 dnode_t
*nil
= &load
->nilnode
;
1036 assert (!dnode_is_in_a_dict(newnode
));
1037 assert (dict
->nodecount
< dict
->maxcount
);
1040 if (dict
->nodecount
> 0) {
1042 assert (dict
->compare(nil
->left
->key
, key
) <= 0);
1044 assert (dict
->compare(nil
->left
->key
, key
) < 0);
1049 nil
->right
->left
= newnode
;
1050 nil
->right
= newnode
;
1051 newnode
->left
= nil
;
1055 void dict_load_end(dict_load_t
*load
)
1057 dict_t
*dict
= load
->dictptr
;
1058 dnode_t
*tree
[DICT_DEPTH_MAX
] = { 0 };
1059 dnode_t
*curr
, *dictnil
= dict_nil(dict
), *loadnil
= &load
->nilnode
, *next
;
1060 dnode_t
*complete
= 0;
1061 dictcount_t fullcount
= DICTCOUNT_T_MAX
, nodecount
= dict
->nodecount
;
1062 dictcount_t botrowcount
;
1063 unsigned baselevel
= 0, level
= 0, i
;
1065 assert (dnode_red
== 0 && dnode_black
== 1);
1067 while (fullcount
>= nodecount
&& fullcount
)
1070 botrowcount
= nodecount
- fullcount
;
1072 for (curr
= loadnil
->left
; curr
!= loadnil
; curr
= next
) {
1075 if (complete
== NULL
&& botrowcount
-- == 0) {
1076 assert (baselevel
== 0);
1077 assert (level
== 0);
1078 baselevel
= level
= 1;
1081 if (complete
!= 0) {
1083 complete
->right
= dictnil
;
1084 while (tree
[level
] != 0) {
1085 tree
[level
]->right
= complete
;
1086 complete
->parent
= tree
[level
];
1087 complete
= tree
[level
];
1093 if (complete
== NULL
) {
1094 curr
->left
= dictnil
;
1095 curr
->right
= dictnil
;
1096 curr
->color
= level
% 2;
1099 assert (level
== baselevel
);
1100 while (tree
[level
] != 0) {
1101 tree
[level
]->right
= complete
;
1102 complete
->parent
= tree
[level
];
1103 complete
= tree
[level
];
1107 curr
->left
= complete
;
1108 curr
->color
= (level
+ 1) % 2;
1109 complete
->parent
= curr
;
1116 if (complete
== NULL
)
1119 for (i
= 0; i
< DICT_DEPTH_MAX
; i
++) {
1121 tree
[i
]->right
= complete
;
1122 complete
->parent
= tree
[i
];
1127 dictnil
->color
= dnode_black
;
1128 dictnil
->right
= dictnil
;
1129 complete
->parent
= dictnil
;
1130 complete
->color
= dnode_black
;
1131 dict_root(dict
) = complete
;
1133 assert (dict_verify(dict
));
1136 void dict_merge(dict_t
*dest
, dict_t
*source
)
1139 dnode_t
*leftnode
= dict_first(dest
), *rightnode
= dict_first(source
);
1141 assert (dict_similar(dest
, source
));
1146 dest
->nodecount
= 0;
1147 load_begin_internal(&load
, dest
);
1150 if (leftnode
!= NULL
&& rightnode
!= NULL
) {
1151 if (dest
->compare(leftnode
->key
, rightnode
->key
) < 0)
1155 } else if (leftnode
!= NULL
) {
1157 } else if (rightnode
!= NULL
) {
1160 assert (leftnode
== NULL
&& rightnode
== NULL
);
1166 dnode_t
*next
= dict_next(dest
, leftnode
);
1168 leftnode
->left
= NULL
; /* suppress assertion in dict_load_next */
1170 dict_load_next(&load
, leftnode
, leftnode
->key
);
1177 dnode_t
*next
= dict_next(source
, rightnode
);
1179 rightnode
->left
= NULL
;
1181 dict_load_next(&load
, rightnode
, rightnode
->key
);
1188 dict_load_end(&load
);
1191 #ifdef KAZLIB_TEST_MAIN
1198 typedef char input_t
[256];
1200 static int tokenize(char *string
, ...)
1206 va_start(arglist
, string
);
1207 tokptr
= va_arg(arglist
, char **);
1209 while (*string
&& isspace((unsigned char) *string
))
1214 while (*string
&& !isspace((unsigned char) *string
))
1216 tokptr
= va_arg(arglist
, char **);
1227 static int comparef(const void *key1
, const void *key2
)
1229 return strcmp(key1
, key2
);
1232 static char *dupstring(char *str
)
1234 int sz
= strlen(str
) + 1;
1235 char *new = malloc(sz
);
1237 memcpy(new, str
, sz
);
1241 static dnode_t
*new_node(void *c
)
1243 static dnode_t few
[5];
1247 return few
+ count
++;
1252 static void del_node(dnode_t
*n
, void *c
)
1256 static int prompt
= 0;
1258 static void construct(dict_t
*d
)
1264 char *tok1
, *tok2
, *val
;
1267 "p turn prompt on\n"
1268 "q finish construction\n"
1269 "a <key> <val> add new entry\n";
1271 if (!dict_isempty(d
))
1272 puts("warning: dictionary not empty!");
1274 dict_load_begin(&dl
, d
);
1281 if (!fgets(in
, sizeof(input_t
), stdin
))
1295 if (tokenize(in
+1, &tok1
, &tok2
, (char **) 0) != 2) {
1299 key
= dupstring(tok1
);
1300 val
= dupstring(tok2
);
1301 dn
= dnode_create(val
);
1303 if (!key
|| !val
|| !dn
) {
1304 puts("out of memory");
1311 dict_load_next(&dl
, dn
, key
);
1327 dict_t
*d
= &darray
[0];
1330 char *tok1
, *tok2
, *val
;
1334 "a <key> <val> add value to dictionary\n"
1335 "d <key> delete value from dictionary\n"
1336 "l <key> lookup value in dictionary\n"
1337 "( <key> lookup lower bound\n"
1338 ") <key> lookup upper bound\n"
1339 "# <num> switch to alternate dictionary (0-9)\n"
1340 "j <num> <num> merge two dictionaries\n"
1341 "f free the whole dictionary\n"
1342 "k allow duplicate keys\n"
1343 "c show number of entries\n"
1344 "t dump whole dictionary in sort order\n"
1345 "m make dictionary out of sorted items\n"
1346 "p turn prompt on\n"
1347 "s switch to non-functioning allocator\n"
1350 for (i
= 0; i
< sizeof darray
/ sizeof *darray
; i
++)
1351 dict_init(&darray
[i
], DICTCOUNT_T_MAX
, comparef
);
1358 if (!fgets(in
, sizeof(input_t
), stdin
))
1366 if (tokenize(in
+1, &tok1
, &tok2
, (char **) 0) != 2) {
1370 key
= dupstring(tok1
);
1371 val
= dupstring(tok2
);
1374 puts("out of memory");
1379 if (!dict_alloc_insert(d
, key
, val
)) {
1380 puts("dict_alloc_insert failed");
1387 if (tokenize(in
+1, &tok1
, (char **) 0) != 1) {
1391 dn
= dict_lookup(d
, tok1
);
1393 puts("dict_lookup failed");
1396 val
= dnode_get(dn
);
1397 key
= dnode_getkey(dn
);
1398 dict_delete_free(d
, dn
);
1409 if (tokenize(in
+1, &tok1
, (char **) 0) != 1) {
1416 dn
= dict_lookup(d
, tok1
);
1419 dn
= dict_lower_bound(d
, tok1
);
1422 dn
= dict_upper_bound(d
, tok1
);
1426 puts("lookup failed");
1429 val
= dnode_get(dn
);
1436 dict_allow_dupes(d
);
1439 printf("%lu\n", (unsigned long) dict_count(d
));
1442 for (dn
= dict_first(d
); dn
; dn
= dict_next(d
, dn
)) {
1443 printf("%s\t%s\n", (char *) dnode_getkey(dn
),
1444 (char *) dnode_get(dn
));
1456 dict_set_allocator(d
, new_node
, del_node
, NULL
);
1459 if (tokenize(in
+1, &tok1
, (char **) 0) != 1) {
1463 int dictnum
= atoi(tok1
);
1464 if (dictnum
< 0 || dictnum
> 9) {
1465 puts("invalid number");
1468 d
= &darray
[dictnum
];
1472 if (tokenize(in
+1, &tok1
, &tok2
, (char **) 0) != 2) {
1476 int dict1
= atoi(tok1
), dict2
= atoi(tok2
);
1477 if (dict1
< 0 || dict1
> 9 || dict2
< 0 || dict2
> 9) {
1478 puts("invalid number");
1481 dict_merge(&darray
[dict1
], &darray
[dict2
]);