util/concurrent/ConcurrentLinkedQueue.java

/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/licenses/publicdomain
 */

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 <em>head</em> of the queue is that element that has been on the
 * queue the longest time.
 * The <em>tail</em> 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 <tt>ConcurrentLinkedQueue</tt> is an appropriate choice when
 * many threads will share access to a common collection.
 * This queue does not permit <tt>null</tt> elements.
 *
 * <p>This implementation employs an efficient &quot;wait-free&quot;
 * algorithm based on one described in <a
 * href="http://www.cs.rochester.edu/u/michael/PODC96.html"> Simple,
 * Fast, and Practical Non-Blocking and Blocking Concurrent Queue
 * Algorithms</a> by Maged M. Michael and Michael L. Scott.
 *
 * <p>Beware that, unlike in most collections, the <tt>size</tt> method
 * is <em>NOT</em> a constant-time operation. Because of the
 * asynchronous nature of these queues, determining the current number
 * of elements requires a traversal of the elements.
 *
 * <p>This class and its iterator implement all of the
 * <em>optional</em> methods of the {@link Collection} and {@link
 * Iterator} interfaces.
 *
 * <p>Memory consistency effects: As with other concurrent
 * collections, actions in a thread prior to placing an object into a
 * {@code ConcurrentLinkedQueue}
 * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a>
 * actions subsequent to the access or removal of that element from
 * the {@code ConcurrentLinkedQueue} in another thread.
 *
 * <p>This class is a member of the
 * <a href="{@docRoot}/../guide/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @since 1.5
 * @author Doug Lea
 * @param <E> the type of elements held in this collection
 *
 */
public class ConcurrentLinkedQueue<E> extends AbstractQueue<E>
        implements Queue<E>, java.io.Serializable {
    private static final long serialVersionUID = 196745693267521676L;

    /*
     * This is a straight adaptation of Michael & Scott algorithm.
     * For explanation, read the paper.  The only (minor) algorithmic
     * difference is that this version supports lazy deletion of
     * internal nodes (method remove(Object)) -- remove CAS'es item
     * fields to null. The normal queue operations unlink but then
     * pass over nodes with null item fields. Similarly, iteration
     * methods ignore those with nulls.
     */

    private static class Node<E> {
        private volatile E item;
        private volatile Node<E> next;

        private static final
            AtomicReferenceFieldUpdater<Node, Node>
            nextUpdater =
            AtomicReferenceFieldUpdater.newUpdater
            (Node.class, Node.class, "next");
        private static final
            AtomicReferenceFieldUpdater<Node, Object>
            itemUpdater =
            AtomicReferenceFieldUpdater.newUpdater
            (Node.class, Object.class, "item");

        Node(E x) { item = x; }

        Node(E x, Node<E> n) { item = x; next = n; }

        E getItem() {
            return item;
        }

        boolean casItem(E cmp, E val) {
            return itemUpdater.compareAndSet(this, cmp, val);
        }

        void setItem(E val) {
            itemUpdater.set(this, val);
        }

        Node<E> getNext() {
            return next;
        }

        boolean casNext(Node<E> cmp, Node<E> val) {
            return nextUpdater.compareAndSet(this, cmp, val);
        }

        void setNext(Node<E> val) {
            nextUpdater.set(this, val);
        }

    }

    private static final
        AtomicReferenceFieldUpdater<ConcurrentLinkedQueue, Node>
        tailUpdater =
        AtomicReferenceFieldUpdater.newUpdater
        (ConcurrentLinkedQueue.class, Node.class, "tail");
    private static final
        AtomicReferenceFieldUpdater<ConcurrentLinkedQueue, Node>
        headUpdater =
        AtomicReferenceFieldUpdater.newUpdater
        (ConcurrentLinkedQueue.class,  Node.class, "head");

    private boolean casTail(Node<E> cmp, Node<E> val) {
        return tailUpdater.compareAndSet(this, cmp, val);
    }

    private boolean casHead(Node<E> cmp, Node<E> val) {
        return headUpdater.compareAndSet(this, cmp, val);
    }


    /**
     * Pointer to header node, initialized to a dummy node.  The first
     * actual node is at head.getNext().
     */
    private transient volatile Node<E> head = new Node<E>(null, null);

    /** Pointer to last node on list **/
    private transient volatile Node<E> tail = head;


    /**
     * Creates a <tt>ConcurrentLinkedQueue</tt> that is initially empty.
     */
    public ConcurrentLinkedQueue() {}

    /**
     * Creates a <tt>ConcurrentLinkedQueue</tt>
     * 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 the specified collection or any
     *         of its elements are null
     */
    public ConcurrentLinkedQueue(Collection<? extends E> c) {
        for (Iterator<? extends E> it = c.iterator(); it.hasNext();)
            add(it.next());
    }

    // Have to override just to update the javadoc

    /**
     * Inserts the specified element at the tail of this queue.
     *
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     * @throws NullPointerException if the specified element is null
     */
    public boolean add(E e) {
        return offer(e);
    }

    /**
     * Inserts the specified element at the tail of this queue.
     *
     * @return <tt>true</tt> (as specified by {@link Queue#offer})
     * @throws NullPointerException if the specified element is null
     */
    public boolean offer(E e) {
        if (e == null) throw new NullPointerException();
        Node<E> n = new Node<E>(e, 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 E poll() {
        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,
                }
            }
        }
    }

    public E peek() { // 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);
                }
            }
        }
    }

    /**
     * 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.)
     */
    Node<E> first() {
        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);
                }
            }
        }
    }


    /**
     * Returns <tt>true</tt> if this queue contains no elements.
     *
     * @return <tt>true</tt> if this queue contains no elements
     */
    public boolean isEmpty() {
        return first() == null;
    }

    /**
     * Returns the number of elements in this queue.  If this queue
     * contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
     * <tt>Integer.MAX_VALUE</tt>.
     *
     * <p>Beware that, unlike in most collections, this method is
     * <em>NOT</em> 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
     */
    public int size() {
        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;
    }

    /**
     * Returns <tt>true</tt> if this queue contains the specified element.
     * More formally, returns <tt>true</tt> if and only if this queue contains
     * at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>.
     *
     * @param o object to be checked for containment in this queue
     * @return <tt>true</tt> if this queue contains the specified element
     */
    public boolean contains(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;
    }

    /**
     * Removes a single instance of the specified element from this queue,
     * if it is present.  More formally, removes an element <tt>e</tt> such
     * that <tt>o.equals(e)</tt>, if this queue contains one or more such
     * elements.
     * Returns <tt>true</tt> if this queue contained the specified element
     * (or equivalently, if this queue changed as a result of the call).
     *
     * @param o element to be removed from this queue, if present
     * @return <tt>true</tt> if this queue changed as a result of the call
     */
    public boolean remove(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;
    }

    /**
     * Returns an array containing all of the elements in this queue, in
     * proper sequence.
     *
     * <p>The returned array will be "safe" in that no references to it are
     * maintained by this queue.  (In other words, this method must allocate
     * a new array).  The caller is thus free to modify the returned array.
     *
     * <p>This method acts as bridge between array-based and collection-based
     * APIs.
     *
     * @return an array containing all of the elements in this queue
     */
    public 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();
    }

    /**
     * Returns an array containing all of the elements in this queue, in
     * proper sequence; the runtime type of the returned array is that of
     * the specified array.  If the queue fits in the specified array, it
     * is returned therein.  Otherwise, a new array is allocated with the
     * runtime type of the specified array and the size of this queue.
     *
     * <p>If this queue fits in the specified array with room to spare
     * (i.e., the array has more elements than this queue), the element in
     * the array immediately following the end of the queue is set to
     * <tt>null</tt>.
     *
     * <p>Like the {@link #toArray()} method, this method acts as bridge between
     * array-based and collection-based APIs.  Further, this method allows
     * precise control over the runtime type of the output array, and may,
     * under certain circumstances, be used to save allocation costs.
     *
     * <p>Suppose <tt>x</tt> is a queue known to contain only strings.
     * The following code can be used to dump the queue into a newly
     * allocated array of <tt>String</tt>:
     *
     * <pre>
     *     String[] y = x.toArray(new String[0]);</pre>
     *
     * Note that <tt>toArray(new Object[0])</tt> is identical in function to
     * <tt>toArray()</tt>.
     *
     * @param a the array into which the elements of the queue are to
     *          be stored, if it is big enough; otherwise, a new array of the
     *          same runtime type is allocated for this purpose
     * @return an array containing all of the elements in this queue
     * @throws ArrayStoreException if the runtime type of the specified array
     *         is not a supertype of the runtime type of every element in
     *         this queue
     * @throws NullPointerException if the specified array is null
     */
    public <T> 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);
    }

    /**
     * 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 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
     */
    public Iterator<E> iterator() {
        return new Itr();
    }

    private class Itr implements Iterator<E> {
        /**
         * Next node to return item for.
         */
        private Node<E> nextNode;

        /**
         * nextItem holds on to item fields because once we claim
         * that an element exists in hasNext(), we must return it in
         * the following next() call even if it was in the process of
         * being removed when hasNext() was called.
         */
        private E nextItem;

        /**
         * Node of the last returned item, to support remove.
         */
        private Node<E> lastRet;

        Itr() {
            advance();
        }

        /**
         * Moves to next valid node and returns item to return for
         * next(), or null if no such.
         */
        private E advance() {
            lastRet = nextNode;
            E x = nextItem;

            Node<E> p = (nextNode == null)? first() : nextNode.getNext();
            for (;;) {
                if (p == null) {
                    nextNode = null;
                    nextItem = null;
                    return x;
                }
                E item = p.getItem();
                if (item != null) {
                    nextNode = p;
                    nextItem = item;
                    return x;
                } else // skip over nulls
                    p = p.getNext();
            }
        }

        public boolean hasNext() {
            return nextNode != null;
        }

        public E next() {
            if (nextNode == null) throw new NoSuchElementException();
            return advance();
        }

        public void remove() {
            Node<E> l = lastRet;
            if (l == null) throw new IllegalStateException();
            // rely on a future traversal to relink.
            l.setItem(null);
            lastRet = null;
        }
    }

    /**
     * Save the state to a stream (that is, serialize it).
     *
     * @serialData All of the elements (each an <tt>E</tt>) in
     * the proper order, followed by a null
     * @param s the stream
     */
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {

        // 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);
    }

    /**
     * Reconstitute the Queue instance from a stream (that is,
     * deserialize it).
     * @param s the stream
     */
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // 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);
        }
    }

}
Revision:	1.43
Committed:	Wed Sep 14 21:45:12 2005 UTC (18 years, 9 months ago) by jsr166
Branch:	MAIN
Changes since 1.42:	+7 -6 lines
Log Message:	happens-before
#	User	Rev	Content
1	dl	1.1	/*
2			* Written by Doug Lea with assistance from members of JCP JSR-166
3	dl	1.24	* Expert Group and released to the public domain, as explained at
4			* http://creativecommons.org/licenses/publicdomain
5	dl	1.1	*/
6
7			package java.util.concurrent;
8			import java.util.*;
9			import java.util.concurrent.atomic.*;
10
11
12			/**
13	jsr166	1.29	* An unbounded thread-safe {@linkplain Queue queue} based on linked nodes.
14	dholmes	1.6	* This queue orders elements FIFO (first-in-first-out).
15			* The <em>head</em> of the queue is that element that has been on the
16			* queue the longest time.
17			* The <em>tail</em> of the queue is that element that has been on the
18	dl	1.17	* queue the shortest time. New elements
19			* are inserted at the tail of the queue, and the queue retrieval
20			* operations obtain elements at the head of the queue.
21	jsr166	1.29	* A <tt>ConcurrentLinkedQueue</tt> is an appropriate choice when
22	dl	1.19	* many threads will share access to a common collection.
23	dholmes	1.6	* This queue does not permit <tt>null</tt> elements.
24	dl	1.1	*
25	jsr166	1.29	* <p>This implementation employs an efficient "wait-free"
26	dholmes	1.6	* algorithm based on one described in <a
27	dl	1.1	* href="http://www.cs.rochester.edu/u/michael/PODC96.html"> Simple,
28			* Fast, and Practical Non-Blocking and Blocking Concurrent Queue
29	dl	1.15	* Algorithms</a> by Maged M. Michael and Michael L. Scott.
30	dl	1.1	*
31	dholmes	1.7	* <p>Beware that, unlike in most collections, the <tt>size</tt> method
32	dl	1.1	* is <em>NOT</em> a constant-time operation. Because of the
33			* asynchronous nature of these queues, determining the current number
34	dl	1.15	* of elements requires a traversal of the elements.
35	dl	1.18	*
36	dl	1.27	* <p>This class and its iterator implement all of the
37			* <em>optional</em> methods of the {@link Collection} and {@link
38	jsr166	1.29	* Iterator} interfaces.
39	dl	1.18	*
40	jsr166	1.43	* <p>Memory consistency effects: As with other concurrent
41			* collections, actions in a thread prior to placing an object into a
42			* {@code ConcurrentLinkedQueue}
43			* <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a>
44			* actions subsequent to the access or removal of that element from
45			* the {@code ConcurrentLinkedQueue} in another thread.
46			*
47	dl	1.25	* <p>This class is a member of the
48			* <a href="{@docRoot}/../guide/collections/index.html">
49			* Java Collections Framework</a>.
50			*
51	dl	1.1	* @since 1.5
52			* @author Doug Lea
53	dl	1.21	* @param <E> the type of elements held in this collection
54	tim	1.2	*
55	dl	1.25	*/
56	dl	1.1	public class ConcurrentLinkedQueue<E> extends AbstractQueue<E>
57			implements Queue<E>, java.io.Serializable {
58	dl	1.14	private static final long serialVersionUID = 196745693267521676L;
59	dl	1.1
60			/*
61			* This is a straight adaptation of Michael & Scott algorithm.
62			* For explanation, read the paper. The only (minor) algorithmic
63			* difference is that this version supports lazy deletion of
64			* internal nodes (method remove(Object)) -- remove CAS'es item
65			* fields to null. The normal queue operations unlink but then
66			* pass over nodes with null item fields. Similarly, iteration
67			* methods ignore those with nulls.
68			*/
69
70	dl	1.23	private static class Node<E> {
71	dl	1.22	private volatile E item;
72	dl	1.23	private volatile Node<E> next;
73	jsr166	1.29
74			private static final
75			AtomicReferenceFieldUpdater<Node, Node>
76	dl	1.13	nextUpdater =
77			AtomicReferenceFieldUpdater.newUpdater
78	dl	1.23	(Node.class, Node.class, "next");
79	jsr166	1.29	private static final
80			AtomicReferenceFieldUpdater<Node, Object>
81	dl	1.13	itemUpdater =
82			AtomicReferenceFieldUpdater.newUpdater
83	dl	1.23	(Node.class, Object.class, "item");
84	jsr166	1.29
85	dl	1.23	Node(E x) { item = x; }
86	jsr166	1.29
87	dl	1.23	Node(E x, Node<E> n) { item = x; next = n; }
88	jsr166	1.29
89	dl	1.22	E getItem() {
90	dl	1.13	return item;
91			}
92	jsr166	1.29
93	dl	1.22	boolean casItem(E cmp, E val) {
94	dl	1.13	return itemUpdater.compareAndSet(this, cmp, val);
95			}
96	jsr166	1.29
97	dl	1.22	void setItem(E val) {
98	dl	1.13	itemUpdater.set(this, val);
99			}
100	jsr166	1.29
101	dl	1.23	Node<E> getNext() {
102	dl	1.13	return next;
103			}
104	jsr166	1.29
105	dl	1.23	boolean casNext(Node<E> cmp, Node<E> val) {
106	dl	1.13	return nextUpdater.compareAndSet(this, cmp, val);
107			}
108	jsr166	1.29
109	dl	1.23	void setNext(Node<E> val) {
110	dl	1.13	nextUpdater.set(this, val);
111			}
112	jsr166	1.29
113	dl	1.13	}
114	dl	1.1
115	jsr166	1.29	private static final
116			AtomicReferenceFieldUpdater<ConcurrentLinkedQueue, Node>
117			tailUpdater =
118	dl	1.5	AtomicReferenceFieldUpdater.newUpdater
119	dl	1.23	(ConcurrentLinkedQueue.class, Node.class, "tail");
120	jsr166	1.29	private static final
121			AtomicReferenceFieldUpdater<ConcurrentLinkedQueue, Node>
122			headUpdater =
123	dl	1.5	AtomicReferenceFieldUpdater.newUpdater
124	dl	1.23	(ConcurrentLinkedQueue.class, Node.class, "head");
125	dl	1.1
126	dl	1.23	private boolean casTail(Node<E> cmp, Node<E> val) {
127	dl	1.1	return tailUpdater.compareAndSet(this, cmp, val);
128			}
129
130	dl	1.23	private boolean casHead(Node<E> cmp, Node<E> val) {
131	dl	1.1	return headUpdater.compareAndSet(this, cmp, val);
132			}
133
134
135	tim	1.2	/**
136	dl	1.1	* Pointer to header node, initialized to a dummy node. The first
137			* actual node is at head.getNext().
138			*/
139	dl	1.23	private transient volatile Node<E> head = new Node<E>(null, null);
140	dl	1.1
141			/ Pointer to last node on list /
142	dl	1.23	private transient volatile Node<E> tail = head;
143	dl	1.1
144
145			/**
146	dholmes	1.6	* Creates a <tt>ConcurrentLinkedQueue</tt> that is initially empty.
147	dl	1.1	*/
148			public ConcurrentLinkedQueue() {}
149
150			/**
151	jsr166	1.29	* Creates a <tt>ConcurrentLinkedQueue</tt>
152	dholmes	1.7	* initially containing the elements of the given collection,
153	dholmes	1.6	* added in traversal order of the collection's iterator.
154			* @param c the collection of elements to initially contain
155	jsr166	1.34	* @throws NullPointerException if the specified collection or any
156			* of its elements are null
157	dl	1.1	*/
158	dholmes	1.6	public ConcurrentLinkedQueue(Collection<? extends E> c) {
159			for (Iterator<? extends E> it = c.iterator(); it.hasNext();)
160	dl	1.1	add(it.next());
161			}
162
163	jsr166	1.29	// Have to override just to update the javadoc
164	dholmes	1.6
165			/**
166	jsr166	1.35	* Inserts the specified element at the tail of this queue.
167	dholmes	1.7	*
168	jsr166	1.39	* @return <tt>true</tt> (as specified by {@link Collection#add})
169	jsr166	1.32	* @throws NullPointerException if the specified element is null
170	dholmes	1.6	*/
171	jsr166	1.31	public boolean add(E e) {
172			return offer(e);
173	dholmes	1.6	}
174
175			/**
176	jsr166	1.32	* Inserts the specified element at the tail of this queue.
177	dl	1.17	*
178	jsr166	1.39	* @return <tt>true</tt> (as specified by {@link Queue#offer})
179	jsr166	1.32	* @throws NullPointerException if the specified element is null
180	dholmes	1.6	*/
181	jsr166	1.31	public boolean offer(E e) {
182			if (e == null) throw new NullPointerException();
183			Node<E> n = new Node<E>(e, null);
184	jsr166	1.38	for (;;) {
185	dl	1.23	Node<E> t = tail;
186			Node<E> s = t.getNext();
187	dl	1.1	if (t == tail) {
188			if (s == null) {
189			if (t.casNext(s, n)) {
190	tim	1.2	casTail(t, n);
191	dl	1.1	return true;
192			}
193	tim	1.12	} else {
194	dl	1.1	casTail(t, s);
195			}
196			}
197			}
198			}
199
200			public E poll() {
201			for (;;) {
202	dl	1.23	Node<E> h = head;
203			Node<E> t = tail;
204			Node<E> first = h.getNext();
205	dl	1.1	if (h == head) {
206			if (h == t) {
207			if (first == null)
208			return null;
209			else
210			casTail(t, first);
211	tim	1.12	} else if (casHead(h, first)) {
212	dl	1.22	E item = first.getItem();
213	dl	1.1	if (item != null) {
214			first.setItem(null);
215			return item;
216			}
217	tim	1.2	// else skip over deleted item, continue loop,
218	dl	1.1	}
219			}
220			}
221			}
222
223			public E peek() { // same as poll except don't remove item
224			for (;;) {
225	dl	1.23	Node<E> h = head;
226			Node<E> t = tail;
227			Node<E> first = h.getNext();
228	dl	1.1	if (h == head) {
229			if (h == t) {
230			if (first == null)
231			return null;
232			else
233			casTail(t, first);
234	tim	1.12	} else {
235	dl	1.22	E item = first.getItem();
236	dl	1.1	if (item != null)
237			return item;
238			else // remove deleted node and continue
239			casHead(h, first);
240			}
241			}
242			}
243			}
244
245			/**
246	dholmes	1.6	* Returns the first actual (non-header) node on list. This is yet
247	dl	1.1	* another variant of poll/peek; here returning out the first
248			* node, not element (so we cannot collapse with peek() without
249			* introducing race.)
250			*/
251	dl	1.23	Node<E> first() {
252	dl	1.1	for (;;) {
253	dl	1.23	Node<E> h = head;
254			Node<E> t = tail;
255			Node<E> first = h.getNext();
256	dl	1.1	if (h == head) {
257			if (h == t) {
258			if (first == null)
259			return null;
260			else
261			casTail(t, first);
262	tim	1.12	} else {
263	dl	1.1	if (first.getItem() != null)
264			return first;
265			else // remove deleted node and continue
266			casHead(h, first);
267			}
268			}
269			}
270			}
271
272
273	dl	1.28	/**
274	jsr166	1.30	* Returns <tt>true</tt> if this queue contains no elements.
275	dl	1.28	*
276	jsr166	1.33	* @return <tt>true</tt> if this queue contains no elements
277	dl	1.28	*/
278	dl	1.1	public boolean isEmpty() {
279			return first() == null;
280			}
281
282			/**
283	dl	1.17	* Returns the number of elements in this queue. If this queue
284			* contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
285			* <tt>Integer.MAX_VALUE</tt>.
286	tim	1.2	*
287	dl	1.17	* <p>Beware that, unlike in most collections, this method is
288	dl	1.1	* <em>NOT</em> a constant-time operation. Because of the
289			* asynchronous nature of these queues, determining the current
290			* number of elements requires an O(n) traversal.
291	dl	1.17	*
292	jsr166	1.37	* @return the number of elements in this queue
293	tim	1.2	*/
294	dl	1.1	public int size() {
295			int count = 0;
296	dl	1.23	for (Node<E> p = first(); p != null; p = p.getNext()) {
297	dl	1.8	if (p.getItem() != null) {
298			// Collections.size() spec says to max out
299			if (++count == Integer.MAX_VALUE)
300			break;
301			}
302	dl	1.1	}
303			return count;
304			}
305
306	jsr166	1.37	/**
307			* Returns <tt>true</tt> if this queue contains the specified element.
308			* More formally, returns <tt>true</tt> if and only if this queue contains
309			* at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>.
310			*
311			* @param o object to be checked for containment in this queue
312			* @return <tt>true</tt> if this queue contains the specified element
313			*/
314	dholmes	1.6	public boolean contains(Object o) {
315			if (o == null) return false;
316	dl	1.23	for (Node<E> p = first(); p != null; p = p.getNext()) {
317	dl	1.22	E item = p.getItem();
318	tim	1.2	if (item != null &&
319	dholmes	1.6	o.equals(item))
320	dl	1.1	return true;
321			}
322			return false;
323			}
324
325	jsr166	1.37	/**
326			* Removes a single instance of the specified element from this queue,
327			* if it is present. More formally, removes an element <tt>e</tt> such
328			* that <tt>o.equals(e)</tt>, if this queue contains one or more such
329			* elements.
330			* Returns <tt>true</tt> if this queue contained the specified element
331			* (or equivalently, if this queue changed as a result of the call).
332			*
333			* @param o element to be removed from this queue, if present
334			* @return <tt>true</tt> if this queue changed as a result of the call
335			*/
336	dholmes	1.6	public boolean remove(Object o) {
337			if (o == null) return false;
338	dl	1.23	for (Node<E> p = first(); p != null; p = p.getNext()) {
339	dl	1.22	E item = p.getItem();
340	tim	1.2	if (item != null &&
341	dholmes	1.6	o.equals(item) &&
342	dl	1.1	p.casItem(item, null))
343			return true;
344			}
345			return false;
346			}
347	tim	1.2
348	jsr166	1.33	/**
349			* Returns an array containing all of the elements in this queue, in
350			* proper sequence.
351			*
352			* <p>The returned array will be "safe" in that no references to it are
353			* maintained by this queue. (In other words, this method must allocate
354			* a new array). The caller is thus free to modify the returned array.
355	jsr166	1.36	*
356	jsr166	1.33	* <p>This method acts as bridge between array-based and collection-based
357			* APIs.
358			*
359			* @return an array containing all of the elements in this queue
360			*/
361	dl	1.1	public Object[] toArray() {
362			// Use ArrayList to deal with resizing.
363	tim	1.3	ArrayList<E> al = new ArrayList<E>();
364	dl	1.23	for (Node<E> p = first(); p != null; p = p.getNext()) {
365	dl	1.22	E item = p.getItem();
366	dl	1.1	if (item != null)
367			al.add(item);
368			}
369			return al.toArray();
370			}
371
372	jsr166	1.33	/**
373			* Returns an array containing all of the elements in this queue, in
374			* proper sequence; the runtime type of the returned array is that of
375			* the specified array. If the queue fits in the specified array, it
376			* is returned therein. Otherwise, a new array is allocated with the
377			* runtime type of the specified array and the size of this queue.
378			*
379			* <p>If this queue fits in the specified array with room to spare
380			* (i.e., the array has more elements than this queue), the element in
381			* the array immediately following the end of the queue is set to
382			* <tt>null</tt>.
383			*
384			* <p>Like the {@link #toArray()} method, this method acts as bridge between
385			* array-based and collection-based APIs. Further, this method allows
386			* precise control over the runtime type of the output array, and may,
387			* under certain circumstances, be used to save allocation costs.
388			*
389			* <p>Suppose <tt>x</tt> is a queue known to contain only strings.
390			* The following code can be used to dump the queue into a newly
391			* allocated array of <tt>String</tt>:
392			*
393			* <pre>
394			* String[] y = x.toArray(new String[0]);</pre>
395			*
396			* Note that <tt>toArray(new Object[0])</tt> is identical in function to
397			* <tt>toArray()</tt>.
398			*
399			* @param a the array into which the elements of the queue are to
400			* be stored, if it is big enough; otherwise, a new array of the
401			* same runtime type is allocated for this purpose
402			* @return an array containing all of the elements in this queue
403			* @throws ArrayStoreException if the runtime type of the specified array
404			* is not a supertype of the runtime type of every element in
405			* this queue
406			* @throws NullPointerException if the specified array is null
407			*/
408	dl	1.1	public <T> T[] toArray(T[] a) {
409			// try to use sent-in array
410			int k = 0;
411	dl	1.23	Node<E> p;
412	dl	1.1	for (p = first(); p != null && k < a.length; p = p.getNext()) {
413	dl	1.22	E item = p.getItem();
414	dl	1.1	if (item != null)
415			a[k++] = (T)item;
416			}
417			if (p == null) {
418			if (k < a.length)
419			a[k] = null;
420			return a;
421			}
422
423			// If won't fit, use ArrayList version
424	tim	1.3	ArrayList<E> al = new ArrayList<E>();
425	dl	1.23	for (Node<E> q = first(); q != null; q = q.getNext()) {
426	dl	1.22	E item = q.getItem();
427	dl	1.1	if (item != null)
428			al.add(item);
429			}
430			return (T[])al.toArray(a);
431			}
432
433	dholmes	1.7	/**
434			* Returns an iterator over the elements in this queue in proper sequence.
435	dl	1.9	* The returned iterator is a "weakly consistent" iterator that
436	jsr166	1.29	* will never throw {@link ConcurrentModificationException},
437	dl	1.9	* and guarantees to traverse elements as they existed upon
438			* construction of the iterator, and may (but is not guaranteed to)
439			* reflect any modifications subsequent to construction.
440	dholmes	1.7	*
441	jsr166	1.33	* @return an iterator over the elements in this queue in proper sequence
442	dholmes	1.7	*/
443	dl	1.1	public Iterator<E> iterator() {
444			return new Itr();
445			}
446
447			private class Itr implements Iterator<E> {
448			/**
449			* Next node to return item for.
450			*/
451	dl	1.23	private Node<E> nextNode;
452	dl	1.1
453	tim	1.2	/**
454	dl	1.1	* nextItem holds on to item fields because once we claim
455			* that an element exists in hasNext(), we must return it in
456			* the following next() call even if it was in the process of
457			* being removed when hasNext() was called.
458	jsr166	1.29	*/
459	dl	1.1	private E nextItem;
460
461			/**
462			* Node of the last returned item, to support remove.
463			*/
464	dl	1.23	private Node<E> lastRet;
465	dl	1.1
466	tim	1.2	Itr() {
467	dl	1.1	advance();
468			}
469	tim	1.2
470	dl	1.1	/**
471	dl	1.26	* Moves to next valid node and returns item to return for
472			* next(), or null if no such.
473	dl	1.1	*/
474	tim	1.2	private E advance() {
475	dl	1.1	lastRet = nextNode;
476	dl	1.22	E x = nextItem;
477	dl	1.1
478	dl	1.23	Node<E> p = (nextNode == null)? first() : nextNode.getNext();
479	dl	1.1	for (;;) {
480			if (p == null) {
481			nextNode = null;
482			nextItem = null;
483			return x;
484			}
485	dl	1.22	E item = p.getItem();
486	dl	1.1	if (item != null) {
487			nextNode = p;
488			nextItem = item;
489			return x;
490	tim	1.12	} else // skip over nulls
491	dl	1.1	p = p.getNext();
492			}
493			}
494	tim	1.2
495	dl	1.1	public boolean hasNext() {
496			return nextNode != null;
497			}
498	tim	1.2
499	dl	1.1	public E next() {
500			if (nextNode == null) throw new NoSuchElementException();
501			return advance();
502			}
503	tim	1.2
504	dl	1.1	public void remove() {
505	dl	1.23	Node<E> l = lastRet;
506	dl	1.1	if (l == null) throw new IllegalStateException();
507			// rely on a future traversal to relink.
508			l.setItem(null);
509			lastRet = null;
510			}
511			}
512
513			/**
514			* Save the state to a stream (that is, serialize it).
515			*
516			* @serialData All of the elements (each an <tt>E</tt>) in
517			* the proper order, followed by a null
518			* @param s the stream
519			*/
520			private void writeObject(java.io.ObjectOutputStream s)
521			throws java.io.IOException {
522
523			// Write out any hidden stuff
524			s.defaultWriteObject();
525	tim	1.2
526	dl	1.1	// Write out all elements in the proper order.
527	dl	1.23	for (Node<E> p = first(); p != null; p = p.getNext()) {
528	dl	1.1	Object item = p.getItem();
529			if (item != null)
530			s.writeObject(item);
531			}
532
533			// Use trailing null as sentinel
534			s.writeObject(null);
535			}
536
537			/**
538			* Reconstitute the Queue instance from a stream (that is,
539			* deserialize it).
540			* @param s the stream
541			*/
542			private void readObject(java.io.ObjectInputStream s)
543			throws java.io.IOException, ClassNotFoundException {
544	tim	1.2	// Read in capacity, and any hidden stuff
545			s.defaultReadObject();
546	dl	1.23	head = new Node<E>(null, null);
547	dl	1.16	tail = head;
548	tim	1.2	// Read in all elements and place in queue
549	dl	1.1	for (;;) {
550			E item = (E)s.readObject();
551			if (item == null)
552			break;
553	dl	1.16	else
554			offer(item);
555	dl	1.1	}
556			}
557
558			}