--- /dev/null
+//
+// ========================================================================
+// Copyright (c) 1995-2014 Mort Bay Consulting Pty. Ltd.
+// ------------------------------------------------------------------------
+// All rights reserved. This program and the accompanying materials
+// are made available under the terms of the Eclipse Public License v1.0
+// and Apache License v2.0 which accompanies this distribution.
+//
+// The Eclipse Public License is available at
+// http://www.eclipse.org/legal/epl-v10.html
+//
+// The Apache License v2.0 is available at
+// http://www.opensource.org/licenses/apache2.0.php
+//
+// You may elect to redistribute this code under either of these licenses.
+// ========================================================================
+//
+
+package org.eclipse.jetty.util;
+
+import java.util.AbstractList;
+import java.util.NoSuchElementException;
+import java.util.Queue;
+
+/* ------------------------------------------------------------ */
+/**
+ * Queue backed by circular array.
+ * <p/>
+ * This partial Queue implementation (also with {@link #remove()} for stack operation)
+ * is backed by a growable circular array.
+ *
+ * @param <E>
+ */
+public class ArrayQueue<E> extends AbstractList<E> implements Queue<E>
+{
+ public static final int DEFAULT_CAPACITY = 64;
+ public static final int DEFAULT_GROWTH = 32;
+
+ protected final Object _lock;
+ protected final int _growCapacity;
+ protected Object[] _elements;
+ protected int _nextE;
+ protected int _nextSlot;
+ protected int _size;
+
+ /* ------------------------------------------------------------ */
+ public ArrayQueue()
+ {
+ this(DEFAULT_CAPACITY, -1);
+ }
+
+ /* ------------------------------------------------------------ */
+ public ArrayQueue(Object lock)
+ {
+ this(DEFAULT_CAPACITY, -1,lock);
+ }
+
+ /* ------------------------------------------------------------ */
+ public ArrayQueue(int capacity)
+ {
+ this(capacity, -1);
+ }
+
+ /* ------------------------------------------------------------ */
+ public ArrayQueue(int initCapacity, int growBy)
+ {
+ this(initCapacity, growBy, null);
+ }
+
+ /* ------------------------------------------------------------ */
+ public ArrayQueue(int initCapacity, int growBy, Object lock)
+ {
+ _lock = lock == null ? this : lock;
+ _growCapacity = growBy;
+ _elements = new Object[initCapacity];
+ }
+
+ /* ------------------------------------------------------------ */
+ public Object lock()
+ {
+ return _lock;
+ }
+
+ /* ------------------------------------------------------------ */
+ public int getCapacity()
+ {
+ synchronized (_lock)
+ {
+ return _elements.length;
+ }
+ }
+
+ /* ------------------------------------------------------------ */
+ @Override
+ public boolean add(E e)
+ {
+ if (!offer(e))
+ throw new IllegalStateException("Full");
+ return true;
+ }
+
+ /* ------------------------------------------------------------ */
+ public boolean offer(E e)
+ {
+ synchronized (_lock)
+ {
+ return enqueue(e);
+ }
+ }
+
+ /* ------------------------------------------------------------ */
+ private boolean enqueue(E e)
+ {
+ if (_size == _elements.length && !grow())
+ return false;
+
+ _size++;
+ _elements[_nextSlot++] = e;
+ if (_nextSlot == _elements.length)
+ _nextSlot = 0;
+
+ return true;
+ }
+
+ /* ------------------------------------------------------------ */
+ /**
+ * Add without synchronization or bounds checking
+ *
+ * @param e the element to add
+ * @see #add(Object)
+ */
+ public void addUnsafe(E e)
+ {
+ if (!enqueue(e))
+ throw new IllegalStateException("Full");
+ }
+
+ /* ------------------------------------------------------------ */
+ public E element()
+ {
+ synchronized (_lock)
+ {
+ if (isEmpty())
+ throw new NoSuchElementException();
+ return at(_nextE);
+ }
+ }
+
+ /* ------------------------------------------------------------ */
+ @SuppressWarnings("unchecked")
+ private E at(int index)
+ {
+ return (E)_elements[index];
+ }
+
+ /* ------------------------------------------------------------ */
+ public E peek()
+ {
+ synchronized (_lock)
+ {
+ if (_size == 0)
+ return null;
+ return at(_nextE);
+ }
+ }
+
+ /* ------------------------------------------------------------ */
+ public E peekUnsafe()
+ {
+ if (_size == 0)
+ return null;
+ return at(_nextE);
+ }
+
+ /* ------------------------------------------------------------ */
+ public E poll()
+ {
+ synchronized (_lock)
+ {
+ if (_size == 0)
+ return null;
+ return dequeue();
+ }
+ }
+
+ /* ------------------------------------------------------------ */
+ public E pollUnsafe()
+ {
+ if (_size == 0)
+ return null;
+ return dequeue();
+ }
+
+ /* ------------------------------------------------------------ */
+ private E dequeue()
+ {
+ E e = at(_nextE);
+ _elements[_nextE] = null;
+ _size--;
+ if (++_nextE == _elements.length)
+ _nextE = 0;
+ return e;
+ }
+
+ /* ------------------------------------------------------------ */
+ public E remove()
+ {
+ synchronized (_lock)
+ {
+ if (_size == 0)
+ throw new NoSuchElementException();
+ return dequeue();
+ }
+ }
+
+ /* ------------------------------------------------------------ */
+ @Override
+ public void clear()
+ {
+ synchronized (_lock)
+ {
+ _size = 0;
+ _nextE = 0;
+ _nextSlot = 0;
+ }
+ }
+
+ /* ------------------------------------------------------------ */
+ @Override
+ public boolean isEmpty()
+ {
+ synchronized (_lock)
+ {
+ return _size == 0;
+ }
+ }
+
+ /* ------------------------------------------------------------ */
+ @Override
+ public int size()
+ {
+ synchronized (_lock)
+ {
+ return _size;
+ }
+ }
+
+ /* ------------------------------------------------------------ */
+ @Override
+ public E get(int index)
+ {
+ synchronized (_lock)
+ {
+ if (index < 0 || index >= _size)
+ throw new IndexOutOfBoundsException("!(" + 0 + "<" + index + "<=" + _size + ")");
+ return getUnsafe(index);
+ }
+ }
+
+ /* ------------------------------------------------------------ */
+ /**
+ * Get without synchronization or bounds checking.
+ *
+ * @param index index of the element to return
+ * @return the element at the specified index
+ * @see #get(int)
+ */
+ public E getUnsafe(int index)
+ {
+ int i = (_nextE + index) % _elements.length;
+ return at(i);
+ }
+
+ /* ------------------------------------------------------------ */
+ @Override
+ public E remove(int index)
+ {
+ synchronized (_lock)
+ {
+ if (index < 0 || index >= _size)
+ throw new IndexOutOfBoundsException("!(" + 0 + "<" + index + "<=" + _size + ")");
+
+ int i = (_nextE + index) % _elements.length;
+ E old = at(i);
+
+ if (i < _nextSlot)
+ {
+ // 0 _elements.length
+ // _nextE........._nextSlot
+ System.arraycopy(_elements, i + 1, _elements, i, _nextSlot - i);
+ _nextSlot--;
+ _size--;
+ }
+ else
+ {
+ // 0 _elements.length
+ // ......_nextSlot _nextE..........
+ System.arraycopy(_elements, i + 1, _elements, i, _elements.length - i - 1);
+ if (_nextSlot > 0)
+ {
+ _elements[_elements.length - 1] = _elements[0];
+ System.arraycopy(_elements, 1, _elements, 0, _nextSlot - 1);
+ _nextSlot--;
+ }
+ else
+ _nextSlot = _elements.length - 1;
+
+ _size--;
+ }
+
+ return old;
+ }
+ }
+
+ /* ------------------------------------------------------------ */
+ @Override
+ public E set(int index, E element)
+ {
+ synchronized (_lock)
+ {
+ if (index < 0 || index >= _size)
+ throw new IndexOutOfBoundsException("!(" + 0 + "<" + index + "<=" + _size + ")");
+
+ int i = _nextE + index;
+ if (i >= _elements.length)
+ i -= _elements.length;
+ E old = at(i);
+ _elements[i] = element;
+ return old;
+ }
+ }
+
+ /* ------------------------------------------------------------ */
+ @Override
+ public void add(int index, E element)
+ {
+ synchronized (_lock)
+ {
+ if (index < 0 || index > _size)
+ throw new IndexOutOfBoundsException("!(" + 0 + "<" + index + "<=" + _size + ")");
+
+ if (_size == _elements.length && !grow())
+ throw new IllegalStateException("Full");
+
+ if (index == _size)
+ {
+ add(element);
+ }
+ else
+ {
+ int i = _nextE + index;
+ if (i >= _elements.length)
+ i -= _elements.length;
+
+ _size++;
+ _nextSlot++;
+ if (_nextSlot == _elements.length)
+ _nextSlot = 0;
+
+ if (i < _nextSlot)
+ {
+ // 0 _elements.length
+ // _nextE.....i..._nextSlot
+ // 0 _elements.length
+ // ..i..._nextSlot _nextE..........
+ System.arraycopy(_elements, i, _elements, i + 1, _nextSlot - i);
+ _elements[i] = element;
+ }
+ else
+ {
+ // 0 _elements.length
+ // ......_nextSlot _nextE.....i....
+ if (_nextSlot > 0)
+ {
+ System.arraycopy(_elements, 0, _elements, 1, _nextSlot);
+ _elements[0] = _elements[_elements.length - 1];
+ }
+
+ System.arraycopy(_elements, i, _elements, i + 1, _elements.length - i - 1);
+ _elements[i] = element;
+ }
+ }
+ }
+ }
+
+ /* ------------------------------------------------------------ */
+ protected boolean grow()
+ {
+ synchronized (_lock)
+ {
+ if (_growCapacity <= 0)
+ return false;
+
+ Object[] elements = new Object[_elements.length + _growCapacity];
+
+ int split = _elements.length - _nextE;
+ if (split > 0)
+ System.arraycopy(_elements, _nextE, elements, 0, split);
+ if (_nextE != 0)
+ System.arraycopy(_elements, 0, elements, split, _nextSlot);
+
+ _elements = elements;
+ _nextE = 0;
+ _nextSlot = _size;
+ return true;
+ }
+ }
+}
projects / gigi.git / blobdiff