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