The high level classes in java.util.concurrent.atomic makes it quite easy to create data structures that are thread safe and low on contention. This is a lock free concurrent circular buffer that I once found the need for:
import java.util.List;
import java.util.Vector;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReferenceArray;
/**
* A lock-free thread safe circular fixed length buffer.
*
* Uses an AtomicInteger as index counter and an AtomicReferenceArray
* to hold the references to the values.
*
* When the buffer is full, the oldest item is overwritten.
*
*/
public class CircularBuffer<T> {
private final AtomicInteger index = new AtomicInteger(-1);
private final AtomicReferenceArray<T> buffer;
private final int size;
public CircularBuffer(int size) {
this.size = size;
buffer = new AtomicReferenceArray<T>(this.size);
}
public void add(T item) {
if (index.compareAndSet(size-1, 0)) {
buffer.set(0, item);
} else {
buffer.set(index.incrementAndGet(), item);
}
}
/**
* Get contents of buffer, as a list.
*
* Note that the list always has the size of the buffer,
* no matter how many elements there actually are.
*
* The ordering is also unpredictable.
*
* @return contents
*/
public List<T> getAll() {
List<T> list = new Vector<T>(size);
for (int i = 0; i < size; i++)
list.add(buffer.get(i));
return list;
}
public T get(int i) {
return buffer.get(i);
}
}