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?
#	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			* 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