Repair/RepairCompiler/MCC/CRuntime/redblack.c

   1 static char rcsid[]="$Id: redblack.c,v 1.1 2004/10/28 19:28:59 bdemsky 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 #define RB_TRUE 1
  34 #define RB_FALSE 0
  35
  36 /* Uncomment this if you would rather use a raw sbrk to get memory
  37 ** (however the memory is never released again (only re-used). Can't
  38 ** see any point in using this these days.
  39 */
  40 /* #define USE_SBRK */
  41
  42 enum nodecolour { BLACK, RED };
  43
  44 struct rbnode {
  45   struct rbnode *left;          /* Left down */
  46   struct rbnode *right;         /* Right down */
  47   struct rbnode *up;            /* Up */
  48   enum nodecolour colour;               /* Node colour */
  49   const void *key;              /* Pointer to user's key (and data) */
  50   const void *high;
  51   const void *max;
  52   void *object;
  53 };
  54
  55 /* Dummy (sentinel) node, so that we can make X->left->up = X
  56 ** We then use this instead of NULL to mean the top or bottom
  57 ** end of the rb tree. It is a black node.
  58 */
  59 struct rbnode rb_null={&rb_null, &rb_null, &rb_null, BLACK, NULL,NULL,NULL,NULL};
  60 #define RBNULL (&rb_null)
  61
  62 #if defined(USE_SBRK)
  63
  64 static struct rbnode *rb_alloc();
  65 static void rb_free(struct rbnode *);
  66
  67 #else
  68
  69 #define rb_alloc() ((struct rbnode *) malloc(sizeof(struct rbnode)))
  70 #define rb_free(x) (free(x))
  71
  72 #endif
  73
  74 static struct rbnode *rb_traverse(const void *, struct rbtree *);
  75 static struct rbnode *rb_lookup(const void *low,const void *high, struct rbtree *);
  76 static void rb_destroy(struct rbnode *,void (*)(void *));
  77 static void rb_left_rotate(struct rbnode **, struct rbnode *);
  78 static void rb_right_rotate(struct rbnode **, struct rbnode *);
  79 static void rb_delete(struct rbnode **, struct rbnode *);
  80 static void rb_delete_fix(struct rbnode **, struct rbnode *);
  81 static struct rbnode *rb_successor(const struct rbnode *);
  82 static struct rbnode *rb_preccessor(const struct rbnode *);
  83 static void rb_walk(const struct rbnode *, void (*)(const void *, const VISIT, const int, void *), void *, int);
  84 static RBLIST *rb_openlist(const struct rbnode *);
  85 static const void *rb_readlist(RBLIST *);
  86 static void rb_closelist(RBLIST *);
  87
  88 /*
  89 ** OK here we go, the balanced tree stuff. The algorithm is the
  90 ** fairly standard red/black taken from "Introduction to Algorithms"
  91 ** by Cormen, Leiserson & Rivest. Maybe one of these days I will
  92 ** fully understand all this stuff.
  93 **
  94 ** Basically a red/black balanced tree has the following properties:-
  95 ** 1) Every node is either red or black (colour is RED or BLACK)
  96 ** 2) A leaf (RBNULL pointer) is considered black
  97 ** 3) If a node is red then its children are black
  98 ** 4) Every path from a node to a leaf contains the same no
  99 **    of black nodes
 100 **
 101 ** 3) & 4) above guarantee that the longest path (alternating
 102 ** red and black nodes) is only twice as long as the shortest
 103 ** path (all black nodes). Thus the tree remains fairly balanced.
 104 */
 105
 106 /*
 107  * Initialise a tree. Identifies the comparison routine and any config
 108  * data that must be sent to it when called.
 109  * Returns a pointer to the top of the tree.
 110  */
 111 struct rbtree * rbinit() {
 112   struct rbtree *retval;
 113   char c;
 114
 115   c=rcsid[0]; /* This does nothing but shutup the -Wall */
 116
 117   if ((retval=(struct rbtree *) malloc(sizeof(struct rbtree)))==NULL)
 118     return(NULL);
 119
 120   retval->rb_root=RBNULL;
 121
 122   return(retval);
 123 }
 124
 125 void rbdestroy(struct rbtree *rbinfo, void (*free_function)(void *)) {
 126   if (rbinfo==NULL)
 127     return;
 128
 129   if (rbinfo->rb_root!=RBNULL)
 130     rb_destroy(rbinfo->rb_root,free_function);
 131
 132   free(rbinfo);
 133 }
 134
 135 const void * rbdelete(const void *key, struct rbtree *rbinfo) {
 136   struct rbnode *x;
 137   const void *y;
 138
 139   if (rbinfo==NULL)
 140     return(NULL);
 141
 142   x=rb_traverse(key, rbinfo);
 143
 144   if (x==RBNULL) {
 145     return(NULL);
 146   } else {
 147     y=x->key;
 148     rb_delete(&rbinfo->rb_root, x);
 149
 150     return(y);
 151   }
 152 }
 153
 154 void rbwalk(const struct rbtree *rbinfo, void (*action)(const void *, const VISIT, const int, void *), void *arg) {
 155   if (rbinfo==NULL)
 156     return;
 157
 158   rb_walk(rbinfo->rb_root, action, arg, 0);
 159 }
 160
 161 RBLIST * rbopenlist(const struct rbtree *rbinfo) {
 162   if (rbinfo==NULL)
 163     return(NULL);
 164
 165   return(rb_openlist(rbinfo->rb_root));
 166 }
 167
 168 const void * rbreadlist(RBLIST *rblistp) {
 169   if (rblistp==NULL)
 170     return(NULL);
 171
 172   return(rb_readlist(rblistp));
 173 }
 174
 175 void rbcloselist(RBLIST *rblistp) {
 176   if (rblistp==NULL)
 177     return;
 178
 179   rb_closelist(rblistp);
 180 }
 181
 182 void * rblookup(const void *low,const void *high, struct rbtree *rbinfo) {
 183   struct rbnode *x;
 184
 185   /* If we have a NULL root (empty tree) then just return NULL */
 186   if (rbinfo==NULL || rbinfo->rb_root==NULL)
 187     return(NULL);
 188
 189   x=rb_lookup(low, high, rbinfo);
 190
 191   return((x==RBNULL) ? NULL : x->object);
 192 }
 193
 194 struct pair rbfind(const void *low,const void *high, struct rbtree *rbinfo) {
 195   struct rbnode *x;
 196   struct pair p;
 197   /* If we have a NULL root (empty tree) then just return NULL */
 198
 199   p.low=NULL;
 200   p.high=NULL;
 201   if (rbinfo==NULL || rbinfo->rb_root==NULL)
 202     return p;
 203
 204   x=rb_lookup(low, high, rbinfo);
 205   if (x!=NULL) {
 206     p.low=x->key;
 207     p.high=x->high;
 208   }
 209   return p;
 210 }
 211
 212
 213 /* --------------------------------------------------------------------- */
 214
 215 /* Search for and if not found and insert is true, will add a new
 216 ** node in. Returns a pointer to the new node, or the node found
 217 */
 218 int rbinsert(const void *key, const void * high, void *object,struct rbtree *rbinfo) {
 219   struct rbnode *x,*y,*z, *tmp;
 220   const void *max;
 221   int found=0;
 222
 223   y=RBNULL; /* points to the parent of x */
 224   x=rbinfo->rb_root;
 225
 226   /* walk x down the tree */
 227   while(x!=RBNULL && found==0) {
 228     y=x;
 229     /* printf("key=%s, x->key=%s\n", key, x->key); */
 230
 231     if (key<x->key)
 232       x=x->left;
 233     else if (key>x->key)
 234       x=x->right;
 235     else
 236       found=1;
 237   }
 238
 239   if (found)
 240     return RB_FALSE;
 241
 242   if ((z=rb_alloc())==NULL) {
 243     /* Whoops, no memory */
 244     return RB_FALSE;
 245   }
 246
 247   z->object=object;
 248   z->high=high;
 249   z->key=key;
 250   z->max=high;
 251   z->up=y;
 252   tmp=y;
 253   max=high;
 254   while(tmp!=RBNULL) {
 255     if (max>tmp->max)
 256       tmp->max=max;
 257     else
 258       max=tmp->max;
 259     tmp=tmp->up;
 260   }
 261
 262   if (y==RBNULL) {
 263       rbinfo->rb_root=z;
 264   } else {
 265     if (z->key<y->key)
 266       y->left=z;
 267     else
 268       y->right=z;
 269   }
 270
 271   z->left=RBNULL;
 272   z->right=RBNULL;
 273
 274   /* colour this new node red */
 275   z->colour=RED;
 276
 277   /* Having added a red node, we must now walk back up the tree balancing
 278   ** it, by a series of rotations and changing of colours
 279   */
 280   x=z;
 281
 282   /* While we are not at the top and our parent node is red
 283   ** N.B. Since the root node is garanteed black, then we
 284   ** are also going to stop if we are the child of the root
 285   */
 286
 287   while(x != rbinfo->rb_root && (x->up->colour == RED)) {
 288     /* if our parent is on the left side of our grandparent */
 289     if (x->up == x->up->up->left) {
 290       /* get the right side of our grandparent (uncle?) */
 291       y=x->up->up->right;
 292       if (y->colour == RED) {
 293         /* make our parent black */
 294         x->up->colour = BLACK;
 295         /* make our uncle black */
 296         y->colour = BLACK;
 297         /* make our grandparent red */
 298         x->up->up->colour = RED;
 299
 300         /* now consider our grandparent */
 301         x=x->up->up;
 302       } else {
 303         /* if we are on the right side of our parent */
 304         if (x == x->up->right) {
 305         /* Move up to our parent */
 306           x=x->up;
 307           rb_left_rotate(&rbinfo->rb_root, x);
 308         }
 309
 310         /* make our parent black */
 311         x->up->colour = BLACK;
 312         /* make our grandparent red */
 313         x->up->up->colour = RED;
 314         /* right rotate our grandparent */
 315         rb_right_rotate(&rbinfo->rb_root, x->up->up);
 316       }
 317     } else {
 318         /* everything here is the same as above, but
 319         ** exchanging left for right
 320         */
 321
 322       y=x->up->up->left;
 323       if (y->colour == RED) {
 324         x->up->colour = BLACK;
 325         y->colour = BLACK;
 326         x->up->up->colour = RED;
 327
 328         x=x->up->up;
 329       } else {
 330         if (x == x->up->left) {
 331           x=x->up;
 332           rb_right_rotate(&rbinfo->rb_root, x);
 333         }
 334
 335         x->up->colour = BLACK;
 336         x->up->up->colour = RED;
 337         rb_left_rotate(&rbinfo->rb_root, x->up->up);
 338       }
 339     }
 340   }
 341
 342   /* Set the root node black */
 343   (rbinfo->rb_root)->colour = BLACK;
 344
 345   return RB_TRUE;
 346 }
 347
 348 /* Search for and if not found and insert is true, will add a new
 349 ** node in. Returns a pointer to the new node, or the node found
 350 */
 351 static struct rbnode * rb_traverse(const void *key, struct rbtree *rbinfo) {
 352   struct rbnode *x,*y,*z;
 353   int found=0;
 354
 355   y=RBNULL; /* points to the parent of x */
 356   x=rbinfo->rb_root;
 357
 358   /* walk x down the tree */
 359   while(x!=RBNULL && found==0) {
 360     y=x;
 361     if (key<x->key)
 362       x=x->left;
 363     else if (key>x->key)
 364       x=x->right;
 365     else
 366       found=1;
 367   }
 368
 369   if (found)
 370     return(x);
 371   return NULL;
 372 }
 373
 374 /* Search for a key according (see redblack.h)
 375 */
 376 static struct rbnode * rb_lookup(const void *low, const void *high, struct rbtree *rbinfo) {
 377   struct rbnode *x;
 378
 379   x=rbinfo->rb_root;
 380
 381   /* walk x down the tree */
 382   while(x!=RBNULL) {
 383     if (low<x->high&&
 384         x->key<high)
 385       return x;
 386     if (x->left!=RBNULL && x->left->max>low)
 387       x=x->left;
 388     else
 389       x=x->right;
 390   }
 391
 392   return(RBNULL);
 393 }
 394
 395 /* Search for a key according (see redblack.h)
 396 */
 397 int rbsearch(const void *low, const void *high, struct rbtree *rbinfo) {
 398   struct rbnode *x;
 399   if (rbinfo==NULL)
 400     return RB_FALSE;
 401
 402   x=rbinfo->rb_root;
 403
 404   /* walk x down the tree */
 405   while(x!=RBNULL) {
 406     if (low<x->high &&
 407         x->key<high)
 408       return RB_TRUE;
 409     if (x->left!=RBNULL && x->left->max>low)
 410       x=x->left;
 411     else
 412       x=x->right;
 413   }
 414
 415   return RB_FALSE;
 416 }
 417
 418 /*
 419  * Destroy all the elements blow us in the tree
 420  * only useful as part of a complete tree destroy.
 421  */
 422 static void rb_destroy(struct rbnode *x,void (*free_function)(void *)) {
 423   if (x!=RBNULL) {
 424     if (x->left!=RBNULL)
 425       rb_destroy(x->left,free_function);
 426     if (x->right!=RBNULL)
 427       rb_destroy(x->right,free_function);
 428     if (free_function!=NULL)
 429       free_function(x->object);
 430     rb_free(x);
 431   }
 432 }
 433
 434 /*
 435 ** Rotate our tree thus:-
 436 **
 437 **             X        rb_left_rotate(X)--->            Y
 438 **           /   \                                     /   \
 439 **          A     Y     <---rb_right_rotate(Y)        X     C
 440 **              /   \                               /   \
 441 **             B     C                             A     B
 442 **
 443 ** N.B. This does not change the ordering.
 444 **
 445 ** We assume that neither X or Y is NULL
 446 */
 447
 448 static void rb_left_rotate(struct rbnode **rootp, struct rbnode *x) {
 449   struct rbnode *y;
 450   const void *max;
 451   assert(x!=RBNULL);
 452   assert(x->right!=RBNULL);
 453
 454   y=x->right; /* set Y */
 455
 456   /* Turn Y's left subtree into X's right subtree (move B)*/
 457   x->right = y->left;
 458
 459   /* If B is not null, set it's parent to be X */
 460   if (y->left != RBNULL)
 461     y->left->up = x;
 462
 463   /* Set Y's parent to be what X's parent was */
 464   y->up = x->up;
 465
 466   /* if X was the root */
 467   if (x->up == RBNULL) {
 468     *rootp=y;
 469   } else {
 470     /* Set X's parent's left or right pointer to be Y */
 471     if (x == x->up->left) {
 472       x->up->left=y;
 473     } else {
 474       x->up->right=y;
 475     }
 476   }
 477
 478   /* Put X on Y's left */
 479   y->left=x;
 480
 481   /* Set X's parent to be Y */
 482   x->up = y;
 483
 484   y->max=x->max; /* compute Y's max */
 485   max=NULL;
 486
 487   if (x->left!=RBNULL)
 488     max=x->left->max;
 489
 490   if (x->right!=RBNULL&&
 491       x->right->max>max)
 492     max=x->right->max;
 493   if (x->high>max)
 494     max=x->high;
 495   x->max=max;
 496 }
 497
 498 static void rb_right_rotate(struct rbnode **rootp, struct rbnode *y) {
 499   struct rbnode *x;
 500   const void *max;
 501
 502   assert(y!=RBNULL);
 503   assert(y->left!=RBNULL);
 504
 505   x=y->left; /* set X */
 506
 507   /* Turn X's right subtree into Y's left subtree (move B) */
 508   y->left = x->right;
 509
 510   /* If B is not null, set it's parent to be Y */
 511   if (x->right != RBNULL)
 512     x->right->up = y;
 513
 514   /* Set X's parent to be what Y's parent was */
 515   x->up = y->up;
 516
 517   /* if Y was the root */
 518   if (y->up == RBNULL) {
 519     *rootp=x;
 520   } else {
 521     /* Set Y's parent's left or right pointer to be X */
 522     if (y == y->up->left) {
 523       y->up->left=x;
 524     } else {
 525       y->up->right=x;
 526     }
 527   }
 528
 529   /* Put Y on X's right */
 530   x->right=y;
 531
 532   /* Set Y's parent to be X */
 533   y->up = x;
 534
 535   x->max=y->max; /* compute Y's max */
 536   max=NULL;
 537
 538   if (y->left!=RBNULL)
 539     max=y->left->max;
 540
 541   if (y->right!=RBNULL&&
 542       y->right->max>max)
 543     max=y->right->max;
 544   if (y->high>max)
 545     max=y->high;
 546   y->max=max;
 547 }
 548
 549 /* Return a pointer to the smallest key greater than x
 550 */
 551 static struct rbnode * rb_successor(const struct rbnode *x) {
 552   struct rbnode *y;
 553
 554   if (x->right!=RBNULL) {
 555     /* If right is not NULL then go right one and
 556     ** then keep going left until we find a node with
 557     ** no left pointer.
 558     */
 559     for (y=x->right; y->left!=RBNULL; y=y->left);
 560   } else {
 561     /* Go up the tree until we get to a node that is on the
 562     ** left of its parent (or the root) and then return the
 563     ** parent.
 564     */
 565     y=x->up;
 566     while(y!=RBNULL && x==y->right) {
 567       x=y;
 568       y=y->up;
 569     }
 570   }
 571   return(y);
 572 }
 573
 574 /* Return a pointer to the largest key smaller than x
 575 */
 576 static struct rbnode * rb_preccessor(const struct rbnode *x) {
 577   struct rbnode *y;
 578
 579   if (x->left!=RBNULL) {
 580     /* If left is not NULL then go left one and
 581     ** then keep going right until we find a node with
 582     ** no right pointer.
 583     */
 584     for (y=x->left; y->right!=RBNULL; y=y->right);
 585   } else {
 586     /* Go up the tree until we get to a node that is on the
 587     ** right of its parent (or the root) and then return the
 588     ** parent.
 589     */
 590     y=x->up;
 591     while(y!=RBNULL && x==y->left) {
 592       x=y;
 593       y=y->up;
 594     }
 595   }
 596   return(y);
 597 }
 598
 599 /* Delete the node z, and free up the space
 600 */
 601 static void rb_delete(struct rbnode **rootp, struct rbnode *z) {
 602   struct rbnode *x, *y, *tmp;
 603   const void *max;
 604
 605   if (z->left == RBNULL || z->right == RBNULL)
 606     y=z;
 607   else
 608     y=rb_successor(z);
 609
 610   if (y->left != RBNULL)
 611     x=y->left;
 612   else
 613     x=y->right;
 614
 615   x->up = y->up;
 616
 617   if (y->up == RBNULL) {
 618     *rootp=x;
 619   } else {
 620     if (y==y->up->left)
 621       y->up->left = x;
 622     else
 623       y->up->right = x;
 624   }
 625
 626   if (y!=z) {
 627     z->key = y->key;
 628     z->high=y->high;
 629     z->object=y->object;
 630   }
 631   tmp=y->up;
 632   while(tmp!=RBNULL) {
 633     max=NULL;
 634     if (tmp->left!=RBNULL)
 635       max=tmp->left->max;
 636     if (tmp->right!=RBNULL&&
 637         tmp->right->max>max)
 638       max=tmp->right->max;
 639     if (tmp->high>max)
 640       max=tmp->high;
 641     tmp->max=max;
 642     tmp=tmp->up;
 643   }
 644   if (y->colour == BLACK)
 645     rb_delete_fix(rootp, x);
 646
 647   rb_free(y);
 648 }
 649
 650 /* Restore the reb-black properties after a delete */
 651 static void rb_delete_fix(struct rbnode **rootp, struct rbnode *x) {
 652   struct rbnode *w;
 653
 654   while (x!=*rootp && x->colour==BLACK) {
 655     if (x==x->up->left) {
 656       w=x->up->right;
 657       if (w->colour==RED) {
 658         w->colour=BLACK;
 659         x->up->colour=RED;
 660         rb_left_rotate(rootp, x->up);
 661         w=x->up->right;
 662       }
 663       if (w->left->colour==BLACK && w->right->colour==BLACK) {
 664         w->colour=RED;
 665         x=x->up;
 666       } else {
 667         if (w->right->colour == BLACK) {
 668           w->left->colour=BLACK;
 669           w->colour=RED;
 670           rb_right_rotate(rootp, w);
 671           w=x->up->right;
 672         }
 673         w->colour=x->up->colour;
 674         x->up->colour = BLACK;
 675         w->right->colour = BLACK;
 676         rb_left_rotate(rootp, x->up);
 677         x=*rootp;
 678       }
 679     } else {
 680       w=x->up->left;
 681       if (w->colour==RED) {
 682         w->colour=BLACK;
 683         x->up->colour=RED;
 684         rb_right_rotate(rootp, x->up);
 685         w=x->up->left;
 686       }
 687       if (w->right->colour==BLACK && w->left->colour==BLACK) {
 688         w->colour=RED;
 689         x=x->up;
 690       } else {
 691         if (w->left->colour == BLACK) {
 692           w->right->colour=BLACK;
 693           w->colour=RED;
 694           rb_left_rotate(rootp, w);
 695           w=x->up->left;
 696         }
 697         w->colour=x->up->colour;
 698         x->up->colour = BLACK;
 699         w->left->colour = BLACK;
 700         rb_right_rotate(rootp, x->up);
 701         x=*rootp;
 702       }
 703     }
 704   }
 705
 706   x->colour=BLACK;
 707 }
 708
 709 static void
 710 rb_walk(const struct rbnode *x, void (*action)(const void *, const VISIT, const int, void *), void *arg, int level) {
 711   if (x==RBNULL)
 712     return;
 713
 714   if (x->left==RBNULL && x->right==RBNULL) {
 715     /* leaf */
 716     (*action)(x->key, leaf, level, arg);
 717   } else {
 718     (*action)(x->key, preorder, level, arg);
 719
 720     rb_walk(x->left, action, arg, level+1);
 721
 722     (*action)(x->key, postorder, level, arg);
 723
 724     rb_walk(x->right, action, arg, level+1);
 725
 726     (*action)(x->key, endorder, level, arg);
 727   }
 728 }
 729
 730 static RBLIST * rb_openlist(const struct rbnode *rootp) {
 731   RBLIST *rblistp;
 732
 733   rblistp=(RBLIST *) malloc(sizeof(RBLIST));
 734   if (!rblistp)
 735     return(NULL);
 736
 737   rblistp->rootp=rootp;
 738   rblistp->nextp=rootp;
 739
 740   if (rootp!=RBNULL) {
 741     while(rblistp->nextp->left!=RBNULL) {
 742       rblistp->nextp=rblistp->nextp->left;
 743     }
 744   }
 745
 746   return(rblistp);
 747 }
 748
 749 static const void * rb_readlist(RBLIST *rblistp) {
 750   const void *key=NULL;
 751
 752   if (rblistp!=NULL && rblistp->nextp!=RBNULL) {
 753     key=rblistp->nextp->key;
 754     rblistp->nextp=rb_successor(rblistp->nextp);
 755   }
 756
 757   return(key);
 758 }
 759
 760 static void rb_closelist(RBLIST *rblistp) {
 761   if (rblistp)
 762     free(rblistp);
 763 }
 764
 765 #if defined(USE_SBRK)
 766 /* Allocate space for our nodes, allowing us to get space from
 767 ** sbrk in larger chucks.
 768 */
 769 static struct rbnode *rbfreep=NULL;
 770
 771 #define RBNODEALLOC_CHUNK_SIZE 1000
 772 static struct rbnode * rb_alloc() {
 773   struct rbnode *x;
 774   int i;
 775
 776   if (rbfreep==NULL) {
 777     /* must grab some more space */
 778     rbfreep=(struct rbnode *) sbrk(sizeof(struct rbnode) * RBNODEALLOC_CHUNK_SIZE);
 779
 780     if (rbfreep==(struct rbnode *) -1) {
 781       return(NULL);
 782     }
 783
 784     /* tie them together in a linked list (use the up pointer) */
 785     for (i=0, x=rbfreep; i<RBNODEALLOC_CHUNK_SIZE-1; i++, x++) {
 786       x->up = (x+1);
 787     }
 788     x->up=NULL;
 789   }
 790
 791   x=rbfreep;
 792   rbfreep = rbfreep->up;
 793   return(x);
 794 }
 795
 796 /* free (dealloc) an rbnode structure - add it onto the front of the list
 797 ** N.B. rbnode need not have been allocated through rb_alloc()
 798 */
 799 static void rb_free(struct rbnode *x) {
 800   x->up=rbfreep;
 801   rbfreep=x;
 802 }
 803
 804 #endif
 805
 806 #if 0
 807 int rb_check(struct rbnode *rootp) {
 808   if (rootp==NULL || rootp==RBNULL)
 809     return(0);
 810
 811   if (rootp->up!=RBNULL) {
 812     fprintf(stderr, "Root up pointer not RBNULL");
 813     dumptree(rootp, 0);
 814     return(1);
 815   }
 816
 817   if (rb_check1(rootp)) {
 818     dumptree(rootp, 0);
 819     return(1);
 820   }
 821
 822   if (count_black(rootp)==-1)
 823     {
 824       dumptree(rootp, 0);
 825       return(-1);
 826     }
 827
 828   return(0);
 829 }
 830
 831 int
 832 rb_check1(struct rbnode *x)
 833 {
 834   if (x->left==NULL || x->right==NULL)
 835     {
 836       fprintf(stderr, "Left or right is NULL");
 837       return(1);
 838     }
 839
 840   if (x->colour==RED)
 841     {
 842       if (x->left->colour!=BLACK && x->right->colour!=BLACK)
 843         {
 844           fprintf(stderr, "Children of red node not both black, x=%ld", x);
 845           return(1);
 846         }
 847     }
 848
 849   if (x->left != RBNULL)
 850     {
 851       if (x->left->up != x)
 852         {
 853           fprintf(stderr, "x->left->up != x, x=%ld", x);
 854           return(1);
 855         }
 856
 857       if (rb_check1(x->left))
 858         return(1);
 859     }
 860
 861   if (x->right != RBNULL)
 862     {
 863       if (x->right->up != x)
 864         {
 865           fprintf(stderr, "x->right->up != x, x=%ld", x);
 866           return(1);
 867         }
 868
 869       if (rb_check1(x->right))
 870         return(1);
 871     }
 872   return(0);
 873 }
 874
 875 count_black(struct rbnode *x)
 876 {
 877   int nleft, nright;
 878
 879   if (x==RBNULL)
 880     return(1);
 881
 882   nleft=count_black(x->left);
 883   nright=count_black(x->right);
 884
 885   if (nleft==-1 || nright==-1)
 886     return(-1);
 887
 888   if (nleft != nright)
 889     {
 890       fprintf(stderr, "Black count not equal on left & right, x=%ld", x);
 891       return(-1);
 892     }
 893
 894   if (x->colour == BLACK)
 895     {
 896       nleft++;
 897     }
 898
 899   return(nleft);
 900 }
 901
 902 dumptree(struct rbnode *x, int n)
 903 {
 904   char *prkey();
 905
 906   if (x!=NULL && x!=RBNULL)
 907     {
 908       n++;
 909       fprintf(stderr, "Tree: %*s %ld: left=%ld, right=%ld, colour=%s, key=%s",
 910               n,
 911               "",
 912               x,
 913               x->left,
 914               x->right,
 915               (x->colour==BLACK) ? "BLACK" : "RED",
 916               prkey(x->key));
 917
 918       dumptree(x->left, n);
 919       dumptree(x->right, n);
 920     }
 921 }
 922 #endif
 923
 924 /*
 925  * $Log: redblack.c,v $
 926  * Revision 1.1  2004/10/28 19:28:59  bdemsky
 927  * Checking in C runtime.
 928  *
 929  * Revision 1.2  2004/03/10 06:15:03  bdemsky
 930  *
 931  *
 932  * Added:
 933  * Concrete Interference rule that falsify a rule that quantifies over a set can't
 934  * remove the last element of the set.
 935  *
 936  * Concrete Interference rule that updates that definitely falsify a rule can't modify
 937  * the inclusion condition causing a possible addition.
 938  *
 939  * Intelligence in the GraphAnalysis package that computes must & cant remove sets.
 940  * Search through only unique combinations.
 941  *
 942  * Revision 1.1  2004/03/07 22:02:43  bdemsky
 943  *
 944  *
 945  * Still buggy, but getting closer...
 946  *
 947  * Revision 1.3  2003/06/18 06:06:18  bdemsky
 948  *
 949  *
 950  * Added option to pass in function to free items in the redblack interval tree.
 951  *
 952  * Revision 1.5  2002/01/30 07:54:53  damo
 953  * Fixed up the libtool versioning stuff (finally)
 954  * Fixed bug 500600 (not detecting a NULL return from malloc)
 955  * Fixed bug 509485 (no longer needs search.h)
 956  * Cleaned up debugging section
 957  * Allow multiple inclusions of redblack.h
 958  * Thanks to Matthias Andree for reporting (and fixing) these
 959  *
 960  * Revision 1.4  2000/06/06 14:43:43  damo
 961  * Added all the rbwalk & rbopenlist stuff. Fixed up malloc instead of sbrk.
 962  * Added two new examples
 963  *
 964  * Revision 1.3  2000/05/24 06:45:27  damo
 965  * Converted everything over to using const
 966  * Added a new example1.c file to demonstrate the worst case scenario
 967  * Minor fixups of the spec file
 968  *
 969  * Revision 1.2  2000/05/24 06:17:10  damo
 970  * Fixed up the License (now the LGPL)
 971  *
 972  * Revision 1.1  2000/05/24 04:15:53  damo
 973  * Initial import of files. Versions are now all over the place. Oh well
 974  *
 975  */
 976