2 // ========================================================================
3 // Copyright (c) 1995-2014 Mort Bay Consulting Pty. Ltd.
4 // ------------------------------------------------------------------------
5 // All rights reserved. This program and the accompanying materials
6 // are made available under the terms of the Eclipse Public License v1.0
7 // and Apache License v2.0 which accompanies this distribution.
9 // The Eclipse Public License is available at
10 // http://www.eclipse.org/legal/epl-v10.html
12 // The Apache License v2.0 is available at
13 // http://www.opensource.org/licenses/apache2.0.php
15 // You may elect to redistribute this code under either of these licenses.
16 // ========================================================================
19 package org.eclipse.jetty.util;
21 import java.util.AbstractList;
22 import java.util.NoSuchElementException;
23 import java.util.Queue;
25 /* ------------------------------------------------------------ */
27 * Queue backed by circular array.
29 * This partial Queue implementation (also with {@link #remove()} for stack operation)
30 * is backed by a growable circular array.
34 public class ArrayQueue<E> extends AbstractList<E> implements Queue<E>
36 public static final int DEFAULT_CAPACITY = 64;
37 public static final int DEFAULT_GROWTH = 32;
39 protected final Object _lock;
40 protected final int _growCapacity;
41 protected Object[] _elements;
43 protected int _nextSlot;
46 /* ------------------------------------------------------------ */
49 this(DEFAULT_CAPACITY, -1);
52 /* ------------------------------------------------------------ */
53 public ArrayQueue(Object lock)
55 this(DEFAULT_CAPACITY, -1,lock);
58 /* ------------------------------------------------------------ */
59 public ArrayQueue(int capacity)
64 /* ------------------------------------------------------------ */
65 public ArrayQueue(int initCapacity, int growBy)
67 this(initCapacity, growBy, null);
70 /* ------------------------------------------------------------ */
71 public ArrayQueue(int initCapacity, int growBy, Object lock)
73 _lock = lock == null ? this : lock;
74 _growCapacity = growBy;
75 _elements = new Object[initCapacity];
78 /* ------------------------------------------------------------ */
84 /* ------------------------------------------------------------ */
85 public int getCapacity()
89 return _elements.length;
93 /* ------------------------------------------------------------ */
95 public boolean add(E e)
98 throw new IllegalStateException("Full");
102 /* ------------------------------------------------------------ */
103 public boolean offer(E e)
111 /* ------------------------------------------------------------ */
112 private boolean enqueue(E e)
114 if (_size == _elements.length && !grow())
118 _elements[_nextSlot++] = e;
119 if (_nextSlot == _elements.length)
125 /* ------------------------------------------------------------ */
127 * Add without synchronization or bounds checking
129 * @param e the element to add
132 public void addUnsafe(E e)
135 throw new IllegalStateException("Full");
138 /* ------------------------------------------------------------ */
144 throw new NoSuchElementException();
149 /* ------------------------------------------------------------ */
150 @SuppressWarnings("unchecked")
151 private E at(int index)
153 return (E)_elements[index];
156 /* ------------------------------------------------------------ */
167 /* ------------------------------------------------------------ */
168 public E peekUnsafe()
175 /* ------------------------------------------------------------ */
186 /* ------------------------------------------------------------ */
187 public E pollUnsafe()
194 /* ------------------------------------------------------------ */
198 _elements[_nextE] = null;
200 if (++_nextE == _elements.length)
205 /* ------------------------------------------------------------ */
211 throw new NoSuchElementException();
216 /* ------------------------------------------------------------ */
228 /* ------------------------------------------------------------ */
230 public boolean isEmpty()
238 /* ------------------------------------------------------------ */
248 /* ------------------------------------------------------------ */
250 public E get(int index)
254 if (index < 0 || index >= _size)
255 throw new IndexOutOfBoundsException("!(" + 0 + "<" + index + "<=" + _size + ")");
256 return getUnsafe(index);
260 /* ------------------------------------------------------------ */
262 * Get without synchronization or bounds checking.
264 * @param index index of the element to return
265 * @return the element at the specified index
268 public E getUnsafe(int index)
270 int i = (_nextE + index) % _elements.length;
274 /* ------------------------------------------------------------ */
276 public E remove(int index)
280 if (index < 0 || index >= _size)
281 throw new IndexOutOfBoundsException("!(" + 0 + "<" + index + "<=" + _size + ")");
283 int i = (_nextE + index) % _elements.length;
288 // 0 _elements.length
289 // _nextE........._nextSlot
290 System.arraycopy(_elements, i + 1, _elements, i, _nextSlot - i);
296 // 0 _elements.length
297 // ......_nextSlot _nextE..........
298 System.arraycopy(_elements, i + 1, _elements, i, _elements.length - i - 1);
301 _elements[_elements.length - 1] = _elements[0];
302 System.arraycopy(_elements, 1, _elements, 0, _nextSlot - 1);
306 _nextSlot = _elements.length - 1;
315 /* ------------------------------------------------------------ */
317 public E set(int index, E element)
321 if (index < 0 || index >= _size)
322 throw new IndexOutOfBoundsException("!(" + 0 + "<" + index + "<=" + _size + ")");
324 int i = _nextE + index;
325 if (i >= _elements.length)
326 i -= _elements.length;
328 _elements[i] = element;
333 /* ------------------------------------------------------------ */
335 public void add(int index, E element)
339 if (index < 0 || index > _size)
340 throw new IndexOutOfBoundsException("!(" + 0 + "<" + index + "<=" + _size + ")");
342 if (_size == _elements.length && !grow())
343 throw new IllegalStateException("Full");
351 int i = _nextE + index;
352 if (i >= _elements.length)
353 i -= _elements.length;
357 if (_nextSlot == _elements.length)
362 // 0 _elements.length
363 // _nextE.....i..._nextSlot
364 // 0 _elements.length
365 // ..i..._nextSlot _nextE..........
366 System.arraycopy(_elements, i, _elements, i + 1, _nextSlot - i);
367 _elements[i] = element;
371 // 0 _elements.length
372 // ......_nextSlot _nextE.....i....
375 System.arraycopy(_elements, 0, _elements, 1, _nextSlot);
376 _elements[0] = _elements[_elements.length - 1];
379 System.arraycopy(_elements, i, _elements, i + 1, _elements.length - i - 1);
380 _elements[i] = element;
386 /* ------------------------------------------------------------ */
387 protected boolean grow()
391 if (_growCapacity <= 0)
394 Object[] elements = new Object[_elements.length + _growCapacity];
396 int split = _elements.length - _nextE;
398 System.arraycopy(_elements, _nextE, elements, 0, split);
400 System.arraycopy(_elements, 0, elements, split, _nextSlot);
402 _elements = elements;