| // |
| // ======================================================================== |
| // 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(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 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 (isEmpty()) |
| return null; |
| return at(_nextE); |
| } |
| } |
| |
| /* ------------------------------------------------------------ */ |
| public E poll() |
| { |
| synchronized (_lock) |
| { |
| 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; |
| } |
| } |
| } |