Robust/src/Benchmarks/SingleTM/Labyrinth/Router.java

   1 /* =============================================================================
   2  *
   3  * Router.java
   4  *
   5  * =============================================================================
   6  *
   7  * Copyright (C) Stanford University, 2006.  All Rights Reserved.
   8  * Author: Chi Cao Minh
   9  *
  10  * Ported to Java
  11  * Author: Jihoon Lee
  12  * University of California, Irvine
  13  *
  14  * =============================================================================
  15  *
  16  * For the license of bayes/sort.h and bayes/sort.c, please see the header
  17  * of the files.
  18  *
  19  * ------------------------------------------------------------------------
  20  *
  21  * For the license of kmeans, please see kmeans/LICENSE.kmeans
  22  *
  23  * ------------------------------------------------------------------------
  24  *
  25  * For the license of ssca2, please see ssca2/COPYRIGHT
  26  *
  27  * ------------------------------------------------------------------------
  28  *
  29  * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the
  30  * header of the files.
  31  *
  32  * ------------------------------------------------------------------------
  33  *
  34  * For the license of lib/rbtree.h and lib/rbtree.c, please see
  35  * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree
  36  *
  37  * ------------------------------------------------------------------------
  38  *
  39  * Unless otherwise noted, the following license applies to STAMP files:
  40  *
  41  * Copyright (c) 2007, Stanford University
  42  * All rights reserved.
  43  *
  44  * Redistribution and use in source and binary forms, with or without
  45  * modification, are permitted provided that the following conditions are
  46  * met:
  47  *
  48  *     * Redistributions of source code must retain the above copyright
  49  *       notice, this list of conditions and the following disclaimer.
  50  *
  51  *     * Redistributions in binary form must reproduce the above copyright
  52  *       notice, this list of conditions and the following disclaimer in
  53  *       the documentation and/or other materials provided with the
  54  *       distribution.
  55  *
  56  *     * Neither the name of Stanford University nor the names of its
  57  *       contributors may be used to endorse or promote products derived
  58  *       from this software without specific prior written permission.
  59  *
  60  * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
  61  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  62  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  63  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
  64  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  65  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  66  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  67  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  68  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  69  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  70  * THE POSSIBILITY OF SUCH DAMAGE.
  71  *
  72  * =============================================================================
  73  */
  74
  75 #define MOMENTUM_ZERO 0
  76 #define MOMENTUM_POSX 1
  77 #define MOMENTUM_POSY 2
  78 #define MOMENTUM_POSZ 3
  79 #define MOMENTUM_NEGX 4
  80 #define MOMENTUM_NEGY 5
  81 #define MOMENTUM_NEGZ 6
  82
  83
  84 public class Router {
  85     int xCost;
  86     int yCost;
  87     int zCost;
  88     int bendCost;
  89
  90
  91 /* =============================================================================
  92  * router_alloc
  93  * =============================================================================
  94  * router_t* router_alloc (long xCost, long yCost, long zCost, long bendCost);
  95  */
  96     public static Router alloc(int xCost,int yCost,int zCost,int bendCost)
  97     {
  98         Router routerPtr = new Router();
  99
 100
 101         Point MOVE_POSX = new Point(1,0,0,0,MOMENTUM_POSX);
 102         Point MOVE_POSY = new Point(0,1,0,0,MOMENTUM_POSY);
 103         Point MOVE_POSZ = new Point(0,0,1,0,MOMENTUM_POSZ);
 104         Point MOVE_NEGX = new Point(-1,0,0,0,MOMENTUM_NEGX);
 105         Point MOVE_NEGY = new Point(0,-1,0,0,MOMENTUM_NEGY);
 106         Point MOVE_NEGZ = new Point(0,0,-1,0,MOMENTUM_NEGZ);
 107
 108         if(routerPtr != null) {
 109             routerPtr.xCost = xCost;
 110             routerPtr.yCost = yCost;
 111             routerPtr.zCost = zCost;
 112             routerPtr.bendCost = bendCost;
 113         }
 114
 115         return routerPtr;
 116     }
 117
 118
 119
 120
 121 /* =============================================================================
 122  * router_free
 123  * =============================================================================
 124  * void router_free (router_t* routerPtr);
 125  */
 126     public static void free(Router routerPtr)
 127     {
 128         routerPtr = null;
 129     }
 130
 131 /* ============================================================================
 132  * PexpandToneighbor
 133  * ============================================================================
 134  */
 135     private void PexpandToNeighbor(Grid myGridPtr,
 136                                     int x,int y,int z, int value,Queue queuePtr)
 137     {
 138         if (myGridPtr.isPointValid(x,y,z)) {
 139             int neighborGridPointIndex = myGridPtr.getPointIndex(x,y,z);
 140             int neighborValue = myGridPtr.getPoint(neighborGridPointIndex);
 141             if (neighborValue == GRID_POINT_EMPTY) {
 142                 myGridPtr.setPoint(neighborGridPointIndex,value);
 143                 queuePtr.queue_push(neighborGridPointIndex);
 144             } else if (neighborValue != GRID_POINT_FULL) {
 145
 146                 if (value < neighborValue) {
 147                     myGridPtr.setPoint(neighborGridPointIndex,value);
 148                     queuePtr.queue_push(neighborGridPointIndex);
 149                 }
 150             }
 151         }
 152     }
 153
 154
 155 /* ============================================================================
 156  * PdoExpansion
 157  * ============================================================================
 158  */
 159     private boolean PdoExpansion (Router routerPtr,Grid myGridPtr,Queue queuePtr,
 160                                   Coordinate srcPtr,Coordinate dstPtr)
 161     {
 162         int xCost = routerPtr.xCost;
 163         int yCost = routerPtr.yCost;
 164         int zCost = routerPtr.zCost;
 165
 166         /*
 167          * Potential Optimization: Make 'src' the one closet to edge.
 168          * This will likely decrease the area of the emitted wave.
 169          */
 170
 171         queuePtr.queue_clear();
 172
 173         int srcGridPointIndex = myGridPtr.getPointIndex(srcPtr.x,srcPtr.y,srcPtr.z);
 174         queuePtr.queue_push(srcGridPointIndex);
 175         myGridPtr.setPoint(srcPtr.x,srcPtr.y,srcPtr.z,0);
 176         myGridPtr.setPoint(dstPtr.x,dstPtr.y,dstPtr.z,GRID_POINT_EMPTY);
 177         int dstGridPointIndex = myGridPtr.getPointIndex(dstPtr.x,dstPtr.y,dstPtr.z);
 178         boolean isPathFound = false;
 179
 180         while (queuePtr.queue_isEmpty()) {
 181             int gridPointIndex = queuePtr.queue_pop();
 182             if(gridPointIndex == dstGridPointIndex) {
 183                 isPathFound = true;
 184                 break;
 185             }
 186
 187             int[] x = new int[1];
 188             int[] y = new int[1];
 189             int[] z = new int[1];
 190
 191             myGridPtr.getPointIndices(gridPointIndex,x,y,z);
 192             int value = myGridPtr.getPoint(gridPointIndex);
 193
 194             /*
 195              * Check 6 neighbors
 196              *
 197              * Potential Optimization: Only need to check 5 of these
 198              */
 199           PexpandToNeighbor(myGridPtr, x[0]+1, y[0],   z[0],   (value + xCost), queuePtr);
 200           PexpandToNeighbor(myGridPtr, x[0]-1, y[0],   z[0],   (value + xCost), queuePtr);
 201           PexpandToNeighbor(myGridPtr, x[0], y[0]+1,   z[0],   (value + xCost), queuePtr);
 202           PexpandToNeighbor(myGridPtr, x[0], y[0]-1,   z[0],   (value + xCost), queuePtr);
 203           PexpandToNeighbor(myGridPtr, x[0], y[0],   z[0]+1,   (value + xCost), queuePtr);
 204           PexpandToNeighbor(myGridPtr, x[0], y[0],   z[0]-1,   (value + xCost), queuePtr);
 205
 206         } /* iterate over work queue */
 207
 208         return isPathfound;
 209     }
 210
 211
 212 /* ============================================================================
 213  * traceToNeighbor
 214  * ============================================================================
 215  */
 216     private void traceToNeighbor(Grid myGridPtr,
 217                                  Point currPtr,
 218                                  Point movePtr,
 219                                  boolean useMomentum,
 220                                  int bendCost,
 221                                  Point nextPtr)
 222     {
 223         int x = currPtr.x + movePtr.x;
 224         int y = currPtr.y + movePtr.y;
 225         int z = currPtr.z + movePtr.z;
 226
 227         if (myGridPtr.isPointValid(x,y,z) &&
 228                 !myGridPtr.isPointEmpty(x,y,z) &&
 229                 !myGridPtr.isPointFull(x,y,z))
 230         {
 231             int value = myGridPtr.getPoint(x,y,z);
 232             int b = 0;
 233
 234             if (useMomentum && (currPtr.momentum != movePtr.momentum)) {
 235                 b = bendCost;
 236             }
 237             if ((value + b) <= nextPtr.value) { /* '=' favors neighbors over current */
 238                 nextPtr.x = x;
 239                 nextPtr.y = y;
 240                 nextPtr.z = z;
 241                 nextPtr.value = value;
 242                 nextPtr.momentum = movePtr.momentum;
 243             }
 244         }
 245     }
 246 /* =============================================================================
 247  * PdoTraceback
 248  * =============================================================================
 249  */
 250
 251     private Vector_t PdoTraceback(Grid gridPtr,Grid myGridPtr,
 252                                   Coordinate dstPtr, int bendCost)
 253     {
 254         Vector_t pointVectorPtr = Vector.vector_alloc(1);
 255
 256         Point next = new Point();
 257         next.x = dstPtr.x;
 258         next.y = dstPtr.y;
 259         next.z = dstPtr.z;
 260         next.value = myGridPtr.getPoint(next.x,next.y,next.z);
 261         next.momentum = MOMENTUM_ZERO;
 262
 263         while(true) {
 264             int gridPointIndex = gridPtr.getPointIndex(next.x,next.y,next.z);
 265             pointVectorPtr.vector_pushBack(gridPointIndex);
 266             myGridPtr.setPoint(next.x,next.y,next.z,GRID_POINT_FULL);
 267
 268             /* Check if we are done */
 269             if (next.value == 0) {
 270                 break;
 271             }
 272             Point curr = next;
 273
 274             /*
 275              * Check 6 neibors
 276              */
 277
 278             traceToNeighbor(myGridPtr,curr,MOVE_POSX,true, bendCost, next);
 279             traceToNeighbor(myGridPtr,curr,MOVE_POSY,true, bendCost, next);
 280             traceToNeighbor(myGridPtr,curr,MOVE_POSZ,true, bendCost, next);
 281             traceToNeighbor(myGridPtr,curr,MOVE_NEGX,true, bendCost, next);
 282             traceToNeighbor(myGridPtr,curr,MOVE_NEGY,true, bendCost, next);
 283             traceToNeighbor(myGridPtr,curr,MOVE_NEGZ,true, bendCost, next);
 284
 285             /*
 286              * Because of bend costs, none of the neighbors may appear to be closer.
 287              * In this case, pick a neighbor while ignoring momentum.
 288              */
 289
 290             if ((curr.x == next.y) &&
 291                 (curr.y == next.y) &&
 292                 (curr.z == next.z))
 293             {
 294                 next.value = curr.value;
 295                 traceToNeighbor(myGridPtr,curr,MOVE_POSX,false, bendCost, next);
 296                 traceToNeighbor(myGridPtr,curr,MOVE_POSY,false, bendCost, next);
 297                 traceToNeighbor(myGridPtr,curr,MOVE_POSZ,false, bendCost, next);
 298                 traceToNeighbor(myGridPtr,curr,MOVE_NEGX,false, bendCost, next);
 299                 traceToNeighbor(myGridPtr,curr,MOVE_NEGY,false, bendCost, next);
 300                 traceToNeighbor(myGridPtr,curr,MOVE_NEGZ,false, bendCost, next);
 301
 302                 if ((curr.x == next.x) &&
 303                     (curr.y == next.y) &&
 304                     (curr.z == next.z))
 305                 {
 306                     pointVectorPtr.vector_free();
 307                     return null;
 308                 }
 309             }
 310         }
 311
 312         return pointVectorPtr;
 313     }
 314
 315 /* =============================================================================
 316  * router_solve
 317  * =============================================================================
 318  * void router_solve (void* argPtr);
 319  */
 320     public static void solve(Object argPtr)
 321     {
 322         // TM_THREAD_ENTER();
 323         Solve_Arg routerArgPtr = (SolveArg) argPtr;
 324         Router routerPtr = routerArgPtr.routerPtr;
 325         Maze mazePtr = routerArgPtr.mazePtr;
 326         Vector_t myPathVectorPtr = Vector.alloc(1);
 327
 328         Queue workQueuePtr = mazePtr.workqueuePtr;
 329         Grid gridPtr = mazePtr.gridPtr;
 330         Grid myGridPtr = Grid.alloc(gridPtr.width,gridPtr.height,gridPtr.depth);
 331         int bendCost = routerPtr.bendCost;
 332         Queue myExpansionQueuePtr = Queue.queue_alloc(-1);
 333
 334         /*
 335          * Iterate over work list to route each path. This involves an
 336          * 'expansion' and 'tracback' phase for each source/destination pair.
 337          */
 338         while(true) {
 339             Pair coordinatePairPtr;
 340
 341             // TM_BEGIN();
 342             atomic {
 343                 if(workQueuePtr.queue_isEmpty()) {
 344                     coordinatePairPtr = null;
 345                 } else {
 346                     coordinatePairPtr = (Pair)workQueuePtr.queue_pop();
 347                 }
 348             }
 349             // TM_END();
 350             //
 351
 352             if (coordinatePairPtr = null) {
 353                 break;
 354             }
 355
 356             Coordinate srcPtr = coordinatePairPtr.firstPtr;
 357             Coordinate dstPtr = coordinatePairPtr.secondPtr;
 358
 359             boolean success = false;
 360             Vector_t pointvectorPtr = null;
 361
 362             // TM_BEGIN();
 363             atomic {
 364                 Grid.copy(myGridPtr, gridPtr); /* ok if not most up-to-date */
 365                 if (PdoExpansion(routerPtr, myGridPtr, myExpansionQueuePtr,
 366                             srcPtr, dstPtr)) {
 367                     pointVectorPtr = PdoTraceback(gridPtr,myGridPtr,dstPtr,bendCost);
 368
 369                     if (pointVectorPtr) {
 370                         gridPtr.addPath(pointVectorPtr);
 371                         success = true;
 372                     }
 373                 }
 374             }
 375
 376             if(success) {
 377                 boolean status = myPathVectorPtr.vector_pushBack(pointVectorPtr);
 378             }
 379         }
 380
 381         /*
 382          * Add my paths to global list
 383          */
 384         List_t pathVectorListPtr = routerArgPtr.pathVectorListPtr;
 385
 386         atomic {
 387             pathVectorListPtr.insert(myPathVectorPtr);
 388         }
 389
 390         // TM_THREAD_EXIT();
 391     }
 392 }
 393 /* =============================================================================
 394  *
 395  * End of router.java
 396  *
 397  * =============================================================================
 398  */