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    * Pqueue_alloc
  75    * =============================================================================
  76    */
  77   public Queue_t
  78     Pqueue_alloc (int initCapacity)
  79     {
  80       Queue_t queuePtr = new Queue_t();
  81
  82       int capacity = ((initCapacity < 2) ? 2 : initCapacity);
  83       queuePtr.elements = new Object[capacity];
  84       if (queuePtr.elements == null) {
  85         queuePtr = null;
  86         return null;
  87       }
  88       queuePtr.pop      = capacity - 1;
  89       queuePtr.push     = 0;
  90       queuePtr.capacity = capacity;
  91
  92       return queuePtr;
  93     }
  94
  95   /* =============================================================================
  96    * queue_free
  97    * =============================================================================
  98    */
  99   public void queue_free (Queue_t queuePtr) {
 100     queuePtr.elements = null;
 101     queuePtr = null;
 102   }
 103
 104
 105   /* =============================================================================
 106    * Pqueue_free
 107    * =============================================================================
 108    */
 109   public void
 110     Pqueue_free (Queue_t queuePtr)
 111     {
 112       queuePtr.elements = null;
 113       queuePtr = null;
 114     }
 115
 116
 117   /* =============================================================================
 118    * TMqueue_free
 119    * =============================================================================
 120    *
 121   public void
 122     TMqueue_free (TM_ARGDECL  Queue* queuePtr)
 123     {
 124       queuePtr.elements = null;
 125       queuePtr = null;
 126     }
 127
 128 */
 129   /* =============================================================================
 130    * queue_isEmpty
 131    * =============================================================================
 132    */
 133   public boolean queue_isEmpty () {
 134     //int pop      = queuePtr.pop;
 135     //int push     = queuePtr.push;
 136     //int capacity = queuePtr.capacity;
 137
 138     return (pop + 1) % capacity == push;
 139   }
 140
 141
 142   /* =============================================================================
 143    * queue_clear
 144    * =============================================================================
 145    */
 146   public void
 147     queue_clear ()
 148     {
 149       pop  = capacity - 1;
 150       push = 0;
 151     }
 152
 153
 154   /* =============================================================================
 155    * TMqueue_isEmpty
 156    * =============================================================================
 157    */
 158
 159
 160
 161   /* =============================================================================
 162    * queue_push
 163    * =============================================================================
 164    */
 165   public boolean queue_push (Object dataPtr) {
 166     if(pop == push) {
 167
 168       System.out.println("push == pop in Queue.java");
 169       return false;
 170     }
 171
 172
 173     /* Need to resize */
 174     int newPush = (push + 1) % capacity;
 175     if (newPush == pop) {
 176
 177       int newCapacity = capacity * QUEUE_GROWTH_FACTOR;
 178       Object[] newElements = new Object[newCapacity];
 179       if (newElements == null) {
 180         return false;
 181       }
 182
 183       int dst = 0;
 184       Object[] tmpelements = elements;
 185       if (pop < push) {
 186         int src;
 187         for (src = (pop + 1); src < push; src++, dst++) {
 188           newElements[dst] = elements[src];
 189         }
 190       } else {
 191         int src;
 192         for (src = (pop + 1); src < capacity; src++, dst++) {
 193           newElements[dst] = elements[src];
 194         }
 195         for (src = 0; src < push; src++, dst++) {
 196           newElements[dst] = elements[src];
 197         }
 198       }
 199
 200       //elements = null;
 201       elements = newElements;
 202       pop      = newCapacity - 1;
 203       capacity = newCapacity;
 204       push = dst;
 205       newPush = push + 1; /* no need modulo */
 206     }
 207
 208     elements[push] = dataPtr;
 209     push = newPush;
 210
 211     return true;
 212   }
 213
 214
 215   /* =============================================================================
 216    * Pqueue_push
 217    * =============================================================================
 218    */
 219   public boolean
 220     Pqueue_push (Queue_t queuePtr, Object dataPtr)
 221     {
 222       int pop      = queuePtr.pop;
 223       int push     = queuePtr.push;
 224       int capacity = queuePtr.capacity;
 225
 226       if(pop == push) {
 227         System.out.println("push == pop in Queue.java");
 228         return false;
 229       }
 230
 231       /* Need to resize */
 232       int newPush = (push + 1) % capacity;
 233       if (newPush == pop) {
 234
 235         int newCapacity = capacity * QUEUE_GROWTH_FACTOR;
 236         Object[] newElements = new Object[newCapacity];
 237         if (newElements == null) {
 238           return false;
 239         }
 240
 241         int dst = 0;
 242         Object[] elements = queuePtr.elements;
 243         if (pop < push) {
 244           int src;
 245           for (src = (pop + 1); src < push; src++, dst++) {
 246             newElements[dst] = elements[src];
 247           }
 248         } else {
 249           int src;
 250           for (src = (pop + 1); src < capacity; src++, dst++) {
 251             newElements[dst] = elements[src];
 252           }
 253           for (src = 0; src < push; src++, dst++) {
 254             newElements[dst] = elements[src];
 255           }
 256         }
 257
 258         elements = null;
 259         queuePtr.elements = newElements;
 260         queuePtr.pop      = newCapacity - 1;
 261         queuePtr.capacity = newCapacity;
 262         push = dst;
 263         newPush = push + 1; /* no need modulo */
 264
 265       }
 266
 267       queuePtr.elements[push] = dataPtr;
 268       queuePtr.push = newPush;
 269
 270       return true;
 271     }
 272
 273   /* =============================================================================
 274    * queue_pop
 275    * =============================================================================
 276    */
 277   public Object queue_pop () {
 278     int newPop = (pop + 1) % capacity;
 279     if (newPop == push) {
 280       return null;
 281     }
 282
 283     //Object dataPtr = queuePtr.elements[newPop];
 284     //queuePtr.pop = newPop;
 285     Object dataPtr = elements[newPop];
 286     pop = newPop;
 287
 288     return dataPtr;
 289   }
 290
 291
 292 }
 293 /* =============================================================================
 294  *
 295  * End of queue.java
 296  *
 297  * =============================================================================
 298  */