How can I atomically "enqueue if free space OR dequeue then enqueue" for a Java queue / list?

Question

I've got a requirement for a list in Java with a fixed capacity but which always allows threads to add items to the start. If it's full it should remove an item from the end to make space. No other process will remove items, but other processes will wish to iterate over the items.

Is there something in the JDK which would allow me to do this atomically?

My current plan is just to use some existing threadsafe Collection (e.g. LinkedBlockingQueue) and further synchronise on it when I check capacity / add / remove. Would that work as well?

Thanks.

Answer 1

I'm working in an old version of Java (yes 1.3, I have no choice), so even if it's there in later Javas I can't use it. So I coded along these lines:

public class Fifo  {
 private LinkedList fifoContents = new LinkedList();
 public synchronized void  put(Object element) {
     if ( fifoContents.size() > 100){       
          fifoContents.removeFirst();        
          logger.logWarning("*** Backlog, discarding messaage ");
     }
     fifoContents.add (element);
     return;
 }

 public synchronized Object get() throws NoSuchElementException {
     return fifoContents.removeFirst();
 }
}

Answer 2

Your idea would work but would involve taking out multiple locks (see example below). Given you need to synchronize multiple operations when adding data you may as well wrap a LinkedList implementation of a Queue to avoid the overhead of additional locks.

// Create queue with fixed capacity.
Queue<Item> queue = new LinkedBlockingQueue<Item>(1000);

...

// Attempt to add item to queue, removing items if required.
synchronized(queue) { // First lock
  while (!queue.offer(item)) { // Second lock
    queue.take(); // Third lock
  }
}

Answer 3

You may be able to get away with just testing/removing/inserting without additional locks:

class DroppingQueue<E>
extends ArrayBlockingQueue<E> {
    public boolean add(E item) {
        while (! offer(item)) {
            take();
        }
        return true;
    }
}

Although this method is not synchronized, add and offer still are, so the worst that can happen is that thread #1 will call offer, find the queue to be full, thread #2 will do the same, and both will remove items, temporarily reducing the number of items to less than the maximum, before both threads successfully add their items. This will probably not cause serious problems.

Answer 4

There's no such class in JDK. If you are going to implement such collection, you might want to use array with floating head/tail pointers - since you have fixed size you don't need linked list at all.