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