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