util/concurrent/ConcurrentLinkedQueue.java

/*
 * 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 <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.
 * A <tt>ConcurrentLinkedQueue</tt> is an especially good choice when 
 * many threads will share access to a common queue.
 * 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 an O(n) traversal.
 * @since 1.5
 * @author Doug Lea
 *
 **/
public class ConcurrentLinkedQueue<E> extends AbstractQueue<E>
        implements Queue<E>, java.io.Serializable {

    /*
     * 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.
     */

    // Atomics support

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

    private boolean casTail(AtomicLinkedNode cmp, AtomicLinkedNode val) {
        return tailUpdater.compareAndSet(this, cmp, val);
    }

    private boolean casHead(AtomicLinkedNode cmp, AtomicLinkedNode 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 AtomicLinkedNode head = new AtomicLinkedNode(null, null);

    /** Pointer to last node on list **/
    private transient volatile AtomicLinkedNode 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 <tt>c</tt> or any element within it
     * is <tt>null</tt>
     */
    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 

    /**
     * Adds the specified element to the tail of this queue.
     * @return <tt>true</tt> (as per the general contract of
     * <tt>Collection.add</tt>).
     *
     * @throws NullPointerException {@inheritDoc}
     */
    public boolean add(E o) {
        return super.add(o);
    }

    /**
     * Adds all of the elements in the specified collection to this queue.
     * The behavior of this operation is undefined if
     * the specified collection is modified while the operation is in
     * progress.  (This implies that the behavior of this call is undefined if
     * the specified collection is this queue, and this queue is nonempty.)
     * <p>
     * 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 <tt>null</tt>
     */
    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
     * <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.
     */
    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 <tt>e</tt> such that <tt>(o==null ? e==null :
     * o.equals(e))</tt>, if the queue contains one or more such
     * elements.  Returns <tt>true</tt> if the queue contained the
     * specified element (or equivalently, if the queue changed as a
     * result of the call).
     *
     * <p>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.<p>
     *
     */
    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<E> al = new ArrayList<E>();
        for (AtomicLinkedNode p = first(); p != null; p = p.getNext()) {
            E item = (E) p.getItem();
            if (item != null)
                al.add(item);
        }
        return al.toArray();
    }

    public <T> T[] toArray(T[] a) {
        // try to use sent-in array
        int k = 0;
        AtomicLinkedNode p;
        for (p = first(); p != null && k < a.length; p = p.getNext()) {
            Object 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 (AtomicLinkedNode q = first(); q != null; q = q.getNext()) {
            E item = (E) 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 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.
     */
    public Iterator<E> iterator() {
        return new Itr();
    }

    private class Itr implements Iterator<E> {
        /**
         * Next node to return item for.
         */
        private AtomicLinkedNode 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 AtomicLinkedNode lastRet;

        Itr() {
            advance();
        }

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

            AtomicLinkedNode p = (nextNode == null)? first() : nextNode.getNext();
            for (;;) {
                if (p == null) {
                    nextNode = null;
                    nextItem = null;
                    return x;
                }
                E item = (E)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() {
            AtomicLinkedNode 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 (AtomicLinkedNode 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();

        // Read in all elements and place in queue
        for (;;) {
            E item = (E)s.readObject();
            if (item == null)
                break;
            add(item);
        }
    }

}
Revision:	1.11
Committed:	Wed Aug 6 19:04:55 2003 UTC (20 years, 10 months ago) by tim
Branch:	MAIN
CVS Tags:	JSR166_CR1
Changes since 1.10:	+2 -2 lines
Log Message:	More DocCheck fixes.
#	User	Rev	Content
1	dl	1.1	/*
2			* Written by Doug Lea with assistance from members of JCP JSR-166
3			* Expert Group and released to the public domain. Use, modify, and
4			* redistribute this code in any way without acknowledgement.
5			*/
6
7			package java.util.concurrent;
8			import java.util.*;
9			import java.util.concurrent.atomic.*;
10
11
12			/**
13	dholmes	1.7	* 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			* queue the shortest time.
19			* A <tt>ConcurrentLinkedQueue</tt> is an especially good choice when
20			* many threads will share access to a common queue.
21			* This queue does not permit <tt>null</tt> elements.
22	dl	1.1	*
23	dholmes	1.6	* <p>This implementation employs an efficient "wait-free"
24			* algorithm based on one described in <a
25	dl	1.1	* href="http://www.cs.rochester.edu/u/michael/PODC96.html"> Simple,
26			* Fast, and Practical Non-Blocking and Blocking Concurrent Queue
27			* Algorithms</a> by Maged M. Michael and Michael L. Scott.)
28			*
29	dholmes	1.7	* <p>Beware that, unlike in most collections, the <tt>size</tt> method
30	dl	1.1	* is <em>NOT</em> a constant-time operation. Because of the
31			* asynchronous nature of these queues, determining the current number
32			* of elements requires an O(n) traversal.
33			* @since 1.5
34			* @author Doug Lea
35	tim	1.2	*
36	dl	1.1	**/
37			public class ConcurrentLinkedQueue<E> extends AbstractQueue<E>
38			implements Queue<E>, java.io.Serializable {
39
40			/*
41			* This is a straight adaptation of Michael & Scott algorithm.
42			* For explanation, read the paper. The only (minor) algorithmic
43			* difference is that this version supports lazy deletion of
44			* internal nodes (method remove(Object)) -- remove CAS'es item
45			* fields to null. The normal queue operations unlink but then
46			* pass over nodes with null item fields. Similarly, iteration
47			* methods ignore those with nulls.
48			*/
49
50			// Atomics support
51
52	dl	1.5	private static final
53			AtomicReferenceFieldUpdater<ConcurrentLinkedQueue, AtomicLinkedNode>
54			tailUpdater =
55			AtomicReferenceFieldUpdater.newUpdater
56			(ConcurrentLinkedQueue.class, AtomicLinkedNode.class, "tail");
57			private static final
58			AtomicReferenceFieldUpdater<ConcurrentLinkedQueue, AtomicLinkedNode>
59			headUpdater =
60			AtomicReferenceFieldUpdater.newUpdater
61			(ConcurrentLinkedQueue.class, AtomicLinkedNode.class, "head");
62	dl	1.1
63			private boolean casTail(AtomicLinkedNode cmp, AtomicLinkedNode val) {
64			return tailUpdater.compareAndSet(this, cmp, val);
65			}
66
67			private boolean casHead(AtomicLinkedNode cmp, AtomicLinkedNode val) {
68			return headUpdater.compareAndSet(this, cmp, val);
69			}
70
71
72	tim	1.2	/**
73	dl	1.1	* Pointer to header node, initialized to a dummy node. The first
74			* actual node is at head.getNext().
75			*/
76			private transient volatile AtomicLinkedNode head = new AtomicLinkedNode(null, null);
77
78			/ Pointer to last node on list /
79			private transient volatile AtomicLinkedNode tail = head;
80
81
82			/**
83	dholmes	1.6	* Creates a <tt>ConcurrentLinkedQueue</tt> that is initially empty.
84	dl	1.1	*/
85			public ConcurrentLinkedQueue() {}
86
87			/**
88	dholmes	1.6	* Creates a <tt>ConcurrentLinkedQueue</tt>
89	dholmes	1.7	* initially containing the elements of the given collection,
90	dholmes	1.6	* added in traversal order of the collection's iterator.
91			* @param c the collection of elements to initially contain
92			* @throws NullPointerException if <tt>c</tt> or any element within it
93			* is <tt>null</tt>
94	dl	1.1	*/
95	dholmes	1.6	public ConcurrentLinkedQueue(Collection<? extends E> c) {
96			for (Iterator<? extends E> it = c.iterator(); it.hasNext();)
97	dl	1.1	add(it.next());
98			}
99
100	dholmes	1.7	// Have to override just to update the javadoc
101	dholmes	1.6
102			/**
103	dholmes	1.7	* Adds the specified element to the tail of this queue.
104			* @return <tt>true</tt> (as per the general contract of
105			* <tt>Collection.add</tt>).
106			*
107	dholmes	1.6	* @throws NullPointerException {@inheritDoc}
108			*/
109			public boolean add(E o) {
110			return super.add(o);
111			}
112
113			/**
114	dholmes	1.7	* Adds all of the elements in the specified collection to this queue.
115			* The behavior of this operation is undefined if
116			* the specified collection is modified while the operation is in
117			* progress. (This implies that the behavior of this call is undefined if
118			* the specified collection is this queue, and this queue is nonempty.)
119			* <p>
120			* This implementation iterates over the specified collection, and adds
121			* each object returned by the iterator to this queue's tail, in turn.
122	dholmes	1.6	* @throws NullPointerException {@inheritDoc}
123			*/
124			public boolean addAll(Collection<? extends E> c) {
125			return super.addAll(c);
126			}
127
128			/**
129			* @throws NullPointerException if the specified element is <tt>null</tt>
130			*/
131			public boolean offer(E o) {
132			if (o == null) throw new NullPointerException();
133			AtomicLinkedNode n = new AtomicLinkedNode(o, null);
134	dl	1.1	for(;;) {
135			AtomicLinkedNode t = tail;
136			AtomicLinkedNode s = t.getNext();
137			if (t == tail) {
138			if (s == null) {
139			if (t.casNext(s, n)) {
140	tim	1.2	casTail(t, n);
141	dl	1.1	return true;
142			}
143			}
144			else {
145			casTail(t, s);
146			}
147			}
148			}
149			}
150
151			public E poll() {
152			for (;;) {
153			AtomicLinkedNode h = head;
154			AtomicLinkedNode t = tail;
155			AtomicLinkedNode first = h.getNext();
156			if (h == head) {
157			if (h == t) {
158			if (first == null)
159			return null;
160			else
161			casTail(t, first);
162			}
163			else if (casHead(h, first)) {
164			E item = (E)first.getItem();
165			if (item != null) {
166			first.setItem(null);
167			return item;
168			}
169	tim	1.2	// else skip over deleted item, continue loop,
170	dl	1.1	}
171			}
172			}
173			}
174
175			public E peek() { // same as poll except don't remove item
176			for (;;) {
177			AtomicLinkedNode h = head;
178			AtomicLinkedNode t = tail;
179			AtomicLinkedNode first = h.getNext();
180			if (h == head) {
181			if (h == t) {
182			if (first == null)
183			return null;
184			else
185			casTail(t, first);
186			}
187			else {
188			E item = (E)first.getItem();
189			if (item != null)
190			return item;
191			else // remove deleted node and continue
192			casHead(h, first);
193			}
194			}
195			}
196			}
197
198			/**
199	dholmes	1.6	* Returns the first actual (non-header) node on list. This is yet
200	dl	1.1	* another variant of poll/peek; here returning out the first
201			* node, not element (so we cannot collapse with peek() without
202			* introducing race.)
203			*/
204	tim	1.2	AtomicLinkedNode first() {
205	dl	1.1	for (;;) {
206			AtomicLinkedNode h = head;
207			AtomicLinkedNode t = tail;
208			AtomicLinkedNode first = h.getNext();
209			if (h == head) {
210			if (h == t) {
211			if (first == null)
212			return null;
213			else
214			casTail(t, first);
215			}
216			else {
217			if (first.getItem() != null)
218			return first;
219			else // remove deleted node and continue
220			casHead(h, first);
221			}
222			}
223			}
224			}
225
226
227			public boolean isEmpty() {
228			return first() == null;
229			}
230
231			/**
232	tim	1.11	* {@inheritDoc}
233	tim	1.2	*
234	tim	1.11	* Beware that, unlike in most collections, this method is
235	dl	1.1	* <em>NOT</em> a constant-time operation. Because of the
236			* asynchronous nature of these queues, determining the current
237			* number of elements requires an O(n) traversal.
238	tim	1.2	*/
239	dl	1.1	public int size() {
240			int count = 0;
241			for (AtomicLinkedNode p = first(); p != null; p = p.getNext()) {
242	dl	1.8	if (p.getItem() != null) {
243			// Collections.size() spec says to max out
244			if (++count == Integer.MAX_VALUE)
245			break;
246			}
247	dl	1.1	}
248			return count;
249			}
250
251	dholmes	1.6	public boolean contains(Object o) {
252			if (o == null) return false;
253	dl	1.1	for (AtomicLinkedNode p = first(); p != null; p = p.getNext()) {
254			Object item = p.getItem();
255	tim	1.2	if (item != null &&
256	dholmes	1.6	o.equals(item))
257	dl	1.1	return true;
258			}
259			return false;
260			}
261
262	dholmes	1.7	/**
263			* Removes a single instance of the specified element from this
264			* queue, if it is present. More formally,
265			* removes an element <tt>e</tt> such that <tt>(o==null ? e==null :
266			* o.equals(e))</tt>, if the queue contains one or more such
267			* elements. Returns <tt>true</tt> if the queue contained the
268			* specified element (or equivalently, if the queue changed as a
269			* result of the call).
270			*
271			* <p>This implementation iterates over the queue looking for the
272			* specified element. If it finds the element, it removes the element
273			* from the queue using the iterator's remove method.<p>
274			*
275			*/
276	dholmes	1.6	public boolean remove(Object o) {
277			if (o == null) return false;
278	dl	1.1	for (AtomicLinkedNode p = first(); p != null; p = p.getNext()) {
279			Object item = p.getItem();
280	tim	1.2	if (item != null &&
281	dholmes	1.6	o.equals(item) &&
282	dl	1.1	p.casItem(item, null))
283			return true;
284			}
285			return false;
286			}
287	tim	1.2
288	dl	1.1	public Object[] toArray() {
289			// Use ArrayList to deal with resizing.
290	tim	1.3	ArrayList<E> al = new ArrayList<E>();
291	dl	1.1	for (AtomicLinkedNode p = first(); p != null; p = p.getNext()) {
292	tim	1.3	E item = (E) p.getItem();
293	dl	1.1	if (item != null)
294			al.add(item);
295			}
296			return al.toArray();
297			}
298
299			public <T> T[] toArray(T[] a) {
300			// try to use sent-in array
301			int k = 0;
302			AtomicLinkedNode p;
303			for (p = first(); p != null && k < a.length; p = p.getNext()) {
304			Object item = p.getItem();
305			if (item != null)
306			a[k++] = (T)item;
307			}
308			if (p == null) {
309			if (k < a.length)
310			a[k] = null;
311			return a;
312			}
313
314			// If won't fit, use ArrayList version
315	tim	1.3	ArrayList<E> al = new ArrayList<E>();
316	dl	1.1	for (AtomicLinkedNode q = first(); q != null; q = q.getNext()) {
317	tim	1.3	E item = (E) q.getItem();
318	dl	1.1	if (item != null)
319			al.add(item);
320			}
321			return (T[])al.toArray(a);
322			}
323
324	dholmes	1.7	/**
325			* Returns an iterator over the elements in this queue in proper sequence.
326	dl	1.9	* The returned iterator is a "weakly consistent" iterator that
327			* will never throw {@link java.util.ConcurrentModificationException},
328			* and guarantees to traverse elements as they existed upon
329			* construction of the iterator, and may (but is not guaranteed to)
330			* reflect any modifications subsequent to construction.
331	dholmes	1.7	*
332			* @return an iterator over the elements in this queue in proper sequence.
333			*/
334	dl	1.1	public Iterator<E> iterator() {
335			return new Itr();
336			}
337
338			private class Itr implements Iterator<E> {
339			/**
340			* Next node to return item for.
341			*/
342			private AtomicLinkedNode nextNode;
343
344	tim	1.2	/**
345	dl	1.1	* nextItem holds on to item fields because once we claim
346			* that an element exists in hasNext(), we must return it in
347			* the following next() call even if it was in the process of
348			* being removed when hasNext() was called.
349			**/
350			private E nextItem;
351
352			/**
353			* Node of the last returned item, to support remove.
354			*/
355			private AtomicLinkedNode lastRet;
356
357	tim	1.2	Itr() {
358	dl	1.1	advance();
359			}
360	tim	1.2
361	dl	1.1	/**
362	tim	1.2	* Move to next valid node.
363	dl	1.1	* Return item to return for next(), or null if no such.
364			*/
365	tim	1.2	private E advance() {
366	dl	1.1	lastRet = nextNode;
367			E x = (E)nextItem;
368
369			AtomicLinkedNode p = (nextNode == null)? first() : nextNode.getNext();
370			for (;;) {
371			if (p == null) {
372			nextNode = null;
373			nextItem = null;
374			return x;
375			}
376			E item = (E)p.getItem();
377			if (item != null) {
378			nextNode = p;
379			nextItem = item;
380			return x;
381			}
382	tim	1.2	else // skip over nulls
383	dl	1.1	p = p.getNext();
384			}
385			}
386	tim	1.2
387	dl	1.1	public boolean hasNext() {
388			return nextNode != null;
389			}
390	tim	1.2
391	dl	1.1	public E next() {
392			if (nextNode == null) throw new NoSuchElementException();
393			return advance();
394			}
395	tim	1.2
396	dl	1.1	public void remove() {
397			AtomicLinkedNode l = lastRet;
398			if (l == null) throw new IllegalStateException();
399			// rely on a future traversal to relink.
400			l.setItem(null);
401			lastRet = null;
402			}
403			}
404
405			/**
406			* Save the state to a stream (that is, serialize it).
407			*
408			* @serialData All of the elements (each an <tt>E</tt>) in
409			* the proper order, followed by a null
410			* @param s the stream
411			*/
412			private void writeObject(java.io.ObjectOutputStream s)
413			throws java.io.IOException {
414
415			// Write out any hidden stuff
416			s.defaultWriteObject();
417	tim	1.2
418	dl	1.1	// Write out all elements in the proper order.
419			for (AtomicLinkedNode p = first(); p != null; p = p.getNext()) {
420			Object item = p.getItem();
421			if (item != null)
422			s.writeObject(item);
423			}
424
425			// Use trailing null as sentinel
426			s.writeObject(null);
427			}
428
429			/**
430			* Reconstitute the Queue instance from a stream (that is,
431			* deserialize it).
432			* @param s the stream
433			*/
434			private void readObject(java.io.ObjectInputStream s)
435			throws java.io.IOException, ClassNotFoundException {
436	tim	1.2	// Read in capacity, and any hidden stuff
437			s.defaultReadObject();
438	dl	1.1
439	tim	1.2	// Read in all elements and place in queue
440	dl	1.1	for (;;) {
441			E item = (E)s.readObject();
442			if (item == null)
443			break;
444			add(item);
445			}
446			}
447
448			}