1 /* =============================================================================
4 * -- Red-black balanced binary search tree
6 * =============================================================================
8 * Copyright (C) Sun Microsystems Inc., 2006. All Rights Reserved.
9 * Authors: Dave Dice, Nir Shavit, Ori Shalev.
11 * STM: Transactional Locking for Disjoint Access Parallelism
13 * Transactional Locking II,
14 * Dave Dice, Ori Shalev, Nir Shavit
15 * DISC 2006, Sept 2006, Stockholm, Sweden.
17 * =============================================================================
19 * Modified by Chi Cao Minh
21 * =============================================================================
23 * For the license of bayes/sort.h and bayes/sort.c, please see the header
26 * ------------------------------------------------------------------------
28 * For the license of kmeans, please see kmeans/LICENSE.kmeans
30 * ------------------------------------------------------------------------
32 * For the license of ssca2, please see ssca2/COPYRIGHT
34 * ------------------------------------------------------------------------
36 * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the
37 * header of the files.
39 * ------------------------------------------------------------------------
41 * For the license of lib/rbtree.h and lib/rbtree.c, please see
42 * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree
44 * ------------------------------------------------------------------------
46 * Unless otherwise noted, the following license applies to STAMP files:
48 * Copyright (c) 2007, Stanford University
49 * All rights reserved.
51 * Redistribution and use in source and binary forms, with or without
52 * modification, are permitted provided that the following conditions are
55 * * Redistributions of source code must retain the above copyright
56 * notice, this list of conditions and the following disclaimer.
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
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.
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.
79 * =============================================================================
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;
98 private Node lookup(Object k)
103 int cmp = compare(k,p.k);
107 p = (cmp < 0) ? p.l : p.r;
115 private void rotateLeft(Node x)
128 } else if (xp.l == x) {
138 private void rotateRight(Node x)
150 } else if (xp.r == x) {
162 /* fixAfterInsertion */
163 private void fixAfterInsertion(Node x)
167 while (x != null && x != root) {
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);
178 setColor(parentOf(parentOf(x)),RED);
179 x = parentOf(parentOf(x));
181 if ( x== rightOf(parentOf(x))) {
185 setColor(parentOf(x),BLACK);
186 setColor(parentOf(parentOf(x)),RED);
187 if(parentOf(parentOf(x)) != null) {
188 rotateRight(parentOf(parentOf(x)));
192 Node y = leftOf(parentOf(parentOf(x)));
193 if(colorOf(y) == RED) {
194 setColor(parentOf(x),BLACK);
196 setColor(parentOf(parentOf(x)),RED);
197 x = parentOf(parentOf(x));
199 if (x == leftOf(parentOf(x))) {
203 setColor(parentOf(x),BLACK);
204 setColor(parentOf(parentOf(x)),RED);
205 if (parentOf(parentOf(x)) != null) {
206 rotateLeft(parentOf(parentOf(x)));
218 private Node insert(Object k,Object v,Node n)
225 /* Note: the following STs don't really need to be transactional */
237 int cmp = compare(k,t.k);
240 } else if (cmp < 0) {
251 fixAfterInsertion(n);
254 } else { /* cmp > 0 */
265 fixAfterInsertion(n);
273 private Node successor(Node t)
277 } else if( t.r != null) {
279 while (p.l != null) {
286 while (p != null && ch == p.r) {
295 /* fixAfterDeletion */
296 private void fixAfterDeletion(Node x)
298 while (x != root && colorOf(x) == BLACK) {
299 if ( x == leftOf(parentOf(x))) {
300 Node sib = rightOf(parentOf(x));
301 if (colorOf(sib) == RED) {
303 setColor(parentOf(x),RED);
304 rotateLeft(parentOf(x));
305 sib = rightOf(parentOf(x));
307 if(colorOf(leftOf(sib)) == BLACK &&
308 colorOf(rightOf(sib)) == BLACK) {
312 if(colorOf(rightOf(sib)) == BLACK) {
313 setColor(leftOf(sib),BLACK);
316 sib = rightOf(parentOf(x));
318 setColor(sib,colorOf(parentOf(x)));
319 setColor(parentOf(x),BLACK);
320 setColor(rightOf(sib),BLACK);
321 rotateLeft(parentOf(x));
324 } else { /* symmetric */
325 Node sib = leftOf(parentOf(x));
326 if(colorOf(sib) == RED) {
328 setColor(parentOf(x),RED);
329 rotateRight(parentOf(x));
330 sib = leftOf(parentOf(x));
332 if (colorOf(rightOf(sib)) == BLACK &&
333 colorOf(leftOf(sib)) == BLACK) {
337 if(colorOf(leftOf(sib)) == BLACK) {
338 setColor(rightOf(sib), BLACK);
341 sib = leftOf(parentOf(x));
343 setColor(sib,colorOf(parentOf(x)));
344 setColor(parentOf(x),BLACK);
345 setColor(leftOf(sib),BLACK);
346 rotateRight(parentOf(x));
352 if (x != null && x.c != BLACK) {
357 private Node deleteNode(Node p) {
359 * If strictly internal, copy successor's element to p and then make p
362 if(p.l != null && p.r != null) {
363 Node s = successor(p);
367 } /* p has 2 children */
369 /* Start fixup at replacement node, if it exists */
370 Node replacement = (p.l != null)? p.l : p.r;
372 if (replacement != null) {
373 /* Link replacement to parent */
378 } else if( p == pp.l) {
384 /* Null out links so they are OK to use by fixAfterDeletion */
389 /* Fix replacement */
391 fixAfterDeletion(replacement);
393 } else if(p.p == null) { /* return if we are the only node */
395 } else { /* No children. Use self as phantom replacement and unlink */
403 } else if( p == pp.r) {
419 private Node firstEntry()
423 while ( p.l != null) {
432 private int verifyRedBlack(Node root,int depth)
441 height_left = verifyRedBlack(root.l,depth+1);
442 height_right = verifyRedBlack(root.r,depth+1);
443 if(height_left == 0 || height_right == 0) {
446 if (height_left != height_right) {
447 System.out.println(" Imbalace @depth = " + depth + " : " + height_left + " " + height_right);
450 if (root.l != null && root.l.p != root) {
451 System.out.println(" lineage");
453 if (root.r != null && root.r.p != root) {
454 System.out.println(" lineage");
457 /* Red-Black alternation */
459 if (root.l != null && root.l.c != BLACK) {
460 System.out.println("VERIFY in verifyRedBlack");
464 if (root.r != null && root.r.c != BLACK) {
465 System.out.println("VERIFY in verifyRedBlack");
470 if(root.c != BLACK) {
471 System.out.println("VERIFY in verifyRedBlack");
475 return (height_left + 1);
478 private int compare(Object a,Object b)
481 return compareKeysDefault(a,b);
483 return compareKeysDefault(a,b);
491 /*****************************************
493 *****************************************/
496 /* =============================================================================
498 * =============================================================================
499 long rbtree_verify (rbtree_t* s, long verbose);
501 public int verify(int verbose)
507 System.out.println("Integrity check: ");
510 if (root.p != null) {
511 System.out.println(" (WARNING) root = " + root + " parent = " + root.p);
514 if (root.c != BLACK) {
515 System.out.println(" (WARNING) root = " + root + " color = " + root.c);
518 /* Weak check of binary-tree property */
520 Node its = firstEntry();
521 while (its != null) {
524 if ( child != null && child.p != its) {
525 System.out.println("bad parent");
528 if ( child != null && child.p != its) {
529 System.out.println("Bad parent");
531 Node nxt = successor(its);
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+") ");
543 int vfy = verifyRedBlack(root, 0);
545 System.out.println(" Nodes = " + ctr + " Depth = " + vfy);
552 /* =============================================================================
554 * =============================================================================
555 * rbtree_t* rbtree_alloc (long (*compare)(const void*, const void*));
557 public RBTree(int compID) {
558 this.compID = compID;
562 /* =============================================================================
564 * -- Returns TRUE on success
565 * =============================================================================
566 * bool_t rbtree_insert (rbtree_t* r, void* key, void* val);
568 public boolean insert(Object key,Object val) {
569 Node node = new Node();
570 Node ex = insert(key,val,node);
574 return ((ex == null) ? true : false);
578 /* =============================================================================
580 * =============================================================================
581 * bool_t rbtree_delete (rbtree_t* r, void* key);
583 public boolean deleteNode(Object key) {
588 node = deleteNode(node);
592 return ((node != null) ? true : false);
598 /* =============================================================================
600 * -- Return FALSE if had to insert node first
601 * =============================================================================
602 * bool_t rbtree_update (rbtree_t* r, void* key, void* val);
604 public boolean update(Object key,Object val) {
605 Node nn = new Node();
606 Node ex = insert(key,val,nn);
617 /* =============================================================================
619 * =============================================================================
620 * void* rbtree_get (rbtree_t* r, void* key);
622 public Object get(Object key) {
623 Node n = lookup(key);
633 /* =============================================================================
635 * =============================================================================
636 * bool_t rbtree_contains (rbtree_t* r, void* key);
638 public boolean contains(Object key) {
639 Node n = lookup(key);