Top Description Fields Constructors Methods
rx.internal.util.unsafe

public final Class SpscLinkedQueue<E>

extends BaseLinkedQueue<E>
Class Inheritance
Imports
rx.internal.util.atomic.LinkedQueueNode
This is a weakened version 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 inheritance to ensure no false sharing occurs between producer/consumer node reference fields.
  2. As this is an SPSC we have no need for XCHG, an ordered store is enough.
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

Field Summary

Inherited from rx.internal.util.unsafe.BaseLinkedQueue:
p00p01p02p03p04p05p06p07p30p31p32p33p34p35p36p37

Constructor Summary

AccessConstructor and Description
public
SpscLinkedQueue()

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.unsafe.BaseLinkedQueue:
isEmptyiteratorsize

Constructor Detail

SpscLinkedQueueback to summary
public SpscLinkedQueue()

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 a SINGLE thread.
Offer allocates a new node (holding the offered value) and:

  1. Sets that node as the producerNode.next
  2. Sets the new node as the producerNode
From this follows that producerNode.next is always null and for all other nodes node.next is not null.
Parameters
nextValue:E

the element to add

Returns:boolean

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

Annotations
@Override
See Also
MessagePassingQueue#offer(Object), 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 empty.
  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