1 /*
   2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   3  *
   4  * This code is free software; you can redistribute it and/or modify it
   5  * under the terms of the GNU General Public License version 2 only, as
   6  * published by the Free Software Foundation.  Oracle designates this
   7  * particular file as subject to the "Classpath" exception as provided
   8  * by Oracle in the LICENSE file that accompanied this code.
   9  *
  10  * This code is distributed in the hope that it will be useful, but WITHOUT
  11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  13  * version 2 for more details (a copy is included in the LICENSE file that
  14  * accompanied this code).
  15  *
  16  * You should have received a copy of the GNU General Public License version
  17  * 2 along with this work; if not, write to the Free Software Foundation,
  18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  19  *
  20  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  21  * or visit www.oracle.com if you need additional information or have any
  22  * questions.
  23  */
  24 
  25 /*
  26  * This file is available under and governed by the GNU General Public
  27  * License version 2 only, as published by the Free Software Foundation.
  28  * However, the following notice accompanied the original version of this
  29  * file:
  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/licenses/publicdomain
  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 }
--- EOF ---