org.jctools.queues

Class MpscArrayQueue<E>

java.lang.Object

java.util.AbstractCollection<E>

java.util.AbstractQueue<E>

org.jctools.queues.ConcurrentCircularArrayQueue<E>

org.jctools.queues.MpscArrayQueue<E>

Type Parameters:

E -

All Implemented Interfaces:

Iterable<E>, Collection<E>, Queue<E>, IndexedQueueSizeUtil.IndexedQueue, MessagePassingQueue<E>, QueueProgressIndicators

public class MpscArrayQueue<E>
extends ConcurrentCircularArrayQueue<E>

A Multi-Producer-Single-Consumer queue based on a ConcurrentCircularArrayQueue. This implies that any thread may call the offer method, but only a single thread may call poll/peek for correctness to maintained.
This implementation follows patterns documented on the package level for False Sharing protection.
This implementation is using the Fast Flow method for polling from the queue (with minor change to correctly publish the index) and an extension of the Leslie Lamport concurrent queue algorithm (originated by Martin Thompson) on the producer side.

Author:

nitsanw

Nested Class Summary

Nested classes/interfaces inherited from interface org.jctools.queues.MessagePassingQueue

MessagePassingQueue.Consumer<T>, MessagePassingQueue.ExitCondition, MessagePassingQueue.Supplier<T>, MessagePassingQueue.WaitStrategy

Field Summary

Fields

Modifier and Type	Field and Description
protected long	consumerIndex

Fields inherited from class org.jctools.queues.ConcurrentCircularArrayQueue

buffer, mask

Fields inherited from interface org.jctools.queues.MessagePassingQueue

UNBOUNDED_CAPACITY

Constructor Summary

Constructors

Constructor and Description
MpscArrayQueue(int capacity)

Method Summary

Modifier and Type	Method and Description
protected boolean	casProducerIndex(long expect, long newValue)
int	drain(MessagePassingQueue.Consumer<E> c) Remove all available item from the queue and hand to consume.
int	drain(MessagePassingQueue.Consumer<E> c, int limit) Remove up to limit elements from the queue and hand to consume.
void	drain(MessagePassingQueue.Consumer<E> c, MessagePassingQueue.WaitStrategy w, MessagePassingQueue.ExitCondition exit) Remove elements from the queue and hand to consume forever.
int	failFastOffer(E e) A wait free alternative to offer which fails on CAS failure.
int	fill(MessagePassingQueue.Supplier<E> s) Stuff the queue with elements from the supplier.
int	fill(MessagePassingQueue.Supplier<E> s, int limit) Stuff the queue with up to limit elements from the supplier.
void	fill(MessagePassingQueue.Supplier<E> s, MessagePassingQueue.WaitStrategy w, MessagePassingQueue.ExitCondition exit) Stuff the queue with elements from the supplier forever.
protected long	lpConsumerIndex()
long	lvConsumerIndex()
long	lvProducerIndex()
protected long	lvProducerLimit()
boolean	offer(E e) Called from a producer thread subject to the restrictions appropriate to the implementation and according to the Queue.offer(Object) interface.
boolean	offerIfBelowThreshold(E e, int threshold) offer(E)} if ConcurrentCircularArrayQueue.size() is less than threshold.
E	peek() Called from the consumer thread subject to the restrictions appropriate to the implementation and according to the Queue.peek() interface.
E	poll() Called from the consumer thread subject to the restrictions appropriate to the implementation and according to the Queue.poll() interface.
boolean	relaxedOffer(E e) Called from a producer thread subject to the restrictions appropriate to the implementation.
E	relaxedPeek() Called from the consumer thread subject to the restrictions appropriate to the implementation.
E	relaxedPoll() Called from the consumer thread subject to the restrictions appropriate to the implementation.
protected void	soConsumerIndex(long newValue)
protected void	soProducerLimit(long newValue)

Methods inherited from class org.jctools.queues.ConcurrentCircularArrayQueue

calcElementOffset, calcElementOffset, capacity, clear, currentConsumerIndex, currentProducerIndex, isEmpty, iterator, size, toString

Methods inherited from class java.util.AbstractQueue

add, addAll, element, remove

Methods inherited from class java.util.AbstractCollection

contains, containsAll, remove, removeAll, retainAll, toArray, toArray

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Collection

contains, containsAll, equals, hashCode, parallelStream, remove, removeAll, removeIf, retainAll, spliterator, stream, toArray, toArray

Methods inherited from interface java.lang.Iterable

forEach

Field Detail

consumerIndex

protected long consumerIndex

Constructor Detail

MpscArrayQueue

public MpscArrayQueue(int capacity)

Method Detail

offerIfBelowThreshold

public boolean offerIfBelowThreshold(E e,
                                     int threshold)

offer(E)} if ConcurrentCircularArrayQueue.size() is less than threshold.

Parameters:

e - the object to offer onto the queue, not null

threshold - the maximum allowable size

Returns:

true if the offer is successful, false if queue size exceeds threshold

Since:

1.0.1

offer

public boolean offer(E e)

Called from a producer thread subject to the restrictions appropriate to the implementation and according to the Queue.offer(Object) interface.

IMPLEMENTATION NOTES:
Lock free offer using a single CAS. As class name suggests access is permitted to many threads concurrently.

Parameters:

e - not null, will throw NPE if it is

Returns:

true if element was inserted into the queue, false iff full

See Also:

Queue.offer(E), MessagePassingQueue.offer(T)

failFastOffer

public final int failFastOffer(E e)

A wait free alternative to offer which fails on CAS failure.

Parameters:

e - new element, not null

Returns:

1 if next element cannot be filled, -1 if CAS failed, 0 if successful

poll

public E poll()

Called from the consumer thread subject to the restrictions appropriate to the implementation and according to the Queue.poll() interface.

IMPLEMENTATION NOTES:
Lock free poll using ordered loads/stores. As class name suggests access is limited to a single thread.

Returns:

a message from the queue if one is available, null iff empty

See Also:

Queue.poll(), MessagePassingQueue.poll()

peek

public E peek()

Called from the consumer thread subject to the restrictions appropriate to the implementation and according to the Queue.peek() interface.

IMPLEMENTATION NOTES:
Lock free peek using ordered loads. As class name suggests access is limited to a single thread.

Returns:

a message from the queue if one is available, null iff empty

See Also:

Queue.poll(), MessagePassingQueue.poll()

relaxedOffer

public boolean relaxedOffer(E e)

Description copied from interface: MessagePassingQueue

Called from a producer thread subject to the restrictions appropriate to the implementation. As opposed to Queue.offer(Object) this method may return false without the queue being full.

Parameters:

e - not null, will throw NPE if it is

Returns:

true if element was inserted into the queue, false if unable to offer

relaxedPoll

public E relaxedPoll()

Description copied from interface: MessagePassingQueue

Called from the consumer thread subject to the restrictions appropriate to the implementation. As opposed to Queue.poll() this method may return null without the queue being empty.

Returns:

a message from the queue if one is available, null if unable to poll

relaxedPeek

public E relaxedPeek()

Description copied from interface: MessagePassingQueue

Called from the consumer thread subject to the restrictions appropriate to the implementation. As opposed to Queue.peek() this method may return null without the queue being empty.

Returns:

a message from the queue if one is available, null if unable to peek

drain

public int drain(MessagePassingQueue.Consumer<E> c)

Description copied from interface: MessagePassingQueue

Remove all available item from the queue and hand to consume. This should be semantically similar to:
M m;
while((m = relaxedPoll()) != null){
c.accept(m);
}
There's no strong commitment to the queue being empty at the end of a drain. Called from a consumer thread subject to the restrictions appropriate to the implementation.

Returns:

the number of polled elements

fill

public int fill(MessagePassingQueue.Supplier<E> s)

Description copied from interface: MessagePassingQueue

Stuff the queue with elements from the supplier. Semantically similar to:
while(relaxedOffer(s.get());
There's no strong commitment to the queue being full at the end of a fill. Called from a producer thread subject to the restrictions appropriate to the implementation.

Returns:

the number of offered elements

drain

public int drain(MessagePassingQueue.Consumer<E> c,
                 int limit)

Description copied from interface: MessagePassingQueue

Remove up to limit elements from the queue and hand to consume. This should be semantically similar to:

 
   M m;
   int i = 0;
   for(;i < limit && (m = relaxedPoll()) != null; i++){
     c.accept(m);
   }
   return i;
 
 

There's no strong commitment to the queue being empty at the end of a drain. Called from a consumer thread subject to the restrictions appropriate to the implementation.

Returns:

the number of polled elements

fill

public int fill(MessagePassingQueue.Supplier<E> s,
                int limit)

Description copied from interface: MessagePassingQueue

Stuff the queue with up to limit elements from the supplier. Semantically similar to:

 
   for(int i=0; i < limit && relaxedOffer(s.get()); i++);

 
 

There's no strong commitment to the queue being full at the end of a fill. Called from a producer thread subject to the restrictions appropriate to the implementation.

Returns:

the number of offered elements

drain

public void drain(MessagePassingQueue.Consumer<E> c,
                  MessagePassingQueue.WaitStrategy w,
                  MessagePassingQueue.ExitCondition exit)

Description copied from interface: MessagePassingQueue

Remove elements from the queue and hand to consume forever. Semantically similar to:

 
  int idleCounter = 0;
  while (exit.keepRunning()) {
      E e = relaxedPoll();
      if(e==null){
          idleCounter = wait.idle(idleCounter);
          continue;
      }
      idleCounter = 0;
      c.accept(e);
  }
 
 

Called from a consumer thread subject to the restrictions appropriate to the implementation.

fill

public void fill(MessagePassingQueue.Supplier<E> s,
                 MessagePassingQueue.WaitStrategy w,
                 MessagePassingQueue.ExitCondition exit)

Description copied from interface: MessagePassingQueue

Stuff the queue with elements from the supplier forever. Semantically similar to:

 
  int idleCounter = 0;
  while (exit.keepRunning()) {
      E e = s.get();
      while (!relaxedOffer(e)) {
          idleCounter = wait.idle(idleCounter);
          continue;
      }
      idleCounter = 0;
  }
 
 

Called from a producer thread subject to the restrictions appropriate to the implementation.

lpConsumerIndex

protected final long lpConsumerIndex()

lvConsumerIndex

public final long lvConsumerIndex()

soConsumerIndex

protected void soConsumerIndex(long newValue)

lvProducerLimit

protected final long lvProducerLimit()

soProducerLimit

protected final void soProducerLimit(long newValue)

lvProducerIndex

public final long lvProducerIndex()

casProducerIndex

protected final boolean casProducerIndex(long expect,
                                         long newValue)