View Javadoc
1   /*
2    *  Licensed to the Apache Software Foundation (ASF) under one
3    *  or more contributor license agreements.  See the NOTICE file
4    *  distributed with this work for additional information
5    *  regarding copyright ownership.  The ASF licenses this file
6    *  to you under the Apache License, Version 2.0 (the
7    *  "License"); you may not use this file except in compliance
8    *  with the License.  You may obtain a copy of the License at
9    *  
10   *    http://www.apache.org/licenses/LICENSE-2.0
11   *  
12   *  Unless required by applicable law or agreed to in writing,
13   *  software distributed under the License is distributed on an
14   *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *  KIND, either express or implied.  See the License for the
16   *  specific language governing permissions and limitations
17   *  under the License. 
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   * A unbounded circular queue based on array.
30   * 
31   * @author <a href="http://mina.apache.org">Apache MINA Project</a>
32   */
33  public class CircularQueue<E> extends AbstractList<E> implements Queue<E>, Serializable {
34      /** The serialVersionUID : mandatory for serializable classes */
35      private static final long serialVersionUID = 3993421269224511264L;
36  
37      /** Minimal size of the underlying array */
38      private static final int DEFAULT_CAPACITY = 4;
39  
40      /** The initial capacity of the list */
41      private final int initialCapacity;
42  
43      // XXX: This volatile keyword here is a workaround for SUN Java Compiler bug,
44      //      which produces buggy byte code.  I don't event know why adding a volatile
45      //      fixes the problem.  Eclipse Java Compiler seems to produce correct byte code.
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       * Construct a new, empty queue.
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       * The capacity must be a power of 2.
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       * Returns the capacity of this queue.
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             // expand queue
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             // shrink queue
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             // Copy only when there's something to copy.
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         // Make a room for a new element.
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         // Remove a room for the removed element.
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 }