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