hu.akarnokd.rxjava2.internal.queue

Class SpscArrayQueue<E>

java.lang.Object

java.util.concurrent.atomic.AtomicReferenceArray<E>

hu.akarnokd.rxjava2.internal.queue.SpscArrayQueue<E>

Type Parameters:

E -

All Implemented Interfaces:

java.io.Serializable, java.lang.Iterable<E>, java.util.Collection<E>, java.util.Queue<E>

public final class SpscArrayQueue<E>
extends java.util.concurrent.atomic.AtomicReferenceArray<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.

See Also:

Serialized Form

Field Summary

Fields

Modifier and Type	Field and Description
protected int	mask
protected long	producerLookAhead

Constructor Summary

Constructors

Constructor and Description
SpscArrayQueue(int capacity)

Method Summary

Modifier and Type	Method and Description
boolean	add(E e)
boolean	addAll(java.util.Collection<? extends E> c)
protected int	calcElementOffset(long index)
protected int	calcElementOffset(long index, int mask)
void	clear()
boolean	contains(java.lang.Object o)
boolean	containsAll(java.util.Collection<?> c)
E	element()
boolean	isEmpty()
java.util.Iterator<E>	iterator()
protected E	lpElement(java.util.concurrent.atomic.AtomicReferenceArray<E> buffer, int offset)
protected E	lpElement(int offset)
protected E	lvElement(java.util.concurrent.atomic.AtomicReferenceArray<E> buffer, int offset)
protected E	lvElement(int offset)
boolean	offer(E e)
E	peek()
E	poll()
E	remove()
boolean	remove(java.lang.Object o)
boolean	removeAll(java.util.Collection<?> c)
boolean	retainAll(java.util.Collection<?> c)
int	size()
protected void	soElement(java.util.concurrent.atomic.AtomicReferenceArray<E> buffer, int offset, E value)
protected void	soElement(int offset, E value)
protected void	spElement(java.util.concurrent.atomic.AtomicReferenceArray<E> buffer, int offset, E value)
protected void	spElement(int offset, E value)
protected void	svElement(java.util.concurrent.atomic.AtomicReferenceArray<E> buffer, int offset, E value)
java.lang.Object[]	toArray()
<T> T[]	toArray(T[] a)

Methods inherited from class java.util.concurrent.atomic.AtomicReferenceArray

accumulateAndGet, compareAndSet, get, getAndAccumulate, getAndSet, getAndUpdate, lazySet, length, set, toString, updateAndGet, weakCompareAndSet

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Collection

equals, hashCode, parallelStream, removeIf, spliterator, stream

Methods inherited from interface java.lang.Iterable

forEach

Field Detail

producerLookAhead

protected long producerLookAhead

mask

protected final int mask

Constructor Detail

SpscArrayQueue

public SpscArrayQueue(int capacity)

Method Detail

offer

public boolean offer(E e)

poll

public E poll()

peek

public E peek()

isEmpty

public boolean isEmpty()

size

public int size()

iterator

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

Specified by:

iterator in interface java.lang.Iterable<E>

Specified by:

iterator in interface java.util.Collection<E>

clear

public void clear()

Specified by:

clear in interface java.util.Collection<E>

calcElementOffset

protected final int calcElementOffset(long index,
                                      int mask)

calcElementOffset

protected final int calcElementOffset(long index)

lvElement

protected final E lvElement(java.util.concurrent.atomic.AtomicReferenceArray<E> buffer,
                            int offset)

lpElement

protected final E lpElement(java.util.concurrent.atomic.AtomicReferenceArray<E> buffer,
                            int offset)

lpElement

protected final E lpElement(int offset)

spElement

protected final void spElement(java.util.concurrent.atomic.AtomicReferenceArray<E> buffer,
                               int offset,
                               E value)

spElement

protected final void spElement(int offset,
                               E value)

soElement

protected final void soElement(java.util.concurrent.atomic.AtomicReferenceArray<E> buffer,
                               int offset,
                               E value)

soElement

protected final void soElement(int offset,
                               E value)

svElement

protected final void svElement(java.util.concurrent.atomic.AtomicReferenceArray<E> buffer,
                               int offset,
                               E value)

lvElement

protected final E lvElement(int offset)

add

public boolean add(E e)

Specified by:

add in interface java.util.Collection<E>

Specified by:

add in interface java.util.Queue<E>

remove

public E remove()

Specified by:

remove in interface java.util.Queue<E>

element

public E element()

Specified by:

element in interface java.util.Queue<E>

contains

public boolean contains(java.lang.Object o)

Specified by:

contains in interface java.util.Collection<E>

toArray

public java.lang.Object[] toArray()

Specified by:

toArray in interface java.util.Collection<E>

toArray

public <T> T[] toArray(T[] a)

Specified by:

toArray in interface java.util.Collection<E>

remove

public boolean remove(java.lang.Object o)

Specified by:

remove in interface java.util.Collection<E>

containsAll

public boolean containsAll(java.util.Collection<?> c)

Specified by:

containsAll in interface java.util.Collection<E>

addAll

public boolean addAll(java.util.Collection<? extends E> c)

Specified by:

addAll in interface java.util.Collection<E>

removeAll

public boolean removeAll(java.util.Collection<?> c)

Specified by:

removeAll in interface java.util.Collection<E>

retainAll

public boolean retainAll(java.util.Collection<?> c)

Specified by:

retainAll in interface java.util.Collection<E>