lib/classpath/external/jsr166/java/util/concurrent/CopyOnWriteArraySet.java

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