Package io.reactivex.rxjava3.operators

Class 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

    • 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

      • Methods inherited from class java.lang.Object

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

    • Field Detail

      • 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

    • Constructor Detail

      • SpscArrayQueue

        public SpscArrayQueue​(int capacity)
        Constructs an array-backed queue with the given capacity rounded up to the next power of 2 size.
        Parameters:
        capacity - the maximum number of elements the queue would hold, rounded up to the next power of 2

    • Method Detail

      • offer

        public boolean offer​(E e)
        Description copied from interface: SimpleQueue
        Atomically enqueue a single value.
        Specified by:
        offer in interface SimpleQueue<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 interface SimpleQueue<E>
        Parameters:
        v1 - the first value to enqueue, not null
        v2 - 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 interface SimplePlainQueue<E>
        Specified by:
        poll in interface SimpleQueue<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 interface SimpleQueue<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 interface SimpleQueue<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)