Class LinkedBlockingDeque<E>

  • Type Parameters:
    E - the type of elements held in this collection Note: This was copied from Apache Harmony and modified to suit the needs of Commons Pool.
    All Implemented Interfaces:
    java.io.Serializable, java.lang.Iterable<E>, java.util.Collection<E>, java.util.Deque<E>, java.util.Queue<E>

    class LinkedBlockingDeque<E>
    extends java.util.AbstractQueue<E>
    implements java.util.Deque<E>, java.io.Serializable
    An optionally-bounded blocking deque based on linked nodes.

    The optional capacity bound constructor argument serves as a way to prevent excessive expansion. The capacity, if unspecified, is equal to Integer.MAX_VALUE. Linked nodes are dynamically created upon each insertion unless this would bring the deque above capacity.

    Most operations run in constant time (ignoring time spent blocking). Exceptions include remove, removeFirstOccurrence, removeLastOccurrence, contains, iterator.remove(), and the bulk operations, all of which run in linear time.

    This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces.

    This class is a member of the Java Collections Framework.

    Since:
    2.0
    • Constructor Summary

      Constructors 
      Constructor Description
      LinkedBlockingDeque()
      Creates a LinkedBlockingDeque with a capacity of Integer.MAX_VALUE.
      LinkedBlockingDeque​(boolean fairness)
      Creates a LinkedBlockingDeque with a capacity of Integer.MAX_VALUE and the given fairness policy.
      LinkedBlockingDeque​(int capacity)
      Creates a LinkedBlockingDeque with the given (fixed) capacity.
      LinkedBlockingDeque​(int capacity, boolean fairness)
      Creates a LinkedBlockingDeque with the given (fixed) capacity and fairness policy.
      LinkedBlockingDeque​(java.util.Collection<? extends E> c)
      Creates a LinkedBlockingDeque with a capacity of Integer.MAX_VALUE, initially containing the elements of the given collection, added in traversal order of the collection's iterator.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean add​(E e)
      void addFirst​(E e)
      void addLast​(E e)
      void clear()
      Atomically removes all of the elements from this deque.
      boolean contains​(java.lang.Object o)
      Returns true if this deque contains the specified element.
      java.util.Iterator<E> descendingIterator()
      int drainTo​(java.util.Collection<? super E> c)
      Empty the queue to the specified collection.
      int drainTo​(java.util.Collection<? super E> c, int maxElements)
      Empty no more than the specified number of elements from the queue to the specified collection.
      E element()
      Retrieves, but does not remove, the head of the queue represented by this deque.
      E getFirst()
      E getLast()
      int getTakeQueueLength()
      Returns the length of the queue of threads waiting to take instances from this deque.
      boolean hasTakeWaiters()
      Returns true if there are threads waiting to take instances from this deque.
      void interuptTakeWaiters()
      Interrupts the threads currently waiting to take an object from the pool.
      java.util.Iterator<E> iterator()
      Returns an iterator over the elements in this deque in proper sequence.
      private boolean linkFirst​(E e)
      Links provided element as first element, or returns false if full.
      private boolean linkLast​(E e)
      Links provided element as last element, or returns false if full.
      boolean offer​(E e)
      boolean offer​(E e, long timeout, java.util.concurrent.TimeUnit unit)
      Links the provided element as the last in the queue, waiting up to the specified time to do so if the queue is full.
      boolean offerFirst​(E e)
      boolean offerFirst​(E e, long timeout, java.util.concurrent.TimeUnit unit)
      Links the provided element as the first in the queue, waiting up to the specified time to do so if the queue is full.
      boolean offerLast​(E e)
      boolean offerLast​(E e, long timeout, java.util.concurrent.TimeUnit unit)
      Links the provided element as the last in the queue, waiting up to the specified time to do so if the queue is full.
      E peek()  
      E peekFirst()  
      E peekLast()  
      E poll()  
      E poll​(long timeout, java.util.concurrent.TimeUnit unit)
      Unlinks the first element in the queue, waiting up to the specified time to do so if the queue is empty.
      E pollFirst()  
      E pollFirst​(long timeout, java.util.concurrent.TimeUnit unit)
      Unlinks the first element in the queue, waiting up to the specified time to do so if the queue is empty.
      E pollLast()  
      E pollLast​(long timeout, java.util.concurrent.TimeUnit unit)
      Unlinks the last element in the queue, waiting up to the specified time to do so if the queue is empty.
      E pop()
      void push​(E e)
      void put​(E e)
      Links the provided element as the last in the queue, waiting until there is space to do so if the queue is full.
      void putFirst​(E e)
      Links the provided element as the first in the queue, waiting until there is space to do so if the queue is full.
      void putLast​(E e)
      Links the provided element as the last in the queue, waiting until there is space to do so if the queue is full.
      private void readObject​(java.io.ObjectInputStream s)
      Reconstitute this deque from a stream (that is, deserialize it).
      int remainingCapacity()
      Returns the number of additional elements that this deque can ideally (in the absence of memory or resource constraints) accept without blocking.
      E remove()
      Retrieves and removes the head of the queue represented by this deque.
      boolean remove​(java.lang.Object o)
      Removes the first occurrence of the specified element from this deque.
      E removeFirst()
      boolean removeFirstOccurrence​(java.lang.Object o)  
      E removeLast()
      boolean removeLastOccurrence​(java.lang.Object o)  
      int size()
      Returns the number of elements in this deque.
      E take()
      Unlinks the first element in the queue, waiting until there is an element to unlink if the queue is empty.
      E takeFirst()
      Unlinks the first element in the queue, waiting until there is an element to unlink if the queue is empty.
      E takeLast()
      Unlinks the last element in the queue, waiting until there is an element to unlink if the queue is empty.
      java.lang.Object[] toArray()
      Returns an array containing all of the elements in this deque, in proper sequence (from first to last element).
      <T> T[] toArray​(T[] a)
      java.lang.String toString()  
      private void unlink​(LinkedBlockingDeque.Node<E> x)
      Unlinks the provided node.
      private E unlinkFirst()
      Removes and returns the first element, or null if empty.
      private E unlinkLast()
      Removes and returns the last element, or null if empty.
      private void writeObject​(java.io.ObjectOutputStream s)
      Save the state of this deque to a stream (that is, serialize it).
      • Methods inherited from class java.util.AbstractQueue

        addAll
      • Methods inherited from class java.util.AbstractCollection

        containsAll, isEmpty, removeAll, retainAll
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
      • Methods inherited from interface java.util.Collection

        containsAll, equals, hashCode, isEmpty, parallelStream, removeAll, removeIf, retainAll, spliterator, stream, toArray
      • Methods inherited from interface java.util.Deque

        addAll
      • Methods inherited from interface java.lang.Iterable

        forEach
    • Field Detail

      • first

        private transient LinkedBlockingDeque.Node<E> first
        Pointer to first node. Invariant: (first == null && last == null) || (first.prev == null && first.item != null)
      • last

        private transient LinkedBlockingDeque.Node<E> last
        Pointer to last node. Invariant: (first == null && last == null) || (last.next == null && last.item != null)
      • count

        private transient int count
        Number of items in the deque
      • capacity

        private final int capacity
        Maximum number of items in the deque
      • notEmpty

        private final java.util.concurrent.locks.Condition notEmpty
        Condition for waiting takes
      • notFull

        private final java.util.concurrent.locks.Condition notFull
        Condition for waiting puts
    • Constructor Detail

      • LinkedBlockingDeque

        public LinkedBlockingDeque()
        Creates a LinkedBlockingDeque with a capacity of Integer.MAX_VALUE.
      • LinkedBlockingDeque

        public LinkedBlockingDeque​(boolean fairness)
        Creates a LinkedBlockingDeque with a capacity of Integer.MAX_VALUE and the given fairness policy.
        Parameters:
        fairness - true means threads waiting on the deque should be served as if waiting in a FIFO request queue
      • LinkedBlockingDeque

        public LinkedBlockingDeque​(int capacity)
        Creates a LinkedBlockingDeque with the given (fixed) capacity.
        Parameters:
        capacity - the capacity of this deque
        Throws:
        java.lang.IllegalArgumentException - if capacity is less than 1
      • LinkedBlockingDeque

        public LinkedBlockingDeque​(int capacity,
                                   boolean fairness)
        Creates a LinkedBlockingDeque with the given (fixed) capacity and fairness policy.
        Parameters:
        capacity - the capacity of this deque
        fairness - true means threads waiting on the deque should be served as if waiting in a FIFO request queue
        Throws:
        java.lang.IllegalArgumentException - if capacity is less than 1
      • LinkedBlockingDeque

        public LinkedBlockingDeque​(java.util.Collection<? extends E> c)
        Creates a LinkedBlockingDeque with a capacity of Integer.MAX_VALUE, initially containing the elements of the given collection, added in traversal order of the collection's iterator.
        Parameters:
        c - the collection of elements to initially contain
        Throws:
        java.lang.NullPointerException - if the specified collection or any of its elements are null
    • Method Detail

      • linkFirst

        private boolean linkFirst​(E e)
        Links provided element as first element, or returns false if full.
        Parameters:
        e - The element to link as the first element.
        Returns:
        true if successful, otherwise false
      • linkLast

        private boolean linkLast​(E e)
        Links provided element as last element, or returns false if full.
        Parameters:
        e - The element to link as the last element.
        Returns:
        true if successful, otherwise false
      • unlinkFirst

        private E unlinkFirst()
        Removes and returns the first element, or null if empty.
        Returns:
        The first element or null if empty
      • unlinkLast

        private E unlinkLast()
        Removes and returns the last element, or null if empty.
        Returns:
        The first element or null if empty
      • unlink

        private void unlink​(LinkedBlockingDeque.Node<E> x)
        Unlinks the provided node.
        Parameters:
        x - The node to unlink
      • addFirst

        public void addFirst​(E e)
        Specified by:
        addFirst in interface java.util.Deque<E>
      • addLast

        public void addLast​(E e)
        Specified by:
        addLast in interface java.util.Deque<E>
      • offerFirst

        public boolean offerFirst​(E e)
        Specified by:
        offerFirst in interface java.util.Deque<E>
      • offerLast

        public boolean offerLast​(E e)
        Specified by:
        offerLast in interface java.util.Deque<E>
      • putFirst

        public void putFirst​(E e)
                      throws java.lang.InterruptedException
        Links the provided element as the first in the queue, waiting until there is space to do so if the queue is full.
        Parameters:
        e - element to link
        Throws:
        java.lang.NullPointerException
        java.lang.InterruptedException
      • putLast

        public void putLast​(E e)
                     throws java.lang.InterruptedException
        Links the provided element as the last in the queue, waiting until there is space to do so if the queue is full.
        Parameters:
        e - element to link
        Throws:
        java.lang.NullPointerException
        java.lang.InterruptedException
      • offerFirst

        public boolean offerFirst​(E e,
                                  long timeout,
                                  java.util.concurrent.TimeUnit unit)
                           throws java.lang.InterruptedException
        Links the provided element as the first in the queue, waiting up to the specified time to do so if the queue is full.
        Parameters:
        e - element to link
        timeout - length of time to wait
        unit - units that timeout is expressed in
        Returns:
        true if successful, otherwise false
        Throws:
        java.lang.NullPointerException
        java.lang.InterruptedException
      • offerLast

        public boolean offerLast​(E e,
                                 long timeout,
                                 java.util.concurrent.TimeUnit unit)
                          throws java.lang.InterruptedException
        Links the provided element as the last in the queue, waiting up to the specified time to do so if the queue is full.
        Parameters:
        e - element to link
        timeout - length of time to wait
        unit - units that timeout is expressed in
        Returns:
        true if successful, otherwise false
        Throws:
        java.lang.NullPointerException
        java.lang.InterruptedException
      • removeFirst

        public E removeFirst()
        Specified by:
        removeFirst in interface java.util.Deque<E>
      • removeLast

        public E removeLast()
        Specified by:
        removeLast in interface java.util.Deque<E>
      • pollFirst

        public E pollFirst()
        Specified by:
        pollFirst in interface java.util.Deque<E>
      • pollLast

        public E pollLast()
        Specified by:
        pollLast in interface java.util.Deque<E>
      • takeFirst

        public E takeFirst()
                    throws java.lang.InterruptedException
        Unlinks the first element in the queue, waiting until there is an element to unlink if the queue is empty.
        Returns:
        the unlinked element
        Throws:
        java.lang.InterruptedException - if the current thread is interrupted
      • takeLast

        public E takeLast()
                   throws java.lang.InterruptedException
        Unlinks the last element in the queue, waiting until there is an element to unlink if the queue is empty.
        Returns:
        the unlinked element
        Throws:
        java.lang.InterruptedException - if the current thread is interrupted
      • pollFirst

        public E pollFirst​(long timeout,
                           java.util.concurrent.TimeUnit unit)
                    throws java.lang.InterruptedException
        Unlinks the first element in the queue, waiting up to the specified time to do so if the queue is empty.
        Parameters:
        timeout - length of time to wait
        unit - units that timeout is expressed in
        Returns:
        the unlinked element
        Throws:
        java.lang.InterruptedException - if the current thread is interrupted
      • pollLast

        public E pollLast​(long timeout,
                          java.util.concurrent.TimeUnit unit)
                   throws java.lang.InterruptedException
        Unlinks the last element in the queue, waiting up to the specified time to do so if the queue is empty.
        Parameters:
        timeout - length of time to wait
        unit - units that timeout is expressed in
        Returns:
        the unlinked element
        Throws:
        java.lang.InterruptedException - if the current thread is interrupted
      • getFirst

        public E getFirst()
        Specified by:
        getFirst in interface java.util.Deque<E>
      • getLast

        public E getLast()
        Specified by:
        getLast in interface java.util.Deque<E>
      • peekFirst

        public E peekFirst()
        Specified by:
        peekFirst in interface java.util.Deque<E>
      • peekLast

        public E peekLast()
        Specified by:
        peekLast in interface java.util.Deque<E>
      • removeFirstOccurrence

        public boolean removeFirstOccurrence​(java.lang.Object o)
        Specified by:
        removeFirstOccurrence in interface java.util.Deque<E>
      • removeLastOccurrence

        public boolean removeLastOccurrence​(java.lang.Object o)
        Specified by:
        removeLastOccurrence in interface java.util.Deque<E>
      • add

        public boolean add​(E e)
        Specified by:
        add in interface java.util.Collection<E>
        Specified by:
        add in interface java.util.Deque<E>
        Specified by:
        add in interface java.util.Queue<E>
        Overrides:
        add in class java.util.AbstractQueue<E>
      • offer

        public boolean offer​(E e)
        Specified by:
        offer in interface java.util.Deque<E>
        Specified by:
        offer in interface java.util.Queue<E>
      • put

        public void put​(E e)
                 throws java.lang.InterruptedException
        Links the provided element as the last in the queue, waiting until there is space to do so if the queue is full.

        This method is equivalent to putLast(Object).

        Parameters:
        e - element to link
        Throws:
        java.lang.NullPointerException
        java.lang.InterruptedException
      • offer

        public boolean offer​(E e,
                             long timeout,
                             java.util.concurrent.TimeUnit unit)
                      throws java.lang.InterruptedException
        Links the provided element as the last in the queue, waiting up to the specified time to do so if the queue is full.

        This method is equivalent to offerLast(Object, long, TimeUnit)

        Parameters:
        e - element to link
        timeout - length of time to wait
        unit - units that timeout is expressed in
        Returns:
        true if successful, otherwise false
        Throws:
        java.lang.NullPointerException
        java.lang.InterruptedException
      • remove

        public E remove()
        Retrieves and removes the head of the queue represented by this deque. This method differs from poll only in that it throws an exception if this deque is empty.

        This method is equivalent to removeFirst.

        Specified by:
        remove in interface java.util.Deque<E>
        Specified by:
        remove in interface java.util.Queue<E>
        Overrides:
        remove in class java.util.AbstractQueue<E>
        Returns:
        the head of the queue represented by this deque
        Throws:
        java.util.NoSuchElementException - if this deque is empty
      • poll

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

        public E take()
               throws java.lang.InterruptedException
        Unlinks the first element in the queue, waiting until there is an element to unlink if the queue is empty.

        This method is equivalent to takeFirst().

        Returns:
        the unlinked element
        Throws:
        java.lang.InterruptedException - if the current thread is interrupted
      • poll

        public E poll​(long timeout,
                      java.util.concurrent.TimeUnit unit)
               throws java.lang.InterruptedException
        Unlinks the first element in the queue, waiting up to the specified time to do so if the queue is empty.

        This method is equivalent to pollFirst(long, TimeUnit).

        Parameters:
        timeout - length of time to wait
        unit - units that timeout is expressed in
        Returns:
        the unlinked element
        Throws:
        java.lang.InterruptedException - if the current thread is interrupted
      • element

        public E element()
        Retrieves, but does not remove, the head of the queue represented by this deque. This method differs from peek only in that it throws an exception if this deque is empty.

        This method is equivalent to getFirst.

        Specified by:
        element in interface java.util.Deque<E>
        Specified by:
        element in interface java.util.Queue<E>
        Overrides:
        element in class java.util.AbstractQueue<E>
        Returns:
        the head of the queue represented by this deque
        Throws:
        java.util.NoSuchElementException - if this deque is empty
      • peek

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

        public int remainingCapacity()
        Returns the number of additional elements that this deque can ideally (in the absence of memory or resource constraints) accept without blocking. This is always equal to the initial capacity of this deque less the current size of this deque.

        Note that you cannot always tell if an attempt to insert an element will succeed by inspecting remainingCapacity because it may be the case that another thread is about to insert or remove an element.

        Returns:
        The number of additional elements the queue is able to accept
      • drainTo

        public int drainTo​(java.util.Collection<? super E> c)
        Empty the queue to the specified collection.
        Parameters:
        c - The collection to add the elements to
        Returns:
        number of elements added to the collection
        Throws:
        java.lang.UnsupportedOperationException
        java.lang.ClassCastException
        java.lang.NullPointerException
        java.lang.IllegalArgumentException
      • drainTo

        public int drainTo​(java.util.Collection<? super E> c,
                           int maxElements)
        Empty no more than the specified number of elements from the queue to the specified collection.
        Parameters:
        c - collection to add the elements to
        maxElements - maximum number of elements to remove from the queue
        Returns:
        number of elements added to the collection
        Throws:
        java.lang.UnsupportedOperationException
        java.lang.ClassCastException
        java.lang.NullPointerException
        java.lang.IllegalArgumentException
      • push

        public void push​(E e)
        Specified by:
        push in interface java.util.Deque<E>
      • pop

        public E pop()
        Specified by:
        pop in interface java.util.Deque<E>
      • remove

        public boolean remove​(java.lang.Object o)
        Removes the first occurrence of the specified element from this deque. If the deque does not contain the element, it is unchanged. More formally, removes the first element e such that o.equals(e) (if such an element exists). Returns true if this deque contained the specified element (or equivalently, if this deque changed as a result of the call).

        This method is equivalent to removeFirstOccurrence.

        Specified by:
        remove in interface java.util.Collection<E>
        Specified by:
        remove in interface java.util.Deque<E>
        Overrides:
        remove in class java.util.AbstractCollection<E>
        Parameters:
        o - element to be removed from this deque, if present
        Returns:
        true if this deque changed as a result of the call
      • size

        public int size()
        Returns the number of elements in this deque.
        Specified by:
        size in interface java.util.Collection<E>
        Specified by:
        size in interface java.util.Deque<E>
        Specified by:
        size in class java.util.AbstractCollection<E>
        Returns:
        the number of elements in this deque
      • contains

        public boolean contains​(java.lang.Object o)
        Returns true if this deque contains the specified element. More formally, returns true if and only if this deque contains at least one element e such that o.equals(e).
        Specified by:
        contains in interface java.util.Collection<E>
        Specified by:
        contains in interface java.util.Deque<E>
        Overrides:
        contains in class java.util.AbstractCollection<E>
        Parameters:
        o - object to be checked for containment in this deque
        Returns:
        true if this deque contains the specified element
      • toArray

        public java.lang.Object[] toArray()
        Returns an array containing all of the elements in this deque, in proper sequence (from first to last element).

        The returned array will be "safe" in that no references to it are maintained by this deque. (In other words, this method must allocate a new array). The caller is thus free to modify the returned array.

        This method acts as bridge between array-based and collection-based APIs.

        Specified by:
        toArray in interface java.util.Collection<E>
        Overrides:
        toArray in class java.util.AbstractCollection<E>
        Returns:
        an array containing all of the elements in this deque
      • toArray

        public <T> T[] toArray​(T[] a)
        Specified by:
        toArray in interface java.util.Collection<E>
        Overrides:
        toArray in class java.util.AbstractCollection<E>
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.util.AbstractCollection<E>
      • clear

        public void clear()
        Atomically removes all of the elements from this deque. The deque will be empty after this call returns.
        Specified by:
        clear in interface java.util.Collection<E>
        Overrides:
        clear in class java.util.AbstractQueue<E>
      • iterator

        public java.util.Iterator<E> iterator()
        Returns an iterator over the elements in this deque in proper sequence. The elements will be returned in order from first (head) to last (tail). The returned Iterator is a "weakly consistent" iterator that will never throw ConcurrentModificationException, and guarantees to traverse elements as they existed upon construction of the iterator, and may (but is not guaranteed to) reflect any modifications subsequent to construction.
        Specified by:
        iterator in interface java.util.Collection<E>
        Specified by:
        iterator in interface java.util.Deque<E>
        Specified by:
        iterator in interface java.lang.Iterable<E>
        Specified by:
        iterator in class java.util.AbstractCollection<E>
        Returns:
        an iterator over the elements in this deque in proper sequence
      • descendingIterator

        public java.util.Iterator<E> descendingIterator()
        Specified by:
        descendingIterator in interface java.util.Deque<E>
      • writeObject

        private void writeObject​(java.io.ObjectOutputStream s)
                          throws java.io.IOException
        Save the state of this deque to a stream (that is, serialize it).
        Parameters:
        s - the stream
        Throws:
        java.io.IOException
      • readObject

        private void readObject​(java.io.ObjectInputStream s)
                         throws java.io.IOException,
                                java.lang.ClassNotFoundException
        Reconstitute this deque from a stream (that is, deserialize it).
        Parameters:
        s - the stream
        Throws:
        java.io.IOException
        java.lang.ClassNotFoundException
      • hasTakeWaiters

        public boolean hasTakeWaiters()
        Returns true if there are threads waiting to take instances from this deque. See disclaimer on accuracy in ReentrantLock.hasWaiters(Condition).
        Returns:
        true if there is at least one thread waiting on this deque's notEmpty condition.
      • getTakeQueueLength

        public int getTakeQueueLength()
        Returns the length of the queue of threads waiting to take instances from this deque. See disclaimer on accuracy in ReentrantLock.getWaitQueueLength(Condition).
        Returns:
        number of threads waiting on this deque's notEmpty condition.
      • interuptTakeWaiters

        public void interuptTakeWaiters()
        Interrupts the threads currently waiting to take an object from the pool. See disclaimer on accuracy in ReentrantLock.getWaitingThreads(Condition).