Lockfree quasi-queue of integers.

IntFreeList.java

package com.nyeggen.strintmap;

import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;

/** Lockfree quasi-queue of integers.  Conceptually there is a queue of integers
 *  at the head, followed by a stream of integers from n to Integer.MAX_VALUE.
 *  add() places at the end of the queue; get() retrieves first from the queue,
 *  and then from the increasing stream.  The stream is implemented with an
 *  AtomicInteger; continuing beyond Integer.MAX_VALUE will cycle back down to
 *  Integer.MIN_VALUE, wrapping as primitive addition.
 *  
 *  IntFreeList a = new IntFreeList()
 *  
 *  a.get()  -> 0
 *  a.get()  -> 1
 *  a.add(7) -> true
 *  a.add(3) -> true
 *  a.get()  -> 7
 *  a.get()  -> 3
 *  a.get()  -> 2 */
public class IntFreeList {
	private static class IntNode {
		private volatile int item;
		private volatile IntNode next;

		private static final AtomicReferenceFieldUpdater<IntNode, IntNode> nextUpdater =
			AtomicReferenceFieldUpdater.newUpdater(IntNode.class, IntNode.class, "next");

		IntNode(int x, IntNode n) { item = x; next = n; }
		int getItem() { return item; }
		void setItem(int val) { item = val; }
		IntNode getNext() { return next; }
		boolean casNext(IntNode cmp, IntNode val) {
			return nextUpdater.compareAndSet(this, cmp, val);
		}
	}

	private static final AtomicReferenceFieldUpdater<IntFreeList, IntNode> tailUpdater =
			AtomicReferenceFieldUpdater.newUpdater(IntFreeList.class, IntNode.class, "tail");
	private static final AtomicReferenceFieldUpdater<IntFreeList, IntNode> headUpdater =
			AtomicReferenceFieldUpdater.newUpdater(IntFreeList.class, IntNode.class, "head");
	public static final int INVALID = Integer.MIN_VALUE;

	private volatile IntNode head = new IntNode(INVALID, null);
	private volatile IntNode tail = head;
	private final AtomicInteger counter;

	public IntFreeList(){
		this(0);
	}
	public IntFreeList(int n){
		this.counter = new AtomicInteger(n);
	}

	private boolean casTail(IntNode cmp, IntNode val) {
		return tailUpdater.compareAndSet(this, cmp, val);
	}

	private boolean casHead(IntNode cmp, IntNode val) {
		return headUpdater.compareAndSet(this, cmp, val);
	}

	public boolean add(int e) {
		IntNode n = new IntNode(e, null);
		for (;;) {
			IntNode t = tail;
			IntNode s = t.getNext();
			if (t == tail) {
				if (s == null) {
					if (t.casNext(s, n)) {
						casTail(t, n);
						return true;
					}
				} else {
					casTail(t, s);
				}
			}
		}
	}

	public int get() {
		for (;;) {
			IntNode h = head;
			IntNode t = tail;
			IntNode first = h.getNext();
			if (h == head) {
				if (h == t) {
					if (first == null) return counter.getAndIncrement();
					else casTail(t, first);
				} else if (casHead(h, first)) {
					int item = first.getItem();
					if (item != INVALID) {
						first.setItem(INVALID);
						return item;
					}
				}
			}
		}
	}
}