]>
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
));
249 new->allocnode
= dnode_alloc
;
250 new->freenode
= dnode_free
;
253 new->maxcount
= maxcount
;
254 new->nilnode
.left
= &new->nilnode
;
255 new->nilnode
.right
= &new->nilnode
;
256 new->nilnode
.parent
= &new->nilnode
;
257 new->nilnode
.color
= dnode_black
;
264 * Select a different set of node allocator routines.
267 void dict_set_allocator(dict_t
*dict
, dnode_alloc_t al
, dnode_free_t fr
,
270 assert(dict_count(dict
) == 0);
271 assert((al
== NULL
&& fr
== NULL
) || (al
!= NULL
&& fr
!= NULL
));
273 dict
->allocnode
= al
? al
: dnode_alloc
;
274 dict
->freenode
= fr
? fr
: dnode_free
;
275 dict
->context
= context
;
279 * Free a dynamically allocated dictionary object. Removing the nodes
280 * from the tree before deleting it is required.
283 void dict_destroy(dict_t
*dict
)
285 assert(dict_isempty(dict
));
286 XFREE(MTYPE_ISIS_DICT
, dict
);
290 * Free all the nodes in the dictionary by using the dictionary's
291 * installed free routine. The dictionary is emptied.
294 void dict_free_nodes(dict_t
*dict
)
296 dnode_t
*nil
= dict_nil(dict
), *root
= dict_root(dict
);
297 free_nodes(dict
, root
, nil
);
299 dict
->nilnode
.left
= &dict
->nilnode
;
300 dict
->nilnode
.right
= &dict
->nilnode
;
304 * Obsolescent function, equivalent to dict_free_nodes
307 void dict_free(dict_t
*dict
)
309 dict_free_nodes(dict
);
313 * Initialize a user-supplied dictionary object.
316 dict_t
*dict_init(dict_t
*dict
, dictcount_t maxcount
, dict_comp_t comp
)
318 dict
->compare
= comp
;
319 dict
->allocnode
= dnode_alloc
;
320 dict
->freenode
= dnode_free
;
321 dict
->context
= NULL
;
323 dict
->maxcount
= maxcount
;
324 dict
->nilnode
.left
= &dict
->nilnode
;
325 dict
->nilnode
.right
= &dict
->nilnode
;
326 dict
->nilnode
.parent
= &dict
->nilnode
;
327 dict
->nilnode
.color
= dnode_black
;
333 * Initialize a dictionary in the likeness of another dictionary
336 void dict_init_like(dict_t
*dict
, const dict_t
*template)
338 dict
->compare
= template->compare
;
339 dict
->allocnode
= template->allocnode
;
340 dict
->freenode
= template->freenode
;
341 dict
->context
= template->context
;
343 dict
->maxcount
= template->maxcount
;
344 dict
->nilnode
.left
= &dict
->nilnode
;
345 dict
->nilnode
.right
= &dict
->nilnode
;
346 dict
->nilnode
.parent
= &dict
->nilnode
;
347 dict
->nilnode
.color
= dnode_black
;
348 dict
->dupes
= template->dupes
;
350 assert(dict_similar(dict
, template));
354 * Remove all nodes from the dictionary (without freeing them in any way).
357 static void dict_clear(dict_t
*dict
)
360 dict
->nilnode
.left
= &dict
->nilnode
;
361 dict
->nilnode
.right
= &dict
->nilnode
;
362 dict
->nilnode
.parent
= &dict
->nilnode
;
363 assert(dict
->nilnode
.color
== dnode_black
);
368 * Verify the integrity of the dictionary structure. This is provided for
369 * debugging purposes, and should be placed in assert statements. Just because
370 * this function succeeds doesn't mean that the tree is not corrupt. Certain
371 * corruptions in the tree may simply cause undefined behavior.
374 int dict_verify(dict_t
*dict
)
376 #ifdef EXTREME_DICT_DEBUG
377 dnode_t
*nil
= dict_nil(dict
), *root
= dict_root(dict
);
379 /* check that the sentinel node and root node are black */
380 if (root
->color
!= dnode_black
)
382 if (nil
->color
!= dnode_black
)
384 if (nil
->right
!= nil
)
386 /* nil->left is the root node; check that its parent pointer is nil */
387 if (nil
->left
->parent
!= nil
)
389 /* perform a weak test that the tree is a binary search tree */
390 if (!verify_bintree(dict
))
392 /* verify that the tree is a red-black tree */
393 if (!verify_redblack(nil
, root
))
395 if (verify_node_count(nil
, root
) != dict_count(dict
))
402 * Determine whether two dictionaries are similar: have the same comparison and
403 * allocator functions, and same status as to whether duplicates are allowed.
406 int dict_similar(const dict_t
*left
, const dict_t
*right
)
408 if (left
->compare
!= right
->compare
)
411 if (left
->allocnode
!= right
->allocnode
)
414 if (left
->freenode
!= right
->freenode
)
417 if (left
->context
!= right
->context
)
420 if (left
->dupes
!= right
->dupes
)
427 * Locate a node in the dictionary having the given key.
428 * If the node is not found, a null a pointer is returned (rather than
429 * a pointer that dictionary's nil sentinel node), otherwise a pointer to the
430 * located node is returned.
433 dnode_t
*dict_lookup(dict_t
*dict
, const void *key
)
435 dnode_t
*root
= dict_root(dict
);
436 dnode_t
*nil
= dict_nil(dict
);
440 /* simple binary search adapted for trees that contain duplicate keys */
442 while (root
!= nil
) {
443 result
= dict
->compare(key
, root
->key
);
449 if (!dict
->dupes
) { /* no duplicates, return match
452 } else { /* could be dupes, find leftmost one */
457 && dict
->compare(key
, root
->key
))
459 } while (root
!= nil
);
469 * Look for the node corresponding to the lowest key that is equal to or
470 * greater than the given key. If there is no such node, return null.
473 dnode_t
*dict_lower_bound(dict_t
*dict
, const void *key
)
475 dnode_t
*root
= dict_root(dict
);
476 dnode_t
*nil
= dict_nil(dict
);
477 dnode_t
*tentative
= 0;
479 while (root
!= nil
) {
480 int result
= dict
->compare(key
, root
->key
);
484 } else if (result
< 0) {
501 * Look for the node corresponding to the greatest key that is equal to or
502 * lower than the given key. If there is no such node, return null.
505 dnode_t
*dict_upper_bound(dict_t
*dict
, const void *key
)
507 dnode_t
*root
= dict_root(dict
);
508 dnode_t
*nil
= dict_nil(dict
);
509 dnode_t
*tentative
= 0;
511 while (root
!= nil
) {
512 int result
= dict
->compare(key
, root
->key
);
516 } else if (result
> 0) {
533 * Insert a node into the dictionary. The node should have been
534 * initialized with a data field. All other fields are ignored.
535 * The behavior is undefined if the user attempts to insert into
536 * a dictionary that is already full (for which the dict_isfull()
537 * function returns true).
540 void dict_insert(dict_t
*dict
, dnode_t
*node
, const void *key
)
542 dnode_t
*where
= dict_root(dict
), *nil
= dict_nil(dict
);
543 dnode_t
*parent
= nil
, *uncle
, *grandpa
;
548 assert(!dict_isfull(dict
));
549 assert(!dict_contains(dict
, node
));
550 assert(!dnode_is_in_a_dict(node
));
552 /* basic binary tree insert */
554 while (where
!= nil
) {
556 result
= dict
->compare(key
, where
->key
);
557 /* trap attempts at duplicate key insertion unless it's
558 * explicitly allowed */
559 assert(dict
->dupes
|| result
!= 0);
563 where
= where
->right
;
566 assert(where
== nil
);
571 parent
->right
= node
;
573 node
->parent
= parent
;
579 /* red black adjustments */
581 node
->color
= dnode_red
;
583 while (parent
->color
== dnode_red
) {
584 grandpa
= parent
->parent
;
585 if (parent
== grandpa
->left
) {
586 uncle
= grandpa
->right
;
588 == dnode_red
) { /* red parent, red uncle */
589 parent
->color
= dnode_black
;
590 uncle
->color
= dnode_black
;
591 grandpa
->color
= dnode_red
;
593 parent
= grandpa
->parent
;
594 } else { /* red parent, black uncle */
595 if (node
== parent
->right
) {
598 assert(grandpa
== parent
->parent
);
599 /* rotation between parent and child
600 * preserves grandpa */
602 parent
->color
= dnode_black
;
603 grandpa
->color
= dnode_red
;
604 rotate_right(grandpa
);
607 } else { /* symmetric cases: parent == parent->parent->right */
608 uncle
= grandpa
->left
;
609 if (uncle
->color
== dnode_red
) {
610 parent
->color
= dnode_black
;
611 uncle
->color
= dnode_black
;
612 grandpa
->color
= dnode_red
;
614 parent
= grandpa
->parent
;
616 if (node
== parent
->left
) {
617 rotate_right(parent
);
619 assert(grandpa
== parent
->parent
);
621 parent
->color
= dnode_black
;
622 grandpa
->color
= dnode_red
;
623 rotate_left(grandpa
);
629 dict_root(dict
)->color
= dnode_black
;
631 assert(dict_verify(dict
));
635 * Delete the given node from the dictionary. If the given node does not belong
636 * to the given dictionary, undefined behavior results. A pointer to the
637 * deleted node is returned.
640 dnode_t
*dict_delete(dict_t
*dict
, dnode_t
*delete)
642 dnode_t
*nil
= dict_nil(dict
), *child
, *delparent
= delete->parent
;
646 assert(!dict_isempty(dict
));
647 assert(dict_contains(dict
, delete));
650 * If the node being deleted has two children, then we replace it with
652 * successor (i.e. the leftmost node in the right subtree.) By doing
654 * we avoid the traditional algorithm under which the successor's key
656 * value *only* move to the deleted node and the successor is spliced
658 * from the tree. We cannot use this approach because the user may hold
659 * pointers to the successor, or nodes may be inextricably tied to some
660 * other structures by way of embedding, etc. So we must splice out the
661 * node we are given, not some other node, and must not move contents
663 * one node to another behind the user's back.
666 if (delete->left
!= nil
&& delete->right
!= nil
) {
667 dnode_t
*next
= dict_next(dict
, delete);
669 dnode_t
*nextparent
= next
->parent
;
670 dnode_color_t nextcolor
= next
->color
;
673 assert(next
->parent
!= nil
);
674 assert(next
->left
== nil
);
677 * First, splice out the successor from the tree completely, by
678 * moving up its right child into its place.
682 child
->parent
= nextparent
;
684 if (nextparent
->left
== next
) {
685 nextparent
->left
= child
;
687 assert(nextparent
->right
== next
);
688 nextparent
->right
= child
;
692 * Now that the successor has been extricated from the tree,
694 * in place of the node that we want deleted.
697 next
->parent
= delparent
;
698 next
->left
= delete->left
;
699 next
->right
= delete->right
;
700 next
->left
->parent
= next
;
701 next
->right
->parent
= next
;
702 next
->color
= delete->color
;
703 delete->color
= nextcolor
;
705 if (delparent
->left
== delete) {
706 delparent
->left
= next
;
708 assert(delparent
->right
== delete);
709 delparent
->right
= next
;
713 assert(delete != nil
);
714 assert(delete->left
== nil
|| delete->right
== nil
);
716 child
= (delete->left
!= nil
) ? delete->left
: delete->right
;
718 child
->parent
= delparent
= delete->parent
;
720 if (delete == delparent
->left
) {
721 delparent
->left
= child
;
723 assert(delete == delparent
->right
);
724 delparent
->right
= child
;
728 delete->parent
= NULL
;
729 delete->right
= NULL
;
734 assert(verify_bintree(dict
));
736 /* red-black adjustments */
738 if (delete->color
== dnode_black
) {
739 dnode_t
*parent
, *sister
;
741 dict_root(dict
)->color
= dnode_red
;
743 while (child
->color
== dnode_black
) {
744 parent
= child
->parent
;
745 if (child
== parent
->left
) {
746 sister
= parent
->right
;
747 assert(sister
!= nil
);
748 if (sister
->color
== dnode_red
) {
749 sister
->color
= dnode_black
;
750 parent
->color
= dnode_red
;
752 sister
= parent
->right
;
753 assert(sister
!= nil
);
755 if (sister
->left
->color
== dnode_black
756 && sister
->right
->color
== dnode_black
) {
757 sister
->color
= dnode_red
;
760 if (sister
->right
->color
762 assert(sister
->left
->color
764 sister
->left
->color
=
766 sister
->color
= dnode_red
;
767 rotate_right(sister
);
768 sister
= parent
->right
;
769 assert(sister
!= nil
);
771 sister
->color
= parent
->color
;
772 sister
->right
->color
= dnode_black
;
773 parent
->color
= dnode_black
;
777 } else { /* symmetric case: child ==
778 child->parent->right */
779 assert(child
== parent
->right
);
780 sister
= parent
->left
;
781 assert(sister
!= nil
);
782 if (sister
->color
== dnode_red
) {
783 sister
->color
= dnode_black
;
784 parent
->color
= dnode_red
;
785 rotate_right(parent
);
786 sister
= parent
->left
;
787 assert(sister
!= nil
);
789 if (sister
->right
->color
== dnode_black
790 && sister
->left
->color
== dnode_black
) {
791 sister
->color
= dnode_red
;
794 if (sister
->left
->color
796 assert(sister
->right
->color
798 sister
->right
->color
=
800 sister
->color
= dnode_red
;
802 sister
= parent
->left
;
803 assert(sister
!= nil
);
805 sister
->color
= parent
->color
;
806 sister
->left
->color
= dnode_black
;
807 parent
->color
= dnode_black
;
808 rotate_right(parent
);
814 child
->color
= dnode_black
;
815 dict_root(dict
)->color
= dnode_black
;
818 assert(dict_verify(dict
));
824 * Allocate a node using the dictionary's allocator routine, give it
828 int dict_alloc_insert(dict_t
*dict
, const void *key
, void *data
)
830 dnode_t
*node
= dict
->allocnode(dict
->context
);
833 dnode_init(node
, data
);
834 dict_insert(dict
, node
, key
);
840 void dict_delete_free(dict_t
*dict
, dnode_t
*node
)
842 dict_delete(dict
, node
);
843 dict
->freenode(node
, dict
->context
);
847 * Return the node with the lowest (leftmost) key. If the dictionary is empty
848 * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
851 dnode_t
*dict_first(dict_t
*dict
)
853 dnode_t
*nil
= dict_nil(dict
), *root
= dict_root(dict
), *left
;
856 while ((left
= root
->left
) != nil
)
859 return (root
== nil
) ? NULL
: root
;
863 * Return the node with the highest (rightmost) key. If the dictionary is empty
864 * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
867 dnode_t
*dict_last(dict_t
*dict
)
869 dnode_t
*nil
= dict_nil(dict
), *root
= dict_root(dict
), *right
;
872 while ((right
= root
->right
) != nil
)
875 return (root
== nil
) ? NULL
: root
;
879 * Return the given node's successor node---the node which has the
880 * next key in the the left to right ordering. If the node has
881 * no successor, a null pointer is returned rather than a pointer to
885 dnode_t
*dict_next(dict_t
*dict
, dnode_t
*curr
)
887 dnode_t
*nil
= dict_nil(dict
), *parent
, *left
;
889 if (curr
->right
!= nil
) {
891 while ((left
= curr
->left
) != nil
)
896 parent
= curr
->parent
;
898 while (parent
!= nil
&& curr
== parent
->right
) {
900 parent
= curr
->parent
;
903 return (parent
== nil
) ? NULL
: parent
;
907 * Return the given node's predecessor, in the key order.
908 * The nil sentinel node is returned if there is no predecessor.
911 dnode_t
*dict_prev(dict_t
*dict
, dnode_t
*curr
)
913 dnode_t
*nil
= dict_nil(dict
), *parent
, *right
;
915 if (curr
->left
!= nil
) {
917 while ((right
= curr
->right
) != nil
)
922 parent
= curr
->parent
;
924 while (parent
!= nil
&& curr
== parent
->left
) {
926 parent
= curr
->parent
;
929 return (parent
== nil
) ? NULL
: parent
;
932 void dict_allow_dupes(dict_t
*dict
)
944 dictcount_t
dict_count(dict_t
*dict
)
946 return dict
->nodecount
;
949 int dict_isempty(dict_t
*dict
)
951 return dict
->nodecount
== 0;
954 int dict_isfull(dict_t
*dict
)
956 return dict
->nodecount
== dict
->maxcount
;
959 int dict_contains(dict_t
*dict
, dnode_t
*node
)
961 return verify_dict_has_node(dict_nil(dict
), dict_root(dict
), node
);
964 static dnode_t
*dnode_alloc(void *context
)
966 return XCALLOC(MTYPE_ISIS_DICT_NODE
, sizeof(dnode_t
));
969 static void dnode_free(dnode_t
*node
, void *context
)
971 XFREE(MTYPE_ISIS_DICT_NODE
, node
);
974 dnode_t
*dnode_create(void *data
)
976 dnode_t
*new = XCALLOC(MTYPE_ISIS_DICT_NODE
, sizeof(dnode_t
));
986 dnode_t
*dnode_init(dnode_t
*dnode
, void *data
)
989 dnode
->parent
= NULL
;
995 void dnode_destroy(dnode_t
*dnode
)
997 assert(!dnode_is_in_a_dict(dnode
));
998 XFREE(MTYPE_ISIS_DICT_NODE
, dnode
);
1001 void *dnode_get(dnode_t
*dnode
)
1006 const void *dnode_getkey(dnode_t
*dnode
)
1011 void dnode_put(dnode_t
*dnode
, void *data
)
1016 int dnode_is_in_a_dict(dnode_t
*dnode
)
1018 return (dnode
->parent
&& dnode
->left
&& dnode
->right
);
1021 void dict_process(dict_t
*dict
, void *context
, dnode_process_t function
)
1023 dnode_t
*node
= dict_first(dict
), *next
;
1025 while (node
!= NULL
) {
1026 /* check for callback function deleting */
1027 /* the next node from under us */
1028 assert(dict_contains(dict
, node
));
1029 next
= dict_next(dict
, node
);
1030 function(dict
, node
, context
);
1035 static void load_begin_internal(dict_load_t
*load
, dict_t
*dict
)
1037 load
->dictptr
= dict
;
1038 load
->nilnode
.left
= &load
->nilnode
;
1039 load
->nilnode
.right
= &load
->nilnode
;
1042 void dict_load_begin(dict_load_t
*load
, dict_t
*dict
)
1044 assert(dict_isempty(dict
));
1045 load_begin_internal(load
, dict
);
1048 void dict_load_next(dict_load_t
*load
, dnode_t
*newnode
, const void *key
)
1050 dict_t
*dict
= load
->dictptr
;
1051 dnode_t
*nil
= &load
->nilnode
;
1053 assert(!dnode_is_in_a_dict(newnode
));
1054 assert(dict
->nodecount
< dict
->maxcount
);
1057 if (dict
->nodecount
> 0) {
1059 assert(dict
->compare(nil
->left
->key
, key
) <= 0);
1061 assert(dict
->compare(nil
->left
->key
, key
) < 0);
1066 nil
->right
->left
= newnode
;
1067 nil
->right
= newnode
;
1068 newnode
->left
= nil
;
1072 void dict_load_end(dict_load_t
*load
)
1074 dict_t
*dict
= load
->dictptr
;
1075 dnode_t
*tree
[DICT_DEPTH_MAX
] = {0};
1076 dnode_t
*curr
, *dictnil
= dict_nil(dict
), *loadnil
= &load
->nilnode
,
1078 dnode_t
*complete
= 0;
1079 dictcount_t fullcount
= DICTCOUNT_T_MAX
, nodecount
= dict
->nodecount
;
1080 dictcount_t botrowcount
;
1081 unsigned baselevel
= 0, level
= 0, i
;
1083 assert(dnode_red
== 0 && dnode_black
== 1);
1085 while (fullcount
>= nodecount
&& fullcount
)
1088 botrowcount
= nodecount
- fullcount
;
1090 for (curr
= loadnil
->left
; curr
!= loadnil
; curr
= next
) {
1093 if (complete
== NULL
&& botrowcount
-- == 0) {
1094 assert(baselevel
== 0);
1096 baselevel
= level
= 1;
1099 if (complete
!= 0) {
1101 complete
->right
= dictnil
;
1102 while (tree
[level
] != 0) {
1103 tree
[level
]->right
= complete
;
1104 complete
->parent
= tree
[level
];
1105 complete
= tree
[level
];
1111 if (complete
== NULL
) {
1112 curr
->left
= dictnil
;
1113 curr
->right
= dictnil
;
1114 curr
->color
= level
% 2;
1117 assert(level
== baselevel
);
1118 while (tree
[level
] != 0) {
1119 tree
[level
]->right
= complete
;
1120 complete
->parent
= tree
[level
];
1121 complete
= tree
[level
];
1125 curr
->left
= complete
;
1126 curr
->color
= (level
+ 1) % 2;
1127 complete
->parent
= curr
;
1134 if (complete
== NULL
)
1137 for (i
= 0; i
< DICT_DEPTH_MAX
; i
++) {
1139 tree
[i
]->right
= complete
;
1140 complete
->parent
= tree
[i
];
1145 dictnil
->color
= dnode_black
;
1146 dictnil
->right
= dictnil
;
1147 complete
->parent
= dictnil
;
1148 complete
->color
= dnode_black
;
1149 dict_root(dict
) = complete
;
1151 assert(dict_verify(dict
));
1154 void dict_merge(dict_t
*dest
, dict_t
*source
)
1157 dnode_t
*leftnode
= dict_first(dest
), *rightnode
= dict_first(source
);
1159 assert(dict_similar(dest
, source
));
1164 dest
->nodecount
= 0;
1165 load_begin_internal(&load
, dest
);
1168 if (leftnode
!= NULL
&& rightnode
!= NULL
) {
1169 if (dest
->compare(leftnode
->key
, rightnode
->key
) < 0)
1173 } else if (leftnode
!= NULL
) {
1175 } else if (rightnode
!= NULL
) {
1178 assert(leftnode
== NULL
&& rightnode
== NULL
);
1183 dnode_t
*next
= dict_next(dest
, leftnode
);
1186 NULL
; /* suppress assertion in dict_load_next */
1188 dict_load_next(&load
, leftnode
, leftnode
->key
);
1194 dnode_t
*next
= dict_next(source
, rightnode
);
1196 rightnode
->left
= NULL
;
1198 dict_load_next(&load
, rightnode
, rightnode
->key
);
1205 dict_load_end(&load
);
1208 #ifdef KAZLIB_TEST_MAIN
1215 typedef char input_t
[256];
1217 static int tokenize(char *string
, ...)
1223 va_start(arglist
, string
);
1224 tokptr
= va_arg(arglist
, char **);
1226 while (*string
&& isspace((unsigned char)*string
))
1231 while (*string
&& !isspace((unsigned char)*string
))
1233 tokptr
= va_arg(arglist
, char **);
1244 static int comparef(const void *key1
, const void *key2
)
1246 return strcmp(key1
, key2
);
1249 static char *dupstring(char *str
)
1251 int sz
= strlen(str
) + 1;
1252 char *new = XCALLOC(MTYPE_ISIS_TMP
, sz
);
1254 memcpy(new, str
, sz
);
1258 static dnode_t
*new_node(void *c
)
1260 static dnode_t few
[5];
1264 return few
+ count
++;
1269 static void del_node(dnode_t
*n
, void *c
)
1273 static int prompt
= 0;
1275 static void construct(dict_t
*d
)
1281 char *tok1
, *tok2
, *val
;
1284 "p turn prompt on\n"
1285 "q finish construction\n"
1286 "a <key> <val> add new entry\n";
1288 if (!dict_isempty(d
))
1289 puts("warning: dictionary not empty!");
1291 dict_load_begin(&dl
, d
);
1298 if (!fgets(in
, sizeof(input_t
), stdin
))
1312 if (tokenize(in
+ 1, &tok1
, &tok2
, (char **)0) != 2) {
1316 key
= dupstring(tok1
);
1317 val
= dupstring(tok2
);
1318 dn
= dnode_create(val
);
1320 if (!key
|| !val
|| !dn
) {
1321 puts("out of memory");
1327 dict_load_next(&dl
, dn
, key
);
1343 dict_t
*d
= &darray
[0];
1346 char *tok1
, *tok2
, *val
;
1350 "a <key> <val> add value to dictionary\n"
1351 "d <key> delete value from dictionary\n"
1352 "l <key> lookup value in dictionary\n"
1353 "( <key> lookup lower bound\n"
1354 ") <key> lookup upper bound\n"
1355 "# <num> switch to alternate dictionary (0-9)\n"
1356 "j <num> <num> merge two dictionaries\n"
1357 "f free the whole dictionary\n"
1358 "k allow duplicate keys\n"
1359 "c show number of entries\n"
1360 "t dump whole dictionary in sort order\n"
1361 "m make dictionary out of sorted items\n"
1362 "p turn prompt on\n"
1363 "s switch to non-functioning allocator\n"
1366 for (i
= 0; i
< 10; i
++)
1367 dict_init(&darray
[i
], DICTCOUNT_T_MAX
, comparef
);
1374 if (!fgets(in
, sizeof(input_t
), stdin
))
1382 if (tokenize(in
+ 1, &tok1
, &tok2
, (char **)0) != 2) {
1386 key
= dupstring(tok1
);
1387 val
= dupstring(tok2
);
1390 puts("out of memory");
1395 if (!dict_alloc_insert(d
, key
, val
)) {
1396 puts("dict_alloc_insert failed");
1403 if (tokenize(in
+ 1, &tok1
, (char **)0) != 1) {
1407 dn
= dict_lookup(d
, tok1
);
1409 puts("dict_lookup failed");
1412 val
= dnode_get(dn
);
1413 key
= dnode_getkey(dn
);
1414 dict_delete_free(d
, dn
);
1425 if (tokenize(in
+ 1, &tok1
, (char **)0) != 1) {
1432 dn
= dict_lookup(d
, tok1
);
1435 dn
= dict_lower_bound(d
, tok1
);
1438 dn
= dict_upper_bound(d
, tok1
);
1442 puts("lookup failed");
1445 val
= dnode_get(dn
);
1452 dict_allow_dupes(d
);
1455 printf("%lu\n", (unsigned long)dict_count(d
));
1458 for (dn
= dict_first(d
); dn
; dn
= dict_next(d
, dn
)) {
1459 printf("%s\t%s\n", (char *)dnode_getkey(dn
),
1460 (char *)dnode_get(dn
));
1472 dict_set_allocator(d
, new_node
, del_node
, NULL
);
1475 if (tokenize(in
+ 1, &tok1
, (char **)0) != 1) {
1479 int dictnum
= atoi(tok1
);
1480 if (dictnum
< 0 || dictnum
> 9) {
1481 puts("invalid number");
1484 d
= &darray
[dictnum
];
1488 if (tokenize(in
+ 1, &tok1
, &tok2
, (char **)0) != 2) {
1492 int dict1
= atoi(tok1
), dict2
= atoi(tok2
);
1493 if (dict1
< 0 || dict1
> 9 || dict2
< 0
1495 puts("invalid number");
1498 dict_merge(&darray
[dict1
], &darray
[dict2
]);