src/org/ibex/util/Queue.java

   1 // Copyright 2000-2005 the Contributors, as shown in the revision logs.
   2 // Licensed under the Apache Public Source License 2.0 ("the License").
   3 // You may not use this file except in compliance with the License.
   4
   5 package org.ibex.util;
   6
   7 /** A simple synchronized queue, implemented as an array */
   8 public class Queue {
   9
  10     public Queue(int initiallength) { vec = new Object[initiallength]; }
  11
  12     /** The store */
  13     private Object[] vec;
  14
  15     /** The index of the first node in the queue */
  16     private int first = 0;
  17
  18     /** The number of elements in the queue; INVARAINT: size <= vec.length */
  19     private int size = 0;
  20
  21     /** Grow the queue, if needed */
  22     private void grow(int newlength) {
  23         Object[] newvec = new Object[newlength];
  24         if (first + size > vec.length) {
  25             System.arraycopy(vec, first, newvec, 0, vec.length - first);
  26             System.arraycopy(vec, 0, newvec, vec.length - first, size - (vec.length - first));
  27         } else {
  28             System.arraycopy(vec, first, newvec, 0, size);
  29         }
  30         first = 0;
  31         vec = newvec;
  32     }
  33
  34     /** The number of elements in the queue */
  35     public int size() { return size; }
  36
  37     /** Empties the queue */
  38     public synchronized void flush() {
  39         first = 0;
  40         size = 0;
  41         for(int i=0; i<vec.length; i++) vec[i] = null;
  42     }
  43
  44     /** Add an element to the front of the queue */
  45     public synchronized void prepend(Object o) {
  46         if (size == vec.length) grow(vec.length * 2);
  47         first--;
  48         if (first < 0) first += vec.length;
  49         vec[first] = o;
  50         size++;
  51         if (size == 1) notify();
  52     }
  53
  54     /** Add an element to the back of the queue */
  55     public synchronized void append(Object o) {
  56         if (size == vec.length) grow(vec.length * 2);
  57         if (first + size >= vec.length) vec[first + size - vec.length] = o;
  58         else vec[first + size] = o;
  59         size++;
  60         if (size == 1) notify();
  61     }
  62
  63     /** Remove and return and element from the queue, blocking if empty. */
  64     public Object remove() { return remove(true); }
  65
  66     /** Remove and return an element from the queue, blocking if
  67         <tt>block</tt> is true and the queue is empty. */
  68     public synchronized Object remove(boolean block) {
  69
  70         while (size == 0 && block) {
  71             try { wait(); } catch (InterruptedException e) { }
  72         }
  73
  74         if (!block && size == 0) return null;
  75         Object ret = vec[first];
  76         first++;
  77         size--;
  78         if (first >= vec.length) first = 0;
  79         return ret;
  80     }
  81
  82     /** Returns the top element in the queue without removing it */
  83     public synchronized Object peek() {
  84         if (size == 0) return null;
  85         return vec[first];
  86     }
  87
  88 }