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 implements all of the <em>optional</em> methods
 * of the {@link Collection} and {@link Iterator} interfaces.
 *
 * <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 <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.
     * @param o the element to add.
     * @return <tt>true</tt> (as per the general contract of
     * <tt>Collection.add</tt>).
     *
     * @throws NullPointerException if the specified element is <tt>null</tt>
     */
    public boolean add(E o) {
        return offer(o);
    }

    /**
     * Inserts the specified element to the tail of this queue.
     *
     * @param o the element to add.
     * @return <tt>true</tt> (as per the general contract of
     * <tt>Queue.offer</tt>).
     * @throws NullPointerException if the specified element is <tt>null</tt>
     */
    public boolean offer(E o) {
        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 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);
                }
            }
        }
    }


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

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

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

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

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