Source for java.util.concurrent.CopyOnWriteArraySet

   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: }