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