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).