util/concurrent/ConcurrentLinkedStack.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.*;

/**
 * A stack based on a linked list using atomic operations for adding
 * (pushing) and removing (popping) elements. The <tt>add</tt>
 * method performs a <em>push</em>, <tt>remove</tt> performs a
 * <em>pop</em>. Other methods similarly map to stack-based
 * last-in-first-out (LIFO) operations.
 * 
 * In addition to its use as a stack, this class is useful as an
 * efficient concurrently accessible "bag", a collection to hold and
 * traverse items across many threads in which you do not care about
 * ordering.
 *
 * <p> This collection does not support the use of <tt>null</tt> as
 * elements.
 *
 * <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 stacks, determining the current number
 * of elements requires an O(n) traversal.
 * @since 1.5
 * @author Doug Lea
**/

public class ConcurrentLinkedStack<E> extends AbstractQueue<E>
        implements Queue<E>, java.io.Serializable {

    /*
     * The basic strategy here relies on a classic linked-list stack,
     * using CAS to relink head on push and pop. The implementation is
     * a little more complicated than this though because the class
     * must support of arbitrary deletion (remove(Object x)). 
     * Rather than just lazily nulling out nodes, and skipping
     * them when they reach top, we detect and relink around nodes
     * as they are removed. This is still partially lazy though.
     * Multiple adjacent concurrent relinks may leave nulls in place,
     * so all traversals must detect and relink lingering nulls.
     */

    /** Head of the linked list */
    private transient volatile AtomicLinkedNode head;

    private static final AtomicReferenceFieldUpdater<ConcurrentLinkedStack, AtomicLinkedNode> headUpdater = new AtomicReferenceFieldUpdater<ConcurrentLinkedStack, AtomicLinkedNode>(new ConcurrentLinkedStack[0], new AtomicLinkedNode[0], "head");

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

    /**
     * Creates an initially empty ConcurrentLinkedStack.
     */
    public ConcurrentLinkedStack() {
    }

    /**
     * Creates a ConcurrentLinkedStack initially holding the elements
     * of the given collection. The elements are added in 
     * iterator traversal order.
     *
     * @param initialElements the collections whose elements are to be added.
     */
    public ConcurrentLinkedStack(Collection<E> initialElements) {
        for (Iterator<E> it = initialElements.iterator(); it.hasNext();) 
            add(it.next());
    }

    /**
     * Relink over a deleted item; return next node.  This is called
     * whenever a null item field is encountered during any traversal.
     * This is necessary (although rare) because a previous remove()
     * could have linked one node to another node that was also in the
     * process of being removed. Also, iterator.remove exploits the fact
     * that nulls are cleaned out later to allow fully lazy deletion
     * that would otherwise be O(n). 
     * @param deleted the deleted node. Precondition: deleted.item==null.
     * @param previous the node before deleted, or null if deleted is first node
     * @return the next node after previous, or first node if no previous.
     **/
    private AtomicLinkedNode skip(AtomicLinkedNode previous, AtomicLinkedNode deleted) {
        if (previous == null) {
            casHead(deleted, deleted.getNext());
            return head.getNext(); 
        }
        else {
            previous.casNext(deleted, deleted.getNext());
            return previous.getNext();
        }
    }

    /**
     * Pushes the given element on the stack.
     * @param x the element to insert
     * @return true -- (as per the general contract of Queue.offer). 
     * @throws NullPointerException if x is null
     **/
    public boolean offer(E x) {
        if (x == null) throw new NullPointerException();
        AtomicLinkedNode p = new AtomicLinkedNode(x);
        for (;;) {
            AtomicLinkedNode h = head;
            p.setNext(h); 
            if (casHead(h, p))
                return true;
        }
    }

    /**
     * Returns the top element of this stack, or null if empty.
     * @return the top element of this stack, or null if empty.
     **/
    public E peek() {
        AtomicLinkedNode previous = null;
        AtomicLinkedNode p = head;
        while (p != null) {
            Object item = p.getItem();
            if (item == null) 
                p = skip(previous, p);
            else 
                return (E)item;
        }
        return null;
    }
    
    /**
     * Removes and returns the top element of this stack, or null if empty.
     * @return the top element of this stack, or null if empty.
     **/
    public E poll() {
        AtomicLinkedNode previous = null;
        AtomicLinkedNode p = head;
        while (p != null) {
            Object item = p.getItem();
            if (item == null) 
                p = skip(previous, p);
            else {
                p.setItem(null);
                skip(previous, p);
                return (E)item;
            }
        }
        return null;
    }    

    public boolean isEmpty() {
        AtomicLinkedNode previous = null;
        AtomicLinkedNode p = head;
        while (p != null) {
            Object item = p.getItem();
            if (item == null) 
                p = skip(previous, p);
            else 
                return false;
        }
        return true;
    }

    /**
     * Returns the number of elements in this collection. 
     * 
     * Beware that, unlike in most collection, 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 collection
     */ 
    public int size() {
        int count = 0;
        AtomicLinkedNode previous = null;
        AtomicLinkedNode p = head;
        while (p != null) {
            Object item = p.getItem();
            if (item == null) 
                p = skip(previous, p);
            else {
                ++count;
                previous = p;
                p = p.getNext();
            }
        }
        return count;
    }

    public boolean remove(Object x) {
        /*
         * Algorithm:
         *   1. Find node
         *        Clean up after any previous removes while doing so.
         *   2. Null out item field
         *        This will be noticed by other traversals, that will ignore 
         *        it and/or help remove it. 
         *   3. Relink previous node to next node.
         *        If the next node is also in the process of being removed,
         *        this may leave a nulled node in the list. We clean this up
         *        during any traversal.
         */

        if (x == null) return false; // nulls never present

        AtomicLinkedNode previous = null;
        AtomicLinkedNode p = head;
        while (p != null) {
            Object item = p.getItem();
            if (item == null) 
                p = skip(previous, p);
            else if (x.equals(item) && p.casItem(item, null)) {
                skip(previous, p);
                return true;
            }
            else {
                previous = p;
                p = p.getNext();
            }
        }
        return false;
    }

    public boolean contains(Object x) {
        if (x == null) return false; // nulls never present

        AtomicLinkedNode previous = null;
        AtomicLinkedNode p = head;
        while (p != null) {
            Object item = p.getItem();
            if (item == null) 
                p = skip(previous, p);
            else if (x.equals(item))
                return true;
            else {
                previous = p;
                p = p.getNext();
            }
        }
        return false;
    }

    public Object[] toArray() {
        // Use ArrayList to deal with resizing.
        ArrayList al = new ArrayList();
        AtomicLinkedNode previous = null;
        AtomicLinkedNode p = head;
        while (p != null) {
            Object item = p.getItem();
            if (item == null) 
                p = skip(previous, p);
            else {
                al.add(item);
                previous = p;
                p = p.getNext();
            }
        }

        return al.toArray();
    }

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

        // If won't fit, use ArrayList version
        ArrayList al = new ArrayList();
        previous = null;
        p = head;
        while (p != null) {
            Object item = p.getItem();
            if (item == null) 
                p = skip(previous, p);
            else {
                al.add(item);
                previous = p;
                p = p.getNext();
            }
        }
        return (T[])al.toArray(a);
    }

    public Iterator<E> iterator() { return new Itr(); }

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

        /** 
         * We need to hold on to item fields here 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;

        /**
         * Move to next valid node. 
         * Return item to return for next(), or null if no such.
         */
        private E advance() { 
            lastRet = nextNode;
            E x = nextItem;
            
            AtomicLinkedNode p = (nextNode == null) ? head : nextNode.getNext();
            for (;;) {
                if (p == null) {
                    nextNode = null;
                    nextItem = null;
                    return x;
                }
                Object item = p.getItem();
                if (item == null) 
                    p = skip(nextNode, p);
                else {
                    nextNode = p;
                    nextItem = (E)item;
                    return x;
                }
            }
        }

        Itr() { 
            advance();
        }

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

        AtomicLinkedNode previous = null;
        AtomicLinkedNode p = head;
        while (p != null) {
            Object item = p.getItem();
            if (item == null) 
                p = skip(previous, p);
            else {
                s.writeObject(item);
                previous = p;
                p = p.getNext();
            }
        }
        
        // Use trailing null as sentinel
        s.writeObject(null);
    }

    /**
     * Reconstitute the Queue instance from a stream (that is,
     * deserialize it).
     * @param s the stream
     */
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in capacity, and any hidden stuff
        s.defaultReadObject();

        // Read in all elements into array and then insert in reverse order.
        ArrayList<E> al = new ArrayList<E>();
        for (;;) {
            E item = (E)s.readObject();
            if (item == null)
                break;
            al.add(item);
        }

        ListIterator<E> it = al.listIterator(al.size());
        while (it.hasPrevious())
            add(it.previous());
    }


}

Revision:	1.2
Committed:	Mon Jul 14 19:54:18 2003 UTC (20 years, 10 months ago) by dl
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.1:	+0 -0 lines
State:	*FILE REMOVED*
Log Message:	Re-removed ConcurrentLinkedStack?
#	Content
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	* A stack based on a linked list using atomic operations for adding
13	* (pushing) and removing (popping) elements. The <tt>add</tt>
14	* method performs a <em>push</em>, <tt>remove</tt> performs a
15	* <em>pop</em>. Other methods similarly map to stack-based
16	* last-in-first-out (LIFO) operations.
17	*
18	* In addition to its use as a stack, this class is useful as an
19	* efficient concurrently accessible "bag", a collection to hold and
20	* traverse items across many threads in which you do not care about
21	* ordering.
22	*
23	* <p> This collection does not support the use of <tt>null</tt> as
24	* elements.
25	*
26	* <p> Beware that, unlike in most collections, the <tt>size</tt>
27	* method is <em>NOT</em> a constant-time operation. Because of the
28	* asynchronous nature of these stacks, determining the current number
29	* of elements requires an O(n) traversal.
30	* @since 1.5
31	* @author Doug Lea
32	**/
33
34	public class ConcurrentLinkedStack<E> extends AbstractQueue<E>
35	implements Queue<E>, java.io.Serializable {
36
37	/*
38	* The basic strategy here relies on a classic linked-list stack,
39	* using CAS to relink head on push and pop. The implementation is
40	* a little more complicated than this though because the class
41	* must support of arbitrary deletion (remove(Object x)).
42	* Rather than just lazily nulling out nodes, and skipping
43	* them when they reach top, we detect and relink around nodes
44	* as they are removed. This is still partially lazy though.
45	* Multiple adjacent concurrent relinks may leave nulls in place,
46	* so all traversals must detect and relink lingering nulls.
47	*/
48
49	/** Head of the linked list */
50	private transient volatile AtomicLinkedNode head;
51
52	private static final AtomicReferenceFieldUpdater<ConcurrentLinkedStack, AtomicLinkedNode> headUpdater = new AtomicReferenceFieldUpdater<ConcurrentLinkedStack, AtomicLinkedNode>(new ConcurrentLinkedStack[0], new AtomicLinkedNode[0], "head");
53
54	private boolean casHead(AtomicLinkedNode cmp, AtomicLinkedNode val) {
55	return headUpdater.compareAndSet(this, cmp, val);
56	}
57
58
59	/**
60	* Creates an initially empty ConcurrentLinkedStack.
61	*/
62	public ConcurrentLinkedStack() {
63	}
64
65	/**
66	* Creates a ConcurrentLinkedStack initially holding the elements
67	* of the given collection. The elements are added in
68	* iterator traversal order.
69	*
70	* @param initialElements the collections whose elements are to be added.
71	*/
72	public ConcurrentLinkedStack(Collection<E> initialElements) {
73	for (Iterator<E> it = initialElements.iterator(); it.hasNext();)
74	add(it.next());
75	}
76
77	/**
78	* Relink over a deleted item; return next node. This is called
79	* whenever a null item field is encountered during any traversal.
80	* This is necessary (although rare) because a previous remove()
81	* could have linked one node to another node that was also in the
82	* process of being removed. Also, iterator.remove exploits the fact
83	* that nulls are cleaned out later to allow fully lazy deletion
84	* that would otherwise be O(n).
85	* @param deleted the deleted node. Precondition: deleted.item==null.
86	* @param previous the node before deleted, or null if deleted is first node
87	* @return the next node after previous, or first node if no previous.
88	**/
89	private AtomicLinkedNode skip(AtomicLinkedNode previous, AtomicLinkedNode deleted) {
90	if (previous == null) {
91	casHead(deleted, deleted.getNext());
92	return head.getNext();
93	}
94	else {
95	previous.casNext(deleted, deleted.getNext());
96	return previous.getNext();
97	}
98	}
99
100	/**
101	* Pushes the given element on the stack.
102	* @param x the element to insert
103	* @return true -- (as per the general contract of Queue.offer).
104	* @throws NullPointerException if x is null
105	**/
106	public boolean offer(E x) {
107	if (x == null) throw new NullPointerException();
108	AtomicLinkedNode p = new AtomicLinkedNode(x);
109	for (;;) {
110	AtomicLinkedNode h = head;
111	p.setNext(h);
112	if (casHead(h, p))
113	return true;
114	}
115	}
116
117	/**
118	* Returns the top element of this stack, or null if empty.
119	* @return the top element of this stack, or null if empty.
120	**/
121	public E peek() {
122	AtomicLinkedNode previous = null;
123	AtomicLinkedNode p = head;
124	while (p != null) {
125	Object item = p.getItem();
126	if (item == null)
127	p = skip(previous, p);
128	else
129	return (E)item;
130	}
131	return null;
132	}
133
134	/**
135	* Removes and returns the top element of this stack, or null if empty.
136	* @return the top element of this stack, or null if empty.
137	**/
138	public E poll() {
139	AtomicLinkedNode previous = null;
140	AtomicLinkedNode p = head;
141	while (p != null) {
142	Object item = p.getItem();
143	if (item == null)
144	p = skip(previous, p);
145	else {
146	p.setItem(null);
147	skip(previous, p);
148	return (E)item;
149	}
150	}
151	return null;
152	}
153
154	public boolean isEmpty() {
155	AtomicLinkedNode previous = null;
156	AtomicLinkedNode p = head;
157	while (p != null) {
158	Object item = p.getItem();
159	if (item == null)
160	p = skip(previous, p);
161	else
162	return false;
163	}
164	return true;
165	}
166
167	/**
168	* Returns the number of elements in this collection.
169	*
170	* Beware that, unlike in most collection, this method> is
171	* <em>NOT</em> a constant-time operation. Because of the
172	* asynchronous nature of these queues, determining the current
173	* number of elements requires an O(n) traversal.
174	* @return the number of elements in this collection
175	*/
176	public int size() {
177	int count = 0;
178	AtomicLinkedNode previous = null;
179	AtomicLinkedNode p = head;
180	while (p != null) {
181	Object item = p.getItem();
182	if (item == null)
183	p = skip(previous, p);
184	else {
185	++count;
186	previous = p;
187	p = p.getNext();
188	}
189	}
190	return count;
191	}
192
193	public boolean remove(Object x) {
194	/*
195	* Algorithm:
196	* 1. Find node
197	* Clean up after any previous removes while doing so.
198	* 2. Null out item field
199	* This will be noticed by other traversals, that will ignore
200	* it and/or help remove it.
201	* 3. Relink previous node to next node.
202	* If the next node is also in the process of being removed,
203	* this may leave a nulled node in the list. We clean this up
204	* during any traversal.
205	*/
206
207	if (x == null) return false; // nulls never present
208
209	AtomicLinkedNode previous = null;
210	AtomicLinkedNode p = head;
211	while (p != null) {
212	Object item = p.getItem();
213	if (item == null)
214	p = skip(previous, p);
215	else if (x.equals(item) && p.casItem(item, null)) {
216	skip(previous, p);
217	return true;
218	}
219	else {
220	previous = p;
221	p = p.getNext();
222	}
223	}
224	return false;
225	}
226
227	public boolean contains(Object x) {
228	if (x == null) return false; // nulls never present
229
230	AtomicLinkedNode previous = null;
231	AtomicLinkedNode p = head;
232	while (p != null) {
233	Object item = p.getItem();
234	if (item == null)
235	p = skip(previous, p);
236	else if (x.equals(item))
237	return true;
238	else {
239	previous = p;
240	p = p.getNext();
241	}
242	}
243	return false;
244	}
245
246	public Object[] toArray() {
247	// Use ArrayList to deal with resizing.
248	ArrayList al = new ArrayList();
249	AtomicLinkedNode previous = null;
250	AtomicLinkedNode p = head;
251	while (p != null) {
252	Object item = p.getItem();
253	if (item == null)
254	p = skip(previous, p);
255	else {
256	al.add(item);
257	previous = p;
258	p = p.getNext();
259	}
260	}
261
262	return al.toArray();
263	}
264
265	public <T> T[] toArray(T[] a) {
266	// try to use sent-in array
267	int k = 0;
268	AtomicLinkedNode previous = null;
269	AtomicLinkedNode p = head;
270	while (p != null && k < a.length) {
271	Object item = p.getItem();
272	if (item == null)
273	p = skip(previous, p);
274	else {
275	a[k++] = (T)item;
276	previous = p;
277	p = p.getNext();
278	}
279	}
280	if (p == null) {
281	if (k < a.length)
282	a[k] = null;
283	return a;
284	}
285
286	// If won't fit, use ArrayList version
287	ArrayList al = new ArrayList();
288	previous = null;
289	p = head;
290	while (p != null) {
291	Object item = p.getItem();
292	if (item == null)
293	p = skip(previous, p);
294	else {
295	al.add(item);
296	previous = p;
297	p = p.getNext();
298	}
299	}
300	return (T[])al.toArray(a);
301	}
302
303	public Iterator<E> iterator() { return new Itr(); }
304
305	private class Itr implements Iterator<E> {
306	/**
307	* Next node to return item for.
308	*/
309	private AtomicLinkedNode nextNode;
310
311	/**
312	* We need to hold on to item fields here because once we claim
313	* that an element exists in hasNext(), we must return it in the
314	* following next() call even if it was in the process of being
315	* removed when hasNext() was called.
316	**/
317	private E nextItem;
318
319	/**
320	* Node of the last returned item, to support remove.
321	*/
322	private AtomicLinkedNode lastRet;
323
324	/**
325	* Move to next valid node.
326	* Return item to return for next(), or null if no such.
327	*/
328	private E advance() {
329	lastRet = nextNode;
330	E x = nextItem;
331
332	AtomicLinkedNode p = (nextNode == null) ? head : nextNode.getNext();
333	for (;;) {
334	if (p == null) {
335	nextNode = null;
336	nextItem = null;
337	return x;
338	}
339	Object item = p.getItem();
340	if (item == null)
341	p = skip(nextNode, p);
342	else {
343	nextNode = p;
344	nextItem = (E)item;
345	return x;
346	}
347	}
348	}
349
350	Itr() {
351	advance();
352	}
353
354	public boolean hasNext() {
355	return nextNode != null;
356	}
357
358	public E next() {
359	if (nextNode == null) throw new NoSuchElementException();
360	return advance();
361	}
362
363	public void remove() {
364	AtomicLinkedNode l = lastRet;
365	if (l == null) throw new IllegalStateException();
366	// rely on a future traversal to relink.
367	l.setItem(null);
368	lastRet = null;
369	}
370	}
371
372	/**
373	* Save the state to a stream (that is, serialize it).
374	*
375	* @serialData All of the elements (each an <tt>E</tt>) in
376	* the proper order, followed by a null
377	* @param s the stream
378	*/
379	private void writeObject(java.io.ObjectOutputStream s)
380	throws java.io.IOException {
381
382	// Write out any hidden stuff
383	s.defaultWriteObject();
384
385	AtomicLinkedNode previous = null;
386	AtomicLinkedNode p = head;
387	while (p != null) {
388	Object item = p.getItem();
389	if (item == null)
390	p = skip(previous, p);
391	else {
392	s.writeObject(item);
393	previous = p;
394	p = p.getNext();
395	}
396	}
397
398	// Use trailing null as sentinel
399	s.writeObject(null);
400	}
401
402	/**
403	* Reconstitute the Queue instance from a stream (that is,
404	* deserialize it).
405	* @param s the stream
406	*/
407	private void readObject(java.io.ObjectInputStream s)
408	throws java.io.IOException, ClassNotFoundException {
409	// Read in capacity, and any hidden stuff
410	s.defaultReadObject();
411
412	// Read in all elements into array and then insert in reverse order.
413	ArrayList<E> al = new ArrayList<E>();
414	for (;;) {
415	E item = (E)s.readObject();
416	if (item == null)
417	break;
418	al.add(item);
419	}
420
421	ListIterator<E> it = al.listIterator(al.size());
422	while (it.hasPrevious())
423	add(it.previous());
424	}
425
426
427	}
428