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

    /**
     * Adds the specified element to the tail of this queue.
     *
     * @return <tt>true</tt> (as per the spec for {@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 per the spec for {@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;
    }

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

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