1
2
3
4
5
6
7
8
9
10
11
12
13
14 package org.eclipse.jetty.util;
15
16 import java.util.AbstractList;
17 import java.util.NoSuchElementException;
18 import java.util.Queue;
19
20
21
22
23
24
25
26
27
28 public class ArrayQueue<E> extends AbstractList<E> implements Queue<E>
29 {
30 public final int DEFAULT_CAPACITY=64;
31 public final int DEFAULT_GROWTH=32;
32 protected Object _lock=this;
33 protected Object[] _elements;
34 protected int _nextE;
35 protected int _nextSlot;
36 protected volatile int _size;
37 protected int _growCapacity;
38
39
40 public ArrayQueue()
41 {
42 _elements=new Object[64];
43 _growCapacity=32;
44 }
45
46
47 public ArrayQueue(int capacity)
48 {
49 _elements=new Object[capacity];
50 _growCapacity=-1;
51 }
52
53
54 public ArrayQueue(int initCapacity,int growBy)
55 {
56 _elements=new Object[initCapacity];
57 _growCapacity=growBy;
58 }
59
60
61 public ArrayQueue(int initCapacity,int growBy,Object lock)
62 {
63 _elements=new Object[initCapacity];
64 _growCapacity=growBy;
65 _lock=lock;
66 }
67
68
69 public int getCapacity()
70 {
71 return _elements.length;
72 }
73
74
75 @Override
76 public boolean add(E e)
77 {
78 if (!offer(e))
79 throw new IllegalStateException("Full");
80 return true;
81 }
82
83
84 public boolean offer(E e)
85 {
86 synchronized(_lock)
87 {
88 if (_size==_elements.length && !grow())
89 return false;
90
91 _size++;
92 _elements[_nextSlot++]=e;
93 if (_nextSlot==_elements.length)
94 _nextSlot=0;
95 }
96 return true;
97 }
98
99
100
101
102
103
104 public void addUnsafe(E e)
105 {
106 if (_size==_elements.length && !grow())
107 throw new IllegalStateException("Full");
108
109 _size++;
110 _elements[_nextSlot++]=e;
111 if (_nextSlot==_elements.length)
112 _nextSlot=0;
113 }
114
115
116 public E element()
117 {
118 synchronized(_lock)
119 {
120 if (_size==0)
121 throw new NoSuchElementException();
122 return (E)_elements[_nextE];
123 }
124 }
125
126
127 public E peek()
128 {
129 synchronized(_lock)
130 {
131 if (_size==0)
132 return null;
133 return (E)_elements[_nextE];
134 }
135 }
136
137
138 public E poll()
139 {
140 synchronized(_lock)
141 {
142 if (_size==0)
143 return null;
144 E e = (E)_elements[_nextE];
145 _elements[_nextE]=null;
146 _size--;
147 if (++_nextE==_elements.length)
148 _nextE=0;
149 return e;
150 }
151 }
152
153
154 public E remove()
155 {
156 synchronized(_lock)
157 {
158 if (_size==0)
159 throw new NoSuchElementException();
160 E e = (E)_elements[_nextE];
161 _elements[_nextE]=null;
162 _size--;
163 if (++_nextE==_elements.length)
164 _nextE=0;
165 return e;
166 }
167 }
168
169
170 @Override
171 public void clear()
172 {
173 synchronized(_lock)
174 {
175 _size=0;
176 _nextE=0;
177 _nextSlot=0;
178 }
179 }
180
181
182 @Override
183 public boolean isEmpty()
184 {
185 synchronized(_lock)
186 {
187 return _size==0;
188 }
189 }
190
191
192
193 @Override
194 public int size()
195 {
196 return _size;
197 }
198
199
200 @Override
201 public E get(int index)
202 {
203 synchronized(_lock)
204 {
205 if (index<0 || index>=_size)
206 throw new IndexOutOfBoundsException("!("+0+"<"+index+"<="+_size+")");
207 int i = (_nextE+index)%_elements.length;
208 return (E)_elements[i];
209 }
210 }
211
212
213
214
215
216
217 public E getUnsafe(int index)
218 {
219 int i = (_nextE+index)%_elements.length;
220 return (E)_elements[i];
221 }
222
223
224 @Override
225 public E remove(int index)
226 {
227 synchronized(_lock)
228 {
229 if (index<0 || index>=_size)
230 throw new IndexOutOfBoundsException("!("+0+"<"+index+"<="+_size+")");
231
232 int i = (_nextE+index)%_elements.length;
233 E old=(E)_elements[i];
234
235 if (i<_nextSlot)
236 {
237
238
239 System.arraycopy(_elements,i+1,_elements,i,_nextSlot-i);
240 _nextSlot--;
241 _size--;
242 }
243 else
244 {
245
246
247 System.arraycopy(_elements,i+1,_elements,i,_elements.length-i-1);
248 if (_nextSlot>0)
249 {
250 _elements[_elements.length-1]=_elements[0];
251 System.arraycopy(_elements,1,_elements,0,_nextSlot-1);
252 _nextSlot--;
253 }
254 else
255 _nextSlot=_elements.length-1;
256
257 _size--;
258 }
259
260 return old;
261 }
262 }
263
264
265 @Override
266 public E set(int index, E element)
267 {
268 synchronized(_lock)
269 {
270 if (index<0 || index>=_size)
271 throw new IndexOutOfBoundsException("!("+0+"<"+index+"<="+_size+")");
272
273 int i = _nextE+index;
274 if (i>=_elements.length)
275 i-=_elements.length;
276 E old=(E)_elements[i];
277 _elements[i]=element;
278 return old;
279 }
280 }
281
282
283 @Override
284 public void add(int index, E element)
285 {
286 synchronized(_lock)
287 {
288 if (index<0 || index>_size)
289 throw new IndexOutOfBoundsException("!("+0+"<"+index+"<="+_size+")");
290
291 if (_size==_elements.length && !grow())
292 throw new IllegalStateException("Full");
293
294 if (index==_size)
295 {
296 add(element);
297 }
298 else
299 {
300 int i = _nextE+index;
301 if (i>=_elements.length)
302 i-=_elements.length;
303
304 _size++;
305 _nextSlot++;
306 if (_nextSlot==_elements.length)
307 _nextSlot=0;
308
309 if (i<_nextSlot)
310 {
311
312
313
314
315 System.arraycopy(_elements,i,_elements,i+1,_nextSlot-i);
316 _elements[i]=element;
317 }
318 else
319 {
320
321
322 if (_nextSlot>0)
323 {
324 System.arraycopy(_elements,0,_elements,1,_nextSlot);
325 _elements[0]=_elements[_elements.length-1];
326 }
327
328 System.arraycopy(_elements,i,_elements,i+1,_elements.length-i-1);
329 _elements[i]=element;
330 }
331 }
332 }
333 }
334
335 protected boolean grow()
336 {
337 if (_growCapacity<=0)
338 return false;
339
340 Object[] elements=new Object[_elements.length+_growCapacity];
341
342 int split=_elements.length-_nextE;
343 if (split>0)
344 System.arraycopy(_elements,_nextE,elements,0,split);
345 if (_nextE!=0)
346 System.arraycopy(_elements,0,elements,split,_nextSlot);
347
348 _elements=elements;
349 _nextE=0;
350 _nextSlot=_size;
351 return true;
352 }
353
354 }