Bounded, auto-discarding, non-blocking, concurrent collection
I made this simple imeplementation:
public class AutoDiscardingDeque<E> extends LinkedBlockingDeque<E> {
public AutoDiscardingDeque() {
super();
}
public AutoDiscardingDeque(int capacity) {
super(capacity);
}
@Override
public synchronized boolean offerFirst(E e) {
if (remainingCapacity() == 0) {
removeLast();
}
super.offerFirst(e);
return true;
}
}
For my needs this suffices, but it should be well-documented methods different than addFirst
/ offerFirst
are still following the semantics of a blocking deque.
I believe what you're looking for is a bounded stack. There isn't a core library class that does this, so I think the best way of doing this is to take a non-synchronized stack (LinkedList) and wrap it in a synchronized collection that does the auto-discard and returning null on empty pop. Something like this:
import java.util.Iterator;
import java.util.LinkedList;
public class BoundedStack<T> implements Iterable<T> {
private final LinkedList<T> ll = new LinkedList<T>();
private final int bound;
public BoundedStack(int bound) {
this.bound = bound;
}
public synchronized void push(T item) {
ll.push(item);
if (ll.size() > bound) {
ll.removeLast();
}
}
public synchronized T pop() {
return ll.poll();
}
public synchronized Iterator<T> iterator() {
return ll.iterator();
}
}
...adding methods like isEmpty as required, if you want it to implement eg List.
The simplest and classic solution is a bounded ring buffer that overrides the oldest elements.
The implementation is rather easy. You need one AtomicInteger/Long for index + AtomicReferenceArray and you have a lock free general purpose stack with 2 methods only offer/poll
, no size()
. Most concurrent/lock-free structures have hardships w/ size(). Non-overriding stack can have O(1) but w/ an allocation on put.
Something along the lines of:
package bestsss.util;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.atomic.AtomicReferenceArray;
public class ConcurrentArrayStack<E> extends AtomicReferenceArray<E>{
//easy to extend and avoid indirections,
//feel free to contain the ConcurrentArrayStack if feel purist
final AtomicLong index = new AtomicLong(-1);
public ConcurrentArrayStack(int length) {
super(length); //returns
}
/**
* @param e the element to offer into the stack
* @return the previously evicted element
*/
public E offer(E e){
for (;;){
long i = index.get();
//get the result, CAS expect before the claim
int idx = idx(i+1);
E result = get(idx);
if (!index.compareAndSet(i, i+1))//claim index spot
continue;
if (compareAndSet(idx, result, e)){
return result;
}
}
}
private int idx(long idx){//can/should use golden ratio to spread the index around and reduce false sharing
return (int)(idx%length());
}
public E poll(){
for (;;){
long i = index.get();
if (i==-1)
return null;
int idx = idx(i);
E result = get(idx);//get before the claim
if (!index.compareAndSet(i, i-1))//claim index spot
continue;
if (compareAndSet(idx, result, null)){
return result;
}
}
}
}
Last note:
having mod operation is an expensive one and power-of-2 capacity is to preferred, via &length()-1
(also guards vs long overflow).