]>
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);
653 dnode_t
*nextparent
= next
->parent
;
654 dnode_color_t nextcolor
= next
->color
;
656 assert (next
!= nil
);
657 assert (next
->parent
!= nil
);
658 assert (next
->left
== nil
);
661 * First, splice out the successor from the tree completely, by
662 * moving up its right child into its place.
666 child
->parent
= nextparent
;
668 if (nextparent
->left
== next
) {
669 nextparent
->left
= child
;
671 assert (nextparent
->right
== next
);
672 nextparent
->right
= child
;
676 * Now that the successor has been extricated from the tree, install it
677 * in place of the node that we want deleted.
680 next
->parent
= delparent
;
681 next
->left
= delete->left
;
682 next
->right
= delete->right
;
683 next
->left
->parent
= next
;
684 next
->right
->parent
= next
;
685 next
->color
= delete->color
;
686 delete->color
= nextcolor
;
688 if (delparent
->left
== delete) {
689 delparent
->left
= next
;
691 assert (delparent
->right
== delete);
692 delparent
->right
= next
;
696 assert (delete != nil
);
697 assert (delete->left
== nil
|| delete->right
== nil
);
699 child
= (delete->left
!= nil
) ? delete->left
: delete->right
;
701 child
->parent
= delparent
= delete->parent
;
703 if (delete == delparent
->left
) {
704 delparent
->left
= child
;
706 assert (delete == delparent
->right
);
707 delparent
->right
= child
;
711 delete->parent
= NULL
;
712 delete->right
= NULL
;
717 assert (verify_bintree(dict
));
719 /* red-black adjustments */
721 if (delete->color
== dnode_black
) {
722 dnode_t
*parent
, *sister
;
724 dict_root(dict
)->color
= dnode_red
;
726 while (child
->color
== dnode_black
) {
727 parent
= child
->parent
;
728 if (child
== parent
->left
) {
729 sister
= parent
->right
;
730 assert (sister
!= nil
);
731 if (sister
->color
== dnode_red
) {
732 sister
->color
= dnode_black
;
733 parent
->color
= dnode_red
;
735 sister
= parent
->right
;
736 assert (sister
!= nil
);
738 if (sister
->left
->color
== dnode_black
739 && sister
->right
->color
== dnode_black
) {
740 sister
->color
= dnode_red
;
743 if (sister
->right
->color
== dnode_black
) {
744 assert (sister
->left
->color
== dnode_red
);
745 sister
->left
->color
= dnode_black
;
746 sister
->color
= dnode_red
;
747 rotate_right(sister
);
748 sister
= parent
->right
;
749 assert (sister
!= nil
);
751 sister
->color
= parent
->color
;
752 sister
->right
->color
= dnode_black
;
753 parent
->color
= dnode_black
;
757 } else { /* symmetric case: child == child->parent->right */
758 assert (child
== parent
->right
);
759 sister
= parent
->left
;
760 assert (sister
!= nil
);
761 if (sister
->color
== dnode_red
) {
762 sister
->color
= dnode_black
;
763 parent
->color
= dnode_red
;
764 rotate_right(parent
);
765 sister
= parent
->left
;
766 assert (sister
!= nil
);
768 if (sister
->right
->color
== dnode_black
769 && sister
->left
->color
== dnode_black
) {
770 sister
->color
= dnode_red
;
773 if (sister
->left
->color
== dnode_black
) {
774 assert (sister
->right
->color
== dnode_red
);
775 sister
->right
->color
= dnode_black
;
776 sister
->color
= dnode_red
;
778 sister
= parent
->left
;
779 assert (sister
!= nil
);
781 sister
->color
= parent
->color
;
782 sister
->left
->color
= dnode_black
;
783 parent
->color
= dnode_black
;
784 rotate_right(parent
);
790 child
->color
= dnode_black
;
791 dict_root(dict
)->color
= dnode_black
;
794 assert (dict_verify(dict
));
800 * Allocate a node using the dictionary's allocator routine, give it
804 int dict_alloc_insert(dict_t
*dict
, const void *key
, void *data
)
806 dnode_t
*node
= dict
->allocnode (dict
->context
);
809 dnode_init(node
, data
);
810 dict_insert(dict
, node
, key
);
816 void dict_delete_free(dict_t
*dict
, dnode_t
*node
)
818 dict_delete(dict
, node
);
819 dict
->freenode(node
, dict
->context
);
823 * Return the node with the lowest (leftmost) key. If the dictionary is empty
824 * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
827 dnode_t
*dict_first(dict_t
*dict
)
829 dnode_t
*nil
= dict_nil(dict
), *root
= dict_root(dict
), *left
;
832 while ((left
= root
->left
) != nil
)
835 return (root
== nil
) ? NULL
: root
;
839 * Return the node with the highest (rightmost) key. If the dictionary is empty
840 * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
843 dnode_t
*dict_last(dict_t
*dict
)
845 dnode_t
*nil
= dict_nil(dict
), *root
= dict_root(dict
), *right
;
848 while ((right
= root
->right
) != nil
)
851 return (root
== nil
) ? NULL
: root
;
855 * Return the given node's successor node---the node which has the
856 * next key in the the left to right ordering. If the node has
857 * no successor, a null pointer is returned rather than a pointer to
861 dnode_t
*dict_next(dict_t
*dict
, dnode_t
*curr
)
863 dnode_t
*nil
= dict_nil(dict
), *parent
, *left
;
865 if (curr
->right
!= nil
) {
867 while ((left
= curr
->left
) != nil
)
872 parent
= curr
->parent
;
874 while (parent
!= nil
&& curr
== parent
->right
) {
876 parent
= curr
->parent
;
879 return (parent
== nil
) ? NULL
: parent
;
883 * Return the given node's predecessor, in the key order.
884 * The nil sentinel node is returned if there is no predecessor.
887 dnode_t
*dict_prev(dict_t
*dict
, dnode_t
*curr
)
889 dnode_t
*nil
= dict_nil(dict
), *parent
, *right
;
891 if (curr
->left
!= nil
) {
893 while ((right
= curr
->right
) != nil
)
898 parent
= curr
->parent
;
900 while (parent
!= nil
&& curr
== parent
->left
) {
902 parent
= curr
->parent
;
905 return (parent
== nil
) ? NULL
: parent
;
908 void dict_allow_dupes(dict_t
*dict
)
920 dictcount_t
dict_count(dict_t
*dict
)
922 return dict
->nodecount
;
925 int dict_isempty(dict_t
*dict
)
927 return dict
->nodecount
== 0;
930 int dict_isfull(dict_t
*dict
)
932 return dict
->nodecount
== dict
->maxcount
;
935 int dict_contains(dict_t
*dict
, dnode_t
*node
)
937 return verify_dict_has_node(dict_nil(dict
), dict_root(dict
), node
);
940 static dnode_t
*dnode_alloc(void *context
)
942 return XCALLOC(MTYPE_ISIS_DICT_NODE
, sizeof(dnode_t
));
945 static void dnode_free(dnode_t
*node
, void *context
)
947 XFREE(MTYPE_ISIS_DICT_NODE
, node
);
950 dnode_t
*dnode_create(void *data
)
952 dnode_t
*new = XCALLOC(MTYPE_ISIS_DICT_NODE
, sizeof(dnode_t
));
962 dnode_t
*dnode_init(dnode_t
*dnode
, void *data
)
965 dnode
->parent
= NULL
;
971 void dnode_destroy(dnode_t
*dnode
)
973 assert (!dnode_is_in_a_dict(dnode
));
974 XFREE(MTYPE_ISIS_DICT_NODE
, dnode
);
977 void *dnode_get(dnode_t
*dnode
)
982 const void *dnode_getkey(dnode_t
*dnode
)
987 void dnode_put(dnode_t
*dnode
, void *data
)
992 int dnode_is_in_a_dict(dnode_t
*dnode
)
994 return (dnode
->parent
&& dnode
->left
&& dnode
->right
);
997 void dict_process(dict_t
*dict
, void *context
, dnode_process_t function
)
999 dnode_t
*node
= dict_first(dict
), *next
;
1001 while (node
!= NULL
) {
1002 /* check for callback function deleting */
1003 /* the next node from under us */
1004 assert (dict_contains(dict
, node
));
1005 next
= dict_next(dict
, node
);
1006 function(dict
, node
, context
);
1011 static void load_begin_internal(dict_load_t
*load
, dict_t
*dict
)
1013 load
->dictptr
= dict
;
1014 load
->nilnode
.left
= &load
->nilnode
;
1015 load
->nilnode
.right
= &load
->nilnode
;
1018 void dict_load_begin(dict_load_t
*load
, dict_t
*dict
)
1020 assert (dict_isempty(dict
));
1021 load_begin_internal(load
, dict
);
1024 void dict_load_next(dict_load_t
*load
, dnode_t
*newnode
, const void *key
)
1026 dict_t
*dict
= load
->dictptr
;
1027 dnode_t
*nil
= &load
->nilnode
;
1029 assert (!dnode_is_in_a_dict(newnode
));
1030 assert (dict
->nodecount
< dict
->maxcount
);
1033 if (dict
->nodecount
> 0) {
1035 assert (dict
->compare(nil
->left
->key
, key
) <= 0);
1037 assert (dict
->compare(nil
->left
->key
, key
) < 0);
1042 nil
->right
->left
= newnode
;
1043 nil
->right
= newnode
;
1044 newnode
->left
= nil
;
1048 void dict_load_end(dict_load_t
*load
)
1050 dict_t
*dict
= load
->dictptr
;
1051 dnode_t
*tree
[DICT_DEPTH_MAX
] = { 0 };
1052 dnode_t
*curr
, *dictnil
= dict_nil(dict
), *loadnil
= &load
->nilnode
, *next
;
1053 dnode_t
*complete
= 0;
1054 dictcount_t fullcount
= DICTCOUNT_T_MAX
, nodecount
= dict
->nodecount
;
1055 dictcount_t botrowcount
;
1056 unsigned baselevel
= 0, level
= 0, i
;
1058 assert (dnode_red
== 0 && dnode_black
== 1);
1060 while (fullcount
>= nodecount
&& fullcount
)
1063 botrowcount
= nodecount
- fullcount
;
1065 for (curr
= loadnil
->left
; curr
!= loadnil
; curr
= next
) {
1068 if (complete
== NULL
&& botrowcount
-- == 0) {
1069 assert (baselevel
== 0);
1070 assert (level
== 0);
1071 baselevel
= level
= 1;
1074 if (complete
!= 0) {
1076 complete
->right
= dictnil
;
1077 while (tree
[level
] != 0) {
1078 tree
[level
]->right
= complete
;
1079 complete
->parent
= tree
[level
];
1080 complete
= tree
[level
];
1086 if (complete
== NULL
) {
1087 curr
->left
= dictnil
;
1088 curr
->right
= dictnil
;
1089 curr
->color
= level
% 2;
1092 assert (level
== baselevel
);
1093 while (tree
[level
] != 0) {
1094 tree
[level
]->right
= complete
;
1095 complete
->parent
= tree
[level
];
1096 complete
= tree
[level
];
1100 curr
->left
= complete
;
1101 curr
->color
= (level
+ 1) % 2;
1102 complete
->parent
= curr
;
1109 if (complete
== NULL
)
1112 for (i
= 0; i
< DICT_DEPTH_MAX
; i
++) {
1114 tree
[i
]->right
= complete
;
1115 complete
->parent
= tree
[i
];
1120 dictnil
->color
= dnode_black
;
1121 dictnil
->right
= dictnil
;
1122 complete
->parent
= dictnil
;
1123 complete
->color
= dnode_black
;
1124 dict_root(dict
) = complete
;
1126 assert (dict_verify(dict
));
1129 void dict_merge(dict_t
*dest
, dict_t
*source
)
1132 dnode_t
*leftnode
= dict_first(dest
), *rightnode
= dict_first(source
);
1134 assert (dict_similar(dest
, source
));
1139 dest
->nodecount
= 0;
1140 load_begin_internal(&load
, dest
);
1143 if (leftnode
!= NULL
&& rightnode
!= NULL
) {
1144 if (dest
->compare(leftnode
->key
, rightnode
->key
) < 0)
1148 } else if (leftnode
!= NULL
) {
1150 } else if (rightnode
!= NULL
) {
1153 assert (leftnode
== NULL
&& rightnode
== NULL
);
1159 dnode_t
*next
= dict_next(dest
, leftnode
);
1161 leftnode
->left
= NULL
; /* suppress assertion in dict_load_next */
1163 dict_load_next(&load
, leftnode
, leftnode
->key
);
1170 dnode_t
*next
= dict_next(source
, rightnode
);
1172 rightnode
->left
= NULL
;
1174 dict_load_next(&load
, rightnode
, rightnode
->key
);
1181 dict_load_end(&load
);
1184 #ifdef KAZLIB_TEST_MAIN
1191 typedef char input_t
[256];
1193 static int tokenize(char *string
, ...)
1199 va_start(arglist
, string
);
1200 tokptr
= va_arg(arglist
, char **);
1202 while (*string
&& isspace((unsigned char) *string
))
1207 while (*string
&& !isspace((unsigned char) *string
))
1209 tokptr
= va_arg(arglist
, char **);
1220 static int comparef(const void *key1
, const void *key2
)
1222 return strcmp(key1
, key2
);
1225 static char *dupstring(char *str
)
1227 int sz
= strlen(str
) + 1;
1228 char *new = XCALLOC(MTYPE_ISIS_TMP
, sz
);
1230 memcpy(new, str
, sz
);
1234 static dnode_t
*new_node(void *c
)
1236 static dnode_t few
[5];
1240 return few
+ count
++;
1245 static void del_node(dnode_t
*n
, void *c
)
1249 static int prompt
= 0;
1251 static void construct(dict_t
*d
)
1257 char *tok1
, *tok2
, *val
;
1260 "p turn prompt on\n"
1261 "q finish construction\n"
1262 "a <key> <val> add new entry\n";
1264 if (!dict_isempty(d
))
1265 puts("warning: dictionary not empty!");
1267 dict_load_begin(&dl
, d
);
1274 if (!fgets(in
, sizeof(input_t
), stdin
))
1288 if (tokenize(in
+1, &tok1
, &tok2
, (char **) 0) != 2) {
1292 key
= dupstring(tok1
);
1293 val
= dupstring(tok2
);
1294 dn
= dnode_create(val
);
1296 if (!key
|| !val
|| !dn
) {
1297 puts("out of memory");
1304 dict_load_next(&dl
, dn
, key
);
1320 dict_t
*d
= &darray
[0];
1323 char *tok1
, *tok2
, *val
;
1327 "a <key> <val> add value to dictionary\n"
1328 "d <key> delete value from dictionary\n"
1329 "l <key> lookup value in dictionary\n"
1330 "( <key> lookup lower bound\n"
1331 ") <key> lookup upper bound\n"
1332 "# <num> switch to alternate dictionary (0-9)\n"
1333 "j <num> <num> merge two dictionaries\n"
1334 "f free the whole dictionary\n"
1335 "k allow duplicate keys\n"
1336 "c show number of entries\n"
1337 "t dump whole dictionary in sort order\n"
1338 "m make dictionary out of sorted items\n"
1339 "p turn prompt on\n"
1340 "s switch to non-functioning allocator\n"
1343 for (i
= 0; i
< 10; i
++)
1344 dict_init(&darray
[i
], DICTCOUNT_T_MAX
, comparef
);
1351 if (!fgets(in
, sizeof(input_t
), stdin
))
1359 if (tokenize(in
+1, &tok1
, &tok2
, (char **) 0) != 2) {
1363 key
= dupstring(tok1
);
1364 val
= dupstring(tok2
);
1367 puts("out of memory");
1372 if (!dict_alloc_insert(d
, key
, val
)) {
1373 puts("dict_alloc_insert failed");
1380 if (tokenize(in
+1, &tok1
, (char **) 0) != 1) {
1384 dn
= dict_lookup(d
, tok1
);
1386 puts("dict_lookup failed");
1389 val
= dnode_get(dn
);
1390 key
= dnode_getkey(dn
);
1391 dict_delete_free(d
, dn
);
1402 if (tokenize(in
+1, &tok1
, (char **) 0) != 1) {
1409 dn
= dict_lookup(d
, tok1
);
1412 dn
= dict_lower_bound(d
, tok1
);
1415 dn
= dict_upper_bound(d
, tok1
);
1419 puts("lookup failed");
1422 val
= dnode_get(dn
);
1429 dict_allow_dupes(d
);
1432 printf("%lu\n", (unsigned long) dict_count(d
));
1435 for (dn
= dict_first(d
); dn
; dn
= dict_next(d
, dn
)) {
1436 printf("%s\t%s\n", (char *) dnode_getkey(dn
),
1437 (char *) dnode_get(dn
));
1449 dict_set_allocator(d
, new_node
, del_node
, NULL
);
1452 if (tokenize(in
+1, &tok1
, (char **) 0) != 1) {
1456 int dictnum
= atoi(tok1
);
1457 if (dictnum
< 0 || dictnum
> 9) {
1458 puts("invalid number");
1461 d
= &darray
[dictnum
];
1465 if (tokenize(in
+1, &tok1
, &tok2
, (char **) 0) != 2) {
1469 int dict1
= atoi(tok1
), dict2
= atoi(tok2
);
1470 if (dict1
< 0 || dict1
> 9 || dict2
< 0 || dict2
> 9) {
1471 puts("invalid number");
1474 dict_merge(&darray
[dict1
], &darray
[dict2
]);