Robust/src/Benchmarks/SingleTM/Yada/RBTree.java

   1 /* =============================================================================
   2  *
   3  * rbtree.java
   4  * -- Red-black balanced binary search tree
   5  *
   6  * =============================================================================
   7  *
   8  * Copyright (C) Sun Microsystems Inc., 2006.  All Rights Reserved.
   9  * Authors: Dave Dice, Nir Shavit, Ori Shalev.
  10  *
  11  * STM: Transactional Locking for Disjoint Access Parallelism
  12  *
  13  * Transactional Locking II,
  14  * Dave Dice, Ori Shalev, Nir Shavit
  15  * DISC 2006, Sept 2006, Stockholm, Sweden.
  16  *
  17  * =============================================================================
  18  *
  19  * Modified by Chi Cao Minh
  20  *
  21  * =============================================================================
  22  *
  23  * For the license of bayes/sort.h and bayes/sort.c, please see the header
  24  * of the files.
  25  *
  26  * ------------------------------------------------------------------------
  27  *
  28  * For the license of kmeans, please see kmeans/LICENSE.kmeans
  29  *
  30  * ------------------------------------------------------------------------
  31  *
  32  * For the license of ssca2, please see ssca2/COPYRIGHT
  33  *
  34  * ------------------------------------------------------------------------
  35  *
  36  * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the
  37  * header of the files.
  38  *
  39  * ------------------------------------------------------------------------
  40  *
  41  * For the license of lib/rbtree.h and lib/rbtree.c, please see
  42  * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree
  43  *
  44  * ------------------------------------------------------------------------
  45  *
  46  * Unless otherwise noted, the following license applies to STAMP files:
  47  *
  48  * Copyright (c) 2007, Stanford University
  49  * All rights reserved.
  50  *
  51  * Redistribution and use in source and binary forms, with or without
  52  * modification, are permitted provided that the following conditions are
  53  * met:
  54  *
  55  *     * Redistributions of source code must retain the above copyright
  56  *       notice, this list of conditions and the following disclaimer.
  57  *
  58  *     * Redistributions in binary form must reproduce the above copyright
  59  *       notice, this list of conditions and the following disclaimer in
  60  *       the documentation and/or other materials provided with the
  61  *       distribution.
  62  *
  63  *     * Neither the name of Stanford University nor the names of its
  64  *       contributors may be used to endorse or promote products derived
  65  *       from this software without specific prior written permission.
  66  *
  67  * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
  68  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  69  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  70  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
  71  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  72  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  73  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  74  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  75  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  76  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  77  * THE POSSIBILITY OF SUCH DAMAGE.
  78  *
  79  * =============================================================================
  80  */
  81
  82 #define RED 0
  83 #define BLACK 1
  84 #define parentOf(n) (n!=null? n.p : null)
  85 #define leftOf(n) (n!=null? n.l : null)
  86 #define rightOf(n) (n!=null? n.r : null)
  87 #define colorOf(n) (n!=null? n.c : BLACK)
  88 #define setColor(n, col) if (n!=null) n.c=col;
  89
  90 public class RBTree {
  91     Node root;
  92     int compID;
  93
  94     public RBTree() {}
  95
  96     /* private Methods */
  97     /* lookup */
  98   private Node lookup(Object k)
  99     {
 100         Node p = root;
 101
 102         while(p != null) {
 103             int cmp = compare(k,p.k);
 104             if(cmp == 0) {
 105                 return p;
 106             }
 107             p = (cmp < 0) ? p.l : p.r;
 108         }
 109
 110         return null;
 111     }
 112
 113
 114     /* rotateLeft */
 115     private void rotateLeft(Node x)
 116     {
 117         Node r = x.r;
 118         Node rl = r.l;
 119         x.r = rl;
 120         if(rl != null) {
 121             rl.p = x;
 122         }
 123
 124         Node xp = x.p;
 125         r.p = xp;
 126         if (xp == null) {
 127             root = r;
 128         } else if (xp.l == x) {
 129             xp.l = r;
 130         } else {
 131             xp.r = r;
 132         }
 133         r.l = x;
 134         x.p = r;
 135     }
 136
 137     /* rotateRight */
 138     private void rotateRight(Node x)
 139     {
 140         Node l = x.l;
 141         Node lr = l.r;
 142         x.l = lr;
 143         if (lr != null) {
 144             lr.p = x;
 145         }
 146         Node xp = x.p;
 147         l.p = xp;
 148         if (xp == null) {
 149             root = l;
 150         } else if (xp.r == x) {
 151             xp.r = l;
 152         } else {
 153             xp.l = l;
 154         }
 155
 156         l.r = x;
 157         x.p = l;
 158     }
 159
 160
 161
 162     /* fixAfterInsertion */
 163     private void fixAfterInsertion(Node x)
 164     {
 165         x.c = RED;
 166
 167         while (x != null && x != root) {
 168             Node xp = x.p;
 169             if(xp.c != RED) {
 170                 break;
 171             }
 172
 173             if(parentOf(x) == leftOf(parentOf(parentOf(x)))) {
 174                 Node y = rightOf(parentOf(parentOf(x)));
 175                 if(colorOf(y) == RED) {
 176                     setColor(parentOf(x),BLACK);
 177                     setColor(y,BLACK);
 178                     setColor(parentOf(parentOf(x)),RED);
 179                     x = parentOf(parentOf(x));
 180                 } else {
 181                     if ( x== rightOf(parentOf(x))) {
 182                         x = parentOf(x);
 183                         rotateLeft(x);
 184                     }
 185                     setColor(parentOf(x),BLACK);
 186                     setColor(parentOf(parentOf(x)),RED);
 187                     if(parentOf(parentOf(x)) != null) {
 188                         rotateRight(parentOf(parentOf(x)));
 189                     }
 190                 }
 191             } else {
 192                 Node y = leftOf(parentOf(parentOf(x)));
 193                 if(colorOf(y) == RED) {
 194                     setColor(parentOf(x),BLACK);
 195                     setColor(y,BLACK);
 196                     setColor(parentOf(parentOf(x)),RED);
 197                     x = parentOf(parentOf(x));
 198                 } else {
 199                     if (x == leftOf(parentOf(x))) {
 200                         x = parentOf(x);
 201                         rotateRight(x);
 202                     }
 203                     setColor(parentOf(x),BLACK);
 204                     setColor(parentOf(parentOf(x)),RED);
 205                     if (parentOf(parentOf(x)) != null) {
 206                         rotateLeft(parentOf(parentOf(x)));
 207                     }
 208                 }
 209             }
 210         }
 211
 212         Node ro = root;
 213         if(ro.c != BLACK) {
 214             ro.c = BLACK;
 215         }
 216     }
 217
 218     private Node insert(Object k,Object v,Node n)
 219     {
 220         Node t = root;
 221         if (t== null) {
 222             if (n == null) {
 223                 return null;
 224             }
 225             /* Note: the following STs don't really need to be transactional */
 226             n.l = null;
 227             n.r = null;
 228             n.p = null;
 229             n.k = k;
 230             n.v = v;
 231             n.c = BLACK;
 232             root = n;
 233             return null;
 234         }
 235
 236         while(true) {
 237             int cmp = compare(k,t.k);
 238             if (cmp == 0) {
 239                 return t;
 240             } else if (cmp < 0) {
 241                 Node tl = t.l;
 242                 if (tl != null) {
 243                     t = tl;
 244                 } else {
 245                     n.l = null;
 246                     n.r = null;
 247                     n.k = k;
 248                     n.v = v;
 249                     n.p = t;
 250                     t.l = n;
 251                     fixAfterInsertion(n);
 252                     return null;
 253                 }
 254             } else { /* cmp > 0 */
 255                 Node tr = t.r;
 256                 if (tr != null) {
 257                     t = tr;
 258                 } else {
 259                     n.l = null;
 260                     n.r = null;
 261                     n.k = k;
 262                     n.v = v;
 263                     n.p = t;
 264                     t.r = n;
 265                     fixAfterInsertion(n);
 266                     return null;
 267                 }
 268             }
 269         }
 270     }
 271
 272     /* successor */
 273     private Node successor(Node t)
 274     {
 275         if ( t == null) {
 276             return null;
 277         } else if( t.r != null) {
 278             Node p = t.r;
 279             while (p.l != null) {
 280                 p = p.l;
 281             }
 282             return p;
 283         } else {
 284             Node p = t.p;
 285             Node ch = t;
 286             while (p != null && ch == p.r) {
 287                 ch = p;
 288                 p = p.p;
 289             }
 290             return p;
 291         }
 292
 293     }
 294
 295     /* fixAfterDeletion */
 296     private void fixAfterDeletion(Node x)
 297     {
 298         while (x != root && colorOf(x) == BLACK) {
 299             if ( x == leftOf(parentOf(x))) {
 300                 Node sib = rightOf(parentOf(x));
 301                 if (colorOf(sib) == RED) {
 302                     setColor(sib,BLACK);
 303                     setColor(parentOf(x),RED);
 304                     rotateLeft(parentOf(x));
 305                     sib = rightOf(parentOf(x));
 306                 }
 307                 if(colorOf(leftOf(sib)) == BLACK &&
 308                         colorOf(rightOf(sib)) == BLACK) {
 309                     setColor(sib,RED);
 310                     x = parentOf(x);
 311                 } else {
 312                     if(colorOf(rightOf(sib)) == BLACK) {
 313                         setColor(leftOf(sib),BLACK);
 314                         setColor(sib,RED);
 315                         rotateRight(sib);
 316                         sib = rightOf(parentOf(x));
 317                     }
 318                     setColor(sib,colorOf(parentOf(x)));
 319                     setColor(parentOf(x),BLACK);
 320                     setColor(rightOf(sib),BLACK);
 321                     rotateLeft(parentOf(x));
 322                     x = root;
 323                 }
 324             } else { /* symmetric */
 325                 Node sib = leftOf(parentOf(x));
 326                 if(colorOf(sib) == RED) {
 327                     setColor(sib,BLACK);
 328                     setColor(parentOf(x),RED);
 329                     rotateRight(parentOf(x));
 330                     sib = leftOf(parentOf(x));
 331                 }
 332                 if (colorOf(rightOf(sib)) == BLACK &&
 333                         colorOf(leftOf(sib)) == BLACK) {
 334                     setColor(sib,RED);
 335                     x = parentOf(x);
 336                 } else {
 337                     if(colorOf(leftOf(sib)) == BLACK) {
 338                         setColor(rightOf(sib), BLACK);
 339                         setColor(sib,RED);
 340                         rotateLeft(sib);
 341                         sib = leftOf(parentOf(x));
 342                     }
 343                     setColor(sib,colorOf(parentOf(x)));
 344                     setColor(parentOf(x),BLACK);
 345                     setColor(leftOf(sib),BLACK);
 346                     rotateRight(parentOf(x));
 347                     x = root;
 348                 }
 349             }
 350         }
 351
 352         if (x != null && x.c != BLACK) {
 353             x.c = BLACK;
 354         }
 355     }
 356
 357     private Node deleteNode(Node p) {
 358         /*
 359          * If strictly internal, copy successor's element to p and then make p
 360          * point to successor
 361          */
 362         if(p.l != null && p.r != null) {
 363             Node s = successor(p);
 364             p.k = s.k;
 365             p.v = s.v;
 366             p = s;
 367         } /* p has 2 children */
 368
 369         /* Start fixup at replacement node, if it exists */
 370         Node replacement = (p.l != null)? p.l : p.r;
 371
 372         if (replacement != null) {
 373             /* Link replacement to parent */
 374             replacement.p = p.p;
 375             Node pp = p.p;
 376             if(pp == null) {
 377                 root = replacement;
 378             } else if( p == pp.l) {
 379                 pp.l = replacement;
 380             } else {
 381                 pp.r = replacement;
 382             }
 383
 384             /* Null out links so they are OK to use by fixAfterDeletion */
 385             p.l = null;
 386             p.r = null;
 387             p.p = null;
 388
 389             /* Fix replacement */
 390             if(p.c == BLACK) {
 391                 fixAfterDeletion(replacement);
 392             }
 393         } else if(p.p == null) { /* return if we are the only node */
 394             root = null;
 395         } else { /* No children. Use self as phantom replacement and unlink */
 396             if (p.c == BLACK) {
 397                 fixAfterDeletion(p);
 398             }
 399             Node pp = p.p;
 400             if(pp != null) {
 401                 if( p == pp.l) {
 402                     pp.l = null;
 403                 } else if( p == pp.r) {
 404                     pp.r = null;
 405                 }
 406                 p.p = null;
 407             }
 408         }
 409         return p;
 410     }
 411
 412
 413     /*
 414      * Diagnostic section
 415      */
 416
 417     /* firstEntry */
 418
 419     private Node firstEntry()
 420     {
 421         Node p = root;
 422         if( p != null) {
 423             while ( p.l != null) {
 424                 p = p.l;
 425             }
 426         }
 427         return p;
 428     }
 429
 430     /* verifyRedBlack */
 431
 432     private int verifyRedBlack(Node root,int depth)
 433     {
 434         int height_left;
 435         int height_right;
 436
 437         if ( root == null) {
 438             return 1;
 439         }
 440
 441         height_left = verifyRedBlack(root.l,depth+1);
 442         height_right = verifyRedBlack(root.r,depth+1);
 443         if(height_left == 0 || height_right == 0) {
 444             return 0;
 445         }
 446         if (height_left != height_right) {
 447             System.out.println(" Imbalace @depth = " + depth + " : " + height_left + " " + height_right);
 448         }
 449
 450         if (root.l != null && root.l.p != root) {
 451             System.out.println(" lineage");
 452         }
 453         if (root.r != null && root.r.p != root) {
 454             System.out.println(" lineage");
 455         }
 456
 457         /* Red-Black alternation */
 458         if (root.c == RED) {
 459             if (root.l != null && root.l.c != BLACK) {
 460                 System.out.println("VERIFY in verifyRedBlack");
 461                 return 0;
 462              }
 463
 464             if (root.r != null && root.r.c != BLACK) {
 465                  System.out.println("VERIFY in verifyRedBlack");
 466                  return 0;
 467             }
 468             return height_left;
 469         }
 470         if(root.c != BLACK) {
 471                 System.out.println("VERIFY in verifyRedBlack");
 472                 return 0;
 473         }
 474
 475         return (height_left + 1);
 476     }
 477
 478     private int compare(Object a,Object b)
 479     {
 480         if(compID == 0)
 481             return compareKeysDefault(a,b);
 482         else
 483             return compareKeysDefault(a,b);
 484     }
 485
 486
 487
 488
 489
 490
 491 /*****************************************
 492  * public methods
 493  *****************************************/
 494
 495
 496 /* =============================================================================
 497  * rbtree_verify
 498  * =============================================================================
 499  long rbtree_verify (rbtree_t* s, long verbose);
 500  */
 501     public int verify(int verbose)
 502     {
 503         if ( root == null) {
 504             return 1;
 505         }
 506         if(verbose != 0) {
 507             System.out.println("Integrity check: ");
 508         }
 509
 510         if (root.p != null) {
 511             System.out.println("  (WARNING) root = " + root + " parent = " + root.p);
 512             return -1;
 513         }
 514         if (root.c != BLACK) {
 515             System.out.println("  (WARNING) root = " + root + " color = " + root.c);
 516         }
 517
 518         /* Weak check of binary-tree property */
 519         int ctr = 0;
 520         Node its = firstEntry();
 521         while (its != null) {
 522             ctr++;
 523             Node child = its.l;
 524             if ( child != null && child.p != its) {
 525                 System.out.println("bad parent");
 526             }
 527             child = its.r;
 528             if ( child != null && child.p != its) {
 529                 System.out.println("Bad parent");
 530             }
 531             Node nxt = successor(its);
 532             if (nxt == null) {
 533                 break;
 534             }
 535             if( compare(its.k,nxt.k) >= 0) {
 536                 System.out.println("Key order " + its + " ("+its.k+" "+its.v+") "
 537                                                 + nxt + " ("+nxt.k+" "+nxt.v+") ");
 538                 return -3;
 539             }
 540             its =  nxt;
 541         }
 542
 543         int vfy = verifyRedBlack(root, 0);
 544         if(verbose != 0) {
 545             System.out.println(" Nodes = " + ctr + " Depth = " + vfy);
 546         }
 547
 548         return vfy;
 549
 550     }
 551
 552 /* =============================================================================
 553  * rbtree_alloc
 554  * =============================================================================
 555  * rbtree_t* rbtree_alloc (long (*compare)(const void*, const void*));
 556  */
 557   public RBTree(int compID) {
 558     this.compID = compID;
 559     this.root = null;
 560   }
 561
 562 /* =============================================================================
 563  * rbtree_insert
 564  * -- Returns TRUE on success
 565  * =============================================================================
 566  * bool_t rbtree_insert (rbtree_t* r, void* key, void* val);
 567  */
 568   public boolean insert(Object key,Object val) {
 569     Node node = new Node();
 570     Node ex = insert(key,val,node);
 571     if ( ex != null) {
 572       node = null;
 573     }
 574     return ((ex == null) ? true : false);
 575   }
 576
 577
 578 /* =============================================================================
 579  * rbtree_delete
 580  * =============================================================================
 581  * bool_t rbtree_delete (rbtree_t* r, void* key);
 582  */
 583   public boolean deleteObjNode(Object key)  {
 584         Node node = null;
 585         node = lookup(key);
 586
 587         if(node != null) {
 588             node = deleteNode(node);
 589         }
 590         if(node != null) {
 591         }
 592         return ((node != null) ? true : false);
 593
 594     }
 595
 596
 597
 598 /* =============================================================================
 599  * rbtree_update
 600  * -- Return FALSE if had to insert node first
 601  * =============================================================================
 602  * bool_t rbtree_update (rbtree_t* r, void* key, void* val);
 603  */
 604   public boolean update(Object key,Object val) {
 605     Node nn = new Node();
 606     Node ex = insert(key,val,nn);
 607     if (ex != null) {
 608       ex.v = val;
 609       nn = null;
 610       return true;
 611     }
 612     return false;
 613   }
 614
 615
 616
 617 /* =============================================================================
 618  * rbtree_get
 619  * =============================================================================
 620  * void* rbtree_get (rbtree_t* r, void* key);
 621  */
 622   public Object get(Object key) {
 623     Node n = lookup(key);
 624     if (n != null) {
 625       Object val = n.v;
 626       return val;
 627     }
 628     return null;
 629   }
 630
 631
 632
 633 /* =============================================================================
 634  * rbtree_contains
 635  * =============================================================================
 636  *  bool_t rbtree_contains (rbtree_t* r, void* key);
 637  */
 638   public boolean contains(Object key) {
 639     Node n = lookup(key);
 640     return (n != null);
 641   }
 642 }