Package rx.internal.util.atomic

Class SpscUnboundedAtomicArrayQueue<T>

java.lang.Object

rx.internal.util.atomic.SpscUnboundedAtomicArrayQueue<T>

Type Parameters:

T - the value type held by this queue

All Implemented Interfaces:

Iterable<T>, Collection<T>, Queue<T>

public final class SpscUnboundedAtomicArrayQueue<T>
extends Object
implements Queue<T>

A single-producer single-consumer queue with unbounded capacity.

The implementation uses fixed, power-of-2 arrays to store elements and turns into a linked-list like structure if the production overshoots the consumption.

Note that the minimum capacity of the 'islands' are 8 due to how the look-ahead optimization works.

The implementation uses field updaters and thus should be platform-safe.

Field Summary

Fields

Modifier and Type	Field	Description
(package private) AtomicReferenceArray<Object>	consumerBuffer
(package private) final AtomicLong	consumerIndex
(package private) int	consumerMask
private static final Object	HAS_NEXT
(package private) static final int	MAX_LOOK_AHEAD_STEP
(package private) AtomicReferenceArray<Object>	producerBuffer
(package private) final AtomicLong	producerIndex
(package private) long	producerLookAhead
(package private) int	producerLookAheadStep
(package private) int	producerMask

Constructor Summary

Constructors

Constructor	Description
SpscUnboundedAtomicArrayQueue(int bufferSize)

Method Summary

Modifier and Type	Method	Description
boolean	add(T e)
boolean	addAll(Collection<? extends T> c)
private void	adjustLookAheadStep(int capacity)
private static int	calcDirectOffset(int index)
private static int	calcWrappedOffset(long index, int mask)
void	clear()
boolean	contains(Object o)
boolean	containsAll(Collection<?> c)
T	element()
boolean	isEmpty()
Iterator<T>	iterator()
private long	lpConsumerIndex()
private long	lpProducerIndex()
private long	lvConsumerIndex()
private static <E> Object	lvElement(AtomicReferenceArray<Object> buffer, int offset)
private AtomicReferenceArray<Object>	lvNext(AtomicReferenceArray<Object> curr)
private long	lvProducerIndex()
private T	newBufferPeek(AtomicReferenceArray<Object> nextBuffer, long index, int mask)
private T	newBufferPoll(AtomicReferenceArray<Object> nextBuffer, long index, int mask)
boolean	offer(T e)
T	peek()
T	poll()
T	remove()
boolean	remove(Object o)
boolean	removeAll(Collection<?> c)
private void	resize(AtomicReferenceArray<Object> oldBuffer, long currIndex, int offset, T e, long mask)
boolean	retainAll(Collection<?> c)
int	size()
private void	soConsumerIndex(long v)
private static void	soElement(AtomicReferenceArray<Object> buffer, int offset, Object e)
private void	soNext(AtomicReferenceArray<Object> curr, AtomicReferenceArray<Object> next)
private void	soProducerIndex(long v)
Object[]	toArray()
<E> E[]	toArray(E[] a)
private boolean	writeToQueue(AtomicReferenceArray<Object> buffer, T e, long index, int offset)

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Collection

equals, hashCode, parallelStream, removeIf, spliterator, stream, toArray

Methods inherited from interface java.lang.Iterable

forEach

Field Details

MAX_LOOK_AHEAD_STEP

static final int MAX_LOOK_AHEAD_STEP

producerIndex

final AtomicLong producerIndex

producerLookAheadStep

int producerLookAheadStep

producerLookAhead

long producerLookAhead

producerMask

int producerMask

producerBuffer

AtomicReferenceArray<Object> producerBuffer

consumerMask

int consumerMask

consumerBuffer

AtomicReferenceArray<Object> consumerBuffer

consumerIndex

final AtomicLong consumerIndex

HAS_NEXT

private static final Object HAS_NEXT

Constructor Details

SpscUnboundedAtomicArrayQueue

public SpscUnboundedAtomicArrayQueue(int bufferSize)

Method Details

offer

public boolean offer(T e)

This implementation is correct for single producer thread use only.

Specified by:

offer in interface Queue<T>

writeToQueue

private boolean writeToQueue(AtomicReferenceArray<Object> buffer,
 T e,
 long index,
 int offset)

resize

private void resize(AtomicReferenceArray<Object> oldBuffer,
 long currIndex,
 int offset,
 T e,
 long mask)

soNext

private void soNext(AtomicReferenceArray<Object> curr,
 AtomicReferenceArray<Object> next)

lvNext

private AtomicReferenceArray<Object> lvNext(AtomicReferenceArray<Object> curr)

poll

public T poll()

This implementation is correct for single consumer thread use only.

Specified by:

poll in interface Queue<T>

newBufferPoll

private T newBufferPoll(AtomicReferenceArray<Object> nextBuffer,
 long index,
 int mask)

peek

public T peek()

This implementation is correct for single consumer thread use only.

Specified by:

peek in interface Queue<T>

clear

public void clear()

Specified by:

clear in interface Collection<T>

newBufferPeek

private T newBufferPeek(AtomicReferenceArray<Object> nextBuffer,
 long index,
 int mask)

size

public int size()

Specified by:

size in interface Collection<T>

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface Collection<T>

adjustLookAheadStep

private void adjustLookAheadStep(int capacity)

lvProducerIndex

private long lvProducerIndex()

lvConsumerIndex

private long lvConsumerIndex()

lpProducerIndex

private long lpProducerIndex()

lpConsumerIndex

private long lpConsumerIndex()

soProducerIndex

private void soProducerIndex(long v)

soConsumerIndex

private void soConsumerIndex(long v)

calcWrappedOffset

private static int calcWrappedOffset(long index,
 int mask)

calcDirectOffset

private static int calcDirectOffset(int index)

soElement

private static void soElement(AtomicReferenceArray<Object> buffer,
 int offset,
 Object e)

lvElement

private static <E> Object lvElement(AtomicReferenceArray<Object> buffer,
 int offset)

iterator

public Iterator<T> iterator()

Specified by:

iterator in interface Collection<T>

Specified by:

iterator in interface Iterable<T>

contains

public boolean contains(Object o)

Specified by:

contains in interface Collection<T>

toArray

public Object[] toArray()

Specified by:

toArray in interface Collection<T>

toArray

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

Specified by:

toArray in interface Collection<T>

remove

public boolean remove(Object o)

Specified by:

remove in interface Collection<T>

containsAll

public boolean containsAll(Collection<?> c)

Specified by:

containsAll in interface Collection<T>

addAll

public boolean addAll(Collection<? extends T> c)

Specified by:

addAll in interface Collection<T>

removeAll

public boolean removeAll(Collection<?> c)

Specified by:

removeAll in interface Collection<T>

retainAll

public boolean retainAll(Collection<?> c)

Specified by:

retainAll in interface Collection<T>

add

public boolean add(T e)

Specified by:

add in interface Collection<T>

Specified by:

add in interface Queue<T>

remove

public T remove()

Specified by:

remove in interface Queue<T>

element

public T element()

Specified by:

element in interface Queue<T>