hu.akarnokd.rxjava2.internal.queue

Class MpscLinkedQueue<T>

java.lang.Object

java.util.AbstractCollection<E>

java.util.AbstractQueue<E>

hu.akarnokd.rxjava2.internal.queue.MpscLinkedQueue<T>

Type Parameters:

T - the contained value type

All Implemented Interfaces:

java.lang.Iterable<T>, java.util.Collection<T>, java.util.Queue<T>

public final class MpscLinkedQueue<T>
extends java.util.AbstractQueue<E>

A multi-producer single consumer unbounded queue.

Constructor Summary

Constructors

Constructor and Description
MpscLinkedQueue()

Method Summary

Modifier and Type	Method and Description
boolean	isEmpty() IMPLEMENTATION NOTES: Queue is empty when producerNode is the same as consumerNode.
java.util.Iterator<E>	iterator()
protected LinkedQueueNode<E>	lpConsumerNode()
protected LinkedQueueNode<E>	lpProducerNode()
protected LinkedQueueNode<E>	lvConsumerNode()
protected LinkedQueueNode<E>	lvProducerNode()
boolean	offer(T nextValue) IMPLEMENTATION NOTES: Offer is allowed from multiple threads.
T	peek()
T	poll() IMPLEMENTATION NOTES: Poll is allowed from a SINGLE thread.
int	size() IMPLEMENTATION NOTES: This is an O(n) operation as we run through all the nodes and count them.
protected void	spConsumerNode(LinkedQueueNode<E> node)
protected void	spProducerNode(LinkedQueueNode<E> node)
protected LinkedQueueNode<E>	xchgProducerNode(LinkedQueueNode<E> node)

Methods inherited from class java.util.AbstractQueue

add, addAll, clear, element, remove

Methods inherited from class java.util.AbstractCollection

contains, containsAll, remove, removeAll, retainAll, 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.Collection

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

Methods inherited from interface java.lang.Iterable

forEach

Constructor Detail

MpscLinkedQueue

public MpscLinkedQueue()

Method Detail

offer

public final boolean offer(T nextValue)

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.

See Also:

Queue.offer(java.lang.Object)

poll

public final T poll()

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.

See Also:

Queue.poll()

peek

public final T peek()

lvProducerNode

protected final LinkedQueueNode<E> lvProducerNode()

lpProducerNode

protected final LinkedQueueNode<E> lpProducerNode()

spProducerNode

protected final void spProducerNode(LinkedQueueNode<E> node)

xchgProducerNode

protected final LinkedQueueNode<E> xchgProducerNode(LinkedQueueNode<E> node)

lvConsumerNode

protected final LinkedQueueNode<E> lvConsumerNode()

lpConsumerNode

protected final LinkedQueueNode<E> lpConsumerNode()

spConsumerNode

protected final void spConsumerNode(LinkedQueueNode<E> node)

iterator

public final java.util.Iterator<E> iterator()

Specified by:

iterator in interface java.lang.Iterable<E>

Specified by:

iterator in interface java.util.Collection<E>

Specified by:

iterator in class java.util.AbstractCollection<E>

size

public final int size()

IMPLEMENTATION NOTES:
This is an O(n) operation as we run through all the nodes and count them.

Specified by:

size in interface java.util.Collection<E>

Specified by:

size in class java.util.AbstractCollection<E>

See Also:

Collection.size()

isEmpty

public final boolean isEmpty()

IMPLEMENTATION NOTES:
Queue is empty when producerNode is the same as consumerNode. An alternative implementation would be to observe the producerNode.value is null, which also means an empty queue because only the consumerNode.value is allowed to be null.

Specified by:

isEmpty in interface java.util.Collection<E>

Overrides:

isEmpty in class java.util.AbstractCollection<E>