Annotation of embedaddon/libpdel/util/gtree.c, revision 1.1
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 */
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