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