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    * queue_isEmpty
  74    * =============================================================================
  75    */
  76   public boolean queue_isEmpty () {
  77     //int pop      = queuePtr.pop;
  78     //int push     = queuePtr.push;
  79     //int capacity = queuePtr.capacity;
  80
  81     return (pop + 1) % capacity == push;
  82   }
  83
  84
  85   /* =============================================================================
  86    * queue_clear
  87    * =============================================================================
  88    */
  89   public void
  90     queue_clear ()
  91     {
  92       pop  = capacity - 1;
  93       push = 0;
  94     }
  95
  96
  97   /* =============================================================================
  98    * TMqueue_isEmpty
  99    * =============================================================================
 100    */
 101
 102
 103
 104   /* =============================================================================
 105    * queue_push
 106    * =============================================================================
 107    */
 108   public boolean queue_push (Object dataPtr) {
 109     if(pop == push) {
 110
 111       System.out.println("push == pop in Queue.java");
 112       return false;
 113     }
 114
 115
 116     /* Need to resize */
 117     int newPush = (push + 1) % capacity;
 118     if (newPush == pop) {
 119
 120       int newCapacity = capacity * QUEUE_GROWTH_FACTOR;
 121       Object[] newElements = new Object[newCapacity];
 122       if (newElements == null) {
 123         return false;
 124       }
 125
 126       int dst = 0;
 127       Object[] tmpelements = elements;
 128       if (pop < push) {
 129         int src;
 130         for (src = (pop + 1); src < push; src++, dst++) {
 131           newElements[dst] = elements[src];
 132         }
 133       } else {
 134         int src;
 135         for (src = (pop + 1); src < capacity; src++, dst++) {
 136           newElements[dst] = elements[src];
 137         }
 138         for (src = 0; src < push; src++, dst++) {
 139           newElements[dst] = elements[src];
 140         }
 141       }
 142
 143       //elements = null;
 144       elements = newElements;
 145       pop      = newCapacity - 1;
 146       capacity = newCapacity;
 147       push = dst;
 148       newPush = push + 1; /* no need modulo */
 149     }
 150
 151     elements[push] = dataPtr;
 152     push = newPush;
 153
 154     return true;
 155   }
 156
 157
 158   /* =============================================================================
 159    * Pqueue_push
 160    * =============================================================================
 161    */
 162   public boolean
 163     Pqueue_push (Queue_t queuePtr, Object dataPtr)
 164     {
 165       int pop      = queuePtr.pop;
 166       int push     = queuePtr.push;
 167       int capacity = queuePtr.capacity;
 168
 169       if(pop == push) {
 170         System.out.println("push == pop in Queue.java");
 171         return false;
 172       }
 173
 174       /* Need to resize */
 175       int newPush = (push + 1) % capacity;
 176       if (newPush == pop) {
 177
 178         int newCapacity = capacity * QUEUE_GROWTH_FACTOR;
 179         Object[] newElements = new Object[newCapacity];
 180         if (newElements == null) {
 181           return false;
 182         }
 183
 184         int dst = 0;
 185         Object[] elements = queuePtr.elements;
 186         if (pop < push) {
 187           int src;
 188           for (src = (pop + 1); src < push; src++, dst++) {
 189             newElements[dst] = elements[src];
 190           }
 191         } else {
 192           int src;
 193           for (src = (pop + 1); src < capacity; src++, dst++) {
 194             newElements[dst] = elements[src];
 195           }
 196           for (src = 0; src < push; src++, dst++) {
 197             newElements[dst] = elements[src];
 198           }
 199         }
 200
 201         elements = null;
 202         queuePtr.elements = newElements;
 203         queuePtr.pop      = newCapacity - 1;
 204         queuePtr.capacity = newCapacity;
 205         push = dst;
 206         newPush = push + 1; /* no need modulo */
 207
 208       }
 209
 210       queuePtr.elements[push] = dataPtr;
 211       queuePtr.push = newPush;
 212
 213       return true;
 214     }
 215
 216   /* =============================================================================
 217    * queue_pop
 218    * =============================================================================
 219    */
 220   public Object queue_pop () {
 221     int newPop = (pop + 1) % capacity;
 222     if (newPop == push) {
 223       return null;
 224     }
 225
 226     //Object dataPtr = queuePtr.elements[newPop];
 227     //queuePtr.pop = newPop;
 228     Object dataPtr = elements[newPop];
 229     pop = newPop;
 230
 231     return dataPtr;
 232   }
 233
 234
 235 }
 236 /* =============================================================================
 237  *
 238  * End of queue.java
 239  *
 240  * =============================================================================
 241  */