Package org.eclipse.jetty.util

Class BlockingArrayQueue<E>

  • Type Parameters:
    E - The element type
    All Implemented Interfaces:
    java.lang.Iterable<E>, java.util.Collection<E>, java.util.concurrent.BlockingQueue<E>, java.util.List<E>, java.util.Queue<E>
    public class BlockingArrayQueue<E>
extends java.util.AbstractList<E>
implements java.util.concurrent.BlockingQueue<E>
    A BlockingQueue backed by a circular array capable or growing.

    This queue is uses a variant of the two lock queue algorithm to provide an efficient queue or list backed by a growable circular array.

    Unlike ArrayBlockingQueue, this class is able to grow and provides a blocking put call.

    The queue has both a capacity (the size of the array currently allocated) and a max capacity (the maximum size that may be allocated), which defaults to Integer.MAX_VALUE.

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      private class  BlockingArrayQueue.Itr  

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private java.lang.Object[] _elements  
      private int _growCapacity  
      private java.util.concurrent.locks.Lock _headLock  
      private int[] _indexes
      Array that holds the head and tail indexes, separated by a cache line to avoid false sharing
      private int _maxCapacity  
      private java.util.concurrent.locks.Condition _notEmpty  
      private java.util.concurrent.atomic.AtomicInteger _size  
      private java.util.concurrent.locks.Lock _tailLock  
      static int DEFAULT_CAPACITY
      Default initial capacity, 128.
      static int DEFAULT_GROWTH
      Default growth factor, 64.
      private static int HEAD_OFFSET
      The head offset in the _indexes array, displaced by 15 slots to avoid false sharing with the array length (stored before the first element of the array itself).
      private static int TAIL_OFFSET
      The tail offset in the _indexes array, displaced by 16 slots from the head to avoid false sharing with it.

      • Fields inherited from class java.util.AbstractList

        modCount

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void add​(int index, E e)  
      boolean add​(E e)  
      void clear()  
      int drainTo​(java.util.Collection<? super E> c)  
      int drainTo​(java.util.Collection<? super E> c, int maxElements)  
      E element()  
      E get​(int index)  
      int getCapacity()  
      int getMaxCapacity()  
      private boolean grow()  
      java.util.Iterator<E> iterator()  
      java.util.ListIterator<E> listIterator​(int index)  
      boolean offer​(E e)  
      boolean offer​(E o, long timeout, java.util.concurrent.TimeUnit unit)  
      E peek()  
      E poll()  
      E poll​(long time, java.util.concurrent.TimeUnit unit)  
      void put​(E o)  
      int remainingCapacity()  
      E remove()  
      E remove​(int index)  
      boolean remove​(java.lang.Object o)  
      E set​(int index, E e)  
      int size()  
      E take()  

      • Methods inherited from class java.util.AbstractList

        addAll, equals, hashCode, indexOf, lastIndexOf, listIterator, removeRange, subList

      • Methods inherited from class java.util.AbstractCollection

        addAll, contains, containsAll, isEmpty, removeAll, retainAll, toArray, toArray, toString

      • Methods inherited from class java.lang.Object

        clone, finalize, getClass, notify, notifyAll, wait, wait, wait

      • Methods inherited from interface java.util.concurrent.BlockingQueue

        contains

      • Methods inherited from interface java.util.Collection

        parallelStream, removeIf, stream

      • Methods inherited from interface java.lang.Iterable

        forEach

      • Methods inherited from interface java.util.List

        addAll, contains, containsAll, isEmpty, removeAll, replaceAll, retainAll, sort, spliterator, toArray, toArray

    • Field Detail

      • HEAD_OFFSET

        private static final int HEAD_OFFSET
        The head offset in the _indexes array, displaced by 15 slots to avoid false sharing with the array length (stored before the first element of the array itself).

      • TAIL_OFFSET

        private static final int TAIL_OFFSET
        The tail offset in the _indexes array, displaced by 16 slots from the head to avoid false sharing with it.

      • DEFAULT_CAPACITY

        public static final int DEFAULT_CAPACITY
        Default initial capacity, 128.
        See Also:
        Constant Field Values

      • DEFAULT_GROWTH

        public static final int DEFAULT_GROWTH
        Default growth factor, 64.
        See Also:
        Constant Field Values

      • _maxCapacity

        private final int _maxCapacity

      • _growCapacity

        private final int _growCapacity

      • _indexes

        private final int[] _indexes
        Array that holds the head and tail indexes, separated by a cache line to avoid false sharing

      • _tailLock

        private final java.util.concurrent.locks.Lock _tailLock

      • _size

        private final java.util.concurrent.atomic.AtomicInteger _size

      • _headLock

        private final java.util.concurrent.locks.Lock _headLock

      • _notEmpty

        private final java.util.concurrent.locks.Condition _notEmpty

      • _elements

        private java.lang.Object[] _elements

    • Constructor Detail

      • BlockingArrayQueue

        public BlockingArrayQueue​(int maxCapacity)
        Creates a bounded BlockingArrayQueue that does not grow. The capacity of the queue is fixed and equal to the given parameter.
        Parameters:
        maxCapacity - the maximum capacity

      • BlockingArrayQueue

        public BlockingArrayQueue​(int capacity,
                          int growBy)
        Creates an unbounded BlockingArrayQueue that grows by the given parameter.
        Parameters:
        capacity - the initial capacity
        growBy - the growth factor

      • BlockingArrayQueue

        public BlockingArrayQueue​(int capacity,
                          int growBy,
                          int maxCapacity)
        Create a bounded BlockingArrayQueue that grows by the given parameter.
        Parameters:
        capacity - the initial capacity
        growBy - the growth factor
        maxCapacity - the maximum capacity

    • Method Detail

      • clear

        public void clear()
        Specified by:
        clear in interface java.util.Collection<E>
        Specified by:
        clear in interface java.util.List<E>
        Overrides:
        clear in class java.util.AbstractList<E>

      • size

        public int size()
        Specified by:
        size in interface java.util.Collection<E>
        Specified by:
        size in interface java.util.List<E>
        Specified by:
        size in class java.util.AbstractCollection<E>

      • iterator

        public java.util.Iterator<E> iterator()
        Specified by:
        iterator in interface java.util.Collection<E>
        Specified by:
        iterator in interface java.lang.Iterable<E>
        Specified by:
        iterator in interface java.util.List<E>
        Overrides:
        iterator in class java.util.AbstractList<E>

      • poll

        public E poll()
        Specified by:
        poll in interface java.util.Queue<E>

      • peek

        public E peek()
        Specified by:
        peek in interface java.util.Queue<E>

      • remove

        public E remove()
        Specified by:
        remove in interface java.util.Queue<E>

      • element

        public E element()
        Specified by:
        element in interface java.util.Queue<E>

      • offer

        public boolean offer​(E e)
        Specified by:
        offer in interface java.util.concurrent.BlockingQueue<E>
        Specified by:
        offer in interface java.util.Queue<E>

      • add

        public boolean add​(E e)
        Specified by:
        add in interface java.util.concurrent.BlockingQueue<E>
        Specified by:
        add in interface java.util.Collection<E>
        Specified by:
        add in interface java.util.List<E>
        Specified by:
        add in interface java.util.Queue<E>
        Overrides:
        add in class java.util.AbstractList<E>

      • put

        public void put​(E o)
         throws java.lang.InterruptedException
        Specified by:
        put in interface java.util.concurrent.BlockingQueue<E>
        Throws:
        java.lang.InterruptedException

      • offer

        public boolean offer​(E o,
                     long timeout,
                     java.util.concurrent.TimeUnit unit)
              throws java.lang.InterruptedException
        Specified by:
        offer in interface java.util.concurrent.BlockingQueue<E>
        Throws:
        java.lang.InterruptedException

      • take

        public E take()
       throws java.lang.InterruptedException
        Specified by:
        take in interface java.util.concurrent.BlockingQueue<E>
        Throws:
        java.lang.InterruptedException

      • poll

        public E poll​(long time,
              java.util.concurrent.TimeUnit unit)
       throws java.lang.InterruptedException
        Specified by:
        poll in interface java.util.concurrent.BlockingQueue<E>
        Throws:
        java.lang.InterruptedException

      • remove

        public boolean remove​(java.lang.Object o)
        Specified by:
        remove in interface java.util.concurrent.BlockingQueue<E>
        Specified by:
        remove in interface java.util.Collection<E>
        Specified by:
        remove in interface java.util.List<E>
        Overrides:
        remove in class java.util.AbstractCollection<E>

      • remainingCapacity

        public int remainingCapacity()
        Specified by:
        remainingCapacity in interface java.util.concurrent.BlockingQueue<E>

      • drainTo

        public int drainTo​(java.util.Collection<? super E> c)
        Specified by:
        drainTo in interface java.util.concurrent.BlockingQueue<E>

      • drainTo

        public int drainTo​(java.util.Collection<? super E> c,
                   int maxElements)
        Specified by:
        drainTo in interface java.util.concurrent.BlockingQueue<E>

      • get

        public E get​(int index)
        Specified by:
        get in interface java.util.List<E>
        Specified by:
        get in class java.util.AbstractList<E>

      • add

        public void add​(int index,
                E e)
        Specified by:
        add in interface java.util.List<E>
        Overrides:
        add in class java.util.AbstractList<E>

      • set

        public E set​(int index,
             E e)
        Specified by:
        set in interface java.util.List<E>
        Overrides:
        set in class java.util.AbstractList<E>

      • remove

        public E remove​(int index)
        Specified by:
        remove in interface java.util.List<E>
        Overrides:
        remove in class java.util.AbstractList<E>

      • listIterator

        public java.util.ListIterator<E> listIterator​(int index)
        Specified by:
        listIterator in interface java.util.List<E>
        Overrides:
        listIterator in class java.util.AbstractList<E>

      • getCapacity

        public int getCapacity()
        Returns:
        the current capacity of this queue

      • getMaxCapacity

        public int getMaxCapacity()
        Returns:
        the max capacity of this queue, or -1 if this queue is unbounded

      • grow

        private boolean grow()