Robust/src/Benchmarks/SingleTM/Yada/Queue_t.java

   1 /* =============================================================================
   2  *
   3  * queue.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:Alokika Dash
  12  * University of California, Irvine
  13  *
  14  * =============================================================================
  15  *
  16  * Unless otherwise noted, the following license applies to STAMP files:
  17  *
  18  * Copyright (c) 2007, Stanford University
  19  * All rights reserved.
  20  *
  21  * Redistribution and use in source and binary forms, with or without
  22  * modification, are permitted provided that the following conditions are
  23  * met:
  24  *
  25  *     * Redistributions of source code must retain the above copyright
  26  *       notice, this list of conditions and the following disclaimer.
  27  *
  28  *     * Redistributions in binary form must reproduce the above copyright
  29  *       notice, this list of conditions and the following disclaimer in
  30  *       the documentation and/or other materials provided with the
  31  *       distribution.
  32  *
  33  *     * Neither the name of Stanford University nor the names of its
  34  *       contributors may be used to endorse or promote products derived
  35  *       from this software without specific prior written permission.
  36  *
  37  * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
  38  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  39  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  40  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
  41  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  42  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  43  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  44  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  45  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  46  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  47  * THE POSSIBILITY OF SUCH DAMAGE.
  48  *
  49  * =============================================================================
  50  */
  51
  52 #define QUEUE_GROWTH_FACTOR 2
  53
  54 public class Queue_t {
  55   int pop; /* points before element to pop */
  56   int push;
  57   int capacity;
  58   Object[] elements;
  59
  60   /* =============================================================================
  61    * queue_alloc
  62    * =============================================================================
  63    */
  64   public Queue_t(int initCapacity) {
  65     int capacity = ((initCapacity < 2) ? 2 : initCapacity);
  66     elements = new Object[capacity];
  67     pop      = capacity - 1;
  68     push     = 0;
  69     this.capacity = capacity;
  70   }
  71
  72
  73
  74
  75   /* =============================================================================
  76    * queue_isEmpty
  77    * =============================================================================
  78    */
  79   public boolean queue_isEmpty () {
  80     //int pop      = queuePtr.pop;
  81     //int push     = queuePtr.push;
  82     //int capacity = queuePtr.capacity;
  83
  84     return (pop + 1) % capacity == push;
  85   }
  86
  87
  88   /* =============================================================================
  89    * queue_clear
  90    * =============================================================================
  91    */
  92   public void
  93     queue_clear ()
  94     {
  95       pop  = capacity - 1;
  96       push = 0;
  97     }
  98
  99
 100   /* =============================================================================
 101    * TMqueue_isEmpty
 102    * =============================================================================
 103    */
 104
 105
 106   public void queue_shuffle(Random randomPtr) {
 107     int numElement;
 108     if (pop < push) {
 109       numElement = push - (pop + 1);
 110     } else {
 111       numElement = capacity - (pop - push + 1);
 112     }
 113
 114     int base = pop + 1;
 115     for (int i = 0; i < numElement; i++) {
 116       int r1 = (int) randomPtr.random_generate() % numElement;
 117       int r2 = (int) randomPtr.random_generate() % numElement;
 118       int i1 = (base + r1) % capacity;
 119       int i2 = (base + r2) % capacity;
 120       Object tmp = elements[i1];
 121       elements[i1] = elements[i2];
 122       elements[i2] = tmp;
 123     }
 124   }
 125
 126
 127
 128   /* =============================================================================
 129    * queue_push
 130    * =============================================================================
 131    */
 132   public boolean queue_push (Object dataPtr) {
 133     if(pop == push) {
 134
 135       System.out.println("push == pop in Queue.java");
 136       return false;
 137     }
 138
 139
 140     /* Need to resize */
 141     int newPush = (push + 1) % capacity;
 142     if (newPush == pop) {
 143
 144       int newCapacity = capacity * QUEUE_GROWTH_FACTOR;
 145       Object[] newElements = new Object[newCapacity];
 146       if (newElements == null) {
 147         return false;
 148       }
 149
 150       int dst = 0;
 151       Object[] tmpelements = elements;
 152       if (pop < push) {
 153         int src;
 154         for (src = (pop + 1); src < push; src++, dst++) {
 155           newElements[dst] = elements[src];
 156         }
 157       } else {
 158         int src;
 159         for (src = (pop + 1); src < capacity; src++, dst++) {
 160           newElements[dst] = elements[src];
 161         }
 162         for (src = 0; src < push; src++, dst++) {
 163           newElements[dst] = elements[src];
 164         }
 165       }
 166
 167       //elements = null;
 168       elements = newElements;
 169       pop      = newCapacity - 1;
 170       capacity = newCapacity;
 171       push = dst;
 172       newPush = push + 1; /* no need modulo */
 173     }
 174
 175     elements[push] = dataPtr;
 176     push = newPush;
 177
 178     return true;
 179   }
 180
 181
 182   /* =============================================================================
 183    * Pqueue_push
 184    * =============================================================================
 185    */
 186   public boolean
 187     Pqueue_push (Queue_t queuePtr, Object dataPtr)
 188     {
 189       int pop      = queuePtr.pop;
 190       int push     = queuePtr.push;
 191       int capacity = queuePtr.capacity;
 192
 193       if(pop == push) {
 194         System.out.println("push == pop in Queue.java");
 195         return false;
 196       }
 197
 198       /* Need to resize */
 199       int newPush = (push + 1) % capacity;
 200       if (newPush == pop) {
 201
 202         int newCapacity = capacity * QUEUE_GROWTH_FACTOR;
 203         Object[] newElements = new Object[newCapacity];
 204         if (newElements == null) {
 205           return false;
 206         }
 207
 208         int dst = 0;
 209         Object[] elements = queuePtr.elements;
 210         if (pop < push) {
 211           int src;
 212           for (src = (pop + 1); src < push; src++, dst++) {
 213             newElements[dst] = elements[src];
 214           }
 215         } else {
 216           int src;
 217           for (src = (pop + 1); src < capacity; src++, dst++) {
 218             newElements[dst] = elements[src];
 219           }
 220           for (src = 0; src < push; src++, dst++) {
 221             newElements[dst] = elements[src];
 222           }
 223         }
 224
 225         elements = null;
 226         queuePtr.elements = newElements;
 227         queuePtr.pop      = newCapacity - 1;
 228         queuePtr.capacity = newCapacity;
 229         push = dst;
 230         newPush = push + 1; /* no need modulo */
 231
 232       }
 233
 234       queuePtr.elements[push] = dataPtr;
 235       queuePtr.push = newPush;
 236
 237       return true;
 238     }
 239
 240   /* =============================================================================
 241    * queue_pop
 242    * =============================================================================
 243    */
 244   public Object queue_pop () {
 245     int newPop = (pop + 1) % capacity;
 246     if (newPop == push) {
 247       return null;
 248     }
 249
 250     //Object dataPtr = queuePtr.elements[newPop];
 251     //queuePtr.pop = newPop;
 252     Object dataPtr = elements[newPop];
 253     pop = newPop;
 254
 255     return dataPtr;
 256   }
 257
 258
 259 }
 260 /* =============================================================================
 261  *
 262  * End of queue.java
 263  *
 264  * =============================================================================
 265  */