]>
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.
21 #include "isis_memory.h"
25 * These macros provide short convenient names for structure members,
26 * which are embellished with dict_ prefixes so that they are
27 * properly confined to the documented namespace. It's legal for a
28 * program which uses dict to define, for instance, a macro called ``parent''.
29 * Such a macro would interfere with the dnode_t struct definition.
30 * In general, highly portable and reusable C modules which expose their
31 * structures need to confine structure member names to well-defined spaces.
32 * The resulting identifiers aren't necessarily convenient to use, nor
33 * readable, in the implementation, however!
36 #define left dict_left
37 #define right dict_right
38 #define parent dict_parent
39 #define color dict_color
41 #define data dict_data
43 #define nilnode dict_nilnode
44 #define nodecount dict_nodecount
45 #define maxcount dict_maxcount
46 #define compare dict_compare
47 #define allocnode dict_allocnode
48 #define freenode dict_freenode
49 #define context dict_context
50 #define dupes dict_dupes
52 #define dictptr dict_dictptr
54 #define dict_root(D) ((D)->nilnode.left)
55 #define dict_nil(D) (&(D)->nilnode)
56 #define DICT_DEPTH_MAX 64
58 static dnode_t
*dnode_alloc(void *context
);
59 static void dnode_free(dnode_t
*node
, void *context
);
62 * Perform a ``left rotation'' adjustment on the tree. The given node P and
63 * its right child C are rearranged so that the P instead becomes the left
64 * child of C. The left subtree of C is inherited as the new right subtree
65 * for P. The ordering of the keys within the tree is thus preserved.
68 static void rotate_left(dnode_t
*upper
)
70 dnode_t
*lower
, *lowleft
, *upparent
;
73 upper
->right
= lowleft
= lower
->left
;
74 lowleft
->parent
= upper
;
76 lower
->parent
= upparent
= upper
->parent
;
78 /* don't need to check for root node here because root->parent is
79 the sentinel nil node, and root->parent->left points back to root */
81 if (upper
== upparent
->left
) {
82 upparent
->left
= lower
;
84 assert(upper
== upparent
->right
);
85 upparent
->right
= lower
;
89 upper
->parent
= lower
;
93 * This operation is the ``mirror'' image of rotate_left. It is
94 * the same procedure, but with left and right interchanged.
97 static void rotate_right(dnode_t
*upper
)
99 dnode_t
*lower
, *lowright
, *upparent
;
102 upper
->left
= lowright
= lower
->right
;
103 lowright
->parent
= upper
;
105 lower
->parent
= upparent
= upper
->parent
;
107 if (upper
== upparent
->right
) {
108 upparent
->right
= lower
;
110 assert(upper
== upparent
->left
);
111 upparent
->left
= lower
;
114 lower
->right
= upper
;
115 upper
->parent
= lower
;
119 * Do a postorder traversal of the tree rooted at the specified
120 * node and free everything under it. Used by dict_free().
123 static void free_nodes(dict_t
*dict
, dnode_t
*node
, dnode_t
*nil
)
127 free_nodes(dict
, node
->left
, nil
);
128 free_nodes(dict
, node
->right
, nil
);
129 dict
->freenode(node
, dict
->context
);
133 * This procedure performs a verification that the given subtree is a binary
134 * search tree. It performs an inorder traversal of the tree using the
135 * dict_next() successor function, verifying that the key of each node is
136 * strictly lower than that of its successor, if duplicates are not allowed,
137 * or lower or equal if duplicates are allowed. This function is used for
138 * debugging purposes.
141 static int verify_bintree(dict_t
*dict
)
143 dnode_t
*first
, *next
;
145 first
= dict_first(dict
);
148 while (first
&& (next
= dict_next(dict
, first
))) {
149 if (dict
->compare(first
->key
, next
->key
) > 0)
154 while (first
&& (next
= dict_next(dict
, first
))) {
155 if (dict
->compare(first
->key
, next
->key
) >= 0)
165 * This function recursively verifies that the given binary subtree satisfies
166 * three of the red black properties. It checks that every red node has only
167 * black children. It makes sure that each node is either red or black. And it
168 * checks that every path has the same count of black nodes from root to leaf.
169 * It returns the blackheight of the given subtree; this allows blackheights to
170 * be computed recursively and compared for left and right siblings for
171 * mismatches. It does not check for every nil node being black, because there
172 * is only one sentinel nil node. The return value of this function is the
173 * black height of the subtree rooted at the node ``root'', or zero if the
174 * subtree is not red-black.
177 #ifdef EXTREME_DICT_DEBUG
178 static unsigned int verify_redblack(dnode_t
*nil
, dnode_t
*root
)
180 unsigned height_left
, height_right
;
183 height_left
= verify_redblack(nil
, root
->left
);
184 height_right
= verify_redblack(nil
, root
->right
);
185 if (height_left
== 0 || height_right
== 0)
187 if (height_left
!= height_right
)
189 if (root
->color
== dnode_red
) {
190 if (root
->left
->color
!= dnode_black
)
192 if (root
->right
->color
!= dnode_black
)
196 if (root
->color
!= dnode_black
)
198 return height_left
+ 1;
205 * Compute the actual count of nodes by traversing the tree and
206 * return it. This could be compared against the stored count to
210 #ifdef EXTREME_DICT_DEBUG
211 static dictcount_t
verify_node_count(dnode_t
*nil
, dnode_t
*root
)
216 return 1 + verify_node_count(nil
, root
->left
)
217 + verify_node_count(nil
, root
->right
);
222 * Verify that the tree contains the given node. This is done by
223 * traversing all of the nodes and comparing their pointers to the
224 * given pointer. Returns 1 if the node is found, otherwise
225 * returns zero. It is intended for debugging purposes.
228 static int verify_dict_has_node(dnode_t
*nil
, dnode_t
*root
, dnode_t
*node
)
232 || verify_dict_has_node(nil
, root
->left
, node
)
233 || verify_dict_has_node(nil
, root
->right
, node
);
240 * Dynamically allocate and initialize a dictionary object.
243 dict_t
*dict_create(dictcount_t maxcount
, dict_comp_t comp
)
245 dict_t
*new = XCALLOC(MTYPE_ISIS_DICT
, sizeof(dict_t
));
248 new->allocnode
= dnode_alloc
;
249 new->freenode
= dnode_free
;
252 new->maxcount
= maxcount
;
253 new->nilnode
.left
= &new->nilnode
;
254 new->nilnode
.right
= &new->nilnode
;
255 new->nilnode
.parent
= &new->nilnode
;
256 new->nilnode
.color
= dnode_black
;
263 * Select a different set of node allocator routines.
266 void dict_set_allocator(dict_t
*dict
, dnode_alloc_t al
, dnode_free_t fr
,
269 assert(dict_count(dict
) == 0);
270 assert((al
== NULL
&& fr
== NULL
) || (al
!= NULL
&& fr
!= NULL
));
272 dict
->allocnode
= al
? al
: dnode_alloc
;
273 dict
->freenode
= fr
? fr
: dnode_free
;
274 dict
->context
= context
;
278 * Free a dynamically allocated dictionary object. Removing the nodes
279 * from the tree before deleting it is required.
282 void dict_destroy(dict_t
*dict
)
284 assert(dict_isempty(dict
));
285 XFREE(MTYPE_ISIS_DICT
, dict
);
289 * Free all the nodes in the dictionary by using the dictionary's
290 * installed free routine. The dictionary is emptied.
293 void dict_free_nodes(dict_t
*dict
)
295 dnode_t
*nil
= dict_nil(dict
), *root
= dict_root(dict
);
296 free_nodes(dict
, root
, nil
);
298 dict
->nilnode
.left
= &dict
->nilnode
;
299 dict
->nilnode
.right
= &dict
->nilnode
;
303 * Obsolescent function, equivalent to dict_free_nodes
306 void dict_free(dict_t
*dict
)
308 dict_free_nodes(dict
);
312 * Initialize a user-supplied dictionary object.
315 dict_t
*dict_init(dict_t
*dict
, dictcount_t maxcount
, dict_comp_t comp
)
317 dict
->compare
= comp
;
318 dict
->allocnode
= dnode_alloc
;
319 dict
->freenode
= dnode_free
;
320 dict
->context
= NULL
;
322 dict
->maxcount
= maxcount
;
323 dict
->nilnode
.left
= &dict
->nilnode
;
324 dict
->nilnode
.right
= &dict
->nilnode
;
325 dict
->nilnode
.parent
= &dict
->nilnode
;
326 dict
->nilnode
.color
= dnode_black
;
332 * Initialize a dictionary in the likeness of another dictionary
335 void dict_init_like(dict_t
*dict
, const dict_t
*template)
337 dict
->compare
= template->compare
;
338 dict
->allocnode
= template->allocnode
;
339 dict
->freenode
= template->freenode
;
340 dict
->context
= template->context
;
342 dict
->maxcount
= template->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
= template->dupes
;
349 assert(dict_similar(dict
, template));
353 * Remove all nodes from the dictionary (without freeing them in any way).
356 static void dict_clear(dict_t
*dict
)
359 dict
->nilnode
.left
= &dict
->nilnode
;
360 dict
->nilnode
.right
= &dict
->nilnode
;
361 dict
->nilnode
.parent
= &dict
->nilnode
;
362 assert(dict
->nilnode
.color
== dnode_black
);
367 * Verify the integrity of the dictionary structure. This is provided for
368 * debugging purposes, and should be placed in assert statements. Just because
369 * this function succeeds doesn't mean that the tree is not corrupt. Certain
370 * corruptions in the tree may simply cause undefined behavior.
373 int dict_verify(dict_t
*dict
)
375 #ifdef EXTREME_DICT_DEBUG
376 dnode_t
*nil
= dict_nil(dict
), *root
= dict_root(dict
);
378 /* check that the sentinel node and root node are black */
379 if (root
->color
!= dnode_black
)
381 if (nil
->color
!= dnode_black
)
383 if (nil
->right
!= nil
)
385 /* nil->left is the root node; check that its parent pointer is nil */
386 if (nil
->left
->parent
!= nil
)
388 /* perform a weak test that the tree is a binary search tree */
389 if (!verify_bintree(dict
))
391 /* verify that the tree is a red-black tree */
392 if (!verify_redblack(nil
, root
))
394 if (verify_node_count(nil
, root
) != dict_count(dict
))
401 * Determine whether two dictionaries are similar: have the same comparison and
402 * allocator functions, and same status as to whether duplicates are allowed.
405 int dict_similar(const dict_t
*left
, const dict_t
*right
)
407 if (left
->compare
!= right
->compare
)
410 if (left
->allocnode
!= right
->allocnode
)
413 if (left
->freenode
!= right
->freenode
)
416 if (left
->context
!= right
->context
)
419 if (left
->dupes
!= right
->dupes
)
426 * Locate a node in the dictionary having the given key.
427 * If the node is not found, a null a pointer is returned (rather than
428 * a pointer that dictionary's nil sentinel node), otherwise a pointer to the
429 * located node is returned.
432 dnode_t
*dict_lookup(dict_t
*dict
, const void *key
)
434 dnode_t
*root
= dict_root(dict
);
435 dnode_t
*nil
= dict_nil(dict
);
439 /* simple binary search adapted for trees that contain duplicate keys */
441 while (root
!= nil
) {
442 result
= dict
->compare(key
, root
->key
);
448 if (!dict
->dupes
) { /* no duplicates, return match
451 } else { /* could be dupes, find leftmost one */
456 && dict
->compare(key
, root
->key
))
458 } while (root
!= nil
);
468 * Look for the node corresponding to the lowest key that is equal to or
469 * greater than the given key. If there is no such node, return null.
472 dnode_t
*dict_lower_bound(dict_t
*dict
, const void *key
)
474 dnode_t
*root
= dict_root(dict
);
475 dnode_t
*nil
= dict_nil(dict
);
476 dnode_t
*tentative
= 0;
478 while (root
!= nil
) {
479 int result
= dict
->compare(key
, root
->key
);
483 } else if (result
< 0) {
500 * Look for the node corresponding to the greatest key that is equal to or
501 * lower than the given key. If there is no such node, return null.
504 dnode_t
*dict_upper_bound(dict_t
*dict
, const void *key
)
506 dnode_t
*root
= dict_root(dict
);
507 dnode_t
*nil
= dict_nil(dict
);
508 dnode_t
*tentative
= 0;
510 while (root
!= nil
) {
511 int result
= dict
->compare(key
, root
->key
);
515 } else if (result
> 0) {
532 * Insert a node into the dictionary. The node should have been
533 * initialized with a data field. All other fields are ignored.
534 * The behavior is undefined if the user attempts to insert into
535 * a dictionary that is already full (for which the dict_isfull()
536 * function returns true).
539 void dict_insert(dict_t
*dict
, dnode_t
*node
, const void *key
)
541 dnode_t
*where
= dict_root(dict
), *nil
= dict_nil(dict
);
542 dnode_t
*parent
= nil
, *uncle
, *grandpa
;
547 assert(!dict_isfull(dict
));
548 assert(!dict_contains(dict
, node
));
549 assert(!dnode_is_in_a_dict(node
));
551 /* basic binary tree insert */
553 while (where
!= nil
) {
555 result
= dict
->compare(key
, where
->key
);
556 /* trap attempts at duplicate key insertion unless it's
557 * 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
;
587 == dnode_red
) { /* red parent, red uncle */
588 parent
->color
= dnode_black
;
589 uncle
->color
= dnode_black
;
590 grandpa
->color
= dnode_red
;
592 parent
= grandpa
->parent
;
593 } else { /* red parent, black uncle */
594 if (node
== parent
->right
) {
597 assert(grandpa
== parent
->parent
);
598 /* rotation between parent and child
599 * preserves grandpa */
601 parent
->color
= dnode_black
;
602 grandpa
->color
= dnode_red
;
603 rotate_right(grandpa
);
606 } else { /* symmetric cases: parent == parent->parent->right */
607 uncle
= grandpa
->left
;
608 if (uncle
->color
== dnode_red
) {
609 parent
->color
= dnode_black
;
610 uncle
->color
= dnode_black
;
611 grandpa
->color
= dnode_red
;
613 parent
= grandpa
->parent
;
615 if (node
== parent
->left
) {
616 rotate_right(parent
);
618 assert(grandpa
== parent
->parent
);
620 parent
->color
= dnode_black
;
621 grandpa
->color
= dnode_red
;
622 rotate_left(grandpa
);
628 dict_root(dict
)->color
= dnode_black
;
630 assert(dict_verify(dict
));
634 * Delete the given node from the dictionary. If the given node does not belong
635 * to the given dictionary, undefined behavior results. A pointer to the
636 * deleted node is returned.
639 dnode_t
*dict_delete(dict_t
*dict
, dnode_t
*delete)
641 dnode_t
*nil
= dict_nil(dict
), *child
, *delparent
= delete->parent
;
645 assert(!dict_isempty(dict
));
646 assert(dict_contains(dict
, delete));
649 * If the node being deleted has two children, then we replace it with
651 * successor (i.e. the leftmost node in the right subtree.) By doing
653 * we avoid the traditional algorithm under which the successor's key
655 * value *only* move to the deleted node and the successor is spliced
657 * from the tree. We cannot use this approach because the user may hold
658 * pointers to the successor, or nodes may be inextricably tied to some
659 * other structures by way of embedding, etc. So we must splice out the
660 * node we are given, not some other node, and must not move contents
662 * one node to another behind the user's back.
665 if (delete->left
!= nil
&& delete->right
!= nil
) {
666 dnode_t
*next
= dict_next(dict
, delete);
668 dnode_t
*nextparent
= next
->parent
;
669 dnode_color_t nextcolor
= next
->color
;
672 assert(next
->parent
!= nil
);
673 assert(next
->left
== nil
);
676 * First, splice out the successor from the tree completely, by
677 * moving up its right child into its place.
681 child
->parent
= nextparent
;
683 if (nextparent
->left
== next
) {
684 nextparent
->left
= child
;
686 assert(nextparent
->right
== next
);
687 nextparent
->right
= child
;
691 * Now that the successor has been extricated from the tree,
693 * in place of the node that we want deleted.
696 next
->parent
= delparent
;
697 next
->left
= delete->left
;
698 next
->right
= delete->right
;
699 next
->left
->parent
= next
;
700 next
->right
->parent
= next
;
701 next
->color
= delete->color
;
702 delete->color
= nextcolor
;
704 if (delparent
->left
== delete) {
705 delparent
->left
= next
;
707 assert(delparent
->right
== delete);
708 delparent
->right
= next
;
712 assert(delete != nil
);
713 assert(delete->left
== nil
|| delete->right
== nil
);
715 child
= (delete->left
!= nil
) ? delete->left
: delete->right
;
717 child
->parent
= delparent
= delete->parent
;
719 if (delete == delparent
->left
) {
720 delparent
->left
= child
;
722 assert(delete == delparent
->right
);
723 delparent
->right
= child
;
727 delete->parent
= NULL
;
728 delete->right
= NULL
;
733 assert(verify_bintree(dict
));
735 /* red-black adjustments */
737 if (delete->color
== dnode_black
) {
738 dnode_t
*parent
, *sister
;
740 dict_root(dict
)->color
= dnode_red
;
742 while (child
->color
== dnode_black
) {
743 parent
= child
->parent
;
744 if (child
== parent
->left
) {
745 sister
= parent
->right
;
746 assert(sister
!= nil
);
747 if (sister
->color
== dnode_red
) {
748 sister
->color
= dnode_black
;
749 parent
->color
= dnode_red
;
751 sister
= parent
->right
;
752 assert(sister
!= nil
);
754 if (sister
->left
->color
== dnode_black
755 && sister
->right
->color
== dnode_black
) {
756 sister
->color
= dnode_red
;
759 if (sister
->right
->color
761 assert(sister
->left
->color
763 sister
->left
->color
=
765 sister
->color
= dnode_red
;
766 rotate_right(sister
);
767 sister
= parent
->right
;
768 assert(sister
!= nil
);
770 sister
->color
= parent
->color
;
771 sister
->right
->color
= dnode_black
;
772 parent
->color
= dnode_black
;
776 } else { /* symmetric case: child ==
777 child->parent->right */
778 assert(child
== parent
->right
);
779 sister
= parent
->left
;
780 assert(sister
!= nil
);
781 if (sister
->color
== dnode_red
) {
782 sister
->color
= dnode_black
;
783 parent
->color
= dnode_red
;
784 rotate_right(parent
);
785 sister
= parent
->left
;
786 assert(sister
!= nil
);
788 if (sister
->right
->color
== dnode_black
789 && sister
->left
->color
== dnode_black
) {
790 sister
->color
= dnode_red
;
793 if (sister
->left
->color
795 assert(sister
->right
->color
797 sister
->right
->color
=
799 sister
->color
= dnode_red
;
801 sister
= parent
->left
;
802 assert(sister
!= nil
);
804 sister
->color
= parent
->color
;
805 sister
->left
->color
= dnode_black
;
806 parent
->color
= dnode_black
;
807 rotate_right(parent
);
813 child
->color
= dnode_black
;
814 dict_root(dict
)->color
= dnode_black
;
817 assert(dict_verify(dict
));
823 * Allocate a node using the dictionary's allocator routine, give it
827 int dict_alloc_insert(dict_t
*dict
, const void *key
, void *data
)
829 dnode_t
*node
= dict
->allocnode(dict
->context
);
832 dnode_init(node
, data
);
833 dict_insert(dict
, node
, key
);
839 void dict_delete_free(dict_t
*dict
, dnode_t
*node
)
841 dict_delete(dict
, node
);
842 dict
->freenode(node
, dict
->context
);
846 * Return the node with the lowest (leftmost) key. If the dictionary is empty
847 * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
850 dnode_t
*dict_first(dict_t
*dict
)
852 dnode_t
*nil
= dict_nil(dict
), *root
= dict_root(dict
), *left
;
855 while ((left
= root
->left
) != nil
)
858 return (root
== nil
) ? NULL
: root
;
862 * Return the node with the highest (rightmost) key. If the dictionary is empty
863 * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
866 dnode_t
*dict_last(dict_t
*dict
)
868 dnode_t
*nil
= dict_nil(dict
), *root
= dict_root(dict
), *right
;
871 while ((right
= root
->right
) != nil
)
874 return (root
== nil
) ? NULL
: root
;
878 * Return the given node's successor node---the node which has the
879 * next key in the the left to right ordering. If the node has
880 * no successor, a null pointer is returned rather than a pointer to
884 dnode_t
*dict_next(dict_t
*dict
, dnode_t
*curr
)
886 dnode_t
*nil
= dict_nil(dict
), *parent
, *left
;
888 if (curr
->right
!= nil
) {
890 while ((left
= curr
->left
) != nil
)
895 parent
= curr
->parent
;
897 while (parent
!= nil
&& curr
== parent
->right
) {
899 parent
= curr
->parent
;
902 return (parent
== nil
) ? NULL
: parent
;
906 * Return the given node's predecessor, in the key order.
907 * The nil sentinel node is returned if there is no predecessor.
910 dnode_t
*dict_prev(dict_t
*dict
, dnode_t
*curr
)
912 dnode_t
*nil
= dict_nil(dict
), *parent
, *right
;
914 if (curr
->left
!= nil
) {
916 while ((right
= curr
->right
) != nil
)
921 parent
= curr
->parent
;
923 while (parent
!= nil
&& curr
== parent
->left
) {
925 parent
= curr
->parent
;
928 return (parent
== nil
) ? NULL
: parent
;
931 void dict_allow_dupes(dict_t
*dict
)
943 dictcount_t
dict_count(dict_t
*dict
)
945 return dict
->nodecount
;
948 int dict_isempty(dict_t
*dict
)
950 return dict
->nodecount
== 0;
953 int dict_isfull(dict_t
*dict
)
955 return dict
->nodecount
== dict
->maxcount
;
958 int dict_contains(dict_t
*dict
, dnode_t
*node
)
960 return verify_dict_has_node(dict_nil(dict
), dict_root(dict
), node
);
963 static dnode_t
*dnode_alloc(void *context
)
965 return XCALLOC(MTYPE_ISIS_DICT_NODE
, sizeof(dnode_t
));
968 static void dnode_free(dnode_t
*node
, void *context
)
970 XFREE(MTYPE_ISIS_DICT_NODE
, node
);
973 dnode_t
*dnode_create(void *data
)
975 dnode_t
*new = XCALLOC(MTYPE_ISIS_DICT_NODE
, sizeof(dnode_t
));
985 dnode_t
*dnode_init(dnode_t
*dnode
, void *data
)
988 dnode
->parent
= NULL
;
994 void dnode_destroy(dnode_t
*dnode
)
996 assert(!dnode_is_in_a_dict(dnode
));
997 XFREE(MTYPE_ISIS_DICT_NODE
, dnode
);
1000 void *dnode_get(dnode_t
*dnode
)
1005 const void *dnode_getkey(dnode_t
*dnode
)
1010 void dnode_put(dnode_t
*dnode
, void *data
)
1015 int dnode_is_in_a_dict(dnode_t
*dnode
)
1017 return (dnode
->parent
&& dnode
->left
&& dnode
->right
);
1020 void dict_process(dict_t
*dict
, void *context
, dnode_process_t function
)
1022 dnode_t
*node
= dict_first(dict
), *next
;
1024 while (node
!= NULL
) {
1025 /* check for callback function deleting */
1026 /* the next node from under us */
1027 assert(dict_contains(dict
, node
));
1028 next
= dict_next(dict
, node
);
1029 function(dict
, node
, context
);
1034 static void load_begin_internal(dict_load_t
*load
, dict_t
*dict
)
1036 load
->dictptr
= dict
;
1037 load
->nilnode
.left
= &load
->nilnode
;
1038 load
->nilnode
.right
= &load
->nilnode
;
1041 void dict_load_begin(dict_load_t
*load
, dict_t
*dict
)
1043 assert(dict_isempty(dict
));
1044 load_begin_internal(load
, dict
);
1047 void dict_load_next(dict_load_t
*load
, dnode_t
*newnode
, const void *key
)
1049 dict_t
*dict
= load
->dictptr
;
1050 dnode_t
*nil
= &load
->nilnode
;
1052 assert(!dnode_is_in_a_dict(newnode
));
1053 assert(dict
->nodecount
< dict
->maxcount
);
1056 if (dict
->nodecount
> 0) {
1058 assert(dict
->compare(nil
->left
->key
, key
) <= 0);
1060 assert(dict
->compare(nil
->left
->key
, key
) < 0);
1065 nil
->right
->left
= newnode
;
1066 nil
->right
= newnode
;
1067 newnode
->left
= nil
;
1071 void dict_load_end(dict_load_t
*load
)
1073 dict_t
*dict
= load
->dictptr
;
1074 dnode_t
*tree
[DICT_DEPTH_MAX
] = {0};
1075 dnode_t
*curr
, *dictnil
= dict_nil(dict
), *loadnil
= &load
->nilnode
,
1077 dnode_t
*complete
= 0;
1078 dictcount_t fullcount
= DICTCOUNT_T_MAX
, nodecount
= dict
->nodecount
;
1079 dictcount_t botrowcount
;
1080 unsigned baselevel
= 0, level
= 0, i
;
1082 assert(dnode_red
== 0 && dnode_black
== 1);
1084 while (fullcount
>= nodecount
&& fullcount
)
1087 botrowcount
= nodecount
- fullcount
;
1089 for (curr
= loadnil
->left
; curr
!= loadnil
; curr
= next
) {
1092 if (complete
== NULL
&& botrowcount
-- == 0) {
1093 assert(baselevel
== 0);
1095 baselevel
= level
= 1;
1098 if (complete
!= 0) {
1100 complete
->right
= dictnil
;
1101 while (tree
[level
] != 0) {
1102 tree
[level
]->right
= complete
;
1103 complete
->parent
= tree
[level
];
1104 complete
= tree
[level
];
1110 if (complete
== NULL
) {
1111 curr
->left
= dictnil
;
1112 curr
->right
= dictnil
;
1113 curr
->color
= level
% 2;
1116 assert(level
== baselevel
);
1117 while (tree
[level
] != 0) {
1118 tree
[level
]->right
= complete
;
1119 complete
->parent
= tree
[level
];
1120 complete
= tree
[level
];
1124 curr
->left
= complete
;
1125 curr
->color
= (level
+ 1) % 2;
1126 complete
->parent
= curr
;
1133 if (complete
== NULL
)
1136 for (i
= 0; i
< DICT_DEPTH_MAX
; i
++) {
1138 tree
[i
]->right
= complete
;
1139 complete
->parent
= tree
[i
];
1144 dictnil
->color
= dnode_black
;
1145 dictnil
->right
= dictnil
;
1146 complete
->parent
= dictnil
;
1147 complete
->color
= dnode_black
;
1148 dict_root(dict
) = complete
;
1150 assert(dict_verify(dict
));
1153 void dict_merge(dict_t
*dest
, dict_t
*source
)
1156 dnode_t
*leftnode
= dict_first(dest
), *rightnode
= dict_first(source
);
1158 assert(dict_similar(dest
, source
));
1163 dest
->nodecount
= 0;
1164 load_begin_internal(&load
, dest
);
1167 if (leftnode
!= NULL
&& rightnode
!= NULL
) {
1168 if (dest
->compare(leftnode
->key
, rightnode
->key
) < 0)
1172 } else if (leftnode
!= NULL
) {
1174 } else if (rightnode
!= NULL
) {
1177 assert(leftnode
== NULL
&& rightnode
== NULL
);
1182 dnode_t
*next
= dict_next(dest
, leftnode
);
1185 NULL
; /* suppress assertion in dict_load_next */
1187 dict_load_next(&load
, leftnode
, leftnode
->key
);
1193 dnode_t
*next
= dict_next(source
, rightnode
);
1195 rightnode
->left
= NULL
;
1197 dict_load_next(&load
, rightnode
, rightnode
->key
);
1204 dict_load_end(&load
);
1207 #ifdef KAZLIB_TEST_MAIN
1214 typedef char input_t
[256];
1216 static int tokenize(char *string
, ...)
1222 va_start(arglist
, string
);
1223 tokptr
= va_arg(arglist
, char **);
1225 while (*string
&& isspace((unsigned char)*string
))
1230 while (*string
&& !isspace((unsigned char)*string
))
1232 tokptr
= va_arg(arglist
, char **);
1243 static int comparef(const void *key1
, const void *key2
)
1245 return strcmp(key1
, key2
);
1248 static char *dupstring(char *str
)
1250 int sz
= strlen(str
) + 1;
1251 char *new = XCALLOC(MTYPE_ISIS_TMP
, sz
);
1253 memcpy(new, str
, sz
);
1257 static dnode_t
*new_node(void *c
)
1259 static dnode_t few
[5];
1263 return few
+ count
++;
1268 static void del_node(dnode_t
*n
, void *c
)
1272 static int prompt
= 0;
1274 static void construct(dict_t
*d
)
1280 char *tok1
, *tok2
, *val
;
1283 "p turn prompt on\n"
1284 "q finish construction\n"
1285 "a <key> <val> add new entry\n";
1287 if (!dict_isempty(d
))
1288 puts("warning: dictionary not empty!");
1290 dict_load_begin(&dl
, d
);
1297 if (!fgets(in
, sizeof(input_t
), stdin
))
1311 if (tokenize(in
+ 1, &tok1
, &tok2
, (char **)0) != 2) {
1315 key
= dupstring(tok1
);
1316 val
= dupstring(tok2
);
1317 dn
= dnode_create(val
);
1319 if (!key
|| !val
|| !dn
) {
1320 puts("out of memory");
1326 dict_load_next(&dl
, dn
, key
);
1342 dict_t
*d
= &darray
[0];
1345 char *tok1
, *tok2
, *val
;
1349 "a <key> <val> add value to dictionary\n"
1350 "d <key> delete value from dictionary\n"
1351 "l <key> lookup value in dictionary\n"
1352 "( <key> lookup lower bound\n"
1353 ") <key> lookup upper bound\n"
1354 "# <num> switch to alternate dictionary (0-9)\n"
1355 "j <num> <num> merge two dictionaries\n"
1356 "f free the whole dictionary\n"
1357 "k allow duplicate keys\n"
1358 "c show number of entries\n"
1359 "t dump whole dictionary in sort order\n"
1360 "m make dictionary out of sorted items\n"
1361 "p turn prompt on\n"
1362 "s switch to non-functioning allocator\n"
1365 for (i
= 0; i
< 10; i
++)
1366 dict_init(&darray
[i
], DICTCOUNT_T_MAX
, comparef
);
1373 if (!fgets(in
, sizeof(input_t
), stdin
))
1381 if (tokenize(in
+ 1, &tok1
, &tok2
, (char **)0) != 2) {
1385 key
= dupstring(tok1
);
1386 val
= dupstring(tok2
);
1389 puts("out of memory");
1394 if (!dict_alloc_insert(d
, key
, val
)) {
1395 puts("dict_alloc_insert failed");
1402 if (tokenize(in
+ 1, &tok1
, (char **)0) != 1) {
1406 dn
= dict_lookup(d
, tok1
);
1408 puts("dict_lookup failed");
1411 val
= dnode_get(dn
);
1412 key
= dnode_getkey(dn
);
1413 dict_delete_free(d
, dn
);
1424 if (tokenize(in
+ 1, &tok1
, (char **)0) != 1) {
1431 dn
= dict_lookup(d
, tok1
);
1434 dn
= dict_lower_bound(d
, tok1
);
1437 dn
= dict_upper_bound(d
, tok1
);
1441 puts("lookup failed");
1444 val
= dnode_get(dn
);
1451 dict_allow_dupes(d
);
1454 printf("%lu\n", (unsigned long)dict_count(d
));
1457 for (dn
= dict_first(d
); dn
; dn
= dict_next(d
, dn
)) {
1458 printf("%s\t%s\n", (char *)dnode_getkey(dn
),
1459 (char *)dnode_get(dn
));
1471 dict_set_allocator(d
, new_node
, del_node
, NULL
);
1474 if (tokenize(in
+ 1, &tok1
, (char **)0) != 1) {
1478 int dictnum
= atoi(tok1
);
1479 if (dictnum
< 0 || dictnum
> 9) {
1480 puts("invalid number");
1483 d
= &darray
[dictnum
];
1487 if (tokenize(in
+ 1, &tok1
, &tok2
, (char **)0) != 2) {
1491 int dict1
= atoi(tok1
), dict2
= atoi(tok2
);
1492 if (dict1
< 0 || dict1
> 9 || dict2
< 0
1494 puts("invalid number");
1497 dict_merge(&darray
[dict1
], &darray
[dict2
]);