From ba49cfb460e9c2bdc840762ae6634d5f0ec7eb52 Mon Sep 17 00:00:00 2001 From: bdemsky Date: Sat, 17 Oct 2009 22:19:02 +0000 Subject: [PATCH] changes --- Robust/src/Benchmarks/SingleTM/Yada/Node.java | 13 + .../src/Benchmarks/SingleTM/Yada/RBTree.java | 642 ++++++++++++++++++ .../src/Benchmarks/SingleTM/Yada/avltree.java | 51 +- Robust/src/Benchmarks/SingleTM/Yada/mesh.java | 21 +- .../src/Benchmarks/SingleTM/Yada/region.java | 20 +- 5 files changed, 721 insertions(+), 26 deletions(-) create mode 100644 Robust/src/Benchmarks/SingleTM/Yada/Node.java create mode 100644 Robust/src/Benchmarks/SingleTM/Yada/RBTree.java diff --git a/Robust/src/Benchmarks/SingleTM/Yada/Node.java b/Robust/src/Benchmarks/SingleTM/Yada/Node.java new file mode 100644 index 00000000..f9387bb2 --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Yada/Node.java @@ -0,0 +1,13 @@ + + +public class Node { + Object k; // key + Object v; // val + Node p; // parent + Node l; // left + Node r; // right + int c; // color + + public Node() {} + +} diff --git a/Robust/src/Benchmarks/SingleTM/Yada/RBTree.java b/Robust/src/Benchmarks/SingleTM/Yada/RBTree.java new file mode 100644 index 00000000..e63e4a2b --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Yada/RBTree.java @@ -0,0 +1,642 @@ +/* ============================================================================= + * + * rbtree.java + * -- Red-black balanced binary search tree + * + * ============================================================================= + * + * Copyright (C) Sun Microsystems Inc., 2006. All Rights Reserved. + * Authors: Dave Dice, Nir Shavit, Ori Shalev. + * + * STM: Transactional Locking for Disjoint Access Parallelism + * + * Transactional Locking II, + * Dave Dice, Ori Shalev, Nir Shavit + * DISC 2006, Sept 2006, Stockholm, Sweden. + * + * ============================================================================= + * + * Modified by Chi Cao Minh + * + * ============================================================================= + * + * For the license of bayes/sort.h and bayes/sort.c, please see the header + * of the files. + * + * ------------------------------------------------------------------------ + * + * For the license of kmeans, please see kmeans/LICENSE.kmeans + * + * ------------------------------------------------------------------------ + * + * For the license of ssca2, please see ssca2/COPYRIGHT + * + * ------------------------------------------------------------------------ + * + * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the + * header of the files. + * + * ------------------------------------------------------------------------ + * + * For the license of lib/rbtree.h and lib/rbtree.c, please see + * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree + * + * ------------------------------------------------------------------------ + * + * Unless otherwise noted, the following license applies to STAMP files: + * + * Copyright (c) 2007, Stanford University + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * * Neither the name of Stanford University nor the names of its + * contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF + * THE POSSIBILITY OF SUCH DAMAGE. + * + * ============================================================================= + */ + +#define RED 0 +#define BLACK 1 +#define parentOf(n) (n!=null? n.p : null) +#define leftOf(n) (n!=null? n.l : null) +#define rightOf(n) (n!=null? n.r : null) +#define colorOf(n) (n!=null? n.c : BLACK) +#define setColor(n, col) if (n!=null) n.c=col; + +public class RBTree { + Node root; + int compID; + + public RBTree() {} + + /* private Methods */ + /* lookup */ + private Node lookup(Object k) + { + Node p = root; + + while(p != null) { + int cmp = compare(k,p.k); + if(cmp == 0) { + return p; + } + p = (cmp < 0) ? p.l : p.r; + } + + return null; + } + + + /* rotateLeft */ + private void rotateLeft(Node x) + { + Node r = x.r; + Node rl = r.l; + x.r = rl; + if(rl != null) { + rl.p = x; + } + + Node xp = x.p; + r.p = xp; + if (xp == null) { + root = r; + } else if (xp.l == x) { + xp.l = r; + } else { + xp.r = r; + } + r.l = x; + x.p = r; + } + + /* rotateRight */ + private void rotateRight(Node x) + { + Node l = x.l; + Node lr = l.r; + x.l = lr; + if (lr != null) { + lr.p = x; + } + Node xp = x.p; + l.p = xp; + if (xp == null) { + root = l; + } else if (xp.r == x) { + xp.r = l; + } else { + xp.l = l; + } + + l.r = x; + x.p = l; + } + + + + /* fixAfterInsertion */ + private void fixAfterInsertion(Node x) + { + x.c = RED; + + while (x != null && x != root) { + Node xp = x.p; + if(xp.c != RED) { + break; + } + + if(parentOf(x) == leftOf(parentOf(parentOf(x)))) { + Node y = rightOf(parentOf(parentOf(x))); + if(colorOf(y) == RED) { + setColor(parentOf(x),BLACK); + setColor(y,BLACK); + setColor(parentOf(parentOf(x)),RED); + x = parentOf(parentOf(x)); + } else { + if ( x== rightOf(parentOf(x))) { + x = parentOf(x); + rotateLeft(x); + } + setColor(parentOf(x),BLACK); + setColor(parentOf(parentOf(x)),RED); + if(parentOf(parentOf(x)) != null) { + rotateRight(parentOf(parentOf(x))); + } + } + } else { + Node y = leftOf(parentOf(parentOf(x))); + if(colorOf(y) == RED) { + setColor(parentOf(x),BLACK); + setColor(y,BLACK); + setColor(parentOf(parentOf(x)),RED); + x = parentOf(parentOf(x)); + } else { + if (x == leftOf(parentOf(x))) { + x = parentOf(x); + rotateRight(x); + } + setColor(parentOf(x),BLACK); + setColor(parentOf(parentOf(x)),RED); + if (parentOf(parentOf(x)) != null) { + rotateLeft(parentOf(parentOf(x))); + } + } + } + } + + Node ro = root; + if(ro.c != BLACK) { + ro.c = BLACK; + } + } + + private Node insert(Object k,Object v,Node n) + { + Node t = root; + if (t== null) { + if (n == null) { + return null; + } + /* Note: the following STs don't really need to be transactional */ + n.l = null; + n.r = null; + n.p = null; + n.k = k; + n.v = v; + n.c = BLACK; + root = n; + return null; + } + + while(true) { + int cmp = compare(k,t.k); + if (cmp == 0) { + return t; + } else if (cmp < 0) { + Node tl = t.l; + if (tl != null) { + t = tl; + } else { + n.l = null; + n.r = null; + n.k = k; + n.v = v; + n.p = t; + t.l = n; + fixAfterInsertion(n); + return null; + } + } else { /* cmp > 0 */ + Node tr = t.r; + if (tr != null) { + t = tr; + } else { + n.l = null; + n.r = null; + n.k = k; + n.v = v; + n.p = t; + t.r = n; + fixAfterInsertion(n); + return null; + } + } + } + } + + /* successor */ + private Node successor(Node t) + { + if ( t == null) { + return null; + } else if( t.r != null) { + Node p = t.r; + while (p.l != null) { + p = p.l; + } + return p; + } else { + Node p = t.p; + Node ch = t; + while (p != null && ch == p.r) { + ch = p; + p = p.p; + } + return p; + } + + } + + /* fixAfterDeletion */ + private void fixAfterDeletion(Node x) + { + while (x != root && colorOf(x) == BLACK) { + if ( x == leftOf(parentOf(x))) { + Node sib = rightOf(parentOf(x)); + if (colorOf(sib) == RED) { + setColor(sib,BLACK); + setColor(parentOf(x),RED); + rotateLeft(parentOf(x)); + sib = rightOf(parentOf(x)); + } + if(colorOf(leftOf(sib)) == BLACK && + colorOf(rightOf(sib)) == BLACK) { + setColor(sib,RED); + x = parentOf(x); + } else { + if(colorOf(rightOf(sib)) == BLACK) { + setColor(leftOf(sib),BLACK); + setColor(sib,RED); + rotateRight(sib); + sib = rightOf(parentOf(x)); + } + setColor(sib,colorOf(parentOf(x))); + setColor(parentOf(x),BLACK); + setColor(rightOf(sib),BLACK); + rotateLeft(parentOf(x)); + x = root; + } + } else { /* symmetric */ + Node sib = leftOf(parentOf(x)); + if(colorOf(sib) == RED) { + setColor(sib,BLACK); + setColor(parentOf(x),RED); + rotateRight(parentOf(x)); + sib = leftOf(parentOf(x)); + } + if (colorOf(rightOf(sib)) == BLACK && + colorOf(leftOf(sib)) == BLACK) { + setColor(sib,RED); + x = parentOf(x); + } else { + if(colorOf(leftOf(sib)) == BLACK) { + setColor(rightOf(sib), BLACK); + setColor(sib,RED); + rotateLeft(sib); + sib = leftOf(parentOf(x)); + } + setColor(sib,colorOf(parentOf(x))); + setColor(parentOf(x),BLACK); + setColor(leftOf(sib),BLACK); + rotateRight(parentOf(x)); + x = root; + } + } + } + + if (x != null && x.c != BLACK) { + x.c = BLACK; + } + } + + private Node deleteNode(Node p) { + /* + * If strictly internal, copy successor's element to p and then make p + * point to successor + */ + if(p.l != null && p.r != null) { + Node s = successor(p); + p.k = s.k; + p.v = s.v; + p = s; + } /* p has 2 children */ + + /* Start fixup at replacement node, if it exists */ + Node replacement = (p.l != null)? p.l : p.r; + + if (replacement != null) { + /* Link replacement to parent */ + replacement.p = p.p; + Node pp = p.p; + if(pp == null) { + root = replacement; + } else if( p == pp.l) { + pp.l = replacement; + } else { + pp.r = replacement; + } + + /* Null out links so they are OK to use by fixAfterDeletion */ + p.l = null; + p.r = null; + p.p = null; + + /* Fix replacement */ + if(p.c == BLACK) { + fixAfterDeletion(replacement); + } + } else if(p.p == null) { /* return if we are the only node */ + root = null; + } else { /* No children. Use self as phantom replacement and unlink */ + if (p.c == BLACK) { + fixAfterDeletion(p); + } + Node pp = p.p; + if(pp != null) { + if( p == pp.l) { + pp.l = null; + } else if( p == pp.r) { + pp.r = null; + } + p.p = null; + } + } + return p; + } + + + /* + * Diagnostic section + */ + + /* firstEntry */ + + private Node firstEntry() + { + Node p = root; + if( p != null) { + while ( p.l != null) { + p = p.l; + } + } + return p; + } + + /* verifyRedBlack */ + + private int verifyRedBlack(Node root,int depth) + { + int height_left; + int height_right; + + if ( root == null) { + return 1; + } + + height_left = verifyRedBlack(root.l,depth+1); + height_right = verifyRedBlack(root.r,depth+1); + if(height_left == 0 || height_right == 0) { + return 0; + } + if (height_left != height_right) { + System.out.println(" Imbalace @depth = " + depth + " : " + height_left + " " + height_right); + } + + if (root.l != null && root.l.p != root) { + System.out.println(" lineage"); + } + if (root.r != null && root.r.p != root) { + System.out.println(" lineage"); + } + + /* Red-Black alternation */ + if (root.c == RED) { + if (root.l != null && root.l.c != BLACK) { + System.out.println("VERIFY in verifyRedBlack"); + return 0; + } + + if (root.r != null && root.r.c != BLACK) { + System.out.println("VERIFY in verifyRedBlack"); + return 0; + } + return height_left; + } + if(root.c != BLACK) { + System.out.println("VERIFY in verifyRedBlack"); + return 0; + } + + return (height_left + 1); + } + + private int compare(Object a,Object b) + { + if(compID == 0) + return compareKeysDefault(a,b); + else + return compareKeysDefault(a,b); + } + + + + + + +/***************************************** + * public methods + *****************************************/ + + +/* ============================================================================= + * rbtree_verify + * ============================================================================= + long rbtree_verify (rbtree_t* s, long verbose); + */ + public int verify(int verbose) + { + if ( root == null) { + return 1; + } + if(verbose != 0) { + System.out.println("Integrity check: "); + } + + if (root.p != null) { + System.out.println(" (WARNING) root = " + root + " parent = " + root.p); + return -1; + } + if (root.c != BLACK) { + System.out.println(" (WARNING) root = " + root + " color = " + root.c); + } + + /* Weak check of binary-tree property */ + int ctr = 0; + Node its = firstEntry(); + while (its != null) { + ctr++; + Node child = its.l; + if ( child != null && child.p != its) { + System.out.println("bad parent"); + } + child = its.r; + if ( child != null && child.p != its) { + System.out.println("Bad parent"); + } + Node nxt = successor(its); + if (nxt == null) { + break; + } + if( compare(its.k,nxt.k) >= 0) { + System.out.println("Key order " + its + " ("+its.k+" "+its.v+") " + + nxt + " ("+nxt.k+" "+nxt.v+") "); + return -3; + } + its = nxt; + } + + int vfy = verifyRedBlack(root, 0); + if(verbose != 0) { + System.out.println(" Nodes = " + ctr + " Depth = " + vfy); + } + + return vfy; + + } + +/* ============================================================================= + * rbtree_alloc + * ============================================================================= + * rbtree_t* rbtree_alloc (long (*compare)(const void*, const void*)); + */ + public RBTree(int compID) { + this.compID = compID; + this.root = null; + } + +/* ============================================================================= + * rbtree_insert + * -- Returns TRUE on success + * ============================================================================= + * bool_t rbtree_insert (rbtree_t* r, void* key, void* val); + */ + public boolean insert(Object key,Object val) { + Node node = new Node(); + Node ex = insert(key,val,node); + if ( ex != null) { + node = null; + } + return ((ex == null) ? true : false); + } + + +/* ============================================================================= + * rbtree_delete + * ============================================================================= + * bool_t rbtree_delete (rbtree_t* r, void* key); + */ + public boolean deleteNode(Object key) { + Node node = null; + node = lookup(key); + + if(node != null) { + node = deleteNode(node); + } + if(node != null) { + } + return ((node != null) ? true : false); + + } + + + +/* ============================================================================= + * rbtree_update + * -- Return FALSE if had to insert node first + * ============================================================================= + * bool_t rbtree_update (rbtree_t* r, void* key, void* val); + */ + public boolean update(Object key,Object val) { + Node nn = new Node(); + Node ex = insert(key,val,nn); + if (ex != null) { + ex.v = val; + nn = null; + return true; + } + return false; + } + + + +/* ============================================================================= + * rbtree_get + * ============================================================================= + * void* rbtree_get (rbtree_t* r, void* key); + */ + public Object get(Object key) { + Node n = lookup(key); + if (n != null) { + Object val = n.v; + return val; + } + return null; + } + + + +/* ============================================================================= + * rbtree_contains + * ============================================================================= + * bool_t rbtree_contains (rbtree_t* r, void* key); + */ + public boolean contains(Object key) { + Node n = lookup(key); + return (n != null); + } +} diff --git a/Robust/src/Benchmarks/SingleTM/Yada/avltree.java b/Robust/src/Benchmarks/SingleTM/Yada/avltree.java index 780265fa..204b51e1 100644 --- a/Robust/src/Benchmarks/SingleTM/Yada/avltree.java +++ b/Robust/src/Benchmarks/SingleTM/Yada/avltree.java @@ -248,16 +248,63 @@ class avltrav { public class avltree { avlnode root; /* Top of the tree */ int size; /* Number of items (user-defined) */ + int mode; + //mode=0 element_mapCompareEdge + //mode=1 element_mapCompare - - public avltree() { + public avltree(int mode) { size = 0; + this.mode=mode; } int cmp(Object a, Object b) { return 0; } + + boolean contains(Object key) { + boolean success = false; + edge searchPair=new edge(); + searchPair.firstPtr = key; + if (map.avlfind(map, searchPair) != null) { + success = true; + } + return success; + } + + Object find(Object key) { + Object dataPtr = null; + edge searchPair=new edge(); + searchPair.firstPtr = key; + edge pairPtr = (edge)map.avlfind(searchPair); + if (pairPtr != null) { + dataPtr = pairPtr.secondPtr; + } + return dataPtr; + } + + boolean insert(Object key, Object data) { + boolean success = false; + edge insertPtr = new edge(key, data); + if (insertPtr != null) { + if (map.insert(insertPtr)) { + success = true; + } + } + return success; + } + + boolean remove(Object key) { + boolean success = false; + edge searchPair=new edge(); + searchPair.firstPtr = key; + edge pairPtr = (edge) map.avlfind(searchPair); + if (map.avlerase(searchPair)) { + success=true; + } + return success; + } + Object avlfind(Object data ) { avlnode it = root; diff --git a/Robust/src/Benchmarks/SingleTM/Yada/mesh.java b/Robust/src/Benchmarks/SingleTM/Yada/mesh.java index 288154d4..b7f4eda2 100644 --- a/Robust/src/Benchmarks/SingleTM/Yada/mesh.java +++ b/Robust/src/Benchmarks/SingleTM/Yada/mesh.java @@ -90,7 +90,7 @@ public class mesh { * TMmesh_insert * ============================================================================= */ - void TMmesh_insert (element elementPtr, MAP_T edgeMapPtr) { + void TMmesh_insert (element elementPtr, avltree edgeMapPtr) { /* * Assuming fully connected graph, we just need to record one element. * The root element is not needed for the actual refining, but rather @@ -198,9 +198,9 @@ boolean TMmesh_removeBoundary(edge boundaryPtr) { */ static void createElement (coordinate coordinates, int numCoordinate, - MAP_T edgeMapPtr) { + avltree edgeMapPtr) { element elementPtr = new element(coordinates, numCoordinate); - yada.Assert(elementPtr); + yada.Assert(elementPtr!=null); if (numCoordinate == 2) { edge boundaryPtr = elementPtr.element_getEdge(0); @@ -238,8 +238,7 @@ int mesh_read(String fileNamePrefix) { int i; int numElement = 0; - MAP_T edgeMapPtr = MAP_ALLOC(NULL, element_mapCompareEdge); - yada.Assert(edgeMapPtr); + avltree edgeMapPtr = new avltree(0); /* * Read .node file @@ -375,9 +374,7 @@ boolean mesh_check(int expectedNumElement) { System.out.println("Checking final mesh:"); Queue_t searchQueuePtr = new Queue_t(-1); - yada.Assert(searchQueuePtr); - MAP_T visitedMapPtr = MAP_ALLOC(NULL, element_mapCompare); - yada.Assert(visitedMapPtr); + avltree visitedMapPtr = new avltree(1); /* * Do breadth-first search starting from rootElementPtr @@ -389,10 +386,10 @@ boolean mesh_check(int expectedNumElement) { List_t neighborListPtr; element currentElementPtr = (element)queue_pop(searchQueuePtr); - if (MAP_CONTAINS(visitedMapPtr, currentElementPtr)) { + if (visitedMapPtr.contains(currentElementPtr)) { continue; } - boolean isSuccess = MAP_INSERT(visitedMapPtr, currentElementPtr, null); + boolean isSuccess = visitedMapPtr.insert(currentElementPtr, null); yada.Assert(isSuccess); if (!currentElementPtr.checkAngles()) { numBadTriangle++; @@ -406,7 +403,7 @@ boolean mesh_check(int expectedNumElement) { /* * Continue breadth-first search */ - if (!MAP_CONTAINS(visitedMapPtr, neighborElementPtr)) { + if (!visitedMapPtr.contains(neighborElementPtr)) { boolean isSuccess = searchQueuePtr.queue_push(neighborElementPtr); yada.Assert(isSuccess); } @@ -419,8 +416,6 @@ boolean mesh_check(int expectedNumElement) { System.out.println("Number of elements = "+ numElement); System.out.println("Number of bad triangles = "+ numBadTriangle); - MAP_FREE(visitedMapPtr); - return (!(numBadTriangle > 0 || numFalseNeighbor > 0 || numElement != expectedNumElement)); diff --git a/Robust/src/Benchmarks/SingleTM/Yada/region.java b/Robust/src/Benchmarks/SingleTM/Yada/region.java index 8ba5dfee..54857bb1 100644 --- a/Robust/src/Benchmarks/SingleTM/Yada/region.java +++ b/Robust/src/Benchmarks/SingleTM/Yada/region.java @@ -106,7 +106,7 @@ public class region { public int TMretriangulate (element elementPtr, region regionPtr, mesh meshPtr, - MAP_T edgeMapPtr) { + avltree edgeMapPtr) { Vector_t badVectorPtr = regionPtr.badVectorPtr; /* private */ List_t beforeListPtr = regionPtr.beforeListPtr; /* private */ List_t borderListPtr = regionPtr.borderListPtr; /* private */ @@ -192,7 +192,7 @@ public class region { element TMgrowRegion(element centerElementPtr, region regionPtr, mesh meshPtr, - MAP_T edgeMapPtr) { + avltree edgeMapPtr) { boolean isBoundary = false; if (centerElementPtr.element_getNumEdge() == 1) { @@ -212,7 +212,7 @@ public class region { expandQueuePtr.queue_push(centerElementPtr); while (!expandQueuePtr.queue_isEmpty()) { - element currentElementPtr = expandQueuePtr.queue_pop(); + element currentElementPtr = (element) expandQueuePtr.queue_pop(); beforeListPtr.insert(currentElementPtr); /* no duplicates */ List_t neighborListPtr = currentElementPtr.element_getNeighborListPtr(); @@ -240,8 +240,8 @@ public class region { TM_RESTART(); } borderListPtr.insert(borderEdgePtr); /* no duplicates */ - if (!MAP_CONTAINS(edgeMapPtr, borderEdgePtr)) { - PMAP_INSERT(edgeMapPtr, borderEdgePtr, neighborElementPtr); + if (!edgeMapPtr.contains(borderEdgePtr)) { + edgeMapPtr.insert(borderEdgePtr, neighborElementPtr); } } } /* not visited before */ @@ -260,20 +260,20 @@ public class region { */ int TMregion_refine(element elementPtr, mesh meshPtr) { int numDelta = 0; - MAP_T edgeMapPtr = null; + avltree edgeMapPtr = null; element encroachElementPtr = null; elementPtr.element_isGarbage(); /* so we can detect conflicts */ while (true) { - edgeMapPtr = PMAP_ALLOC(NULL, element_mapCompareEdge); - yada.Assert(edgeMapPtr); + edgeMapPtr = new avltree(1); + yada.Assert(edgeMapPtr!=null); encroachElementPtr = TMgrowRegion(elementPtr, this, meshPtr, edgeMapPtr); - if (encroachElementPtr) { + if (encroachElementPtr!=null) { encroachElementPtr.element_setIsReferenced(true); numDelta += TMregion_refine(regionPtr, encroachElementPtr, @@ -297,8 +297,6 @@ public class region { edgeMapPtr); } - PMAP_FREE(edgeMapPtr); /* no need to free elements */ - return numDelta; } -- 2.34.1