libtu/rb.c

   1 /*
   2 Generic C code for red-black trees.
   3 Copyright (C) 2000 James S. Plank,
   4               2004 Tuomo Valkonen.
   5
   6 This library is free software; you can redistribute it and/or
   7 modify it under the terms of the GNU Lesser General Public
   8 License as published by the Free Software Foundation; either
   9 version 2.1 of the License, or (at your option) any later version.
  10
  11 This library is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 Lesser General Public License for more details.
  15
  16 You should have received a copy of the GNU Lesser General Public
  17 License along with this library; if not, write to the Free Software
  18 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301 USA
  19  */
  20 /* Revision 1.2.  Jim Plank */
  21
  22 /* Original code by Jim Plank (plank@cs.utk.edu) */
  23 /* modified for THINK C 6.0 for Macintosh by Chris Bartley */
  24
  25 #include <string.h>
  26 #include <stdio.h>
  27 #include <stdlib.h>
  28 #include <ctype.h>
  29 #include "rb.h"
  30
  31 static void mk_new_int(Rb_node l, Rb_node r, Rb_node p, int il);
  32 static Rb_node lprev(Rb_node n);
  33 static Rb_node rprev(Rb_node n);
  34 static void recolor(Rb_node n);
  35 static void single_rotate(Rb_node y, int l);
  36 static void rb_print_tree(Rb_node t, int level);
  37 static void rb_iprint_tree(Rb_node t, int level);
  38
  39 /* Gcc complains if non-char* pointer is passed to printf %p  */
  40 #define DONT_COMPLAIN (char*)
  41
  42 #define isred(n) (n->s.red)
  43 #define isblack(n) (!isred(n))
  44 #define isleft(n) (n->s.left)
  45 #define isright(n) (!isleft(n))
  46 #define isint(n) (n->s.internal)
  47 #define isext(n) (!isint(n))
  48 #define ishead(n) (n->s.head)
  49 #define isroot(n) (n->s.root)
  50 #define setred(n) n->s.red = 1
  51 #define setblack(n) n->s.red = 0
  52 #define setleft(n) n->s.left = 1
  53 #define setright(n) n->s.left = 0
  54 #define sethead(n) n->s.head = 1
  55 #define setroot(n) n->s.root = 1
  56 #define setint(n) n->s.internal = 1
  57 #define setext(n) n->s.internal = 0
  58 #define setnormal(n) { n->s.root = 0; n ->s.head = 0; }
  59 #define sibling(n) ((isleft(n)) ? n->p.parent->c.child.right \
  60                                 : n->p.parent->c.child.left)
  61
  62 static void insert(Rb_node item, Rb_node list)  /* Inserts to the end of a list */
  63 {
  64   Rb_node last_node;
  65
  66   last_node = list->c.list.blink;
  67
  68   list->c.list.blink = item;
  69   last_node->c.list.flink = item;
  70   item->c.list.blink = last_node;
  71   item->c.list.flink = list;
  72 }
  73
  74 static void delete_item(Rb_node item)           /* Deletes an arbitrary iterm */
  75 {
  76   item->c.list.flink->c.list.blink = item->c.list.blink;
  77   item->c.list.blink->c.list.flink = item->c.list.flink;
  78 }
  79
  80 #define mk_new_ext(new, kkkey, vvval) {\
  81   new = (Rb_node) malloc(sizeof(struct rb_node));\
  82   if(new==NULL) return NULL;\
  83   new->v.val = vvval;\
  84   new->k.key = kkkey;\
  85   setext(new);\
  86   setblack(new);\
  87   setnormal(new);\
  88 }
  89
  90 static void mk_new_int(Rb_node l, Rb_node r, Rb_node p, int il)
  91 {
  92   Rb_node newnode;
  93
  94   newnode = (Rb_node) malloc(sizeof(struct rb_node));
  95   setint(newnode);
  96   setred(newnode);
  97   setnormal(newnode);
  98   newnode->c.child.left = l;
  99   newnode->c.child.right = r;
 100   newnode->p.parent = p;
 101   newnode->k.lext = l;
 102   newnode->v.rext = r;
 103   l->p.parent = newnode;
 104   r->p.parent = newnode;
 105   setleft(l);
 106   setright(r);
 107   if (ishead(p)) {
 108     p->p.root = newnode;
 109     setroot(newnode);
 110   } else if (il) {
 111     setleft(newnode);
 112     p->c.child.left = newnode;
 113   } else {
 114     setright(newnode);
 115     p->c.child.right = newnode;
 116   }
 117   recolor(newnode);
 118 }
 119
 120
 121 Rb_node lprev(Rb_node n)
 122 {
 123   if (ishead(n)) return n;
 124   while (!isroot(n)) {
 125     if (isright(n)) return n->p.parent;
 126     n = n->p.parent;
 127   }
 128   return n->p.parent;
 129 }
 130
 131 Rb_node rprev(Rb_node n)
 132 {
 133   if (ishead(n)) return n;
 134   while (!isroot(n)) {
 135     if (isleft(n)) return n->p.parent;
 136     n = n->p.parent;
 137   }
 138   return n->p.parent;
 139 }
 140
 141 Rb_node make_rb()
 142 {
 143   Rb_node head;
 144
 145   head = (Rb_node) malloc (sizeof(struct rb_node));
 146   if(head!=NULL){
 147       head->c.list.flink = head;
 148       head->c.list.blink = head;
 149       head->p.root = head;
 150       head->k.key = "";
 151       sethead(head);
 152   }
 153   return head;
 154 }
 155
 156 Rb_node rb_find_ikey_n(Rb_node n, int ikey, int *fnd)
 157 {
 158   *fnd = 0;
 159   if (!ishead(n)) {
 160     fprintf(stderr, "rb_find_ikey_n called on non-head %p\n",
 161             DONT_COMPLAIN n);
 162     exit(1);
 163   }
 164   if (n->p.root == n) return n;
 165   if (ikey == n->c.list.blink->k.ikey) {
 166     *fnd = 1;
 167     return n->c.list.blink;
 168   }
 169   if (ikey > n->c.list.blink->k.ikey) return n;
 170   else n = n->p.root;
 171   while (1) {
 172     if (isext(n)) return n;
 173     if (ikey == n->k.lext->k.ikey) {
 174       *fnd = 1;
 175       return n->k.lext;
 176     }
 177     n = (ikey < n->k.lext->k.ikey) ? n->c.child.left : n->c.child.right;
 178   }
 179 }
 180
 181 Rb_node rb_find_ikey(Rb_node n, int ikey)
 182 {
 183   int fnd;
 184   return rb_find_ikey_n(n, ikey, &fnd);
 185 }
 186
 187 Rb_node rb_find_gkey_n(Rb_node n, const void *key, Rb_compfn *fxn, int *fnd)
 188 {
 189   int cmp;
 190
 191   *fnd = 0;
 192   if (!ishead(n)) {
 193     fprintf(stderr, "rb_find_gkey_n called on non-head %p\n",
 194             DONT_COMPLAIN n);
 195     exit(1);
 196   }
 197   if (n->p.root == n) return n;
 198   cmp = (*fxn)(key, n->c.list.blink->k.key);
 199   if (cmp == 0) {
 200     *fnd = 1;
 201     return n->c.list.blink;
 202   }
 203   if (cmp > 0) return n;
 204   else n = n->p.root;
 205   while (1) {
 206     if (isext(n)) return n;
 207     cmp = (*fxn)(key, n->k.lext->k.key);
 208     if (cmp == 0) {
 209       *fnd = 1;
 210       return n->k.lext;
 211     }
 212     if (cmp < 0) n = n->c.child.left ; else n = n->c.child.right;
 213   }
 214 }
 215
 216 Rb_node rb_find_gkey(Rb_node n, const void *key, Rb_compfn *fxn)
 217 {
 218   int fnd;
 219   return rb_find_gkey_n(n, key, fxn, &fnd);
 220 }
 221
 222 Rb_node rb_find_key_n(Rb_node n, const char *key, int *fnd)
 223 {
 224   return rb_find_gkey_n(n, key, (Rb_compfn*)strcmp, fnd);
 225 }
 226
 227 Rb_node rb_find_key(Rb_node n, const char *key)
 228 {
 229   int fnd;
 230   return rb_find_gkey_n(n, key, (Rb_compfn*)strcmp, &fnd);
 231 }
 232
 233 static int ptrcmp(const void *a, const void *b)
 234 {
 235     return (a<b ? -1 : ((a==b) ? 0 : 1));
 236 }
 237
 238 Rb_node rb_find_pkey_n(Rb_node n, const void *key, int *fnd)
 239 {
 240   return rb_find_gkey_n(n, key, ptrcmp, fnd);
 241 }
 242
 243 Rb_node rb_find_pkey(Rb_node n, const void *key)
 244 {
 245   int fnd;
 246   return rb_find_gkey_n(n, key, ptrcmp, &fnd);
 247 }
 248
 249 Rb_node rb_insert_b(Rb_node n, const void *key, void *val)
 250 {
 251   Rb_node newleft, newright, newnode, list, p;
 252
 253   if (ishead(n)) {
 254     if (n->p.root == n) {         /* Tree is empty */
 255       mk_new_ext(newnode, key, val);
 256       insert(newnode, n);
 257       n->p.root = newnode;
 258       newnode->p.parent = n;
 259       setroot(newnode);
 260       return newnode;
 261     } else {
 262       mk_new_ext(newright, key, val);
 263       insert(newright, n);
 264       newleft = newright->c.list.blink;
 265       setnormal(newleft);
 266       mk_new_int(newleft, newright, newleft->p.parent, isleft(newleft));
 267       p = rprev(newright);
 268       if (!ishead(p)) p->k.lext = newright;
 269       return newright;
 270     }
 271   } else {
 272     mk_new_ext(newleft, key, val);
 273     insert(newleft, n);
 274     setnormal(n);
 275     mk_new_int(newleft, n, n->p.parent, isleft(n));
 276     p = lprev(newleft);
 277     if (!ishead(p)) p->v.rext = newleft;
 278     return newleft;
 279   }
 280 }
 281
 282 static void recolor(Rb_node n)
 283 {
 284   Rb_node p, gp, s;
 285   int done = 0;
 286
 287   while(!done) {
 288     if (isroot(n)) {
 289       setblack(n);
 290       return;
 291     }
 292
 293     p = n->p.parent;
 294
 295     if (isblack(p)) return;
 296
 297     if (isroot(p)) {
 298       setblack(p);
 299       return;
 300     }
 301
 302     gp = p->p.parent;
 303     s = sibling(p);
 304     if (isred(s)) {
 305       setblack(p);
 306       setred(gp);
 307       setblack(s);
 308       n = gp;
 309     } else {
 310       done = 1;
 311     }
 312   }
 313   /* p's sibling is black, p is red, gp is black */
 314
 315   if ((isleft(n) == 0) == (isleft(p) == 0)) {
 316     single_rotate(gp, isleft(n));
 317     setblack(p);
 318     setred(gp);
 319   } else {
 320     single_rotate(p, isleft(n));
 321     single_rotate(gp, isleft(n));
 322     setblack(n);
 323     setred(gp);
 324   }
 325 }
 326
 327 static void single_rotate(Rb_node y, int l)
 328 {
 329   int rl=0, ir=0;
 330   Rb_node x=NULL, yp=NULL;
 331   void *tmp=NULL;
 332
 333   ir = isroot(y);
 334   yp = y->p.parent;
 335   if (!ir) {
 336     rl = isleft(y);
 337   }
 338
 339   if (l) {
 340     x = y->c.child.left;
 341     y->c.child.left = x->c.child.right;
 342     setleft(y->c.child.left);
 343     y->c.child.left->p.parent = y;
 344     x->c.child.right = y;
 345     setright(y);
 346   } else {
 347     x = y->c.child.right;
 348     y->c.child.right = x->c.child.left;
 349     setright(y->c.child.right);
 350     y->c.child.right->p.parent = y;
 351     x->c.child.left = y;
 352     setleft(y);
 353   }
 354
 355   x->p.parent = yp;
 356   y->p.parent = x;
 357   if (ir) {
 358     yp->p.root = x;
 359     setnormal(y);
 360     setroot(x);
 361   } else {
 362     if (rl) {
 363       yp->c.child.left = x;
 364       setleft(x);
 365     } else {
 366       yp->c.child.right = x;
 367       setright(x);
 368     }
 369   }
 370 }
 371
 372 void rb_delete_node(Rb_node n)
 373 {
 374   Rb_node s, p, gp;
 375   char ir;
 376
 377   if (isint(n)) {
 378     fprintf(stderr, "Cannot delete an internal node: %p\n", DONT_COMPLAIN n);
 379     exit(1);
 380   }
 381   if (ishead(n)) {
 382     fprintf(stderr, "Cannot delete the head of an rb_tree: %p\n", DONT_COMPLAIN n);
 383     exit(1);
 384   }
 385   delete_item(n); /* Delete it from the list */
 386   p = n->p.parent;  /* The only node */
 387   if (isroot(n)) {
 388     p->p.root = p;
 389     free(n);
 390     return;
 391   }
 392   s = sibling(n);    /* The only node after deletion */
 393   if (isroot(p)) {
 394     s->p.parent = p->p.parent;
 395     s->p.parent->p.root = s;
 396     setroot(s);
 397     free(p);
 398     free(n);
 399     return;
 400   }
 401   gp = p->p.parent;  /* Set parent to sibling */
 402   s->p.parent = gp;
 403   if (isleft(p)) {
 404     gp->c.child.left = s;
 405     setleft(s);
 406   } else {
 407     gp->c.child.right = s;
 408     setright(s);
 409   }
 410   ir = isred(p);
 411   free(p);
 412   free(n);
 413
 414   if (isext(s)) {      /* Update proper rext and lext values */
 415     p = lprev(s);
 416     if (!ishead(p)) p->v.rext = s;
 417     p = rprev(s);
 418     if (!ishead(p)) p->k.lext = s;
 419   } else if (isblack(s)) {
 420     fprintf(stderr, "DELETION PROB -- sib is black, internal\n");
 421     exit(1);
 422   } else {
 423     p = lprev(s);
 424     if (!ishead(p)) p->v.rext = s->c.child.left;
 425     p = rprev(s);
 426     if (!ishead(p)) p->k.lext = s->c.child.right;
 427     setblack(s);
 428     return;
 429   }
 430
 431   if (ir) return;
 432
 433   /* Recolor */
 434
 435   n = s;
 436   p = n->p.parent;
 437   s = sibling(n);
 438   while(isblack(p) && isblack(s) && isint(s) &&
 439         isblack(s->c.child.left) && isblack(s->c.child.right)) {
 440     setred(s);
 441     n = p;
 442     if (isroot(n)) return;
 443     p = n->p.parent;
 444     s = sibling(n);
 445   }
 446
 447   if (isblack(p) && isred(s)) {  /* Rotation 2.3b */
 448     single_rotate(p, isright(n));
 449     setred(p);
 450     setblack(s);
 451     s = sibling(n);
 452   }
 453
 454   { Rb_node x, z; char il;
 455
 456     if (isext(s)) {
 457       fprintf(stderr, "DELETION ERROR: sibling not internal\n");
 458       exit(1);
 459     }
 460
 461     il = isleft(n);
 462     x = il ? s->c.child.left : s->c.child.right ;
 463     z = sibling(x);
 464
 465     if (isred(z)) {  /* Rotation 2.3f */
 466       single_rotate(p, !il);
 467       setblack(z);
 468       if (isred(p)) setred(s); else setblack(s);
 469       setblack(p);
 470     } else if (isblack(x)) {   /* Recoloring only (2.3c) */
 471       if (isred(s) || isblack(p)) {
 472         fprintf(stderr, "DELETION ERROR: 2.3c not quite right\n");
 473         exit(1);
 474       }
 475       setblack(p);
 476       setred(s);
 477       return;
 478     } else if (isred(p)) { /* 2.3d */
 479       single_rotate(s, il);
 480       single_rotate(p, !il);
 481       setblack(x);
 482       setred(s);
 483       return;
 484     } else {  /* 2.3e */
 485       single_rotate(s, il);
 486       single_rotate(p, !il);
 487       setblack(x);
 488       return;
 489     }
 490   }
 491 }
 492
 493
 494 void rb_print_tree(Rb_node t, int level)
 495 {
 496   int i;
 497   if (ishead(t) && t->p.parent == t) {
 498     printf("tree %p is empty\n", DONT_COMPLAIN t);
 499   } else if (ishead(t)) {
 500     printf("Head: %p.  Root = %p\n", DONT_COMPLAIN t, DONT_COMPLAIN t->p.root);
 501     rb_print_tree(t->p.root, 0);
 502   } else {
 503     if (isext(t)) {
 504       for (i = 0; i < level; i++) putchar(' ');
 505       printf("Ext node %p: %c,%c: p=%p, k=%s\n",
 506              DONT_COMPLAIN t, isred(t)?'R':'B', isleft(t)?'l':'r',
 507              DONT_COMPLAIN t->p.parent, DONT_COMPLAIN t->k.key);
 508     } else {
 509       rb_print_tree(t->c.child.left, level+2);
 510       rb_print_tree(t->c.child.right, level+2);
 511       for (i = 0; i < level; i++) putchar(' ');
 512       printf("Int node %p: %c,%c: l=%p, r=%p, p=%p, lr=(%s,%s)\n",
 513              DONT_COMPLAIN t, isred(t)?'R':'B', isleft(t)?'l':'r',
 514              DONT_COMPLAIN t->c.child.left, DONT_COMPLAIN t->c.child.right,
 515              DONT_COMPLAIN t->p.parent, DONT_COMPLAIN t->k.lext->k.key,
 516              DONT_COMPLAIN t->v.rext->k.key);
 517     }
 518   }
 519 }
 520
 521 void rb_iprint_tree(Rb_node t, int level)
 522 {
 523   int i;
 524   if (ishead(t) && t->p.parent == t) {
 525     printf("tree %p is empty\n", DONT_COMPLAIN t);
 526   } else if (ishead(t)) {
 527     printf("Head: %p.  Root = %p, < = %p, > = %p\n",
 528            DONT_COMPLAIN t, DONT_COMPLAIN t->p.root,
 529            DONT_COMPLAIN t->c.list.blink,
 530            DONT_COMPLAIN t->c.list.flink);
 531     rb_iprint_tree(t->p.root, 0);
 532   } else {
 533     if (isext(t)) {
 534       for (i = 0; i < level; i++) putchar(' ');
 535       printf("Ext node %p: %c,%c: p=%p, <=%p, >=%p k=%d\n",
 536              DONT_COMPLAIN t, isred(t)?'R':'B', isleft(t)?'l':'r',
 537              DONT_COMPLAIN t->p.parent, DONT_COMPLAIN t->c.list.blink,
 538              DONT_COMPLAIN t->c.list.flink, t->k.ikey);
 539     } else {
 540       rb_iprint_tree(t->c.child.left, level+2);
 541       rb_iprint_tree(t->c.child.right, level+2);
 542       for (i = 0; i < level; i++) putchar(' ');
 543       printf("Int node %p: %c,%c: l=%p, r=%p, p=%p, lr=(%d,%d)\n",
 544              DONT_COMPLAIN t, isred(t)?'R':'B', isleft(t)?'l':'r',
 545              DONT_COMPLAIN t->c.child.left, DONT_COMPLAIN t->c.child.right,
 546              DONT_COMPLAIN t->p.parent, t->k.lext->k.ikey, t->v.rext->k.ikey);
 547     }
 548   }
 549 }
 550
 551 int rb_nblack(Rb_node n)
 552 {
 553   int nb;
 554   if (ishead(n) || isint(n)) {
 555     fprintf(stderr, "ERROR: rb_nblack called on a non-external node %p\n",
 556             DONT_COMPLAIN n);
 557     exit(1);
 558   }
 559   nb = 0;
 560   while(!ishead(n)) {
 561     if (isblack(n)) nb++;
 562     n = n->p.parent;
 563   }
 564   return nb;
 565 }
 566
 567 int rb_plength(Rb_node n)
 568 {
 569   int pl;
 570   if (ishead(n) || isint(n)) {
 571     fprintf(stderr, "ERROR: rb_plength called on a non-external node %p\n",
 572             DONT_COMPLAIN n);
 573     exit(1);
 574   }
 575   pl = 0;
 576   while(!ishead(n)) {
 577     pl++;
 578     n = n->p.parent;
 579   }
 580   return pl;
 581 }
 582
 583 void rb_free_tree(Rb_node n)
 584 {
 585   if (!ishead(n)) {
 586     fprintf(stderr, "ERROR: Rb_free_tree called on a non-head node\n");
 587     exit(1);
 588   }
 589
 590   while(rb_first(n) != rb_nil(n)) {
 591     rb_delete_node(rb_first(n));
 592   }
 593   free(n);
 594 }
 595
 596 void *rb_val(Rb_node n)
 597 {
 598   return n->v.val;
 599 }
 600
 601 Rb_node rb_insert_a(Rb_node nd, const void *key, void *val)
 602 {
 603   return rb_insert_b(nd->c.list.flink, key, val);
 604 }
 605
 606 Rb_node rb_insert(Rb_node tree, const char *key, void *val)
 607 {
 608   return rb_insert_b(rb_find_key(tree, key), key, val);
 609 }
 610
 611 Rb_node rb_inserti(Rb_node tree, int ikey, void *val)
 612 {
 613   return rb_insert_b(rb_find_ikey(tree, ikey), (void *) ikey, val);
 614 }
 615
 616 Rb_node rb_insertg(Rb_node tree, const void *key, void *val, Rb_compfn *func)
 617 {
 618   return rb_insert_b(rb_find_gkey(tree, key, func), key, val);
 619 }
 620
 621 Rb_node rb_insertp(Rb_node tree, const void *key, void *val)
 622 {
 623   return rb_insertg(tree, key, val, ptrcmp);
 624 }
 625
 626