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: 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 */