Add/Remove without object allocation (after initial construction).

This is meant for hundreds or single-digit thousands of elements that need to be rapidly added and randomly or sequentially removed while avoiding object allocation.

On Intel Core i7, 2.3Mhz, Mac Java 8:

- adds per second single-threaded => ~32,598,500 for 100 - adds per second single-threaded => ~23,200,000 for 10,000 - adds + removes per second single-threaded => 15,562,100 for 100 - adds + removes per second single-threaded => 8,760,000 for 10,000

 Benchmark                                              (size)   Mode   Samples        Score  Score error    Units
r.i.IndexedRingBufferPerf.indexedRingBufferAdd            100  thrpt         5   263571.721     9856.994    ops/s
r.i.IndexedRingBufferPerf.indexedRingBufferAdd          10000  thrpt         5     1763.417      211.998    ops/s
r.i.IndexedRingBufferPerf.indexedRingBufferAddRemove      100  thrpt         5   139850.115    17143.705    ops/s
r.i.IndexedRingBufferPerf.indexedRingBufferAddRemove    10000  thrpt         5      809.982       72.931    ops/s

Modifier and Type	Class and Description
pack-priv static class	IndexedRingBuffer.ElementSection<E>
pack-priv static class	IndexedRingBuffer.IndexSection

Field Summary

Modifier and Type	Field and Description
private final IndexedRingBuffer.ElementSection<E>	elements
pack-priv final AtomicInteger	index
private final IndexedRingBuffer.IndexSection	removed
pack-priv final AtomicInteger	removedIndex
pack-priv static final int	SIZE

Access	Constructor and Description
pack-priv	IndexedRingBuffer()

Method Summary

Modifier and Type	Method and Description
public int	Returns: the index where the element was added add(E the element to add e) Add an element and return the index where it was added to allow removal.
public int	forEach(Func1<? super E, Boolean> action)
public int	Returns: int of next index to process, or last index seen if it exited early forEach(Func1<? super E, Boolean> that processes each item and returns true if it wants to continue to the next action, int at which index the loop should start startIndex) Loop through each element in the buffer and call a specific function.
private int	forEach(Func1<? super E, Boolean> action, int startIndex, int endIndex)
private IndexedRingBuffer.ElementSection<E>	getElementSection(int index)
private synchronized int	getIndexForAdd()
private synchronized int	Returns: the index or -1 if none getIndexFromPreviouslyRemoved() Returns -1 if nothing, 0 or greater if the index should be used
private IndexedRingBuffer.IndexSection	getIndexSection(int index)
public static <T> IndexedRingBuffer<T>	getInstance()
public boolean	isUnsubscribed() Implements rx.Subscription.isUnsubscribed. Indicates whether this `Subscription` is currently unsubscribed.
private synchronized void	pushRemovedIndex(int elementIndex)
public void	releaseToPool() This resets the arrays, nulls out references and returns it to the pool.
public E	remove(int index)
public void	unsubscribe() Implements rx.Subscription.unsubscribe. Stops the receipt of notifications on the `Subscriber` that was registered when this Subscription was received.

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

elements	back to summary
private final IndexedRingBuffer.ElementSection<E> elements

index	back to summary
pack-priv final AtomicInteger index

removed	back to summary
private final IndexedRingBuffer.IndexSection removed

removedIndex	back to summary
pack-priv final AtomicInteger removedIndex

SIZE	back to summary
pack-priv static final int SIZE

Constructor Detail

IndexedRingBuffer	back to summary
pack-priv IndexedRingBuffer()

Method Detail

add	back to summary
public int add(E e) Add an element and return the index where it was added to allow removal. Parameters e:E the element to add Returns:int the index where the element was added

add

back to summary

public int add(E e)

Add an element and return the index where it was added to allow removal.

Parameters

e:E: the element to add

Returns:int

the index where the element was added

forEach	back to summary
public int forEach(Func1<? super E, Boolean> action)

forEach	back to summary
public int forEach(Func1<? super E, Boolean> action, int startIndex) Loop through each element in the buffer and call a specific function. Parameters action:Func1<? super E, Boolean> that processes each item and returns true if it wants to continue to the next startIndex:int at which index the loop should start Returns:int int of next index to process, or last index seen if it exited early

forEach

back to summary

public int forEach(Func1<? super E, Boolean> action, int startIndex)

Loop through each element in the buffer and call a specific function.

Parameters

action:Func1<? super E, Boolean>: that processes each item and returns true if it wants to continue to the next
startIndex:int: at which index the loop should start

Returns:int

int of next index to process, or last index seen if it exited early

forEach	back to summary
private int forEach(Func1<? super E, Boolean> action, int startIndex, int endIndex)

getElementSection	back to summary
private IndexedRingBuffer.ElementSection<E> getElementSection(int index)

getIndexForAdd	back to summary
private synchronized int getIndexForAdd()

getIndexFromPreviouslyRemoved	back to summary
private synchronized int getIndexFromPreviouslyRemoved() Returns -1 if nothing, 0 or greater if the index should be used Returns:int the index or -1 if none

getIndexFromPreviouslyRemoved

back to summary

private synchronized int getIndexFromPreviouslyRemoved()

Returns -1 if nothing, 0 or greater if the index should be used

Returns:int: the index or -1 if none

getIndexSection	back to summary
private IndexedRingBuffer.IndexSection getIndexSection(int index)

getInstance	back to summary
public static <T> IndexedRingBuffer<T> getInstance()

isUnsubscribed back to summary

isUnsubscribed	back to summary
public boolean isUnsubscribed() Implements rx.Subscription.isUnsubscribed. Doc from rx.Subscription.isUnsubscribed. Indicates whether this `Subscription` is currently unsubscribed. Returns:boolean `true` if this `Subscription` is currently unsubscribed, `false` otherwise Annotations @Override

public boolean isUnsubscribed()

Implements rx.Subscription.isUnsubscribed.

Doc from rx.Subscription.isUnsubscribed.

Indicates whether this Subscription is currently unsubscribed.

Returns:boolean

true if this Subscription is currently unsubscribed, false otherwise

Annotations

@Override

pushRemovedIndex	back to summary
private synchronized void pushRemovedIndex(int elementIndex)

releaseToPool	back to summary
public void releaseToPool() This resets the arrays, nulls out references and returns it to the pool. This extra CPU cost is far smaller than the object allocation cost of not pooling.

remove	back to summary
public E remove(int index)

unsubscribe back to summary

unsubscribe	back to summary
public void unsubscribe() Implements rx.Subscription.unsubscribe. Doc from rx.Subscription.unsubscribe. Stops the receipt of notifications on the `Subscriber` that was registered when this Subscription was received. This allows deregistering an `Subscriber` before it has finished receiving all events (i.e. before onCompleted is called). Annotations @Override

public void unsubscribe()

Implements rx.Subscription.unsubscribe.

Doc from rx.Subscription.unsubscribe.

Stops the receipt of notifications on the Subscriber that was registered when this Subscription was received.

This allows deregistering an Subscriber before it has finished receiving all events (i.e. before onCompleted is called).

Annotations

@Override

rx.internal.util back to summary

pack-priv final Class IndexedRingBuffer.ElementSection<E>

Class Inheritance

extends Object

java.lang.Object
rx.internal.util.IndexedRingBuffer.ElementSection

Field Summary

Modifier and Type	Field and Description
pack-priv final AtomicReferenceArray<E>	array
pack-priv final AtomicReference<IndexedRingBuffer.ElementSection<E>>	next

Constructor Summary

Access	Constructor and Description
pack-priv	ElementSection()

Method Summary

Modifier and Type	Method and Description
pack-priv IndexedRingBuffer.ElementSection<E>	getNext()

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

array	back to summary
pack-priv final AtomicReferenceArray<E> array

next	back to summary
pack-priv final AtomicReference<IndexedRingBuffer.ElementSection<E>> next

Constructor Detail

ElementSection	back to summary
pack-priv ElementSection()

Method Detail

getNext	back to summary
pack-priv IndexedRingBuffer.ElementSection<E> getNext()

rx.internal.util back to summary

pack-priv Class IndexedRingBuffer.IndexSection

Class Inheritance

extends Object

java.lang.Object
rx.internal.util.IndexedRingBuffer.IndexSection

Field Summary

Modifier and Type	Field and Description
private final AtomicReference<IndexedRingBuffer.IndexSection>	_next
private final AtomicIntegerArray	unsafeArray

Constructor Summary

Access	Constructor and Description
pack-priv	IndexSection()

Method Summary

Modifier and Type	Method and Description
public int	getAndSet(int expected, int newValue)
pack-priv IndexedRingBuffer.IndexSection	getNext()
public void	set(int i, int elementIndex)

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

_next	back to summary
private final AtomicReference<IndexedRingBuffer.IndexSection> _next

unsafeArray	back to summary
private final AtomicIntegerArray unsafeArray

Constructor Detail

IndexSection	back to summary
pack-priv IndexSection()

Method Detail

getAndSet	back to summary
public int getAndSet(int expected, int newValue)

getNext	back to summary
pack-priv IndexedRingBuffer.IndexSection getNext()

set	back to summary
public void set(int i, int elementIndex)

public final Class IndexedRingBuffer<E>

Nested and Inner Type Summary

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

pack-priv final Class IndexedRingBuffer.ElementSection<E>

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

pack-priv Class IndexedRingBuffer.IndexSection

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail