1static char rcsid[]="$Id: redblack.c,v 1.1 2009-06-30 02:31:09 steven Exp $"; 2 3/* 4 Redblack balanced tree algorithm 5 Copyright (C) Damian Ivereigh 2000 6 7 This program is free software; you can redistribute it and/or modify 8 it under the terms of the GNU Lesser General Public License as published by 9 the Free Software Foundation; either version 2.1 of the License, or 10 (at your option) any later version. See the file COPYING for details. 11 12 This program is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU Lesser General Public License 18 along with this program; if not, write to the Free Software 19 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 20 */ 21 22/* Implement the red/black tree structure. It is designed to emulate 23** the standard tsearch() stuff. i.e. the calling conventions are 24** exactly the same 25*/ 26 27#include <stddef.h> 28#include <stdlib.h> 29#include <unistd.h> 30#include "redblack.h" 31 32#define assert(expr) 33 34/* Uncomment this if you would rather use a raw sbrk to get memory 35** (however the memory is never released again (only re-used). Can't 36** see any point in using this these days. 37*/ 38/* #define USE_SBRK */ 39 40enum nodecolour { BLACK, RED }; 41 42struct RB_ENTRY(node) 43{ 44 struct RB_ENTRY(node) *left; /* Left down */ 45 struct RB_ENTRY(node) *right; /* Right down */ 46 struct RB_ENTRY(node) *up; /* Up */ 47 enum nodecolour colour; /* Node colour */ 48#ifdef RB_INLINE 49 RB_ENTRY(data_t) key; /* User's key (and data) */ 50#define RB_GET(x,y) &x->y 51#define RB_SET(x,y,v) x->y = *(v) 52#else 53 const RB_ENTRY(data_t) *key; /* Pointer to user's key (and data) */ 54#define RB_GET(x,y) x->y 55#define RB_SET(x,y,v) x->y = v 56#endif /* RB_INLINE */ 57}; 58 59/* Dummy (sentinel) node, so that we can make X->left->up = X 60** We then use this instead of NULL to mean the top or bottom 61** end of the rb tree. It is a black node. 62** 63** Initialization of the last field in this initializer is left implicit 64** because it could be of any type. We count on the compiler to zero it. 65*/ 66struct RB_ENTRY(node) RB_ENTRY(_null)={&RB_ENTRY(_null), &RB_ENTRY(_null), &RB_ENTRY(_null), BLACK}; 67#define RBNULL (&RB_ENTRY(_null)) 68 69#if defined(USE_SBRK) 70 71static struct RB_ENTRY(node) *RB_ENTRY(_alloc)(); 72static void RB_ENTRY(_free)(struct RB_ENTRY(node) *); 73 74#else 75 76static struct RB_ENTRY(node) *RB_ENTRY(_alloc)() {return (struct RB_ENTRY(node) *) malloc(sizeof(struct RB_ENTRY(node)));} 77static void RB_ENTRY(_free)(struct RB_ENTRY(node) *x) {free(x);} 78 79#endif 80 81/* These functions are always needed */ 82static void RB_ENTRY(_left_rotate)(struct RB_ENTRY(node) **, struct RB_ENTRY(node) *); 83static void RB_ENTRY(_right_rotate)(struct RB_ENTRY(node) **, struct RB_ENTRY(node) *); 84static struct RB_ENTRY(node) *RB_ENTRY(_successor)(const struct RB_ENTRY(node) *); 85static struct RB_ENTRY(node) *RB_ENTRY(_predecessor)(const struct RB_ENTRY(node) *); 86static struct RB_ENTRY(node) *RB_ENTRY(_traverse)(int, const RB_ENTRY(data_t) * , struct RB_ENTRY(tree) *); 87 88/* These functions may not be needed */ 89#ifndef no_lookup 90static struct RB_ENTRY(node) *RB_ENTRY(_lookup)(int, const RB_ENTRY(data_t) * , struct RB_ENTRY(tree) *); 91#endif 92 93#ifndef no_destroy 94static void RB_ENTRY(_destroy)(struct RB_ENTRY(node) *); 95#endif 96 97#ifndef no_delete 98static void RB_ENTRY(_delete)(struct RB_ENTRY(node) **, struct RB_ENTRY(node) *); 99static void RB_ENTRY(_delete_fix)(struct RB_ENTRY(node) **, struct RB_ENTRY(node) *); 100#endif 101 102#ifndef no_walk 103static void RB_ENTRY(_walk)(const struct RB_ENTRY(node) *, void (*)(const RB_ENTRY(data_t) *, const VISIT, const int, void *), void *, int); 104#endif 105 106#ifndef no_readlist 107static RBLIST *RB_ENTRY(_openlist)(const struct RB_ENTRY(node) *); 108static const RB_ENTRY(data_t) * RB_ENTRY(_readlist)(RBLIST *); 109static void RB_ENTRY(_closelist)(RBLIST *); 110#endif 111 112/* 113** OK here we go, the balanced tree stuff. The algorithm is the 114** fairly standard red/black taken from "Introduction to Algorithms" 115** by Cormen, Leiserson & Rivest. Maybe one of these days I will 116** fully understand all this stuff. 117** 118** Basically a red/black balanced tree has the following properties:- 119** 1) Every node is either red or black (colour is RED or BLACK) 120** 2) A leaf (RBNULL pointer) is considered black 121** 3) If a node is red then its children are black 122** 4) Every path from a node to a leaf contains the same no 123** of black nodes 124** 125** 3) & 4) above guarantee that the longest path (alternating 126** red and black nodes) is only twice as long as the shortest 127** path (all black nodes). Thus the tree remains fairly balanced. 128*/ 129 130/* 131 * Initialise a tree. Identifies the comparison routine and any config 132 * data that must be sent to it when called. 133 * Returns a pointer to the top of the tree. 134 */ 135#ifndef RB_CUSTOMIZE 136RB_STATIC struct RB_ENTRY(tree) * 137rbinit(int (*cmp)(const void *, const void *, const void *), const void *config) 138#else 139RB_STATIC struct RB_ENTRY(tree) *RB_ENTRY(init)(void) 140#endif /* RB_CUSTOMIZE */ 141{ 142 struct RB_ENTRY(tree) *retval; 143 char c; 144 145 c=rcsid[0]; /* This does nothing but shutup the -Wall */ 146 147 if ((retval=(struct RB_ENTRY(tree) *) malloc(sizeof(struct RB_ENTRY(tree))))==NULL) 148 return(NULL); 149 150#ifndef RB_CUSTOMIZE 151 retval->rb_cmp=cmp; 152 retval->rb_config=config; 153#endif /* RB_CUSTOMIZE */ 154 retval->rb_root=RBNULL; 155 156 return(retval); 157} 158 159#ifndef no_destroy 160RB_STATIC void 161RB_ENTRY(destroy)(struct RB_ENTRY(tree) *rbinfo) 162{ 163 if (rbinfo==NULL) 164 return; 165 166 if (rbinfo->rb_root!=RBNULL) 167 RB_ENTRY(_destroy)(rbinfo->rb_root); 168 169 free(rbinfo); 170} 171#endif /* no_destroy */ 172 173#ifndef no_search 174RB_STATIC const RB_ENTRY(data_t) * 175RB_ENTRY(search)(const RB_ENTRY(data_t) *key, struct RB_ENTRY(tree) *rbinfo) 176{ 177 struct RB_ENTRY(node) *x; 178 179 if (rbinfo==NULL) 180 return(NULL); 181 182 x=RB_ENTRY(_traverse)(1, key, rbinfo); 183 184 return((x==RBNULL) ? NULL : RB_GET(x, key)); 185} 186#endif /* no_search */ 187 188#ifndef no_find 189RB_STATIC const RB_ENTRY(data_t) * 190RB_ENTRY(find)(const RB_ENTRY(data_t) *key, struct RB_ENTRY(tree) *rbinfo) 191{ 192 struct RB_ENTRY(node) *x; 193 194 if (rbinfo==NULL) 195 return(NULL); 196 197 /* If we have a NULL root (empty tree) then just return */ 198 if (rbinfo->rb_root==RBNULL) 199 return(NULL); 200 201 x=RB_ENTRY(_traverse)(0, key, rbinfo); 202 203 return((x==RBNULL) ? NULL : RB_GET(x, key)); 204} 205#endif /* no_find */ 206 207#ifndef no_delete 208RB_STATIC const RB_ENTRY(data_t) * 209RB_ENTRY(delete)(const RB_ENTRY(data_t) *key, struct RB_ENTRY(tree) *rbinfo) 210{ 211 struct RB_ENTRY(node) *x; 212 const RB_ENTRY(data_t) * y; 213 214 if (rbinfo==NULL) 215 return(NULL); 216 217 x=RB_ENTRY(_traverse)(0, key, rbinfo); 218 219 if (x==RBNULL) 220 { 221 return(NULL); 222 } 223 else 224 { 225 y=RB_GET(x, key); 226 RB_ENTRY(_delete)(&rbinfo->rb_root, x); 227 228 return(y); 229 } 230} 231#endif /* no_delete */ 232 233#ifndef no_walk 234RB_STATIC void 235RB_ENTRY(walk)(const struct RB_ENTRY(tree) *rbinfo, void (*action)(const RB_ENTRY(data_t) *, const VISIT, const int, void *), void *arg) 236{ 237 if (rbinfo==NULL) 238 return; 239 240 RB_ENTRY(_walk)(rbinfo->rb_root, action, arg, 0); 241} 242#endif /* no_walk */ 243 244#ifndef no_readlist 245RB_STATIC RBLIST * 246RB_ENTRY(openlist)(const struct RB_ENTRY(tree) *rbinfo) 247{ 248 if (rbinfo==NULL) 249 return(NULL); 250 251 return(RB_ENTRY(_openlist)(rbinfo->rb_root)); 252} 253 254RB_STATIC const RB_ENTRY(data_t) * 255RB_ENTRY(readlist)(RBLIST *rblistp) 256{ 257 if (rblistp==NULL) 258 return(NULL); 259 260 return(RB_ENTRY(_readlist)(rblistp)); 261} 262 263RB_STATIC void 264RB_ENTRY(closelist)(RBLIST *rblistp) 265{ 266 if (rblistp==NULL) 267 return; 268 269 RB_ENTRY(_closelist)(rblistp); 270} 271#endif /* no_readlist */ 272 273#ifndef no_lookup 274RB_STATIC const RB_ENTRY(data_t) * 275RB_ENTRY(lookup)(int mode, const RB_ENTRY(data_t) *key, struct RB_ENTRY(tree) *rbinfo) 276{ 277 struct RB_ENTRY(node) *x; 278 279 /* If we have a NULL root (empty tree) then just return NULL */ 280 if (rbinfo==NULL || rbinfo->rb_root==NULL) 281 return(NULL); 282 283 x=RB_ENTRY(_lookup)(mode, key, rbinfo); 284 285 return((x==RBNULL) ? NULL : RB_GET(x, key)); 286} 287#endif /* no_lookup */ 288 289/* --------------------------------------------------------------------- */ 290 291/* Search for and if not found and insert is true, will add a new 292** node in. Returns a pointer to the new node, or the node found 293*/ 294static struct RB_ENTRY(node) * 295RB_ENTRY(_traverse)(int insert, const RB_ENTRY(data_t) *key, struct RB_ENTRY(tree) *rbinfo) 296{ 297 struct RB_ENTRY(node) *x,*y,*z; 298 int cmp; 299 int found=0; 300 int cmpmods(); 301 302 y=RBNULL; /* points to the parent of x */ 303 x=rbinfo->rb_root; 304 305 /* walk x down the tree */ 306 while(x!=RBNULL && found==0) 307 { 308 y=x; 309 /* printf("key=%s, RB_GET(x, key)=%s\n", key, RB_GET(x, key)); */ 310#ifndef RB_CUSTOMIZE 311 cmp=RB_CMP(key, RB_GET(x, key), rbinfo->rb_config); 312#else 313 cmp=RB_CMP(key, RB_GET(x, key)); 314#endif /* RB_CUSTOMIZE */ 315 316 if (cmp<0) 317 x=x->left; 318 else if (cmp>0) 319 x=x->right; 320 else 321 found=1; 322 } 323 324 if (found || !insert) 325 return(x); 326 327 if ((z=RB_ENTRY(_alloc)())==NULL) 328 { 329 /* Whoops, no memory */ 330 return(RBNULL); 331 } 332 333 RB_SET(z, key, key); 334 z->up=y; 335 if (y==RBNULL) 336 { 337 rbinfo->rb_root=z; 338 } 339 else 340 { 341#ifndef RB_CUSTOMIZE 342 cmp=RB_CMP(RB_GET(z, key), RB_GET(y, key), rbinfo->rb_config); 343#else 344 cmp=RB_CMP(RB_GET(z, key), RB_GET(y, key)); 345#endif /* RB_CUSTOMIZE */ 346 if (cmp<0) 347 y->left=z; 348 else 349 y->right=z; 350 } 351 352 z->left=RBNULL; 353 z->right=RBNULL; 354 355 /* colour this new node red */ 356 z->colour=RED; 357 358 /* Having added a red node, we must now walk back up the tree balancing 359 ** it, by a series of rotations and changing of colours 360 */ 361 x=z; 362 363 /* While we are not at the top and our parent node is red 364 ** N.B. Since the root node is garanteed black, then we 365 ** are also going to stop if we are the child of the root 366 */ 367 368 while(x != rbinfo->rb_root && (x->up->colour == RED)) 369 { 370 /* if our parent is on the left side of our grandparent */ 371 if (x->up == x->up->up->left) 372 { 373 /* get the right side of our grandparent (uncle?) */ 374 y=x->up->up->right; 375 if (y->colour == RED) 376 { 377 /* make our parent black */ 378 x->up->colour = BLACK; 379 /* make our uncle black */ 380 y->colour = BLACK; 381 /* make our grandparent red */ 382 x->up->up->colour = RED; 383 384 /* now consider our grandparent */ 385 x=x->up->up; 386 } 387 else 388 { 389 /* if we are on the right side of our parent */ 390 if (x == x->up->right) 391 { 392 /* Move up to our parent */ 393 x=x->up; 394 RB_ENTRY(_left_rotate)(&rbinfo->rb_root, x); 395 } 396 397 /* make our parent black */ 398 x->up->colour = BLACK; 399 /* make our grandparent red */ 400 x->up->up->colour = RED; 401 /* right rotate our grandparent */ 402 RB_ENTRY(_right_rotate)(&rbinfo->rb_root, x->up->up); 403 } 404 } 405 else 406 { 407 /* everything here is the same as above, but 408 ** exchanging left for right 409 */ 410 411 y=x->up->up->left; 412 if (y->colour == RED) 413 { 414 x->up->colour = BLACK; 415 y->colour = BLACK; 416 x->up->up->colour = RED; 417 418 x=x->up->up; 419 } 420 else 421 { 422 if (x == x->up->left) 423 { 424 x=x->up; 425 RB_ENTRY(_right_rotate)(&rbinfo->rb_root, x); 426 } 427 428 x->up->colour = BLACK; 429 x->up->up->colour = RED; 430 RB_ENTRY(_left_rotate)(&rbinfo->rb_root, x->up->up); 431 } 432 } 433 } 434 435 /* Set the root node black */ 436 (rbinfo->rb_root)->colour = BLACK; 437 438 return(z); 439} 440 441#ifndef no_lookup 442/* Search for a key according to mode (see redblack.h) 443*/ 444static struct RB_ENTRY(node) * 445RB_ENTRY(_lookup)(int mode, const RB_ENTRY(data_t) *key, struct RB_ENTRY(tree) *rbinfo) 446{ 447 struct RB_ENTRY(node) *x,*y; 448 int cmp; 449 int found=0; 450 451 y=RBNULL; /* points to the parent of x */ 452 x=rbinfo->rb_root; 453 454 if (mode==RB_LUFIRST) 455 { 456 /* Keep going left until we hit a NULL */ 457 while(x!=RBNULL) 458 { 459 y=x; 460 x=x->left; 461 } 462 463 return(y); 464 } 465 else if (mode==RB_LULAST) 466 { 467 /* Keep going right until we hit a NULL */ 468 while(x!=RBNULL) 469 { 470 y=x; 471 x=x->right; 472 } 473 474 return(y); 475 } 476 477 /* walk x down the tree */ 478 while(x!=RBNULL && found==0) 479 { 480 y=x; 481 /* printf("key=%s, RB_GET(x, key)=%s\n", key, RB_GET(x, key)); */ 482#ifndef RB_CUSTOMIZE 483 cmp=RB_CMP(key, RB_GET(x, key), rbinfo->rb_config); 484#else 485 cmp=RB_CMP(key, RB_GET(x, key)); 486#endif /* RB_CUSTOMIZE */ 487 488 489 if (cmp<0) 490 x=x->left; 491 else if (cmp>0) 492 x=x->right; 493 else 494 found=1; 495 } 496 497 if (found && (mode==RB_LUEQUAL || mode==RB_LUGTEQ || mode==RB_LULTEQ)) 498 return(x); 499 500 if (!found && (mode==RB_LUEQUAL || mode==RB_LUNEXT || mode==RB_LUPREV)) 501 return(RBNULL); 502 503 if (mode==RB_LUGTEQ || (!found && mode==RB_LUGREAT)) 504 { 505 if (cmp>0) 506 return(RB_ENTRY(_successor)(y)); 507 else 508 return(y); 509 } 510 511 if (mode==RB_LULTEQ || (!found && mode==RB_LULESS)) 512 { 513 if (cmp<0) 514 return(RB_ENTRY(_predecessor)(y)); 515 else 516 return(y); 517 } 518 519 if (mode==RB_LUNEXT || (found && mode==RB_LUGREAT)) 520 return(RB_ENTRY(_successor)(x)); 521 522 if (mode==RB_LUPREV || (found && mode==RB_LULESS)) 523 return(RB_ENTRY(_predecessor)(x)); 524 525 /* Shouldn't get here */ 526 return(RBNULL); 527} 528#endif /* no_lookup */ 529 530#ifndef no_destroy 531/* 532 * Destroy all the elements blow us in the tree 533 * only useful as part of a complete tree destroy. 534 */ 535static void 536RB_ENTRY(_destroy)(struct RB_ENTRY(node) *x) 537{ 538 if (x!=RBNULL) 539 { 540 if (x->left!=RBNULL) 541 RB_ENTRY(_destroy)(x->left); 542 if (x->right!=RBNULL) 543 RB_ENTRY(_destroy)(x->right); 544 RB_ENTRY(_free)(x); 545 } 546} 547#endif /* no_destroy */ 548 549/* 550** Rotate our tree thus:- 551** 552** X rb_left_rotate(X)---> Y 553** / \ / \ 554** A Y <---rb_right_rotate(Y) X C 555** / \ / \ 556** B C A B 557** 558** N.B. This does not change the ordering. 559** 560** We assume that neither X or Y is NULL 561*/ 562 563static void 564RB_ENTRY(_left_rotate)(struct RB_ENTRY(node) **rootp, struct RB_ENTRY(node) *x) 565{ 566 struct RB_ENTRY(node) *y; 567 568 assert(x!=RBNULL); 569 assert(x->right!=RBNULL); 570 571 y=x->right; /* set Y */ 572 573 /* Turn Y's left subtree into X's right subtree (move B)*/ 574 x->right = y->left; 575 576 /* If B is not null, set it's parent to be X */ 577 if (y->left != RBNULL) 578 y->left->up = x; 579 580 /* Set Y's parent to be what X's parent was */ 581 y->up = x->up; 582 583 /* if X was the root */ 584 if (x->up == RBNULL) 585 { 586 *rootp=y; 587 } 588 else 589 { 590 /* Set X's parent's left or right pointer to be Y */ 591 if (x == x->up->left) 592 { 593 x->up->left=y; 594 } 595 else 596 { 597 x->up->right=y; 598 } 599 } 600 601 /* Put X on Y's left */ 602 y->left=x; 603 604 /* Set X's parent to be Y */ 605 x->up = y; 606} 607 608static void 609RB_ENTRY(_right_rotate)(struct RB_ENTRY(node) **rootp, struct RB_ENTRY(node) *y) 610{ 611 struct RB_ENTRY(node) *x; 612 613 assert(y!=RBNULL); 614 assert(y->left!=RBNULL); 615 616 x=y->left; /* set X */ 617 618 /* Turn X's right subtree into Y's left subtree (move B) */ 619 y->left = x->right; 620 621 /* If B is not null, set it's parent to be Y */ 622 if (x->right != RBNULL) 623 x->right->up = y; 624 625 /* Set X's parent to be what Y's parent was */ 626 x->up = y->up; 627 628 /* if Y was the root */ 629 if (y->up == RBNULL) 630 { 631 *rootp=x; 632 } 633 else 634 { 635 /* Set Y's parent's left or right pointer to be X */ 636 if (y == y->up->left) 637 { 638 y->up->left=x; 639 } 640 else 641 { 642 y->up->right=x; 643 } 644 } 645 646 /* Put Y on X's right */ 647 x->right=y; 648 649 /* Set Y's parent to be X */ 650 y->up = x; 651} 652 653/* Return a pointer to the smallest key greater than x 654*/ 655static struct RB_ENTRY(node) * 656RB_ENTRY(_successor)(const struct RB_ENTRY(node) *x) 657{ 658 struct RB_ENTRY(node) *y; 659 660 if (x->right!=RBNULL) 661 { 662 /* If right is not NULL then go right one and 663 ** then keep going left until we find a node with 664 ** no left pointer. 665 */ 666 for (y=x->right; y->left!=RBNULL; y=y->left); 667 } 668 else 669 { 670 /* Go up the tree until we get to a node that is on the 671 ** left of its parent (or the root) and then return the 672 ** parent. 673 */ 674 y=x->up; 675 while(y!=RBNULL && x==y->right) 676 { 677 x=y; 678 y=y->up; 679 } 680 } 681 return(y); 682} 683 684/* Return a pointer to the largest key smaller than x 685*/ 686static struct RB_ENTRY(node) * 687RB_ENTRY(_predecessor)(const struct RB_ENTRY(node) *x) 688{ 689 struct RB_ENTRY(node) *y; 690 691 if (x->left!=RBNULL) 692 { 693 /* If left is not NULL then go left one and 694 ** then keep going right until we find a node with 695 ** no right pointer. 696 */ 697 for (y=x->left; y->right!=RBNULL; y=y->right); 698 } 699 else 700 { 701 /* Go up the tree until we get to a node that is on the 702 ** right of its parent (or the root) and then return the 703 ** parent. 704 */ 705 y=x->up; 706 while(y!=RBNULL && x==y->left) 707 { 708 x=y; 709 y=y->up; 710 } 711 } 712 return(y); 713} 714 715#ifndef no_delete 716/* Delete the node z, and free up the space 717*/ 718static void 719RB_ENTRY(_delete)(struct RB_ENTRY(node) **rootp, struct RB_ENTRY(node) *z) 720{ 721 struct RB_ENTRY(node) *x, *y; 722 723 if (z->left == RBNULL || z->right == RBNULL) 724 y=z; 725 else 726 y=RB_ENTRY(_successor)(z); 727 728 if (y->left != RBNULL) 729 x=y->left; 730 else 731 x=y->right; 732 733 x->up = y->up; 734 735 if (y->up == RBNULL) 736 { 737 *rootp=x; 738 } 739 else 740 { 741 if (y==y->up->left) 742 y->up->left = x; 743 else 744 y->up->right = x; 745 } 746 747 if (y!=z) 748 { 749 RB_SET(z, key, RB_GET(y, key)); 750 } 751 752 if (y->colour == BLACK) 753 RB_ENTRY(_delete_fix)(rootp, x); 754 755 RB_ENTRY(_free)(y); 756} 757 758/* Restore the reb-black properties after a delete */ 759static void 760RB_ENTRY(_delete_fix)(struct RB_ENTRY(node) **rootp, struct RB_ENTRY(node) *x) 761{ 762 struct RB_ENTRY(node) *w; 763 764 while (x!=*rootp && x->colour==BLACK) 765 { 766 if (x==x->up->left) 767 { 768 w=x->up->right; 769 if (w->colour==RED) 770 { 771 w->colour=BLACK; 772 x->up->colour=RED; 773 rb_left_rotate(rootp, x->up); 774 w=x->up->right; 775 } 776 777 if (w->left->colour==BLACK && w->right->colour==BLACK) 778 { 779 w->colour=RED; 780 x=x->up; 781 } 782 else 783 { 784 if (w->right->colour == BLACK) 785 { 786 w->left->colour=BLACK; 787 w->colour=RED; 788 RB_ENTRY(_right_rotate)(rootp, w); 789 w=x->up->right; 790 } 791 792 793 w->colour=x->up->colour; 794 x->up->colour = BLACK; 795 w->right->colour = BLACK; 796 RB_ENTRY(_left_rotate)(rootp, x->up); 797 x=*rootp; 798 } 799 } 800 else 801 { 802 w=x->up->left; 803 if (w->colour==RED) 804 { 805 w->colour=BLACK; 806 x->up->colour=RED; 807 RB_ENTRY(_right_rotate)(rootp, x->up); 808 w=x->up->left; 809 } 810 811 if (w->right->colour==BLACK && w->left->colour==BLACK) 812 { 813 w->colour=RED; 814 x=x->up; 815 } 816 else 817 { 818 if (w->left->colour == BLACK) 819 { 820 w->right->colour=BLACK; 821 w->colour=RED; 822 RB_ENTRY(_left_rotate)(rootp, w); 823 w=x->up->left; 824 } 825 826 w->colour=x->up->colour; 827 x->up->colour = BLACK; 828 w->left->colour = BLACK; 829 RB_ENTRY(_right_rotate)(rootp, x->up); 830 x=*rootp; 831 } 832 } 833 } 834 835 x->colour=BLACK; 836} 837#endif /* no_delete */ 838 839#ifndef no_walk 840static void 841RB_ENTRY(_walk)(const struct RB_ENTRY(node) *x, void (*action)(const RB_ENTRY(data_t) *, const VISIT, const int, void *), void *arg, int level) 842{ 843 if (x==RBNULL) 844 return; 845 846 if (x->left==RBNULL && x->right==RBNULL) 847 { 848 /* leaf */ 849 (*action)(RB_GET(x, key), leaf, level, arg); 850 } 851 else 852 { 853 (*action)(RB_GET(x, key), preorder, level, arg); 854 855 RB_ENTRY(_walk)(x->left, action, arg, level+1); 856 857 (*action)(RB_GET(x, key), postorder, level, arg); 858 859 RB_ENTRY(_walk)(x->right, action, arg, level+1); 860 861 (*action)(RB_GET(x, key), endorder, level, arg); 862 } 863} 864#endif /* no_walk */ 865 866#ifndef no_readlist 867static RBLIST * 868RB_ENTRY(_openlist)(const struct RB_ENTRY(node) *rootp) 869{ 870 RBLIST *rblistp; 871 872 rblistp=(RBLIST *) malloc(sizeof(RBLIST)); 873 if (!rblistp) 874 return(NULL); 875 876 rblistp->rootp=rootp; 877 rblistp->nextp=rootp; 878 879 if (rootp!=RBNULL) 880 { 881 while(rblistp->nextp->left!=RBNULL) 882 { 883 rblistp->nextp=rblistp->nextp->left; 884 } 885 } 886 887 return(rblistp); 888} 889 890static const RB_ENTRY(data_t) * 891RB_ENTRY(_readlist)(RBLIST *rblistp) 892{ 893 const RB_ENTRY(data_t) *key=NULL; 894 895 if (rblistp!=NULL && rblistp->nextp!=RBNULL) 896 { 897 key=RB_GET(rblistp->nextp, key); 898 rblistp->nextp=RB_ENTRY(_successor)(rblistp->nextp); 899 } 900 901 return(key); 902} 903 904static void 905rb_closelist(RBLIST *rblistp) 906{ 907 if (rblistp) 908 free(rblistp); 909} 910#endif /* no_readlist */ 911 912#if defined(RB_USE_SBRK) 913/* Allocate space for our nodes, allowing us to get space from 914** sbrk in larger chucks. 915*/ 916static struct RB_ENTRY(node) *rbfreep=NULL; 917 918#define RB_ENTRY(NODE)ALLOC_CHUNK_SIZE 1000 919static struct RB_ENTRY(node) * 920RB_ENTRY(_alloc)() 921{ 922 struct RB_ENTRY(node) *x; 923 int i; 924 925 if (rbfreep==NULL) 926 { 927 /* must grab some more space */ 928 rbfreep=(struct RB_ENTRY(node) *) sbrk(sizeof(struct RB_ENTRY(node)) * RB_ENTRY(NODE)ALLOC_CHUNK_SIZE); 929 930 if (rbfreep==(struct RB_ENTRY(node) *) -1) 931 { 932 return(NULL); 933 } 934 935 /* tie them together in a linked list (use the up pointer) */ 936 for (i=0, x=rbfreep; i<RB_ENTRY(NODE)ALLOC_CHUNK_SIZE-1; i++, x++) 937 { 938 x->up = (x+1); 939 } 940 x->up=NULL; 941 } 942 943 x=rbfreep; 944 rbfreep = rbfreep->up; 945#ifdef RB_ALLOC 946 RB_ALLOC(ACCESS(x, key)); 947#endif /* RB_ALLOC */ 948 return(x); 949} 950 951/* free (dealloc) an RB_ENTRY(node) structure - add it onto the front of the list 952** N.B. RB_ENTRY(node) need not have been allocated through rb_alloc() 953*/ 954static void 955RB_ENTRY(_free)(struct RB_ENTRY(node) *x) 956{ 957#ifdef RB_FREE 958 RB_FREE(ACCESS(x, key)); 959#endif /* RB_FREE */ 960 x->up=rbfreep; 961 rbfreep=x; 962} 963 964#endif 965 966#if 0 967int 968RB_ENTRY(_check)(struct RB_ENTRY(node) *rootp) 969{ 970 if (rootp==NULL || rootp==RBNULL) 971 return(0); 972 973 if (rootp->up!=RBNULL) 974 { 975 fprintf(stderr, "Root up pointer not RBNULL"); 976 dumptree(rootp, 0); 977 return(1); 978 } 979 980 if (RB_ENTRY(_check)1(rootp)) 981 { 982 RB_ENTRY(dumptree)(rootp, 0); 983 return(1); 984 } 985 986 if (RB_ENTRY(count_black)(rootp)==-1) 987 { 988 RB_ENTRY(dumptree)(rootp, 0); 989 return(-1); 990 } 991 992 return(0); 993} 994 995int 996RB_ENTRY(_check1)(struct RB_ENTRY(node) *x) 997{ 998 if (x->left==NULL || x->right==NULL) 999 { 1000 fprintf(stderr, "Left or right is NULL"); 1001 return(1); 1002 } 1003 1004 if (x->colour==RED) 1005 { 1006 if (x->left->colour!=BLACK && x->right->colour!=BLACK) 1007 { 1008 fprintf(stderr, "Children of red node not both black, x=%ld", x); 1009 return(1); 1010 } 1011 } 1012 1013 if (x->left != RBNULL) 1014 { 1015 if (x->left->up != x) 1016 { 1017 fprintf(stderr, "x->left->up != x, x=%ld", x); 1018 return(1); 1019 } 1020 1021 if (rb_check1(x->left)) 1022 return(1); 1023 } 1024 1025 if (x->right != RBNULL) 1026 { 1027 if (x->right->up != x) 1028 { 1029 fprintf(stderr, "x->right->up != x, x=%ld", x); 1030 return(1); 1031 } 1032 1033 if (rb_check1(x->right)) 1034 return(1); 1035 } 1036 return(0); 1037} 1038 1039RB_ENTRY(count_black)(struct RB_ENTRY(node) *x) 1040{ 1041 int nleft, nright; 1042 1043 if (x==RBNULL) 1044 return(1); 1045 1046 nleft=RB_ENTRY(count_black)(x->left); 1047 nright=RB_ENTRY(count_black)(x->right); 1048 1049 if (nleft==-1 || nright==-1) 1050 return(-1); 1051 1052 if (nleft != nright) 1053 { 1054 fprintf(stderr, "Black count not equal on left & right, x=%ld", x); 1055 return(-1); 1056 } 1057 1058 if (x->colour == BLACK) 1059 { 1060 nleft++; 1061 } 1062 1063 return(nleft); 1064} 1065 1066RB_ENTRY(dumptree)(struct RB_ENTRY(node) *x, int n) 1067{ 1068 char *prkey(); 1069 1070 if (x!=NULL && x!=RBNULL) 1071 { 1072 n++; 1073 fprintf(stderr, "Tree: %*s %ld: left=%ld, right=%ld, colour=%s, key=%s", 1074 n, 1075 "", 1076 x, 1077 x->left, 1078 x->right, 1079 (x->colour==BLACK) ? "BLACK" : "RED", 1080 prkey(RB_GET(x, key))); 1081 1082 RB_ENTRY(dumptree)(x->left, n); 1083 RB_ENTRY(dumptree)(x->right, n); 1084 } 1085} 1086#endif 1087 1088/* 1089 * $Log: redblack.c,v $ 1090 * Revision 1.1 2009-06-30 02:31:09 steven 1091 * iTune Server 1092 * 1093 * Revision 1.1 2004/03/13 23:43:02 rpedde 1094 * Add Damian Ivereigh's redblack tree implementation to speed lookups 1095 * 1096 * Revision 1.9 2003/10/24 01:31:21 damo 1097 * Patches from Eric Raymond: %prefix is implemented.�� Various other small 1098 * changes avoid stepping on global namespaces and improve the documentation. 1099 * 1100 * Revision 1.8 2002/08/26 05:33:47 damo 1101 * Some minor fixes:- 1102 * Stopped ./configure warning about stuff being in the wrong order 1103 * Fixed compiler warning about const (not sure about this) 1104 * Changed directory of redblack.c in documentation 1105 * 1106 * Revision 1.7 2002/08/26 03:11:40 damo 1107 * Fixed up a bunch of compiler warnings when compiling example4 1108 * 1109 * Tidies up the Makefile.am & Specfile. 1110 * 1111 * Renamed redblack to rbgen 1112 * 1113 * Revision 1.6 2002/08/26 01:03:35 damo 1114 * Patch from Eric Raymond to change the way the library is used:- 1115 * 1116 * Eric's idea is to convert libredblack into a piece of in-line code 1117 * generated by another program. This should be faster, smaller and easier 1118 * to use. 1119 * 1120 * This is the first check-in of his code before I start futzing with it! 1121 * 1122 * Revision 1.5 2002/01/30 07:54:53 damo 1123 * Fixed up the libtool versioning stuff (finally) 1124 * Fixed bug 500600 (not detecting a NULL return from malloc) 1125 * Fixed bug 509485 (no longer needs search.h) 1126 * Cleaned up debugging section 1127 * Allow multiple inclusions of redblack.h 1128 * Thanks to Matthias Andree for reporting (and fixing) these 1129 * 1130 * Revision 1.4 2000/06/06 14:43:43 damo 1131 * Added all the rbwalk & rbopenlist stuff. Fixed up malloc instead of sbrk. 1132 * Added two new examples 1133 * 1134 * Revision 1.3 2000/05/24 06:45:27 damo 1135 * Converted everything over to using const 1136 * Added a new example1.c file to demonstrate the worst case scenario 1137 * Minor fixups of the spec file 1138 * 1139 * Revision 1.2 2000/05/24 06:17:10 damo 1140 * Fixed up the License (now the LGPL) 1141 * 1142 * Revision 1.1 2000/05/24 04:15:53 damo 1143 * Initial import of files. Versions are now all over the place. Oh well 1144 * 1145 */ 1146 1147