lib/jetty/org/eclipse/jetty/util/ArrayQueue.java

   1 //
   2 //  ========================================================================
   3 //  Copyright (c) 1995-2016 Mort Bay Consulting Pty. Ltd.
   4 //  ------------------------------------------------------------------------
   5 //  All rights reserved. This program and the accompanying materials
   6 //  are made available under the terms of the Eclipse Public License v1.0
   7 //  and Apache License v2.0 which accompanies this distribution.
   8 //
   9 //      The Eclipse Public License is available at
  10 //      http://www.eclipse.org/legal/epl-v10.html
  11 //
  12 //      The Apache License v2.0 is available at
  13 //      http://www.opensource.org/licenses/apache2.0.php
  14 //
  15 //  You may elect to redistribute this code under either of these licenses.
  16 //  ========================================================================
  17 //
  18
  19 package org.eclipse.jetty.util;
  20
  21 import java.util.AbstractList;
  22 import java.util.NoSuchElementException;
  23 import java.util.Queue;
  24
  25 /* ------------------------------------------------------------ */
  26 /**
  27  * Queue backed by circular array.
  28  * <p/>
  29  * This partial Queue implementation (also with {@link #remove()} for stack operation)
  30  * is backed by a growable circular array.
  31  *
  32  * @param <E>
  33  */
  34 public class ArrayQueue<E> extends AbstractList<E> implements Queue<E>
  35 {
  36     public static final int DEFAULT_CAPACITY = 64;
  37     public static final int DEFAULT_GROWTH = 32;
  38
  39     protected final Object _lock;
  40     protected final int _growCapacity;
  41     protected Object[] _elements;
  42     protected int _nextE;
  43     protected int _nextSlot;
  44     protected int _size;
  45
  46     /* ------------------------------------------------------------ */
  47     public ArrayQueue()
  48     {
  49         this(DEFAULT_CAPACITY, -1);
  50     }
  51
  52     /* ------------------------------------------------------------ */
  53     public ArrayQueue(Object lock)
  54     {
  55         this(DEFAULT_CAPACITY, -1,lock);
  56     }
  57
  58     /* ------------------------------------------------------------ */
  59     public ArrayQueue(int capacity)
  60     {
  61         this(capacity, -1);
  62     }
  63
  64     /* ------------------------------------------------------------ */
  65     public ArrayQueue(int initCapacity, int growBy)
  66     {
  67         this(initCapacity, growBy, null);
  68     }
  69
  70     /* ------------------------------------------------------------ */
  71     public ArrayQueue(int initCapacity, int growBy, Object lock)
  72     {
  73         _lock = lock == null ? this : lock;
  74         _growCapacity = growBy;
  75         _elements = new Object[initCapacity];
  76     }
  77
  78     /* ------------------------------------------------------------ */
  79     public Object lock()
  80     {
  81         return _lock;
  82     }
  83
  84     /* ------------------------------------------------------------ */
  85     public int getCapacity()
  86     {
  87         synchronized (_lock)
  88         {
  89             return _elements.length;
  90         }
  91     }
  92
  93     /* ------------------------------------------------------------ */
  94     @Override
  95     public boolean add(E e)
  96     {
  97         if (!offer(e))
  98             throw new IllegalStateException("Full");
  99         return true;
 100     }
 101
 102     /* ------------------------------------------------------------ */
 103     public boolean offer(E e)
 104     {
 105         synchronized (_lock)
 106         {
 107             return enqueue(e);
 108         }
 109     }
 110
 111     /* ------------------------------------------------------------ */
 112     private boolean enqueue(E e)
 113     {
 114         if (_size == _elements.length && !grow())
 115             return false;
 116
 117         _size++;
 118         _elements[_nextSlot++] = e;
 119         if (_nextSlot == _elements.length)
 120             _nextSlot = 0;
 121
 122         return true;
 123     }
 124
 125     /* ------------------------------------------------------------ */
 126     /**
 127      * Add without synchronization or bounds checking
 128      *
 129      * @param e the element to add
 130      * @see #add(Object)
 131      */
 132     public void addUnsafe(E e)
 133     {
 134         if (!enqueue(e))
 135             throw new IllegalStateException("Full");
 136     }
 137
 138     /* ------------------------------------------------------------ */
 139     public E element()
 140     {
 141         synchronized (_lock)
 142         {
 143             if (isEmpty())
 144                 throw new NoSuchElementException();
 145             return at(_nextE);
 146         }
 147     }
 148
 149     /* ------------------------------------------------------------ */
 150     @SuppressWarnings("unchecked")
 151     private E at(int index)
 152     {
 153         return (E)_elements[index];
 154     }
 155
 156     /* ------------------------------------------------------------ */
 157     public E peek()
 158     {
 159         synchronized (_lock)
 160         {
 161             if (_size == 0)
 162                 return null;
 163             return at(_nextE);
 164         }
 165     }
 166
 167     /* ------------------------------------------------------------ */
 168     public E peekUnsafe()
 169     {
 170         if (_size == 0)
 171             return null;
 172         return at(_nextE);
 173     }
 174
 175     /* ------------------------------------------------------------ */
 176     public E poll()
 177     {
 178         synchronized (_lock)
 179         {
 180             if (_size == 0)
 181                 return null;
 182             return dequeue();
 183         }
 184     }
 185
 186     /* ------------------------------------------------------------ */
 187     public E pollUnsafe()
 188     {
 189         if (_size == 0)
 190             return null;
 191         return dequeue();
 192     }
 193
 194     /* ------------------------------------------------------------ */
 195     private E dequeue()
 196     {
 197         E e = at(_nextE);
 198         _elements[_nextE] = null;
 199         _size--;
 200         if (++_nextE == _elements.length)
 201             _nextE = 0;
 202         return e;
 203     }
 204
 205     /* ------------------------------------------------------------ */
 206     public E remove()
 207     {
 208         synchronized (_lock)
 209         {
 210             if (_size == 0)
 211                 throw new NoSuchElementException();
 212             return dequeue();
 213         }
 214     }
 215
 216     /* ------------------------------------------------------------ */
 217     @Override
 218     public void clear()
 219     {
 220         synchronized (_lock)
 221         {
 222             _size = 0;
 223             _nextE = 0;
 224             _nextSlot = 0;
 225         }
 226     }
 227
 228     /* ------------------------------------------------------------ */
 229     @Override
 230     public boolean isEmpty()
 231     {
 232         synchronized (_lock)
 233         {
 234             return _size == 0;
 235         }
 236     }
 237
 238     /* ------------------------------------------------------------ */
 239     @Override
 240     public int size()
 241     {
 242         synchronized (_lock)
 243         {
 244             return _size;
 245         }
 246     }
 247
 248     /* ------------------------------------------------------------ */
 249     @Override
 250     public E get(int index)
 251     {
 252         synchronized (_lock)
 253         {
 254             if (index < 0 || index >= _size)
 255                 throw new IndexOutOfBoundsException("!(" + 0 + "<" + index + "<=" + _size + ")");
 256             return getUnsafe(index);
 257         }
 258     }
 259
 260     /* ------------------------------------------------------------ */
 261     /**
 262      * Get without synchronization or bounds checking.
 263      *
 264      * @param  index index of the element to return
 265      * @return the element at the specified index
 266      * @see #get(int)
 267      */
 268     public E getUnsafe(int index)
 269     {
 270         int i = (_nextE + index) % _elements.length;
 271         return at(i);
 272     }
 273
 274     /* ------------------------------------------------------------ */
 275     @Override
 276     public E remove(int index)
 277     {
 278         synchronized (_lock)
 279         {
 280             if (index < 0 || index >= _size)
 281                 throw new IndexOutOfBoundsException("!(" + 0 + "<" + index + "<=" + _size + ")");
 282
 283             int i = (_nextE + index) % _elements.length;
 284             E old = at(i);
 285
 286             if (i < _nextSlot)
 287             {
 288                 // 0                         _elements.length
 289                 //       _nextE........._nextSlot
 290                 System.arraycopy(_elements, i + 1, _elements, i, _nextSlot - i);
 291                 _nextSlot--;
 292                 _size--;
 293             }
 294             else
 295             {
 296                 // 0                         _elements.length
 297                 // ......_nextSlot   _nextE..........
 298                 System.arraycopy(_elements, i + 1, _elements, i, _elements.length - i - 1);
 299                 if (_nextSlot > 0)
 300                 {
 301                     _elements[_elements.length - 1] = _elements[0];
 302                     System.arraycopy(_elements, 1, _elements, 0, _nextSlot - 1);
 303                     _nextSlot--;
 304                 }
 305                 else
 306                     _nextSlot = _elements.length - 1;
 307
 308                 _size--;
 309             }
 310
 311             return old;
 312         }
 313     }
 314
 315     /* ------------------------------------------------------------ */
 316     @Override
 317     public E set(int index, E element)
 318     {
 319         synchronized (_lock)
 320         {
 321             if (index < 0 || index >= _size)
 322                 throw new IndexOutOfBoundsException("!(" + 0 + "<" + index + "<=" + _size + ")");
 323
 324             int i = _nextE + index;
 325             if (i >= _elements.length)
 326                 i -= _elements.length;
 327             E old = at(i);
 328             _elements[i] = element;
 329             return old;
 330         }
 331     }
 332
 333     /* ------------------------------------------------------------ */
 334     @Override
 335     public void add(int index, E element)
 336     {
 337         synchronized (_lock)
 338         {
 339             if (index < 0 || index > _size)
 340                 throw new IndexOutOfBoundsException("!(" + 0 + "<" + index + "<=" + _size + ")");
 341
 342             if (_size == _elements.length && !grow())
 343                 throw new IllegalStateException("Full");
 344
 345             if (index == _size)
 346             {
 347                 add(element);
 348             }
 349             else
 350             {
 351                 int i = _nextE + index;
 352                 if (i >= _elements.length)
 353                     i -= _elements.length;
 354
 355                 _size++;
 356                 _nextSlot++;
 357                 if (_nextSlot == _elements.length)
 358                     _nextSlot = 0;
 359
 360                 if (i < _nextSlot)
 361                 {
 362                     // 0                         _elements.length
 363                     //       _nextE.....i..._nextSlot
 364                     // 0                         _elements.length
 365                     // ..i..._nextSlot   _nextE..........
 366                     System.arraycopy(_elements, i, _elements, i + 1, _nextSlot - i);
 367                     _elements[i] = element;
 368                 }
 369                 else
 370                 {
 371                     // 0                         _elements.length
 372                     // ......_nextSlot   _nextE.....i....
 373                     if (_nextSlot > 0)
 374                     {
 375                         System.arraycopy(_elements, 0, _elements, 1, _nextSlot);
 376                         _elements[0] = _elements[_elements.length - 1];
 377                     }
 378
 379                     System.arraycopy(_elements, i, _elements, i + 1, _elements.length - i - 1);
 380                     _elements[i] = element;
 381                 }
 382             }
 383         }
 384     }
 385
 386     /* ------------------------------------------------------------ */
 387     protected boolean grow()
 388     {
 389         synchronized (_lock)
 390         {
 391             if (_growCapacity <= 0)
 392                 return false;
 393
 394             Object[] elements = new Object[_elements.length + _growCapacity];
 395
 396             int split = _elements.length - _nextE;
 397             if (split > 0)
 398                 System.arraycopy(_elements, _nextE, elements, 0, split);
 399             if (_nextE != 0)
 400                 System.arraycopy(_elements, 0, elements, split, _nextSlot);
 401
 402             _elements = elements;
 403             _nextE = 0;
 404             _nextSlot = _size;
 405             return true;
 406         }
 407     }
 408 }