FileDocCategorySizeDatePackage
ConcurrentLinkedQueue.javaAPI DocAndroid 1.5 API15169Wed May 06 22:41:02 BST 2009java.util.concurrent

ConcurrentLinkedQueue

public class ConcurrentLinkedQueue extends AbstractQueue implements Queue, Serializable
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. New elements are inserted at the tail of the queue, and the queue retrieval operations obtain elements at the head of the queue. A ConcurrentLinkedQueue is an appropriate choice when many threads will share access to a common collection. 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 a traversal of the elements.

This class implements all of the optional methods of the {@link Collection} and {@link Iterator} interfaces.

since
1.5
author
Doug Lea
param
the type of elements held in this collection

Fields Summary
private static final long
serialVersionUID
private static final AtomicReferenceFieldUpdater
tailUpdater
private static final AtomicReferenceFieldUpdater
headUpdater
private volatile transient Node
head
Pointer to header node, initialized to a dummy node. The first actual node is at head.getNext().
private volatile transient Node
tail
Pointer to last node on list
Constructors Summary
public ConcurrentLinkedQueue()
Creates a ConcurrentLinkedQueue that is initially empty.



                
      
public ConcurrentLinkedQueue(Collection c)
Creates a ConcurrentLinkedQueue initially containing the elements of the given collection, added in traversal order of the collection's iterator.

param
c the collection of elements to initially contain
throws
NullPointerException if c or any element within it is null

        for (Iterator<? extends E> it = c.iterator(); it.hasNext();)
            add(it.next());
    
Methods Summary
public booleanadd(E o)
Adds the specified element to the tail of this queue.

param
o the element to add.
return
true (as per the general contract of Collection.add).
throws
NullPointerException if the specified element is null

        return offer(o);
    
private booleancasHead(java.util.concurrent.ConcurrentLinkedQueue$Node cmp, java.util.concurrent.ConcurrentLinkedQueue$Node val)

        return headUpdater.compareAndSet(this, cmp, val);
    
private booleancasTail(java.util.concurrent.ConcurrentLinkedQueue$Node cmp, java.util.concurrent.ConcurrentLinkedQueue$Node val)


          
        return tailUpdater.compareAndSet(this, cmp, val);
    
public booleancontains(java.lang.Object o)

        if (o == null) return false;
        for (Node<E> p = first(); p != null; p = p.getNext()) {
            E item = p.getItem();
            if (item != null &&
                o.equals(item))
                return true;
        }
        return false;
    
java.util.concurrent.ConcurrentLinkedQueue$Nodefirst()
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.)

        for (;;) {
            Node<E> h = head;
            Node<E> t = tail;
            Node<E> 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 booleanisEmpty()

        return first() == null;
    
public java.util.Iteratoriterator()
Returns an iterator over the elements in this queue in proper sequence. The returned iterator is a "weakly consistent" iterator that will never throw {@link java.util.ConcurrentModificationException}, and guarantees to traverse elements as they existed upon construction of the iterator, and may (but is not guaranteed to) reflect any modifications subsequent to construction.

return
an iterator over the elements in this queue in proper sequence.

        return new Itr();
    
public booleanoffer(E o)
Inserts the specified element to the tail of this queue.

param
o the element to add.
return
true (as per the general contract of Queue.offer).
throws
NullPointerException if the specified element is null

        if (o == null) throw new NullPointerException();
        Node<E> n = new Node<E>(o, null);
        for(;;) {
            Node<E> t = tail;
            Node<E> s = t.getNext();
            if (t == tail) {
                if (s == null) {
                    if (t.casNext(s, n)) {
                        casTail(t, n);
                        return true;
                    }
                } else {
                    casTail(t, s);
                }
            }
        }
    
public Epeek()

 // same as poll except don't remove item
        for (;;) {
            Node<E> h = head;
            Node<E> t = tail;
            Node<E> first = h.getNext();
            if (h == head) {
                if (h == t) {
                    if (first == null)
                        return null;
                    else
                        casTail(t, first);
                } else {
                    E item = first.getItem();
                    if (item != null)
                        return item;
                    else // remove deleted node and continue
                        casHead(h, first);
                }
            }
        }
    
public Epoll()

        for (;;) {
            Node<E> h = head;
            Node<E> t = tail;
            Node<E> 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 = first.getItem();
                    if (item != null) {
                        first.setItem(null);
                        return item;
                    }
                    // else skip over deleted item, continue loop,
                }
            }
        }
    
private voidreadObject(java.io.ObjectInputStream s)
Reconstitute the Queue instance from a stream (that is, deserialize it).

param
s the stream

        // Read in capacity, and any hidden stuff
        s.defaultReadObject();
        head = new Node<E>(null, null);
        tail = head;
        // Read in all elements and place in queue
        for (;;) {
            E item = (E)s.readObject();
            if (item == null)
                break;
            else
                offer(item);
        }
    
public booleanremove(java.lang.Object o)

        if (o == null) return false;
        for (Node<E> p = first(); p != null; p = p.getNext()) {
            E item = p.getItem();
            if (item != null &&
                o.equals(item) &&
                p.casItem(item, null))
                return true;
        }
        return false;
    
public intsize()
Returns the number of elements in this queue. If this queue contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.

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.

return
the number of elements in this queue.

        int count = 0;
        for (Node<E> 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 java.lang.Object[]toArray()

        // Use ArrayList to deal with resizing.
        ArrayList<E> al = new ArrayList<E>();
        for (Node<E> p = first(); p != null; p = p.getNext()) {
            E item = p.getItem();
            if (item != null)
                al.add(item);
        }
        return al.toArray();
    
public T[]toArray(T[] a)

        // try to use sent-in array
        int k = 0;
        Node<E> p;
        for (p = first(); p != null && k < a.length; p = p.getNext()) {
            E item = p.getItem();
            if (item != null)
                a[k++] = (T)item;
        }
        if (p == null) {
            if (k < a.length)
                a[k] = null;
            return a;
        }

        // If won't fit, use ArrayList version
        ArrayList<E> al = new ArrayList<E>();
        for (Node<E> q = first(); q != null; q = q.getNext()) {
            E item = q.getItem();
            if (item != null)
                al.add(item);
        }
        return (T[])al.toArray(a);
    
private voidwriteObject(java.io.ObjectOutputStream s)
Save the state to a stream (that is, serialize it).

serialData
All of the elements (each an E) in the proper order, followed by a null
param
s the stream


        // Write out any hidden stuff
        s.defaultWriteObject();

        // Write out all elements in the proper order.
        for (Node<E> p = first(); p != null; p = p.getNext()) {
            Object item = p.getItem();
            if (item != null)
                s.writeObject(item);
        }

        // Use trailing null as sentinel
        s.writeObject(null);