![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to gtree.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / mpd / src / contrib / libpdel / util|
Return to gtree.c CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / mpd / src / contrib / libpdel / util |
1.1 misho 1:
2: /*
3: * Copyright (c) 2001-2002 Packet Design, LLC.
4: * All rights reserved.
5: *
6: * Subject to the following obligations and disclaimer of warranty,
7: * use and redistribution of this software, in source or object code
8: * forms, with or without modifications are expressly permitted by
9: * Packet Design; provided, however, that:
10: *
11: * (i) Any and all reproductions of the source or object code
12: * must include the copyright notice above and the following
13: * disclaimer of warranties; and
14: * (ii) No rights are granted, in any manner or form, to use
15: * Packet Design trademarks, including the mark "PACKET DESIGN"
16: * on advertising, endorsements, or otherwise except as such
17: * appears in the above copyright notice or in the software.
18: *
19: * THIS SOFTWARE IS BEING PROVIDED BY PACKET DESIGN "AS IS", AND
20: * TO THE MAXIMUM EXTENT PERMITTED BY LAW, PACKET DESIGN MAKES NO
21: * REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED, REGARDING
22: * THIS SOFTWARE, INCLUDING WITHOUT LIMITATION, ANY AND ALL IMPLIED
23: * WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE,
24: * OR NON-INFRINGEMENT. PACKET DESIGN DOES NOT WARRANT, GUARANTEE,
25: * OR MAKE ANY REPRESENTATIONS REGARDING THE USE OF, OR THE RESULTS
26: * OF THE USE OF THIS SOFTWARE IN TERMS OF ITS CORRECTNESS, ACCURACY,
27: * RELIABILITY OR OTHERWISE. IN NO EVENT SHALL PACKET DESIGN BE
28: * LIABLE FOR ANY DAMAGES RESULTING FROM OR ARISING OUT OF ANY USE
29: * OF THIS SOFTWARE, INCLUDING WITHOUT LIMITATION, ANY DIRECT,
30: * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, PUNITIVE, OR CONSEQUENTIAL
31: * DAMAGES, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES, LOSS OF
32: * USE, DATA OR PROFITS, HOWEVER CAUSED AND UNDER ANY THEORY OF
33: * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
34: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
35: * THE USE OF THIS SOFTWARE, EVEN IF PACKET DESIGN IS ADVISED OF
36: * THE POSSIBILITY OF SUCH DAMAGE.
37: *
38: * Author: Archie Cobbs <archie@freebsd.org>
39: */
40:
41: #include <sys/types.h>
42: #include <sys/param.h>
43:
44: #ifdef _KERNEL
45: #include <sys/systm.h>
46: #else
47: #include <stdio.h>
48: #include <stdlib.h>
49: #include <stdarg.h>
50: #include <string.h>
51: #include <assert.h>
52: #include <errno.h>
53: #endif /* !_KERNEL */
54:
55: #include "structs/structs.h"
56: #include "structs/type/array.h"
57:
58: #include "util/gtree.h"
59: #include "util/typed_mem.h"
60:
1.1.1.2 ! misho 61: #include "defs.h"
! 62: #include "log.h"
! 63:
1.1 misho 64: /* Enabled debug tracing: only use this when keys are strings */
65: #define GTREE_TRACE 0
66:
67: enum node_color {
68: BLACK=0,
69: RED=1
70: };
71:
72: /* One node in the tree */
73: struct node {
74: enum node_color color; /* item color */
75: struct node *left; /* left child */
76: struct node *right; /* right child */
77: struct node *parent; /* parent */
1.1.1.2 ! misho 78: void *item; /* this item */
1.1 misho 79: };
80:
81: /* The tree itself */
82: struct gtree {
83: void *arg;
84: gtree_cmp_t *cmp;
85: gtree_add_t *add;
86: gtree_del_t *del;
87: gtree_print_t *print;
88: u_int mods; /* modification counter */
89: u_int size; /* number of items in table */
90: struct node *root; /* root of tree */
91: const char *mtype; /* memory type */
92: char mtbuf[TYPED_MEM_TYPELEN];
93: u_char locked;
94: };
95:
96: /*
97: * Internal functions
98: */
99: static struct node *gtree_find(struct gtree *g,
100: const void *item, struct node **parentp);
101: static struct node *gtree_get_next(struct gtree *g, struct node *node);
102: static struct node *gtree_get_prev(struct gtree *g, struct node *node);
103: static void gtree_insert_fixup(struct gtree *g, struct node *x);
104: static void gtree_delete_fixup(struct gtree *g, struct node *x);
105: static void gtree_rotate_left(struct gtree *g, struct node *x);
106: static void gtree_rotate_right(struct gtree *g, struct node *x);
107: #ifndef _KERNEL
108: static void gtree_print_node(struct gtree *g, FILE *fp,
109: struct node *node, const char *which, int depth);
110: #endif
111:
112: static gtree_cmp_t gtree_default_cmp;
113: static gtree_add_t gtree_default_add;
114: static gtree_del_t gtree_default_del;
115:
116: /*
117: * Internal variables
118: */
119:
120: #define NIL (&nil)
121:
122: /* Note: nil->parent is modified during normal operation */
1.1.1.2 ! misho 123: static struct node nil = { BLACK, NIL, NIL, NULL, NULL };
1.1 misho 124:
125: /*
126: * Create a new tree.
127: */
128: struct gtree *
129: gtree_create(void *arg, const char *mtype, gtree_cmp_t *cmp,
130: gtree_add_t *add, gtree_del_t *del, gtree_print_t *print)
131: {
132: struct gtree *g;
133:
134: /* Create new tree object */
135: if ((g = MALLOC(mtype, sizeof(*g))) == NULL)
136: return (NULL);
137: memset(g, 0, sizeof(*g));
138: g->arg = arg;
139: g->cmp = cmp != NULL ? cmp : gtree_default_cmp;
140: g->add = add != NULL ? add : gtree_default_add;
141: g->del = del != NULL ? del: gtree_default_del;
142: g->print = print;
143: g->root = NIL;
144:
145: /* Create memory subtypes */
146: if (mtype != NULL) {
147: strlcpy(g->mtbuf, mtype, sizeof(g->mtbuf));
148: g->mtype = g->mtbuf;
149: }
150:
151: #if GTREE_TRACE
152: /* Tracing */
153: if (g->print != NULL)
154: fprintf(stderr, "%s[%p]: tree created\n", __FUNCTION__, g);
155: #endif
156:
157: /* Done */
158: return (g);
159: }
160:
161: /*
162: * Destroy a tree.
163: */
164: void
165: gtree_destroy(struct gtree **gp)
166: {
167: struct gtree *const g = *gp;
168:
169: /* Sanity check */
170: if (g == NULL)
171: return;
172: assert(!g->locked);
173:
174: /* Remove all remaining nodes */
175: while (g->root != NIL)
176: gtree_remove(g, g->root->item);
177:
178: #if GTREE_TRACE
179: /* Tracing */
180: if (g->print != NULL)
181: fprintf(stderr, "%s[%p]: tree destroyed\n", __FUNCTION__, g);
182: #endif
183:
184: /* Free object */
185: FREE(g->mtype, g);
186: *gp = NULL;
187: }
188:
189: /*
190: * Get the argument supplied to gtree_create().
191: */
192: void *
193: gtree_arg(struct gtree *g)
194: {
195: return (g->arg);
196: }
197:
198: /*
199: * Return number of items in the table.
200: */
201: u_int
202: gtree_size(struct gtree *g)
203: {
204: return (g->size);
205: }
206:
207: /*
208: * Get an item.
209: *
210: * Returns the item, or NULL if the item does not exist.
211: */
212: void *
1.1.1.2 ! misho 213: gtree_get(struct gtree *g, void *item)
1.1 misho 214: {
215: struct node *dummy;
216: struct node *node;
217:
218: /* Find node */
219: node = gtree_find(g, item, &dummy);
220:
221: #if GTREE_TRACE
222: /* Tracing */
223: if (g->print != NULL) {
224: fprintf(stderr, "%s[%p]: key=\"%s\" found=%d size=%u\n",
225: __FUNCTION__, g, (*g->print)(g, (void *)item),
226: node != NULL, g->size);
227: }
228: #endif
229:
230: /* Return result */
231: if (node != NULL)
232: return ((void *)node->item);
233: return (NULL);
234: }
235:
236: /*
237: * Put an item.
238: *
239: * Returns 0 if the item is new, 1 if it replaces an existing
240: * item, and -1 if there was an error.
241: */
242: int
1.1.1.2 ! misho 243: gtree_put(struct gtree *g, void *item)
1.1 misho 244: {
245: return (gtree_put_prealloc(g, item, NULL));
246: }
247:
248: /*
249: * Put an item -- common internal code.
250: */
251: int
1.1.1.2 ! misho 252: gtree_put_prealloc(struct gtree *g, void *item, void *new_node)
1.1 misho 253: {
254: struct node *parent;
255: struct node *node;
256:
257: /* NULL item is invalid */
258: if (item == NULL) {
259: errno = EINVAL;
260: return (-1);
261: }
262:
263: /* Lock tree */
264: if (g->locked) {
265: errno = EBUSY;
266: return (-1);
267: }
268: g->locked = 1;
269:
270: /* See if item already exists */
271: node = gtree_find(g, item, &parent);
272:
273: #if GTREE_TRACE
274: /* Tracing */
275: if (g->print != NULL) {
276: fprintf(stderr, "%s[%p]: key=\"%s\" exists=%d newsize=%u\n",
277: __FUNCTION__, g, (*g->print)(g, (void *)item),
278: node != NULL, g->size + (node == NULL));
279: }
280: #endif
281:
282: /* If item already exists, just replace */
283: if (node != NULL) {
284: if (new_node != NULL)
285: FREE(g->mtype, new_node); /* didn't need it */
286: g->mods++;
287: (*g->del)(g, (void *)node->item);
288: node->item = item;
289: (*g->add)(g, (void *)node->item);
290: g->locked = 0;
291: return (1);
292: }
293:
294: /* Allocate or use caller-supplied memory for new node */
295: if (new_node != NULL)
296: node = new_node;
297: else if ((node = MALLOC(g->mtype, sizeof(*node))) == NULL) {
298: g->locked = 0;
299: return (-1);
300: }
301: memset(node, 0, sizeof(*node));
302: node->color = RED;
303: node->left = NIL;
304: node->right = NIL;
305: node->parent = parent;
306: node->item = item;
307: g->mods++;
308: g->size++;
309:
310: /* Add to tree */
311: if (parent != NULL) {
312: if ((*g->cmp)(g, node->item, parent->item) < 0)
313: parent->left = node;
314: else
315: parent->right = node;
316: } else
317: g->root = node;
318:
319: /* Rebalance */
320: gtree_insert_fixup(g, node);
321:
322: /* Notify caller of new item */
323: (*g->add)(g, (void *)node->item);
324:
325: #if GTREE_TRACE
326: /* Tracing */
327: if (g->print != NULL)
328: gtree_print(g, stderr);
329: #endif
330:
331: /* Unlock tree and return */
332: g->locked = 0;
333: return (0);
334: }
335:
336: /*
337: * Remove an item.
338: *
339: * Returns 1 if the item was found and removed, 0 if not found.
340: */
341: int
342: gtree_remove(struct gtree *g, const void *item)
343: {
344: struct node *dummy;
345: struct node *node;
346: struct node *x;
347: struct node *y;
348:
349: /* Lock tree */
350: if (g->locked) {
351: errno = EBUSY;
352: return (-1);
353: }
354: g->locked = 1;
355:
356: /* Find node */
357: node = gtree_find(g, item, &dummy);
358:
359: #if GTREE_TRACE
360: /* Tracing */
361: if (g->print != NULL) {
362: fprintf(stderr, "%s[%p]: key=\"%s\" exists=%d newsize=%u\n",
363: __FUNCTION__, g, (*g->print)(g, (void *)item),
364: node != NULL, g->size - (node != NULL));
365: }
366: #endif
367:
368: /* If not found, nothing to do */
369: if (node == NULL) {
370: g->locked = 0;
371: return (0);
372: }
373:
374: /* Notify caller of deletion */
375: (*g->del)(g, (void *)node->item);
376:
377: /* Set y to node or first successor with a NIL child */
378: if (node->left == NIL || node->right == NIL)
379: y = node;
380: else
381: for (y = node->right; y->left != NIL; y = y->left);
382:
383: /* Set x to y's only child, or NIL if no children */
384: if (y->left != NIL)
385: x = y->left;
386: else
387: x = y->right;
388:
389: /* Remove y from the parent chain */
390: x->parent = y->parent;
391: if (y->parent != NULL) {
392: if (y == y->parent->left)
393: y->parent->left = x;
394: else
395: y->parent->right = x;
396: } else
397: g->root = x;
398:
399: /* Move y's item to node */
400: if (y != node)
401: node->item = y->item;
402:
403: /* Do fixup if necessary */
404: if (y->color == BLACK)
405: gtree_delete_fixup(g, x);
406:
407: /* Free node y */
408: FREE(g->mtype, y);
409:
410: /* Update stats */
411: g->mods++;
412: g->size--;
413:
414: #if GTREE_TRACE
415: /* Tracing */
416: if (g->print != NULL)
417: gtree_print(g, stderr);
418: #endif
419:
420: /* Unlock tree and return */
421: g->locked = 0;
422: return (1);
423: }
424:
425: /*
426: * Get the size of a node.
427: */
428: u_int
429: gtree_node_size(void)
430: {
431: return (sizeof(struct node));
432: }
433:
434: /*
435: * Get the first item.
436: */
437: void *
438: gtree_first(struct gtree *g)
439: {
440: struct node *node;
441:
442: if ((node = gtree_get_next(g, NULL)) == NULL)
443: return (NULL);
444: return ((void *)node->item);
445: }
446:
447: /*
448: * Get the next item.
449: */
450: void *
451: gtree_next(struct gtree *g, const void *item)
452: {
453: struct node *dummy;
454: struct node *node;
455:
456: if ((node = gtree_find(g, item, &dummy)) == NULL)
457: return (NULL);
458: if ((node = gtree_get_next(g, node)) == NULL)
459: return (NULL);
460: return ((void *)node->item);
461: }
462:
463: /*
464: * Get the last item.
465: */
466: void *
467: gtree_last(struct gtree *g)
468: {
469: struct node *node;
470:
471: if ((node = gtree_get_prev(g, NULL)) == NULL)
472: return (NULL);
473: return ((void *)node->item);
474: }
475:
476: /*
477: * Get the previous item.
478: */
479: void *
480: gtree_prev(struct gtree *g, const void *item)
481: {
482: struct node *dummy;
483: struct node *node;
484:
485: if ((node = gtree_find(g, item, &dummy)) == NULL)
486: return (NULL);
487: if ((node = gtree_get_prev(g, node)) == NULL)
488: return (NULL);
489: return ((void *)node->item);
490: }
491:
492: /*
493: * Traverse the tree.
494: */
495: int
496: gtree_traverse(struct gtree *g, int (*handler)(struct gtree *g, void *item))
497: {
498: struct node *node;
499: int r = 0;
500:
501: /* Lock tree */
502: if (g->locked) {
503: errno = EBUSY;
504: return (-1);
505: }
506: g->locked = 1;
507:
508: /* Get items in a list */
509: for (node = gtree_get_next(g, NULL);
510: node != NULL; node = gtree_get_next(g, node)) {
511: if ((*handler)(g, (void *)node->item) == -1) {
512: r = -1;
513: break;
514: }
515: }
516:
517: /* Done */
518: g->locked = 0;
519: return (r);
520: }
521:
522: /*
523: * Get a sorted array of tree contents.
524: */
525: int
526: gtree_dump(struct gtree *g, void ***listp, const char *mtype)
527: {
528: struct node *node;
529: void **list;
1.1.1.2 ! misho 530: unsigned i;
1.1 misho 531:
532: /* Get items in a list */
533: if ((list = MALLOC(mtype, g->size * sizeof(*list))) == NULL)
534: return (-1);
535: for (i = 0, node = gtree_get_next(g, NULL);
536: node != NULL; node = gtree_get_next(g, node))
537: list[i++] = (void *)node->item;
538: assert(i == g->size);
539:
540: /* Done */
541: *listp = list;
542: return (i);
543: }
544:
545: #ifndef _KERNEL
546: /*
547: * Print out a tree
548: */
549: void
550: gtree_print(struct gtree *g, FILE *fp)
551: {
552: gtree_print_node(g, fp, g->root, "ROOT", 0);
553: }
554: #endif
555:
556: /**********************************************************************
557: DEFAULT CALLBACKS
558: **********************************************************************/
559:
560: static int
561: gtree_default_cmp(struct gtree *g, const void *item1, const void *item2)
562: {
1.1.1.2 ! misho 563: (void)g;
1.1 misho 564: if (item1 < item2)
565: return (-1);
566: if (item1 > item2)
567: return (-1);
568: return (0);
569: }
570:
571: static void
572: gtree_default_add(struct gtree *g, void *item)
573: {
1.1.1.2 ! misho 574: (void)g;
! 575: (void)item;
! 576:
1.1 misho 577: return;
578: }
579:
580: static void
581: gtree_default_del(struct gtree *g, void *item)
582: {
1.1.1.2 ! misho 583: (void)g;
! 584: (void)item;
! 585:
1.1 misho 586: return;
587: }
588:
589: /**********************************************************************
590: HELPER METHODS
591: **********************************************************************/
592:
593: /*
594: * Find an item. If not found, set *parentp to the would-be parent
595: * (NULL if the tree is empty).
596: */
597: static struct node *
598: gtree_find(struct gtree *g, const void *item, struct node **parentp)
599: {
600: struct node *node;
601: int diff;
602:
603: *parentp = NULL;
604: for (node = g->root; node != NIL; ) {
605: diff = (*g->cmp)(g, item, node->item);
606: if (diff == 0)
607: return (node);
608: *parentp = node;
609: node = (diff < 0) ? node->left : node->right;
610: }
611: return (NULL);
612: }
613:
614: /*
615: * Get the next item in the tree after "node", or the first
616: * item if "node" is NULL.
617: */
618: static struct node *
619: gtree_get_next(struct gtree *g, struct node *node)
620: {
621: if (node == NULL) {
622: if (g->root == NIL)
623: return (NULL);
624: node = g->root;
625: } else if (node->right != NIL)
626: node = node->right;
627: else {
628: while (1) {
629: if (node->parent == NULL
630: || node == node->parent->left)
631: return (node->parent);
632: node = node->parent;
633: }
634: }
635: while (node->left != NIL)
636: node = node->left;
637: return (node);
638: }
639:
640: /*
641: * Get the previous item in the tree before "node", or the last
642: * item if "node" is NULL.
643: */
644: static struct node *
645: gtree_get_prev(struct gtree *g, struct node *node)
646: {
647: if (node == NULL) {
648: if (g->root == NIL)
649: return (NULL);
650: node = g->root;
651: } else if (node->left != NIL)
652: node = node->left;
653: else {
654: while (1) {
655: if (node->parent == NULL
656: || node == node->parent->right)
657: return (node->parent);
658: node = node->parent;
659: }
660: }
661: while (node->right != NIL)
662: node = node->right;
663: return (node);
664: }
665:
666: /*
667: * Rotate node x to the left
668: */
669: static void
670: gtree_rotate_left(struct gtree *g, struct node *x)
671: {
672: struct node *y = x->right;
673:
674: x->right = y->left;
675: if (y->left != NIL)
676: y->left->parent = x;
677: if (y != NIL)
678: y->parent = x->parent;
679: if (x->parent != NULL) {
680: if (x == x->parent->left)
681: x->parent->left = y;
682: else
683: x->parent->right = y;
684: } else
685: g->root = y;
686: y->left = x;
687: if (x != NIL)
688: x->parent = y;
689: }
690:
691: /*
692: * Rotate node x to the right
693: */
694: static void
695: gtree_rotate_right(struct gtree *g, struct node *x)
696: {
697: struct node *y = x->left;
698:
699: x->left = y->right;
700: if (y->right != NIL)
701: y->right->parent = x;
702: if (y != NIL)
703: y->parent = x->parent;
704: if (x->parent != NULL) {
705: if (x == x->parent->right)
706: x->parent->right = y;
707: else
708: x->parent->left = y;
709: } else
710: g->root = y;
711: y->right = x;
712: if (x != NIL)
713: x->parent = y;
714: }
715:
716: /*
717: * Reestablish red/black balance after inserting "node"
718: */
719: static void
720: gtree_insert_fixup(struct gtree *g, struct node *x)
721: {
722: while (x != g->root && x->parent->color == RED) {
723: if (x->parent == x->parent->parent->left) {
724: struct node *y = x->parent->parent->right;
725:
726: if (y->color == RED) {
727: x->parent->color = BLACK;
728: y->color = BLACK;
729: x->parent->parent->color = RED;
730: x = x->parent->parent;
731: } else {
732: if (x == x->parent->right) {
733: x = x->parent;
734: gtree_rotate_left(g, x);
735: }
736: x->parent->color = BLACK;
737: x->parent->parent->color = RED;
738: gtree_rotate_right(g, x->parent->parent);
739: }
740: } else {
741: struct node *y = x->parent->parent->left;
742:
743: if (y->color == RED) {
744: x->parent->color = BLACK;
745: y->color = BLACK;
746: x->parent->parent->color = RED;
747: x = x->parent->parent;
748: } else {
749: if (x == x->parent->left) {
750: x = x->parent;
751: gtree_rotate_right(g, x);
752: }
753: x->parent->color = BLACK;
754: x->parent->parent->color = RED;
755: gtree_rotate_left(g, x->parent->parent);
756: }
757: }
758: }
759: g->root->color = BLACK;
760: }
761:
762: /*
763: * Reestablish red/black balance after deleting node x
764: */
765: static void
766: gtree_delete_fixup(struct gtree *g, struct node *x)
767: {
768: while (x != g->root && x->color == BLACK) {
769: if (x == x->parent->left) {
770: struct node *w = x->parent->right;
771:
772: if (w->color == RED) {
773: w->color = BLACK;
774: x->parent->color = RED;
775: gtree_rotate_left(g, x->parent);
776: w = x->parent->right;
777: }
778: if (w->left->color == BLACK
779: && w->right->color == BLACK) {
780: w->color = RED;
781: x = x->parent;
782: } else {
783: if (w->right->color == BLACK) {
784: w->left->color = BLACK;
785: w->color = RED;
786: gtree_rotate_right(g, w);
787: w = x->parent->right;
788: }
789: w->color = x->parent->color;
790: x->parent->color = BLACK;
791: w->right->color = BLACK;
792: gtree_rotate_left(g, x->parent);
793: x = g->root;
794: }
795: } else {
796: struct node *w = x->parent->left;
797:
798: if (w->color == RED) {
799: w->color = BLACK;
800: x->parent->color = RED;
801: gtree_rotate_right(g, x->parent);
802: w = x->parent->left;
803: }
804: if (w->right->color == BLACK
805: && w->left->color == BLACK) {
806: w->color = RED;
807: x = x->parent;
808: } else {
809: if (w->left->color == BLACK) {
810: w->right->color = BLACK;
811: w->color = RED;
812: gtree_rotate_left(g, w);
813: w = x->parent->left;
814: }
815: w->color = x->parent->color;
816: x->parent->color = BLACK;
817: w->left->color = BLACK;
818: gtree_rotate_right(g, x->parent);
819: x = g->root;
820: }
821: }
822: }
823: x->color = BLACK;
824: }
825:
826: #ifndef _KERNEL
827: /*
828: * Recursively print out one node and all its descendants.
829: */
830: static void
831: gtree_print_node(struct gtree *g, FILE *fp, struct node *node,
832: const char *which, int depth)
833: {
834: int i;
835:
836: for (i = 0; i < depth; i++)
837: fprintf(fp, " ");
838: fprintf(fp, "%s: ", which);
839: if (node == NIL) {
840: fprintf(fp, "NIL\n");
841: return;
842: }
843: if (g->print != NULL)
844: fprintf(fp, "%s", (*g->print)(g, (void *)node->item));
845: else
846: fprintf(fp, "%p", node);
847: fprintf(fp, " %s\n", node->color == RED ? "RED" : "BLACK");
848: if (node->left != NIL)
849: gtree_print_node(g, fp, node->left, "LEFT", depth + 1);
850: if (node->right != NIL)
851: gtree_print_node(g, fp, node->right, "RIGHT", depth + 1);
852: }
853: #endif /* !_KERNEL */
854:
855: #ifdef GTREE_TEST
856:
857: /**********************************************************************
858: TEST ROUTINE
859: **********************************************************************/
860:
861: #include <err.h>
862: #include <string.h>
863: #include <signal.h>
864: #include <unistd.h>
865: #include <time.h>
866:
867: /* Debugging */
868: #define DBG(fmt, args...) \
869: do { \
870: if (debug) \
871: printf(fmt "\n" , ## args); \
872: } while (0)
873:
874: static gtree_cmp_t gtree_test_cmp;
875: static gtree_add_t gtree_test_add;
876: static gtree_del_t gtree_test_del;
877: static gtree_print_t gtree_test_print;
878:
879: static int *trin; /* trin[i] iff i in the tree, according to add, del */
880: static int trsz; /* size of tree according to add, del */
881: static int *nums; /* fixed array where nums[i] == i */
882: static u_long num; /* size of nums[] array */
883: static int debug;
884: static struct gtree *g;
885:
886: static void gtree_assert(int i, const char *s, const char *func, int line);
887: static int chknode(struct node *node);
888:
889: #define CHECK(x) gtree_assert(x, #x, __FUNCTION__, __LINE__)
890:
891: int
892: main(int ac, char **av)
893: {
894: u_long count;
895: u_long seed;
896: int size = 0; /* my idea of what the tree size should be */
897: int *myin; /* our idea of what values are in the tree */
898: int ch;
899: int i;
900:
901: /* Default seed and count */
902: seed = htonl(getpid()) ^ time(NULL);
903: count = 10000;
904:
905: /* Parse command line */
906: while ((ch = getopt(ac, av, "dc:s:n:")) != -1) {
907: switch (ch) {
908: case 'c':
909: count = strtoul(optarg, NULL, 0);
910: break;
911: case 'd':
912: debug++;
913: break;
914: case 'n':
915: num = strtoul(optarg, NULL, 0);
916: break;
917: case 's':
918: seed = strtoul(optarg, NULL, 0);
919: break;
920: default:
921: usage:
922: errx(1, "usage: gtree [-s seed] [-c count] [-n num]");
923: }
924: }
925: ac -= optind;
926: av += optind;
927: if (ac != 0)
928: goto usage;
929:
930: /* Seed RNG */
931: srandom(seed);
932: if (num == 0)
933: num = (random() % 500) + 1;
934: printf("seed = %lu num = %lu count = %lu\n", seed, num, count);
935:
936: /* Initialize number array */
937: if ((nums = MALLOC(TYPED_MEM_TEMP, num * sizeof(*nums))) == NULL)
938: err(1, "malloc");
939: if ((myin = MALLOC(TYPED_MEM_TEMP, num * sizeof(*myin))) == NULL)
940: err(1, "malloc");
941: if ((trin = MALLOC(TYPED_MEM_TEMP, num * sizeof(*trin))) == NULL)
942: err(1, "malloc");
943: for (i = 0; i < num; i++)
944: nums[i] = i;
945: memset(myin, 0, num * sizeof(*myin));
946: memset(trin, 0, num * sizeof(*trin));
947:
948: /* Get tree */
949: if ((g = gtree_create(NULL, "gtree", gtree_test_cmp,
950: gtree_test_add, gtree_test_del, gtree_test_print)) == NULL)
951: err(1, "gtree_create");
952:
953: /* Iterate */
954: for (i = 0; i < count; i++) {
955: void **list;
956: int first;
957: int last;
958: int add;
959: int *p;
960: int i;
961: int r;
962:
963: /* Pick a random number and action */
964: i = random() % num;
965: add = (random() & (1 << (i % 17))) != 0;
966: DBG("%s %u siz=%u in=%d",
967: add ? "add" : "del", i, size, myin[i]);
968:
969: /* Do an operation (add or remove) */
970: if (add) {
971: if (gtree_put(g, &nums[i]) == -1) {
972: warn("gtree_put");
973: CHECK(0);
974: }
975: if (!myin[i])
976: size++;
977: myin[i] = 1;
978: } else {
979: r = gtree_remove(g, &nums[i]);
980: if (r == -1) {
981: warn("gtree_remove");
982: CHECK(0);
983: }
984: CHECK(r == myin[i]);
985: if (myin[i])
986: size--;
987: myin[i] = 0;
988: }
989:
990: /* Dump tree */
991: if (debug >= 2)
992: gtree_print(g, stdout);
993:
994: /* Check sizes */
995: CHECK(trsz == size);
996: CHECK(gtree_size(g) == size);
997:
998: /* Check presence of items */
999: if (memcmp(trin, myin, num * sizeof(*trin)) != 0)
1000: CHECK(0);
1001:
1002: /* Check first and last */
1003: p = (int *)gtree_first(g);
1004: first = p ? *p : -1;
1005: p = (int *)gtree_last(g);
1006: last = p ? *p : -1;
1007: for (i = 0; i < num && myin[i] == 0; i++);
1008: if (i == num)
1009: i = -1;
1010: CHECK(first == i);
1011:
1012: /* Check last */
1013: for (i = num - 1; i >= 0 && myin[i] == 0; i--);
1014: CHECK(last == i);
1015:
1016: /* Check sorting */
1017: if ((r = gtree_dump(g, &list, TYPED_MEM_TEMP)) == -1)
1018: err(1, "gtree_dump");
1019: CHECK(r == size);
1020: for (i = 1; i < r; i++) {
1021: const int this = *((int *)list[i]);
1022: const int prev = *((int *)list[i - 1]);
1023:
1024: CHECK(prev < this);
1025: }
1026: FREE(TYPED_MEM_TEMP, list);
1027:
1028: /* Check red-black property */
1029: chknode(g->root);
1030: }
1031:
1032: /* Done */
1033: gtree_destroy(&g);
1034: FREE(TYPED_MEM_TEMP, nums);
1035: FREE(TYPED_MEM_TEMP, myin);
1036: FREE(TYPED_MEM_TEMP, trin);
1037: if (debug)
1038: typed_mem_dump(stdout);
1039: return (0);
1040: }
1041:
1042: static int
1043: gtree_test_cmp(struct gtree *g, const void *item1, const void *item2)
1044: {
1045: const int *const p1 = item1;
1046: const int *const p2 = item2;
1047:
1048: CHECK(p1 >= &nums[0] && p1 < &nums[num]);
1049: CHECK(p2 >= &nums[0] && p2 < &nums[num]);
1050: return (*((int *)item1) - *((int *)item2));
1051: }
1052:
1053: static void
1054: gtree_test_add(struct gtree *g, void *item)
1055: {
1056: const int *const p = item;
1057: const int i = *((int *)item);
1058:
1059: DBG(" add->%u", i);
1060: CHECK(p >= &nums[0] && p < &nums[num]);
1061: if (gtree_remove(g, item) != -1 || errno != EBUSY)
1062: CHECK(0);
1063: CHECK(!trin[i]);
1064: trin[i] = 1;
1065: trsz++;
1066: }
1067:
1068: static void
1069: gtree_test_del(struct gtree *g, void *item)
1070: {
1071: const int *const p = item;
1072: const int i = *((int *)item);
1073:
1074: DBG(" del->%u", i);
1075: CHECK(p >= &nums[0] && p < &nums[num]);
1076: if (gtree_put(g, item) != -1 || errno != EBUSY)
1077: CHECK(0);
1078: CHECK(trin[i]);
1079: trin[i] = 0;
1080: trsz--;
1081: }
1082:
1083: static const char *
1084: gtree_test_print(struct gtree *g, const void *item)
1085: {
1086: static char buf[16];
1087:
1088: snprintf(buf, sizeof(buf), "%03u", *((u_int *)item));
1089: return (buf);
1090: }
1091:
1092: static void
1093: gtree_assert(int pred, const char *s, const char *func, int line)
1094: {
1095: if (pred)
1096: return;
1.1.1.2 ! misho 1097: Perror("FAILURE: %s:%u: %s\n", func, line, s);
1.1 misho 1098: gtree_print(g, stdout);
1099: kill(getpid(), SIGABRT);
1100: }
1101:
1102: static int
1103: chknode(struct node *node)
1104: {
1105: int l, r;
1106:
1107: CHECK(node->color == RED || node->color == BLACK);
1108: if (node == NIL) {
1109: CHECK(node->left == NIL && node->right == NIL);
1110: CHECK(node->color == BLACK);
1111: return (1);
1112: }
1113: if (node->color == RED) {
1114: CHECK(node->left->color == BLACK);
1115: CHECK(node->right->color == BLACK);
1116: }
1117: l = chknode(node->left);
1118: r = chknode(node->right);
1119: CHECK(l == r);
1120: return (l + (node->color == BLACK));
1121: }
1122:
1123: #endif /* GTREE_TEST */