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