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<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 * } 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 ? e==null : 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 ? e==null : 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 ? e2==null : 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 ---