Robust/src/Benchmarks/Recovery/Spider/recovery/GlobalQueue.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 public class GlobalQueue{
  53   int pop; /* points before element to pop */
  54   int push;
  55   int capacity;
  56   int size;
  57   int QUEUE_GROWTH_FACTOR;
  58   Object[] elements;
  59
  60   public GlobalQueue() {
  61                 GlobalQueue(10);
  62   }
  63
  64   /* =============================================================================
  65    * queue_alloc
  66    * =============================================================================
  67    */
  68   public GlobalQueue (int initCapacity)
  69   {
  70     QUEUE_GROWTH_FACTOR = 2;
  71     capacity = ((initCapacity < 2) ? 2 : initCapacity);
  72
  73     elements = global new Object[capacity];
  74     size = 0;
  75     pop      = capacity - 1;
  76     push     = 0;
  77     capacity = capacity;
  78   }
  79
  80   /* =============================================================================
  81    * queue_isEmpty
  82    * =============================================================================
  83    */
  84   public boolean
  85     isEmpty ()
  86     {
  87       return (((pop + 1) % capacity == push) ? true : false);
  88     }
  89
  90
  91   /* =============================================================================
  92    * queue_clear
  93    * =============================================================================
  94    */
  95   public void
  96     queue_clear ()
  97     {
  98       pop  = capacity - 1;
  99       push = 0;
 100     }
 101
 102   /* =============================================================================
 103    * queue_push
 104    * =============================================================================
 105    */
 106   public boolean
 107     push (Object dataPtr)
 108     {
 109       if(pop == push) {
 110 //        System.out.println("push == pop in Queue.java");
 111         return false;
 112       }
 113
 114       /* Need to resize */
 115       int newPush = (push + 1) % capacity;
 116       if (newPush == pop) {
 117
 118         int newCapacity = capacity * QUEUE_GROWTH_FACTOR;
 119         Object[] newElements = global new Object[newCapacity];
 120
 121         if (newElements == null) {
 122           return false;
 123         }
 124
 125         int dst = 0;
 126         Object[] tmpelements = elements;
 127         if (pop < push) {
 128           int src;
 129           for (src = (pop + 1); src < push; src++, dst++) {
 130             newElements[dst] = elements[src];
 131           }
 132         } else {
 133           int src;
 134           for (src = (pop + 1); src < capacity; src++, dst++) {
 135             newElements[dst] = elements[src];
 136           }
 137           for (src = 0; src < push; src++, dst++) {
 138             newElements[dst] = elements[src];
 139           }
 140         }
 141
 142         //elements = null;
 143         elements = newElements;
 144         pop      = newCapacity - 1;
 145         capacity = newCapacity;
 146         push = dst;
 147         newPush = push + 1; /* no need modulo */
 148       }
 149       size++;
 150       elements[push] = dataPtr;
 151       push = newPush;
 152
 153       return true;
 154     }
 155
 156
 157   /* =============================================================================
 158    * queue_pop
 159    * =============================================================================
 160    */
 161   public Object
 162     pop ()
 163     {
 164       int newPop = (pop + 1) % capacity;
 165       if (newPop == push) {
 166         return null;
 167       }
 168
 169       //Object dataPtr = queuePtr.elements[newPop];
 170       //queuePtr.pop = newPop;
 171       Object dataPtr = elements[newPop];
 172       pop = newPop;
 173       size--;
 174       return dataPtr;
 175     }
 176   public int size()
 177   {
 178     return size;
 179   }
 180
 181 }
 182 /* =============================================================================
 183  *
 184  * End of queue.java
 185  *
 186  * =============================================================================
 187  */