From b987fd1d50a42a45bd5bbd0307cd53ed091752af Mon Sep 17 00:00:00 2001 From: stephey Date: Wed, 16 Jun 2010 00:32:28 +0000 Subject: [PATCH] Under Original/Normal_Java/ one would find the original Labyrinth project ported to Transactional Memory by Jihoon and reported to normal Java by Stephen Yang Under mlp is the Labyrinth project modified with rblocks. Under mlp/Normal_Java is a version that can be compiled and run on the normal Java platform. Under rBlocked is the rBlocked version that SHOULD run under OoOJava compiler. Both of which are ported by Stephen Yang (from Jihoon's original port) NOTE that at this point in time, the rBlocked version causes a NullPointerException in the OoOJava compiler but will compile and produce correct results under normal Java. --- .../Original/Normal_Java/Coordinate.java | 178 ++++++ .../Labyrinth/Original/Normal_Java/Grid.java | 283 ++++++++++ .../Original/Normal_Java/Labyrinth.java | 258 +++++++++ .../Original/Normal_Java/List_Iter.java | 38 ++ .../Original/Normal_Java/List_Node.java | 10 + .../Original/Normal_Java/List_t.java | 312 +++++++++++ .../Labyrinth/Original/Normal_Java/Math.java | 136 +++++ .../Labyrinth/Original/Normal_Java/Maze.java | 415 ++++++++++++++ .../Labyrinth/Original/Normal_Java/Pair.java | 86 +++ .../Labyrinth/Original/Normal_Java/Point.java | 25 + .../Original/Normal_Java/Queue_Int.java | 448 +++++++++++++++ .../Original/Normal_Java/Queue_t.java | 327 +++++++++++ .../Labyrinth/Original/Normal_Java/README | 71 +++ .../Original/Normal_Java/Router.java | 456 ++++++++++++++++ .../Original/Normal_Java/Solve_Arg.java | 15 + .../Original/Normal_Java/Vector_t.java | 156 ++++++ .../Original/Normal_Java/extractLines | 3 + .../mlp/Normal_Java/CoordPathWrapper.java | 12 + .../Labyrinth/mlp/Normal_Java/Coordinate.java | 178 ++++++ .../Labyrinth/mlp/Normal_Java/Grid.java | 307 +++++++++++ .../Labyrinth/mlp/Normal_Java/Labyrinth.java | 237 ++++++++ .../Labyrinth/mlp/Normal_Java/List_Iter.java | 38 ++ .../Labyrinth/mlp/Normal_Java/List_Node.java | 10 + .../Labyrinth/mlp/Normal_Java/List_t.java | 312 +++++++++++ .../Labyrinth/mlp/Normal_Java/Math.java | 136 +++++ .../Labyrinth/mlp/Normal_Java/Maze.java | 508 ++++++++++++++++++ .../Labyrinth/mlp/Normal_Java/Original README | 71 +++ .../Labyrinth/mlp/Normal_Java/Pair.java | 86 +++ .../Labyrinth/mlp/Normal_Java/Point.java | 25 + .../Labyrinth/mlp/Normal_Java/Queue_Int.java | 448 +++++++++++++++ .../Labyrinth/mlp/Normal_Java/Queue_t.java | 345 ++++++++++++ .../Labyrinth/mlp/Normal_Java/Router.java | 498 +++++++++++++++++ .../Labyrinth/mlp/Normal_Java/Solve_Arg.java | 20 + .../Labyrinth/mlp/Normal_Java/TODO.txt | 13 + .../Labyrinth/mlp/Normal_Java/Vector_t.java | 156 ++++++ .../Labyrinth/mlp/Normal_Java/extractLines | 3 + .../mlp/rBlocked/CoordPathWrapper.java | 12 + .../Labyrinth/mlp/rBlocked/Coordinate.java | 178 ++++++ .../Labyrinth/mlp/rBlocked/Grid.java | 307 +++++++++++ .../Labyrinth/mlp/rBlocked/Labyrinth.java | 237 ++++++++ .../Labyrinth/mlp/rBlocked/List_Iter.java | 38 ++ .../Labyrinth/mlp/rBlocked/List_Node.java | 10 + .../Labyrinth/mlp/rBlocked/List_t.java | 312 +++++++++++ .../Labyrinth/mlp/rBlocked/Maze.java | 486 +++++++++++++++++ .../Labyrinth/mlp/rBlocked/Original README | 71 +++ .../Labyrinth/mlp/rBlocked/Pair.java | 86 +++ .../Labyrinth/mlp/rBlocked/Point.java | 25 + .../Labyrinth/mlp/rBlocked/Queue_Int.java | 448 +++++++++++++++ .../Labyrinth/mlp/rBlocked/Queue_t.java | 345 ++++++++++++ .../Labyrinth/mlp/rBlocked/Router.java | 498 +++++++++++++++++ .../Labyrinth/mlp/rBlocked/Solve_Arg.java | 20 + .../Labyrinth/mlp/rBlocked/Vector_t.java | 156 ++++++ .../Labyrinth/mlp/rBlocked/extractLines | 3 + .../Labyrinth/mlp/rBlocked/makefile | 29 + 54 files changed, 9881 insertions(+) create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Coordinate.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Grid.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Labyrinth.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/List_Iter.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/List_Node.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/List_t.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Math.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Maze.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Pair.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Point.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Queue_Int.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Queue_t.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/README create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Router.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Solve_Arg.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Vector_t.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/extractLines create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/CoordPathWrapper.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Coordinate.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Grid.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Labyrinth.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/List_Iter.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/List_Node.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/List_t.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Math.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Maze.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Original README create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Pair.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Point.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Queue_Int.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Queue_t.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Router.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Solve_Arg.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/TODO.txt create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Vector_t.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/extractLines create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/CoordPathWrapper.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Coordinate.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Grid.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Labyrinth.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/List_Iter.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/List_Node.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/List_t.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Maze.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Original README create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Pair.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Point.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Queue_Int.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Queue_t.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Router.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Solve_Arg.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Vector_t.java create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/extractLines create mode 100644 Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/makefile diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Coordinate.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Coordinate.java new file mode 100644 index 00000000..68f792b9 --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Coordinate.java @@ -0,0 +1,178 @@ +/* ============================================================================= + * + * coordinate.java + * + * ============================================================================= + * + * 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. + * + * ============================================================================= + */ + + + + +import java.lang.Math; + +public class Coordinate { + + public int x; + public int y; + public int z; + + public Coordinate() {} + + + // coordiate_alloc will be constructor + // coordinate_t* coordinate_alloc(long x, long y, long z) + public Coordinate(int x,int y,int z) { + this.x = x; + this.y = y; + this.z = z; + } + + public static Coordinate alloc(int x,int y,int z) { + Coordinate c = new Coordinate(x,y,z); + + return c; + } + + + // deallocate memory + // may not need + // coordinate_free + + /*======================================================== + // coordinate_isEqual + ==========================================================*/ + public static boolean isEqual(Coordinate a,Coordinate b) + { + if((a.x == b.x) && (a.y == b.y) && (a.z == b.z)) + return true; + + return false; + } + + /*========================================================== + * + * getPairDistance + * + *========================================================*/ + private static double getPairDistance(Pair p) + { + Coordinate a = (Coordinate)p.first; + Coordinate b = (Coordinate)p.second; + int dx = a.x - b.x; + int dy = a.y - b.y; + int dz = a.z - b.z; + int dx2 = dx* dx; + int dy2 = dy* dy; + int dz2 = dz* dz; + + return Math.sqrt((double)(dx2+dy2+dz2)); + } + + + /*================================================ + // coordinat_ comparePair + * -- For sorting in list of source/destination pairs + * -- Route longer paths first so they are more likely to suceed + + *================================================*/ + public static int comparePair(final Object a,final Object b) + { + double aDistance = getPairDistance((Pair)a); + double bDistance = getPairDistance((Pair)b); + + if(aDistance < bDistance) { + return 1; + } else if(aDistance > bDistance) { + return -1; + } + + return 0; + } + + /*======================================================= + * coordinate_areAdjacent + *=======================================================*/ + + public static boolean areAdjacent(Coordinate a,Coordinate b) + { + int dx = a.x - b.x; + int dy = a.y - b.y; + int dz = a.z - b.z; + int dx2 = dx * dx; + int dy2 = dy * dy; + int dz2 = dz * dz; + + return (((dx2 + dy2 + dz2) == 1) ? true : false); + } + } + + /*===================================================== + * + * End of Coordinate + * + *====================================================*/ + + diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Grid.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Grid.java new file mode 100644 index 00000000..aabcf476 --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Grid.java @@ -0,0 +1,283 @@ + + +//#define GRID_POINT_FULL -2 +//#define GRID_POINT_EMPTY -1 + + + +public class Grid +{ + //TODO change these back into #defines up top + private static int GRID_POINT_FULL; + private static int GRID_POINT_EMPTY; + + + public int width; + public int height; + public int depth; + public int[][] points_unaligned; + + public Grid() + { + //Kept from #defines + GRID_POINT_FULL = -2; + GRID_POINT_EMPTY =-1; + } + + +/* ============================================================================= + * grid_alloc + * ============================================================================= + grid_t* grid_alloc (long width, long height, long depth); + + well... need to implement + got stuck + */ + public static Grid alloc(int width,int height,int depth) { + Grid grid = new Grid(); + + if(grid != null) { + + grid.width = width; + grid.height = height; + grid.depth = depth; + + int n = width * height * depth; + + // long* points_unaligned = (long*) malloc(n*sizeof(long) + CACHE_LINE_SIZE); + int[][] points_unaligned = new int[n][1]; + + grid.points_unaligned = points_unaligned; + + for(int i=0;i= width || + y < 0 || y >= height || + z < 0 || z >= depth) + { + return false; + } + + return true; + } + + +/* ============================================================================= + * grid_getPointRef + * ============================================================================= +long* grid_getPointRef (grid_t* gridPtr, long x, long y, long z); + + it is returning the index of the point +*/ + public int getPointIndex(int x,int y,int z) + { + return ((z * height) + y) * width + x; + } + + +/* ============================================================================= + * grid_getPointIndices + * ============================================================================= + void grid_getPointIndices (grid_t* gridPtr, + long* gridPointPtr, long* xPtr, long* yPtr, long* zPtr); + */ + public void getPointIndices(int gridPointIndex,int[] xPtr, int[] yPtr,int[] zPtr) + { + int height = this.height; + int width = this.width; + int area = height * width; + int index3d = (gridPointIndex); + zPtr[0] = index3d / area; + int index2d = index3d % area; + yPtr[0] = index2d / width; + xPtr[0] = index2d % width; + } + + +/* ============================================================================= + * grid_getPoint + * ============================================================================= + long grid_getPoint (grid_t* gridPtr, long x, long y, long z); + */ + public int getPoint(int x,int y,int z) + { + return this.points_unaligned[getPointIndex(x,y,z)][0]; + } + + public int getPoint(int index) + { + return this.points_unaligned[index][0]; + } + + +/* ============================================================================= + * grid_isPointEmpty + * ============================================================================= + bool_t grid_isPointEmpty (grid_t* gridPtr, long x, long y, long z); + */ + public boolean isPointEmpty(int x,int y,int z) + { + int value = getPoint(x,y,z); + return ((value == GRID_POINT_EMPTY) ? true:false); + } + + + +/* ============================================================================= + * grid_isPointFull + * ============================================================================= + bool_t grid_isPointFull (grid_t* gridPtr, long x, long y, long z); + */ + public boolean isPointFull(int x,int y,int z) + { + int value = getPoint(x,y,z); + return ((value == GRID_POINT_FULL) ? true : false); + } + + +/* ============================================================================= + * grid_setPoint + * ============================================================================= + void grid_setPoint (grid_t* gridPtr, long x, long y, long z, long value); + */ + public void setPoint(int x,int y,int z,int value) + { + points_unaligned[getPointIndex(x,y,z)][0] = value; + } + + +/* ============================================================================= + * grid_addPath + * ============================================================================= + +void grid_addPath (grid_t* gridPtr, vector_t* pointVectorPtr); +*/ + public void addPath(Vector_t pointVectorPtr) + { + int i; + int n = pointVectorPtr.vector_getSize(); + + for(i = 0; i < n; i++) { + Coordinate coordinatePtr = (Coordinate)pointVectorPtr.vector_at(i); + int x = coordinatePtr.x; + int y = coordinatePtr.y; + int z = coordinatePtr.z; + +// System.out.println("x = " + x + " y = " + y + " z = " + z); + setPoint(x,y,z,GRID_POINT_FULL); + } + } + + public void TM_addPath(Vector_t pointVectorPtr) + { + int i; + int n = pointVectorPtr.vector_getSize(); + + for(i = 0; i < n; i++) { + int gridPointIndex = ((Integer)(pointVectorPtr.vector_at(i))).intValue(); + points_unaligned[gridPointIndex][0] = GRID_POINT_FULL; + } + } + +/* ============================================================================= + * TMgrid_addPath + * ============================================================================= + TM_CALLABLE +void +TMgrid_addPath (TM_ARGDECL grid_t* gridPtr, vector_t* pointVectorPtr); +*/ + + +/* ============================================================================= + * grid_print + * ============================================================================= +void grid_print (grid_t* gridPtr); +*/ + public void print() + { + int z; + + for(z = 0; z < depth; z++) { + System.out.println("[z = " + z + "]"); + int x; + for(x = 0; x < width; x++) { + int y; + for(y = 0; y < height; y++) { + System.out.print(points_unaligned[getPointIndex(x,y,z)][0] + " "); + } + System.out.println(""); + } + System.out.println(""); + } + + } +} + +/* ============================================================================= + * + * End of grid.c + * + * ============================================================================= + */ diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Labyrinth.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Labyrinth.java new file mode 100644 index 00000000..fad4f1d6 --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Labyrinth.java @@ -0,0 +1,258 @@ +/* ============================================================================= + * + * Labyrinth.java + * + * ============================================================================= + * + * 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 Labyrinth extends Thread{ + + static String global_inputFile; + static boolean global_doPrint; + int numThread; + int bendCost; + int xCost; + int yCost; + int zCost; + + + // For threads + int threadID; + Solve_Arg routerArg; + + private void setDefaultParams() { + + /* default values */ + global_inputFile = null; + global_doPrint = false; + bendCost = 1; + xCost = 1; + yCost = 1; + zCost = 2; + numThread = 1; + } + + private void parseArg(String[] argv) { + int i=0; + String arg; + boolean opterr = false; + + + setDefaultParams(); + + while (i < argv.length) { + + if(argv[i].charAt(0) == '-' ) { + arg = argv[i++]; + // check options + if(arg.equals("-b")) { + bendCost = Integer.parseInt(argv[i++]); + } + else if(arg.equals("-x")) { + xCost = Integer.parseInt(argv[i++]); + } + else if(arg.equals("-y")) { + yCost = Integer.parseInt(argv[i++]); + } + else if(arg.equals("-z")) { + zCost = Integer.parseInt(argv[i++]); + } + else if(arg.equals("-t")) { + numThread = Integer.parseInt(argv[i++]); + } + else if(arg.equals("-i")) { + global_inputFile = argv[i++]; + } + else if(arg.equals("-p")) { + global_doPrint = true; + } + else { + System.out.println("Non-option argument: " + argv[i]); + opterr = true; + } + + } + } + if(opterr) { + displayUsage(); + System.exit(1); + } + } + + public Labyrinth(String[] argv) + { + System.out.println("Parsing args"); + parseArg(argv); + System.out.println("Paring done."); + } + + + public Labyrinth(int myID,Solve_Arg rArg) + { + threadID = myID; + routerArg = rArg; + } + + public void run() { +// Barrier.enterBarrier(); + System.out.println("Starting Thread..."); + Router.solve(routerArg); +// Barrier.enterBarrier(); + } + + public void displayUsage() + { + System.out.println("Usage: Labyrinth [options]"); + System.out.println("Options:"); + System.out.println(" b bend cost"); + System.out.println(" i input file name"); + System.out.println(" p print routed maze"); + System.out.println(" t Number of threads"); + System.out.println(" x x movement cost"); + System.out.println(" y y movement cost"); + System.out.println(" z z movement cost"); + } + + + public static void main(String[] argv) + { + /* + * Initailization + */ + System.out.println("Program started"); + Labyrinth labyrinth = new Labyrinth(argv); + +// Barrier.setBarrier(labyrinth.numThread); + + Maze mazePtr = Maze.alloc(); + + int numPathToRoute = mazePtr.readMaze(labyrinth.global_inputFile); + + Router routerPtr = Router.alloc(labyrinth.xCost,labyrinth.yCost, + labyrinth.zCost,labyrinth.bendCost); + + List_t pathVectorListPtr = List_t.alloc(0); // list_t.alloc(null) + /* + * Run transactions + */ + Solve_Arg routerArg = new Solve_Arg(routerPtr,mazePtr,pathVectorListPtr); + + /* Create and start thread */ + Labyrinth[] lb = new Labyrinth[labyrinth.numThread]; + + for(int i = 1; i= 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) + { + if(isCoordinate) + { + return Coordinate.comparePair(obj1,obj2); + } + else + return compareObject(obj1,obj2); + } + +/* ============================================================================= + * 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/Java-Single/Labyrinth/Original/Normal_Java/Math.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Math.java new file mode 100644 index 00000000..7e6a59f6 --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Math.java @@ -0,0 +1,136 @@ +public class Math { + + public static double setPI() { + double PI = 3.14159265358979323846; + return PI; + } + + // an alias for setPI() + public static double PI() { + double PI = 3.14159265358979323846; + return PI; + } + + public static int abs(int x) { + if (x < 0) { + return -x; + } else { + return x; + } + } + + public static double fabs(double x) { + if (x < 0) { + return -x; + } else { + return x; + } + } + + public static double abs(double x) { + if (x < 0) { + return -x; + } else { + return x; + } + } + + public static float abs(float a) { + if (a<0) + return -a; + else return a; + } + + public static double max(double a, double b) { + if(a == b) + return a; + if(a > b) { + return a; + } else { + return b; + } + } + + public static int max(int a, int b) { + if(a == b) + return a; + if(a > b) { + return a; + } else { + return b; + } + } + + public static int imax(int a, int b) { + if(a == b) + return a; + if(a > b) { + return a; + } else { + return b; + } + } + + public static int imin(int a, int b) { + if(a == b) + return a; + if(a > b) { + return b; + } else { + return a; + } + } + + /** sqrt(a^2 + b^2) without under/overflow. **/ + public static double hypot(double a, double b) { + double r; + if (fabs(a) > fabs(b)) { + r = b/a; + r = fabs(a)*sqrt(1+r*r); + } else if (b != 0) { + r = a/b; + r = fabs(b)*sqrt(1+r*r); + } else { + r = 0.0; + } + return r; + } + + public static double rint(double x) { + double y = ceil(x); + double d = y - x; + if( d == 0.5 ) { + if( ((int)y)%2 == 0 ) { + return y; + } else { + return y - 1.0; + } + } else if( d < 0.5 ) { + return y; + } + return y - 1.0; + } + + public static native double sin(double a); + public static native double cos(double a); + public static native double asin(double a); + public static native double acos(double a); + public static native double tan(double a); + public static native double atan(double a); + public static native double atan2(double a, double b); + public static native double exp(double a); + public static native double sqrt(double a); + public static native double log(double a); + public static native double pow(double a, double b); + + public static native double ceil(double a); + public static native double floor(double a); + + public static native float sinf(float a); + public static native float cosf(float a); + public static native float expf(float a); + public static native float sqrtf(float a); + public static native float logf(float a); + public static native float powf(float a, float b); + public static native float ceilf(float a); +} diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Maze.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Maze.java new file mode 100644 index 00000000..8dd13834 --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Maze.java @@ -0,0 +1,415 @@ +import java.io.File; +import java.io.FileInputStream; +import java.io.FileNotFoundException; +import java.util.Scanner; +import java.util.StringTokenizer; + +/*============================================================================= + * + * Maze.java + * + * ============================================================================= + * + * 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. + * + * ============================================================================= + */ + +//#define GRID_POINT_FULL -2 +//#define GRID_POINT_EMPTY -1 + +//TODO change these back and delete class variables. + +public class Maze +{ + private static int GRID_POINT_FULL; + private static int GRID_POINT_EMPTY; + + Grid gridPtr; + Queue_t workQueuePtr; + Vector_t wallVectorPtr; /* contains source/destination pairs to route */ + Vector_t srcVectorPtr; /* obstacles */ + Vector_t dstVectorPtr; /* destinations */ + + public Maze() + { + //these were changed from #defines + GRID_POINT_FULL = -2; + GRID_POINT_EMPTY = -1; + } + + +/* ============================================================================= + * maze_alloc + * ============================================================================= + maze_t* maze_alloc (); + */ + public static Maze alloc() + { + Maze mazePtr = new Maze(); + + if(mazePtr != null) { + mazePtr.gridPtr = null; + mazePtr.workQueuePtr = Queue_t.queue_alloc(1024); + mazePtr.wallVectorPtr = Vector_t.vector_alloc(1); + mazePtr.srcVectorPtr = Vector_t.vector_alloc(1); + mazePtr.dstVectorPtr = Vector_t.vector_alloc(1); + + } + + return mazePtr; + } + +/* ============================================================================= + * maze_free + * ============================================================================= + void maze_free (maze_t* mazePtr); + */ + public static void free(Maze m) + { + m = null; + } + +/* ============================================================================= + * addToGrid + * ============================================================================= + */ + private void addToGrid(Grid gridPtr,Vector_t vectorPtr,String type) + { + int i; + int n = vectorPtr.vector_getSize(); + + for(i = 0; i < n; i++) { + Coordinate coordinatePtr = (Coordinate)vectorPtr.vector_at(i); + if(!gridPtr.isPointValid(coordinatePtr.x,coordinatePtr.y,coordinatePtr.z)) + { + System.out.println("Error: " + type + " (" + coordinatePtr.x + + ", " + coordinatePtr.y + + ", " + coordinatePtr.z); + System.exit(1); + } + } + gridPtr.addPath(vectorPtr); + } +/* ============================================================================= + * maze_read + * -- Return number of path to route + * ============================================================================= + long maze_read (maze_t* mazePtr, char* inputFileName); + */ + public int readMaze(String inputFileName) + { + // FileInputStream in = new FileInputStream(inputFileName); + Scanner in; + try { + System.out.println("Opening file: " + inputFileName); + in = new Scanner(new File(inputFileName)); + + /* + * Parse input file + */ + int lineNumber = 0; + int height = -1; + int width = -1; + int depth = -1; + boolean isParseError = false; + List_t workListPtr = List_t.alloc(1); // List.alloc(Coordinate.comparePair); + String line; + + while(in.hasNext()) { + + line = in.nextLine(); + String code; + int[] xy = new int[6]; // equivalent to x1,y1,z1,x2,y2,z2 + int numToken = 0; + + StringTokenizer tok = new StringTokenizer(line); + + if((numToken = tok.countTokens()) < 1 ) { + continue; + } + + code = tok.nextToken(); + + if(code.equals("#")) { + /* comment line */ + continue; + } + for(int i=0;i + +in the source directory. For example, for the sequential flavor, run: + + make -f Makefile.seq + +By default, this produces an executable named "labyrinth", which can then be +run in the following manner: + + ./labyrinth -i + +The following input file is recommended for simulated runs: + + ./labyrinth -i inputs/random-x32-y32-z3-n96.txt + +For non-simulator runs, a larger input can be used: + + ./labyrinth -i inputs/random-x512-y512-z7-n512.txt + + +Input Files +----------- + +More input sets can be generated by using "inputs/generate.py". For example, + + inputs/generate.py 128 128 3 64 + +Will create a 128x128x3 maze grid and select 64 uniformly random start/end +point pairs. + + +References +---------- + +[1] C. Cao Minh, J. Chung, C. Kozyrakis, and K. Olukotun. STAMP: Stanford + Transactional Applications for Multi-processing. In IISWC '08: Proceedings + of The IEEE International Symposium on Workload Characterization, + September 2008. + +[2] C. Lee. An algorithm for path connections and its applications. IRE Trans. + On Electronic Computers, 1961. + +[3] I. Watson, C. Kirkham, and M. Lujan. A Study of a Transactional Parallel + Routing Algorithm. Proceedings of the 16th International Conference on + Parallel Architectures and Compilation Techniques, 2007. + diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Router.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Router.java new file mode 100644 index 00000000..a9131fd9 --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Router.java @@ -0,0 +1,456 @@ +/* ============================================================================= + * + * Router.java + * + * ============================================================================= + * + * Copyright (C) Stanford University, 2006. All Rights Reserved. + * Author: Chi Cao Minh + * + * Ported to Java + * Author: Jihoon Lee + * University of California, Irvine + * + * ============================================================================= + * + * 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 MOMENTUM_ZERO 0 +//#define MOMENTUM_POSX 1 +//#define MOMENTUM_POSY 2 +//#define MOMENTUM_POSZ 3 +//#define MOMENTUM_NEGX 4 +//#define MOMENTUM_NEGY 5 +//#define MOMENTUM_NEGZ 6 +//#define GRID_POINT_FULL -2 +//#define GRID_POINT_EMPTY -1 + +public class Router { + private static int MOMENTUM_ZERO; + private static int MOMENTUM_POSX; + private static int MOMENTUM_POSY; + private static int MOMENTUM_POSZ; + private static int MOMENTUM_NEGX; + private static int MOMENTUM_NEGY; + private static int MOMENTUM_NEGZ; + private static int GRID_POINT_FULL; + private static int GRID_POINT_EMPTY; + + + public int xCost; + public int yCost; + public int zCost; + public int bendCost; + public static Point MOVE_POSX; + public static Point MOVE_POSY; + public static Point MOVE_POSZ; + public static Point MOVE_NEGX; + public static Point MOVE_NEGY; + public static Point MOVE_NEGZ; + + public Router() + { + //Replaced #defines + MOMENTUM_ZERO = 0; + MOMENTUM_POSX = 1; + MOMENTUM_POSY = 2; + MOMENTUM_POSZ = 3; + MOMENTUM_NEGX = 4; + MOMENTUM_NEGY = 5; + MOMENTUM_NEGZ = 6; + GRID_POINT_FULL = -2; + GRID_POINT_EMPTY = -1; + + } + +/* ============================================================================= + * router_alloc + * ============================================================================= + * router_t* router_alloc (long xCost, long yCost, long zCost, long bendCost); + */ + public static Router alloc(int xCost,int yCost,int zCost,int bendCost) + { + Router routerPtr = new Router(); + + //added lines of code to account for the #defines + routerPtr.MOVE_POSX = new Point(1,0,0,0, routerPtr.MOMENTUM_POSX); + routerPtr.MOVE_POSY = new Point(0,1,0,0, routerPtr.MOMENTUM_POSY); + routerPtr.MOVE_POSZ = new Point(0,0,1,0, routerPtr.MOMENTUM_POSZ); + routerPtr.MOVE_NEGX = new Point(-1,0,0,0, routerPtr.MOMENTUM_NEGX); + routerPtr.MOVE_NEGY = new Point(0,-1,0,0, routerPtr.MOMENTUM_NEGY); + routerPtr.MOVE_NEGZ = new Point(0,0,-1,0, routerPtr.MOMENTUM_NEGZ); + + if(routerPtr != null) { + routerPtr.xCost = xCost; + routerPtr.yCost = yCost; + routerPtr.zCost = zCost; + routerPtr.bendCost = bendCost; + } + + return routerPtr; + } + + + + +/* ============================================================================= + * router_free + * ============================================================================= + * void router_free (router_t* routerPtr); + */ + public static void free(Router routerPtr) + { + routerPtr = null; + } + +/* ============================================================================ + * PexpandToneighbor + * ============================================================================ + */ + private void PexpandToNeighbor(Grid myGridPtr, + int x,int y,int z, int value,Queue_Int queuePtr) + { + if (myGridPtr.isPointValid(x,y,z)) { + int neighborGridPointIndex = myGridPtr.getPointIndex(x,y,z); + int neighborValue = myGridPtr.points_unaligned[neighborGridPointIndex][0]; + if (neighborValue == GRID_POINT_EMPTY) { + myGridPtr.points_unaligned[neighborGridPointIndex][0] = value; + queuePtr.queue_push(neighborGridPointIndex); + } else if (neighborValue != GRID_POINT_FULL) { + + if (value < neighborValue) { + myGridPtr.points_unaligned[neighborGridPointIndex][0] = value; + queuePtr.queue_push(neighborGridPointIndex); + } + } + } + } + + +/* ============================================================================ + * PdoExpansion + * ============================================================================ + */ + public boolean PdoExpansion (Router routerPtr,Grid myGridPtr,Queue_Int queuePtr, + Coordinate srcPtr,Coordinate dstPtr) + { + int xCost = routerPtr.xCost; + int yCost = routerPtr.yCost; + int zCost = routerPtr.zCost; + + /* + * Potential Optimization: Make 'src' the one closet to edge. + * This will likely decrease the area of the emitted wave. + */ + + queuePtr.queue_clear(); + + int srcGridPointIndex = myGridPtr.getPointIndex(srcPtr.x,srcPtr.y,srcPtr.z); + + queuePtr.queue_push(srcGridPointIndex); + // System.out.println("dstPtr :\tx = " + dstPtr.x + "\ty = " + dstPtr.y + "\tz = " + dstPtr.z); + myGridPtr.setPoint(srcPtr.x,srcPtr.y,srcPtr.z,0); + myGridPtr.setPoint(dstPtr.x,dstPtr.y,dstPtr.z,GRID_POINT_EMPTY); + int dstGridPointIndex = myGridPtr.getPointIndex(dstPtr.x,dstPtr.y,dstPtr.z); + boolean isPathFound = false; + int[] x = new int[1]; + int[] y = new int[1]; + int[] z = new int[1]; + + while (!queuePtr.queue_isEmpty()) { + int gridPointIndex = queuePtr.queue_pop(); + +// System.out.println("gridPointIndex = " +gridPointIndex); + if(gridPointIndex == dstGridPointIndex) { + isPathFound = true; + break; + } + + myGridPtr.getPointIndices(gridPointIndex,x,y,z); + int value = myGridPtr.points_unaligned[gridPointIndex][0]; + + /* + * Check 6 neighbors + * + * Potential Optimization: Only need to check 5 of these + */ + PexpandToNeighbor(myGridPtr, x[0]+1, y[0], z[0], (value + xCost), queuePtr); + PexpandToNeighbor(myGridPtr, x[0]-1, y[0], z[0], (value + xCost), queuePtr); + PexpandToNeighbor(myGridPtr, x[0], y[0]+1, z[0], (value + yCost), queuePtr); + PexpandToNeighbor(myGridPtr, x[0], y[0]-1, z[0], (value + yCost), queuePtr); + PexpandToNeighbor(myGridPtr, x[0], y[0], z[0]+1, (value + zCost), queuePtr); + PexpandToNeighbor(myGridPtr, x[0], y[0], z[0]-1, (value + zCost), queuePtr); + + } /* iterate over work queue */ + + return isPathFound; + } + + +/* ============================================================================ + * traceToNeighbor + * ============================================================================ + */ + private void traceToNeighbor(Grid myGridPtr, + Point currPtr, + Point movePtr, + boolean useMomentum, + int bendCost, + Point nextPtr) + { + int x = currPtr.x + movePtr.x; + int y = currPtr.y + movePtr.y; + int z = currPtr.z + movePtr.z; + + if (myGridPtr.isPointValid(x,y,z) && + !myGridPtr.isPointEmpty(x,y,z) && + !myGridPtr.isPointFull(x,y,z)) + { + int value = myGridPtr.getPoint(x,y,z); + int b = 0; + + if (useMomentum && (currPtr.momentum != movePtr.momentum)) { + b = bendCost; + } + if ((value + b) <= nextPtr.value) { /* '=' favors neighbors over current */ + nextPtr.x = x; + nextPtr.y = y; + nextPtr.z = z; + nextPtr.value = value; + nextPtr.momentum = movePtr.momentum; + } + } + } +/* ============================================================================= + * PdoTraceback + * ============================================================================= + */ + + private Vector_t PdoTraceback(Grid gridPtr,Grid myGridPtr, + Coordinate dstPtr, int bendCost) + { + Vector_t pointVectorPtr = Vector_t.vector_alloc(1); + + Point next = new Point(); + next.x = dstPtr.x; + next.y = dstPtr.y; + next.z = dstPtr.z; + next.value = myGridPtr.getPoint(next.x,next.y,next.z); + next.momentum = MOMENTUM_ZERO; + + while(true) { + int gridPointIndex = gridPtr.getPointIndex(next.x,next.y,next.z); + pointVectorPtr.vector_pushBack(new Integer(gridPointIndex)); + myGridPtr.setPoint(next.x,next.y,next.z,GRID_POINT_FULL); + + /* Check if we are done */ + if (next.value == 0) { + break; + } + Point curr = new Point(); + curr.x = next.x; + curr.y = next.y; + curr.z = next.z; + curr.value = next.value; + curr.momentum = next.momentum; + + /* + * Check 6 neibors + */ + + traceToNeighbor(myGridPtr,curr,MOVE_POSX,true, bendCost, next); + traceToNeighbor(myGridPtr,curr,MOVE_POSY,true, bendCost, next); + traceToNeighbor(myGridPtr,curr,MOVE_POSZ,true, bendCost, next); + traceToNeighbor(myGridPtr,curr,MOVE_NEGX,true, bendCost, next); + traceToNeighbor(myGridPtr,curr,MOVE_NEGY,true, bendCost, next); + traceToNeighbor(myGridPtr,curr,MOVE_NEGZ,true, bendCost, next); + + /* + * Because of bend costs, none of the neighbors may appear to be closer. + * In this case, pick a neighbor while ignoring momentum. + */ + +// System.out.println("next x = " + next.x + " y = " + next.y + " z = " + next.z); + + if ((curr.x == next.y) && + (curr.y == next.y) && + (curr.z == next.z)) + { + next.value = curr.value; + traceToNeighbor(myGridPtr,curr,MOVE_POSX,false, bendCost, next); + traceToNeighbor(myGridPtr,curr,MOVE_POSY,false, bendCost, next); + traceToNeighbor(myGridPtr,curr,MOVE_POSZ,false, bendCost, next); + traceToNeighbor(myGridPtr,curr,MOVE_NEGX,false, bendCost, next); + traceToNeighbor(myGridPtr,curr,MOVE_NEGY,false, bendCost, next); + traceToNeighbor(myGridPtr,curr,MOVE_NEGZ,false, bendCost, next); + + if ((curr.x == next.x) && + (curr.y == next.y) && + (curr.z == next.z)) + { + pointVectorPtr.vector_free(); + System.out.println("Dead"); + return null; + } + } + } + + return pointVectorPtr; + } + +/* ============================================================================= + * router_solve + * ============================================================================= + * void router_solve (void* argPtr); + */ + public static void solve(Object argPtr) + { + // TM_THREAD_ENTER(); + // + Solve_Arg routerArgPtr = (Solve_Arg) argPtr; + Router routerPtr = routerArgPtr.routerPtr; + Maze mazePtr = routerArgPtr.mazePtr; + Vector_t myPathVectorPtr = Vector_t.vector_alloc(1); + + Queue_t workQueuePtr = mazePtr.workQueuePtr; + Grid gridPtr = mazePtr.gridPtr; + Grid myGridPtr = Grid.alloc(gridPtr.width,gridPtr.height,gridPtr.depth); + int bendCost = routerPtr.bendCost; + Queue_Int myExpansionQueuePtr = Queue_Int.queue_alloc(-1); + + /* + * Iterate over work list to route each path. This involves an + * 'expansion' and 'tracback' phase for each source/destination pair. + */ + while(true) { + Pair coordinatePairPtr; + + // TM_BEGIN(); +// atomic { + if(workQueuePtr.queue_isEmpty()) { + coordinatePairPtr = null; + } else { + coordinatePairPtr = (Pair)workQueuePtr.queue_pop(); + } +// } + // TM_END(); + // + + if (coordinatePairPtr == null) { + break; + } + + Coordinate srcPtr = (Coordinate)coordinatePairPtr.first; + Coordinate dstPtr = (Coordinate)coordinatePairPtr.second; + +// System.out.println("SRC x = " + srcPtr.x + " y = " + srcPtr.y + " z = " +srcPtr.z); + + boolean success = false; + Vector_t pointVectorPtr = null; + + + // TM_BEGIN(); +// atomic { + Grid.copy(myGridPtr, gridPtr); /* ok if not most up-to-date */ + + if(routerPtr.PdoExpansion(routerPtr,myGridPtr,myExpansionQueuePtr,srcPtr,dstPtr)) { + pointVectorPtr = routerPtr.PdoTraceback(gridPtr,myGridPtr,dstPtr,bendCost); + + if (pointVectorPtr != null) { + gridPtr.TM_addPath(pointVectorPtr); + success = true; + } + + } +// } + + if(success) { + boolean status = myPathVectorPtr.vector_pushBack(pointVectorPtr); + + if(!status) { + System.out.println("Assert in Router_Solve"); + System.exit(1); + } + } + } + + /* + * Add my paths to global list + */ + List_t pathVectorListPtr = routerArgPtr.pathVectorListPtr; + +// atomic { + pathVectorListPtr.insert(myPathVectorPtr); +// } + + myGridPtr = null; + myExpansionQueuePtr = null; +// System.out.println("Final Grid: "); +// gridPtr.print(); + + // TM_THREAD_EXIT(); + } +} +/* ============================================================================= + * + * End of router.java + * + * ============================================================================= + */ diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Solve_Arg.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Solve_Arg.java new file mode 100644 index 00000000..27df282c --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Solve_Arg.java @@ -0,0 +1,15 @@ + + + public class Solve_Arg { + Router routerPtr; + Maze mazePtr; + List_t pathVectorListPtr; + + public Solve_Arg(Router r,Maze m,List_t l) + { + routerPtr = r; + mazePtr = m; + pathVectorListPtr = l; + } + } + diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Vector_t.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Vector_t.java new file mode 100644 index 00000000..91138e73 --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/Vector_t.java @@ -0,0 +1,156 @@ +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 static Vector_t vector_alloc (int initCapacity) { + int capacity = Math.imax(initCapacity, 1); + Vector_t vectorPtr = new Vector_t(); + if(vectorPtr != null) { + vectorPtr.size = 0; + vectorPtr.capacity = capacity; + vectorPtr.elements = new Object[capacity]; + if(vectorPtr.elements == null) + return null; + } + return vectorPtr; + } + + /* ============================================================================= + * Vector_free + * ============================================================================= + */ + public void + vector_free () + { + elements = null; + } + + /* ============================================================================= + * 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]; + + //void** newElements = (void**)malloc(newCapacity * sizeof(void*)); + if (newElements == null) { + return false; + } + 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]; + + if (elements == null) { + return false; + } + 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/Java-Single/Labyrinth/Original/Normal_Java/extractLines b/Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/extractLines new file mode 100644 index 00000000..c75e5726 --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/Original/Normal_Java/extractLines @@ -0,0 +1,3 @@ +#!/bin/sh +lines=$(grep -n "#" $1 | cut -d: -f1 | sed '1q') +sed '/^#/d' $1 > ttt$1 diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/CoordPathWrapper.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/CoordPathWrapper.java new file mode 100644 index 00000000..70851303 --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/CoordPathWrapper.java @@ -0,0 +1,12 @@ + +public class CoordPathWrapper { + Pair coordinatePair; + Vector_t thePath; + + public CoordPathWrapper(Pair coordinatePairPtr, Vector_t path) { + coordinatePair = coordinatePairPtr; + thePath = path; + + } + +} diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Coordinate.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Coordinate.java new file mode 100644 index 00000000..abbd71ac --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Coordinate.java @@ -0,0 +1,178 @@ +/* ============================================================================= + * + * coordinate.java + * + * ============================================================================= + * + * 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. + * + * ============================================================================= + */ + + + + +import java.lang.Math; + +public class Coordinate { + + public int x; + public int y; + public int z; + + public Coordinate() {} + + + // coordiate_alloc will be constructor + // coordinate_t* coordinate_alloc(long x, long y, long z) + public Coordinate(int x,int y,int z) { + this.x = x; + this.y = y; + this.z = z; + } + + public Coordinate alloc(int x,int y,int z) { + Coordinate c = new Coordinate(x,y,z); + + return c; + } + + + // deallocate memory + // may not need + // coordinate_free + + /*======================================================== + // coordinate_isEqual + ==========================================================*/ + public static boolean isEqual(Coordinate a,Coordinate b) + { + if((a.x == b.x) && (a.y == b.y) && (a.z == b.z)) + return true; + + return false; + } + + /*========================================================== + * + * getPairDistance + * + *========================================================*/ + private static double getPairDistance(Pair p) + { + Coordinate a = (Coordinate)p.first; + Coordinate b = (Coordinate)p.second; + int dx = a.x - b.x; + int dy = a.y - b.y; + int dz = a.z - b.z; + int dx2 = dx* dx; + int dy2 = dy* dy; + int dz2 = dz* dz; + + return Math.sqrt((double)(dx2+dy2+dz2)); + } + + + /*================================================ + // coordinat_ comparePair + * -- For sorting in list of source/destination pairs + * -- Route longer paths first so they are more likely to suceed + + *================================================*/ + public static int comparePair(final Object a,final Object b) + { + double aDistance = getPairDistance((Pair)a); + double bDistance = getPairDistance((Pair)b); + + if(aDistance < bDistance) { + return 1; + } else if(aDistance > bDistance) { + return -1; + } + + return 0; + } + + /*======================================================= + * coordinate_areAdjacent + *=======================================================*/ + + public static boolean areAdjacent(Coordinate a,Coordinate b) + { + int dx = a.x - b.x; + int dy = a.y - b.y; + int dz = a.z - b.z; + int dx2 = dx * dx; + int dy2 = dy * dy; + int dz2 = dz * dz; + + return (((dx2 + dy2 + dz2) == 1) ? true : false); + } + } + + /*===================================================== + * + * End of Coordinate + * + *====================================================*/ + + diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Grid.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Grid.java new file mode 100644 index 00000000..ed94a767 --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Grid.java @@ -0,0 +1,307 @@ + + +//#define GRID_POINT_FULL -2 +//#define GRID_POINT_EMPTY -1 + + + +public class Grid +{ + //TODO change these back into #defines up top + private static int GRID_POINT_FULL; + private static int GRID_POINT_EMPTY; + + + public int width; + public int height; + public int depth; + public int[][] points_unaligned; + + public Grid() + { + //Kept from #defines + GRID_POINT_FULL = -2; + GRID_POINT_EMPTY =-1; + } + + +/* ============================================================================= + * grid_alloc + * ============================================================================= + grid_t* grid_alloc (long width, long height, long depth); + + well... need to implement + got stuck + */ + public Grid alloc(int width,int height,int depth) { + Grid grid = new Grid(); + + if(grid != null) { + + grid.width = width; + grid.height = height; + grid.depth = depth; + + int n = width * height * depth; + + // long* points_unaligned = (long*) malloc(n*sizeof(long) + CACHE_LINE_SIZE); + int[][] points_unaligned = new int[n][1]; + + grid.points_unaligned = points_unaligned; + + for(int i=0;i= width || + y < 0 || y >= height || + z < 0 || z >= depth) + { + return false; + } + + return true; + } + + +/* ============================================================================= + * grid_getPointRef + * ============================================================================= +long* grid_getPointRef (grid_t* gridPtr, long x, long y, long z); + + it is returning the index of the point +*/ + public int getPointIndex(int x,int y,int z) + { + return ((z * height) + y) * width + x; + } + + +/* ============================================================================= + * grid_getPointIndices + * ============================================================================= + void grid_getPointIndices (grid_t* gridPtr, + long* gridPointPtr, long* xPtr, long* yPtr, long* zPtr); + */ + public void getPointIndices(int gridPointIndex,int[] xPtr, int[] yPtr,int[] zPtr) + { + int height = this.height; + int width = this.width; + int area = height * width; + int index3d = (gridPointIndex); + zPtr[0] = index3d / area; + int index2d = index3d % area; + yPtr[0] = index2d / width; + xPtr[0] = index2d % width; + } + + +/* ============================================================================= + * grid_getPoint + * ============================================================================= + long grid_getPoint (grid_t* gridPtr, long x, long y, long z); + */ + public int getPoint(int x,int y,int z) + { + return this.points_unaligned[getPointIndex(x,y,z)][0]; + } + + public int getPoint(int index) + { + return this.points_unaligned[index][0]; + } + + + + + + //added to support redos + public Coordinate getCoordinate(int index) + { + //((z * height) + y) * width + x; + Coordinate c = new Coordinate(); + int x = index % width; + int y = (index/width)%height; + int z = (index/width)/height; + + //TODO remove after debugging + if(index != this.getPoint(x, y, z)) + System.out.println("getCordinate() in Grid.java FAILS..."); + + return c.alloc(x, y, z); + } + +/* ============================================================================= + * grid_isPointEmpty + * ============================================================================= + bool_t grid_isPointEmpty (grid_t* gridPtr, long x, long y, long z); + */ + public boolean isPointEmpty(int x,int y,int z) + { + int value = getPoint(x,y,z); + return ((value == GRID_POINT_EMPTY) ? true:false); + } + + + +/* ============================================================================= + * grid_isPointFull + * ============================================================================= + bool_t grid_isPointFull (grid_t* gridPtr, long x, long y, long z); + */ + public boolean isPointFull(int x,int y,int z) + { + int value = getPoint(x,y,z); + return ((value == GRID_POINT_FULL) ? true : false); + } + + +/* ============================================================================= + * grid_setPoint + * ============================================================================= + void grid_setPoint (grid_t* gridPtr, long x, long y, long z, long value); + */ + public void setPoint(int x,int y,int z,int value) + { + points_unaligned[getPointIndex(x,y,z)][0] = value; + } + + +/* ============================================================================= + * grid_addPath + * ============================================================================= + +void grid_addPath (grid_t* gridPtr, vector_t* pointVectorPtr); +*/ + + public void addPath(Vector_t pointVectorPtr) + { + int i; + int n = pointVectorPtr.vector_getSize(); + + for(i = 0; i < n; i++) { + Coordinate coordinatePtr = (Coordinate)pointVectorPtr.vector_at(i); + int x = coordinatePtr.x; + int y = coordinatePtr.y; + int z = coordinatePtr.z; + +// System.out.println("x = " + x + " y = " + y + " z = " + z); + setPoint(x,y,z,GRID_POINT_FULL); + } + } + + public void TM_addPath(Vector_t pointVectorPtr) + { + int i; + int n = pointVectorPtr.vector_getSize(); + + for(i = 0; i < n; i++) { + int gridPointIndex = ((Integer)(pointVectorPtr.vector_at(i))).intValue(); + points_unaligned[gridPointIndex][0] = GRID_POINT_FULL; + } + } + +/* ============================================================================= + * TMgrid_addPath + * ============================================================================= + TM_CALLABLE +void +TMgrid_addPath (TM_ARGDECL grid_t* gridPtr, vector_t* pointVectorPtr); +*/ + + +/* ============================================================================= + * grid_print + * ============================================================================= +void grid_print (grid_t* gridPtr); +*/ + public void print() + { + int z; + + for(z = 0; z < depth; z++) { + System.out.println("[z = " + z + "]"); + int x; + for(x = 0; x < width; x++) { + int y; + for(y = 0; y < height; y++) { + System.out.print(points_unaligned[getPointIndex(x,y,z)][0] + " "); + } + System.out.println(""); + } + System.out.println(""); + } + + } +} + +/* ============================================================================= + * + * End of grid.c + * + * ============================================================================= + */ diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Labyrinth.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Labyrinth.java new file mode 100644 index 00000000..500bc1dc --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Labyrinth.java @@ -0,0 +1,237 @@ +/* ============================================================================= + * + * Labyrinth.java + * + * ============================================================================= + * + * 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 Labyrinth{ + + static String global_inputFile; + static boolean global_doPrint; + static int global_workload; + int numThread; + int bendCost; + int xCost; + int yCost; + int zCost; + + + // For threads + int threadID; + Solve_Arg routerArg; + + private void setDefaultParams() { + + /* default values */ + global_inputFile = null; + global_doPrint = false; + bendCost = 1; + xCost = 1; + yCost = 1; + zCost = 2; + numThread = 1; + global_workload = 20; + } + + private void parseArg(String[] argv) { + int i=0; + String arg; + boolean opterr = false; + + + setDefaultParams(); + + while (i < argv.length) { + + if(argv[i].charAt(0) == '-' ) { + arg = argv[i++]; + // check options + if(arg.equals("-b")) { + bendCost = Integer.parseInt(argv[i++]); + } + else if(arg.equals("-x")) { + xCost = Integer.parseInt(argv[i++]); + } + else if(arg.equals("-y")) { + yCost = Integer.parseInt(argv[i++]); + } + else if(arg.equals("-z")) { + zCost = Integer.parseInt(argv[i++]); + } + else if(arg.equals("-t")) { + numThread = Integer.parseInt(argv[i++]); + } + else if(arg.equals("-i")) { + global_inputFile = argv[i++]; + } + else if(arg.equals("-p")) { + global_doPrint = true; + } + else if(arg.equals("-w")){ + global_workload = Integer.parseInt(argv[i++]); + } + else { + System.out.println("Non-option argument: " + argv[i]); + opterr = true; + } + + } + } + if(opterr) { + displayUsage(); + System.exit(1); + } + } + + public Labyrinth(String[] argv) + { + parseArg(argv); + } + + + public Labyrinth(int myID,Solve_Arg rArg) + { + threadID = myID; + routerArg = rArg; + } + + public Labyrinth() {} + + public void displayUsage() + { + System.out.println("Usage: Labyrinth [options]"); + System.out.println("Options:"); + System.out.println(" b bend cost"); + System.out.println(" i input file name"); + System.out.println(" p print routed maze"); + System.out.println(" t Number of threads (depricated)"); + System.out.println(" w Workload per rBlock"); + System.out.println(" x x movement cost"); + System.out.println(" y y movement cost"); + System.out.println(" z z movement cost"); + } + + + public static void main(String[] argv) + { + //parse arguments + Labyrinth labyrinth = new Labyrinth(argv); + + Maze maze = new Maze(); + Maze mazePtr = maze.alloc(); + + //parse maze/grid + int numPathToRoute = mazePtr.readMaze(labyrinth.global_inputFile); + + + Router routerPtr = Router.alloc(labyrinth.xCost,labyrinth.yCost, + labyrinth.zCost,labyrinth.bendCost); + + List_t pathVectorListPtr = List_t.alloc(0); + + Solve_Arg routerArg = new Solve_Arg(routerPtr,mazePtr,pathVectorListPtr); + + /* Start */ + long start = System.currentTimeMillis(); + + //rblocks are handled within Router. + Router.solve(routerArg); + + /* End of Solve */ + long finish = System.currentTimeMillis(); + + + int numPathRouted = 0; + List_Iter it = new List_Iter(); + + it.reset(pathVectorListPtr); + while(it.hasNext(pathVectorListPtr)) { + Vector_t pathVectorPtr = (Vector_t)it.next(pathVectorListPtr); + numPathRouted += pathVectorPtr.vector_getSize(); + } + + double elapsed = ((double)finish-(double)start)/1000; + + System.out.println("Paths routed = " + numPathRouted); + System.out.println("Elapsed time = " + elapsed); + + boolean stats = mazePtr.checkPaths(pathVectorListPtr,labyrinth.global_doPrint); + if(!stats) + System.out.println("Verification not passed"); + else + System.out.println("Verification passed."); + + System.out.println("Finished"); + } +} + +/* ============================================================================= + * + * End of labyrinth.c + * + * ============================================================================= + */ diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/List_Iter.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/List_Iter.java new file mode 100644 index 00000000..351e80d0 --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/List_Iter.java @@ -0,0 +1,38 @@ +public class List_Iter { + List_Node itPtr; + + /* ============================================================================= + * list_iter_reset + * ============================================================================= + void list_iter_reset (list_iter_t* itPtr, list_t* listPtr); + */ + public List_Iter() { + itPtr = null; + } + + public void reset(List_t listPtr) + { + itPtr = listPtr.head; + } + + /* ============================================================================= + * list_iter_hasNext + * ============================================================================= + * bool_t list_iter_hasNext (list_iter_t* itPtr, list_t* listPtr); + */ + public boolean hasNext(List_t listPtr) { + return (itPtr.nextPtr != null)? true : false; + } + + /* ============================================================================= + * list_iter_next + * ============================================================================= + * void* list_iter_next (list_iter_t* itPtr, list_t* listPtr); + */ + public Object next(List_t listPtr) + { + itPtr = itPtr.nextPtr; + return itPtr.dataPtr; + } +} + diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/List_Node.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/List_Node.java new file mode 100644 index 00000000..806baa19 --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/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/Java-Single/Labyrinth/mlp/Normal_Java/List_t.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/List_t.java new file mode 100644 index 00000000..93593966 --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/List_t.java @@ -0,0 +1,312 @@ +/* ============================================================================= + * + * 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; + boolean isCoordinate; + 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(int isCoordinate) + { + List_t listPtr = new List_t(); + + if(listPtr == null) { + return null; + } + + listPtr.head.dataPtr = null; + listPtr.head.nextPtr = null; + listPtr.size = 0; + + listPtr.isCoordinate = (isCoordinate==1)?true:false; + + 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) + { + if(isCoordinate) + { + return Coordinate.comparePair(obj1,obj2); + } + else + return compareObject(obj1,obj2); + } + +/* ============================================================================= + * 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/Java-Single/Labyrinth/mlp/Normal_Java/Math.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Math.java new file mode 100644 index 00000000..7e6a59f6 --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Math.java @@ -0,0 +1,136 @@ +public class Math { + + public static double setPI() { + double PI = 3.14159265358979323846; + return PI; + } + + // an alias for setPI() + public static double PI() { + double PI = 3.14159265358979323846; + return PI; + } + + public static int abs(int x) { + if (x < 0) { + return -x; + } else { + return x; + } + } + + public static double fabs(double x) { + if (x < 0) { + return -x; + } else { + return x; + } + } + + public static double abs(double x) { + if (x < 0) { + return -x; + } else { + return x; + } + } + + public static float abs(float a) { + if (a<0) + return -a; + else return a; + } + + public static double max(double a, double b) { + if(a == b) + return a; + if(a > b) { + return a; + } else { + return b; + } + } + + public static int max(int a, int b) { + if(a == b) + return a; + if(a > b) { + return a; + } else { + return b; + } + } + + public static int imax(int a, int b) { + if(a == b) + return a; + if(a > b) { + return a; + } else { + return b; + } + } + + public static int imin(int a, int b) { + if(a == b) + return a; + if(a > b) { + return b; + } else { + return a; + } + } + + /** sqrt(a^2 + b^2) without under/overflow. **/ + public static double hypot(double a, double b) { + double r; + if (fabs(a) > fabs(b)) { + r = b/a; + r = fabs(a)*sqrt(1+r*r); + } else if (b != 0) { + r = a/b; + r = fabs(b)*sqrt(1+r*r); + } else { + r = 0.0; + } + return r; + } + + public static double rint(double x) { + double y = ceil(x); + double d = y - x; + if( d == 0.5 ) { + if( ((int)y)%2 == 0 ) { + return y; + } else { + return y - 1.0; + } + } else if( d < 0.5 ) { + return y; + } + return y - 1.0; + } + + public static native double sin(double a); + public static native double cos(double a); + public static native double asin(double a); + public static native double acos(double a); + public static native double tan(double a); + public static native double atan(double a); + public static native double atan2(double a, double b); + public static native double exp(double a); + public static native double sqrt(double a); + public static native double log(double a); + public static native double pow(double a, double b); + + public static native double ceil(double a); + public static native double floor(double a); + + public static native float sinf(float a); + public static native float cosf(float a); + public static native float expf(float a); + public static native float sqrtf(float a); + public static native float logf(float a); + public static native float powf(float a, float b); + public static native float ceilf(float a); +} diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Maze.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Maze.java new file mode 100644 index 00000000..2180ed5f --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Maze.java @@ -0,0 +1,508 @@ +import java.io.File; +import java.util.Scanner; +import java.util.StringTokenizer; + +/*============================================================================= + * + * Maze.java + * + * ============================================================================= + * + * 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. + * + * ============================================================================= + */ + +//#define GRID_POINT_FULL -2 +//#define GRID_POINT_EMPTY -1 + +//TODO change these back and delete class variables. + +public class Maze +{ + private static int GRID_POINT_FULL; + private static int GRID_POINT_EMPTY; + + Grid gridPtr; + Queue_t workQueuePtr; + Vector_t wallVectorPtr; /* contains source/destination pairs to route */ + Vector_t srcVectorPtr; /* obstacles */ + Vector_t dstVectorPtr; /* destinations */ + + public Maze() + { + //these were changed from #defines + GRID_POINT_FULL = -2; + GRID_POINT_EMPTY = -1; + } + + +/* ============================================================================= + * maze_alloc + * ============================================================================= + maze_t* maze_alloc (); + */ + public Maze alloc() + { + Maze mazePtr = new Maze(); + + if(mazePtr != null) { + Vector_t vector_t = new Vector_t(); + Queue_t queue_t = new Queue_t(); + + mazePtr.gridPtr = null; + mazePtr.workQueuePtr = queue_t.queue_alloc(1024); + mazePtr.wallVectorPtr = vector_t.vector_alloc(1); + mazePtr.srcVectorPtr = vector_t.vector_alloc(1); + mazePtr.dstVectorPtr = vector_t.vector_alloc(1); + + } + + return mazePtr; + } + +/* ============================================================================= + * maze_free + * ============================================================================= + void maze_free (maze_t* mazePtr); + */ + public static void free(Maze m) + { + m = null; + } + +/* ============================================================================= + * addToGrid + * ============================================================================= + */ + private void addToGrid(Grid gridPtr,Vector_t vectorPtr,String type) + { + int i; + int n = vectorPtr.vector_getSize(); + + for(i = 0; i < n; i++) { + Coordinate coordinatePtr = (Coordinate)vectorPtr.vector_at(i); + if(!gridPtr.isPointValid(coordinatePtr.x,coordinatePtr.y,coordinatePtr.z)) + { + System.out.println("Error: " + type + " (" + coordinatePtr.x + + ", " + coordinatePtr.y + + ", " + coordinatePtr.z); + System.exit(1); + } + } + gridPtr.addPath(vectorPtr); + } +/* ============================================================================= + * maze_read + * -- Return number of path to route + * ============================================================================= + long maze_read (maze_t* mazePtr, char* inputFileName); + */ + public int readMaze(String inputFileName) + { + + //TODO remove TRY + try + { + Coordinate coordinate = new Coordinate(); +// FileInputStream in = new FileInputStream(inputFileName); + //TODO remove this and uncomment the line above. + Scanner in = new Scanner(new File(inputFileName)); + + /* + * Parse input file + */ + int lineNumber = 0; + int height = -1; + int width = -1; + int depth = -1; + boolean isParseError = false; + List_t workListPtr = List_t.alloc(1); // List.alloc(Coordinate.comparePair); + String line; + + //TODO change this back as well +// while((line = in.readLine()) != null) { + while(in.hasNextLine()) + { + + line = in.nextLine(); + + String code; + int[] xy = new int[6]; // equivalent to x1,y1,z1,x2,y2,z2 + int numToken = 0; + + StringTokenizer tok = new StringTokenizer(line); + + if((numToken = tok.countTokens()) < 1 ) { + continue; + } + + code = tok.nextToken(); + + if(code.equals("#")) { + /* comment line */ + continue; + } + for(int i=0;i + +in the source directory. For example, for the sequential flavor, run: + + make -f Makefile.seq + +By default, this produces an executable named "labyrinth", which can then be +run in the following manner: + + ./labyrinth -i + +The following input file is recommended for simulated runs: + + ./labyrinth -i inputs/random-x32-y32-z3-n96.txt + +For non-simulator runs, a larger input can be used: + + ./labyrinth -i inputs/random-x512-y512-z7-n512.txt + + +Input Files +----------- + +More input sets can be generated by using "inputs/generate.py". For example, + + inputs/generate.py 128 128 3 64 + +Will create a 128x128x3 maze grid and select 64 uniformly random start/end +point pairs. + + +References +---------- + +[1] C. Cao Minh, J. Chung, C. Kozyrakis, and K. Olukotun. STAMP: Stanford + Transactional Applications for Multi-processing. In IISWC '08: Proceedings + of The IEEE International Symposium on Workload Characterization, + September 2008. + +[2] C. Lee. An algorithm for path connections and its applications. IRE Trans. + On Electronic Computers, 1961. + +[3] I. Watson, C. Kirkham, and M. Lujan. A Study of a Transactional Parallel + Routing Algorithm. Proceedings of the 16th International Conference on + Parallel Architectures and Compilation Techniques, 2007. + diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Pair.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Pair.java new file mode 100644 index 00000000..92db5229 --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Pair.java @@ -0,0 +1,86 @@ + + +public class Pair { + public Object first; + public Object second; + + public Pair() { + first = null; + second = null; + } + + +/* ============================================================================= + * + * pair constructor + * + * pair_t* pair_alloc(void* firstPtr, void* secondPtr); + * ============================================================================= + */ + public static Pair alloc(Object first,Object second) + { + Pair ptr= new Pair(); + ptr.first = first; + ptr.second = second; + + return ptr; + } + + + +/* ============================================================================= + * Ppair_alloc + * + * -- Returns NULL if failure + * ============================================================================= + */ + public static Pair Ppair_alloc (Object firstPtr, Object secondPtr) { + Pair pairPtr = new Pair(); + pairPtr.first = firstPtr; + pairPtr.second = secondPtr; + return pairPtr; + } + + +/* ============================================================================= + * pair_free + * ============================================================================= + * + * void pair_free (pair_t* pairPtr); + * + */ + public static void free(Pair pairPtr) + { + pairPtr = null; + } + + +/* ============================================================================= + * Ppair_free + * ============================================================================= + * +void Ppair_free (pair_t* pairPtr); +*/ + +/* ============================================================================= + * pair_swap + * -- Exchange 'firstPtr' and 'secondPtr' + * ============================================================================= + * void pair_swap (pair_t* pairPtr); +*/ + public static void swap(Pair pairPtr) + { + Object tmpPtr = pairPtr.first; + + pairPtr.first = pairPtr.second; + pairPtr.second = tmpPtr; + } + +} + +/* ============================================================================= + * + * End of pair.java + * + * ============================================================================= + */ diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Point.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Point.java new file mode 100644 index 00000000..8905bd54 --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Point.java @@ -0,0 +1,25 @@ + + public class Point { + int x; + int y; + int z; + int value; + int momentum; + + public Point() { + x = -1; + y = -1; + z = -1; + value = -1; + momentum = -1; + } + + public Point(int x,int y, int z,int value, int m) { + this.x = x; + this.y = y; + this.z = z; + this.value = value; + momentum = m; + } + } + diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Queue_Int.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Queue_Int.java new file mode 100644 index 00000000..a24ced90 --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/Queue_Int.java @@ -0,0 +1,448 @@ +/* ============================================================================= + * + * queue.java + * + * ============================================================================= + * + * Copyright (C) Stanford University, 2006. All Rights Reserved. + * Author: Chi Cao Minh + * + * Ported to Java June 2009 Alokika Dash + * adash@uci.edu + * 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_Int { + + private static int QUEUE_GROWTH_FACTOR; + int pop; /* points before element to pop */ + int push; + int capacity; + int[] elements; + + public Queue_Int() + { + QUEUE_GROWTH_FACTOR = 2; + } + + /* ============================================================================= + * queue_alloc + * ============================================================================= + */ + public static Queue_Int queue_alloc (int initCapacity) + { + Queue_Int queuePtr = new Queue_Int(); + + int capacity = ((initCapacity < 2) ? 2 : initCapacity); + queuePtr.elements = new int[capacity]; + if (queuePtr.elements == null) { + queuePtr = null; + return null; + } + queuePtr.pop = capacity - 1; + queuePtr.push = 0; + queuePtr.capacity = capacity; + + return queuePtr; + } + + + /* ============================================================================= + * Pqueue_alloc + * ============================================================================= + */ + public Queue_Int + Pqueue_alloc (int initCapacity) + { + Queue_Int queuePtr = new Queue_Int(); + + int capacity = ((initCapacity < 2) ? 2 : initCapacity); + queuePtr.elements = new int[capacity]; + if (queuePtr.elements == null) { + queuePtr = null; + return null; + } + queuePtr.pop = capacity - 1; + queuePtr.push = 0; + queuePtr.capacity = capacity; + + return queuePtr; + } + + + /* ============================================================================= + * TMqueue_alloc + * ============================================================================= + */ + public Queue_Int TMqueue_alloc (int initCapacity) + { + Queue_Int queuePtr = new Queue_Int(); + + int capacity = ((initCapacity < 2) ? 2 : initCapacity); + queuePtr.elements = new int[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 () + { + elements = null; + } + + + /* ============================================================================= + * Pqueue_free + * ============================================================================= + */ + public void + Pqueue_free () + { + elements = null; + } + + + /* ============================================================================= + * TMqueue_free + * ============================================================================= + */ + public void + TMqueue_free () + { + elements = null; + } + + + /* ============================================================================= + * queue_isEmpty + * ============================================================================= + */ + public boolean + queue_isEmpty () + { + return (((pop + 1) % capacity == push) ? true : false); + } + + + /* ============================================================================= + * queue_clear + * ============================================================================= + */ + public void + queue_clear () + { + pop = capacity - 1; + push = 0; + } + + + /* ============================================================================= + * TMqueue_isEmpty + * ============================================================================= + */ + public boolean + TMqueue_isEmpty (Queue_Int queuePtr) + { + int pop = queuePtr.pop; + int push = queuePtr.push; + int capacity = queuePtr.capacity; + + return (((pop + 1) % capacity == push) ? true : false); + } + + + /* ============================================================================= + * queue_push + * ============================================================================= + */ + public boolean + queue_push (int 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; + int[] newElements = new int[newCapacity]; + if (newElements == null) { + return false; + } + + int dst = 0; + int[] 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 = 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_Int queuePtr, int 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; + int[] newElements = new int[newCapacity]; + if (newElements == null) { + return false; + } + + int dst = 0; + int[] 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; + } + + + /* ============================================================================= + * TMqueue_push + * ============================================================================= + */ + public boolean + TMqueue_push (Queue_Int queuePtr, int 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; + int[] newElements = new int[newCapacity]; + if (newElements == null) { + return false; + } + + int dst = 0; + int[] 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 */ + + } + + int[] elements = queuePtr.elements; + elements[push] = dataPtr; + queuePtr.push = newPush; + + return true; + } + + + /* ============================================================================= + * queue_pop + * ============================================================================= + */ + public int + queue_pop () + { + int newPop = (pop + 1) % capacity; + if (newPop == push) { + return 0; + } + + int dataPtr = elements[newPop]; + pop = newPop; + + return dataPtr; + } + + + /* ============================================================================= + * TMqueue_pop + * ============================================================================= + */ + public int + TMqueue_pop (Queue_Int queuePtr) + { + int pop = queuePtr.pop; + int push = queuePtr.push; + int capacity = queuePtr.capacity; + + int newPop = (pop + 1) % capacity; + if (newPop == push) { + return 0; + } + + int[] elements = queuePtr.elements; + int dataPtr = elements[newPop]; + queuePtr.pop = newPop; + + return dataPtr; + } + + /**** + * main method for testing + **/ + /* + public static void main(String[] args) { + testQueue queuePtr = testQueue.queue_alloc(-1); + int numData = 4; + if(queuePtr.queue_isEmpty()) + System.out.println("Queue is empty"); + + for(int 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]; + + //void** newElements = (void**)malloc(newCapacity * sizeof(void*)); + if (newElements == null) { + return false; + } + 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]; + + if (elements == null) { + return false; + } + 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/Java-Single/Labyrinth/mlp/Normal_Java/extractLines b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/extractLines new file mode 100644 index 00000000..c75e5726 --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/Normal_Java/extractLines @@ -0,0 +1,3 @@ +#!/bin/sh +lines=$(grep -n "#" $1 | cut -d: -f1 | sed '1q') +sed '/^#/d' $1 > ttt$1 diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/CoordPathWrapper.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/CoordPathWrapper.java new file mode 100644 index 00000000..70851303 --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/CoordPathWrapper.java @@ -0,0 +1,12 @@ + +public class CoordPathWrapper { + Pair coordinatePair; + Vector_t thePath; + + public CoordPathWrapper(Pair coordinatePairPtr, Vector_t path) { + coordinatePair = coordinatePairPtr; + thePath = path; + + } + +} diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Coordinate.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Coordinate.java new file mode 100644 index 00000000..abbd71ac --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Coordinate.java @@ -0,0 +1,178 @@ +/* ============================================================================= + * + * coordinate.java + * + * ============================================================================= + * + * 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. + * + * ============================================================================= + */ + + + + +import java.lang.Math; + +public class Coordinate { + + public int x; + public int y; + public int z; + + public Coordinate() {} + + + // coordiate_alloc will be constructor + // coordinate_t* coordinate_alloc(long x, long y, long z) + public Coordinate(int x,int y,int z) { + this.x = x; + this.y = y; + this.z = z; + } + + public Coordinate alloc(int x,int y,int z) { + Coordinate c = new Coordinate(x,y,z); + + return c; + } + + + // deallocate memory + // may not need + // coordinate_free + + /*======================================================== + // coordinate_isEqual + ==========================================================*/ + public static boolean isEqual(Coordinate a,Coordinate b) + { + if((a.x == b.x) && (a.y == b.y) && (a.z == b.z)) + return true; + + return false; + } + + /*========================================================== + * + * getPairDistance + * + *========================================================*/ + private static double getPairDistance(Pair p) + { + Coordinate a = (Coordinate)p.first; + Coordinate b = (Coordinate)p.second; + int dx = a.x - b.x; + int dy = a.y - b.y; + int dz = a.z - b.z; + int dx2 = dx* dx; + int dy2 = dy* dy; + int dz2 = dz* dz; + + return Math.sqrt((double)(dx2+dy2+dz2)); + } + + + /*================================================ + // coordinat_ comparePair + * -- For sorting in list of source/destination pairs + * -- Route longer paths first so they are more likely to suceed + + *================================================*/ + public static int comparePair(final Object a,final Object b) + { + double aDistance = getPairDistance((Pair)a); + double bDistance = getPairDistance((Pair)b); + + if(aDistance < bDistance) { + return 1; + } else if(aDistance > bDistance) { + return -1; + } + + return 0; + } + + /*======================================================= + * coordinate_areAdjacent + *=======================================================*/ + + public static boolean areAdjacent(Coordinate a,Coordinate b) + { + int dx = a.x - b.x; + int dy = a.y - b.y; + int dz = a.z - b.z; + int dx2 = dx * dx; + int dy2 = dy * dy; + int dz2 = dz * dz; + + return (((dx2 + dy2 + dz2) == 1) ? true : false); + } + } + + /*===================================================== + * + * End of Coordinate + * + *====================================================*/ + + diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Grid.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Grid.java new file mode 100644 index 00000000..ed94a767 --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Grid.java @@ -0,0 +1,307 @@ + + +//#define GRID_POINT_FULL -2 +//#define GRID_POINT_EMPTY -1 + + + +public class Grid +{ + //TODO change these back into #defines up top + private static int GRID_POINT_FULL; + private static int GRID_POINT_EMPTY; + + + public int width; + public int height; + public int depth; + public int[][] points_unaligned; + + public Grid() + { + //Kept from #defines + GRID_POINT_FULL = -2; + GRID_POINT_EMPTY =-1; + } + + +/* ============================================================================= + * grid_alloc + * ============================================================================= + grid_t* grid_alloc (long width, long height, long depth); + + well... need to implement + got stuck + */ + public Grid alloc(int width,int height,int depth) { + Grid grid = new Grid(); + + if(grid != null) { + + grid.width = width; + grid.height = height; + grid.depth = depth; + + int n = width * height * depth; + + // long* points_unaligned = (long*) malloc(n*sizeof(long) + CACHE_LINE_SIZE); + int[][] points_unaligned = new int[n][1]; + + grid.points_unaligned = points_unaligned; + + for(int i=0;i= width || + y < 0 || y >= height || + z < 0 || z >= depth) + { + return false; + } + + return true; + } + + +/* ============================================================================= + * grid_getPointRef + * ============================================================================= +long* grid_getPointRef (grid_t* gridPtr, long x, long y, long z); + + it is returning the index of the point +*/ + public int getPointIndex(int x,int y,int z) + { + return ((z * height) + y) * width + x; + } + + +/* ============================================================================= + * grid_getPointIndices + * ============================================================================= + void grid_getPointIndices (grid_t* gridPtr, + long* gridPointPtr, long* xPtr, long* yPtr, long* zPtr); + */ + public void getPointIndices(int gridPointIndex,int[] xPtr, int[] yPtr,int[] zPtr) + { + int height = this.height; + int width = this.width; + int area = height * width; + int index3d = (gridPointIndex); + zPtr[0] = index3d / area; + int index2d = index3d % area; + yPtr[0] = index2d / width; + xPtr[0] = index2d % width; + } + + +/* ============================================================================= + * grid_getPoint + * ============================================================================= + long grid_getPoint (grid_t* gridPtr, long x, long y, long z); + */ + public int getPoint(int x,int y,int z) + { + return this.points_unaligned[getPointIndex(x,y,z)][0]; + } + + public int getPoint(int index) + { + return this.points_unaligned[index][0]; + } + + + + + + //added to support redos + public Coordinate getCoordinate(int index) + { + //((z * height) + y) * width + x; + Coordinate c = new Coordinate(); + int x = index % width; + int y = (index/width)%height; + int z = (index/width)/height; + + //TODO remove after debugging + if(index != this.getPoint(x, y, z)) + System.out.println("getCordinate() in Grid.java FAILS..."); + + return c.alloc(x, y, z); + } + +/* ============================================================================= + * grid_isPointEmpty + * ============================================================================= + bool_t grid_isPointEmpty (grid_t* gridPtr, long x, long y, long z); + */ + public boolean isPointEmpty(int x,int y,int z) + { + int value = getPoint(x,y,z); + return ((value == GRID_POINT_EMPTY) ? true:false); + } + + + +/* ============================================================================= + * grid_isPointFull + * ============================================================================= + bool_t grid_isPointFull (grid_t* gridPtr, long x, long y, long z); + */ + public boolean isPointFull(int x,int y,int z) + { + int value = getPoint(x,y,z); + return ((value == GRID_POINT_FULL) ? true : false); + } + + +/* ============================================================================= + * grid_setPoint + * ============================================================================= + void grid_setPoint (grid_t* gridPtr, long x, long y, long z, long value); + */ + public void setPoint(int x,int y,int z,int value) + { + points_unaligned[getPointIndex(x,y,z)][0] = value; + } + + +/* ============================================================================= + * grid_addPath + * ============================================================================= + +void grid_addPath (grid_t* gridPtr, vector_t* pointVectorPtr); +*/ + + public void addPath(Vector_t pointVectorPtr) + { + int i; + int n = pointVectorPtr.vector_getSize(); + + for(i = 0; i < n; i++) { + Coordinate coordinatePtr = (Coordinate)pointVectorPtr.vector_at(i); + int x = coordinatePtr.x; + int y = coordinatePtr.y; + int z = coordinatePtr.z; + +// System.out.println("x = " + x + " y = " + y + " z = " + z); + setPoint(x,y,z,GRID_POINT_FULL); + } + } + + public void TM_addPath(Vector_t pointVectorPtr) + { + int i; + int n = pointVectorPtr.vector_getSize(); + + for(i = 0; i < n; i++) { + int gridPointIndex = ((Integer)(pointVectorPtr.vector_at(i))).intValue(); + points_unaligned[gridPointIndex][0] = GRID_POINT_FULL; + } + } + +/* ============================================================================= + * TMgrid_addPath + * ============================================================================= + TM_CALLABLE +void +TMgrid_addPath (TM_ARGDECL grid_t* gridPtr, vector_t* pointVectorPtr); +*/ + + +/* ============================================================================= + * grid_print + * ============================================================================= +void grid_print (grid_t* gridPtr); +*/ + public void print() + { + int z; + + for(z = 0; z < depth; z++) { + System.out.println("[z = " + z + "]"); + int x; + for(x = 0; x < width; x++) { + int y; + for(y = 0; y < height; y++) { + System.out.print(points_unaligned[getPointIndex(x,y,z)][0] + " "); + } + System.out.println(""); + } + System.out.println(""); + } + + } +} + +/* ============================================================================= + * + * End of grid.c + * + * ============================================================================= + */ diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Labyrinth.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Labyrinth.java new file mode 100644 index 00000000..500bc1dc --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Labyrinth.java @@ -0,0 +1,237 @@ +/* ============================================================================= + * + * Labyrinth.java + * + * ============================================================================= + * + * 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 Labyrinth{ + + static String global_inputFile; + static boolean global_doPrint; + static int global_workload; + int numThread; + int bendCost; + int xCost; + int yCost; + int zCost; + + + // For threads + int threadID; + Solve_Arg routerArg; + + private void setDefaultParams() { + + /* default values */ + global_inputFile = null; + global_doPrint = false; + bendCost = 1; + xCost = 1; + yCost = 1; + zCost = 2; + numThread = 1; + global_workload = 20; + } + + private void parseArg(String[] argv) { + int i=0; + String arg; + boolean opterr = false; + + + setDefaultParams(); + + while (i < argv.length) { + + if(argv[i].charAt(0) == '-' ) { + arg = argv[i++]; + // check options + if(arg.equals("-b")) { + bendCost = Integer.parseInt(argv[i++]); + } + else if(arg.equals("-x")) { + xCost = Integer.parseInt(argv[i++]); + } + else if(arg.equals("-y")) { + yCost = Integer.parseInt(argv[i++]); + } + else if(arg.equals("-z")) { + zCost = Integer.parseInt(argv[i++]); + } + else if(arg.equals("-t")) { + numThread = Integer.parseInt(argv[i++]); + } + else if(arg.equals("-i")) { + global_inputFile = argv[i++]; + } + else if(arg.equals("-p")) { + global_doPrint = true; + } + else if(arg.equals("-w")){ + global_workload = Integer.parseInt(argv[i++]); + } + else { + System.out.println("Non-option argument: " + argv[i]); + opterr = true; + } + + } + } + if(opterr) { + displayUsage(); + System.exit(1); + } + } + + public Labyrinth(String[] argv) + { + parseArg(argv); + } + + + public Labyrinth(int myID,Solve_Arg rArg) + { + threadID = myID; + routerArg = rArg; + } + + public Labyrinth() {} + + public void displayUsage() + { + System.out.println("Usage: Labyrinth [options]"); + System.out.println("Options:"); + System.out.println(" b bend cost"); + System.out.println(" i input file name"); + System.out.println(" p print routed maze"); + System.out.println(" t Number of threads (depricated)"); + System.out.println(" w Workload per rBlock"); + System.out.println(" x x movement cost"); + System.out.println(" y y movement cost"); + System.out.println(" z z movement cost"); + } + + + public static void main(String[] argv) + { + //parse arguments + Labyrinth labyrinth = new Labyrinth(argv); + + Maze maze = new Maze(); + Maze mazePtr = maze.alloc(); + + //parse maze/grid + int numPathToRoute = mazePtr.readMaze(labyrinth.global_inputFile); + + + Router routerPtr = Router.alloc(labyrinth.xCost,labyrinth.yCost, + labyrinth.zCost,labyrinth.bendCost); + + List_t pathVectorListPtr = List_t.alloc(0); + + Solve_Arg routerArg = new Solve_Arg(routerPtr,mazePtr,pathVectorListPtr); + + /* Start */ + long start = System.currentTimeMillis(); + + //rblocks are handled within Router. + Router.solve(routerArg); + + /* End of Solve */ + long finish = System.currentTimeMillis(); + + + int numPathRouted = 0; + List_Iter it = new List_Iter(); + + it.reset(pathVectorListPtr); + while(it.hasNext(pathVectorListPtr)) { + Vector_t pathVectorPtr = (Vector_t)it.next(pathVectorListPtr); + numPathRouted += pathVectorPtr.vector_getSize(); + } + + double elapsed = ((double)finish-(double)start)/1000; + + System.out.println("Paths routed = " + numPathRouted); + System.out.println("Elapsed time = " + elapsed); + + boolean stats = mazePtr.checkPaths(pathVectorListPtr,labyrinth.global_doPrint); + if(!stats) + System.out.println("Verification not passed"); + else + System.out.println("Verification passed."); + + System.out.println("Finished"); + } +} + +/* ============================================================================= + * + * End of labyrinth.c + * + * ============================================================================= + */ diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/List_Iter.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/List_Iter.java new file mode 100644 index 00000000..351e80d0 --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/List_Iter.java @@ -0,0 +1,38 @@ +public class List_Iter { + List_Node itPtr; + + /* ============================================================================= + * list_iter_reset + * ============================================================================= + void list_iter_reset (list_iter_t* itPtr, list_t* listPtr); + */ + public List_Iter() { + itPtr = null; + } + + public void reset(List_t listPtr) + { + itPtr = listPtr.head; + } + + /* ============================================================================= + * list_iter_hasNext + * ============================================================================= + * bool_t list_iter_hasNext (list_iter_t* itPtr, list_t* listPtr); + */ + public boolean hasNext(List_t listPtr) { + return (itPtr.nextPtr != null)? true : false; + } + + /* ============================================================================= + * list_iter_next + * ============================================================================= + * void* list_iter_next (list_iter_t* itPtr, list_t* listPtr); + */ + public Object next(List_t listPtr) + { + itPtr = itPtr.nextPtr; + return itPtr.dataPtr; + } +} + diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/List_Node.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/List_Node.java new file mode 100644 index 00000000..806baa19 --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/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/Java-Single/Labyrinth/mlp/rBlocked/List_t.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/List_t.java new file mode 100644 index 00000000..93593966 --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/List_t.java @@ -0,0 +1,312 @@ +/* ============================================================================= + * + * 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; + boolean isCoordinate; + 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(int isCoordinate) + { + List_t listPtr = new List_t(); + + if(listPtr == null) { + return null; + } + + listPtr.head.dataPtr = null; + listPtr.head.nextPtr = null; + listPtr.size = 0; + + listPtr.isCoordinate = (isCoordinate==1)?true:false; + + 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) + { + if(isCoordinate) + { + return Coordinate.comparePair(obj1,obj2); + } + else + return compareObject(obj1,obj2); + } + +/* ============================================================================= + * 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/Java-Single/Labyrinth/mlp/rBlocked/Maze.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Maze.java new file mode 100644 index 00000000..59a5d95b --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Maze.java @@ -0,0 +1,486 @@ +/*============================================================================= + * + * Maze.java + * + * ============================================================================= + * + * 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. + * + * ============================================================================= + */ + +//#define GRID_POINT_FULL -2 +//#define GRID_POINT_EMPTY -1 + +//TODO change these back and delete class variables. + +public class Maze +{ + private static int GRID_POINT_FULL; + private static int GRID_POINT_EMPTY; + + Grid gridPtr; + Queue_t workQueuePtr; + Vector_t wallVectorPtr; /* contains source/destination pairs to route */ + Vector_t srcVectorPtr; /* obstacles */ + Vector_t dstVectorPtr; /* destinations */ + + public Maze() + { + //these were changed from #defines + GRID_POINT_FULL = -2; + GRID_POINT_EMPTY = -1; + } + + +/* ============================================================================= + * maze_alloc + * ============================================================================= + maze_t* maze_alloc (); + */ + public Maze alloc() + { + Maze mazePtr = new Maze(); + + if(mazePtr != null) { + Vector_t vector_t = new Vector_t(); + Queue_t queue_t = new Queue_t(); + + mazePtr.gridPtr = null; + mazePtr.workQueuePtr = queue_t.queue_alloc(1024); + mazePtr.wallVectorPtr = vector_t.vector_alloc(1); + mazePtr.srcVectorPtr = vector_t.vector_alloc(1); + mazePtr.dstVectorPtr = vector_t.vector_alloc(1); + + } + + return mazePtr; + } + +/* ============================================================================= + * maze_free + * ============================================================================= + void maze_free (maze_t* mazePtr); + */ + public static void free(Maze m) + { + m = null; + } + +/* ============================================================================= + * addToGrid + * ============================================================================= + */ + private void addToGrid(Grid gridPtr,Vector_t vectorPtr,String type) + { + int i; + int n = vectorPtr.vector_getSize(); + + for(i = 0; i < n; i++) { + Coordinate coordinatePtr = (Coordinate)vectorPtr.vector_at(i); + if(!gridPtr.isPointValid(coordinatePtr.x,coordinatePtr.y,coordinatePtr.z)) + { + System.out.println("Error: " + type + " (" + coordinatePtr.x + + ", " + coordinatePtr.y + + ", " + coordinatePtr.z); + System.exit(1); + } + } + gridPtr.addPath(vectorPtr); + } +/* ============================================================================= + * maze_read + * -- Return number of path to route + * ============================================================================= + long maze_read (maze_t* mazePtr, char* inputFileName); + */ + public int readMaze(String inputFileName) + { + Coordinate coordinate = new Coordinate(); + FileInputStream in = new FileInputStream(inputFileName); + + + /* + * Parse input file + */ + int lineNumber = 0; + int height = -1; + int width = -1; + int depth = -1; + boolean isParseError = false; + List_t workListPtr = List_t.alloc(1); // List.alloc(Coordinate.comparePair); + String line; + + while((line = in.readLine()) != null) { + String code; + int[] xy = new int[6]; // equivalent to x1,y1,z1,x2,y2,z2 + int numToken = 0; + + StringTokenizer tok = new StringTokenizer(line); + + if((numToken = tok.countTokens()) < 1 ) { + continue; + } + + code = tok.nextToken(); + + if(code.equals("#")) { + /* comment line */ + continue; + } + for(int i=0;i + +in the source directory. For example, for the sequential flavor, run: + + make -f Makefile.seq + +By default, this produces an executable named "labyrinth", which can then be +run in the following manner: + + ./labyrinth -i + +The following input file is recommended for simulated runs: + + ./labyrinth -i inputs/random-x32-y32-z3-n96.txt + +For non-simulator runs, a larger input can be used: + + ./labyrinth -i inputs/random-x512-y512-z7-n512.txt + + +Input Files +----------- + +More input sets can be generated by using "inputs/generate.py". For example, + + inputs/generate.py 128 128 3 64 + +Will create a 128x128x3 maze grid and select 64 uniformly random start/end +point pairs. + + +References +---------- + +[1] C. Cao Minh, J. Chung, C. Kozyrakis, and K. Olukotun. STAMP: Stanford + Transactional Applications for Multi-processing. In IISWC '08: Proceedings + of The IEEE International Symposium on Workload Characterization, + September 2008. + +[2] C. Lee. An algorithm for path connections and its applications. IRE Trans. + On Electronic Computers, 1961. + +[3] I. Watson, C. Kirkham, and M. Lujan. A Study of a Transactional Parallel + Routing Algorithm. Proceedings of the 16th International Conference on + Parallel Architectures and Compilation Techniques, 2007. + diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Pair.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Pair.java new file mode 100644 index 00000000..92db5229 --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Pair.java @@ -0,0 +1,86 @@ + + +public class Pair { + public Object first; + public Object second; + + public Pair() { + first = null; + second = null; + } + + +/* ============================================================================= + * + * pair constructor + * + * pair_t* pair_alloc(void* firstPtr, void* secondPtr); + * ============================================================================= + */ + public static Pair alloc(Object first,Object second) + { + Pair ptr= new Pair(); + ptr.first = first; + ptr.second = second; + + return ptr; + } + + + +/* ============================================================================= + * Ppair_alloc + * + * -- Returns NULL if failure + * ============================================================================= + */ + public static Pair Ppair_alloc (Object firstPtr, Object secondPtr) { + Pair pairPtr = new Pair(); + pairPtr.first = firstPtr; + pairPtr.second = secondPtr; + return pairPtr; + } + + +/* ============================================================================= + * pair_free + * ============================================================================= + * + * void pair_free (pair_t* pairPtr); + * + */ + public static void free(Pair pairPtr) + { + pairPtr = null; + } + + +/* ============================================================================= + * Ppair_free + * ============================================================================= + * +void Ppair_free (pair_t* pairPtr); +*/ + +/* ============================================================================= + * pair_swap + * -- Exchange 'firstPtr' and 'secondPtr' + * ============================================================================= + * void pair_swap (pair_t* pairPtr); +*/ + public static void swap(Pair pairPtr) + { + Object tmpPtr = pairPtr.first; + + pairPtr.first = pairPtr.second; + pairPtr.second = tmpPtr; + } + +} + +/* ============================================================================= + * + * End of pair.java + * + * ============================================================================= + */ diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Point.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Point.java new file mode 100644 index 00000000..8905bd54 --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Point.java @@ -0,0 +1,25 @@ + + public class Point { + int x; + int y; + int z; + int value; + int momentum; + + public Point() { + x = -1; + y = -1; + z = -1; + value = -1; + momentum = -1; + } + + public Point(int x,int y, int z,int value, int m) { + this.x = x; + this.y = y; + this.z = z; + this.value = value; + momentum = m; + } + } + diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Queue_Int.java b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Queue_Int.java new file mode 100644 index 00000000..a24ced90 --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Queue_Int.java @@ -0,0 +1,448 @@ +/* ============================================================================= + * + * queue.java + * + * ============================================================================= + * + * Copyright (C) Stanford University, 2006. All Rights Reserved. + * Author: Chi Cao Minh + * + * Ported to Java June 2009 Alokika Dash + * adash@uci.edu + * 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_Int { + + private static int QUEUE_GROWTH_FACTOR; + int pop; /* points before element to pop */ + int push; + int capacity; + int[] elements; + + public Queue_Int() + { + QUEUE_GROWTH_FACTOR = 2; + } + + /* ============================================================================= + * queue_alloc + * ============================================================================= + */ + public static Queue_Int queue_alloc (int initCapacity) + { + Queue_Int queuePtr = new Queue_Int(); + + int capacity = ((initCapacity < 2) ? 2 : initCapacity); + queuePtr.elements = new int[capacity]; + if (queuePtr.elements == null) { + queuePtr = null; + return null; + } + queuePtr.pop = capacity - 1; + queuePtr.push = 0; + queuePtr.capacity = capacity; + + return queuePtr; + } + + + /* ============================================================================= + * Pqueue_alloc + * ============================================================================= + */ + public Queue_Int + Pqueue_alloc (int initCapacity) + { + Queue_Int queuePtr = new Queue_Int(); + + int capacity = ((initCapacity < 2) ? 2 : initCapacity); + queuePtr.elements = new int[capacity]; + if (queuePtr.elements == null) { + queuePtr = null; + return null; + } + queuePtr.pop = capacity - 1; + queuePtr.push = 0; + queuePtr.capacity = capacity; + + return queuePtr; + } + + + /* ============================================================================= + * TMqueue_alloc + * ============================================================================= + */ + public Queue_Int TMqueue_alloc (int initCapacity) + { + Queue_Int queuePtr = new Queue_Int(); + + int capacity = ((initCapacity < 2) ? 2 : initCapacity); + queuePtr.elements = new int[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 () + { + elements = null; + } + + + /* ============================================================================= + * Pqueue_free + * ============================================================================= + */ + public void + Pqueue_free () + { + elements = null; + } + + + /* ============================================================================= + * TMqueue_free + * ============================================================================= + */ + public void + TMqueue_free () + { + elements = null; + } + + + /* ============================================================================= + * queue_isEmpty + * ============================================================================= + */ + public boolean + queue_isEmpty () + { + return (((pop + 1) % capacity == push) ? true : false); + } + + + /* ============================================================================= + * queue_clear + * ============================================================================= + */ + public void + queue_clear () + { + pop = capacity - 1; + push = 0; + } + + + /* ============================================================================= + * TMqueue_isEmpty + * ============================================================================= + */ + public boolean + TMqueue_isEmpty (Queue_Int queuePtr) + { + int pop = queuePtr.pop; + int push = queuePtr.push; + int capacity = queuePtr.capacity; + + return (((pop + 1) % capacity == push) ? true : false); + } + + + /* ============================================================================= + * queue_push + * ============================================================================= + */ + public boolean + queue_push (int 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; + int[] newElements = new int[newCapacity]; + if (newElements == null) { + return false; + } + + int dst = 0; + int[] 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 = 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_Int queuePtr, int 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; + int[] newElements = new int[newCapacity]; + if (newElements == null) { + return false; + } + + int dst = 0; + int[] 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; + } + + + /* ============================================================================= + * TMqueue_push + * ============================================================================= + */ + public boolean + TMqueue_push (Queue_Int queuePtr, int 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; + int[] newElements = new int[newCapacity]; + if (newElements == null) { + return false; + } + + int dst = 0; + int[] 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 */ + + } + + int[] elements = queuePtr.elements; + elements[push] = dataPtr; + queuePtr.push = newPush; + + return true; + } + + + /* ============================================================================= + * queue_pop + * ============================================================================= + */ + public int + queue_pop () + { + int newPop = (pop + 1) % capacity; + if (newPop == push) { + return 0; + } + + int dataPtr = elements[newPop]; + pop = newPop; + + return dataPtr; + } + + + /* ============================================================================= + * TMqueue_pop + * ============================================================================= + */ + public int + TMqueue_pop (Queue_Int queuePtr) + { + int pop = queuePtr.pop; + int push = queuePtr.push; + int capacity = queuePtr.capacity; + + int newPop = (pop + 1) % capacity; + if (newPop == push) { + return 0; + } + + int[] elements = queuePtr.elements; + int dataPtr = elements[newPop]; + queuePtr.pop = newPop; + + return dataPtr; + } + + /**** + * main method for testing + **/ + /* + public static void main(String[] args) { + testQueue queuePtr = testQueue.queue_alloc(-1); + int numData = 4; + if(queuePtr.queue_isEmpty()) + System.out.println("Queue is empty"); + + for(int 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]; + + //void** newElements = (void**)malloc(newCapacity * sizeof(void*)); + if (newElements == null) { + return false; + } + 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]; + + if (elements == null) { + return false; + } + 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/Java-Single/Labyrinth/mlp/rBlocked/extractLines b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/extractLines new file mode 100644 index 00000000..c75e5726 --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/extractLines @@ -0,0 +1,3 @@ +#!/bin/sh +lines=$(grep -n "#" $1 | cut -d: -f1 | sed '1q') +sed '/^#/d' $1 > ttt$1 diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/makefile b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/makefile new file mode 100644 index 00000000..d618139c --- /dev/null +++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/makefile @@ -0,0 +1,29 @@ +PROGRAM=Labyrinth + +SOURCE_FILES=Coordinate.java CoordPathWrapper.java Grid.java Labyrinth.java List_Iter.java List_Node.java List_t.java Maze.java Pair.java Point.java Queue_Int.java Queue_t.java Router.java Solve_Arg.java Vector_t.java + +BUILDSCRIPT=../../../../../buildscript + +USEMLP= -mlp 8 2 -mlpdebug # use to turn mlp on and off and make sure rest of build not broken +BSFLAGS= -32bit -nooptimize -debug -garbagestats -mainclass Test +OWNERSHIP= -ownership -ownallocdepth 1 -enable-assertions -methodeffects -flatirusermethods -ownwritedots final -ownaliasfile aliases.txt + +default: + ../../../../../buildscript -nojava $(USEMLP) $(BSFLAGS) $(OWNERSHIP) -o $(PROGRAM) $(SOURCE_FILES) + +single: + ../../../../../buildscript $(BSFLAGS) -o $(PROGRAM) $(SOURCE_FILES) + +java: + ../../../../../buildscript $(USEMLP) $(BSFLAGS) $(OWNERSHIP) -o $(PROGRAM) $(SOURCE_FILES) + +clean: + rm -f $(PROGRAM).bin + rm -fr tmpbuilddirectory + rm -f *~ + rm -f *.dot + rm -f *.png + rm -f *.txt + rm -f aliases.txt + rm -f mlpReport*txt + rm -f results*txt -- 2.34.1