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