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.List;
26  import java.util.NoSuchElementException;
27  
28  import org.apache.mina.common.ByteBuffer;
29  import org.apache.mina.common.IoFilter.WriteRequest;
30  
31  /**
32   * A unbounded circular queue.
33   * 
34   * @author The Apache Directory Project (mina-dev@directory.apache.org)
35   * @version $Rev: 561242 $, $Date: 2007-07-31 15:43:29 +0900 (화, 31  7월 2007) $
36   */
37  public class Queue extends AbstractList implements List, Serializable {
38      private static final long serialVersionUID = 3835151744526464313L;
39  
40      private static final int DEFAULT_CAPACITY = 4;
41  
42      private static final int DEFAULT_MASK = DEFAULT_CAPACITY - 1;
43  
44      private Object[] items;
45  
46      private int mask;
47  
48      private int first = 0;
49  
50      private int last = 0;
51  
52      private int size = 0;
53  
54      /**
55       * Construct a new, empty queue.
56       */
57      public Queue() {
58          items = new Object[DEFAULT_CAPACITY];
59          mask = DEFAULT_MASK;
60      }
61  
62      /**
63       * Returns the capacity of this queue.
64       */
65      public int capacity() {
66          return items.length;
67      }
68  
69      /**
70       * Clears this queue.
71       */
72      public void clear() {
73          Arrays.fill(items, null);
74          first = 0;
75          last = 0;
76          size = 0;
77      }
78  
79      /**
80       * Dequeues from this queue.
81       * 
82       * @return <code>null</code>, if this queue is empty or the element is
83       *         really <code>null</code>.
84       */
85      public Object pop() {
86          if (size == 0) {
87              return null;
88          }
89  
90          Object ret = items[first];
91          items[first] = null;
92          decreaseSize();
93  
94          return ret;
95      }
96  
97      /**
98       * Enqueue into this queue.
99       */
100     public void push(Object item) {
101         if (item == null) {
102             throw new NullPointerException("item");
103         }
104         ensureCapacity();
105         items[last] = item;
106         increaseSize();
107     }
108 
109     /**
110      * Returns the first element of the queue.
111      * 
112      * @return <code>null</code>, if the queue is empty, or the element is
113      *         really <code>null</code>.
114      */
115     public Object first() {
116         if (size == 0) {
117             return null;
118         }
119 
120         return items[first];
121     }
122 
123     /**
124      * Returns the last element of the queue.
125      * 
126      * @return <code>null</code>, if the queue is empty, or the element is
127      *         really <code>null</code>.
128      */
129     public Object last() {
130         if (size == 0) {
131             return null;
132         }
133 
134         return items[(last + items.length - 1) & mask];
135     }
136 
137     public Object get(int idx) {
138         checkIndex(idx);
139         return items[getRealIndex(idx)];
140     }
141 
142     /**
143      * Returns <code>true</code> if the queue is empty.
144      */
145     public boolean isEmpty() {
146         return (size == 0);
147     }
148 
149     /**
150      * Returns the number of elements in the queue.
151      */
152     public int size() {
153         return size;
154     }
155     
156     /**
157      * Returns the sum of the '<tt>remaining</tt>' of all {@link ByteBuffer}s
158      * in this queue.
159      */
160     public int byteSize() {
161         if (isEmpty()) {
162             return 0;
163         }
164 
165         int byteSize = 0;
166 
167         if (first < last) {
168             for (int i = first; i < last; i++) {
169                 if (items[i] instanceof ByteBuffer) {
170                     byteSize += ((ByteBuffer) items[i]).remaining();
171                 } else if (items[i] instanceof WriteRequest) {
172                     Object message = ((WriteRequest) items[i]).getMessage();
173                     if (message instanceof ByteBuffer) {
174                         byteSize += ((ByteBuffer) message).remaining();
175                     }
176                 }
177             }
178         } else {
179             for (int i = first; i < items.length; i++) {
180                 if (items[i] instanceof ByteBuffer) {
181                     byteSize += ((ByteBuffer) items[i]).remaining();
182                 } else if (items[i] instanceof WriteRequest) {
183                     Object message = ((WriteRequest) items[i]).getMessage();
184                     if (message instanceof ByteBuffer) {
185                         byteSize += ((ByteBuffer) message).remaining();
186                     }
187                 }
188             }
189             for (int i = last - 1; i >= 0; i--) {
190                 if (items[i] instanceof ByteBuffer) {
191                     byteSize += ((ByteBuffer) items[i]).remaining();
192                 } else if (items[i] instanceof WriteRequest) {
193                     Object message = ((WriteRequest) items[i]).getMessage();
194                     if (message instanceof ByteBuffer) {
195                         byteSize += ((ByteBuffer) message).remaining();
196                     }
197                 }
198             }
199         }
200 
201         return byteSize;
202     }
203     
204     public int messageSize() {
205         if (isEmpty()) {
206             return 0;
207         }
208 
209         int messageSize = 0;
210 
211         if (first < last) {
212             for (int i = first; i < last; i++) {
213                 if (items[i] instanceof WriteRequest) {
214                     Object message = ((WriteRequest) items[i]).getMessage();
215                     if (message instanceof ByteBuffer) {
216                         if (((ByteBuffer) message).hasRemaining()) {
217                             messageSize ++;
218                         }
219                     } else {
220                         messageSize ++;
221                     }
222                 } else if (items[i] instanceof ByteBuffer) {
223                     if (((ByteBuffer) items[i]).hasRemaining()) {
224                         messageSize ++;
225                     }
226                 }
227             }
228         } else {
229             for (int i = first; i < items.length; i++) {
230                 if (items[i] instanceof WriteRequest) {
231                     Object message = ((WriteRequest) items[i]).getMessage();
232                     if (message instanceof ByteBuffer) {
233                         if (((ByteBuffer) message).hasRemaining()) {
234                             messageSize ++;
235                         }
236                     } else {
237                         messageSize ++;
238                     }
239                 } else if (items[i] instanceof ByteBuffer) {
240                     if (((ByteBuffer) items[i]).hasRemaining()) {
241                         messageSize ++;
242                     }
243                 }
244             }
245             for (int i = last - 1; i >= 0; i--) {
246                 if (items[i] instanceof WriteRequest) {
247                     Object message = ((WriteRequest) items[i]).getMessage();
248                     if (message instanceof ByteBuffer) {
249                         if (((ByteBuffer) message).hasRemaining()) {
250                             messageSize ++;
251                         }
252                     } else {
253                         messageSize ++;
254                     }
255                 } else if (items[i] instanceof ByteBuffer) {
256                     if (((ByteBuffer) items[i]).hasRemaining()) {
257                         messageSize ++;
258                     }
259                 }
260             }
261         }
262 
263         return messageSize;
264     }
265 
266     public String toString() {
267         return "first=" + first + ", last=" + last + ", size=" + size
268                 + ", mask = " + mask;
269     }
270 
271     private void checkIndex(int idx) {
272         if (idx < 0 || idx >= size) {
273             throw new IndexOutOfBoundsException(String.valueOf(idx));
274         }
275     }
276 
277     private int getRealIndex(int idx) {
278         return (first + idx) & mask;
279     }
280 
281     private void increaseSize() {
282         last = (last + 1) & mask;
283         size++;
284     }
285 
286     private void decreaseSize() {
287         first = (first + 1) & mask;
288         size--;
289     }
290 
291     private void ensureCapacity() {
292         if (size < items.length) {
293             return;
294         }
295 
296         // expand queue
297         final int oldLen = items.length;
298         Object[] tmp = new Object[oldLen * 2];
299 
300         if (first < last) {
301             System.arraycopy(items, first, tmp, 0, last - first);
302         } else {
303             System.arraycopy(items, first, tmp, 0, oldLen - first);
304             System.arraycopy(items, 0, tmp, oldLen - first, last);
305         }
306 
307         first = 0;
308         last = oldLen;
309         items = tmp;
310         mask = tmp.length - 1;
311     }
312 
313     //////////////////////////////////////////
314     // java.util.List compatibility methods //
315     //////////////////////////////////////////
316 
317     public boolean add(Object o) {
318         push(o);
319         return true;
320     }
321 
322     public Object set(int idx, Object o) {
323         checkIndex(idx);
324 
325         int realIdx = getRealIndex(idx);
326         Object old = items[realIdx];
327         items[realIdx] = o;
328         return old;
329     }
330 
331     public void add(int idx, Object o) {
332         if (idx == size) {
333             push(o);
334             return;
335         }
336 
337         checkIndex(idx);
338         ensureCapacity();
339 
340         int realIdx = getRealIndex(idx);
341 
342         // Make a room for a new element.
343         if (first < last) {
344             System
345                     .arraycopy(items, realIdx, items, realIdx + 1, last
346                             - realIdx);
347         } else {
348             if (realIdx >= first) {
349                 System.arraycopy(items, 0, items, 1, last);
350                 items[0] = items[items.length - 1];
351                 System.arraycopy(items, realIdx, items, realIdx + 1,
352                         items.length - realIdx - 1);
353             } else {
354                 System.arraycopy(items, realIdx, items, realIdx + 1, last
355                         - realIdx);
356             }
357         }
358 
359         items[realIdx] = o;
360         increaseSize();
361     }
362 
363     public Object remove(int idx) {
364         if (idx == 0) {
365             return pop();
366         }
367 
368         checkIndex(idx);
369 
370         int realIdx = getRealIndex(idx);
371         Object removed = items[realIdx];
372 
373         // Remove a room for the removed element.
374         if (first < last) {
375             System.arraycopy(items, first, items, first + 1, realIdx - first);
376         } else {
377             if (realIdx >= first) {
378                 System.arraycopy(items, first, items, first + 1, realIdx
379                         - first);
380             } else {
381                 System.arraycopy(items, 0, items, 1, realIdx);
382                 items[0] = items[items.length - 1];
383                 System.arraycopy(items, first, items, first + 1, items.length
384                         - first - 1);
385             }
386         }
387 
388         items[first] = null;
389         decreaseSize();
390 
391         return removed;
392     }
393 
394     ///////////////////////////////////////////
395     // java.util.Queue compatibility methods //
396     ///////////////////////////////////////////
397 
398     public boolean offer(Object o) {
399         push(o);
400         return true;
401     }
402 
403     public Object poll() {
404         return pop();
405     }
406 
407     public Object remove() {
408         if (size == 0) {
409             throw new NoSuchElementException();
410         }
411         return pop();
412     }
413 
414     public Object peek() {
415         return first();
416     }
417 
418     public Object element() {
419         if (size == 0) {
420             throw new NoSuchElementException();
421         }
422         return first();
423     }
424 }