com.bigdata.cache
Class RingBuffer<T>

java.lang.Object
  com.bigdata.cache.RingBuffer<T>

Type Parameters:

T - The reference type stored in the buffer.

All Implemented Interfaces:

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

Direct Known Subclasses:

HardReferenceQueue

public class RingBuffer<T>
extends Object
implements Queue<T>

A unsynchronized fixed capacity ring buffer. The buffer does not accept null elements. If you want a thread-safe Queue consider ArrayBlockingQueue instead.

Note: The "head" of the ring buffer is the insertion point, NOT the MRU element which is located at the previous "head" index. The "tail" of the ring buffer is the LRU position. Unfortunately, these labels are exactly the reverse of the labels used to describe the Queue semantics.

Version:

$Id: RingBuffer.java 2265 2009-10-26 12:51:06Z thompsonbry $

Author:

Bryan Thompson

Field Summary

protected int	capacity The capacity of the buffer.
protected int	size The #of elements in the buffer.

Constructor Summary

RingBuffer(int capacity)
Ctor.

Method Summary

boolean	add(T ref)
boolean	addAll(Collection<? extends T> c)
protected void	beforeOffer(T ref) All attempts to add an element to the buffer invoke this hook before checking the remaining capacity in the buffer.
int	capacity() The capacity of the buffer as specified to the constructor.
void	clear() Clears the buffer, setting the references in the buffer to null.
void	clear(boolean clearRefs) Clears the buffer (sets the index of the head and the tail to zero and sets the count to zero).
boolean	contains(Object ref)
boolean	containsAll(Collection<?> c)
T	element()
T	get(int index) Return the nth element in the buffer.
boolean	isEmpty()
boolean	isFull() True iff the buffer is full.
Iterator<T>	iterator() Return an iterator over the buffer visiting elements in LRU to MRU order (the order in which those elements would be read by poll()).
boolean	offer(T ref)
T	peek() Note: This is the reference at the "tail" of the RingBuffer (the LRU position).
T	poll()
T	remove()
boolean	remove(Object ref)
boolean	removeAll(Collection<?> c)
boolean	retainAll(Collection<?> c)
boolean	scanHead(int nscan, T ref) Scan the last nscan references for this reference.
boolean	scanTail(int nscan, T ref) Return true iff the reference is found in the first N positions scanning backwards from the tail of the queue.
int	size()
Object[]	toArray() Return the buffer elements in MRU (head) to LRU (tail) order.
<TX> TX[]	toArray(TX[] a) Return the buffer elements in MRU (head) to LRU (tail) order.

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

Field Detail

capacity

protected final int capacity

The capacity of the buffer.

size

protected int size

The #of elements in the buffer. The buffer is empty when this field is zero. The buffer is full when this field equals the capacity.

Note: Exposed to HardReferenceQueue as an optimization for isFull().

Constructor Detail

RingBuffer

public RingBuffer(int capacity)

Ctor.

Parameters:

capacity - The capacity of the buffer.

Method Detail

capacity

public final int capacity()

The capacity of the buffer as specified to the constructor.

size

public final int size()

Specified by:

size in interface Collection<T>

isEmpty

public final boolean isEmpty()

Specified by:

isEmpty in interface Collection<T>

isFull

public final boolean isFull()

True iff the buffer is full.

add

public boolean add(T ref)
            throws IllegalStateException

Specified by:

add in interface Collection<T>

Specified by:

add in interface Queue<T>

Throws:

IllegalStateException

offer

public boolean offer(T ref)

Specified by:

offer in interface Queue<T>

beforeOffer

protected void beforeOffer(T ref)

All attempts to add an element to the buffer invoke this hook before checking the remaining capacity in the buffer.

This hook provides an opportunity to realize an eviction protocol and is used for that purpose by HardReferenceQueue. It is also used to realize the the stale reference protocol in SynchronizedHardReferenceQueueWithTimeout.

TODO:

it can be used to realize the chunk combiner on add protocol as well.

addAll

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

Specified by:

addAll in interface Collection<T>

clear

public void clear()

Clears the buffer, setting the references in the buffer to null.

Specified by:

clear in interface Collection<T>

clear

public final void clear(boolean clearRefs)

Clears the buffer (sets the index of the head and the tail to zero and sets the count to zero).

Parameters:

clearRefs - When true the references are explicitly set to null which can facilitate garbage collection.

toArray

public Object[] toArray()

Return the buffer elements in MRU (head) to LRU (tail) order.

Specified by:

toArray in interface Collection<T>

toArray

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

Return the buffer elements in MRU (head) to LRU (tail) order.

Specified by:

toArray in interface Collection<T>

get

public final T get(int index)

Return the nth element in the buffer. The index positions are counted from the MRU (the insertion point), which has an index of ZERO (0), to the LRU position (the eviction point), which as an index of size()-1.

Parameters:

index - The index of the desired element.

Returns:

The element at that index.

Throws:

IllegalArgumentException - if the index is less than ZERO (0).

IllegalArgumentException - if the index is greater than or equal to the size().

element

public final T element()
                throws NoSuchElementException

Specified by:

element in interface Queue<T>

Throws:

NoSuchElementException

peek

public final T peek()

Note: This is the reference at the "tail" of the RingBuffer (the LRU position).

Specified by:

peek in interface Queue<T>

poll

public final T poll()

Specified by:

poll in interface Queue<T>

scanHead

public final boolean scanHead(int nscan,
                              T ref)

Scan the last nscan references for this reference. If found, return immediately.

Parameters:

nscan - The #of positions to scan, starting with the most recently added reference.

ref - The reference for which we are scanning.

Returns:

True iff we found ref in the scanned queue positions.

scanTail

public final boolean scanTail(int nscan,
                              T ref)

Return true iff the reference is found in the first N positions scanning backwards from the tail of the queue.

Parameters:

nscan - The #of positions to be scanned. When one (1) only the tail of the queue is scanned.

ref - The reference to scan for.

Returns:

True iff the reference is found in the last N queue positions counting backwards from the tail.

TODO:

Write unit tests for this method.

remove

public T remove()
         throws NoSuchElementException

Specified by:

remove in interface Queue<T>

Throws:

NoSuchElementException

contains

public boolean contains(Object ref)

Specified by:

contains in interface Collection<T>

containsAll

public boolean containsAll(Collection<?> c)

Specified by:

containsAll in interface Collection<T>

iterator

public Iterator<T> iterator()

Return an iterator over the buffer visiting elements in LRU to MRU order (the order in which those elements would be read by poll()). The iterator supports Iterator.remove(). The iterator is NOT thread-safe.

Specified by:

iterator in interface Iterable<T>

Specified by:

iterator in interface Collection<T>

remove

public boolean remove(Object ref)

Specified by:

remove 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>