package net.jcip.examples;
import java.util.concurrent.atomic.*;
import net.jcip.annotations.*;
/**
* LinkedQueue
*
* Insertion in the Michael-Scott nonblocking queue algorithm
*
* @author Brian Goetz and Tim Peierls
*/
@ThreadSafe
public class LinkedQueue {
private static class Node {
final E item;
final AtomicReference> next;
public Node(E item, LinkedQueue.Node next) {
this.item = item;
this.next = new AtomicReference>(next);
}
}
private final LinkedQueue.Node dummy = new LinkedQueue.Node(null, null);
private final AtomicReference> head
= new AtomicReference>(dummy);
private final AtomicReference> tail
= new AtomicReference>(dummy);
public boolean put(E item) {
LinkedQueue.Node newNode = new LinkedQueue.Node(item, null);
while (true) {
LinkedQueue.Node curTail = tail.get();
LinkedQueue.Node tailNext = curTail.next.get();
if (curTail == tail.get()) {
if (tailNext != null) {
// Queue in intermediate state, advance tail
tail.compareAndSet(curTail, tailNext);
} else {
// In quiescent state, try inserting new node
if (curTail.next.compareAndSet(null, newNode)) {
// Insertion succeeded, try advancing tail
tail.compareAndSet(curTail, newNode);
return true;
}
}
}
}
}
}