Mercurial Hosting > luan

comparison src/org/eclipse/jetty/util/ArrayQueue.java @ 802:3428c60d7cfc

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
replace jetty jars with source
author Franklin Schmidt <fschmidt@gmail.com>
date Wed, 07 Sep 2016 21:15:48 -0600
parents
children
comparison
equal deleted inserted replaced
801:6a21393191c1 802:3428c60d7cfc
1 //
2 // ========================================================================
3 // Copyright (c) 1995-2014 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 int getCapacity()
74 {
75 synchronized (_lock)
76 {
77 return _elements.length;
78 }
79 }
80
81 /* ------------------------------------------------------------ */
82 @Override
83 public boolean add(E e)
84 {
85 if (!offer(e))
86 throw new IllegalStateException("Full");
87 return true;
88 }
89
90 /* ------------------------------------------------------------ */
91 public boolean offer(E e)
92 {
93 synchronized (_lock)
94 {
95 return enqueue(e);
96 }
97 }
98
99 /* ------------------------------------------------------------ */
100 private boolean enqueue(E e)
101 {
102 if (_size == _elements.length && !grow())
103 return false;
104
105 _size++;
106 _elements[_nextSlot++] = e;
107 if (_nextSlot == _elements.length)
108 _nextSlot = 0;
109
110 return true;
111 }
112
113 /* ------------------------------------------------------------ */
114 /**
115 * Add without synchronization or bounds checking
116 *
117 * @param e the element to add
118 * @see #add(Object)
119 */
120 public void addUnsafe(E e)
121 {
122 if (!enqueue(e))
123 throw new IllegalStateException("Full");
124 }
125
126 /* ------------------------------------------------------------ */
127 public E element()
128 {
129 synchronized (_lock)
130 {
131 if (isEmpty())
132 throw new NoSuchElementException();
133 return at(_nextE);
134 }
135 }
136
137 @SuppressWarnings("unchecked")
138 private E at(int index)
139 {
140 return (E)_elements[index];
141 }
142
143 /* ------------------------------------------------------------ */
144 public E peek()
145 {
146 synchronized (_lock)
147 {
148 if (isEmpty())
149 return null;
150 return at(_nextE);
151 }
152 }
153
154 /* ------------------------------------------------------------ */
155 public E poll()
156 {
157 synchronized (_lock)
158 {
159 if (_size == 0)
160 return null;
161 return dequeue();
162 }
163 }
164
165 /* ------------------------------------------------------------ */
166 private E dequeue()
167 {
168 E e = at(_nextE);
169 _elements[_nextE] = null;
170 _size--;
171 if (++_nextE == _elements.length)
172 _nextE = 0;
173 return e;
174 }
175
176 /* ------------------------------------------------------------ */
177 public E remove()
178 {
179 synchronized (_lock)
180 {
181 if (_size == 0)
182 throw new NoSuchElementException();
183 return dequeue();
184 }
185 }
186
187 /* ------------------------------------------------------------ */
188 @Override
189 public void clear()
190 {
191 synchronized (_lock)
192 {
193 _size = 0;
194 _nextE = 0;
195 _nextSlot = 0;
196 }
197 }
198
199 /* ------------------------------------------------------------ */
200 @Override
201 public boolean isEmpty()
202 {
203 synchronized (_lock)
204 {
205 return _size == 0;
206 }
207 }
208
209 /* ------------------------------------------------------------ */
210 @Override
211 public int size()
212 {
213 synchronized (_lock)
214 {
215 return _size;
216 }
217 }
218
219 /* ------------------------------------------------------------ */
220 @Override
221 public E get(int index)
222 {
223 synchronized (_lock)
224 {
225 if (index < 0 || index >= _size)
226 throw new IndexOutOfBoundsException("!(" + 0 + "<" + index + "<=" + _size + ")");
227 return getUnsafe(index);
228 }
229 }
230
231 /* ------------------------------------------------------------ */
232 /**
233 * Get without synchronization or bounds checking.
234 *
235 * @param index index of the element to return
236 * @return the element at the specified index
237 * @see #get(int)
238 */
239 public E getUnsafe(int index)
240 {
241 int i = (_nextE + index) % _elements.length;
242 return at(i);
243 }
244
245 /* ------------------------------------------------------------ */
246 @Override
247 public E remove(int index)
248 {
249 synchronized (_lock)
250 {
251 if (index < 0 || index >= _size)
252 throw new IndexOutOfBoundsException("!(" + 0 + "<" + index + "<=" + _size + ")");
253
254 int i = (_nextE + index) % _elements.length;
255 E old = at(i);
256
257 if (i < _nextSlot)
258 {
259 // 0 _elements.length
260 // _nextE........._nextSlot
261 System.arraycopy(_elements, i + 1, _elements, i, _nextSlot - i);
262 _nextSlot--;
263 _size--;
264 }
265 else
266 {
267 // 0 _elements.length
268 // ......_nextSlot _nextE..........
269 System.arraycopy(_elements, i + 1, _elements, i, _elements.length - i - 1);
270 if (_nextSlot > 0)
271 {
272 _elements[_elements.length - 1] = _elements[0];
273 System.arraycopy(_elements, 1, _elements, 0, _nextSlot - 1);
274 _nextSlot--;
275 }
276 else
277 _nextSlot = _elements.length - 1;
278
279 _size--;
280 }
281
282 return old;
283 }
284 }
285
286 /* ------------------------------------------------------------ */
287 @Override
288 public E set(int index, E element)
289 {
290 synchronized (_lock)
291 {
292 if (index < 0 || index >= _size)
293 throw new IndexOutOfBoundsException("!(" + 0 + "<" + index + "<=" + _size + ")");
294
295 int i = _nextE + index;
296 if (i >= _elements.length)
297 i -= _elements.length;
298 E old = at(i);
299 _elements[i] = element;
300 return old;
301 }
302 }
303
304 /* ------------------------------------------------------------ */
305 @Override
306 public void add(int index, E element)
307 {
308 synchronized (_lock)
309 {
310 if (index < 0 || index > _size)
311 throw new IndexOutOfBoundsException("!(" + 0 + "<" + index + "<=" + _size + ")");
312
313 if (_size == _elements.length && !grow())
314 throw new IllegalStateException("Full");
315
316 if (index == _size)
317 {
318 add(element);
319 }
320 else
321 {
322 int i = _nextE + index;
323 if (i >= _elements.length)
324 i -= _elements.length;
325
326 _size++;
327 _nextSlot++;
328 if (_nextSlot == _elements.length)
329 _nextSlot = 0;
330
331 if (i < _nextSlot)
332 {
333 // 0 _elements.length
334 // _nextE.....i..._nextSlot
335 // 0 _elements.length
336 // ..i..._nextSlot _nextE..........
337 System.arraycopy(_elements, i, _elements, i + 1, _nextSlot - i);
338 _elements[i] = element;
339 }
340 else
341 {
342 // 0 _elements.length
343 // ......_nextSlot _nextE.....i....
344 if (_nextSlot > 0)
345 {
346 System.arraycopy(_elements, 0, _elements, 1, _nextSlot);
347 _elements[0] = _elements[_elements.length - 1];
348 }
349
350 System.arraycopy(_elements, i, _elements, i + 1, _elements.length - i - 1);
351 _elements[i] = element;
352 }
353 }
354 }
355 }
356
357 /* ------------------------------------------------------------ */
358 protected boolean grow()
359 {
360 synchronized (_lock)
361 {
362 if (_growCapacity <= 0)
363 return false;
364
365 Object[] elements = new Object[_elements.length + _growCapacity];
366
367 int split = _elements.length - _nextE;
368 if (split > 0)
369 System.arraycopy(_elements, _nextE, elements, 0, split);
370 if (_nextE != 0)
371 System.arraycopy(_elements, 0, elements, split, _nextSlot);
372
373 _elements = elements;
374 _nextE = 0;
375 _nextSlot = _size;
376 return true;
377 }
378 }
379 }