1 //
2 // ========================================================================
3 // Copyright (c) 1995-2013 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.
8 //
9 // The Eclipse Public License is available at
10 // http://www.eclipse.org/legal/epl-v10.html
11 //
12 // The Apache License v2.0 is available at
13 // http://www.opensource.org/licenses/apache2.0.php
14 //
15 // You may elect to redistribute this code under either of these licenses.
16 // ========================================================================
17 //
18
19 package org.eclipse.jetty.util;
20
21 import java.util.AbstractList;
22 import java.util.NoSuchElementException;
23 import java.util.Queue;
24
25 /* ------------------------------------------------------------ */
26 /**
27 * Queue backed by circular array.
28 * <p/>
29 * This partial Queue implementation (also with {@link #remove()} for stack operation)
30 * is backed by a growable circular array.
31 *
32 * @param <E>
33 */
34 public class ArrayQueue<E> extends AbstractList<E> implements Queue<E>
35 {
36 public static final int DEFAULT_CAPACITY = 64;
37 public static final int DEFAULT_GROWTH = 32;
38
39 protected final Object _lock;
40 protected final int _growCapacity;
41 protected Object[] _elements;
42 protected int _nextE;
43 protected int _nextSlot;
44 protected int _size;
45
46 /* ------------------------------------------------------------ */
47 public ArrayQueue()
48 {
49 this(DEFAULT_CAPACITY, -1);
50 }
51
52 /* ------------------------------------------------------------ */
53 public ArrayQueue(int capacity)
54 {
55 this(capacity, -1);
56 }
57
58 /* ------------------------------------------------------------ */
59 public ArrayQueue(int initCapacity, int growBy)
60 {
61 this(initCapacity, growBy, null);
62 }
63
64 /* ------------------------------------------------------------ */
65 public ArrayQueue(int initCapacity, int growBy, Object lock)
66 {
67 _lock = lock == null ? this : lock;
68 _growCapacity = growBy;
69 _elements = new Object[initCapacity];
70 }
71
72 /* ------------------------------------------------------------ */
73 public Object lock()
74 {
75 return _lock;
76 }
77
78 /* ------------------------------------------------------------ */
79 public int getCapacity()
80 {
81 synchronized (_lock)
82 {
83 return _elements.length;
84 }
85 }
86
87 /* ------------------------------------------------------------ */
88 @Override
89 public boolean add(E e)
90 {
91 if (!offer(e))
92 throw new IllegalStateException("Full");
93 return true;
94 }
95
96 /* ------------------------------------------------------------ */
97 public boolean offer(E e)
98 {
99 synchronized (_lock)
100 {
101 return enqueue(e);
102 }
103 }
104
105 /* ------------------------------------------------------------ */
106 private boolean enqueue(E e)
107 {
108 if (_size == _elements.length && !grow())
109 return false;
110
111 _size++;
112 _elements[_nextSlot++] = e;
113 if (_nextSlot == _elements.length)
114 _nextSlot = 0;
115
116 return true;
117 }
118
119 /* ------------------------------------------------------------ */
120 /**
121 * Add without synchronization or bounds checking
122 *
123 * @param e the element to add
124 * @see #add(Object)
125 */
126 public void addUnsafe(E e)
127 {
128 if (!enqueue(e))
129 throw new IllegalStateException("Full");
130 }
131
132 /* ------------------------------------------------------------ */
133 public E element()
134 {
135 synchronized (_lock)
136 {
137 if (isEmpty())
138 throw new NoSuchElementException();
139 return at(_nextE);
140 }
141 }
142
143 /* ------------------------------------------------------------ */
144 @SuppressWarnings("unchecked")
145 private E at(int index)
146 {
147 return (E)_elements[index];
148 }
149
150 /* ------------------------------------------------------------ */
151 public E peek()
152 {
153 synchronized (_lock)
154 {
155 if (_size == 0)
156 return null;
157 return at(_nextE);
158 }
159 }
160
161 /* ------------------------------------------------------------ */
162 public E peekUnsafe()
163 {
164 if (_size == 0)
165 return null;
166 return at(_nextE);
167 }
168
169 /* ------------------------------------------------------------ */
170 public E poll()
171 {
172 synchronized (_lock)
173 {
174 if (_size == 0)
175 return null;
176 return dequeue();
177 }
178 }
179
180 /* ------------------------------------------------------------ */
181 public E pollUnsafe()
182 {
183 if (_size == 0)
184 return null;
185 return dequeue();
186 }
187
188 /* ------------------------------------------------------------ */
189 private E dequeue()
190 {
191 E e = at(_nextE);
192 _elements[_nextE] = null;
193 _size--;
194 if (++_nextE == _elements.length)
195 _nextE = 0;
196 return e;
197 }
198
199 /* ------------------------------------------------------------ */
200 public E remove()
201 {
202 synchronized (_lock)
203 {
204 if (_size == 0)
205 throw new NoSuchElementException();
206 return dequeue();
207 }
208 }
209
210 /* ------------------------------------------------------------ */
211 @Override
212 public void clear()
213 {
214 synchronized (_lock)
215 {
216 _size = 0;
217 _nextE = 0;
218 _nextSlot = 0;
219 }
220 }
221
222 /* ------------------------------------------------------------ */
223 @Override
224 public boolean isEmpty()
225 {
226 synchronized (_lock)
227 {
228 return _size == 0;
229 }
230 }
231
232 /* ------------------------------------------------------------ */
233 @Override
234 public int size()
235 {
236 synchronized (_lock)
237 {
238 return _size;
239 }
240 }
241
242 /* ------------------------------------------------------------ */
243 @Override
244 public E get(int index)
245 {
246 synchronized (_lock)
247 {
248 if (index < 0 || index >= _size)
249 throw new IndexOutOfBoundsException("!(" + 0 + "<" + index + "<=" + _size + ")");
250 return getUnsafe(index);
251 }
252 }
253
254 /* ------------------------------------------------------------ */
255 /**
256 * Get without synchronization or bounds checking.
257 *
258 * @param index index of the element to return
259 * @return the element at the specified index
260 * @see #get(int)
261 */
262 public E getUnsafe(int index)
263 {
264 int i = (_nextE + index) % _elements.length;
265 return at(i);
266 }
267
268 /* ------------------------------------------------------------ */
269 @Override
270 public E remove(int index)
271 {
272 synchronized (_lock)
273 {
274 if (index < 0 || index >= _size)
275 throw new IndexOutOfBoundsException("!(" + 0 + "<" + index + "<=" + _size + ")");
276
277 int i = (_nextE + index) % _elements.length;
278 E old = at(i);
279
280 if (i < _nextSlot)
281 {
282 // 0 _elements.length
283 // _nextE........._nextSlot
284 System.arraycopy(_elements, i + 1, _elements, i, _nextSlot - i);
285 _nextSlot--;
286 _size--;
287 }
288 else
289 {
290 // 0 _elements.length
291 // ......_nextSlot _nextE..........
292 System.arraycopy(_elements, i + 1, _elements, i, _elements.length - i - 1);
293 if (_nextSlot > 0)
294 {
295 _elements[_elements.length - 1] = _elements[0];
296 System.arraycopy(_elements, 1, _elements, 0, _nextSlot - 1);
297 _nextSlot--;
298 }
299 else
300 _nextSlot = _elements.length - 1;
301
302 _size--;
303 }
304
305 return old;
306 }
307 }
308
309 /* ------------------------------------------------------------ */
310 @Override
311 public E set(int index, E element)
312 {
313 synchronized (_lock)
314 {
315 if (index < 0 || index >= _size)
316 throw new IndexOutOfBoundsException("!(" + 0 + "<" + index + "<=" + _size + ")");
317
318 int i = _nextE + index;
319 if (i >= _elements.length)
320 i -= _elements.length;
321 E old = at(i);
322 _elements[i] = element;
323 return old;
324 }
325 }
326
327 /* ------------------------------------------------------------ */
328 @Override
329 public void add(int index, E element)
330 {
331 synchronized (_lock)
332 {
333 if (index < 0 || index > _size)
334 throw new IndexOutOfBoundsException("!(" + 0 + "<" + index + "<=" + _size + ")");
335
336 if (_size == _elements.length && !grow())
337 throw new IllegalStateException("Full");
338
339 if (index == _size)
340 {
341 add(element);
342 }
343 else
344 {
345 int i = _nextE + index;
346 if (i >= _elements.length)
347 i -= _elements.length;
348
349 _size++;
350 _nextSlot++;
351 if (_nextSlot == _elements.length)
352 _nextSlot = 0;
353
354 if (i < _nextSlot)
355 {
356 // 0 _elements.length
357 // _nextE.....i..._nextSlot
358 // 0 _elements.length
359 // ..i..._nextSlot _nextE..........
360 System.arraycopy(_elements, i, _elements, i + 1, _nextSlot - i);
361 _elements[i] = element;
362 }
363 else
364 {
365 // 0 _elements.length
366 // ......_nextSlot _nextE.....i....
367 if (_nextSlot > 0)
368 {
369 System.arraycopy(_elements, 0, _elements, 1, _nextSlot);
370 _elements[0] = _elements[_elements.length - 1];
371 }
372
373 System.arraycopy(_elements, i, _elements, i + 1, _elements.length - i - 1);
374 _elements[i] = element;
375 }
376 }
377 }
378 }
379
380 /* ------------------------------------------------------------ */
381 protected boolean grow()
382 {
383 synchronized (_lock)
384 {
385 if (_growCapacity <= 0)
386 return false;
387
388 Object[] elements = new Object[_elements.length + _growCapacity];
389
390 int split = _elements.length - _nextE;
391 if (split > 0)
392 System.arraycopy(_elements, _nextE, elements, 0, split);
393 if (_nextE != 0)
394 System.arraycopy(_elements, 0, elements, split, _nextSlot);
395
396 _elements = elements;
397 _nextE = 0;
398 _nextSlot = _size;
399 return true;
400 }
401 }
402 }