1 // ========================================================================
2 // Copyright (c) 2004-2009 Mort Bay Consulting Pty. Ltd.
3 // ------------------------------------------------------------------------
4 // All rights reserved. This program and the accompanying materials
5 // are made available under the terms of the Eclipse Public License v1.0
6 // and Apache License v2.0 which accompanies this distribution.
7 // The Eclipse Public License is available at
8 // http://www.eclipse.org/legal/epl-v10.html
9 // The Apache License v2.0 is available at
10 // http://www.opensource.org/licenses/apache2.0.php
11 // You may elect to redistribute this code under either of these licenses.
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 /** Queue backed by circular array.
22 *
23 * This partial Queue implementation (also with {@link #pop()} for stack operation)
24 * is backed by a growable circular array.
25 *
26 *
27 *
28 * @param <E>
29 */
30 public class ArrayQueue<E> extends AbstractList<E> implements Queue<E>
31 {
32 public final int DEFAULT_CAPACITY=64;
33 public final int DEFAULT_GROWTH=32;
34 protected Object _lock=this;
35 protected Object[] _elements;
36 protected int _nextE;
37 protected int _nextSlot;
38 protected int _size;
39 protected int _growCapacity;
40
41 /* ------------------------------------------------------------ */
42 public ArrayQueue()
43 {
44 _elements=new Object[64];
45 _growCapacity=32;
46 }
47
48 /* ------------------------------------------------------------ */
49 public ArrayQueue(int capacity)
50 {
51 _elements=new Object[capacity];
52 _growCapacity=-1;
53 }
54
55 /* ------------------------------------------------------------ */
56 public ArrayQueue(int initCapacity,int growBy)
57 {
58 _elements=new Object[initCapacity];
59 _growCapacity=growBy;
60 }
61
62 /* ------------------------------------------------------------ */
63 public ArrayQueue(int initCapacity,int growBy,Object lock)
64 {
65 _elements=new Object[initCapacity];
66 _growCapacity=growBy;
67 _lock=lock;
68 }
69
70 /* ------------------------------------------------------------ */
71 public int getCapacity()
72 {
73 return _elements.length;
74 }
75
76 /* ------------------------------------------------------------ */
77 @Override
78 public boolean add(E e)
79 {
80 if (!offer(e))
81 throw new IllegalStateException("Full");
82 return true;
83 }
84
85 /* ------------------------------------------------------------ */
86 public boolean offer(E e)
87 {
88 synchronized(_lock)
89 {
90 if (_size==_elements.length && !grow())
91 return false;
92
93 _size++;
94 _elements[_nextSlot++]=e;
95 if (_nextSlot==_elements.length)
96 _nextSlot=0;
97 }
98 return true;
99 }
100
101 /* ------------------------------------------------------------ */
102 /**
103 * Add without synchronization or bounds checking
104 * @see #add(Object)
105 */
106 public void addUnsafe(E e)
107 {
108 if (_size==_elements.length && !grow())
109 throw new IllegalStateException("Full");
110
111 _size++;
112 _elements[_nextSlot++]=e;
113 if (_nextSlot==_elements.length)
114 _nextSlot=0;
115 }
116
117 /* ------------------------------------------------------------ */
118 public E element()
119 {
120 synchronized(_lock)
121 {
122 if (_size==0)
123 throw new NoSuchElementException();
124 return (E)_elements[_nextE];
125 }
126 }
127
128 /* ------------------------------------------------------------ */
129 public E peek()
130 {
131 synchronized(_lock)
132 {
133 if (_size==0)
134 return null;
135 return (E)_elements[_nextE];
136 }
137 }
138
139 /* ------------------------------------------------------------ */
140 public E poll()
141 {
142 synchronized(_lock)
143 {
144 if (_size==0)
145 return null;
146 E e = (E)_elements[_nextE];
147 _elements[_nextE]=null;
148 _size--;
149 if (++_nextE==_elements.length)
150 _nextE=0;
151 return e;
152 }
153 }
154
155 /* ------------------------------------------------------------ */
156 public E remove()
157 {
158 synchronized(_lock)
159 {
160 if (_size==0)
161 throw new NoSuchElementException();
162 E e = (E)_elements[_nextE];
163 _elements[_nextE]=null;
164 _size--;
165 if (++_nextE==_elements.length)
166 _nextE=0;
167 return e;
168 }
169 }
170
171 /* ------------------------------------------------------------ */
172 @Override
173 public void clear()
174 {
175 synchronized(_lock)
176 {
177 _size=0;
178 _nextE=0;
179 _nextSlot=0;
180 }
181 }
182
183 /* ------------------------------------------------------------ */
184 public boolean isEmpty()
185 {
186 synchronized(_lock)
187 {
188 return _size==0;
189 }
190 }
191
192
193 /* ------------------------------------------------------------ */
194 @Override
195 public int size()
196 {
197 return _size;
198 }
199
200 /* ------------------------------------------------------------ */
201 @Override
202 public E get(int index)
203 {
204 synchronized(_lock)
205 {
206 if (index<0 || index>=_size)
207 throw new IndexOutOfBoundsException("!("+0+"<"+index+"<="+_size+")");
208 int i = (_nextE+index)%_elements.length;
209 return (E)_elements[i];
210 }
211 }
212
213 /* ------------------------------------------------------------ */
214 /**
215 * Get without synchronization or bounds checking.
216 * @see get(int)
217 */
218 public E getUnsafe(int index)
219 {
220 int i = (_nextE+index)%_elements.length;
221 return (E)_elements[i];
222 }
223
224 /* ------------------------------------------------------------ */
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 // 0 _elements.length
238 // _nextE........._nextSlot
239 System.arraycopy(_elements,i+1,_elements,i,_nextSlot-i);
240 _nextSlot--;
241 _size--;
242 }
243 else
244 {
245 // 0 _elements.length
246 // ......_nextSlot _nextE..........
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 public E set(int index, E element)
266 {
267 synchronized(_lock)
268 {
269 if (index<0 || index>=_size)
270 throw new IndexOutOfBoundsException("!("+0+"<"+index+"<="+_size+")");
271
272 int i = _nextE+index;
273 if (i>=_elements.length)
274 i-=_elements.length;
275 E old=(E)_elements[i];
276 _elements[i]=element;
277 return old;
278 }
279 }
280
281 /* ------------------------------------------------------------ */
282 public void add(int index, E element)
283 {
284 synchronized(_lock)
285 {
286 if (index<0 || index>_size)
287 throw new IndexOutOfBoundsException("!("+0+"<"+index+"<="+_size+")");
288
289 if (_size==_elements.length && !grow())
290 throw new IllegalStateException("Full");
291
292 if (index==_size)
293 {
294 add(element);
295 }
296 else
297 {
298 int i = _nextE+index;
299 if (i>=_elements.length)
300 i-=_elements.length;
301
302 _size++;
303 _nextSlot++;
304 if (_nextSlot==_elements.length)
305 _nextSlot=0;
306
307 if (i<_nextSlot)
308 {
309 // 0 _elements.length
310 // _nextE.....i..._nextSlot
311 // 0 _elements.length
312 // ..i..._nextSlot _nextE..........
313 System.arraycopy(_elements,i,_elements,i+1,_nextSlot-i);
314 _elements[i]=element;
315 }
316 else
317 {
318 // 0 _elements.length
319 // ......_nextSlot _nextE.....i....
320 if (_nextSlot>0)
321 {
322 System.arraycopy(_elements,0,_elements,1,_nextSlot);
323 _elements[0]=_elements[_elements.length-1];
324 }
325
326 System.arraycopy(_elements,i,_elements,i+1,_elements.length-i-1);
327 _elements[i]=element;
328 }
329 }
330 }
331 }
332
333 protected boolean grow()
334 {
335 if (_growCapacity<=0)
336 return false;
337
338 Object[] elements=new Object[_elements.length+_growCapacity];
339
340 int split=_elements.length-_nextE;
341 if (split>0)
342 System.arraycopy(_elements,_nextE,elements,0,split);
343 if (_nextE!=0)
344 System.arraycopy(_elements,0,elements,split,_nextSlot);
345
346 _elements=elements;
347 _nextE=0;
348 _nextSlot=_size;
349 return true;
350 }
351
352 }