Class LinkedBlockingDeque<E>

java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractQueue<E>
org.datanucleus.store.rdbms.datasource.dbcp2.pool2.impl.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:
Serializable, Iterable<E>, Collection<E>, Deque<E>, Queue<E>, SequencedCollection<E>

class LinkedBlockingDeque<E> extends AbstractQueue<E> implements Deque<E>, 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
  • Field Details

    • serialVersionUID

      private static final long serialVersionUID
      See Also:
    • first

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

      private transient LinkedBlockingDeque.Node<E> last
      Pointer to last node. Invariant: (first == null invalid input: '&'invalid input: '&' last == null) || (last.next == null invalid input: '&'invalid input: '&' 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
    • lock

      private final InterruptibleReentrantLock lock
      Main lock guarding all access
    • notEmpty

      private final Condition notEmpty
      Condition for waiting takes
    • notFull

      private final Condition notFull
      Condition for waiting puts
  • Constructor Details

    • 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:
      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:
      IllegalArgumentException - if capacity is less than 1
    • LinkedBlockingDeque

      public LinkedBlockingDeque(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:
      NullPointerException - if the specified collection or any of its elements are null
  • Method Details

    • 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 Deque<E>
      Specified by:
      addFirst in interface SequencedCollection<E>
    • addLast

      public void addLast(E e)
      Specified by:
      addLast in interface Deque<E>
      Specified by:
      addLast in interface SequencedCollection<E>
    • offerFirst

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

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

      public void putFirst(E e) throws 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:
      NullPointerException - if e is null
      InterruptedException - if the thread is interrupted whilst waiting for space
    • putLast

      public void putLast(E e) throws 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:
      NullPointerException - if e is null
      InterruptedException - if the thread is interrupted whilst waiting for space
    • offerFirst

      public boolean offerFirst(E e, long timeout, TimeUnit unit) throws 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:
      NullPointerException - if e is null
      InterruptedException - if the thread is interrupted whilst waiting for space
    • offerLast

      public boolean offerLast(E e, long timeout, TimeUnit unit) throws 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:
      NullPointerException - if e is null
      InterruptedException - if the thread is interrupted whist waiting for space
    • removeFirst

      public E removeFirst()
      Specified by:
      removeFirst in interface Deque<E>
      Specified by:
      removeFirst in interface SequencedCollection<E>
    • removeLast

      public E removeLast()
      Specified by:
      removeLast in interface Deque<E>
      Specified by:
      removeLast in interface SequencedCollection<E>
    • pollFirst

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

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

      public E takeFirst() throws 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:
      InterruptedException - if the current thread is interrupted
    • takeLast

      public E takeLast() throws 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:
      InterruptedException - if the current thread is interrupted
    • pollFirst

      public E pollFirst(long timeout, TimeUnit unit) throws 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:
      InterruptedException - if the current thread is interrupted
    • pollLast

      public E pollLast(long timeout, TimeUnit unit) throws 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:
      InterruptedException - if the current thread is interrupted
    • getFirst

      public E getFirst()
      Specified by:
      getFirst in interface Deque<E>
      Specified by:
      getFirst in interface SequencedCollection<E>
    • getLast

      public E getLast()
      Specified by:
      getLast in interface Deque<E>
      Specified by:
      getLast in interface SequencedCollection<E>
    • peekFirst

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

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

      public boolean removeFirstOccurrence(Object o)
      Specified by:
      removeFirstOccurrence in interface Deque<E>
    • removeLastOccurrence

      public boolean removeLastOccurrence(Object o)
      Specified by:
      removeLastOccurrence in interface Deque<E>
    • add

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

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

      public void put(E e) throws 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:
      NullPointerException - if e is null
      InterruptedException - if the thread is interrupted whilst waiting for space
    • offer

      public boolean offer(E e, long timeout, TimeUnit unit) throws 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:
      NullPointerException - if e is null
      InterruptedException - if the thread is interrupted whilst waiting for space
    • 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 Deque<E>
      Specified by:
      remove in interface Queue<E>
      Overrides:
      remove in class AbstractQueue<E>
      Returns:
      the head of the queue represented by this deque
      Throws:
      NoSuchElementException - if this deque is empty
    • poll

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

      public E take() throws 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:
      InterruptedException - if the current thread is interrupted
    • poll

      public E poll(long timeout, TimeUnit unit) throws 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:
      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 Deque<E>
      Specified by:
      element in interface Queue<E>
      Overrides:
      element in class AbstractQueue<E>
      Returns:
      the head of the queue represented by this deque
      Throws:
      NoSuchElementException - if this deque is empty
    • peek

      public E peek()
      Specified by:
      peek in interface Deque<E>
      Specified by:
      peek in interface 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(Collection<? super E> c)
      Drains the queue to the specified collection.
      Parameters:
      c - The collection to add the elements to
      Returns:
      number of elements added to the collection
      Throws:
      UnsupportedOperationException - if the add operation is not supported by the specified collection
      ClassCastException - if the class of the elements held by this collection prevents them from being added to the specified collection
      NullPointerException - if c is null
      IllegalArgumentException - if c is this instance
    • drainTo

      public int drainTo(Collection<? super E> c, int maxElements)
      Drains 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:
      UnsupportedOperationException - if the add operation is not supported by the specified collection
      ClassCastException - if the class of the elements held by this collection prevents them from being added to the specified collection
      NullPointerException - if c is null
      IllegalArgumentException - if c is this instance
    • push

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

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

      public boolean remove(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 Collection<E>
      Specified by:
      remove in interface Deque<E>
      Overrides:
      remove in class 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 Collection<E>
      Specified by:
      size in interface Deque<E>
      Specified by:
      size in class AbstractCollection<E>
      Returns:
      the number of elements in this deque
    • contains

      public boolean contains(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 Collection<E>
      Specified by:
      contains in interface Deque<E>
      Overrides:
      contains in class AbstractCollection<E>
      Parameters:
      o - object to be checked for containment in this deque
      Returns:
      true if this deque contains the specified element
    • toArray

      public 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 Collection<E>
      Overrides:
      toArray in class 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 Collection<E>
      Overrides:
      toArray in class AbstractCollection<E>
    • toString

      public String toString()
      Overrides:
      toString in class 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 Collection<E>
      Overrides:
      clear in class AbstractQueue<E>
    • iterator

      public 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 Collection<E>
      Specified by:
      iterator in interface Deque<E>
      Specified by:
      iterator in interface Iterable<E>
      Specified by:
      iterator in class AbstractCollection<E>
      Returns:
      an iterator over the elements in this deque in proper sequence
    • descendingIterator

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

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

      private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException
      Reconstitutes this deque from a stream (that is, deserialize it).
      Parameters:
      s - the stream
      Throws:
      IOException
      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).