import java.util.concurrent.atomic.AtomicReference;

public class AtomicReferenceTest {

	private static final class StackEntry { 
		volatile Thread owner; 

		volatile StackEntry next; 
	} 

	private static final AtomicReference<StackEntry> stack = new AtomicReference<StackEntry>(); 

	private static class MyThread extends Thread { 
		@Override 
		public void run() { 
			while (true) { 

				/* 
				 * Pop an entry off the top of the stack. The only way to exit 
				 * this loop is to have found an empty stack, or to have 
				 * ATOMICALLY replaced the head of the stack with the next item 
				 * on the stack. In theory, no two threads should be able to 
				 * exit this loop with the SAME entry... 
				 */ 
				StackEntry entry; 
				while (true) { 
					entry = stack.get(); 
					if (entry == null) 
						break; 

					// Atomic, right? Only one thread can succeed... 
					if (stack.compareAndSet(entry, entry.next)) 
						break; 
				} 

				/* 
				 * If there was nothing on the stack, make a new entry. 
				 * Otherwise, just set the 'next' to null. This isn't required 
				 * but is good practice. 
				 */ 
				if (entry == null) 
					entry = new StackEntry(); 
				else 
					entry.next = null; 

				/* 
				 * Check if the entry really was exclusively claimed. In theory, 
				 * no two threads should ever have a reference to the same 
				 * entry... 
				 */ 
				Thread owner = entry.owner; 
				if (owner != null) 
					System.err.println("ALREADY CLAIMED BY " + owner); 
				entry.owner = Thread.currentThread(); 

				/* Push the entry back on to the queue. */ 
				entry.owner = null; 
				while (true) { 
					entry.next = stack.get(); 

					// Atomic, right? Only one thread can succeed... 
					if (stack.compareAndSet(entry.next, entry)) 
						break; 
				} 
			} 
		} 
	}; 

	public static void main(String[] args) { 
		Thread[] threads = new Thread[8]; 
		for (int i = 0; i < threads.length; i++) 
			threads[i] = new MyThread(); 
		for (int i = 0; i < threads.length; i++) 
			threads[i].start(); 
	} 
}