Top Description Fields Constructors Methods
rx.internal.util.atomic

public final Class SpscUnboundedAtomicArrayQueue<T>

extends Object
implements Queue<T>
Class Inheritance
All Implemented Interfaces
java.util.Queue, java.util.Collection, java.lang.Iterable
Type Parameters
<T>
the value type held by this queue
Imports
java.util.*, java.util.concurrent.atomic.*, rx.internal.util.unsafe.Pow2
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

Modifier and TypeField and Description
pack-priv AtomicReferenceArray<Object>
consumerBuffer

pack-priv final AtomicLong
consumerIndex

pack-priv int
consumerMask

private static final Object
HAS_NEXT

pack-priv static final int
MAX_LOOK_AHEAD_STEP

pack-priv AtomicReferenceArray<Object>
producerBuffer

pack-priv final AtomicLong
producerIndex

pack-priv long
producerLookAhead

pack-priv int
producerLookAheadStep

pack-priv int
producerMask

Constructor Summary

AccessConstructor and Description
public
SpscUnboundedAtomicArrayQueue(final int bufferSize)

Method Summary

Modifier and TypeMethod and Description
public boolean
add(T
the element to add
e)

Implements java.util.Queue.add.

Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.
public boolean
addAll(Collection<? extends T>
collection containing elements to be added to this collection
c)

Implements java.util.Collection.addAll.

Adds all of the elements in the specified collection to this collection (optional operation).
private void
adjustLookAheadStep(int capacity)

private static int
calcDirectOffset(int index)

private static int
calcWrappedOffset(long index, int mask)

public void
clear()

Implements java.util.Collection.clear.

Removes all of the elements from this collection (optional operation).
public boolean
contains(Object
element whose presence in this collection is to be tested
o)

Implements java.util.Collection.contains.

Returns true if this collection contains the specified element.
public boolean
containsAll(Collection<?>
collection to be checked for containment in this collection
c)

Implements java.util.Collection.containsAll.

Returns true if this collection contains all of the elements in the specified collection.
public T
element()

Implements java.util.Queue.element.

Retrieves, but does not remove, the head of this queue.
public boolean
isEmpty()

Implements java.util.Collection.isEmpty.

Returns true if this collection contains no elements.
public Iterator<T>
iterator()

Implements java.util.Collection.iterator.

Returns an iterator over the elements in this collection.
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, final long index, final int mask)

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

public boolean
offer(final T
the element to add
e)

Implements java.util.Queue.offer.

Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions.
public T
peek()

Implements java.util.Queue.peek.

Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
public T
poll()

Implements java.util.Queue.poll.

Retrieves and removes the head of this queue, or returns null if this queue is empty.
public boolean
remove(Object
element to be removed from this collection, if present
o)

Implements java.util.Collection.remove.

Removes a single instance of the specified element from this collection, if it is present (optional operation).
public T
remove()

Implements java.util.Queue.remove.

Retrieves and removes the head of this queue.
public boolean
removeAll(Collection<?>
collection containing elements to be removed from this collection
c)

Implements java.util.Collection.removeAll.

Removes all of this collection's elements that are also contained in the specified collection (optional operation).
private void
resize(final AtomicReferenceArray<Object> oldBuffer, final long currIndex, final int offset, final T e, final long mask)

public boolean
retainAll(Collection<?>
collection containing elements to be retained in this collection
c)

Implements java.util.Collection.retainAll.

Retains only the elements in this collection that are contained in the specified collection (optional operation).
public int
size()

Implements java.util.Collection.size.

Returns the number of elements in this collection.
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)

public Object[]
toArray()

Implements java.util.Collection.toArray.

Returns an array containing all of the elements in this collection.
public <E> E[]
toArray(E[]
the array into which the elements of this collection are to be stored, if it is big enough; otherwise, a new array of the same runtime type is allocated for this purpose.
a)

Implements java.util.Collection.toArray.

Returns an array containing all of the elements in this collection; the runtime type of the returned array is that of the specified array.
private boolean
writeToQueue(final AtomicReferenceArray<Object> buffer, final T e, final long index, final int offset)

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

consumerBufferback to summary
pack-priv AtomicReferenceArray<Object> consumerBuffer
consumerIndexback to summary
pack-priv final AtomicLong consumerIndex
consumerMaskback to summary
pack-priv int consumerMask
HAS_NEXTback to summary
private static final Object HAS_NEXT
MAX_LOOK_AHEAD_STEPback to summary
pack-priv static final int MAX_LOOK_AHEAD_STEP
producerBufferback to summary
pack-priv AtomicReferenceArray<Object> producerBuffer
producerIndexback to summary
pack-priv final AtomicLong producerIndex
producerLookAheadback to summary
pack-priv long producerLookAhead
producerLookAheadStepback to summary
pack-priv int producerLookAheadStep
producerMaskback to summary
pack-priv int producerMask

Constructor Detail

SpscUnboundedAtomicArrayQueueback to summary
public SpscUnboundedAtomicArrayQueue(final int bufferSize)

Method Detail

addback to summary
public boolean add(T e)

Implements java.util.Queue.add.

Doc from java.util.Queue.add.

Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.

Parameters
e:T

the element to add

Returns:boolean

true (as specified by Collection#add)

Annotations
@Override
addAllback to summary
public boolean addAll(Collection<? extends T> c)

Implements java.util.Collection.addAll.

Doc from java.util.Collection.addAll.

Adds all of the elements in the specified collection to this collection (optional operation). The behavior of this operation is undefined if the specified collection is modified while the operation is in progress. (This implies that the behavior of this call is undefined if the specified collection is this collection, and this collection is nonempty.) If the specified collection has a defined encounter order, processing of its elements generally occurs in that order.

Parameters
c:Collection<? extends T>

collection containing elements to be added to this collection

Returns:boolean

true if this collection changed as a result of the call

Annotations
@Override
adjustLookAheadStepback to summary
private void adjustLookAheadStep(int capacity)
calcDirectOffsetback to summary
private static int calcDirectOffset(int index)
calcWrappedOffsetback to summary
private static int calcWrappedOffset(long index, int mask)
clearback to summary
public void clear()

Implements java.util.Collection.clear.

Doc from java.util.Collection.clear.

Removes all of the elements from this collection (optional operation). The collection will be empty after this method returns.

Annotations
@Override
containsback to summary
public boolean contains(Object o)

Implements java.util.Collection.contains.

Doc from java.util.Collection.contains.

Returns true if this collection contains the specified element. More formally, returns true if and only if this collection contains at least one element e such that Objects.equals(o, e).

Parameters
o:Object

element whose presence in this collection is to be tested

Returns:boolean

true if this collection contains the specified element

Annotations
@Override
containsAllback to summary
public boolean containsAll(Collection<?> c)

Implements java.util.Collection.containsAll.

Doc from java.util.Collection.containsAll.

Returns true if this collection contains all of the elements in the specified collection.

Parameters
c:Collection<?>

collection to be checked for containment in this collection

Returns:boolean

true if this collection contains all of the elements in the specified collection

Annotations
@Override
elementback to summary
public T element()

Implements java.util.Queue.element.

Doc from java.util.Queue.element.

Retrieves, but does not remove, the head of this queue. This method differs from peek only in that it throws an exception if this queue is empty.

Returns:T

the head of this queue

Annotations
@Override
isEmptyback to summary
public boolean isEmpty()

Implements java.util.Collection.isEmpty.

Doc from java.util.Collection.isEmpty.

Returns true if this collection contains no elements.

Returns:boolean

true if this collection contains no elements

Annotations
@Override
iteratorback to summary
public Iterator<T> iterator()

Implements java.util.Collection.iterator.

Doc from java.util.Collection.iterator.

Returns an iterator over the elements in this collection. There are no guarantees concerning the order in which the elements are returned (unless this collection is an instance of some class that provides a guarantee).

Returns:Iterator<T>

an Iterator over the elements in this collection

Annotations
@Override
lpConsumerIndexback to summary
private long lpConsumerIndex()
lpProducerIndexback to summary
private long lpProducerIndex()
lvConsumerIndexback to summary
private long lvConsumerIndex()
lvElementback to summary
private static <E> Object lvElement(AtomicReferenceArray<Object> buffer, int offset)
lvNextback to summary
private AtomicReferenceArray<Object> lvNext(AtomicReferenceArray<Object> curr)
Annotations
@SuppressWarnings:unchecked
lvProducerIndexback to summary
private long lvProducerIndex()
newBufferPeekback to summary
private T newBufferPeek(AtomicReferenceArray<Object> nextBuffer, final long index, final int mask)
Annotations
@SuppressWarnings:unchecked
newBufferPollback to summary
private T newBufferPoll(AtomicReferenceArray<Object> nextBuffer, final long index, final int mask)
Annotations
@SuppressWarnings:unchecked
offerback to summary
public boolean offer(final T e)

Implements java.util.Queue.offer.

Doc from java.util.Queue.offer.

Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions. When using a capacity-restricted queue, this method is generally preferable to add, which can fail to insert an element only by throwing an exception.

This implementation is correct for single producer thread use only.

Parameters
e:T

the element to add

Returns:boolean

true if the element was added to this queue, else false

Annotations
@Override
peekback to summary
public T peek()

Implements java.util.Queue.peek.

Doc from java.util.Queue.peek.

Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.

This implementation is correct for single consumer thread use only.

Returns:T

the head of this queue, or null if this queue is empty

Annotations
@SuppressWarnings:unchecked
@Override
pollback to summary
public T poll()

Implements java.util.Queue.poll.

Doc from java.util.Queue.poll.

Retrieves and removes the head of this queue, or returns null if this queue is empty.

This implementation is correct for single consumer thread use only.

Returns:T

the head of this queue, or null if this queue is empty

Annotations
@SuppressWarnings:unchecked
@Override
removeback to summary
public boolean remove(Object o)

Implements java.util.Collection.remove.

Doc from java.util.Collection.remove.

Removes a single instance of the specified element from this collection, if it is present (optional operation). More formally, removes an element e such that Objects.equals(o, e), if this collection contains one or more such elements. Returns true if this collection contained the specified element (or equivalently, if this collection changed as a result of the call).

Parameters
o:Object

element to be removed from this collection, if present

Returns:boolean

true if an element was removed as a result of this call

Annotations
@Override
removeback to summary
public T remove()

Implements java.util.Queue.remove.

Doc from java.util.Queue.remove.

Retrieves and removes the head of this queue. This method differs from poll() only in that it throws an exception if this queue is empty.

Returns:T

the head of this queue

Annotations
@Override
removeAllback to summary
public boolean removeAll(Collection<?> c)

Implements java.util.Collection.removeAll.

Doc from java.util.Collection.removeAll.

Removes all of this collection's elements that are also contained in the specified collection (optional operation). After this call returns, this collection will contain no elements in common with the specified collection.

Parameters
c:Collection<?>

collection containing elements to be removed from this collection

Returns:boolean

true if this collection changed as a result of the call

Annotations
@Override
resizeback to summary
private void resize(final AtomicReferenceArray<Object> oldBuffer, final long currIndex, final int offset, final T e, final long mask)
retainAllback to summary
public boolean retainAll(Collection<?> c)

Implements java.util.Collection.retainAll.

Doc from java.util.Collection.retainAll.

Retains only the elements in this collection that are contained in the specified collection (optional operation). In other words, removes from this collection all of its elements that are not contained in the specified collection.

Parameters
c:Collection<?>

collection containing elements to be retained in this collection

Returns:boolean

true if this collection changed as a result of the call

Annotations
@Override
sizeback to summary
public int size()

Implements java.util.Collection.size.

Doc from java.util.Collection.size.

Returns the number of elements in this collection. If this collection contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.

Returns:int

the number of elements in this collection

Annotations
@Override
soConsumerIndexback to summary
private void soConsumerIndex(long v)
soElementback to summary
private static void soElement(AtomicReferenceArray<Object> buffer, int offset, Object e)
soNextback to summary
private void soNext(AtomicReferenceArray<Object> curr, AtomicReferenceArray<Object> next)
soProducerIndexback to summary
private void soProducerIndex(long v)
toArrayback to summary
public Object[] toArray()

Implements java.util.Collection.toArray.

Doc from java.util.Collection.toArray.

Returns an array containing all of the elements in this collection. If this collection makes any guarantees as to what order its elements are returned by its iterator, this method must return the elements in the same order. The returned array's runtime component type is Object.

The returned array will be "safe" in that no references to it are maintained by this collection. (In other words, this method must allocate a new array even if this collection is backed by an array). The caller is thus free to modify the returned array.

Returns:Object[]

an array, whose runtime component type is Object, containing all of the elements in this collection

Annotations
@Override
toArrayback to summary
public <E> E[] toArray(E[] a)

Implements java.util.Collection.toArray.

Doc from java.util.Collection.toArray.

Returns an array containing all of the elements in this collection; the runtime type of the returned array is that of the specified array. If the collection fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this collection.

If this collection fits in the specified array with room to spare (i.e., the array has more elements than this collection), the element in the array immediately following the end of the collection is set to null. (This is useful in determining the length of this collection only if the caller knows that this collection does not contain any null elements.)

If this collection makes any guarantees as to what order its elements are returned by its iterator, this method must return the elements in the same order.

Parameters
<E>
the component type of the array to contain the collection
a:E[]

the array into which the elements of this collection are to be stored, if it is big enough; otherwise, a new array of the same runtime type is allocated for this purpose.

Returns:E[]

an array containing all of the elements in this collection

Annotations
@Override
writeToQueueback to summary
private boolean writeToQueue(final AtomicReferenceArray<Object> buffer, final T e, final long index, final int offset)