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      private int mask;
48      private int first = 0;
49      private int last = 0;
50      private boolean full;
51      private int shrinkThreshold;
52  
53      /**
54       * Construct a new, empty queue.
55       */
56      public CircularQueue() {
57          this(DEFAULT_CAPACITY);
58      }
59      
60      public CircularQueue(int initialCapacity) {
61          int actualCapacity = normalizeCapacity(initialCapacity);
62          items = new Object[actualCapacity];
63          mask = actualCapacity - 1;
64          this.initialCapacity = actualCapacity;
65          this.shrinkThreshold = 0;
66      }
67  
68      /**
69       * The capacity must be a power of 2.
70       */
71      private static int normalizeCapacity(int initialCapacity) {
72          int actualCapacity = 1;
73          
74          while (actualCapacity < initialCapacity) {
75              actualCapacity <<= 1;
76              if (actualCapacity < 0) {
77                  actualCapacity = 1 << 30;
78                  break;
79              }
80          }
81          return actualCapacity;
82      }
83  
84      /**
85       * Returns the capacity of this queue.
86       */
87      public int capacity() {
88          return items.length;
89      }
90  
91      @Override
92      public void clear() {
93          if (!isEmpty()) {
94              Arrays.fill(items, null);
95              first = 0;
96              last = 0;
97              full = false;
98              shrinkIfNeeded();
99          }
100     }
101 
102     @SuppressWarnings("unchecked")
103     public E poll() {
104         if (isEmpty()) {
105             return null;
106         }
107 
108         Object ret = items[first];
109         items[first] = null;
110         decreaseSize();
111         
112         if (first == last) {
113             first = last = 0;
114         }
115 
116         shrinkIfNeeded();
117         return (E) ret;
118     }
119 
120     public boolean offer(E item) {
121         if (item == null) {
122             throw new NullPointerException("item");
123         }
124         
125         expandIfNeeded();
126         items[last] = item;
127         increaseSize();
128         return true;
129     }
130 
131     @SuppressWarnings("unchecked")
132     public E peek() {
133         if (isEmpty()) {
134             return null;
135         }
136 
137         return (E) items[first];
138     }
139 
140     @SuppressWarnings("unchecked")
141     @Override
142     public E get(int idx) {
143         checkIndex(idx);
144         return (E) items[getRealIndex(idx)];
145     }
146 
147     @Override
148     public boolean isEmpty() {
149         return (first == last) && !full;
150     }
151 
152     @Override
153     public int size() {
154         if (full) {
155             return capacity();
156         }
157         
158         if (last >= first) {
159             return last - first;
160         }
161 
162         return last - first + capacity();
163     }
164     
165     @Override
166     public String toString() {
167         return "first=" + first + ", last=" + last + ", size=" + size()
168                 + ", mask = " + mask;
169     }
170 
171     private void checkIndex(int idx) {
172         if (idx < 0 || idx >= size()) {
173             throw new IndexOutOfBoundsException(String.valueOf(idx));
174         }
175     }
176 
177     private int getRealIndex(int idx) {
178         return (first + idx) & mask;
179     }
180 
181     private void increaseSize() {
182         last = (last + 1) & mask;
183         full = first == last;
184     }
185 
186     private void decreaseSize() {
187         first = (first + 1) & mask;
188         full = false;
189     }
190 
191     private void expandIfNeeded() {
192         if (full) {
193             // expand queue
194             final int oldLen = items.length;
195             final int newLen = oldLen << 1;
196             Object[] tmp = new Object[newLen];
197     
198             if (first < last) {
199                 System.arraycopy(items, first, tmp, 0, last - first);
200             } else {
201                 System.arraycopy(items, first, tmp, 0, oldLen - first);
202                 System.arraycopy(items, 0, tmp, oldLen - first, last);
203             }
204     
205             first = 0;
206             last = oldLen;
207             items = tmp;
208             mask = tmp.length - 1;
209             if (newLen >>> 3 > initialCapacity) {
210                 shrinkThreshold = newLen >>> 3;
211             }
212         }
213     }
214     
215     private void shrinkIfNeeded() {
216         int size = size();
217         if (size <= shrinkThreshold) {
218             // shrink queue
219             final int oldLen = items.length;
220             int newLen = normalizeCapacity(size);
221             if (size == newLen) {
222                 newLen <<= 1;
223             }
224             
225             if (newLen >= oldLen) {
226                 return;
227             }
228             
229             if (newLen < initialCapacity) {
230                 if (oldLen == initialCapacity) {
231                     return;
232                 }
233 
234                 newLen = initialCapacity;
235             }
236             
237             Object[] tmp = new Object[newLen];
238     
239             // Copy only when there's something to copy.
240             if (size > 0) {
241                 if (first < last) {
242                     System.arraycopy(items, first, tmp, 0, last - first);
243                 } else {
244                     System.arraycopy(items, first, tmp, 0, oldLen - first);
245                     System.arraycopy(items, 0, tmp, oldLen - first, last);
246                 }
247             }
248     
249             first = 0;
250             last = size;
251             items = tmp;
252             mask = tmp.length - 1;
253             shrinkThreshold = 0;
254         }
255     }
256 
257     @Override
258     public boolean add(E o) {
259         return offer(o);
260     }
261 
262     @SuppressWarnings("unchecked")
263     @Override
264     public E set(int idx, E o) {
265         checkIndex(idx);
266 
267         int realIdx = getRealIndex(idx);
268         Object old = items[realIdx];
269         items[realIdx] = o;
270         return (E) old;
271     }
272 
273     @Override
274     public void add(int idx, E o) {
275         if (idx == size()) {
276             offer(o);
277             return;
278         }
279 
280         checkIndex(idx);
281         expandIfNeeded();
282 
283         int realIdx = getRealIndex(idx);
284 
285         // Make a room for a new element.
286         if (first < last) {
287             System
288                     .arraycopy(items, realIdx, items, realIdx + 1, last
289                             - realIdx);
290         } else {
291             if (realIdx >= first) {
292                 System.arraycopy(items, 0, items, 1, last);
293                 items[0] = items[items.length - 1];
294                 System.arraycopy(items, realIdx, items, realIdx + 1,
295                         items.length - realIdx - 1);
296             } else {
297                 System.arraycopy(items, realIdx, items, realIdx + 1, last
298                         - 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
324                         - first);
325             } else {
326                 System.arraycopy(items, 0, items, 1, realIdx);
327                 items[0] = items[items.length - 1];
328                 System.arraycopy(items, first, items, first + 1, items.length
329                         - first - 1);
330             }
331         }
332 
333         items[first] = null;
334         decreaseSize();
335 
336         shrinkIfNeeded();
337         return (E) removed;
338     }
339 
340     public E remove() {
341         if (isEmpty()) {
342             throw new NoSuchElementException();
343         }
344         return poll();
345     }
346 
347     public E element() {
348         if (isEmpty()) {
349             throw new NoSuchElementException();
350         }
351         return peek();
352     }
353 }