Class SpscArrayQueue<E>
- java.lang.Object
-
- java.util.concurrent.atomic.AtomicReferenceArray<E>
-
- io.reactivex.rxjava3.operators.SpscArrayQueue<E>
-
- Type Parameters:
E
- the element type of the queue
- All Implemented Interfaces:
SimplePlainQueue<E>
,SimpleQueue<E>
,java.io.Serializable
public final class SpscArrayQueue<E> extends java.util.concurrent.atomic.AtomicReferenceArray<E> implements SimplePlainQueue<E>
A Single-Producer-Single-Consumer queue backed by a pre-allocated buffer.This implementation is a mashup of the Fast Flow algorithm with an optimization of the offer method taken from the BQueue algorithm (a variation on Fast Flow), and adjusted to comply with Queue.offer semantics with regards to capacity.
For convenience the relevant papers are available in the resources folder:
2010 - Pisa - SPSC Queues on Shared Cache Multi-Core Systems.pdf
2012 - Junchang- BQueue- Efficient and Practical Queuing.pdf
This implementation is wait free.- Since:
- 3.1.1
- See Also:
- Serialized Form
-
-
Field Summary
Fields Modifier and Type Field Description (package private) java.util.concurrent.atomic.AtomicLong
consumerIndex
(package private) int
lookAheadStep
(package private) int
mask
private static java.lang.Integer
MAX_LOOK_AHEAD_STEP
(package private) java.util.concurrent.atomic.AtomicLong
producerIndex
(package private) long
producerLookAhead
private static long
serialVersionUID
-
Constructor Summary
Constructors Constructor Description SpscArrayQueue(int capacity)
Constructs an array-backed queue with the given capacity rounded up to the next power of 2 size.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description (package private) int
calcElementOffset(long index)
(package private) int
calcElementOffset(long index, int mask)
void
clear()
Removes all enqueued items from this queue.boolean
isEmpty()
Returns true if the queue is empty.(package private) E
lvElement(int offset)
boolean
offer(E e)
Atomically enqueue a single value.boolean
offer(E v1, E v2)
Atomically enqueue two values.E
poll()
Tries to dequeue a value (non-null) or returns null if the queue is empty.(package private) void
soConsumerIndex(long newIndex)
(package private) void
soElement(int offset, E value)
(package private) void
soProducerIndex(long newIndex)
-
Methods inherited from class java.util.concurrent.atomic.AtomicReferenceArray
accumulateAndGet, compareAndExchange, compareAndExchangeAcquire, compareAndExchangeRelease, compareAndSet, get, getAcquire, getAndAccumulate, getAndSet, getAndUpdate, getOpaque, getPlain, lazySet, length, set, setOpaque, setPlain, setRelease, toString, updateAndGet, weakCompareAndSet, weakCompareAndSetAcquire, weakCompareAndSetPlain, weakCompareAndSetRelease, weakCompareAndSetVolatile
-
-
-
-
Field Detail
-
serialVersionUID
private static final long serialVersionUID
- See Also:
- Constant Field Values
-
MAX_LOOK_AHEAD_STEP
private static final java.lang.Integer MAX_LOOK_AHEAD_STEP
-
mask
final int mask
-
producerIndex
final java.util.concurrent.atomic.AtomicLong producerIndex
-
producerLookAhead
long producerLookAhead
-
consumerIndex
final java.util.concurrent.atomic.AtomicLong consumerIndex
-
lookAheadStep
final int lookAheadStep
-
-
Method Detail
-
offer
public boolean offer(E e)
Description copied from interface:SimpleQueue
Atomically enqueue a single value.- Specified by:
offer
in interfaceSimpleQueue<E>
- Parameters:
e
- the value to enqueue, not null- Returns:
- true if successful, false if the value was not enqueued likely due to reaching the queue capacity)
-
offer
public boolean offer(E v1, E v2)
Description copied from interface:SimpleQueue
Atomically enqueue two values.- Specified by:
offer
in interfaceSimpleQueue<E>
- Parameters:
v1
- the first value to enqueue, not nullv2
- the second value to enqueue, not null- Returns:
- true if successful, false if the value was not enqueued likely due to reaching the queue capacity)
-
poll
@Nullable public E poll()
Description copied from interface:SimpleQueue
Tries to dequeue a value (non-null) or returns null if the queue is empty.If the producer uses
SimpleQueue.offer(Object, Object)
and when polling in pairs, if the first poll() returns a non-null item, the second poll() is guaranteed to return a non-null item as well.- Specified by:
poll
in interfaceSimplePlainQueue<E>
- Specified by:
poll
in interfaceSimpleQueue<E>
- Returns:
- the item or null to indicate an empty queue
-
isEmpty
public boolean isEmpty()
Description copied from interface:SimpleQueue
Returns true if the queue is empty.Note however that due to potential fused functions in
SimpleQueue.poll()
it is possible this method returns false but then poll() returns null because the fused function swallowed the available item(s).- Specified by:
isEmpty
in interfaceSimpleQueue<E>
- Returns:
- true if the queue is empty
-
soProducerIndex
void soProducerIndex(long newIndex)
-
soConsumerIndex
void soConsumerIndex(long newIndex)
-
clear
public void clear()
Description copied from interface:SimpleQueue
Removes all enqueued items from this queue.- Specified by:
clear
in interfaceSimpleQueue<E>
-
calcElementOffset
int calcElementOffset(long index, int mask)
-
calcElementOffset
int calcElementOffset(long index)
-
soElement
void soElement(int offset, E value)
-
lvElement
E lvElement(int offset)
-
-