Top Description Constructors Methods
rx.internal.util.atomic

public final Class MpscLinkedAtomicQueue<E>

extends BaseLinkedAtomicQueue<E>
Class Inheritance
This is a direct Java port of the MPSC algorithm as presented on 1024 Cores by D. Vyukov. The original has been adapted to Java and it's quirks with regards to memory model and layout:
  1. Use XCHG functionality provided by AtomicReference (which is better in JDK 8+).
The queue is initialized with a stub node which is set to both the producer and consumer node references. From this point follow the notes on offer/poll.
Author
nitsanw

Constructor Summary

AccessConstructor and Description
public
MpscLinkedAtomicQueue()

Method Summary

Modifier and TypeMethod and Description
public boolean
offer(final E
the element to add
nextValue)

Implements java.util.Queue.offer.

Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions.
public E
peek()

Implements java.util.Queue.peek.

Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
public E
poll()

Implements java.util.Queue.poll.

Retrieves and removes the head of this queue, or returns null if this queue is empty.
Inherited from rx.internal.util.atomic.BaseLinkedAtomicQueue:
isEmptyiteratorlpConsumerNodelpProducerNodelvConsumerNodelvProducerNodesizespConsumerNodespProducerNodexchgProducerNode

Constructor Detail

MpscLinkedAtomicQueueback to summary
public MpscLinkedAtomicQueue()

Method Detail

offerback to summary
public boolean offer(final E nextValue)

Implements java.util.Queue.offer.

Doc from java.util.Queue.offer.

Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions. When using a capacity-restricted queue, this method is generally preferable to add, which can fail to insert an element only by throwing an exception.

IMPLEMENTATION NOTES:
Offer is allowed from multiple threads.
Offer allocates a new node and:

  1. Swaps it atomically with current producer node (only one producer 'wins')
  2. Sets the new node as the node following from the swapped producer node
This works because each producer is guaranteed to 'plant' a new node and link the old node. No 2 producers can get the same producer node as part of XCHG guarantee.
Parameters
nextValue:E

the element to add

Returns:boolean

true if the element was added to this queue, else false

Annotations
@Override
See Also
java.util.Queue#offer(java.lang.Object)
peekback to summary
public E peek()

Implements java.util.Queue.peek.

Doc from java.util.Queue.peek.

Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.

Returns:E

the head of this queue, or null if this queue is empty

Annotations
@Override
pollback to summary
public E poll()

Implements java.util.Queue.poll.

Doc from java.util.Queue.poll.

Retrieves and removes the head of this queue, or returns null if this queue is empty.

IMPLEMENTATION NOTES:
Poll is allowed from a SINGLE thread.
Poll reads the next node from the consumerNode and:

  1. If it is null, the queue is assumed empty (though it might not be).
  2. If it is not null set it as the consumer node and return it's now evacuated value.
This means the consumerNode.value is always null, which is also the starting point for the queue. Because null values are not allowed to be offered this is the only node with it's value set to null at any one time.
Returns:E

the head of this queue, or null if this queue is empty

Annotations
@Override
See Also
java.util.Queue#poll()