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

/**
 * CopyOnWriteArraySets implement a java.util.Set that uses
 * CopyOnWriteArrayList for all of its operations.
 * Thus, it shares the same basic properties:
 * <ul>
 *  <li> It is best suited for applications in which set sizes generally
 *       stay small, read-only operations
 *       vastly outnumber mutative operations, and you need
 *       to prevent interference among threads during traversal.
 *  <li> Mutative operations(add, set, remove, etc) are expensive
 *      since they usually entail copying the entire underlying array.
 *  <li> Loops involving repeated element-by-element mutative operations
 *      are so expensive that they should generally be avoided.
 *  <li> Iterators do not support the mutative remove operation
 *  <li> Traversal via iterators is very fast and cannot ever encounter
 *      interference from other threads. Iterators rely on
 *      unchanging snapshots of the array at the time the iterators were
 *     constructed.
 * </ul>
 * <p>
 * <b>Sample Usage.</b> Probably the main application
 * of copy-on-write sets are classes that maintain
 * sets of Handler objects
 * that must be multicasted to upon an update command. This
 * is a classic case where you do not want to be holding a 
 * lock while sending a message, and where traversals normally
 * vastly overwhelm additions.
 * <pre>
 * class  Handler { void handle(); ... }
 *
 * class X {
 *    private final CopyOnWriteArraySet handlers = new CopyOnWriteArraySet();
 *    public void addHandler(Handler h) { handlers.add(h); }
 *
 *    private long internalState;
 *    private synchronized void changeState() { internalState = ...; }
 *
 *    public void update() {
 *       changeState();
 *       Iterator it = handlers.iterator();
 *       while (it.hasNext())
 *          ((Handler)(it.next()).handle();
 *    }
 * }
 * </pre>
 * <p>[<a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>]
 * @see CopyOnWriteArrayList
 **/
public class CopyOnWriteArraySet<E> extends AbstractSet<E>
        implements Cloneable, java.io.Serializable {

    private final CopyOnWriteArrayList<E> al;

    /**
     * Constructs an empty set
     */
    public CopyOnWriteArraySet() {
        al = new CopyOnWriteArrayList<E>();
    }

    /**
     * Constructs a set containing all of the elements of the specified
     * Collection.
     */
    public <T extends E> CopyOnWriteArraySet(Collection<T> c) {
        al = new CopyOnWriteArrayList<E>();
        al.addAllAbsent(c);
    }


    public int      size()                    { return al.size(); }
    public boolean  isEmpty()                 { return al.isEmpty(); }
    public boolean  contains(Object o)        { return al.contains(o); }
    public Object[] toArray()                 { return al.toArray(); }
    public <T> T[]  toArray(T[] a)            { return al.toArray(a); }
    public void     clear()                   {        al.clear(); }
    public Iterator<E>  iterator()            { return al.iterator(); }
    public boolean  remove(Object o)          { return al.remove(o); }
    public boolean  add(E o)                  { return al.addIfAbsent(o); }
    public <T> boolean  containsAll(Collection<T> c)      { return al.containsAll(c); }
    public <T extends E> boolean  addAll(Collection<T> c) { return al.addAllAbsent(c) > 0; }
    public <T> boolean  removeAll(Collection<T> c)        { return al.removeAll(c); }
    public <T> boolean  retainAll(Collection<T> c)        { return al.retainAll(c); }

}
Revision:	1.2
Committed:	Tue May 27 18:14:39 2003 UTC (21 years ago) by dl
Branch:	MAIN
CVS Tags:	JSR166_PRERELEASE_0_1
Changes since 1.1:	+7 -2 lines
Log Message:	re-check-in initial implementations
#	User	Rev	Content
1	dl	1.2	/*
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	tim	1.1	package java.util.concurrent;
8			import java.util.*;
9
10			/**
11			* CopyOnWriteArraySets implement a java.util.Set that uses
12			* CopyOnWriteArrayList for all of its operations.
13			* Thus, it shares the same basic properties:
14			* <ul>
15			* <li> It is best suited for applications in which set sizes generally
16			* stay small, read-only operations
17			* vastly outnumber mutative operations, and you need
18			* to prevent interference among threads during traversal.
19			* <li> Mutative operations(add, set, remove, etc) are expensive
20			* since they usually entail copying the entire underlying array.
21			* <li> Loops involving repeated element-by-element mutative operations
22			* are so expensive that they should generally be avoided.
23			* <li> Iterators do not support the mutative remove operation
24			* <li> Traversal via iterators is very fast and cannot ever encounter
25			* interference from other threads. Iterators rely on
26			* unchanging snapshots of the array at the time the iterators were
27			* constructed.
28			* </ul>
29			* <p>
30			* <b>Sample Usage.</b> Probably the main application
31			* of copy-on-write sets are classes that maintain
32			* sets of Handler objects
33			* that must be multicasted to upon an update command. This
34	dl	1.2	* is a classic case where you do not want to be holding a
35	tim	1.1	* lock while sending a message, and where traversals normally
36			* vastly overwhelm additions.
37			* <pre>
38			* class Handler { void handle(); ... }
39			*
40			* class X {
41			* private final CopyOnWriteArraySet handlers = new CopyOnWriteArraySet();
42			* public void addHandler(Handler h) { handlers.add(h); }
43			*
44			* private long internalState;
45			* private synchronized void changeState() { internalState = ...; }
46			*
47			* public void update() {
48			* changeState();
49			* Iterator it = handlers.iterator();
50			* while (it.hasNext())
51			* ((Handler)(it.next()).handle();
52			* }
53			* }
54			* </pre>
55			* <p>[<a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>]
56			* @see CopyOnWriteArrayList
57			**/
58			public class CopyOnWriteArraySet<E> extends AbstractSet<E>
59			implements Cloneable, java.io.Serializable {
60
61			private final CopyOnWriteArrayList<E> al;
62
63			/**
64			* Constructs an empty set
65			*/
66			public CopyOnWriteArraySet() {
67			al = new CopyOnWriteArrayList<E>();
68			}
69
70			/**
71			* Constructs a set containing all of the elements of the specified
72			* Collection.
73			*/
74			public <T extends E> CopyOnWriteArraySet(Collection<T> c) {
75			al = new CopyOnWriteArrayList<E>();
76			al.addAllAbsent(c);
77			}
78
79
80			public int size() { return al.size(); }
81			public boolean isEmpty() { return al.isEmpty(); }
82			public boolean contains(Object o) { return al.contains(o); }
83			public Object[] toArray() { return al.toArray(); }
84			public <T> T[] toArray(T[] a) { return al.toArray(a); }
85			public void clear() { al.clear(); }
86			public Iterator<E> iterator() { return al.iterator(); }
87			public boolean remove(Object o) { return al.remove(o); }
88			public boolean add(E o) { return al.addIfAbsent(o); }
89			public <T> boolean containsAll(Collection<T> c) { return al.containsAll(c); }
90			public <T extends E> boolean addAll(Collection<T> c) { return al.addAllAbsent(c) > 0; }
91			public <T> boolean removeAll(Collection<T> c) { return al.removeAll(c); }
92			public <T> boolean retainAll(Collection<T> c) { return al.retainAll(c); }
93
94			}