001/* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, 013 * software distributed under the License is distributed on an 014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 015 * KIND, either express or implied. See the License for the 016 * specific language governing permissions and limitations 017 * under the License. 018 * 019 */ 020package org.apache.mina.util; 021 022import java.io.Serializable; 023import java.util.AbstractList; 024import java.util.Arrays; 025import java.util.NoSuchElementException; 026import java.util.Queue; 027 028/** 029 * A unbounded circular queue based on array. 030 * 031 * @author <a href="http://mina.apache.org">Apache MINA Project</a> 032 */ 033public class CircularQueue<E> extends AbstractList<E> implements Queue<E>, Serializable { 034 /** The serialVersionUID : mandatory for serializable classes */ 035 private static final long serialVersionUID = 3993421269224511264L; 036 037 /** Minimal size of the underlying array */ 038 private static final int DEFAULT_CAPACITY = 4; 039 040 /** The initial capacity of the list */ 041 private final int initialCapacity; 042 043 // XXX: This volatile keyword here is a workaround for SUN Java Compiler bug, 044 // which produces buggy byte code. I don't event know why adding a volatile 045 // fixes the problem. Eclipse Java Compiler seems to produce correct byte code. 046 private volatile Object[] items; 047 048 private int mask; 049 050 private int first = 0; 051 052 private int last = 0; 053 054 private boolean full; 055 056 private int shrinkThreshold; 057 058 /** 059 * Construct a new, empty queue. 060 */ 061 public CircularQueue() { 062 this(DEFAULT_CAPACITY); 063 } 064 065 public CircularQueue(int initialCapacity) { 066 int actualCapacity = normalizeCapacity(initialCapacity); 067 items = new Object[actualCapacity]; 068 mask = actualCapacity - 1; 069 this.initialCapacity = actualCapacity; 070 this.shrinkThreshold = 0; 071 } 072 073 /** 074 * The capacity must be a power of 2. 075 */ 076 private static int normalizeCapacity(int initialCapacity) { 077 int actualCapacity = 1; 078 079 while (actualCapacity < initialCapacity) { 080 actualCapacity <<= 1; 081 if (actualCapacity < 0) { 082 actualCapacity = 1 << 30; 083 break; 084 } 085 } 086 return actualCapacity; 087 } 088 089 /** 090 * @return the capacity of this queue. 091 */ 092 public int capacity() { 093 return items.length; 094 } 095 096 @Override 097 public void clear() { 098 if (!isEmpty()) { 099 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}