/* * Written by Doug Lea with assistance from members of JCP JSR-166 * Expert Group and released to the public domain. Use, modify, and * redistribute this code in any way without acknowledgement. */ package java.util.concurrent; import java.util.*; import java.util.concurrent.atomic.*; /** * An unbounded thread-safe {@linkplain Queue queue} based on linked nodes. * This queue orders elements FIFO (first-in-first-out). * The head of the queue is that element that has been on the * queue the longest time. * The tail of the queue is that element that has been on the * queue the shortest time. * A ConcurrentLinkedQueue is an especially good choice when * many threads will share access to a common queue. * This queue does not permit null elements. * *
This implementation employs an efficient "wait-free" * algorithm based on one described in Simple, * Fast, and Practical Non-Blocking and Blocking Concurrent Queue * Algorithms by Maged M. Michael and Michael L. Scott.) * *
Beware that, unlike in most collections, the size method
* is NOT a constant-time operation. Because of the
* asynchronous nature of these queues, determining the current number
* of elements requires an O(n) traversal.
* @since 1.5
* @author Doug Lea
*
**/
public class ConcurrentLinkedQueue
* This implementation iterates over the specified collection, and adds
* each object returned by the iterator to this queue's tail, in turn.
* @throws NullPointerException {@inheritDoc}
*/
public boolean addAll(Collection extends E> c) {
return super.addAll(c);
}
/**
* @throws NullPointerException if the specified element is null
*/
public boolean offer(E o) {
if (o == null) throw new NullPointerException();
AtomicLinkedNode n = new AtomicLinkedNode(o, null);
for(;;) {
AtomicLinkedNode t = tail;
AtomicLinkedNode s = t.getNext();
if (t == tail) {
if (s == null) {
if (t.casNext(s, n)) {
casTail(t, n);
return true;
}
} else {
casTail(t, s);
}
}
}
}
public E poll() {
for (;;) {
AtomicLinkedNode h = head;
AtomicLinkedNode t = tail;
AtomicLinkedNode first = h.getNext();
if (h == head) {
if (h == t) {
if (first == null)
return null;
else
casTail(t, first);
} else if (casHead(h, first)) {
E item = (E)first.getItem();
if (item != null) {
first.setItem(null);
return item;
}
// else skip over deleted item, continue loop,
}
}
}
}
public E peek() { // same as poll except don't remove item
for (;;) {
AtomicLinkedNode h = head;
AtomicLinkedNode t = tail;
AtomicLinkedNode first = h.getNext();
if (h == head) {
if (h == t) {
if (first == null)
return null;
else
casTail(t, first);
} else {
E item = (E)first.getItem();
if (item != null)
return item;
else // remove deleted node and continue
casHead(h, first);
}
}
}
}
/**
* Returns the first actual (non-header) node on list. This is yet
* another variant of poll/peek; here returning out the first
* node, not element (so we cannot collapse with peek() without
* introducing race.)
*/
AtomicLinkedNode first() {
for (;;) {
AtomicLinkedNode h = head;
AtomicLinkedNode t = tail;
AtomicLinkedNode first = h.getNext();
if (h == head) {
if (h == t) {
if (first == null)
return null;
else
casTail(t, first);
} else {
if (first.getItem() != null)
return first;
else // remove deleted node and continue
casHead(h, first);
}
}
}
}
public boolean isEmpty() {
return first() == null;
}
/**
* {@inheritDoc}
*
* Beware that, unlike in most collections, this method is
* NOT a constant-time operation. Because of the
* asynchronous nature of these queues, determining the current
* number of elements requires an O(n) traversal.
*/
public int size() {
int count = 0;
for (AtomicLinkedNode p = first(); p != null; p = p.getNext()) {
if (p.getItem() != null) {
// Collections.size() spec says to max out
if (++count == Integer.MAX_VALUE)
break;
}
}
return count;
}
public boolean contains(Object o) {
if (o == null) return false;
for (AtomicLinkedNode p = first(); p != null; p = p.getNext()) {
Object item = p.getItem();
if (item != null &&
o.equals(item))
return true;
}
return false;
}
/**
* Removes a single instance of the specified element from this
* queue, if it is present. More formally,
* removes an element e such that (o==null ? e==null :
* o.equals(e)), if the queue contains one or more such
* elements. Returns true if the queue contained the
* specified element (or equivalently, if the queue changed as a
* result of the call).
*
* This implementation iterates over the queue looking for the
* specified element. If it finds the element, it removes the element
* from the queue using the iterator's remove method.
*
*/
public boolean remove(Object o) {
if (o == null) return false;
for (AtomicLinkedNode p = first(); p != null; p = p.getNext()) {
Object item = p.getItem();
if (item != null &&
o.equals(item) &&
p.casItem(item, null))
return true;
}
return false;
}
public Object[] toArray() {
// Use ArrayList to deal with resizing.
ArrayList