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


    /**
     * Returns <tt>true</tt> if this collection contains no elements.<p>
     *
     * @return <tt>true</tt> if this collection 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;
    }

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