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>
  63  * class Handler { void handle(); ... }
  64  *
  65  * class X {
  66  *    private final CopyOnWriteArraySet&lt;Handler&gt; handlers
  67  *       = new CopyOnWriteArraySet&lt;Handler&gt;();
  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  * }
  79  * </pre>
  80  *
  81  * <p>This class is a member of the
  82  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  83  * Java Collections Framework</a>.
  84  *
  85  * @see CopyOnWriteArrayList
  86  * @since 1.5
  87  * @author Doug Lea
  88  * @param <E> the type of elements held in this collection
  89  */
  90 public class CopyOnWriteArraySet<E> extends AbstractSet<E>
  91         implements java.io.Serializable {
  92     private static final long serialVersionUID = 5457747651344034263L;
  93 
  94     private final CopyOnWriteArrayList<E> al;
  95 
  96     /**
  97      * Creates an empty set.
  98      */
  99     public CopyOnWriteArraySet() {
 100         al = new CopyOnWriteArrayList<E>();
 101     }
 102 
 103     /**
 104      * Creates a set containing all of the elements of the specified
 105      * collection.
 106      *
 107      * @param c the collection of elements to initially contain
 108      * @throws NullPointerException if the specified collection is null
 109      */
 110     public CopyOnWriteArraySet(Collection<? extends E> c) {
 111         al = new CopyOnWriteArrayList<E>();
 112         al.addAllAbsent(c);
 113     }
 114 
 115     /**
 116      * Returns the number of elements in this set.
 117      *
 118      * @return the number of elements in this set
 119      */
 120     public int size() {
 121         return al.size();
 122     }
 123 
 124     /**
 125      * Returns <tt>true</tt> if this set contains no elements.
 126      *
 127      * @return <tt>true</tt> if this set contains no elements
 128      */
 129     public boolean isEmpty() {
 130         return al.isEmpty();
 131     }
 132 
 133     /**
 134      * Returns <tt>true</tt> if this set contains the specified element.
 135      * More formally, returns <tt>true</tt> if and only if this set
 136      * contains an element <tt>e</tt> such that
 137      * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
 138      *
 139      * @param o element whose presence in this set is to be tested
 140      * @return <tt>true</tt> if this set contains the specified element
 141      */
 142     public boolean contains(Object o) {
 143         return al.contains(o);
 144     }
 145 
 146     /**
 147      * Returns an array containing all of the elements in this set.
 148      * If this set makes any guarantees as to what order its elements
 149      * are returned by its iterator, this method must return the
 150      * elements in the same order.
 151      *
 152      * <p>The returned array will be "safe" in that no references to it
 153      * are maintained by this set.  (In other words, this method must
 154      * allocate a new array even if this set is backed by an array).
 155      * The caller is thus free to modify the returned array.
 156      *
 157      * <p>This method acts as bridge between array-based and collection-based
 158      * APIs.
 159      *
 160      * @return an array containing all the elements in this set
 161      */
 162     public Object[] toArray() {
 163         return al.toArray();
 164     }
 165 
 166     /**
 167      * Returns an array containing all of the elements in this set; the
 168      * runtime type of the returned array is that of the specified array.
 169      * If the set fits in the specified array, it is returned therein.
 170      * Otherwise, a new array is allocated with the runtime type of the
 171      * specified array and the size of this set.
 172      *
 173      * <p>If this set fits in the specified array with room to spare
 174      * (i.e., the array has more elements than this set), the element in
 175      * the array immediately following the end of the set is set to
 176      * <tt>null</tt>.  (This is useful in determining the length of this
 177      * set <i>only</i> if the caller knows that this set does not contain
 178      * any null elements.)
 179      *
 180      * <p>If this set makes any guarantees as to what order its elements
 181      * are returned by its iterator, this method must return the elements
 182      * in the same order.
 183      *
 184      * <p>Like the {@link #toArray()} method, this method acts as bridge between
 185      * array-based and collection-based APIs.  Further, this method allows
 186      * precise control over the runtime type of the output array, and may,
 187      * under certain circumstances, be used to save allocation costs.
 188      *
 189      * <p>Suppose <tt>x</tt> is a set known to contain only strings.
 190      * The following code can be used to dump the set into a newly allocated
 191      * array of <tt>String</tt>:
 192      *
 193      * <pre>
 194      *     String[] y = x.toArray(new String[0]);</pre>
 195      *
 196      * Note that <tt>toArray(new Object[0])</tt> is identical in function to
 197      * <tt>toArray()</tt>.
 198      *
 199      * @param a the array into which the elements of this set are to be
 200      *        stored, if it is big enough; otherwise, a new array of the same
 201      *        runtime type is allocated for this purpose.
 202      * @return an array containing all the elements in this set
 203      * @throws ArrayStoreException if the runtime type of the specified array
 204      *         is not a supertype of the runtime type of every element in this
 205      *         set
 206      * @throws NullPointerException if the specified array is null
 207      */
 208     public <T> T[] toArray(T[] a) {
 209         return al.toArray(a);
 210     }
 211 
 212     /**
 213      * Removes all of the elements from this set.
 214      * The set will be empty after this call returns.
 215      */
 216     public void clear() {
 217         al.clear();
 218     }
 219 
 220     /**
 221      * Removes the specified element from this set if it is present.
 222      * More formally, removes an element <tt>e</tt> such that
 223      * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>,
 224      * if this set contains such an element.  Returns <tt>true</tt> if
 225      * this set contained the element (or equivalently, if this set
 226      * changed as a result of the call).  (This set will not contain the
 227      * element once the call returns.)
 228      *
 229      * @param o object to be removed from this set, if present
 230      * @return <tt>true</tt> if this set contained the specified element
 231      */
 232     public boolean remove(Object o) {
 233         return al.remove(o);
 234     }
 235 
 236     /**
 237      * Adds the specified element to this set if it is not already present.
 238      * More formally, adds the specified element <tt>e</tt> to this set if
 239      * the set contains no element <tt>e2</tt> such that
 240      * <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.
 241      * If this set already contains the element, the call leaves the set
 242      * unchanged and returns <tt>false</tt>.
 243      *
 244      * @param e element to be added to this set
 245      * @return <tt>true</tt> if this set did not already contain the specified
 246      *         element
 247      */
 248     public boolean add(E e) {
 249         return al.addIfAbsent(e);
 250     }
 251 
 252     /**
 253      * Returns <tt>true</tt> if this set contains all of the elements of the
 254      * specified collection.  If the specified collection is also a set, this
 255      * method returns <tt>true</tt> if it is a <i>subset</i> of this set.
 256      *
 257      * @param  c collection to be checked for containment in this set
 258      * @return <tt>true</tt> if this set contains all of the elements of the
 259      *         specified collection
 260      * @throws NullPointerException if the specified collection is null
 261      * @see #contains(Object)
 262      */
 263     public boolean containsAll(Collection<?> c) {
 264         return al.containsAll(c);
 265     }
 266 
 267     /**
 268      * Adds all of the elements in the specified collection to this set if
 269      * they're not already present.  If the specified collection is also a
 270      * set, the <tt>addAll</tt> operation effectively modifies this set so
 271      * that its value is the <i>union</i> of the two sets.  The behavior of
 272      * this operation is undefined if the specified collection is modified
 273      * while the operation is in progress.
 274      *
 275      * @param  c collection containing elements to be added to this set
 276      * @return <tt>true</tt> if this set changed as a result of the call
 277      * @throws NullPointerException if the specified collection is null
 278      * @see #add(Object)
 279      */
 280     public boolean addAll(Collection<? extends E> c) {
 281         return al.addAllAbsent(c) > 0;
 282     }
 283 
 284     /**
 285      * Removes from this set all of its elements that are contained in the
 286      * specified collection.  If the specified collection is also a set,
 287      * this operation effectively modifies this set so that its value is the
 288      * <i>asymmetric set difference</i> of the two sets.
 289      *
 290      * @param  c collection containing elements to be removed from this set
 291      * @return <tt>true</tt> if this set changed as a result of the call
 292      * @throws ClassCastException if the class of an element of this set
 293      *         is incompatible with the specified collection (optional)
 294      * @throws NullPointerException if this set contains a null element and the
 295      *         specified collection does not permit null elements (optional),
 296      *         or if the specified collection is null
 297      * @see #remove(Object)
 298      */
 299     public boolean removeAll(Collection<?> c) {
 300         return al.removeAll(c);
 301     }
 302 
 303     /**
 304      * Retains only the elements in this set that are contained in the
 305      * specified collection.  In other words, removes from this set all of
 306      * its elements that are not contained in the specified collection.  If
 307      * the specified collection is also a set, this operation effectively
 308      * modifies this set so that its value is the <i>intersection</i> of the
 309      * two sets.
 310      *
 311      * @param  c collection containing elements to be retained in this set
 312      * @return <tt>true</tt> if this set changed as a result of the call
 313      * @throws ClassCastException if the class of an element of this set
 314      *         is incompatible with the specified collection (optional)
 315      * @throws NullPointerException if this set contains a null element and the
 316      *         specified collection does not permit null elements (optional),
 317      *         or if the specified collection is null
 318      * @see #remove(Object)
 319      */
 320     public boolean retainAll(Collection<?> c) {
 321         return al.retainAll(c);
 322     }
 323 
 324     /**
 325      * Returns an iterator over the elements contained in this set
 326      * in the order in which these elements were added.
 327      *
 328      * <p>The returned iterator provides a snapshot of the state of the set
 329      * when the iterator was constructed. No synchronization is needed while
 330      * traversing the iterator. The iterator does <em>NOT</em> support the
 331      * <tt>remove</tt> method.
 332      *
 333      * @return an iterator over the elements in this set
 334      */
 335     public Iterator<E> iterator() {
 336         return al.iterator();
 337     }
 338 
 339     /**
 340      * Compares the specified object with this set for equality.
 341      * Returns {@code true} if the specified object is the same object
 342      * as this object, or if it is also a {@link Set} and the elements
 343      * returned by an {@linkplain List#iterator() iterator} over the
 344      * specified set are the same as the elements returned by an
 345      * iterator over this set.  More formally, the two iterators are
 346      * considered to return the same elements if they return the same
 347      * number of elements and for every element {@code e1} returned by
 348      * the iterator over the specified set, there is an element
 349      * {@code e2} returned by the iterator over this set such that
 350      * {@code (e1==null ? e2==null : e1.equals(e2))}.
 351      *
 352      * @param o object to be compared for equality with this set
 353      * @return {@code true} if the specified object is equal to this set
 354      */
 355     public boolean equals(Object o) {
 356         if (o == this)
 357             return true;
 358         if (!(o instanceof Set))
 359             return false;
 360         Set<?> set = (Set<?>)(o);
 361         Iterator<?> it = set.iterator();
 362 
 363         // Uses O(n^2) algorithm that is only appropriate
 364         // for small sets, which CopyOnWriteArraySets should be.
 365 
 366         //  Use a single snapshot of underlying array
 367         Object[] elements = al.getArray();
 368         int len = elements.length;
 369         // Mark matched elements to avoid re-checking
 370         boolean[] matched = new boolean[len];
 371         int k = 0;
 372         outer: while (it.hasNext()) {
 373             if (++k > len)
 374                 return false;
 375             Object x = it.next();
 376             for (int i = 0; i < len; ++i) {
 377                 if (!matched[i] && eq(x, elements[i])) {
 378                     matched[i] = true;
 379                     continue outer;
 380                 }
 381             }
 382             return false;
 383         }
 384         return k == len;
 385     }
 386 
 387     /**
 388      * Test for equality, coping with nulls.
 389      */
 390     private static boolean eq(Object o1, Object o2) {
 391         return (o1 == null ? o2 == null : o1.equals(o2));
 392     }
 393 }
--- EOF ---