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