]>
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 static unsigned int verify_redblack(dnode_t
*nil
, dnode_t
*root
)
179 unsigned height_left
, height_right
;
182 height_left
= verify_redblack(nil
, root
->left
);
183 height_right
= verify_redblack(nil
, root
->right
);
184 if (height_left
== 0 || height_right
== 0)
186 if (height_left
!= height_right
)
188 if (root
->color
== dnode_red
) {
189 if (root
->left
->color
!= dnode_black
)
191 if (root
->right
->color
!= dnode_black
)
195 if (root
->color
!= dnode_black
)
197 return height_left
+ 1;
203 * Compute the actual count of nodes by traversing the tree and
204 * return it. This could be compared against the stored count to
208 static dictcount_t
verify_node_count(dnode_t
*nil
, dnode_t
*root
)
213 return 1 + verify_node_count(nil
, root
->left
)
214 + verify_node_count(nil
, root
->right
);
218 * Verify that the tree contains the given node. This is done by
219 * traversing all of the nodes and comparing their pointers to the
220 * given pointer. Returns 1 if the node is found, otherwise
221 * returns zero. It is intended for debugging purposes.
224 static int verify_dict_has_node(dnode_t
*nil
, dnode_t
*root
, dnode_t
*node
)
228 || verify_dict_has_node(nil
, root
->left
, node
)
229 || verify_dict_has_node(nil
, root
->right
, node
);
236 * Dynamically allocate and initialize a dictionary object.
239 dict_t
*dict_create(dictcount_t maxcount
, dict_comp_t comp
)
241 dict_t
*new = XCALLOC(MTYPE_ISIS_DICT
, sizeof(dict_t
));
245 new->allocnode
= dnode_alloc
;
246 new->freenode
= dnode_free
;
249 new->maxcount
= maxcount
;
250 new->nilnode
.left
= &new->nilnode
;
251 new->nilnode
.right
= &new->nilnode
;
252 new->nilnode
.parent
= &new->nilnode
;
253 new->nilnode
.color
= dnode_black
;
260 * Select a different set of node allocator routines.
263 void dict_set_allocator(dict_t
*dict
, dnode_alloc_t al
,
264 dnode_free_t fr
, void *context
)
266 assert (dict_count(dict
) == 0);
267 assert ((al
== NULL
&& fr
== NULL
) || (al
!= NULL
&& fr
!= NULL
));
269 dict
->allocnode
= al
? al
: dnode_alloc
;
270 dict
->freenode
= fr
? fr
: dnode_free
;
271 dict
->context
= context
;
275 * Free a dynamically allocated dictionary object. Removing the nodes
276 * from the tree before deleting it is required.
279 void dict_destroy(dict_t
*dict
)
281 assert (dict_isempty(dict
));
282 XFREE(MTYPE_ISIS_DICT
, dict
);
286 * Free all the nodes in the dictionary by using the dictionary's
287 * installed free routine. The dictionary is emptied.
290 void dict_free_nodes(dict_t
*dict
)
292 dnode_t
*nil
= dict_nil(dict
), *root
= dict_root(dict
);
293 free_nodes(dict
, root
, nil
);
295 dict
->nilnode
.left
= &dict
->nilnode
;
296 dict
->nilnode
.right
= &dict
->nilnode
;
300 * Obsolescent function, equivalent to dict_free_nodes
303 void dict_free(dict_t
*dict
)
305 dict_free_nodes(dict
);
309 * Initialize a user-supplied dictionary object.
312 dict_t
*dict_init(dict_t
*dict
, dictcount_t maxcount
, dict_comp_t comp
)
314 dict
->compare
= comp
;
315 dict
->allocnode
= dnode_alloc
;
316 dict
->freenode
= dnode_free
;
317 dict
->context
= NULL
;
319 dict
->maxcount
= maxcount
;
320 dict
->nilnode
.left
= &dict
->nilnode
;
321 dict
->nilnode
.right
= &dict
->nilnode
;
322 dict
->nilnode
.parent
= &dict
->nilnode
;
323 dict
->nilnode
.color
= dnode_black
;
329 * Initialize a dictionary in the likeness of another dictionary
332 void dict_init_like(dict_t
*dict
, const dict_t
*template)
334 dict
->compare
= template->compare
;
335 dict
->allocnode
= template->allocnode
;
336 dict
->freenode
= template->freenode
;
337 dict
->context
= template->context
;
339 dict
->maxcount
= template->maxcount
;
340 dict
->nilnode
.left
= &dict
->nilnode
;
341 dict
->nilnode
.right
= &dict
->nilnode
;
342 dict
->nilnode
.parent
= &dict
->nilnode
;
343 dict
->nilnode
.color
= dnode_black
;
344 dict
->dupes
= template->dupes
;
346 assert (dict_similar(dict
, template));
350 * Remove all nodes from the dictionary (without freeing them in any way).
353 static void dict_clear(dict_t
*dict
)
356 dict
->nilnode
.left
= &dict
->nilnode
;
357 dict
->nilnode
.right
= &dict
->nilnode
;
358 dict
->nilnode
.parent
= &dict
->nilnode
;
359 assert (dict
->nilnode
.color
== dnode_black
);
364 * Verify the integrity of the dictionary structure. This is provided for
365 * debugging purposes, and should be placed in assert statements. Just because
366 * this function succeeds doesn't mean that the tree is not corrupt. Certain
367 * corruptions in the tree may simply cause undefined behavior.
370 int dict_verify(dict_t
*dict
)
372 dnode_t
*nil
= dict_nil(dict
), *root
= dict_root(dict
);
374 /* check that the sentinel node and root node are black */
375 if (root
->color
!= dnode_black
)
377 if (nil
->color
!= dnode_black
)
379 if (nil
->right
!= nil
)
381 /* nil->left is the root node; check that its parent pointer is nil */
382 if (nil
->left
->parent
!= nil
)
384 /* perform a weak test that the tree is a binary search tree */
385 if (!verify_bintree(dict
))
387 /* verify that the tree is a red-black tree */
388 if (!verify_redblack(nil
, root
))
390 if (verify_node_count(nil
, root
) != dict_count(dict
))
396 * Determine whether two dictionaries are similar: have the same comparison and
397 * allocator functions, and same status as to whether duplicates are allowed.
400 int dict_similar(const dict_t
*left
, const dict_t
*right
)
402 if (left
->compare
!= right
->compare
)
405 if (left
->allocnode
!= right
->allocnode
)
408 if (left
->freenode
!= right
->freenode
)
411 if (left
->context
!= right
->context
)
414 if (left
->dupes
!= right
->dupes
)
421 * Locate a node in the dictionary having the given key.
422 * If the node is not found, a null a pointer is returned (rather than
423 * a pointer that dictionary's nil sentinel node), otherwise a pointer to the
424 * located node is returned.
427 dnode_t
*dict_lookup(dict_t
*dict
, const void *key
)
429 dnode_t
*root
= dict_root(dict
);
430 dnode_t
*nil
= dict_nil(dict
);
434 /* simple binary search adapted for trees that contain duplicate keys */
436 while (root
!= nil
) {
437 result
= dict
->compare(key
, root
->key
);
443 if (!dict
->dupes
) { /* no duplicates, return match */
445 } else { /* could be dupes, find leftmost one */
449 while (root
!= nil
&& dict
->compare(key
, root
->key
))
451 } while (root
!= nil
);
461 * Look for the node corresponding to the lowest key that is equal to or
462 * greater than the given key. If there is no such node, return null.
465 dnode_t
*dict_lower_bound(dict_t
*dict
, const void *key
)
467 dnode_t
*root
= dict_root(dict
);
468 dnode_t
*nil
= dict_nil(dict
);
469 dnode_t
*tentative
= 0;
471 while (root
!= nil
) {
472 int result
= dict
->compare(key
, root
->key
);
476 } else if (result
< 0) {
493 * Look for the node corresponding to the greatest key that is equal to or
494 * lower than the given key. If there is no such node, return null.
497 dnode_t
*dict_upper_bound(dict_t
*dict
, const void *key
)
499 dnode_t
*root
= dict_root(dict
);
500 dnode_t
*nil
= dict_nil(dict
);
501 dnode_t
*tentative
= 0;
503 while (root
!= nil
) {
504 int result
= dict
->compare(key
, root
->key
);
508 } else if (result
> 0) {
525 * Insert a node into the dictionary. The node should have been
526 * initialized with a data field. All other fields are ignored.
527 * The behavior is undefined if the user attempts to insert into
528 * a dictionary that is already full (for which the dict_isfull()
529 * function returns true).
532 void dict_insert(dict_t
*dict
, dnode_t
*node
, const void *key
)
534 dnode_t
*where
= dict_root(dict
), *nil
= dict_nil(dict
);
535 dnode_t
*parent
= nil
, *uncle
, *grandpa
;
540 assert (!dict_isfull(dict
));
541 assert (!dict_contains(dict
, node
));
542 assert (!dnode_is_in_a_dict(node
));
544 /* basic binary tree insert */
546 while (where
!= nil
) {
548 result
= dict
->compare(key
, where
->key
);
549 /* trap attempts at duplicate key insertion unless it's explicitly allowed */
550 assert (dict
->dupes
|| result
!= 0);
554 where
= where
->right
;
557 assert (where
== nil
);
562 parent
->right
= node
;
564 node
->parent
= parent
;
570 /* red black adjustments */
572 node
->color
= dnode_red
;
574 while (parent
->color
== dnode_red
) {
575 grandpa
= parent
->parent
;
576 if (parent
== grandpa
->left
) {
577 uncle
= grandpa
->right
;
578 if (uncle
->color
== dnode_red
) { /* red parent, red uncle */
579 parent
->color
= dnode_black
;
580 uncle
->color
= dnode_black
;
581 grandpa
->color
= dnode_red
;
583 parent
= grandpa
->parent
;
584 } else { /* red parent, black uncle */
585 if (node
== parent
->right
) {
588 assert (grandpa
== parent
->parent
);
589 /* rotation between parent and child preserves grandpa */
591 parent
->color
= dnode_black
;
592 grandpa
->color
= dnode_red
;
593 rotate_right(grandpa
);
596 } else { /* symmetric cases: parent == parent->parent->right */
597 uncle
= grandpa
->left
;
598 if (uncle
->color
== dnode_red
) {
599 parent
->color
= dnode_black
;
600 uncle
->color
= dnode_black
;
601 grandpa
->color
= dnode_red
;
603 parent
= grandpa
->parent
;
605 if (node
== parent
->left
) {
606 rotate_right(parent
);
608 assert (grandpa
== parent
->parent
);
610 parent
->color
= dnode_black
;
611 grandpa
->color
= dnode_red
;
612 rotate_left(grandpa
);
618 dict_root(dict
)->color
= dnode_black
;
620 assert (dict_verify(dict
));
624 * Delete the given node from the dictionary. If the given node does not belong
625 * to the given dictionary, undefined behavior results. A pointer to the
626 * deleted node is returned.
629 dnode_t
*dict_delete(dict_t
*dict
, dnode_t
*delete)
631 dnode_t
*nil
= dict_nil(dict
), *child
, *delparent
= delete->parent
;
635 assert (!dict_isempty(dict
));
636 assert (dict_contains(dict
, delete));
639 * If the node being deleted has two children, then we replace it with its
640 * successor (i.e. the leftmost node in the right subtree.) By doing this,
641 * we avoid the traditional algorithm under which the successor's key and
642 * value *only* move to the deleted node and the successor is spliced out
643 * from the tree. We cannot use this approach because the user may hold
644 * pointers to the successor, or nodes may be inextricably tied to some
645 * other structures by way of embedding, etc. So we must splice out the
646 * node we are given, not some other node, and must not move contents from
647 * one node to another behind the user's back.
650 if (delete->left
!= nil
&& delete->right
!= nil
) {
651 dnode_t
*next
= dict_next(dict
, delete);
652 dnode_t
*nextparent
= next
->parent
;
653 dnode_color_t nextcolor
= next
->color
;
655 assert (next
!= nil
);
656 assert (next
->parent
!= nil
);
657 assert (next
->left
== nil
);
660 * First, splice out the successor from the tree completely, by
661 * moving up its right child into its place.
665 child
->parent
= nextparent
;
667 if (nextparent
->left
== next
) {
668 nextparent
->left
= child
;
670 assert (nextparent
->right
== next
);
671 nextparent
->right
= child
;
675 * Now that the successor has been extricated from the tree, install it
676 * in place of the node that we want deleted.
679 next
->parent
= delparent
;
680 next
->left
= delete->left
;
681 next
->right
= delete->right
;
682 next
->left
->parent
= next
;
683 next
->right
->parent
= next
;
684 next
->color
= delete->color
;
685 delete->color
= nextcolor
;
687 if (delparent
->left
== delete) {
688 delparent
->left
= next
;
690 assert (delparent
->right
== delete);
691 delparent
->right
= next
;
695 assert (delete != nil
);
696 assert (delete->left
== nil
|| delete->right
== nil
);
698 child
= (delete->left
!= nil
) ? delete->left
: delete->right
;
700 child
->parent
= delparent
= delete->parent
;
702 if (delete == delparent
->left
) {
703 delparent
->left
= child
;
705 assert (delete == delparent
->right
);
706 delparent
->right
= child
;
710 delete->parent
= NULL
;
711 delete->right
= NULL
;
716 assert (verify_bintree(dict
));
718 /* red-black adjustments */
720 if (delete->color
== dnode_black
) {
721 dnode_t
*parent
, *sister
;
723 dict_root(dict
)->color
= dnode_red
;
725 while (child
->color
== dnode_black
) {
726 parent
= child
->parent
;
727 if (child
== parent
->left
) {
728 sister
= parent
->right
;
729 assert (sister
!= nil
);
730 if (sister
->color
== dnode_red
) {
731 sister
->color
= dnode_black
;
732 parent
->color
= dnode_red
;
734 sister
= parent
->right
;
735 assert (sister
!= nil
);
737 if (sister
->left
->color
== dnode_black
738 && sister
->right
->color
== dnode_black
) {
739 sister
->color
= dnode_red
;
742 if (sister
->right
->color
== dnode_black
) {
743 assert (sister
->left
->color
== dnode_red
);
744 sister
->left
->color
= dnode_black
;
745 sister
->color
= dnode_red
;
746 rotate_right(sister
);
747 sister
= parent
->right
;
748 assert (sister
!= nil
);
750 sister
->color
= parent
->color
;
751 sister
->right
->color
= dnode_black
;
752 parent
->color
= dnode_black
;
756 } else { /* symmetric case: child == child->parent->right */
757 assert (child
== parent
->right
);
758 sister
= parent
->left
;
759 assert (sister
!= nil
);
760 if (sister
->color
== dnode_red
) {
761 sister
->color
= dnode_black
;
762 parent
->color
= dnode_red
;
763 rotate_right(parent
);
764 sister
= parent
->left
;
765 assert (sister
!= nil
);
767 if (sister
->right
->color
== dnode_black
768 && sister
->left
->color
== dnode_black
) {
769 sister
->color
= dnode_red
;
772 if (sister
->left
->color
== dnode_black
) {
773 assert (sister
->right
->color
== dnode_red
);
774 sister
->right
->color
= dnode_black
;
775 sister
->color
= dnode_red
;
777 sister
= parent
->left
;
778 assert (sister
!= nil
);
780 sister
->color
= parent
->color
;
781 sister
->left
->color
= dnode_black
;
782 parent
->color
= dnode_black
;
783 rotate_right(parent
);
789 child
->color
= dnode_black
;
790 dict_root(dict
)->color
= dnode_black
;
793 assert (dict_verify(dict
));
799 * Allocate a node using the dictionary's allocator routine, give it
803 int dict_alloc_insert(dict_t
*dict
, const void *key
, void *data
)
805 dnode_t
*node
= dict
->allocnode (dict
->context
);
808 dnode_init(node
, data
);
809 dict_insert(dict
, node
, key
);
815 void dict_delete_free(dict_t
*dict
, dnode_t
*node
)
817 dict_delete(dict
, node
);
818 dict
->freenode(node
, dict
->context
);
822 * Return the node with the lowest (leftmost) key. If the dictionary is empty
823 * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
826 dnode_t
*dict_first(dict_t
*dict
)
828 dnode_t
*nil
= dict_nil(dict
), *root
= dict_root(dict
), *left
;
831 while ((left
= root
->left
) != nil
)
834 return (root
== nil
) ? NULL
: root
;
838 * Return the node with the highest (rightmost) key. If the dictionary is empty
839 * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
842 dnode_t
*dict_last(dict_t
*dict
)
844 dnode_t
*nil
= dict_nil(dict
), *root
= dict_root(dict
), *right
;
847 while ((right
= root
->right
) != nil
)
850 return (root
== nil
) ? NULL
: root
;
854 * Return the given node's successor node---the node which has the
855 * next key in the the left to right ordering. If the node has
856 * no successor, a null pointer is returned rather than a pointer to
860 dnode_t
*dict_next(dict_t
*dict
, dnode_t
*curr
)
862 dnode_t
*nil
= dict_nil(dict
), *parent
, *left
;
864 if (curr
->right
!= nil
) {
866 while ((left
= curr
->left
) != nil
)
871 parent
= curr
->parent
;
873 while (parent
!= nil
&& curr
== parent
->right
) {
875 parent
= curr
->parent
;
878 return (parent
== nil
) ? NULL
: parent
;
882 * Return the given node's predecessor, in the key order.
883 * The nil sentinel node is returned if there is no predecessor.
886 dnode_t
*dict_prev(dict_t
*dict
, dnode_t
*curr
)
888 dnode_t
*nil
= dict_nil(dict
), *parent
, *right
;
890 if (curr
->left
!= nil
) {
892 while ((right
= curr
->right
) != nil
)
897 parent
= curr
->parent
;
899 while (parent
!= nil
&& curr
== parent
->left
) {
901 parent
= curr
->parent
;
904 return (parent
== nil
) ? NULL
: parent
;
907 void dict_allow_dupes(dict_t
*dict
)
919 dictcount_t
dict_count(dict_t
*dict
)
921 return dict
->nodecount
;
924 int dict_isempty(dict_t
*dict
)
926 return dict
->nodecount
== 0;
929 int dict_isfull(dict_t
*dict
)
931 return dict
->nodecount
== dict
->maxcount
;
934 int dict_contains(dict_t
*dict
, dnode_t
*node
)
936 return verify_dict_has_node(dict_nil(dict
), dict_root(dict
), node
);
939 static dnode_t
*dnode_alloc(void *context
)
941 return XCALLOC(MTYPE_ISIS_DICT_NODE
, sizeof(dnode_t
));
944 static void dnode_free(dnode_t
*node
, void *context
)
946 XFREE(MTYPE_ISIS_DICT_NODE
, node
);
949 dnode_t
*dnode_create(void *data
)
951 dnode_t
*new = XCALLOC(MTYPE_ISIS_DICT_NODE
, sizeof(dnode_t
));
961 dnode_t
*dnode_init(dnode_t
*dnode
, void *data
)
964 dnode
->parent
= NULL
;
970 void dnode_destroy(dnode_t
*dnode
)
972 assert (!dnode_is_in_a_dict(dnode
));
973 XFREE(MTYPE_ISIS_DICT_NODE
, dnode
);
976 void *dnode_get(dnode_t
*dnode
)
981 const void *dnode_getkey(dnode_t
*dnode
)
986 void dnode_put(dnode_t
*dnode
, void *data
)
991 int dnode_is_in_a_dict(dnode_t
*dnode
)
993 return (dnode
->parent
&& dnode
->left
&& dnode
->right
);
996 void dict_process(dict_t
*dict
, void *context
, dnode_process_t function
)
998 dnode_t
*node
= dict_first(dict
), *next
;
1000 while (node
!= NULL
) {
1001 /* check for callback function deleting */
1002 /* the next node from under us */
1003 assert (dict_contains(dict
, node
));
1004 next
= dict_next(dict
, node
);
1005 function(dict
, node
, context
);
1010 static void load_begin_internal(dict_load_t
*load
, dict_t
*dict
)
1012 load
->dictptr
= dict
;
1013 load
->nilnode
.left
= &load
->nilnode
;
1014 load
->nilnode
.right
= &load
->nilnode
;
1017 void dict_load_begin(dict_load_t
*load
, dict_t
*dict
)
1019 assert (dict_isempty(dict
));
1020 load_begin_internal(load
, dict
);
1023 void dict_load_next(dict_load_t
*load
, dnode_t
*newnode
, const void *key
)
1025 dict_t
*dict
= load
->dictptr
;
1026 dnode_t
*nil
= &load
->nilnode
;
1028 assert (!dnode_is_in_a_dict(newnode
));
1029 assert (dict
->nodecount
< dict
->maxcount
);
1032 if (dict
->nodecount
> 0) {
1034 assert (dict
->compare(nil
->left
->key
, key
) <= 0);
1036 assert (dict
->compare(nil
->left
->key
, key
) < 0);
1041 nil
->right
->left
= newnode
;
1042 nil
->right
= newnode
;
1043 newnode
->left
= nil
;
1047 void dict_load_end(dict_load_t
*load
)
1049 dict_t
*dict
= load
->dictptr
;
1050 dnode_t
*tree
[DICT_DEPTH_MAX
] = { 0 };
1051 dnode_t
*curr
, *dictnil
= dict_nil(dict
), *loadnil
= &load
->nilnode
, *next
;
1052 dnode_t
*complete
= 0;
1053 dictcount_t fullcount
= DICTCOUNT_T_MAX
, nodecount
= dict
->nodecount
;
1054 dictcount_t botrowcount
;
1055 unsigned baselevel
= 0, level
= 0, i
;
1057 assert (dnode_red
== 0 && dnode_black
== 1);
1059 while (fullcount
>= nodecount
&& fullcount
)
1062 botrowcount
= nodecount
- fullcount
;
1064 for (curr
= loadnil
->left
; curr
!= loadnil
; curr
= next
) {
1067 if (complete
== NULL
&& botrowcount
-- == 0) {
1068 assert (baselevel
== 0);
1069 assert (level
== 0);
1070 baselevel
= level
= 1;
1073 if (complete
!= 0) {
1075 complete
->right
= dictnil
;
1076 while (tree
[level
] != 0) {
1077 tree
[level
]->right
= complete
;
1078 complete
->parent
= tree
[level
];
1079 complete
= tree
[level
];
1085 if (complete
== NULL
) {
1086 curr
->left
= dictnil
;
1087 curr
->right
= dictnil
;
1088 curr
->color
= level
% 2;
1091 assert (level
== baselevel
);
1092 while (tree
[level
] != 0) {
1093 tree
[level
]->right
= complete
;
1094 complete
->parent
= tree
[level
];
1095 complete
= tree
[level
];
1099 curr
->left
= complete
;
1100 curr
->color
= (level
+ 1) % 2;
1101 complete
->parent
= curr
;
1108 if (complete
== NULL
)
1111 for (i
= 0; i
< DICT_DEPTH_MAX
; i
++) {
1113 tree
[i
]->right
= complete
;
1114 complete
->parent
= tree
[i
];
1119 dictnil
->color
= dnode_black
;
1120 dictnil
->right
= dictnil
;
1121 complete
->parent
= dictnil
;
1122 complete
->color
= dnode_black
;
1123 dict_root(dict
) = complete
;
1125 assert (dict_verify(dict
));
1128 void dict_merge(dict_t
*dest
, dict_t
*source
)
1131 dnode_t
*leftnode
= dict_first(dest
), *rightnode
= dict_first(source
);
1133 assert (dict_similar(dest
, source
));
1138 dest
->nodecount
= 0;
1139 load_begin_internal(&load
, dest
);
1142 if (leftnode
!= NULL
&& rightnode
!= NULL
) {
1143 if (dest
->compare(leftnode
->key
, rightnode
->key
) < 0)
1147 } else if (leftnode
!= NULL
) {
1149 } else if (rightnode
!= NULL
) {
1152 assert (leftnode
== NULL
&& rightnode
== NULL
);
1158 dnode_t
*next
= dict_next(dest
, leftnode
);
1160 leftnode
->left
= NULL
; /* suppress assertion in dict_load_next */
1162 dict_load_next(&load
, leftnode
, leftnode
->key
);
1169 dnode_t
*next
= dict_next(source
, rightnode
);
1171 rightnode
->left
= NULL
;
1173 dict_load_next(&load
, rightnode
, rightnode
->key
);
1180 dict_load_end(&load
);
1183 #ifdef KAZLIB_TEST_MAIN
1190 typedef char input_t
[256];
1192 static int tokenize(char *string
, ...)
1198 va_start(arglist
, string
);
1199 tokptr
= va_arg(arglist
, char **);
1201 while (*string
&& isspace((unsigned char) *string
))
1206 while (*string
&& !isspace((unsigned char) *string
))
1208 tokptr
= va_arg(arglist
, char **);
1219 static int comparef(const void *key1
, const void *key2
)
1221 return strcmp(key1
, key2
);
1224 static char *dupstring(char *str
)
1226 int sz
= strlen(str
) + 1;
1227 char *new = XCALLOC(MTYPE_ISIS_TMP
, sz
);
1229 memcpy(new, str
, sz
);
1233 static dnode_t
*new_node(void *c
)
1235 static dnode_t few
[5];
1239 return few
+ count
++;
1244 static void del_node(dnode_t
*n
, void *c
)
1248 static int prompt
= 0;
1250 static void construct(dict_t
*d
)
1256 char *tok1
, *tok2
, *val
;
1259 "p turn prompt on\n"
1260 "q finish construction\n"
1261 "a <key> <val> add new entry\n";
1263 if (!dict_isempty(d
))
1264 puts("warning: dictionary not empty!");
1266 dict_load_begin(&dl
, d
);
1273 if (!fgets(in
, sizeof(input_t
), stdin
))
1287 if (tokenize(in
+1, &tok1
, &tok2
, (char **) 0) != 2) {
1291 key
= dupstring(tok1
);
1292 val
= dupstring(tok2
);
1293 dn
= dnode_create(val
);
1295 if (!key
|| !val
|| !dn
) {
1296 puts("out of memory");
1303 dict_load_next(&dl
, dn
, key
);
1319 dict_t
*d
= &darray
[0];
1322 char *tok1
, *tok2
, *val
;
1326 "a <key> <val> add value to dictionary\n"
1327 "d <key> delete value from dictionary\n"
1328 "l <key> lookup value in dictionary\n"
1329 "( <key> lookup lower bound\n"
1330 ") <key> lookup upper bound\n"
1331 "# <num> switch to alternate dictionary (0-9)\n"
1332 "j <num> <num> merge two dictionaries\n"
1333 "f free the whole dictionary\n"
1334 "k allow duplicate keys\n"
1335 "c show number of entries\n"
1336 "t dump whole dictionary in sort order\n"
1337 "m make dictionary out of sorted items\n"
1338 "p turn prompt on\n"
1339 "s switch to non-functioning allocator\n"
1342 for (i
= 0; i
< 10; i
++)
1343 dict_init(&darray
[i
], DICTCOUNT_T_MAX
, comparef
);
1350 if (!fgets(in
, sizeof(input_t
), stdin
))
1358 if (tokenize(in
+1, &tok1
, &tok2
, (char **) 0) != 2) {
1362 key
= dupstring(tok1
);
1363 val
= dupstring(tok2
);
1366 puts("out of memory");
1371 if (!dict_alloc_insert(d
, key
, val
)) {
1372 puts("dict_alloc_insert failed");
1379 if (tokenize(in
+1, &tok1
, (char **) 0) != 1) {
1383 dn
= dict_lookup(d
, tok1
);
1385 puts("dict_lookup failed");
1388 val
= dnode_get(dn
);
1389 key
= dnode_getkey(dn
);
1390 dict_delete_free(d
, dn
);
1401 if (tokenize(in
+1, &tok1
, (char **) 0) != 1) {
1408 dn
= dict_lookup(d
, tok1
);
1411 dn
= dict_lower_bound(d
, tok1
);
1414 dn
= dict_upper_bound(d
, tok1
);
1418 puts("lookup failed");
1421 val
= dnode_get(dn
);
1428 dict_allow_dupes(d
);
1431 printf("%lu\n", (unsigned long) dict_count(d
));
1434 for (dn
= dict_first(d
); dn
; dn
= dict_next(d
, dn
)) {
1435 printf("%s\t%s\n", (char *) dnode_getkey(dn
),
1436 (char *) dnode_get(dn
));
1448 dict_set_allocator(d
, new_node
, del_node
, NULL
);
1451 if (tokenize(in
+1, &tok1
, (char **) 0) != 1) {
1455 int dictnum
= atoi(tok1
);
1456 if (dictnum
< 0 || dictnum
> 9) {
1457 puts("invalid number");
1460 d
= &darray
[dictnum
];
1464 if (tokenize(in
+1, &tok1
, &tok2
, (char **) 0) != 2) {
1468 int dict1
= atoi(tok1
), dict2
= atoi(tok2
);
1469 if (dict1
< 0 || dict1
> 9 || dict2
< 0 || dict2
> 9) {
1470 puts("invalid number");
1473 dict_merge(&darray
[dict1
], &darray
[dict2
]);