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