]>
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
, dnode_free_t fr
,
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
446 } else { /* could be dupes, find leftmost one */
451 && dict
->compare(key
, root
->key
))
453 } while (root
!= nil
);
463 * Look for the node corresponding to the lowest key that is equal to or
464 * greater than the given key. If there is no such node, return null.
467 dnode_t
*dict_lower_bound(dict_t
*dict
, const void *key
)
469 dnode_t
*root
= dict_root(dict
);
470 dnode_t
*nil
= dict_nil(dict
);
471 dnode_t
*tentative
= 0;
473 while (root
!= nil
) {
474 int result
= dict
->compare(key
, root
->key
);
478 } else if (result
< 0) {
495 * Look for the node corresponding to the greatest key that is equal to or
496 * lower than the given key. If there is no such node, return null.
499 dnode_t
*dict_upper_bound(dict_t
*dict
, const void *key
)
501 dnode_t
*root
= dict_root(dict
);
502 dnode_t
*nil
= dict_nil(dict
);
503 dnode_t
*tentative
= 0;
505 while (root
!= nil
) {
506 int result
= dict
->compare(key
, root
->key
);
510 } else if (result
> 0) {
527 * Insert a node into the dictionary. The node should have been
528 * initialized with a data field. All other fields are ignored.
529 * The behavior is undefined if the user attempts to insert into
530 * a dictionary that is already full (for which the dict_isfull()
531 * function returns true).
534 void dict_insert(dict_t
*dict
, dnode_t
*node
, const void *key
)
536 dnode_t
*where
= dict_root(dict
), *nil
= dict_nil(dict
);
537 dnode_t
*parent
= nil
, *uncle
, *grandpa
;
542 assert(!dict_isfull(dict
));
543 assert(!dict_contains(dict
, node
));
544 assert(!dnode_is_in_a_dict(node
));
546 /* basic binary tree insert */
548 while (where
!= nil
) {
550 result
= dict
->compare(key
, where
->key
);
551 /* trap attempts at duplicate key insertion unless it's
552 * explicitly allowed */
553 assert(dict
->dupes
|| result
!= 0);
557 where
= where
->right
;
560 assert(where
== nil
);
565 parent
->right
= node
;
567 node
->parent
= parent
;
573 /* red black adjustments */
575 node
->color
= dnode_red
;
577 while (parent
->color
== dnode_red
) {
578 grandpa
= parent
->parent
;
579 if (parent
== grandpa
->left
) {
580 uncle
= grandpa
->right
;
582 == dnode_red
) { /* red parent, red uncle */
583 parent
->color
= dnode_black
;
584 uncle
->color
= dnode_black
;
585 grandpa
->color
= dnode_red
;
587 parent
= grandpa
->parent
;
588 } else { /* red parent, black uncle */
589 if (node
== parent
->right
) {
592 assert(grandpa
== parent
->parent
);
593 /* rotation between parent and child
594 * preserves grandpa */
596 parent
->color
= dnode_black
;
597 grandpa
->color
= dnode_red
;
598 rotate_right(grandpa
);
601 } else { /* symmetric cases: parent == parent->parent->right */
602 uncle
= grandpa
->left
;
603 if (uncle
->color
== dnode_red
) {
604 parent
->color
= dnode_black
;
605 uncle
->color
= dnode_black
;
606 grandpa
->color
= dnode_red
;
608 parent
= grandpa
->parent
;
610 if (node
== parent
->left
) {
611 rotate_right(parent
);
613 assert(grandpa
== parent
->parent
);
615 parent
->color
= dnode_black
;
616 grandpa
->color
= dnode_red
;
617 rotate_left(grandpa
);
623 dict_root(dict
)->color
= dnode_black
;
625 assert(dict_verify(dict
));
629 * Delete the given node from the dictionary. If the given node does not belong
630 * to the given dictionary, undefined behavior results. A pointer to the
631 * deleted node is returned.
634 dnode_t
*dict_delete(dict_t
*dict
, dnode_t
*delete)
636 dnode_t
*nil
= dict_nil(dict
), *child
, *delparent
= delete->parent
;
640 assert(!dict_isempty(dict
));
641 assert(dict_contains(dict
, delete));
644 * If the node being deleted has two children, then we replace it with
646 * successor (i.e. the leftmost node in the right subtree.) By doing
648 * we avoid the traditional algorithm under which the successor's key
650 * value *only* move to the deleted node and the successor is spliced
652 * from the tree. We cannot use this approach because the user may hold
653 * pointers to the successor, or nodes may be inextricably tied to some
654 * other structures by way of embedding, etc. So we must splice out the
655 * node we are given, not some other node, and must not move contents
657 * one node to another behind the user's back.
660 if (delete->left
!= nil
&& delete->right
!= nil
) {
661 dnode_t
*next
= dict_next(dict
, delete);
663 dnode_t
*nextparent
= next
->parent
;
664 dnode_color_t nextcolor
= next
->color
;
667 assert(next
->parent
!= nil
);
668 assert(next
->left
== nil
);
671 * First, splice out the successor from the tree completely, by
672 * moving up its right child into its place.
676 child
->parent
= nextparent
;
678 if (nextparent
->left
== next
) {
679 nextparent
->left
= child
;
681 assert(nextparent
->right
== next
);
682 nextparent
->right
= child
;
686 * Now that the successor has been extricated from the tree,
688 * in place of the node that we want deleted.
691 next
->parent
= delparent
;
692 next
->left
= delete->left
;
693 next
->right
= delete->right
;
694 next
->left
->parent
= next
;
695 next
->right
->parent
= next
;
696 next
->color
= delete->color
;
697 delete->color
= nextcolor
;
699 if (delparent
->left
== delete) {
700 delparent
->left
= next
;
702 assert(delparent
->right
== delete);
703 delparent
->right
= next
;
707 assert(delete != nil
);
708 assert(delete->left
== nil
|| delete->right
== nil
);
710 child
= (delete->left
!= nil
) ? delete->left
: delete->right
;
712 child
->parent
= delparent
= delete->parent
;
714 if (delete == delparent
->left
) {
715 delparent
->left
= child
;
717 assert(delete == delparent
->right
);
718 delparent
->right
= child
;
722 delete->parent
= NULL
;
723 delete->right
= NULL
;
728 assert(verify_bintree(dict
));
730 /* red-black adjustments */
732 if (delete->color
== dnode_black
) {
733 dnode_t
*parent
, *sister
;
735 dict_root(dict
)->color
= dnode_red
;
737 while (child
->color
== dnode_black
) {
738 parent
= child
->parent
;
739 if (child
== parent
->left
) {
740 sister
= parent
->right
;
741 assert(sister
!= nil
);
742 if (sister
->color
== dnode_red
) {
743 sister
->color
= dnode_black
;
744 parent
->color
= dnode_red
;
746 sister
= parent
->right
;
747 assert(sister
!= nil
);
749 if (sister
->left
->color
== dnode_black
750 && sister
->right
->color
== dnode_black
) {
751 sister
->color
= dnode_red
;
754 if (sister
->right
->color
756 assert(sister
->left
->color
758 sister
->left
->color
=
760 sister
->color
= dnode_red
;
761 rotate_right(sister
);
762 sister
= parent
->right
;
763 assert(sister
!= nil
);
765 sister
->color
= parent
->color
;
766 sister
->right
->color
= dnode_black
;
767 parent
->color
= dnode_black
;
771 } else { /* symmetric case: child ==
772 child->parent->right */
773 assert(child
== parent
->right
);
774 sister
= parent
->left
;
775 assert(sister
!= nil
);
776 if (sister
->color
== dnode_red
) {
777 sister
->color
= dnode_black
;
778 parent
->color
= dnode_red
;
779 rotate_right(parent
);
780 sister
= parent
->left
;
781 assert(sister
!= nil
);
783 if (sister
->right
->color
== dnode_black
784 && sister
->left
->color
== dnode_black
) {
785 sister
->color
= dnode_red
;
788 if (sister
->left
->color
790 assert(sister
->right
->color
792 sister
->right
->color
=
794 sister
->color
= dnode_red
;
796 sister
= parent
->left
;
797 assert(sister
!= nil
);
799 sister
->color
= parent
->color
;
800 sister
->left
->color
= dnode_black
;
801 parent
->color
= dnode_black
;
802 rotate_right(parent
);
808 child
->color
= dnode_black
;
809 dict_root(dict
)->color
= dnode_black
;
812 assert(dict_verify(dict
));
818 * Allocate a node using the dictionary's allocator routine, give it
822 int dict_alloc_insert(dict_t
*dict
, const void *key
, void *data
)
824 dnode_t
*node
= dict
->allocnode(dict
->context
);
827 dnode_init(node
, data
);
828 dict_insert(dict
, node
, key
);
834 void dict_delete_free(dict_t
*dict
, dnode_t
*node
)
836 dict_delete(dict
, node
);
837 dict
->freenode(node
, dict
->context
);
841 * Return the node with the lowest (leftmost) key. If the dictionary is empty
842 * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
845 dnode_t
*dict_first(dict_t
*dict
)
847 dnode_t
*nil
= dict_nil(dict
), *root
= dict_root(dict
), *left
;
850 while ((left
= root
->left
) != nil
)
853 return (root
== nil
) ? NULL
: root
;
857 * Return the node with the highest (rightmost) key. If the dictionary is empty
858 * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
861 dnode_t
*dict_last(dict_t
*dict
)
863 dnode_t
*nil
= dict_nil(dict
), *root
= dict_root(dict
), *right
;
866 while ((right
= root
->right
) != nil
)
869 return (root
== nil
) ? NULL
: root
;
873 * Return the given node's successor node---the node which has the
874 * next key in the the left to right ordering. If the node has
875 * no successor, a null pointer is returned rather than a pointer to
879 dnode_t
*dict_next(dict_t
*dict
, dnode_t
*curr
)
881 dnode_t
*nil
= dict_nil(dict
), *parent
, *left
;
883 if (curr
->right
!= nil
) {
885 while ((left
= curr
->left
) != nil
)
890 parent
= curr
->parent
;
892 while (parent
!= nil
&& curr
== parent
->right
) {
894 parent
= curr
->parent
;
897 return (parent
== nil
) ? NULL
: parent
;
901 * Return the given node's predecessor, in the key order.
902 * The nil sentinel node is returned if there is no predecessor.
905 dnode_t
*dict_prev(dict_t
*dict
, dnode_t
*curr
)
907 dnode_t
*nil
= dict_nil(dict
), *parent
, *right
;
909 if (curr
->left
!= nil
) {
911 while ((right
= curr
->right
) != nil
)
916 parent
= curr
->parent
;
918 while (parent
!= nil
&& curr
== parent
->left
) {
920 parent
= curr
->parent
;
923 return (parent
== nil
) ? NULL
: parent
;
926 void dict_allow_dupes(dict_t
*dict
)
938 dictcount_t
dict_count(dict_t
*dict
)
940 return dict
->nodecount
;
943 int dict_isempty(dict_t
*dict
)
945 return dict
->nodecount
== 0;
948 int dict_isfull(dict_t
*dict
)
950 return dict
->nodecount
== dict
->maxcount
;
953 int dict_contains(dict_t
*dict
, dnode_t
*node
)
955 return verify_dict_has_node(dict_nil(dict
), dict_root(dict
), node
);
958 static dnode_t
*dnode_alloc(void *context
)
960 return XCALLOC(MTYPE_ISIS_DICT_NODE
, sizeof(dnode_t
));
963 static void dnode_free(dnode_t
*node
, void *context
)
965 XFREE(MTYPE_ISIS_DICT_NODE
, node
);
968 dnode_t
*dnode_create(void *data
)
970 dnode_t
*new = XCALLOC(MTYPE_ISIS_DICT_NODE
, sizeof(dnode_t
));
980 dnode_t
*dnode_init(dnode_t
*dnode
, void *data
)
983 dnode
->parent
= NULL
;
989 void dnode_destroy(dnode_t
*dnode
)
991 assert(!dnode_is_in_a_dict(dnode
));
992 XFREE(MTYPE_ISIS_DICT_NODE
, dnode
);
995 void *dnode_get(dnode_t
*dnode
)
1000 const void *dnode_getkey(dnode_t
*dnode
)
1005 void dnode_put(dnode_t
*dnode
, void *data
)
1010 int dnode_is_in_a_dict(dnode_t
*dnode
)
1012 return (dnode
->parent
&& dnode
->left
&& dnode
->right
);
1015 void dict_process(dict_t
*dict
, void *context
, dnode_process_t function
)
1017 dnode_t
*node
= dict_first(dict
), *next
;
1019 while (node
!= NULL
) {
1020 /* check for callback function deleting */
1021 /* the next node from under us */
1022 assert(dict_contains(dict
, node
));
1023 next
= dict_next(dict
, node
);
1024 function(dict
, node
, context
);
1029 static void load_begin_internal(dict_load_t
*load
, dict_t
*dict
)
1031 load
->dictptr
= dict
;
1032 load
->nilnode
.left
= &load
->nilnode
;
1033 load
->nilnode
.right
= &load
->nilnode
;
1036 void dict_load_begin(dict_load_t
*load
, dict_t
*dict
)
1038 assert(dict_isempty(dict
));
1039 load_begin_internal(load
, dict
);
1042 void dict_load_next(dict_load_t
*load
, dnode_t
*newnode
, const void *key
)
1044 dict_t
*dict
= load
->dictptr
;
1045 dnode_t
*nil
= &load
->nilnode
;
1047 assert(!dnode_is_in_a_dict(newnode
));
1048 assert(dict
->nodecount
< dict
->maxcount
);
1051 if (dict
->nodecount
> 0) {
1053 assert(dict
->compare(nil
->left
->key
, key
) <= 0);
1055 assert(dict
->compare(nil
->left
->key
, key
) < 0);
1060 nil
->right
->left
= newnode
;
1061 nil
->right
= newnode
;
1062 newnode
->left
= nil
;
1066 void dict_load_end(dict_load_t
*load
)
1068 dict_t
*dict
= load
->dictptr
;
1069 dnode_t
*tree
[DICT_DEPTH_MAX
] = {0};
1070 dnode_t
*curr
, *dictnil
= dict_nil(dict
), *loadnil
= &load
->nilnode
,
1072 dnode_t
*complete
= 0;
1073 dictcount_t fullcount
= DICTCOUNT_T_MAX
, nodecount
= dict
->nodecount
;
1074 dictcount_t botrowcount
;
1075 unsigned baselevel
= 0, level
= 0, i
;
1077 assert(dnode_red
== 0 && dnode_black
== 1);
1079 while (fullcount
>= nodecount
&& fullcount
)
1082 botrowcount
= nodecount
- fullcount
;
1084 for (curr
= loadnil
->left
; curr
!= loadnil
; curr
= next
) {
1087 if (complete
== NULL
&& botrowcount
-- == 0) {
1088 assert(baselevel
== 0);
1090 baselevel
= level
= 1;
1093 if (complete
!= 0) {
1095 complete
->right
= dictnil
;
1096 while (tree
[level
] != 0) {
1097 tree
[level
]->right
= complete
;
1098 complete
->parent
= tree
[level
];
1099 complete
= tree
[level
];
1105 if (complete
== NULL
) {
1106 curr
->left
= dictnil
;
1107 curr
->right
= dictnil
;
1108 curr
->color
= level
% 2;
1111 assert(level
== baselevel
);
1112 while (tree
[level
] != 0) {
1113 tree
[level
]->right
= complete
;
1114 complete
->parent
= tree
[level
];
1115 complete
= tree
[level
];
1119 curr
->left
= complete
;
1120 curr
->color
= (level
+ 1) % 2;
1121 complete
->parent
= curr
;
1128 if (complete
== NULL
)
1131 for (i
= 0; i
< DICT_DEPTH_MAX
; i
++) {
1133 tree
[i
]->right
= complete
;
1134 complete
->parent
= tree
[i
];
1139 dictnil
->color
= dnode_black
;
1140 dictnil
->right
= dictnil
;
1141 complete
->parent
= dictnil
;
1142 complete
->color
= dnode_black
;
1143 dict_root(dict
) = complete
;
1145 assert(dict_verify(dict
));
1148 void dict_merge(dict_t
*dest
, dict_t
*source
)
1151 dnode_t
*leftnode
= dict_first(dest
), *rightnode
= dict_first(source
);
1153 assert(dict_similar(dest
, source
));
1158 dest
->nodecount
= 0;
1159 load_begin_internal(&load
, dest
);
1162 if (leftnode
!= NULL
&& rightnode
!= NULL
) {
1163 if (dest
->compare(leftnode
->key
, rightnode
->key
) < 0)
1167 } else if (leftnode
!= NULL
) {
1169 } else if (rightnode
!= NULL
) {
1172 assert(leftnode
== NULL
&& rightnode
== NULL
);
1177 dnode_t
*next
= dict_next(dest
, leftnode
);
1180 NULL
; /* suppress assertion in dict_load_next */
1182 dict_load_next(&load
, leftnode
, leftnode
->key
);
1188 dnode_t
*next
= dict_next(source
, rightnode
);
1190 rightnode
->left
= NULL
;
1192 dict_load_next(&load
, rightnode
, rightnode
->key
);
1199 dict_load_end(&load
);
1202 #ifdef KAZLIB_TEST_MAIN
1209 typedef char input_t
[256];
1211 static int tokenize(char *string
, ...)
1217 va_start(arglist
, string
);
1218 tokptr
= va_arg(arglist
, char **);
1220 while (*string
&& isspace((unsigned char)*string
))
1225 while (*string
&& !isspace((unsigned char)*string
))
1227 tokptr
= va_arg(arglist
, char **);
1238 static int comparef(const void *key1
, const void *key2
)
1240 return strcmp(key1
, key2
);
1243 static char *dupstring(char *str
)
1245 int sz
= strlen(str
) + 1;
1246 char *new = XCALLOC(MTYPE_ISIS_TMP
, sz
);
1248 memcpy(new, str
, sz
);
1252 static dnode_t
*new_node(void *c
)
1254 static dnode_t few
[5];
1258 return few
+ count
++;
1263 static void del_node(dnode_t
*n
, void *c
)
1267 static int prompt
= 0;
1269 static void construct(dict_t
*d
)
1275 char *tok1
, *tok2
, *val
;
1278 "p turn prompt on\n"
1279 "q finish construction\n"
1280 "a <key> <val> add new entry\n";
1282 if (!dict_isempty(d
))
1283 puts("warning: dictionary not empty!");
1285 dict_load_begin(&dl
, d
);
1292 if (!fgets(in
, sizeof(input_t
), stdin
))
1306 if (tokenize(in
+ 1, &tok1
, &tok2
, (char **)0) != 2) {
1310 key
= dupstring(tok1
);
1311 val
= dupstring(tok2
);
1312 dn
= dnode_create(val
);
1314 if (!key
|| !val
|| !dn
) {
1315 puts("out of memory");
1322 dict_load_next(&dl
, dn
, key
);
1338 dict_t
*d
= &darray
[0];
1341 char *tok1
, *tok2
, *val
;
1345 "a <key> <val> add value to dictionary\n"
1346 "d <key> delete value from dictionary\n"
1347 "l <key> lookup value in dictionary\n"
1348 "( <key> lookup lower bound\n"
1349 ") <key> lookup upper bound\n"
1350 "# <num> switch to alternate dictionary (0-9)\n"
1351 "j <num> <num> merge two dictionaries\n"
1352 "f free the whole dictionary\n"
1353 "k allow duplicate keys\n"
1354 "c show number of entries\n"
1355 "t dump whole dictionary in sort order\n"
1356 "m make dictionary out of sorted items\n"
1357 "p turn prompt on\n"
1358 "s switch to non-functioning allocator\n"
1361 for (i
= 0; i
< 10; i
++)
1362 dict_init(&darray
[i
], DICTCOUNT_T_MAX
, comparef
);
1369 if (!fgets(in
, sizeof(input_t
), stdin
))
1377 if (tokenize(in
+ 1, &tok1
, &tok2
, (char **)0) != 2) {
1381 key
= dupstring(tok1
);
1382 val
= dupstring(tok2
);
1385 puts("out of memory");
1390 if (!dict_alloc_insert(d
, key
, val
)) {
1391 puts("dict_alloc_insert failed");
1398 if (tokenize(in
+ 1, &tok1
, (char **)0) != 1) {
1402 dn
= dict_lookup(d
, tok1
);
1404 puts("dict_lookup failed");
1407 val
= dnode_get(dn
);
1408 key
= dnode_getkey(dn
);
1409 dict_delete_free(d
, dn
);
1420 if (tokenize(in
+ 1, &tok1
, (char **)0) != 1) {
1427 dn
= dict_lookup(d
, tok1
);
1430 dn
= dict_lower_bound(d
, tok1
);
1433 dn
= dict_upper_bound(d
, tok1
);
1437 puts("lookup failed");
1440 val
= dnode_get(dn
);
1447 dict_allow_dupes(d
);
1450 printf("%lu\n", (unsigned long)dict_count(d
));
1453 for (dn
= dict_first(d
); dn
; dn
= dict_next(d
, dn
)) {
1454 printf("%s\t%s\n", (char *)dnode_getkey(dn
),
1455 (char *)dnode_get(dn
));
1467 dict_set_allocator(d
, new_node
, del_node
, NULL
);
1470 if (tokenize(in
+ 1, &tok1
, (char **)0) != 1) {
1474 int dictnum
= atoi(tok1
);
1475 if (dictnum
< 0 || dictnum
> 9) {
1476 puts("invalid number");
1479 d
= &darray
[dictnum
];
1483 if (tokenize(in
+ 1, &tok1
, &tok2
, (char **)0) != 2) {
1487 int dict1
= atoi(tok1
), dict2
= atoi(tok2
);
1488 if (dict1
< 0 || dict1
> 9 || dict2
< 0
1490 puts("invalid number");
1493 dict_merge(&darray
[dict1
], &darray
[dict2
]);