com.bluegosling.collections.concurrent

Class AbstractLockFreeBlockingDeque<E>

java.lang.Object

java.util.AbstractCollection<E>

java.util.AbstractQueue<E>

com.bluegosling.collections.AbstractDeque<E>

com.bluegosling.collections.concurrent.AbstractLockFreeBlockingDeque<E>

Type Parameters:

E - the type of element held in the queue

All Implemented Interfaces:

Iterable<E>, Collection<E>, BlockingDeque<E>, BlockingQueue<E>, Deque<E>, Queue<E>

Direct Known Subclasses:

ArrayBlockingDeque, LockFreeLinkedBlockingDeque

public abstract class AbstractLockFreeBlockingDeque<E>
extends AbstractDeque<E>
implements BlockingDeque<E>

An abstract blocking deque, useful for building deque implementations that do not rely on locks for thread-safey. This class provides a custom wait/notify mechanism that does not need locks (no Condition queues, no intrinsic locks/monitors).

Sub-classes must invoke signalNotEmpty() when their implementation of Deque.offerFirst(Object)/Deque.offerLast(Object) adds an element to a previously empty queue. Similarly, they must invoke signalNotFull() when their implementation of Deque.pollFirst()/Deque.pollLast() removes an element from a previously full queue.

Constructor Summary

Constructors

Constructor and Description
AbstractLockFreeBlockingDeque()

Method Summary

Modifier and Type	Method and Description
int	drainTo(Collection<? super E> c)
int	drainTo(Collection<? super E> c, int maxElements)
protected boolean	isTentativelyEmpty() Returns true if this deque is tentatively empty.
boolean	offer(E e, long timeout, TimeUnit unit)
boolean	offerFirst(E e, long timeout, TimeUnit unit)
protected boolean	offerFirstInterruptibly(E e) Adds an element to the head of the deque, allowing interruption.
boolean	offerLast(E e, long timeout, TimeUnit unit)
protected boolean	offerLastInterruptibly(E e) Adds an element to the tail of the deque, allowing interruption.
E	poll(long timeout, TimeUnit unit)
E	pollFirst(long timeout, TimeUnit unit)
protected E	pollFirstInterruptibly() Removes the first element in the deque, allowing interruption.
E	pollLast(long timeout, TimeUnit unit)
protected E	pollLastInterruptibly() Removes the last element in the deque, allowing interruption.
void	put(E e)
void	putFirst(E e)
void	putLast(E e)
protected void	signalNotEmpty() Signals a waiting thread that the deque is no longer empty.
protected void	signalNotFull() Signals a waiting thread that the deque is no longer full.
E	take()
E	takeFirst()
E	takeLast()
protected int	tentativeRemainingCapacity() Returns the tentative remaining capacity in the deque.

Methods inherited from class com.bluegosling.collections.AbstractDeque

add, addFirst, addLast, element, getFirst, getLast, offer, peek, poll, pop, push, remove, remove, removeFirst, removeFirstOccurrence, removeLast, removeLastOccurrence

Methods inherited from class java.util.AbstractQueue

addAll, clear

Methods inherited from class java.util.AbstractCollection

contains, containsAll, isEmpty, iterator, removeAll, retainAll, size, toArray, toArray, toString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.concurrent.BlockingDeque

add, addFirst, addLast, contains, element, iterator, offer, offerFirst, offerLast, peek, poll, push, remove, remove, removeFirstOccurrence, removeLastOccurrence, size

Methods inherited from interface java.util.concurrent.BlockingQueue

remainingCapacity

Methods inherited from interface java.util.Deque

descendingIterator, getFirst, getLast, peekFirst, peekLast, pollFirst, pollLast, pop, removeFirst, removeLast

Methods inherited from interface java.util.Collection

addAll, clear, containsAll, equals, hashCode, isEmpty, parallelStream, removeAll, removeIf, retainAll, spliterator, stream, toArray, toArray

Methods inherited from interface java.lang.Iterable

forEach

Constructor Detail

AbstractLockFreeBlockingDeque

public AbstractLockFreeBlockingDeque()

Method Detail

put

public void put(E e)
         throws InterruptedException

Specified by:

put in interface BlockingDeque<E>

Specified by:

put in interface BlockingQueue<E>

Throws:

InterruptedException

offer

public boolean offer(E e,
                     long timeout,
                     TimeUnit unit)
              throws InterruptedException

Specified by:

offer in interface BlockingDeque<E>

Specified by:

offer in interface BlockingQueue<E>

Throws:

InterruptedException

take

public E take()
       throws InterruptedException

Specified by:

take in interface BlockingDeque<E>

Specified by:

take in interface BlockingQueue<E>

Throws:

InterruptedException

poll

public E poll(long timeout,
              TimeUnit unit)
       throws InterruptedException

Specified by:

poll in interface BlockingDeque<E>

Specified by:

poll in interface BlockingQueue<E>

Throws:

InterruptedException

pollFirstInterruptibly

protected E pollFirstInterruptibly()
                            throws InterruptedException

Removes the first element in the deque, allowing interruption. Since most lock-free deques won't have blocking operations during Deque.pollFirst() (and thus not be interruptible), this method typically need not be overridden. But if any operations are interruptible, this method should be implemented to propagate that interruption, whereas the Deque.pollFirst() method (due to its signature) must suppress it.

Returns:

the item removed from the deque or null if the deque is empty

Throws:

InterruptedException - if the operation was interrupted

pollLastInterruptibly

protected E pollLastInterruptibly()
                           throws InterruptedException

Removes the last element in the deque, allowing interruption. Since most lock-free deques won't have blocking operations during Deque.pollLast() (and thus not be interruptible), this method typically need not be overridden. But if any operations are interruptible, this method should be implemented to propagate that interruption, whereas the Deque.pollLast() method (due to its signature) must suppress it.

Returns:

the item removed from the deque or null if the deque is empty

Throws:

InterruptedException - if the operation was interrupted

offerFirstInterruptibly

protected boolean offerFirstInterruptibly(E e)
                                   throws InterruptedException

Adds an element to the head of the deque, allowing interruption. Since most lock-free deques won't have blocking operations during Deque.offerFirst(Object) (and thus not be interruptible), this method typically need not be overridden. But if any operations are interruptible, this method should be implemented to propagate that interruption, whereas the Deque.offerFirst(Object) method (due to its signature) must suppress it.

Returns:

true if the element was accepted or false if the deque is full

Throws:

InterruptedException - if the operation was interrupted

offerLastInterruptibly

protected boolean offerLastInterruptibly(E e)
                                  throws InterruptedException

Adds an element to the tail of the deque, allowing interruption. Since most lock-free deques won't have blocking operations during Deque.offerLast(Object) (and thus not be interruptible), this method typically need not be overridden. But if any operations are interruptible, this method should be implemented to propagate that interruption, whereas the Deque.offerLast(Object) method (due to its signature) must suppress it.

Returns:

true if the element was accepted or false if the deque is full

Throws:

InterruptedException - if the operation was interrupted

signalNotEmpty

protected final void signalNotEmpty()

Signals a waiting thread that the deque is no longer empty. An operation that transitions the deque from empty to not empty must call this method in case there are threads waiting to take an element.

signalNotFull

protected final void signalNotFull()

Signals a waiting thread that the deque is no longer full. An operation that transitions the deque from full to not full must call this method in case there are threads waiting to add an element.

putFirst

public void putFirst(E e)
              throws InterruptedException

Specified by:

putFirst in interface BlockingDeque<E>

Throws:

InterruptedException

putLast

public void putLast(E e)
             throws InterruptedException

Specified by:

putLast in interface BlockingDeque<E>

Throws:

InterruptedException

offerFirst

public boolean offerFirst(E e,
                          long timeout,
                          TimeUnit unit)
                   throws InterruptedException

Specified by:

offerFirst in interface BlockingDeque<E>

Throws:

InterruptedException

offerLast

public boolean offerLast(E e,
                         long timeout,
                         TimeUnit unit)
                  throws InterruptedException

Specified by:

offerLast in interface BlockingDeque<E>

Throws:

InterruptedException

takeFirst

public E takeFirst()
            throws InterruptedException

Specified by:

takeFirst in interface BlockingDeque<E>

Throws:

InterruptedException

takeLast

public E takeLast()
           throws InterruptedException

Specified by:

takeLast in interface BlockingDeque<E>

Throws:

InterruptedException

pollFirst

public E pollFirst(long timeout,
                   TimeUnit unit)
            throws InterruptedException

Specified by:

pollFirst in interface BlockingDeque<E>

Throws:

InterruptedException

pollLast

public E pollLast(long timeout,
                  TimeUnit unit)
           throws InterruptedException

Specified by:

pollLast in interface BlockingDeque<E>

Throws:

InterruptedException

drainTo

public int drainTo(Collection<? super E> c)

Specified by:

drainTo in interface BlockingQueue<E>

drainTo

public int drainTo(Collection<? super E> c,
                   int maxElements)

Specified by:

drainTo in interface BlockingQueue<E>

tentativeRemainingCapacity

protected int tentativeRemainingCapacity()

Returns the tentative remaining capacity in the deque. If different from BlockingQueue.remainingCapacity(), then this returns a capacity after considering incomplete operations whereas the other returns "confirmed" remaining capacity, considering only completed operations.

Returns:

the tentative remaining capacity in the deque

isTentativelyEmpty

protected boolean isTentativelyEmpty()

Returns true if this deque is tentatively empty. If different from AbstractCollection.isEmpty(), then this returns true if the deque is empty after considering incomplete operations whereas the other returns if the deque is "confirmed" empty, considering only completed operations.

Returns:

true if this deque is tentatively empty