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

public class LinkedStack<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.
     */

    private transient volatile AtomicLinkedNode head;

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

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

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

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