From da4e14cf05994188fdf59adb9415d454c314192a Mon Sep 17 00:00:00 2001 From: bdemsky Date: Fri, 16 Oct 2009 08:51:15 +0000 Subject: [PATCH] beginnings of port...won't compile yet --- .../Benchmarks/SingleTM/Yada/List_Node.java | 10 + .../src/Benchmarks/SingleTM/Yada/List_t.java | 310 +++++++++ .../src/Benchmarks/SingleTM/Yada/Queue_t.java | 298 ++++++++ .../src/Benchmarks/SingleTM/Yada/Random.java | 88 +++ .../Benchmarks/SingleTM/Yada/Vector_t.java | 122 ++++ .../Benchmarks/SingleTM/Yada/coordinate.java | 151 ++++ Robust/src/Benchmarks/SingleTM/Yada/edge.java | 117 ++++ .../src/Benchmarks/SingleTM/Yada/element.java | 656 ++++++++++++++++++ Robust/src/Benchmarks/SingleTM/Yada/mesh.java | 428 ++++++++++++ .../src/Benchmarks/SingleTM/Yada/region.java | 331 +++++++++ Robust/src/Benchmarks/SingleTM/Yada/yada.java | 241 +++++++ 11 files changed, 2752 insertions(+) create mode 100644 Robust/src/Benchmarks/SingleTM/Yada/List_Node.java create mode 100644 Robust/src/Benchmarks/SingleTM/Yada/List_t.java create mode 100644 Robust/src/Benchmarks/SingleTM/Yada/Queue_t.java create mode 100644 Robust/src/Benchmarks/SingleTM/Yada/Random.java create mode 100644 Robust/src/Benchmarks/SingleTM/Yada/Vector_t.java create mode 100644 Robust/src/Benchmarks/SingleTM/Yada/coordinate.java create mode 100644 Robust/src/Benchmarks/SingleTM/Yada/edge.java create mode 100644 Robust/src/Benchmarks/SingleTM/Yada/element.java create mode 100644 Robust/src/Benchmarks/SingleTM/Yada/mesh.java create mode 100644 Robust/src/Benchmarks/SingleTM/Yada/region.java create mode 100644 Robust/src/Benchmarks/SingleTM/Yada/yada.java diff --git a/Robust/src/Benchmarks/SingleTM/Yada/List_Node.java b/Robust/src/Benchmarks/SingleTM/Yada/List_Node.java new file mode 100644 index 00000000..806baa19 --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Yada/List_Node.java @@ -0,0 +1,10 @@ + +public class List_Node { + Object dataPtr; + List_Node nextPtr; + + public List_Node() { + dataPtr = null; + nextPtr = null; + } +} diff --git a/Robust/src/Benchmarks/SingleTM/Yada/List_t.java b/Robust/src/Benchmarks/SingleTM/Yada/List_t.java new file mode 100644 index 00000000..0d6e75d4 --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Yada/List_t.java @@ -0,0 +1,310 @@ +/* ============================================================================= + * + * List_t.java + * -- Sorted singly linked list + * -- Options: duplicate allowed + * (DLIST_NO_DUPLICATES) is no implemented yet (default: allow duplicates) + * + * ============================================================================= + * + * Copyright (C) Stanford University, 2006. All Rights Reserved. + * Author: 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. + * + * ============================================================================= + */ + + +public class List_t { + + public List_Node head; + int size; + + public List_t() { + head = new List_Node(); + } + + + /* ======================================================================= + * allocNode + * -- Returns null on failure + * ======================================================================= + */ + private List_Node allocNode(Object dataPtr) + { + List_Node nodePtr = new List_Node(); + + if(nodePtr == null) { + return null; + } + + nodePtr.dataPtr = dataPtr; + nodePtr.nextPtr = null; + + return nodePtr; + } + + +/* ============================================================================= + * list_alloc + * -- If NULL passed for 'compare' function, will compare data pointer addresses + * -- Returns NULL on failure + * ============================================================================= + * list_t* list_alloc (long (*compare)(const void*, const void*)); + * + * + */ + + public static List_t alloc() + { + List_t listPtr = new List_t(); + + if(listPtr == null) { + return null; + } + + listPtr.head.dataPtr = null; + listPtr.head.nextPtr = null; + listPtr.size = 0; + + return listPtr; + } + +/* ============================================================================= + * list_free + * -- If NULL passed for 'compare' function, will compare data pointer addresses + * -- Returns NULL on failure + * ============================================================================= + * void list_free (list_t* listPtr); + */ + public static void free(List_t listPtr) + { + listPtr = null; + } + +// privae freeList + +/* ============================================================================= + * list_isEmpty + * -- Return TRUE if list is empty, else FALSE + * ============================================================================= + * bool_t list_isEmpty (list_t* listPtr); + */ + public boolean isEmpty() + { + return (head.nextPtr == null); + } + +/* ============================================================================= + * list_getSize + * -- Returns size of list + * ============================================================================= + * long list_getSize (list_t* listPtr); + */ + public int getSize() { + return size; + } + +/* ============================================================================= + * findPrevious + * ============================================================================= + * void* list_find (list_t* listPtr, void* dataPtr); + */ + private List_Node findPrevious(Object dataPtr) + { + List_Node prevPtr = head; + List_Node nodePtr = prevPtr.nextPtr; + + for(; nodePtr != null; nodePtr = nodePtr.nextPtr) { + if (compare(nodePtr.dataPtr,dataPtr) >= 0) { + return prevPtr; + } + prevPtr = nodePtr; + } + + return prevPtr; + } + + /* ============================================================================= + * list_find + * -- Returns NULL if not found, else returns pointer to data + * ============================================================================= + * void* list_find (list_t* listPtr, void* dataPtr); + */ + public Object find(Object dataPtr) { + List_Node nodePtr; + List_Node prevPtr = findPrevious(dataPtr); + + nodePtr = prevPtr.nextPtr; + + if((nodePtr == null) || + (compare(nodePtr.dataPtr,dataPtr) != 0)) { + return null; + } + + return (nodePtr.dataPtr); + } + + public int compare(Object obj1,Object obj2) + { + Reservation_Info aPtr=(Reservation_Info)obj1; + Reservation_Info bPtr=(Reservation_Info)obj2; + int typeDiff; + + typeDiff = aPtr.type - bPtr.type; + + return ((typeDiff != 0) ? (typeDiff) : (aPtr.id - bPtr.id)); + } + +/* ============================================================================= + * list_insert + * -- Return TRUE on success, else FALSE + * ============================================================================= + * bool_t list_insert (list_t* listPtr, void* dataPtr); + */ + public boolean insert(Object dataPtr) { + List_Node prevPtr; + List_Node nodePtr; + List_Node currPtr; + + prevPtr = findPrevious(dataPtr); + currPtr = prevPtr.nextPtr; + + nodePtr = allocNode(dataPtr); + if (nodePtr == null) { + return false; + } + + nodePtr.nextPtr = currPtr; + prevPtr.nextPtr = nodePtr; + size++; + + return true; + } + + +/* ============================================================================= + * list_remove + * -- Returns TRUE if successful, else FALSE + * ============================================================================= + * bool_t list_remove (list_t* listPtr, void* dataPtr); + */ + public boolean remove(Object dataPtr) + { + List_Node prevPtr; + List_Node nodePtr; + + prevPtr = findPrevious(dataPtr); + + nodePtr = prevPtr.nextPtr; + + if((nodePtr != null) && + (compare(nodePtr.dataPtr,dataPtr) == 0)) + { + prevPtr.nextPtr = nodePtr.nextPtr; + nodePtr.nextPtr = null; + nodePtr = null; + size--; + + return true; + } + + return false; + } + + int compareObject(Object obj1,Object obj2) { + return 1; + } + + +/* ============================================================================= + * list_clear + * -- Removes all elements + * ============================================================================= + * void list_clear (list_t* listPtr); + */ + public void clear() { + head = new List_Node(); + size = 0; + } + +/* ============================================================================= + * + * End of list.java + * + * ============================================================================= + */ + + /* Test list */ + + public static void main(String[] argv) { + List_t listPtr; + int[] data1 = new int[5]; + int[] data2 = new int[6]; + + int i; + + System.out.println("Starting..."); + } + +} + + + diff --git a/Robust/src/Benchmarks/SingleTM/Yada/Queue_t.java b/Robust/src/Benchmarks/SingleTM/Yada/Queue_t.java new file mode 100644 index 00000000..c133cb20 --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Yada/Queue_t.java @@ -0,0 +1,298 @@ +/* ============================================================================= + * + * queue.java + * + * ============================================================================= + * + * Copyright (C) Stanford University, 2006. All Rights Reserved. + * Author: Chi Cao Minh + * + * Ported to Java + * Author:Alokika Dash + * University of California, Irvine + * + * ============================================================================= + * + * 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 QUEUE_GROWTH_FACTOR 2 + +public class Queue_t { + int pop; /* points before element to pop */ + int push; + int capacity; + Object[] elements; + + /* ============================================================================= + * queue_alloc + * ============================================================================= + */ + public Queue_t(int initCapacity) { + int capacity = ((initCapacity < 2) ? 2 : initCapacity); + elements = new Object[capacity]; + pop = capacity - 1; + push = 0; + this.capacity = capacity; + } + + + /* ============================================================================= + * Pqueue_alloc + * ============================================================================= + */ + public Queue_t + Pqueue_alloc (int initCapacity) + { + Queue_t queuePtr = new Queue_t(); + + int capacity = ((initCapacity < 2) ? 2 : initCapacity); + queuePtr.elements = new Object[capacity]; + if (queuePtr.elements == null) { + queuePtr = null; + return null; + } + queuePtr.pop = capacity - 1; + queuePtr.push = 0; + queuePtr.capacity = capacity; + + return queuePtr; + } + + /* ============================================================================= + * queue_free + * ============================================================================= + */ + public void queue_free (Queue_t queuePtr) { + queuePtr.elements = null; + queuePtr = null; + } + + + /* ============================================================================= + * Pqueue_free + * ============================================================================= + */ + public void + Pqueue_free (Queue_t queuePtr) + { + queuePtr.elements = null; + queuePtr = null; + } + + + /* ============================================================================= + * TMqueue_free + * ============================================================================= + * + public void + TMqueue_free (TM_ARGDECL Queue* queuePtr) + { + queuePtr.elements = null; + queuePtr = null; + } + +*/ + /* ============================================================================= + * queue_isEmpty + * ============================================================================= + */ + public boolean queue_isEmpty () { + //int pop = queuePtr.pop; + //int push = queuePtr.push; + //int capacity = queuePtr.capacity; + + return (pop + 1) % capacity == push; + } + + + /* ============================================================================= + * queue_clear + * ============================================================================= + */ + public void + queue_clear () + { + pop = capacity - 1; + push = 0; + } + + + /* ============================================================================= + * TMqueue_isEmpty + * ============================================================================= + */ + + + + /* ============================================================================= + * queue_push + * ============================================================================= + */ + public boolean queue_push (Object dataPtr) { + if(pop == push) { + + System.out.println("push == pop in Queue.java"); + return false; + } + + + /* Need to resize */ + int newPush = (push + 1) % capacity; + if (newPush == pop) { + + int newCapacity = capacity * QUEUE_GROWTH_FACTOR; + Object[] newElements = new Object[newCapacity]; + if (newElements == null) { + return false; + } + + int dst = 0; + Object[] tmpelements = elements; + if (pop < push) { + int src; + for (src = (pop + 1); src < push; src++, dst++) { + newElements[dst] = elements[src]; + } + } else { + int src; + for (src = (pop + 1); src < capacity; src++, dst++) { + newElements[dst] = elements[src]; + } + for (src = 0; src < push; src++, dst++) { + newElements[dst] = elements[src]; + } + } + + //elements = null; + elements = newElements; + pop = newCapacity - 1; + capacity = newCapacity; + push = dst; + newPush = push + 1; /* no need modulo */ + } + + elements[push] = dataPtr; + push = newPush; + + return true; + } + + + /* ============================================================================= + * Pqueue_push + * ============================================================================= + */ + public boolean + Pqueue_push (Queue_t queuePtr, Object dataPtr) + { + int pop = queuePtr.pop; + int push = queuePtr.push; + int capacity = queuePtr.capacity; + + if(pop == push) { + System.out.println("push == pop in Queue.java"); + return false; + } + + /* Need to resize */ + int newPush = (push + 1) % capacity; + if (newPush == pop) { + + int newCapacity = capacity * QUEUE_GROWTH_FACTOR; + Object[] newElements = new Object[newCapacity]; + if (newElements == null) { + return false; + } + + int dst = 0; + Object[] elements = queuePtr.elements; + if (pop < push) { + int src; + for (src = (pop + 1); src < push; src++, dst++) { + newElements[dst] = elements[src]; + } + } else { + int src; + for (src = (pop + 1); src < capacity; src++, dst++) { + newElements[dst] = elements[src]; + } + for (src = 0; src < push; src++, dst++) { + newElements[dst] = elements[src]; + } + } + + elements = null; + queuePtr.elements = newElements; + queuePtr.pop = newCapacity - 1; + queuePtr.capacity = newCapacity; + push = dst; + newPush = push + 1; /* no need modulo */ + + } + + queuePtr.elements[push] = dataPtr; + queuePtr.push = newPush; + + return true; + } + + /* ============================================================================= + * queue_pop + * ============================================================================= + */ + public Object queue_pop () { + int newPop = (pop + 1) % capacity; + if (newPop == push) { + return null; + } + + //Object dataPtr = queuePtr.elements[newPop]; + //queuePtr.pop = newPop; + Object dataPtr = elements[newPop]; + pop = newPop; + + return dataPtr; + } + + +} +/* ============================================================================= + * + * End of queue.java + * + * ============================================================================= + */ diff --git a/Robust/src/Benchmarks/SingleTM/Yada/Random.java b/Robust/src/Benchmarks/SingleTM/Yada/Random.java new file mode 100644 index 00000000..e402d775 --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Yada/Random.java @@ -0,0 +1,88 @@ +public class Random { + long[] mt; + int mti; + int RANDOM_DEFAULT_SEED; + /* period parameter */ + + + public Random() { + RANDOM_DEFAULT_SEED = 0; + mt = new long[624]; + } + + public void random_alloc() { + init_genrand(this.RANDOM_DEFAULT_SEED); + } + + /* initializes mt[N] with a seed */ + public void init_genrand(int s) { + mt[0]= ((long)s) & 0xFFFFFFFFL; + for (int mti=1; mti<624; mti++) { + mt[mti] = (1812433253L * (mt[mti-1] ^ (mt[mti-1] >> 30)) + ((long)mti)); + /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */ + /* In the previous versions, MSBs of the seed affect */ + /* only MSBs of the array mt[]. */ + /* 2002/01/09 modified by Makoto Matsumoto */ + mt[mti] &= 0xFFFFFFFFL; + /* for >32 bit machines */ + } + this.mti=624; + } + + public void random_seed(int seed) { + init_genrand(seed); + } + + public long random_generate() { + long x= genrand_int32()&0xFFFFFFFFL; + System.out.println(x); + return x; + } + + public long posrandom_generate() { + long r=genrand_int32(); + if (r>0) + return r; + else + return -r; + } + + public long genrand_int32() { + long y; + int mti = this.mti; + long[] mt = this.mt; + + if (mti >= 624) { /* generate N words at one time */ + int kk; + + if (mti == 624+1) { /* if init_genrand() has not been called, */ + init_genrand(5489); /* a default initial seed is used */ + mti=this.mti; + } + for (kk=0;kk<(624-397);kk++) { + y = (mt[kk]&0x80000000L)|(mt[kk+1]&0x7fffffffL); + mt[kk] = mt[kk+397] ^ (y >> 1) ^ ((y & 0x1)==0 ? 0L:0x9908b0dfL); + } + for (;kk<(624-1);kk++) { + y = (mt[kk]&0x80000000L)|(mt[kk+1]&0x7fffffffL); + mt[kk] = mt[kk+(397-624)] ^ (y >> 1) ^ ((y & 0x1)==0 ? 0L:0x9908b0dfL); + } + y = (mt[624-1]&0x80000000L)|(mt[0]&0x7fffffffL); + mt[624-1] = mt[397-1] ^ (y >> 1) ^ ((y & 0x1)==0 ? 0L:0x9908b0dfL); + + mti = 0; + } + + y = mt[mti++]; + + /* Tempering */ + y ^= (y >> 11); + y ^= (y << 7) & 0x9d2c5680L; + y ^= (y << 15) & 0xefc60000L; + y ^= (y >> 18); + + this.mti = mti; + + return y; + } +} diff --git a/Robust/src/Benchmarks/SingleTM/Yada/Vector_t.java b/Robust/src/Benchmarks/SingleTM/Yada/Vector_t.java new file mode 100644 index 00000000..cb0c9f30 --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Yada/Vector_t.java @@ -0,0 +1,122 @@ +public class Vector_t { + int size; + int capacity; + Object[] elements; +// QuickSort qsort; + + public Vector_t() { +// qsort = new QuickSort(); + } + + /* ============================================================================= + * Vector_alloc + * -- Returns null if failed + * ============================================================================= + */ + public Vector_t(int initCapacity) { + int capacity = Math.imax(initCapacity, 1); + size=0; + this.capacity = capacity; + this.elements = new Object[capacity]; + } + + /* ============================================================================= + * Vector_at + * -- Returns null if failed + * ============================================================================= + */ + public Object vector_at(int i) { + if ((i < 0) || (i >= size)) { + System.out.println("Illegal Vector.element\n"); + return null; + } + return elements[i]; + } + + + /* ============================================================================= + * Vector_pushBack + * -- Returns false if fail, else true + * ============================================================================= + */ + public boolean vector_pushBack(Object dataPtr) { + if (size == capacity) { + int newCapacity = capacity * 2; + Object[] newElements = new Object[newCapacity]; + + capacity = newCapacity; + for (int i = 0; i < size; i++) { + newElements[i] = elements[i]; + } + elements = null; + elements = newElements; + } + + elements[size++] = dataPtr; + + return true; + } + + /* ============================================================================= + * Vector_popBack + * -- Returns null if fail, else returns last element + * ============================================================================= + */ + public Object vector_popBack() { + if (size < 1) { + return null; + } + + return elements[--size]; + } + + /* ============================================================================= + * Vector_getSize + * ============================================================================= + */ + public int vector_getSize() { + return size; + } + + /* ============================================================================= + * Vector_clear + * ============================================================================= + */ + public void vector_clear() { + size = 0; + } + + /* ============================================================================= + * Vector_sort + * ============================================================================= + * + public void + vector_sort () + { + //qsort.sort(elements, 0, (elements.length - 1)); + qsort.sort(elements); + //qsort(elements, size, 4, compare); + } + + * ============================================================================= + * Vector_copy + * ============================================================================= + */ + public static boolean vector_copy (Vector_t dstVectorPtr, Vector_t srcVectorPtr) { + int dstCapacity = dstVectorPtr.capacity; + int srcSize = srcVectorPtr.size; + if (dstCapacity < srcSize) { + int srcCapacity = srcVectorPtr.capacity; + Object[] elements = new Object[srcCapacity]; + dstVectorPtr.elements = null; + dstVectorPtr.elements = elements; + dstVectorPtr.capacity = srcCapacity; + } + for(int i = 0; i< srcSize; i++) { + dstVectorPtr.elements[i] = srcVectorPtr.elements[i]; + } + + dstVectorPtr.size = srcSize; + return true; + } +} diff --git a/Robust/src/Benchmarks/SingleTM/Yada/coordinate.java b/Robust/src/Benchmarks/SingleTM/Yada/coordinate.java new file mode 100644 index 00000000..e4b329ec --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Yada/coordinate.java @@ -0,0 +1,151 @@ +/* ============================================================================= + * + * coordinate.c + * + * ============================================================================= + * + * Copyright (C) Stanford University, 2006. All Rights Reserved. + * Author: 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. + * + * ============================================================================= + */ + +public class coordinate { + static int coordinate_compare (coordinate aPtr, coordinate bPtr) { + if (aPtr.x < bPtr.x) { + return -1; + } else if (aPtr.x > bPtr.x) { + return 1; + } else if (aPtr.y < bPtr.y) { + return -1; + } else if (aPt.>y > bPtr.y) { + return 1; + } + return 0; + } + + +/* ============================================================================= + * coordinate_distance + * ============================================================================= + */ + static double coordinate_distance (coordinate coordinatePtr, coordinate aPtr) { + double delta_x = coordinatePtr.x - aPtr.x; + double delta_y = coordinatePtr.y - aPtr.y; + + return Math.sqrt((delta_x * delta_x) + (delta_y * delta_y)); + } + + +/* ============================================================================= + * coordinate_angle + * + * (b - a) .* (c - a) + * cos a = --------------------- + * ||b - a|| * ||c - a|| + * + * ============================================================================= + */ + static double coordinate_angle(coordinate aPtr, coordinate bPtr, coordinate cPtr) { + double delta_b_x; + double delta_b_y; + double delta_c_x; + double delta_c_y; + double distance_b; + double distance_c; + double numerator; + double denominator; + double cosine; + double radian; + + delta_b_x = bPtr.x - aPtr.x; + delta_b_y = bPtr.y - aPtr.y; + + delta_c_x = cPtr.x - aPtr.x; + delta_c_y = cPtr.y - aPtr.y; + + numerator = (delta_b_x * delta_c_x) + (delta_b_y * delta_c_y); + + distance_b = coordinate_distance(aPtr, bPtr); + distance_c = coordinate_distance(aPtr, cPtr); + denominator = distance_b * distance_c; + + cosine = numerator / denominator; + radian = Math.acos(cosine); + + return (180.0 * radian / 3.141592653589793238462643); +} + + +/* ============================================================================= + * coordinate_print + * ============================================================================= + */ + void coordinate_print() { + System.out.println("("+x+", "+y+")"); + } +} +/* ============================================================================= + * + * End of coordinate.c + * + * ============================================================================= + */ diff --git a/Robust/src/Benchmarks/SingleTM/Yada/edge.java b/Robust/src/Benchmarks/SingleTM/Yada/edge.java new file mode 100644 index 00000000..65359c3c --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Yada/edge.java @@ -0,0 +1,117 @@ +/* ============================================================================= + * + * Pair.java + * + * ============================================================================= + * + * Copyright (C) Stanford University, 2006. All Rights Reserved. + * Author: Chi Cao Minh + * + * Ported to Java + * + * + * ============================================================================= + * + * 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. + * + * ============================================================================= + */ + +import java.util.*; + +public class edge { + public Object first; + public Object second; + + public edge() { + first = null; + second = null; + } + + + /* ============================================================================= + * + * pair constructor + * + * pair_t* pair_alloc(void* firstPtr, void* secondPtr); + * ============================================================================= + */ + public edge(Object first,Object second) { + this.first = first; + this.second = second; + } + + + /* ============================================================================= + * pair_swap + * -- Exchange 'firstPtr' and 'secondPtr' + * ============================================================================= + * void pair_swap (pair_t* pairPtr); + */ + public void swap() { + Object tmpPtr = first; + first=second; + second=tmpPtr; + } +} + +/* ============================================================================= + * + * End of pair.java + * + * ============================================================================= + */ diff --git a/Robust/src/Benchmarks/SingleTM/Yada/element.java b/Robust/src/Benchmarks/SingleTM/Yada/element.java new file mode 100644 index 00000000..a7dc9067 --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Yada/element.java @@ -0,0 +1,656 @@ +/* ============================================================================= + * + * element.c + * + * ============================================================================= + * + * Copyright (C) Stanford University, 2006. All Rights Reserved. + * Author: 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. + * + * ============================================================================= + */ + +public class element { + coordinate coordinates[]; + int numCoordinate; + coordinate_t circumCenter; + double circumRadius; + double minAngle; + edge edges[3]; + int numEdge; + coordinate_t midpoints[3]; /* midpoint of each edge */ + double radii[3]; /* half of edge length */ + edge encroachedEdgePtr; /* opposite obtuse angle */ + boolean isSkinny; + list_t neighborListPtr; + boolean isGarbage; + boolean isReferenced; + + + extern double global_angleConstraint; + + + +/* ============================================================================= + * minimizeCoordinates + * -- put smallest coordinate in position 0 + * ============================================================================= + */ + static void minimizeCoordinates (element elementPtr) { + coordinate[] coordinates = elementPtr.coordinates; + int numCoordinate = elementPtr.numCoordinate; + int minPosition = 0; + + for (int i = 1; i < numCoordinate; i++) { + if (coordinate_compare(coordinates[i], coordinates[minPosition]) < 0) { + minPosition = i; + } + } + + while(minPosition != 0) { + coordinate tmp = coordinates[0]; + for (int j = 0; j < (numCoordinate - 1); j++) { + coordinates[j] = coordinates[j+1]; + } + coordinates[numCoordinate-1] = tmp; + minPosition--; + } + } + + +/* ============================================================================= + * checkAngles + * -- Sets isSkinny to TRUE if the angle constraint is not met + * ============================================================================= + */ + void checkAngles () { + double angleConstraint = global_angleConstraint; + minAngle = 180.0; + + assert(numCoordinate == 2 || numCoordinate == 3); + isReferenced = false; + isSkinny = false; + encroachedEdgePtr = null; + + if (numCoordinate == 3) { + int i; + for (i = 0; i < 3; i++) { + double angle = coordinate_angle(coordinates[i], + coordinates[(i + 1) % 3], + coordinates[(i + 2) % 3]); + assert(angle > 0.0); + assert(angle < 180.0); + if (angle > 90.0) { + encroachedEdgePtr = edges[(i + 1) % 3]; + } + if (angle < angleConstraint) { + isSkinny = true; + } + if (angle < minAngle) { + minAngle = angle; + } + } + assert(minAngle < 180.0); + } +} + + +/* ============================================================================= + * calculateCircumCenter + * + * Given three points A(ax,ay), B(bx,by), C(cx,cy), circumcenter R(rx,ry): + * + * | | + * | by - ay (||b - a||)^2 | + * | | + * | cy - ay (||c - a||)^2 | + * | | + * rx = ax - ----------------------------- + * | | + * | bx - ax by - ay | + * 2 * | | + * | cx - ax cy - ay | + * | | + * + * | | + * | bx - ax (||b - a||)^2 | + * | | + * | cx - ax (||c - a||)^2 | + * | | + * ry = ay + ----------------------------- + * | | + * | bx - ax by - ay | + * 2 * | | + * | cx - ax cy - ay | + * | | + * + * ============================================================================= + */ + void calculateCircumCircle() { + coordinate circumCenterPtr = this.circumCenter; + + assert(numCoordinate == 2 || numCoordinate == 3); + + if (numCoordinate == 2) { + circumCenterPtr.x = (coordinates[0].x + coordinates[1].x) / 2.0; + circumCenterPtr.y = (coordinates[0].y + coordinates[1].y) / 2.0; + } else { + double ax = coordinates[0].x; + double ay = coordinates[0].y; + double bx = coordinates[1].x; + double by = coordinates[1].y; + double cx = coordinates[2].x; + double cy = coordinates[2].y; + double bxDelta = bx - ax; + double byDelta = by - ay; + double cxDelta = cx - ax; + double cyDelta = cy - ay; + double bDistance2 = (bxDelta * bxDelta) + (byDelta * byDelta); + double cDistance2 = (cxDelta * cxDelta) + (cyDelta * cyDelta); + double xNumerator = (byDelta * cDistance2) - (cyDelta * bDistance2); + double yNumerator = (bxDelta * cDistance2) - (cxDelta * bDistance2); + double denominator = 2 * ((bxDelta * cyDelta) - (cxDelta * byDelta)); + double rx = ax - (xNumerator / denominator); + double ry = ay + (yNumerator / denominator); + assert(fabs(denominator) > DBL_MIN); /* make sure not colinear */ + circumCenterPtr.x = rx; + circumCenterPtr.y = ry; + } + + elementPtr.circumRadius = coordinate_distance(circumCenterPtr, + coordinates[0]); + } + + +/* ============================================================================= + * setEdge + * + * Note: Makes pairPtr sorted; i.e., coordinate_compare(first, second) < 0 + * ============================================================================= + */ + publicvoid setEdge(int i) { + coordinate firstPtr = coordinates[i]; + coordinate secondPtr = coordinates[(i + 1) % numCoordinate]; + + edge edgePtr = edges[i]; + int cmp = coordinate_compare(firstPtr, secondPtr); + assert(cmp != 0); + if (cmp < 0) { + edgePtr.firstPtr = firstPtr; + edgePtr.secondPtr = secondPtr; + } else { + edgePtr.firstPtr = secondPtr; + edgePtr.secondPtr = firstPtr; + } + + coordinate midpointPtr = elementPtr.midpoints[i]; + midpointPtr.x = (firstPtr.x + secondPtr.x) / 2.0; + midpointPtr.y = (firstPtr.y + secondPtr.y) / 2.0; + + elementPtr.radii[i] = coordinate_distance(firstPtr, midpointPtr); + } + + +/* ============================================================================= + * initEdges + * ============================================================================= + */ + void initEdges(coordinate coordinates, int numCoordinate) { + numEdge = ((numCoordinate * (numCoordinate - 1)) / 2); + + for (int e = 0; e < numEdge; e++) { + setEdge(e); + } + } + + +/* ============================================================================= + * element_compare + * ============================================================================= + */ +int element_compare (element aElementPtr, element bElementPtr) { + int aNumCoordinate = aElementPtr.numCoordinate; + int bNumCoordinate = bElementPtr.numCoordinate; + coordinate aCoordinates = aElementPtr.coordinates; + coordinate bCoordinates = bElementPtr.coordinates; + + if (aNumCoordinate < bNumCoordinate) { + return -1; + } else if (aNumCoordinate > bNumCoordinate) { + return 1; + } + + for (int i = 0; i < aNumCoordinate; i++) { + int compareCoordinate = + coordinate_compare(aCoordinates[i], bCoordinates[i]); + if (compareCoordinate != 0) { + return compareCoordinate; + } + } + + return 0; +} + + +/* ============================================================================= + * element_listCompare + * + * For use in list_t + * ============================================================================= + */ + int element_listCompare (const void* aPtr, const void* bPtr) { + element_t* aElementPtr = (element_t*)aPtr; + element_t* bElementPtr = (element_t*)bPtr; + + return element_compare(aElementPtr, bElementPtr); + } + + +/* ============================================================================= + * element_mapCompare + * + * For use in MAP_T + * ============================================================================= + */ + int element_mapCompare (const pair_t* aPtr, const pair_t* bPtr) { + element_t* aElementPtr = (element_t*)(aPtr->firstPtr); + element_t* bElementPtr = (element_t*)(bPtr->firstPtr); + + return element_compare(aElementPtr, bElementPtr); + } + + + /* ============================================================================= + * TMelement_alloc + * + * Contains a copy of input arg 'coordinates' + * ============================================================================= + */ + public element(coordinate[] coordinates, int numCoordinate) { + this.coordinates=new coordinate[3]; + for (int i = 0; i < numCoordinate; i++) { + this.coordinates[i] = coordinates[i]; + } + this.numCoordinate = numCoordinate; + minimizeCoordinates(); + checkAngles(); + calculateCircumCircle(); + initEdges(coordinates, numCoordinate); + neighborListPtr = TMLIST_ALLOC(element_listCompare); + isGarbage = false; + isReferenced = false; + } + + +/* ============================================================================= + * element_getNumEdge + * ============================================================================= + */ + int element_getNumEdge() { + return numEdge; + } + + +/* ============================================================================= + * element_getEdge + * + * Returned edgePtr is sorted; i.e., coordinate_compare(first, second) < 0 + * ============================================================================= + */ + edge element_getEdge(int i) { + if (i < 0 || i > numEdge) + return null; + return edges[i]; + } + + +/* ============================================================================= + * element_compareEdge + * ============================================================================= + */ + static int compareEdge(edge aEdgePtr, edge bEdgePtr) { + int diffFirst = coordinate_compare((coordinate_t*)aEdgePtr.firstPtr, + (coordinate_t*)bEdgePtr.firstPtr); + + return ((diffFirst != 0) ? + (diffFirst) : + (coordinate_compare((coordinate)aEdgePtr.secondPtr, + (coordinate)bEdgePtr.secondPtr))); + } + + +/* ============================================================================ + * element_listCompareEdge + * + * For use in list_t + * ============================================================================ + */ + int element_listCompareEdge (const void* aPtr, const void* bPtr) { + edge_t* aEdgePtr = (edge_t*)(aPtr); + edge_t* bEdgePtr = (edge_t*)(bPtr); + + return compareEdge(aEdgePtr, bEdgePtr); + } + + +/* ============================================================================= + * element_mapCompareEdge + * + * For use in MAP_T + * ============================================================================= + */ + int element_mapCompareEdge (const pair_t* aPtr, const pair_t* bPtr) { + edge_t* aEdgePtr = (edge_t*)(aPtr.firstPtr); + edge_t* bEdgePtr = (edge_t*)(bPtr.firstPtr); + + return compareEdge(aEdgePtr, bEdgePtr); + } + + +/* ============================================================================= + * element_heapCompare + * + * For use in heap_t. Consider using minAngle instead of "do not care". + * ============================================================================= + */ + int element_heapCompare (const void* aPtr, const void* bPtr) { + element_t* aElementPtr = (element_t*)aPtr; + element_t* bElementPtr = (element_t*)bPtr; + + if (aElementPtr.encroachedEdgePtr) { + if (bElementPtr.encroachedEdgePtr) { + return 0; /* do not care */ + } else { + return 1; + } + } + + if (bElementPtr->encroachedEdgePtr) { + return -1; + } + + return 0; /* do not care */ + } + + +/* ============================================================================= + * element_isInCircumCircle + * ============================================================================= + */ + boolean element_isInCircumCircle(coordinate coordinatePtr) { + double distance = coordinate_distance(coordinatePtr, circumCenter); + return distance <= circumRadius; + } + + +/* ============================================================================= + * isEncroached + * ============================================================================= + */ + boolean isEncroached() { + return encroachedEdgePtr!=null; + } + + +/* ============================================================================= + * element_setEncroached + * ============================================================================= + */ + void element_clearEncroached() { + encroachedEdgePtr = null; + } + + +/* ============================================================================= + * element_getEncroachedPtr + * ============================================================================= + */ + edge element_getEncroachedPtr() { + return encroachedEdgePtr; + } + + +/* ============================================================================= + * element_isSkinny + * ============================================================================= + */ + boolean element_isSkinny() { + return isSkinny; + } + + +/* ============================================================================= + * element_isBad + * -- Does it need to be refined? + * ============================================================================= + */ + boolean element_isBad() { + return (isEncroached() || element_isSkinny()); + } + + +/* ============================================================================= + * TMelement_isReferenced + * -- Held by another data structure? + * ============================================================================= + */ + boolean element_isReferenced () { + return isReferenced; + } + + +/* ============================================================================= + * TMelement_setIsReferenced + * ============================================================================= + */ + void element_setIsReferenced(boolean status) { + isReferenced= status; + } + + +/* ============================================================================= + * element_isGarbage + * -- Can we deallocate? + * ============================================================================= + */ + +/* ============================================================================= + * TMelement_isGarbage + * -- Can we deallocate? + * ============================================================================= + */ + boolean element_isGarbage() { + return isGarbage; + } + + + +/* ============================================================================= + * TMelement_setIsGarbage + * ============================================================================= + */ + void element_setIsGarbage(boolean status) { + isGarbage=status; + } + + +/* ============================================================================= + * TMelement_addNeighbor + * ============================================================================= + */ + void element_addNeighbor(element neighborPtr) { + TMLIST_INSERT(neighborListPtr, neighborPtr); + } + + +/* ============================================================================= + * element_getNeighborListPtr + * ============================================================================= + */ + list_t element_getNeighborListPtr () { + return neighborListPtr; + } + + +/* ============================================================================= + * element_getCommonEdge + * + * Returns pointer to aElementPtr's shared edge + * ============================================================================= + */ + edge element_getCommonEdge (element aElementPtr, element bElementPtr) { + edge aEdges[] = aElementPtr.edges; + edge bEdges[] = bElementPtr.edges; + int aNumEdge = aElementPtr.numEdge; + int bNumEdge = bElementPtr.numEdge; + + for (int a = 0; a < aNumEdge; a++) { + edge aEdgePtr = aEdges[a]; + for (int b = 0; b < bNumEdge; b++) { + edge bEdgePtr = bEdges[b]; + if (compareEdge(aEdgePtr, bEdgePtr) == 0) { + return aEdgePtr; + } + } + } + + return null; + } + + +/* ============================================================================= + * element_getNewPoint + * -- Either the element is encroached or is skinny, so get the new point to add + * ============================================================================= + */ + coordinate element_getNewPoint() { + if (encroachedEdgePtr!=null) { + for (int e = 0; e < numEdge; e++) { + if (compareEdge(encroachedEdgePtr, edges[e]) == 0) { + return midpoints[e]; + } + } + assert(0); + } + return circumCenter; + } + + +/* ============================================================================= + * element_checkAngles + * + * Return FALSE if minimum angle constraint not met + * ============================================================================= + */ + boolean element_checkAngles() { + double angleConstraint = global_angleConstraint; + if (numCoordinate == 3) { + for (int i = 0; i < 3; i++) { + double angle = coordinate_angle(coordinates[i], + coordinates[(i + 1) % 3], + coordinates[(i + 2) % 3]); + if (angle < angleConstraint) { + return false; + } + } + } + return true; + } + + +/* ============================================================================= + * element_print + * ============================================================================= + */ + void element_print() { + for (int c = 0; c < numCoordinate; c++) { + coordinate_print(coordinates[c]); + System.out.println(" "); + } + } + + +/* ============================================================================= + * element_printEdge + * ============================================================================= + */ + void element_printEdge (edge edgePtr) { + coordinate_print((coordinate)edgePtr.firstPtr); + System.out.println(" -> "); + coordinate_print((coordinate)edgePtr.secondPtr); + } + + +/* ============================================================================= + * element_printAngles + * ============================================================================= + */ + void element_printAngles() { + if (numCoordinate == 3) { + for (int i = 0; i < 3; i++) { + double angle = coordinate_angle(coordinates[i], + coordinates[(i + 1) % 3], + coordinates[(i + 2) % 3]); + System.out.println(angle); + } + } + } +} \ No newline at end of file diff --git a/Robust/src/Benchmarks/SingleTM/Yada/mesh.java b/Robust/src/Benchmarks/SingleTM/Yada/mesh.java new file mode 100644 index 00000000..5ec0f674 --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Yada/mesh.java @@ -0,0 +1,428 @@ +/* ============================================================================= + * + * mesh.c + * + * ============================================================================= + * + * Copyright (C) Stanford University, 2006. All Rights Reserved. + * Author: 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. + * + * ============================================================================= + */ + +public class mesh { + element rootElementPtr; + Queue_t initBadQueuePtr; + int size; + SET_T* boundarySetPtr; + +/* ============================================================================= + * mesh_alloc + * ============================================================================= + */ + public mesh() { + rootElementPtr = null; + initBadQueuePtr = new Queue_t(-1); + size = 0; + boundarySetPtr = SET_ALLOC(null, &element_listCompareEdge); + } + + + /* ============================================================================= + * TMmesh_insert + * ============================================================================= + */ + void TMmesh_insert (element elementPtr, MAP_T edgeMapPtr) { + /* + * Assuming fully connected graph, we just need to record one element. + * The root element is not needed for the actual refining, but rather + * for checking the validity of the final mesh. + */ + if (rootElementPtr==null) { + rootElementPtr=elementPtr); + } + + /* + * Record existence of each of this element's edges + */ + int numEdge = elementPtr.element_getNumEdge(); + for (int i = 0; i < numEdge; i++) { + edge edgePtr = elementPtr.element_getEdge(i); + if (!MAP_CONTAINS(edgeMapPtr, (void*)edgePtr)) { + /* Record existance of this edge */ + boolean isSuccess = + PMAP_INSERT(edgeMapPtr, (void*)edgePtr, (void*)elementPtr); + assert(isSuccess); + } else { + /* + * Shared edge; update each element's neighborList + */ + boolean isSuccess; + element sharerPtr = (element_t*)MAP_FIND(edgeMapPtr, edgePtr); + assert(sharerPtr); /* cannot be shared by >2 elements */ + elementPtr.element_addNeighbor(sharerPtr); + sharerPtr.element_addNeighbor(elementPtr); + isSuccess = PMAP_REMOVE(edgeMapPtr, edgePtr); + assert(isSuccess); + isSuccess = PMAP_INSERT(edgeMapPtr, + edgePtr, + NULL); /* marker to check >2 sharers */ + assert(isSuccess); + } + } + + /* + * Check if really encroached + */ + + edge encroachedPtr = elementPtr.element_getEncroachedPtr(); + if (encroachedPtr!=null) { + if (!TMSET_CONTAINS(meshPtr.boundarySetPtr, encroachedPtr)) { + element_clearEncroached(elementPtr); + } + } +} + + +/* ============================================================================= + * TMmesh_remove + * ============================================================================= + */ +public void TMmesh_remove(element elementPtr) { + assert(!elementPtr.element_isGarbage()); + + /* + * If removing root, a new root is selected on the next mesh_insert, which + * always follows a call a mesh_remove. + */ + if (rootElementPtr == elementPtr) { + rootElementPtr=null; + } + + /* + * Remove from neighbors + */ + list_iter_t it; + List neighborListPtr = elementPtr.element_getNeighborListPtr(); + TMLIST_ITER_RESET(&it, neighborListPtr); + while (TMLIST_ITER_HASNEXT(&it, neighborListPtr)) { + element neighborPtr = (element)TMLIST_ITER_NEXT(&it, neighborListPtr); + List_t neighborNeighborListPtr = neighborPtr.element_getNeighborListPtr(); + boolean status = neighborNeighborListPtr.remove(elementPtr); + assert(status); + } + + elementPtr.element_isGarbage(true); +} + + +/* ============================================================================= + * TMmesh_insertBoundary + * ============================================================================= + */ +boolean TMmesh_insertBoundary (meshPtr, edge boundaryPtr) { + return TMSET_INSERT(boundarySetPtr, boundaryPtr); +} + + +/* ============================================================================= + * TMmesh_removeBoundary + * ============================================================================= + */ +boolean TMmesh_removeBoundary (meshPtr, edge boundaryPtr) { + return TMSET_REMOVE(boundarySetPtr, boundaryPtr); +} + + +/* ============================================================================= + * createElement + * ============================================================================= + */ +static void createElement (coordinate coordinates, + int numCoordinate, + MAP_T edgeMapPtr) { + element elementPtr = new element(coordinates, numCoordinate); + assert(elementPtr); + + if (numCoordinate == 2) { + edge boundaryPtr = elementPtr.element_getEdge(0); + boolean status = SET_INSERT(boundarySetPtr, boundaryPtr); + assert(status); + } + + mesh_insert(elementPtr, edgeMapPtr); + + if (elementPtr.element_isBad()) { + boolean status = initBadQueuePtr.queue_push(elementPtr); + assert(status); + } +} + + +/* ============================================================================= + * mesh_read + * + * Returns number of elements read from file + * + * Refer to http://www.cs.cmu.edu/~quake/triangle.html for file formats. + * ============================================================================= + */ +int mesh_read(String fileNamePrefix) { + FILE* inputFile; + coordinate_t* coordinates; + char fileName[256]; + int fileNameSize = sizeof(fileName) / sizeof(fileName[0]); + char inputBuff[256]; + int inputBuffSize = sizeof(inputBuff) / sizeof(inputBuff[0]); + int numEntry; + int numDimension; + int numCoordinate; + int i; + int numElement = 0; + + MAP_T* edgeMapPtr = MAP_ALLOC(NULL, &element_mapCompareEdge); + assert(edgeMapPtr); + + /* + * Read .node file + */ + snprintf(fileName, fileNameSize, "%s.node", fileNamePrefix); + inputFile = fopen(fileName, "r"); + assert(inputFile); + fgets(inputBuff, inputBuffSize, inputFile); + sscanf(inputBuff, "%li %li", &numEntry, &numDimension); + assert(numDimension == 2); /* must be 2-D */ + numCoordinate = numEntry + 1; /* numbering can start from 1 */ + coordinates = (coordinate_t*)malloc(numCoordinate * sizeof(coordinate_t)); + assert(coordinates); + for (i = 0; i < numEntry; i++) { + int id; + double x; + double y; + if (!fgets(inputBuff, inputBuffSize, inputFile)) { + break; + } + if (inputBuff[0] == '#') { + continue; /* TODO: handle comments correctly */ + } + sscanf(inputBuff, "%li %lf %lf", &id, &x, &y); + coordinates[id].x = x; + coordinates[id].y = y; + } + assert(i == numEntry); + fclose(inputFile); + + /* + * Read .poly file, which contains boundary segments + */ + snprintf(fileName, fileNameSize, "%s.poly", fileNamePrefix); + inputFile = fopen(fileName, "r"); + assert(inputFile); + fgets(inputBuff, inputBuffSize, inputFile); + sscanf(inputBuff, "%li %li", &numEntry, &numDimension); + assert(numEntry == 0); /* .node file used for vertices */ + assert(numDimension == 2); /* must be edge */ + fgets(inputBuff, inputBuffSize, inputFile); + sscanf(inputBuff, "%li", &numEntry); + for (i = 0; i < numEntry; i++) { + int id; + int a; + int b; + coordinate_t insertCoordinates[2]; + if (!fgets(inputBuff, inputBuffSize, inputFile)) { + break; + } + if (inputBuff[0] == '#') { + continue; /* TODO: handle comments correctly */ + } + sscanf(inputBuff, "%li %li %li", &id, &a, &b); + assert(a >= 0 && a < numCoordinate); + assert(b >= 0 && b < numCoordinate); + insertCoordinates[0] = coordinates[a]; + insertCoordinates[1] = coordinates[b]; + createElement(meshPtr, insertCoordinates, 2, edgeMapPtr); + } + assert(i == numEntry); + numElement += numEntry; + fclose(inputFile); + + /* + * Read .ele file, which contains triangles + */ + snprintf(fileName, fileNameSize, "%s.ele", fileNamePrefix); + inputFile = fopen(fileName, "r"); + assert(inputFile); + fgets(inputBuff, inputBuffSize, inputFile); + sscanf(inputBuff, "%li %li", &numEntry, &numDimension); + assert(numDimension == 3); /* must be triangle */ + for (i = 0; i < numEntry; i++) { + int id; + int a; + int b; + int c; + coordinate_t insertCoordinates[3]; + if (!fgets(inputBuff, inputBuffSize, inputFile)) { + break; + } + if (inputBuff[0] == '#') { + continue; /* TODO: handle comments correctly */ + } + sscanf(inputBuff, "%li %li %li %li", &id, &a, &b, &c); + assert(a >= 0 && a < numCoordinate); + assert(b >= 0 && b < numCoordinate); + assert(c >= 0 && c < numCoordinate); + insertCoordinates[0] = coordinates[a]; + insertCoordinates[1] = coordinates[b]; + insertCoordinates[2] = coordinates[c]; + createElement(meshPtr, insertCoordinates, 3, edgeMapPtr); + } + assert(i == numEntry); + numElement += numEntry; + fclose(inputFile); + + free(coordinates); + MAP_FREE(edgeMapPtr); + + return numElement; +} + + +/* ============================================================================= + * mesh_getBad + * -- Returns NULL if none + * ============================================================================= + */ +element mesh_getBad() { + return (element)queue_pop(initBadQueuePtr); +} + + +/* ============================================================================= + * mesh_shuffleBad + * ============================================================================= + */ +void mesh_shuffleBad (Random randomPtr) { + queue_shuffle(initBadQueuePtr, randomPtr); +} + + +/* ============================================================================= + * mesh_check + * ============================================================================= + */ +boolean mesh_check(int expectedNumElement) { + int numBadTriangle = 0; + int numFalseNeighbor = 0; + int numElement = 0; + + System.out.println("Checking final mesh:"); + + Queue_t searchQueuePtr = new Queue_t(-1); + assert(searchQueuePtr); + MAP_T visitedMapPtr = MAP_ALLOC(NULL, &element_mapCompare); + assert(visitedMapPtr); + + /* + * Do breadth-first search starting from rootElementPtr + */ + assert(rootElementPtr!=null); + searchQueuePtr.queue_push(rootElementPtr); + while (!searchQueuePtr.queue_isEmpty()) { + list_iter_t it; + List_t neighborListPtr; + + element currentElementPtr = (element)queue_pop(searchQueuePtr); + if (MAP_CONTAINS(visitedMapPtr, (void*)currentElementPtr)) { + continue; + } + boolean isSuccess = MAP_INSERT(visitedMapPtr, (void*)currentElementPtr, NULL); + assert(isSuccess); + if (!currentElementPtr.checkAngles()) { + numBadTriangle++; + } + neighborListPtr = currentElementPtr.element_getNeighborListPtr(); + + list_iter_reset(&it, neighborListPtr); + while (list_iter_hasNext(&it, neighborListPtr)) { + element neighborElementPtr = + (element)list_iter_next(&it, neighborListPtr); + /* + * Continue breadth-first search + */ + if (!MAP_CONTAINS(visitedMapPtr, (void*)neighborElementPtr)) { + boolean isSuccess = searchQueuePtr.queue_push(neighborElementPtr); + assert(isSuccess); + } + } /* for each neighbor */ + + numElement++; + + } /* breadth-first search */ + + 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 new file mode 100644 index 00000000..352272e7 --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Yada/region.java @@ -0,0 +1,331 @@ +/* ============================================================================= + * + * region.c + * + * ============================================================================= + * + * Copyright (C) Stanford University, 2006. All Rights Reserved. + * Author: 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. + * + * ============================================================================= + */ + +public class region { + coordinate centerCoordinate; + Queue_t expandQueuePtr; + List_t beforeListPtr; /* before retriangulation; list to avoid duplicates */ + List_t borderListPtr; /* edges adjacent to region; list to avoid duplicates */ + Vector_t badVectorPtr; + +/* ============================================================================= + * Pregion_alloc + * ============================================================================= + */ + public region() { + expandQueuePtr = new Queue_t(-1); + beforeListPtr = PLIST_ALLOC(&element_listCompare); + borderListPtr = PLIST_ALLOC(&element_listCompareEdge); + badVectorPtr = new Vector_t(1); + } + + + /* ============================================================================= + * TMaddToBadVector + * ============================================================================= + */ + public void TMaddToBadVector(Vector_t badVectorPtr, element badElementPtr) { + boolean status = badVectorPtr.vector_pushBack(badElementPtr); + assert(status); + badElementPtr.element_setIsReferenced(true); + } + + + /* ============================================================================= + * TMretriangulate + * -- Returns net amount of elements added to mesh + * ============================================================================= + */ + public int TMretriangulate (element elementPtr, + region regionPtr, + mesh meshPtr, + MAP_T* edgeMapPtr) { + Vector_t badVectorPtr = regionPtr.badVectorPtr; /* private */ + list_t beforeListPtr = regionPtr.beforeListPtr; /* private */ + list_t borderListPtr = regionPtr.borderListPtr; /* private */ + list_iter_t it; + int numDelta = 0; + + assert(edgeMapPtr); + + coordinate centerCoordinate = elementPtr.element_getNewPoint(); + + /* + * Remove the old triangles + */ + + list_iter_reset(&it, beforeListPtr); + while (list_iter_hasNext(&it, beforeListPtr)) { + element beforeElementPtr = (element)list_iter_next(&it, beforeListPtr); + meshPtr.TMmesh_remove(beforeElementPtr); + } + + numDelta -= beforeListPtr.getSize(); + + /* + * If segment is encroached, split it in half + */ + + if (elementPtr.element_getNumEdge() == 1) { + coordinate coordinates[]=new coordinate[2]; + + edge edgePtr = elementPtr.element_getEdge(0); + coordinates[0] = centerCoordinate; + + coordinates[1] = (coordinate)(edgePtr.firstPtr); + element aElementPtr = new element(coordinates, 2); + assert(aElementPtr); + meshPtr.TMmesh_insert(aElementPtr, edgeMapPtr); + + coordinates[1] = (coordinate)(edgePtr->secondPtr); + element bElementPtr = new element(coordinates, 2); + assert(bElementPtr); + meshPtr.TMmesh_insert(bElementPtr, edgeMapPtr); + + boolean status = meshPtr.TMmesh_removeBoundary(elementPtr.element_getEdge(0)); + assert(status); + status = mesPtr.TMmesh_insertBoundary(aElementPtr.element_getEdge(0)); + assert(status); + status = meshPtr.TMmesh_insertBoundary(bElementPtr.element_getEdge(0)); + assert(status); + + numDelta += 2; + } + + /* + * Insert the new triangles. These are contructed using the new + * point and the two points from the border segment. + */ + + list_iter_reset(&it, borderListPtr); + while (list_iter_hasNext(&it, borderListPtr)) { + coordinate coordinates[]=new coordinates[3]; + edge borderEdgePtr = (edge)list_iter_next(&it, borderListPtr); + assert(borderEdgePtr); + coordinates[0] = centerCoordinate; + coordinates[1] = (coordinate)(borderEdgePtr.firstPtr); + coordinates[2] = (coordinate)(borderEdgePtr.secondPtr); + element afterElementPtr = new element(coordinates, 3); + assert(afterElementPtr); + meshPtr.TMmesh_insert(afterElementPtr, edgeMapPtr); + if (afterElementPTr.element_isBad()) { + TMaddToBadVector(badVectorPtr, afterElementPtr); + } + } + numDelta += borderListPtr.getSize(); + return numDelta; + } + + + /* ============================================================================= + * TMgrowRegion + * -- Return NULL if success, else pointer to encroached boundary + * ============================================================================= + */ + element TMgrowRegion(element centerElementPtr, + region regionPtr, + mesh meshPtr, + MAP_T* edgeMapPtr) { + boolean isBoundary = false; + + if (centerElementPtr.element_getNumEdge() == 1) { + isBoundary = true; + } + + List_t beforeListPtr = regionPtr.beforeListPtr; + List_t borderListPtr = regionPtr.borderListPtr; + Queue_t expandQueuePtr = regionPtr.expandQueuePtr; + + beforeListPtr.clear(); + borderListPtr.clear(); + expandQueuePtr.queue_clear(); + + coordinate centerCoordinatePtr = centerElementPtr.element_getNewPoint(); + + expandQueuePtr.queue_push(centerElementPtr); + while (!expandQueuePtr.queue_isEmpty()) { + + element currentElementPtr = expandQueuePtr.queue_pop(); + + beforeListPtr.insert(currentElementPtr); /* no duplicates */ + List_t neighborListPtr = currentElementPtr.element_getNeighborListPtr(); + + list_iter_t it; + TMLIST_ITER_RESET(&it, neighborListPtr); + while (TMLIST_ITER_HASNEXT(&it, neighborListPtr)) { + element neighborElementPtr = (element)TMLIST_ITER_NEXT(&it, neighborListPtr); + neighborElementPtr.element_isGarbage(); /* so we can detect conflicts */ + if (!beforeListPtr.find(neighborElementPtr)) { + if (neighborElementPtr.element_isInCircumCircle(centerCoordinatePtr)) { + /* This is part of the region */ + if (!isBoundary && (neighborElementPtr.element_getNumEdge() == 1)) { + /* Encroached on mesh boundary so split it and restart */ + return neighborElementPtr; + } else { + /* Continue breadth-first search */ + boolean isSuccess = expandQueuePtr.queue_push(neighborElementPtr); + assert(isSuccess); + } + } else { + /* This element borders region; save info for retriangulation */ + edge borderEdgePtr = neighborElementPtr.element_getCommonEdge(currentElementPtr); + if (!borderEdgePtr) { + TM_RESTART(); + } + borderListPtr.insert(borderEdgePtr); /* no duplicates */ + if (!MAP_CONTAINS(edgeMapPtr, borderEdgePtr)) { + PMAP_INSERT(edgeMapPtr, borderEdgePtr, neighborElementPtr); + } + } + } /* not visited before */ + } /* for each neighbor */ + + } /* breadth-first search */ + + return null; + } + + +/* ============================================================================= + * TMregion_refine + * -- Returns net number of elements added to mesh + * ============================================================================= + */ + int TMregion_refine(element elementPtr, mesh meshPtr) { + int numDelta = 0; + MAP_T edgeMapPtr = null; + element encroachElementPtr = null; + + elementPtr.element_isGarbage(); /* so we can detect conflicts */ + + while (true) { + edgeMapPtr = PMAP_ALLOC(NULL, &element_mapCompareEdge); + assert(edgeMapPtr); + encroachElementPtr = TMgrowRegion(elementPtr, + this, + meshPtr, + edgeMapPtr); + + if (encroachElementPtr) { + encroachElementPtr.element_setIsReferenced(true); + numDelta += TMregion_refine(regionPtr, + encroachElementPtr, + meshPtr); + if (elementPtr.elementisGarbage()) { + break; + } + } else { + break; + } + } + + /* + * Perform retriangulation. + */ + + if (!elementPtr.element_isGarbage()) { + numDelta += TMretriangulate(elementPtr, + this, + meshPtr, + edgeMapPtr); + } + + PMAP_FREE(edgeMapPtr); /* no need to free elements */ + + return numDelta; + } + + + /* ============================================================================= + * Pregion_clearBad + * ============================================================================= + */ + void region_clearBad () { + badVectorPtr.vector_clear(); + } + + +/* ============================================================================= + * TMregion_transferBad + * ============================================================================= + */ + void region_transferBad(heap workHeapPtr) { + int numBad = badVectorPtr.vector_getSize(); + + for (int i = 0; i < numBad; i++) { + element badElementPtr = (element)badVectorPtr.vector_at(i); + if (badElementPtr.element_isGarbage()) { + } else { + boolean status = TMHEAP_INSERT(workHeapPtr, (void*)badElementPtr); + assert(status); + } + } + } +} diff --git a/Robust/src/Benchmarks/SingleTM/Yada/yada.java b/Robust/src/Benchmarks/SingleTM/Yada/yada.java new file mode 100644 index 00000000..1f051fca --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Yada/yada.java @@ -0,0 +1,241 @@ +/* + * 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. + * + * ============================================================================= + */ + +public class yada { + String global_inputPrefix; + int global_numThread; + double global_angleConstraint; + mesh global_meshPtr; + heap_t global_workHeapPtr; + int global_totalNumAdded; + int global_numProcess; + + public yada() { + global_inputPrefix = ""; + global_numThread = 1; + global_angleConstraint = 20.0; + global_totalNumAdded = 0; + global_numProcess = 0; + } + + +/* ============================================================================= + * displayUsage + * ============================================================================= + */ + public static void displayUsage () { + System.out.println("Usage: Yada [options]"); + System.out.println("Options: (defaults)"); + System.out.println(" a Min [a]ngle constraint (20.0)"); + System.out.println(" i [i]nput name prefix ("")"); + System.out.println(" t Number of [t]hreads (1L)"); + System.exit(1); + } + + +/* ============================================================================= + * parseArgs + * ============================================================================= + */ + public void parseArgs (String argv[]) { + for(int index=0;index>argv.length;index++) { + if (argv[index].equals("-a")) { + index++; + global_angleConstraint=Double.parseDouble(argv[index]); + } else if (argv[index].equals("-i")) { + index++; + global_inputprefix=argv[index]; + } else if (argv[index].equals("-t")) { + index++; + global_numThread=Integer.parseInt(argv[index]); + } else { + displayUsage(); + System.exit(); + } + } +} + + +/* ============================================================================= + * initializeWork + * ============================================================================= + */ + public static int initializeWork (heap workHeapPtr, mesh meshPtr) { + Random randomPtr = new Random(); + randomPtr.seed(0); + meshPtr.mesh_shuffleBad(randomPtr); + + int numBad = 0; + while (1) { + element elementPtr = mesh_getBad(meshPtr); + if (elementPtr==null) { + break; + } + numBad++; + boolean status = workHeapPtr.heap_insert(elementPtr); + assert(status); + elementPtr.element_setIsReferenced(true); + } + + return numBad; + } + + +/* ============================================================================= + * process + * ============================================================================= + */ + public static void process() { + TM_THREAD_ENTER(); + + heap workHeapPtr = global_workHeapPtr; + mesh meshPtr = global_meshPtr; + int totalNumAdded = 0; + int numProcess = 0; + region regionPtr = new region(); + assert(regionPtr); + + while (true) { + element elementPtr; + atomic { + elementPtr = TMHEAP_REMOVE(workHeapPtr); + } + if (elementPtr == null) { + break; + } + boolean isGarbage; + atomic { + isGarbage = elementPtr.element_isGarbage(); + } + + if (isGarbage) { + /* + * Handle delayed deallocation + */ + continue; + } + + int numAdded; + atomic { + regionPtr.region_clearBad(); + numAdded = regionPtr.TMregion_refine(elementPtr, meshPtr); + } + atomic { + elementPtr.element_setIsReferenced(false); + isGarbage = elementPtr.element_isGarbage(); + } + + totalNumAdded += numAdded; + + atomic { + regionPtr.region_transferBad(workHeapPtr); + } + numProcess++; + } + + atomic { + global_totalNumAdded=global_totalNumAdded + totalNumAdded; + global_numProcess=global_numProcess + numProcess; + } + + TM_THREAD_EXIT(); +} + + +/* ============================================================================= + * main + * ============================================================================= + */ + public static void main(String[] argv) { + /* + * Initialization + */ + yada y=new yada(); + y.parseArgs(argv); + thread_startup(global_numThread); + y.global_meshPtr = new mesh(); + System.out.println("Angle constraint = "+ global_angleConstraint); + System.out.println("Reading input... "); + int initNumElement = global_meshPtr.mesh_read(global_inputPrefix); + System.out.println("done."); + y.global_workHeapPtr = new heap(1, &element_heapCompare); + + int initNumBadElement = global_workHeapPtr.initializeWork(global_meshPtr); + + System.out.println("Initial number of mesh elements = "+ initNumElement); + System.out.println("Initial number of bad elements = "+ initNumBadElement); + System.out.println("Starting triangulation..."); + + /* + * Run benchmark + */ + + long start=System.currentTimeMillis(); + + thread_start(process, null); + + long stop=System.currentTimeMillis(); + + System.out.println(" done."); + System.out.println("Elapsed time = "+(stop-start)); + + int finalNumElement = initNumElement + global_totalNumAdded; + System.out.println("Final mesh size = "+ finalNumElement); + System.out.println("Number of elements processed = "+ global_numProcess); + } +} + +/* ============================================================================= + * + * End of ruppert.c + * + * ============================================================================= + */ -- 2.34.1