]> git.proxmox.com Git - mirror_frr.git/blob - isisd/dict.c
lib: enforce vrf_name_to_id by returning default_vrf when name is null
[mirror_frr.git] / isisd / dict.c
1 /*
2 * Dictionary Abstract Data Type
3 * Copyright (C) 1997 Kaz Kylheku <kaz@ashi.footprints.net>
4 *
5 * Free Software License:
6 *
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.
16 */
17
18 #include "zebra.h"
19 #include "zassert.h"
20 #include "memory.h"
21 #include "isis_memory.h"
22 #include "dict.h"
23
24 /*
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!
34 */
35
36 #define left dict_left
37 #define right dict_right
38 #define parent dict_parent
39 #define color dict_color
40 #define key dict_key
41 #define data dict_data
42
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
51
52 #define dictptr dict_dictptr
53
54 #define dict_root(D) ((D)->nilnode.left)
55 #define dict_nil(D) (&(D)->nilnode)
56 #define DICT_DEPTH_MAX 64
57
58 static dnode_t *dnode_alloc(void *context);
59 static void dnode_free(dnode_t *node, void *context);
60
61 /*
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.
66 */
67
68 static void rotate_left(dnode_t *upper)
69 {
70 dnode_t *lower, *lowleft, *upparent;
71
72 lower = upper->right;
73 upper->right = lowleft = lower->left;
74 lowleft->parent = upper;
75
76 lower->parent = upparent = upper->parent;
77
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 */
80
81 if (upper == upparent->left) {
82 upparent->left = lower;
83 } else {
84 assert(upper == upparent->right);
85 upparent->right = lower;
86 }
87
88 lower->left = upper;
89 upper->parent = lower;
90 }
91
92 /*
93 * This operation is the ``mirror'' image of rotate_left. It is
94 * the same procedure, but with left and right interchanged.
95 */
96
97 static void rotate_right(dnode_t *upper)
98 {
99 dnode_t *lower, *lowright, *upparent;
100
101 lower = upper->left;
102 upper->left = lowright = lower->right;
103 lowright->parent = upper;
104
105 lower->parent = upparent = upper->parent;
106
107 if (upper == upparent->right) {
108 upparent->right = lower;
109 } else {
110 assert(upper == upparent->left);
111 upparent->left = lower;
112 }
113
114 lower->right = upper;
115 upper->parent = lower;
116 }
117
118 /*
119 * Do a postorder traversal of the tree rooted at the specified
120 * node and free everything under it. Used by dict_free().
121 */
122
123 static void free_nodes(dict_t *dict, dnode_t *node, dnode_t *nil)
124 {
125 if (node == nil)
126 return;
127 free_nodes(dict, node->left, nil);
128 free_nodes(dict, node->right, nil);
129 dict->freenode(node, dict->context);
130 }
131
132 /*
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.
139 */
140
141 static int verify_bintree(dict_t *dict)
142 {
143 dnode_t *first, *next;
144
145 first = dict_first(dict);
146
147 if (dict->dupes) {
148 while (first && (next = dict_next(dict, first))) {
149 if (dict->compare(first->key, next->key) > 0)
150 return 0;
151 first = next;
152 }
153 } else {
154 while (first && (next = dict_next(dict, first))) {
155 if (dict->compare(first->key, next->key) >= 0)
156 return 0;
157 first = next;
158 }
159 }
160 return 1;
161 }
162
163
164 /*
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.
175 */
176
177 #ifdef EXTREME_DICT_DEBUG
178 static unsigned int verify_redblack(dnode_t *nil, dnode_t *root)
179 {
180 unsigned height_left, height_right;
181
182 if (root != nil) {
183 height_left = verify_redblack(nil, root->left);
184 height_right = verify_redblack(nil, root->right);
185 if (height_left == 0 || height_right == 0)
186 return 0;
187 if (height_left != height_right)
188 return 0;
189 if (root->color == dnode_red) {
190 if (root->left->color != dnode_black)
191 return 0;
192 if (root->right->color != dnode_black)
193 return 0;
194 return height_left;
195 }
196 if (root->color != dnode_black)
197 return 0;
198 return height_left + 1;
199 }
200 return 1;
201 }
202 #endif
203
204 /*
205 * Compute the actual count of nodes by traversing the tree and
206 * return it. This could be compared against the stored count to
207 * detect a mismatch.
208 */
209
210 #ifdef EXTREME_DICT_DEBUG
211 static dictcount_t verify_node_count(dnode_t *nil, dnode_t *root)
212 {
213 if (root == nil)
214 return 0;
215 else
216 return 1 + verify_node_count(nil, root->left)
217 + verify_node_count(nil, root->right);
218 }
219 #endif
220
221 /*
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.
226 */
227
228 static int verify_dict_has_node(dnode_t *nil, dnode_t *root, dnode_t *node)
229 {
230 if (root != nil) {
231 return root == node
232 || verify_dict_has_node(nil, root->left, node)
233 || verify_dict_has_node(nil, root->right, node);
234 }
235 return 0;
236 }
237
238
239 /*
240 * Dynamically allocate and initialize a dictionary object.
241 */
242
243 dict_t *dict_create(dictcount_t maxcount, dict_comp_t comp)
244 {
245 dict_t *new = XCALLOC(MTYPE_ISIS_DICT, sizeof(dict_t));
246
247 new->compare = comp;
248 new->allocnode = dnode_alloc;
249 new->freenode = dnode_free;
250 new->context = NULL;
251 new->nodecount = 0;
252 new->maxcount = maxcount;
253 new->nilnode.left = &new->nilnode;
254 new->nilnode.right = &new->nilnode;
255 new->nilnode.parent = &new->nilnode;
256 new->nilnode.color = dnode_black;
257 new->dupes = 0;
258
259 return new;
260 }
261
262 /*
263 * Select a different set of node allocator routines.
264 */
265
266 void dict_set_allocator(dict_t *dict, dnode_alloc_t al, dnode_free_t fr,
267 void *context)
268 {
269 assert(dict_count(dict) == 0);
270 assert((al == NULL && fr == NULL) || (al != NULL && fr != NULL));
271
272 dict->allocnode = al ? al : dnode_alloc;
273 dict->freenode = fr ? fr : dnode_free;
274 dict->context = context;
275 }
276
277 /*
278 * Free a dynamically allocated dictionary object. Removing the nodes
279 * from the tree before deleting it is required.
280 */
281
282 void dict_destroy(dict_t *dict)
283 {
284 assert(dict_isempty(dict));
285 XFREE(MTYPE_ISIS_DICT, dict);
286 }
287
288 /*
289 * Free all the nodes in the dictionary by using the dictionary's
290 * installed free routine. The dictionary is emptied.
291 */
292
293 void dict_free_nodes(dict_t *dict)
294 {
295 dnode_t *nil = dict_nil(dict), *root = dict_root(dict);
296 free_nodes(dict, root, nil);
297 dict->nodecount = 0;
298 dict->nilnode.left = &dict->nilnode;
299 dict->nilnode.right = &dict->nilnode;
300 }
301
302 /*
303 * Obsolescent function, equivalent to dict_free_nodes
304 */
305
306 void dict_free(dict_t *dict)
307 {
308 dict_free_nodes(dict);
309 }
310
311 /*
312 * Initialize a user-supplied dictionary object.
313 */
314
315 dict_t *dict_init(dict_t *dict, dictcount_t maxcount, dict_comp_t comp)
316 {
317 dict->compare = comp;
318 dict->allocnode = dnode_alloc;
319 dict->freenode = dnode_free;
320 dict->context = NULL;
321 dict->nodecount = 0;
322 dict->maxcount = maxcount;
323 dict->nilnode.left = &dict->nilnode;
324 dict->nilnode.right = &dict->nilnode;
325 dict->nilnode.parent = &dict->nilnode;
326 dict->nilnode.color = dnode_black;
327 dict->dupes = 0;
328 return dict;
329 }
330
331 /*
332 * Initialize a dictionary in the likeness of another dictionary
333 */
334
335 void dict_init_like(dict_t *dict, const dict_t *template)
336 {
337 dict->compare = template->compare;
338 dict->allocnode = template->allocnode;
339 dict->freenode = template->freenode;
340 dict->context = template->context;
341 dict->nodecount = 0;
342 dict->maxcount = template->maxcount;
343 dict->nilnode.left = &dict->nilnode;
344 dict->nilnode.right = &dict->nilnode;
345 dict->nilnode.parent = &dict->nilnode;
346 dict->nilnode.color = dnode_black;
347 dict->dupes = template->dupes;
348
349 assert(dict_similar(dict, template));
350 }
351
352 /*
353 * Remove all nodes from the dictionary (without freeing them in any way).
354 */
355
356 static void dict_clear(dict_t *dict)
357 {
358 dict->nodecount = 0;
359 dict->nilnode.left = &dict->nilnode;
360 dict->nilnode.right = &dict->nilnode;
361 dict->nilnode.parent = &dict->nilnode;
362 assert(dict->nilnode.color == dnode_black);
363 }
364
365
366 /*
367 * Verify the integrity of the dictionary structure. This is provided for
368 * debugging purposes, and should be placed in assert statements. Just because
369 * this function succeeds doesn't mean that the tree is not corrupt. Certain
370 * corruptions in the tree may simply cause undefined behavior.
371 */
372
373 int dict_verify(dict_t *dict)
374 {
375 #ifdef EXTREME_DICT_DEBUG
376 dnode_t *nil = dict_nil(dict), *root = dict_root(dict);
377
378 /* check that the sentinel node and root node are black */
379 if (root->color != dnode_black)
380 return 0;
381 if (nil->color != dnode_black)
382 return 0;
383 if (nil->right != nil)
384 return 0;
385 /* nil->left is the root node; check that its parent pointer is nil */
386 if (nil->left->parent != nil)
387 return 0;
388 /* perform a weak test that the tree is a binary search tree */
389 if (!verify_bintree(dict))
390 return 0;
391 /* verify that the tree is a red-black tree */
392 if (!verify_redblack(nil, root))
393 return 0;
394 if (verify_node_count(nil, root) != dict_count(dict))
395 return 0;
396 #endif
397 return 1;
398 }
399
400 /*
401 * Determine whether two dictionaries are similar: have the same comparison and
402 * allocator functions, and same status as to whether duplicates are allowed.
403 */
404
405 int dict_similar(const dict_t *left, const dict_t *right)
406 {
407 if (left->compare != right->compare)
408 return 0;
409
410 if (left->allocnode != right->allocnode)
411 return 0;
412
413 if (left->freenode != right->freenode)
414 return 0;
415
416 if (left->context != right->context)
417 return 0;
418
419 if (left->dupes != right->dupes)
420 return 0;
421
422 return 1;
423 }
424
425 /*
426 * Locate a node in the dictionary having the given key.
427 * If the node is not found, a null a pointer is returned (rather than
428 * a pointer that dictionary's nil sentinel node), otherwise a pointer to the
429 * located node is returned.
430 */
431
432 dnode_t *dict_lookup(dict_t *dict, const void *key)
433 {
434 dnode_t *root = dict_root(dict);
435 dnode_t *nil = dict_nil(dict);
436 dnode_t *saved;
437 int result;
438
439 /* simple binary search adapted for trees that contain duplicate keys */
440
441 while (root != nil) {
442 result = dict->compare(key, root->key);
443 if (result < 0)
444 root = root->left;
445 else if (result > 0)
446 root = root->right;
447 else {
448 if (!dict->dupes) { /* no duplicates, return match
449 */
450 return root;
451 } else { /* could be dupes, find leftmost one */
452 do {
453 saved = root;
454 root = root->left;
455 while (root != nil
456 && dict->compare(key, root->key))
457 root = root->right;
458 } while (root != nil);
459 return saved;
460 }
461 }
462 }
463
464 return NULL;
465 }
466
467 /*
468 * Look for the node corresponding to the lowest key that is equal to or
469 * greater than the given key. If there is no such node, return null.
470 */
471
472 dnode_t *dict_lower_bound(dict_t *dict, const void *key)
473 {
474 dnode_t *root = dict_root(dict);
475 dnode_t *nil = dict_nil(dict);
476 dnode_t *tentative = 0;
477
478 while (root != nil) {
479 int result = dict->compare(key, root->key);
480
481 if (result > 0) {
482 root = root->right;
483 } else if (result < 0) {
484 tentative = root;
485 root = root->left;
486 } else {
487 if (!dict->dupes) {
488 return root;
489 } else {
490 tentative = root;
491 root = root->left;
492 }
493 }
494 }
495
496 return tentative;
497 }
498
499 /*
500 * Look for the node corresponding to the greatest key that is equal to or
501 * lower than the given key. If there is no such node, return null.
502 */
503
504 dnode_t *dict_upper_bound(dict_t *dict, const void *key)
505 {
506 dnode_t *root = dict_root(dict);
507 dnode_t *nil = dict_nil(dict);
508 dnode_t *tentative = 0;
509
510 while (root != nil) {
511 int result = dict->compare(key, root->key);
512
513 if (result < 0) {
514 root = root->left;
515 } else if (result > 0) {
516 tentative = root;
517 root = root->right;
518 } else {
519 if (!dict->dupes) {
520 return root;
521 } else {
522 tentative = root;
523 root = root->right;
524 }
525 }
526 }
527
528 return tentative;
529 }
530
531 /*
532 * Insert a node into the dictionary. The node should have been
533 * initialized with a data field. All other fields are ignored.
534 * The behavior is undefined if the user attempts to insert into
535 * a dictionary that is already full (for which the dict_isfull()
536 * function returns true).
537 */
538
539 void dict_insert(dict_t *dict, dnode_t *node, const void *key)
540 {
541 dnode_t *where = dict_root(dict), *nil = dict_nil(dict);
542 dnode_t *parent = nil, *uncle, *grandpa;
543 int result = -1;
544
545 node->key = key;
546
547 assert(!dict_isfull(dict));
548 assert(!dict_contains(dict, node));
549 assert(!dnode_is_in_a_dict(node));
550
551 /* basic binary tree insert */
552
553 while (where != nil) {
554 parent = where;
555 result = dict->compare(key, where->key);
556 /* trap attempts at duplicate key insertion unless it's
557 * explicitly allowed */
558 assert(dict->dupes || result != 0);
559 if (result < 0)
560 where = where->left;
561 else
562 where = where->right;
563 }
564
565 assert(where == nil);
566
567 if (result < 0)
568 parent->left = node;
569 else
570 parent->right = node;
571
572 node->parent = parent;
573 node->left = nil;
574 node->right = nil;
575
576 dict->nodecount++;
577
578 /* red black adjustments */
579
580 node->color = dnode_red;
581
582 while (parent->color == dnode_red) {
583 grandpa = parent->parent;
584 if (parent == grandpa->left) {
585 uncle = grandpa->right;
586 if (uncle->color
587 == dnode_red) { /* red parent, red uncle */
588 parent->color = dnode_black;
589 uncle->color = dnode_black;
590 grandpa->color = dnode_red;
591 node = grandpa;
592 parent = grandpa->parent;
593 } else { /* red parent, black uncle */
594 if (node == parent->right) {
595 rotate_left(parent);
596 parent = node;
597 assert(grandpa == parent->parent);
598 /* rotation between parent and child
599 * preserves grandpa */
600 }
601 parent->color = dnode_black;
602 grandpa->color = dnode_red;
603 rotate_right(grandpa);
604 break;
605 }
606 } else { /* symmetric cases: parent == parent->parent->right */
607 uncle = grandpa->left;
608 if (uncle->color == dnode_red) {
609 parent->color = dnode_black;
610 uncle->color = dnode_black;
611 grandpa->color = dnode_red;
612 node = grandpa;
613 parent = grandpa->parent;
614 } else {
615 if (node == parent->left) {
616 rotate_right(parent);
617 parent = node;
618 assert(grandpa == parent->parent);
619 }
620 parent->color = dnode_black;
621 grandpa->color = dnode_red;
622 rotate_left(grandpa);
623 break;
624 }
625 }
626 }
627
628 dict_root(dict)->color = dnode_black;
629
630 assert(dict_verify(dict));
631 }
632
633 /*
634 * Delete the given node from the dictionary. If the given node does not belong
635 * to the given dictionary, undefined behavior results. A pointer to the
636 * deleted node is returned.
637 */
638
639 dnode_t *dict_delete(dict_t *dict, dnode_t *delete)
640 {
641 dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent;
642
643 /* basic deletion */
644
645 assert(!dict_isempty(dict));
646 assert(dict_contains(dict, delete));
647
648 /*
649 * If the node being deleted has two children, then we replace it with
650 * its
651 * successor (i.e. the leftmost node in the right subtree.) By doing
652 * this,
653 * we avoid the traditional algorithm under which the successor's key
654 * and
655 * value *only* move to the deleted node and the successor is spliced
656 * out
657 * from the tree. We cannot use this approach because the user may hold
658 * pointers to the successor, or nodes may be inextricably tied to some
659 * other structures by way of embedding, etc. So we must splice out the
660 * node we are given, not some other node, and must not move contents
661 * from
662 * one node to another behind the user's back.
663 */
664
665 if (delete->left != nil && delete->right != nil) {
666 dnode_t *next = dict_next(dict, delete);
667 assert(next);
668 dnode_t *nextparent = next->parent;
669 dnode_color_t nextcolor = next->color;
670
671 assert(next != nil);
672 assert(next->parent != nil);
673 assert(next->left == nil);
674
675 /*
676 * First, splice out the successor from the tree completely, by
677 * moving up its right child into its place.
678 */
679
680 child = next->right;
681 child->parent = nextparent;
682
683 if (nextparent->left == next) {
684 nextparent->left = child;
685 } else {
686 assert(nextparent->right == next);
687 nextparent->right = child;
688 }
689
690 /*
691 * Now that the successor has been extricated from the tree,
692 * install it
693 * in place of the node that we want deleted.
694 */
695
696 next->parent = delparent;
697 next->left = delete->left;
698 next->right = delete->right;
699 next->left->parent = next;
700 next->right->parent = next;
701 next->color = delete->color;
702 delete->color = nextcolor;
703
704 if (delparent->left == delete) {
705 delparent->left = next;
706 } else {
707 assert(delparent->right == delete);
708 delparent->right = next;
709 }
710
711 } else {
712 assert(delete != nil);
713 assert(delete->left == nil || delete->right == nil);
714
715 child = (delete->left != nil) ? delete->left : delete->right;
716
717 child->parent = delparent = delete->parent;
718
719 if (delete == delparent->left) {
720 delparent->left = child;
721 } else {
722 assert(delete == delparent->right);
723 delparent->right = child;
724 }
725 }
726
727 delete->parent = NULL;
728 delete->right = NULL;
729 delete->left = NULL;
730
731 dict->nodecount--;
732
733 assert(verify_bintree(dict));
734
735 /* red-black adjustments */
736
737 if (delete->color == dnode_black) {
738 dnode_t *parent, *sister;
739
740 dict_root(dict)->color = dnode_red;
741
742 while (child->color == dnode_black) {
743 parent = child->parent;
744 if (child == parent->left) {
745 sister = parent->right;
746 assert(sister != nil);
747 if (sister->color == dnode_red) {
748 sister->color = dnode_black;
749 parent->color = dnode_red;
750 rotate_left(parent);
751 sister = parent->right;
752 assert(sister != nil);
753 }
754 if (sister->left->color == dnode_black
755 && sister->right->color == dnode_black) {
756 sister->color = dnode_red;
757 child = parent;
758 } else {
759 if (sister->right->color
760 == dnode_black) {
761 assert(sister->left->color
762 == dnode_red);
763 sister->left->color =
764 dnode_black;
765 sister->color = dnode_red;
766 rotate_right(sister);
767 sister = parent->right;
768 assert(sister != nil);
769 }
770 sister->color = parent->color;
771 sister->right->color = dnode_black;
772 parent->color = dnode_black;
773 rotate_left(parent);
774 break;
775 }
776 } else { /* symmetric case: child ==
777 child->parent->right */
778 assert(child == parent->right);
779 sister = parent->left;
780 assert(sister != nil);
781 if (sister->color == dnode_red) {
782 sister->color = dnode_black;
783 parent->color = dnode_red;
784 rotate_right(parent);
785 sister = parent->left;
786 assert(sister != nil);
787 }
788 if (sister->right->color == dnode_black
789 && sister->left->color == dnode_black) {
790 sister->color = dnode_red;
791 child = parent;
792 } else {
793 if (sister->left->color
794 == dnode_black) {
795 assert(sister->right->color
796 == dnode_red);
797 sister->right->color =
798 dnode_black;
799 sister->color = dnode_red;
800 rotate_left(sister);
801 sister = parent->left;
802 assert(sister != nil);
803 }
804 sister->color = parent->color;
805 sister->left->color = dnode_black;
806 parent->color = dnode_black;
807 rotate_right(parent);
808 break;
809 }
810 }
811 }
812
813 child->color = dnode_black;
814 dict_root(dict)->color = dnode_black;
815 }
816
817 assert(dict_verify(dict));
818
819 return delete;
820 }
821
822 /*
823 * Allocate a node using the dictionary's allocator routine, give it
824 * the data item.
825 */
826
827 int dict_alloc_insert(dict_t *dict, const void *key, void *data)
828 {
829 dnode_t *node = dict->allocnode(dict->context);
830
831 if (node) {
832 dnode_init(node, data);
833 dict_insert(dict, node, key);
834 return 1;
835 }
836 return 0;
837 }
838
839 void dict_delete_free(dict_t *dict, dnode_t *node)
840 {
841 dict_delete(dict, node);
842 dict->freenode(node, dict->context);
843 }
844
845 /*
846 * Return the node with the lowest (leftmost) key. If the dictionary is empty
847 * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
848 */
849
850 dnode_t *dict_first(dict_t *dict)
851 {
852 dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *left;
853
854 if (root != nil)
855 while ((left = root->left) != nil)
856 root = left;
857
858 return (root == nil) ? NULL : root;
859 }
860
861 /*
862 * Return the node with the highest (rightmost) key. If the dictionary is empty
863 * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
864 */
865
866 dnode_t *dict_last(dict_t *dict)
867 {
868 dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *right;
869
870 if (root != nil)
871 while ((right = root->right) != nil)
872 root = right;
873
874 return (root == nil) ? NULL : root;
875 }
876
877 /*
878 * Return the given node's successor node---the node which has the
879 * next key in the the left to right ordering. If the node has
880 * no successor, a null pointer is returned rather than a pointer to
881 * the nil node.
882 */
883
884 dnode_t *dict_next(dict_t *dict, dnode_t *curr)
885 {
886 dnode_t *nil = dict_nil(dict), *parent, *left;
887
888 if (curr->right != nil) {
889 curr = curr->right;
890 while ((left = curr->left) != nil)
891 curr = left;
892 return curr;
893 }
894
895 parent = curr->parent;
896
897 while (parent != nil && curr == parent->right) {
898 curr = parent;
899 parent = curr->parent;
900 }
901
902 return (parent == nil) ? NULL : parent;
903 }
904
905 /*
906 * Return the given node's predecessor, in the key order.
907 * The nil sentinel node is returned if there is no predecessor.
908 */
909
910 dnode_t *dict_prev(dict_t *dict, dnode_t *curr)
911 {
912 dnode_t *nil = dict_nil(dict), *parent, *right;
913
914 if (curr->left != nil) {
915 curr = curr->left;
916 while ((right = curr->right) != nil)
917 curr = right;
918 return curr;
919 }
920
921 parent = curr->parent;
922
923 while (parent != nil && curr == parent->left) {
924 curr = parent;
925 parent = curr->parent;
926 }
927
928 return (parent == nil) ? NULL : parent;
929 }
930
931 void dict_allow_dupes(dict_t *dict)
932 {
933 dict->dupes = 1;
934 }
935
936 #undef dict_count
937 #undef dict_isempty
938 #undef dict_isfull
939 #undef dnode_get
940 #undef dnode_put
941 #undef dnode_getkey
942
943 dictcount_t dict_count(dict_t *dict)
944 {
945 return dict->nodecount;
946 }
947
948 int dict_isempty(dict_t *dict)
949 {
950 return dict->nodecount == 0;
951 }
952
953 int dict_isfull(dict_t *dict)
954 {
955 return dict->nodecount == dict->maxcount;
956 }
957
958 int dict_contains(dict_t *dict, dnode_t *node)
959 {
960 return verify_dict_has_node(dict_nil(dict), dict_root(dict), node);
961 }
962
963 static dnode_t *dnode_alloc(void *context)
964 {
965 return XCALLOC(MTYPE_ISIS_DICT_NODE, sizeof(dnode_t));
966 }
967
968 static void dnode_free(dnode_t *node, void *context)
969 {
970 XFREE(MTYPE_ISIS_DICT_NODE, node);
971 }
972
973 dnode_t *dnode_create(void *data)
974 {
975 dnode_t *new = XCALLOC(MTYPE_ISIS_DICT_NODE, sizeof(dnode_t));
976
977 new->data = data;
978 new->parent = NULL;
979 new->left = NULL;
980 new->right = NULL;
981
982 return new;
983 }
984
985 dnode_t *dnode_init(dnode_t *dnode, void *data)
986 {
987 dnode->data = data;
988 dnode->parent = NULL;
989 dnode->left = NULL;
990 dnode->right = NULL;
991 return dnode;
992 }
993
994 void dnode_destroy(dnode_t *dnode)
995 {
996 assert(!dnode_is_in_a_dict(dnode));
997 XFREE(MTYPE_ISIS_DICT_NODE, dnode);
998 }
999
1000 void *dnode_get(dnode_t *dnode)
1001 {
1002 return dnode->data;
1003 }
1004
1005 const void *dnode_getkey(dnode_t *dnode)
1006 {
1007 return dnode->key;
1008 }
1009
1010 void dnode_put(dnode_t *dnode, void *data)
1011 {
1012 dnode->data = data;
1013 }
1014
1015 int dnode_is_in_a_dict(dnode_t *dnode)
1016 {
1017 return (dnode->parent && dnode->left && dnode->right);
1018 }
1019
1020 void dict_process(dict_t *dict, void *context, dnode_process_t function)
1021 {
1022 dnode_t *node = dict_first(dict), *next;
1023
1024 while (node != NULL) {
1025 /* check for callback function deleting */
1026 /* the next node from under us */
1027 assert(dict_contains(dict, node));
1028 next = dict_next(dict, node);
1029 function(dict, node, context);
1030 node = next;
1031 }
1032 }
1033
1034 static void load_begin_internal(dict_load_t *load, dict_t *dict)
1035 {
1036 load->dictptr = dict;
1037 load->nilnode.left = &load->nilnode;
1038 load->nilnode.right = &load->nilnode;
1039 }
1040
1041 void dict_load_begin(dict_load_t *load, dict_t *dict)
1042 {
1043 assert(dict_isempty(dict));
1044 load_begin_internal(load, dict);
1045 }
1046
1047 void dict_load_next(dict_load_t *load, dnode_t *newnode, const void *key)
1048 {
1049 dict_t *dict = load->dictptr;
1050 dnode_t *nil = &load->nilnode;
1051
1052 assert(!dnode_is_in_a_dict(newnode));
1053 assert(dict->nodecount < dict->maxcount);
1054
1055 #ifndef NDEBUG
1056 if (dict->nodecount > 0) {
1057 if (dict->dupes)
1058 assert(dict->compare(nil->left->key, key) <= 0);
1059 else
1060 assert(dict->compare(nil->left->key, key) < 0);
1061 }
1062 #endif
1063
1064 newnode->key = key;
1065 nil->right->left = newnode;
1066 nil->right = newnode;
1067 newnode->left = nil;
1068 dict->nodecount++;
1069 }
1070
1071 void dict_load_end(dict_load_t *load)
1072 {
1073 dict_t *dict = load->dictptr;
1074 dnode_t *tree[DICT_DEPTH_MAX] = {0};
1075 dnode_t *curr, *dictnil = dict_nil(dict), *loadnil = &load->nilnode,
1076 *next;
1077 dnode_t *complete = 0;
1078 dictcount_t fullcount = DICTCOUNT_T_MAX, nodecount = dict->nodecount;
1079 dictcount_t botrowcount;
1080 unsigned baselevel = 0, level = 0, i;
1081
1082 assert(dnode_red == 0 && dnode_black == 1);
1083
1084 while (fullcount >= nodecount && fullcount)
1085 fullcount >>= 1;
1086
1087 botrowcount = nodecount - fullcount;
1088
1089 for (curr = loadnil->left; curr != loadnil; curr = next) {
1090 next = curr->left;
1091
1092 if (complete == NULL && botrowcount-- == 0) {
1093 assert(baselevel == 0);
1094 assert(level == 0);
1095 baselevel = level = 1;
1096 complete = tree[0];
1097
1098 if (complete != 0) {
1099 tree[0] = 0;
1100 complete->right = dictnil;
1101 while (tree[level] != 0) {
1102 tree[level]->right = complete;
1103 complete->parent = tree[level];
1104 complete = tree[level];
1105 tree[level++] = 0;
1106 }
1107 }
1108 }
1109
1110 if (complete == NULL) {
1111 curr->left = dictnil;
1112 curr->right = dictnil;
1113 curr->color = level % 2;
1114 complete = curr;
1115
1116 assert(level == baselevel);
1117 while (tree[level] != 0) {
1118 tree[level]->right = complete;
1119 complete->parent = tree[level];
1120 complete = tree[level];
1121 tree[level++] = 0;
1122 }
1123 } else {
1124 curr->left = complete;
1125 curr->color = (level + 1) % 2;
1126 complete->parent = curr;
1127 tree[level] = curr;
1128 complete = 0;
1129 level = baselevel;
1130 }
1131 }
1132
1133 if (complete == NULL)
1134 complete = dictnil;
1135
1136 for (i = 0; i < DICT_DEPTH_MAX; i++) {
1137 if (tree[i] != 0) {
1138 tree[i]->right = complete;
1139 complete->parent = tree[i];
1140 complete = tree[i];
1141 }
1142 }
1143
1144 dictnil->color = dnode_black;
1145 dictnil->right = dictnil;
1146 complete->parent = dictnil;
1147 complete->color = dnode_black;
1148 dict_root(dict) = complete;
1149
1150 assert(dict_verify(dict));
1151 }
1152
1153 void dict_merge(dict_t *dest, dict_t *source)
1154 {
1155 dict_load_t load;
1156 dnode_t *leftnode = dict_first(dest), *rightnode = dict_first(source);
1157
1158 assert(dict_similar(dest, source));
1159
1160 if (source == dest)
1161 return;
1162
1163 dest->nodecount = 0;
1164 load_begin_internal(&load, dest);
1165
1166 for (;;) {
1167 if (leftnode != NULL && rightnode != NULL) {
1168 if (dest->compare(leftnode->key, rightnode->key) < 0)
1169 goto copyleft;
1170 else
1171 goto copyright;
1172 } else if (leftnode != NULL) {
1173 goto copyleft;
1174 } else if (rightnode != NULL) {
1175 goto copyright;
1176 } else {
1177 assert(leftnode == NULL && rightnode == NULL);
1178 break;
1179 }
1180
1181 copyleft : {
1182 dnode_t *next = dict_next(dest, leftnode);
1183 #ifndef NDEBUG
1184 leftnode->left =
1185 NULL; /* suppress assertion in dict_load_next */
1186 #endif
1187 dict_load_next(&load, leftnode, leftnode->key);
1188 leftnode = next;
1189 continue;
1190 }
1191
1192 copyright : {
1193 dnode_t *next = dict_next(source, rightnode);
1194 #ifndef NDEBUG
1195 rightnode->left = NULL;
1196 #endif
1197 dict_load_next(&load, rightnode, rightnode->key);
1198 rightnode = next;
1199 continue;
1200 }
1201 }
1202
1203 dict_clear(source);
1204 dict_load_end(&load);
1205 }
1206
1207 #ifdef KAZLIB_TEST_MAIN
1208
1209 #include <stdio.h>
1210 #include <string.h>
1211 #include <ctype.h>
1212 #include <stdarg.h>
1213
1214 typedef char input_t[256];
1215
1216 static int tokenize(char *string, ...)
1217 {
1218 char **tokptr;
1219 va_list arglist;
1220 int tokcount = 0;
1221
1222 va_start(arglist, string);
1223 tokptr = va_arg(arglist, char **);
1224 while (tokptr) {
1225 while (*string && isspace((unsigned char)*string))
1226 string++;
1227 if (!*string)
1228 break;
1229 *tokptr = string;
1230 while (*string && !isspace((unsigned char)*string))
1231 string++;
1232 tokptr = va_arg(arglist, char **);
1233 tokcount++;
1234 if (!*string)
1235 break;
1236 *string++ = 0;
1237 }
1238 va_end(arglist);
1239
1240 return tokcount;
1241 }
1242
1243 static int comparef(const void *key1, const void *key2)
1244 {
1245 return strcmp(key1, key2);
1246 }
1247
1248 static char *dupstring(char *str)
1249 {
1250 int sz = strlen(str) + 1;
1251 char *new = XCALLOC(MTYPE_ISIS_TMP, sz);
1252
1253 memcpy(new, str, sz);
1254 return new;
1255 }
1256
1257 static dnode_t *new_node(void *c)
1258 {
1259 static dnode_t few[5];
1260 static int count;
1261
1262 if (count < 5)
1263 return few + count++;
1264
1265 return NULL;
1266 }
1267
1268 static void del_node(dnode_t *n, void *c)
1269 {
1270 }
1271
1272 static int prompt = 0;
1273
1274 static void construct(dict_t *d)
1275 {
1276 input_t in;
1277 int done = 0;
1278 dict_load_t dl;
1279 dnode_t *dn;
1280 char *tok1, *tok2, *val;
1281 const char *key;
1282 char *help =
1283 "p turn prompt on\n"
1284 "q finish construction\n"
1285 "a <key> <val> add new entry\n";
1286
1287 if (!dict_isempty(d))
1288 puts("warning: dictionary not empty!");
1289
1290 dict_load_begin(&dl, d);
1291
1292 while (!done) {
1293 if (prompt)
1294 putchar('>');
1295 fflush(stdout);
1296
1297 if (!fgets(in, sizeof(input_t), stdin))
1298 break;
1299
1300 switch (in[0]) {
1301 case '?':
1302 puts(help);
1303 break;
1304 case 'p':
1305 prompt = 1;
1306 break;
1307 case 'q':
1308 done = 1;
1309 break;
1310 case 'a':
1311 if (tokenize(in + 1, &tok1, &tok2, (char **)0) != 2) {
1312 puts("what?");
1313 break;
1314 }
1315 key = dupstring(tok1);
1316 val = dupstring(tok2);
1317 dn = dnode_create(val);
1318
1319 if (!key || !val || !dn) {
1320 puts("out of memory");
1321 free((void *)key);
1322 free(val);
1323 if (dn)
1324 dnode_destroy(dn);
1325 } else
1326 dict_load_next(&dl, dn, key);
1327 break;
1328 default:
1329 putchar('?');
1330 putchar('\n');
1331 break;
1332 }
1333 }
1334
1335 dict_load_end(&dl);
1336 }
1337
1338 int main(void)
1339 {
1340 input_t in;
1341 dict_t darray[10];
1342 dict_t *d = &darray[0];
1343 dnode_t *dn;
1344 int i;
1345 char *tok1, *tok2, *val;
1346 const char *key;
1347
1348 char *help =
1349 "a <key> <val> add value to dictionary\n"
1350 "d <key> delete value from dictionary\n"
1351 "l <key> lookup value in dictionary\n"
1352 "( <key> lookup lower bound\n"
1353 ") <key> lookup upper bound\n"
1354 "# <num> switch to alternate dictionary (0-9)\n"
1355 "j <num> <num> merge two dictionaries\n"
1356 "f free the whole dictionary\n"
1357 "k allow duplicate keys\n"
1358 "c show number of entries\n"
1359 "t dump whole dictionary in sort order\n"
1360 "m make dictionary out of sorted items\n"
1361 "p turn prompt on\n"
1362 "s switch to non-functioning allocator\n"
1363 "q quit";
1364
1365 for (i = 0; i < 10; i++)
1366 dict_init(&darray[i], DICTCOUNT_T_MAX, comparef);
1367
1368 for (;;) {
1369 if (prompt)
1370 putchar('>');
1371 fflush(stdout);
1372
1373 if (!fgets(in, sizeof(input_t), stdin))
1374 break;
1375
1376 switch (in[0]) {
1377 case '?':
1378 puts(help);
1379 break;
1380 case 'a':
1381 if (tokenize(in + 1, &tok1, &tok2, (char **)0) != 2) {
1382 puts("what?");
1383 break;
1384 }
1385 key = dupstring(tok1);
1386 val = dupstring(tok2);
1387
1388 if (!key || !val) {
1389 puts("out of memory");
1390 free((void *)key);
1391 free(val);
1392 }
1393
1394 if (!dict_alloc_insert(d, key, val)) {
1395 puts("dict_alloc_insert failed");
1396 free((void *)key);
1397 free(val);
1398 break;
1399 }
1400 break;
1401 case 'd':
1402 if (tokenize(in + 1, &tok1, (char **)0) != 1) {
1403 puts("what?");
1404 break;
1405 }
1406 dn = dict_lookup(d, tok1);
1407 if (!dn) {
1408 puts("dict_lookup failed");
1409 break;
1410 }
1411 val = dnode_get(dn);
1412 key = dnode_getkey(dn);
1413 dict_delete_free(d, dn);
1414
1415 free(val);
1416 free((void *)key);
1417 break;
1418 case 'f':
1419 dict_free(d);
1420 break;
1421 case 'l':
1422 case '(':
1423 case ')':
1424 if (tokenize(in + 1, &tok1, (char **)0) != 1) {
1425 puts("what?");
1426 break;
1427 }
1428 dn = 0;
1429 switch (in[0]) {
1430 case 'l':
1431 dn = dict_lookup(d, tok1);
1432 break;
1433 case '(':
1434 dn = dict_lower_bound(d, tok1);
1435 break;
1436 case ')':
1437 dn = dict_upper_bound(d, tok1);
1438 break;
1439 }
1440 if (!dn) {
1441 puts("lookup failed");
1442 break;
1443 }
1444 val = dnode_get(dn);
1445 puts(val);
1446 break;
1447 case 'm':
1448 construct(d);
1449 break;
1450 case 'k':
1451 dict_allow_dupes(d);
1452 break;
1453 case 'c':
1454 printf("%lu\n", (unsigned long)dict_count(d));
1455 break;
1456 case 't':
1457 for (dn = dict_first(d); dn; dn = dict_next(d, dn)) {
1458 printf("%s\t%s\n", (char *)dnode_getkey(dn),
1459 (char *)dnode_get(dn));
1460 }
1461 break;
1462 case 'q':
1463 exit(0);
1464 break;
1465 case '\0':
1466 break;
1467 case 'p':
1468 prompt = 1;
1469 break;
1470 case 's':
1471 dict_set_allocator(d, new_node, del_node, NULL);
1472 break;
1473 case '#':
1474 if (tokenize(in + 1, &tok1, (char **)0) != 1) {
1475 puts("what?");
1476 break;
1477 } else {
1478 int dictnum = atoi(tok1);
1479 if (dictnum < 0 || dictnum > 9) {
1480 puts("invalid number");
1481 break;
1482 }
1483 d = &darray[dictnum];
1484 }
1485 break;
1486 case 'j':
1487 if (tokenize(in + 1, &tok1, &tok2, (char **)0) != 2) {
1488 puts("what?");
1489 break;
1490 } else {
1491 int dict1 = atoi(tok1), dict2 = atoi(tok2);
1492 if (dict1 < 0 || dict1 > 9 || dict2 < 0
1493 || dict2 > 9) {
1494 puts("invalid number");
1495 break;
1496 }
1497 dict_merge(&darray[dict1], &darray[dict2]);
1498 }
1499 break;
1500 default:
1501 putchar('?');
1502 putchar('\n');
1503 break;
1504 }
1505 }
1506
1507 return 0;
1508 }
1509
1510 #endif