util/concurrent/ConcurrentLinkedQueue.java

/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain. Use, modify, and
 * redistribute this code in any way without acknowledgement.
 */

package java.util.concurrent;
import java.util.*;
import java.util.concurrent.atomic.*;


/**
 * An unbounded thread-safe {@linkplain Queue queue} based on linked nodes.  
 * This queue orders elements FIFO (first-in-first-out).
 * The <em>head</em> of the queue is that element that has been on the
 * queue the longest time.
 * The <em>tail</em> of the queue is that element that has been on the
 * queue the shortest time. 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.
 *
 * @since 1.5
 * @author Doug Lea
 * @param <E> the base class of all 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 AtomicLinkedNode {
        private volatile Object item;
        private volatile AtomicLinkedNode next;
        
        private static final 
            AtomicReferenceFieldUpdater<AtomicLinkedNode, AtomicLinkedNode> 
            nextUpdater =
            AtomicReferenceFieldUpdater.newUpdater
            (AtomicLinkedNode.class, AtomicLinkedNode.class, "next");
        private static final 
            AtomicReferenceFieldUpdater<AtomicLinkedNode, Object> 
            itemUpdater =
            AtomicReferenceFieldUpdater.newUpdater
            (AtomicLinkedNode.class, Object.class, "item");
        
        AtomicLinkedNode(Object x) { item = x; }
        
        AtomicLinkedNode(Object x, AtomicLinkedNode n) { item = x; next = n; }
        
        Object getItem() {
            return item;
        }
        
        boolean casItem(Object cmp, Object val) {
            return itemUpdater.compareAndSet(this, cmp, val);
        }
        
        void setItem(Object val) {
            itemUpdater.set(this, val);
        }
        
        AtomicLinkedNode getNext() {
            return next;
        }
        
        boolean casNext(AtomicLinkedNode cmp, AtomicLinkedNode val) {
            return nextUpdater.compareAndSet(this, cmp, val);
        }
        
        void setNext(AtomicLinkedNode val) {
            nextUpdater.set(this, val);
        }
        
    }

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

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

    private boolean casHead(AtomicLinkedNode cmp, AtomicLinkedNode val) {
        return headUpdater.compareAndSet(this, cmp, val);
    }


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

    /** Pointer to last node on list **/
    private transient volatile AtomicLinkedNode tail = head;


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

    /**
     * Creates a <tt>ConcurrentLinkedQueue</tt> 
     * initially containing the elements of the given collection,
     * added in traversal order of the collection's iterator.
     * @param c the collection of elements to initially contain
     * @throws NullPointerException if <tt>c</tt> or any element within it
     * is <tt>null</tt>
     */
    public ConcurrentLinkedQueue(Collection<? extends E> c) {
        for (Iterator<? extends E> it = c.iterator(); it.hasNext();)
            add(it.next());
    }

    // Have to override just to update the javadoc 

    /**
     * Adds the specified element to the tail of this queue.
     * @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();
        AtomicLinkedNode n = new AtomicLinkedNode(o, null);
        for(;;) {
            AtomicLinkedNode t = tail;
            AtomicLinkedNode s = t.getNext();
            if (t == tail) {
                if (s == null) {
                    if (t.casNext(s, n)) {
                        casTail(t, n);
                        return true;
                    }
                } else {
                    casTail(t, s);
                }
            }
        }
    }

    public E poll() {
        for (;;) {
            AtomicLinkedNode h = head;
            AtomicLinkedNode t = tail;
            AtomicLinkedNode first = h.getNext();
            if (h == head) {
                if (h == t) {
                    if (first == null)
                        return null;
                    else
                        casTail(t, first);
                } else if (casHead(h, first)) {
                    E item = (E)first.getItem();
                    if (item != null) {
                        first.setItem(null);
                        return item;
                    }
                    // else skip over deleted item, continue loop,
                }
            }
        }
    }

    public E peek() { // same as poll except don't remove item
        for (;;) {
            AtomicLinkedNode h = head;
            AtomicLinkedNode t = tail;
            AtomicLinkedNode first = h.getNext();
            if (h == head) {
                if (h == t) {
                    if (first == null)
                        return null;
                    else
                        casTail(t, first);
                } else {
                    E item = (E)first.getItem();
                    if (item != null)
                        return item;
                    else // remove deleted node and continue
                        casHead(h, first);
                }
            }
        }
    }

    /**
     * Returns the first actual (non-header) node on list.  This is yet
     * another variant of poll/peek; here returning out the first
     * node, not element (so we cannot collapse with peek() without
     * introducing race.)
     */
    AtomicLinkedNode first() {
        for (;;) {
            AtomicLinkedNode h = head;
            AtomicLinkedNode t = tail;
            AtomicLinkedNode first = h.getNext();
            if (h == head) {
                if (h == t) {
                    if (first == null)
                        return null;
                    else
                        casTail(t, first);
                } else {
                    if (first.getItem() != null)
                        return first;
                    else // remove deleted node and continue
                        casHead(h, first);
                }
            }
        }
    }


    public boolean isEmpty() {
        return first() == null;
    }

    /**
     * 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 (AtomicLinkedNode p = first(); p != null; p = p.getNext()) {
            if (p.getItem() != null) {
                // Collections.size() spec says to max out
                if (++count == Integer.MAX_VALUE)
                    break;
            }
        }
        return count;
    }

    public boolean contains(Object o) {
        if (o == null) return false;
        for (AtomicLinkedNode p = first(); p != null; p = p.getNext()) {
            Object item = p.getItem();
            if (item != null &&
                o.equals(item))
                return true;
        }
        return false;
    }

    public boolean remove(Object o) {
        if (o == null) return false;
        for (AtomicLinkedNode p = first(); p != null; p = p.getNext()) {
            Object item = p.getItem();
            if (item != null &&
                o.equals(item) &&
                p.casItem(item, null))
                return true;
        }
        return false;
    }

    public Object[] toArray() {
        // Use ArrayList to deal with resizing.
        ArrayList<E> al = new ArrayList<E>();
        for (AtomicLinkedNode p = first(); p != null; p = p.getNext()) {
            E item = (E) p.getItem();
            if (item != null)
                al.add(item);
        }
        return al.toArray();
    }

    public <T> T[] toArray(T[] a) {
        // try to use sent-in array
        int k = 0;
        AtomicLinkedNode p;
        for (p = first(); p != null && k < a.length; p = p.getNext()) {
            Object item = p.getItem();
            if (item != null)
                a[k++] = (T)item;
        }
        if (p == null) {
            if (k < a.length)
                a[k] = null;
            return a;
        }

        // If won't fit, use ArrayList version
        ArrayList<E> al = new ArrayList<E>();
        for (AtomicLinkedNode q = first(); q != null; q = q.getNext()) {
            E item = (E) q.getItem();
            if (item != null)
                al.add(item);
        }
        return (T[])al.toArray(a);
    }

    /**
     * Returns an iterator over the elements in this queue in proper sequence.
     * The returned iterator is a "weakly consistent" iterator that
     * will never throw {@link java.util.ConcurrentModificationException},
     * and guarantees to traverse elements as they existed upon
     * construction of the iterator, and may (but is not guaranteed to)
     * reflect any modifications subsequent to construction.
     *
     * @return an iterator over the elements in this queue in proper sequence.
     */
    public Iterator<E> iterator() {
        return new Itr();
    }

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

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

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

        Itr() {
            advance();
        }

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

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

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

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

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

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

        // Write out any hidden stuff
        s.defaultWriteObject();

        // Write out all elements in the proper order.
        for (AtomicLinkedNode p = first(); p != null; p = p.getNext()) {
            Object item = p.getItem();
            if (item != null)
                s.writeObject(item);
        }

        // Use trailing null as sentinel
        s.writeObject(null);
    }

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