1 /*
  2  * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
  3  *
  4  *
  5  *
  6  *
  7  *
  8  *
  9  *
 10  *
 11  *
 12  *
 13  *
 14  *
 15  *
 16  *
 17  *
 18  *
 19  *
 20  *
 21  *
 22  *
 23  */
 24 
 25 /*
 26  *
 27  *
 28  *
 29  *
 30  *
 31  * Written by Doug Lea with assistance from members of JCP JSR-166
 32  * Expert Group and released to the public domain, as explained at
 33  * http://creativecommons.org/publicdomain/zero/1.0/
 34  */
 35 
 36 package java.util.concurrent;
 37 import java.util.*;
 38 
 39 /**
 40  * A {@link java.util.Set} that uses an internal {@link CopyOnWriteArrayList}
 41  * for all of its operations.  Thus, it shares the same basic properties:
 42  * <ul>
 43  *  <li>It is best suited for applications in which set sizes generally
 44  *       stay small, read-only operations
 45  *       vastly outnumber mutative operations, and you need
 46  *       to prevent interference among threads during traversal.
 47  *  <li>It is thread-safe.
 48  *  <li>Mutative operations (<tt>add</tt>, <tt>set</tt>, <tt>remove</tt>, etc.)
 49  *      are expensive since they usually entail copying the entire underlying
 50  *      array.
 51  *  <li>Iterators do not support the mutative <tt>remove</tt> operation.
 52  *  <li>Traversal via iterators is fast and cannot encounter
 53  *      interference from other threads. Iterators rely on
 54  *      unchanging snapshots of the array at the time the iterators were
 55  *      constructed.
 56  * </ul>
 57  *
 58  * <p> <b>Sample Usage.</b> The following code sketch uses a
 59  * copy-on-write set to maintain a set of Handler objects that
 60  * perform some action upon state updates.
 61  *
 62  *  <pre> {@code
 63  * class Handler { void handle(); ... }
 64  *
 65  * class X {
 66  *   private final CopyOnWriteArraySet<Handler> handlers
 67  *     = new CopyOnWriteArraySet<Handler>();
 68  *   public void addHandler(Handler h) { handlers.add(h); }
 69  *
 70  *   private long internalState;
 71  *   private synchronized void changeState() { internalState = ...; }
 72  *
 73  *   public void update() {
 74  *     changeState();
 75  *     for (Handler handler : handlers)
 76  *        handler.handle();
 77  *   }
 78  * }}</pre>
 79  *
 80  * <p>This class is a member of the
 81  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 82  * Java Collections Framework</a>.
 83  *
 84  * @see CopyOnWriteArrayList
 85  * @since 1.5
 86  * @author Doug Lea
 87  * @param <E> the type of elements held in this collection
 88  */
 89 public class CopyOnWriteArraySet<E> extends AbstractSet<E>
 90         implements java.io.Serializable {
 91     private static final long serialVersionUID = 5457747651344034263L;
 92 
 93     private final CopyOnWriteArrayList<E> al;
 94 
 95     /**
 96      * Creates an empty set.
 97      */
 98     public CopyOnWriteArraySet() {
 99         al = new CopyOnWriteArrayList<E>();
100     }
101 
102     /**
103      * Creates a set containing all of the elements of the specified
104      * collection.
105      *
106      * @param c the collection of elements to initially contain
107      * @throws NullPointerException if the specified collection is null
108      */
109     public CopyOnWriteArraySet(Collection<? extends E> c) {
110         al = new CopyOnWriteArrayList<E>();
111         al.addAllAbsent(c);
112     }
113 
114     /**
115      * Returns the number of elements in this set.
116      *
117      * @return the number of elements in this set
118      */
119     public int size() {
120         return al.size();
121     }
122 
123     /**
124      * Returns <tt>true</tt> if this set contains no elements.
125      *
126      * @return <tt>true</tt> if this set contains no elements
127      */
128     public boolean isEmpty() {
129         return al.isEmpty();
130     }
131 
132     /**
133      * Returns <tt>true</tt> if this set contains the specified element.
134      * More formally, returns <tt>true</tt> if and only if this set
135      * contains an element <tt>e</tt> such that
136      * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
137      *
138      * @param o element whose presence in this set is to be tested
139      * @return <tt>true</tt> if this set contains the specified element
140      */
141     public boolean contains(Object o) {
142         return al.contains(o);
143     }
144 
145     /**
146      * Returns an array containing all of the elements in this set.
147      * If this set makes any guarantees as to what order its elements
148      * are returned by its iterator, this method must return the
149      * elements in the same order.
150      *
151      * <p>The returned array will be "safe" in that no references to it
152      * are maintained by this set.  (In other words, this method must
153      * allocate a new array even if this set is backed by an array).
154      * The caller is thus free to modify the returned array.
155      *
156      * <p>This method acts as bridge between array-based and collection-based
157      * APIs.
158      *
159      * @return an array containing all the elements in this set
160      */
161     public Object[] toArray() {
162         return al.toArray();
163     }
164 
165     /**
166      * Returns an array containing all of the elements in this set; the
167      * runtime type of the returned array is that of the specified array.
168      * If the set fits in the specified array, it is returned therein.
169      * Otherwise, a new array is allocated with the runtime type of the
170      * specified array and the size of this set.
171      *
172      * <p>If this set fits in the specified array with room to spare
173      * (i.e., the array has more elements than this set), the element in
174      * the array immediately following the end of the set is set to
175      * <tt>null</tt>.  (This is useful in determining the length of this
176      * set <i>only</i> if the caller knows that this set does not contain
177      * any null elements.)
178      *
179      * <p>If this set makes any guarantees as to what order its elements
180      * are returned by its iterator, this method must return the elements
181      * in the same order.
182      *
183      * <p>Like the {@link #toArray()} method, this method acts as bridge between
184      * array-based and collection-based APIs.  Further, this method allows
185      * precise control over the runtime type of the output array, and may,
186      * under certain circumstances, be used to save allocation costs.
187      *
188      * <p>Suppose <tt>x</tt> is a set known to contain only strings.
189      * The following code can be used to dump the set into a newly allocated
190      * array of <tt>String</tt>:
191      *
192      * <pre>
193      *     String[] y = x.toArray(new String[0]);</pre>
194      *
195      * Note that <tt>toArray(new Object[0])</tt> is identical in function to
196      * <tt>toArray()</tt>.
197      *
198      * @param a the array into which the elements of this set are to be
199      *        stored, if it is big enough; otherwise, a new array of the same
200      *        runtime type is allocated for this purpose.
201      * @return an array containing all the elements in this set
202      * @throws ArrayStoreException if the runtime type of the specified array
203      *         is not a supertype of the runtime type of every element in this
204      *         set
205      * @throws NullPointerException if the specified array is null
206      */
207     public <T> T[] toArray(T[] a) {
208         return al.toArray(a);
209     }
210 
211     /**
212      * Removes all of the elements from this set.
213      * The set will be empty after this call returns.
214      */
215     public void clear() {
216         al.clear();
217     }
218 
219     /**
220      * Removes the specified element from this set if it is present.
221      * More formally, removes an element <tt>e</tt> such that
222      * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>,
223      * if this set contains such an element.  Returns <tt>true</tt> if
224      * this set contained the element (or equivalently, if this set
225      * changed as a result of the call).  (This set will not contain the
226      * element once the call returns.)
227      *
228      * @param o object to be removed from this set, if present
229      * @return <tt>true</tt> if this set contained the specified element
230      */
231     public boolean remove(Object o) {
232         return al.remove(o);
233     }
234 
235     /**
236      * Adds the specified element to this set if it is not already present.
237      * More formally, adds the specified element <tt>e</tt> to this set if
238      * the set contains no element <tt>e2</tt> such that
239      * <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.
240      * If this set already contains the element, the call leaves the set
241      * unchanged and returns <tt>false</tt>.
242      *
243      * @param e element to be added to this set
244      * @return <tt>true</tt> if this set did not already contain the specified
245      *         element
246      */
247     public boolean add(E e) {
248         return al.addIfAbsent(e);
249     }
250 
251     /**
252      * Returns <tt>true</tt> if this set contains all of the elements of the
253      * specified collection.  If the specified collection is also a set, this
254      * method returns <tt>true</tt> if it is a <i>subset</i> of this set.
255      *
256      * @param  c collection to be checked for containment in this set
257      * @return <tt>true</tt> if this set contains all of the elements of the
258      *         specified collection
259      * @throws NullPointerException if the specified collection is null
260      * @see #contains(Object)
261      */
262     public boolean containsAll(Collection<?> c) {
263         return al.containsAll(c);
264     }
265 
266     /**
267      * Adds all of the elements in the specified collection to this set if
268      * they‘re not already present.  If the specified collection is also a
269      * set, the <tt>addAll</tt> operation effectively modifies this set so
270      * that its value is the <i>union</i> of the two sets.  The behavior of
271      * this operation is undefined if the specified collection is modified
272      * while the operation is in progress.
273      *
274      * @param  c collection containing elements to be added to this set
275      * @return <tt>true</tt> if this set changed as a result of the call
276      * @throws NullPointerException if the specified collection is null
277      * @see #add(Object)
278      */
279     public boolean addAll(Collection<? extends E> c) {
280         return al.addAllAbsent(c) > 0;
281     }
282 
283     /**
284      * Removes from this set all of its elements that are contained in the
285      * specified collection.  If the specified collection is also a set,
286      * this operation effectively modifies this set so that its value is the
287      * <i>asymmetric set difference</i> of the two sets.
288      *
289      * @param  c collection containing elements to be removed from this set
290      * @return <tt>true</tt> if this set changed as a result of the call
291      * @throws ClassCastException if the class of an element of this set
292      *         is incompatible with the specified collection (optional)
293      * @throws NullPointerException if this set contains a null element and the
294      *         specified collection does not permit null elements (optional),
295      *         or if the specified collection is null
296      * @see #remove(Object)
297      */
298     public boolean removeAll(Collection<?> c) {
299         return al.removeAll(c);
300     }
301 
302     /**
303      * Retains only the elements in this set that are contained in the
304      * specified collection.  In other words, removes from this set all of
305      * its elements that are not contained in the specified collection.  If
306      * the specified collection is also a set, this operation effectively
307      * modifies this set so that its value is the <i>intersection</i> of the
308      * two sets.
309      *
310      * @param  c collection containing elements to be retained in this set
311      * @return <tt>true</tt> if this set changed as a result of the call
312      * @throws ClassCastException if the class of an element of this set
313      *         is incompatible with the specified collection (optional)
314      * @throws NullPointerException if this set contains a null element and the
315      *         specified collection does not permit null elements (optional),
316      *         or if the specified collection is null
317      * @see #remove(Object)
318      */
319     public boolean retainAll(Collection<?> c) {
320         return al.retainAll(c);
321     }
322 
323     /**
324      * Returns an iterator over the elements contained in this set
325      * in the order in which these elements were added.
326      *
327      * <p>The returned iterator provides a snapshot of the state of the set
328      * when the iterator was constructed. No synchronization is needed while
329      * traversing the iterator. The iterator does <em>NOT</em> support the
330      * <tt>remove</tt> method.
331      *
332      * @return an iterator over the elements in this set
333      */
334     public Iterator<E> iterator() {
335         return al.iterator();
336     }
337 
338     /**
339      * Compares the specified object with this set for equality.
340      * Returns {@code true} if the specified object is the same object
341      * as this object, or if it is also a {@link Set} and the elements
342      * returned by an {@linkplain List#iterator() iterator} over the
343      * specified set are the same as the elements returned by an
344      * iterator over this set.  More formally, the two iterators are
345      * considered to return the same elements if they return the same
346      * number of elements and for every element {@code e1} returned by
347      * the iterator over the specified set, there is an element
348      * {@code e2} returned by the iterator over this set such that
349      * {@code (e1==null ? e2==null : e1.equals(e2))}.
350      *
351      * @param o object to be compared for equality with this set
352      * @return {@code true} if the specified object is equal to this set
353      */
354     public boolean equals(Object o) {
355         if (o == this)
356             return true;
357         if (!(o instanceof Set))
358             return false;
359         Set<?> set = (Set<?>)(o);
360         Iterator<?> it = set.iterator();
361 
362         // Uses O(n^2) algorithm that is only appropriate
363         // for small sets, which CopyOnWriteArraySets should be.
364 
365         //  Use a single snapshot of underlying array
366         Object[] elements = al.getArray();
367         int len = elements.length;
368         // Mark matched elements to avoid re-checking
369         boolean[] matched = new boolean[len];
370         int k = 0;
371         outer: while (it.hasNext()) {
372             if (++k > len)
373                 return false;
374             Object x = it.next();
375             for (int i = 0; i < len; ++i) {
376                 if (!matched[i] && eq(x, elements[i])) {
377                     matched[i] = true;
378                     continue outer;
379                 }
380             }
381             return false;
382         }
383         return k == len;
384     }
385 
386     /**
387      * Test for equality, coping with nulls.
388      */
389     private static boolean eq(Object o1, Object o2) {
390         return (o1 == null ? o2 == null : o1.equals(o2));
391     }
392 }