Ограниченный, автоматический сброс, неблокирующий, одновременный сбор

Question

Я ищу коллекцию, которая:

• - это Deque / List - т.е. поддерживает вставку элементов «сверху» (самые новые элементы идут вверх) - deque.addFirst(..) / list.add(0, ..). Это может быть Queue, но порядок итераций должен быть обратным - то есть последние добавленные элементы должны стоять на первом месте.
• ограничен - то есть имеет ограничение в 20 пунктов
• автоматически удаляет самые старые элементы (те, что «внизу», добавляются первыми) при достижении емкости
• неблокирование - если очередь пуста, поиск не должен блокироваться. Он также не должен блокировать / возвращать false / null / throw исключение, если очередь заполнена.
• одновременный - несколько потоков должны иметь возможность работать с ним

Я могу взять LinkedBlockingDeque и обернуть его в свою собственную коллекцию, которая при операциях add проверяет размер и отбрасывает последний элемент (ы). Есть ли лучший вариант?

Answer 1

Я сделал эту простую реализацию:

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;
    }
}

Для моих нужд этого достаточно, но это должны быть хорошо документированные методы, отличные от addFirst / offerFirst, которые все еще следуют семантике блокирующей очереди.

Answer 2

Я считаю, что вы ищете ограниченный стек. Не существует базового библиотечного класса, который делает это, поэтому я думаю, что лучший способ сделать это - взять несинхронизированный стек (LinkedList) и обернуть его в синхронизированную коллекцию, которая выполняет автоматический сброс и возвращает ноль при пустом население Примерно так:

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();
    }
}

... добавление методов, таких как isEmpty, если требуется, например, для реализации List.

Answer 3

Самым простым и классическим решением является ограниченный кольцевой буфер, который переопределяет самые старые элементы.

Реализация довольно проста.Вам нужен один AtomicInteger / Long для index + AtomicReferenceArray, и у вас есть свободный от блокировки стек общего назначения только с 2 методами offer/poll, без size().Большинство параллельных / не блокируемых структур имеют трудности с размером ().Не перекрывающий стек может иметь O (1), но с распределением на путе.

Что-то вроде:

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;
            }
        }
    }
}

Последнее примечание: работа с модом стоит дорогомощность в 2 является предпочтительной, через &length()-1 (также защищает от длительного переполнения).

Answer 4

Вот реализация, которая обрабатывает параллелизм и никогда не возвращает Null.

import com.google.common.base.Optional;

import java.util.Deque;
import java.util.concurrent.ConcurrentLinkedDeque;
import java.util.concurrent.locks.ReentrantLock;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;

public class BoundedStack<T> {
   private final Deque<T> list = new ConcurrentLinkedDeque<>();
   private final int maxEntries;
   private final ReentrantLock lock = new ReentrantLock();

   public BoundedStack(final int maxEntries) {
      checkArgument(maxEntries > 0, "maxEntries must be greater than zero");
      this.maxEntries = maxEntries;
   }

   public void push(final T item) {
      checkNotNull(item, "item must not be null");

      lock.lock();
      try {
         list.push(item);
         if (list.size() > maxEntries) { 
            list.removeLast();
         }
      } finally {
         lock.unlock();
      }
   } 

   public Optional<T> pop() {
      return Optional.fromNullable(list.poll());
   }

   public Optional<T> peek() {
      return Optional.fromNullable(list.peekFirst());
   }

   public boolean empty() {
      return list.isEmpty();
   }
}