Repair/RepairInterpreter/redblack.c

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