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