Print this page
Split |
Close |
Expand all |
Collapse all |
--- old/src/share/classes/java/util/concurrent/ConcurrentSkipListSet.java
+++ new/src/share/classes/java/util/concurrent/ConcurrentSkipListSet.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 import sun.misc.Unsafe;
39 39
40 40 /**
41 41 * A scalable concurrent {@link NavigableSet} implementation based on
42 42 * a {@link ConcurrentSkipListMap}. The elements of the set are kept
43 43 * sorted according to their {@linkplain Comparable natural ordering},
44 44 * or by a {@link Comparator} provided at set creation time, depending
45 45 * on which constructor is used.
46 46 *
47 47 * <p>This implementation provides expected average <i>log(n)</i> time
48 48 * cost for the <tt>contains</tt>, <tt>add</tt>, and <tt>remove</tt>
49 49 * operations and their variants. Insertion, removal, and access
50 50 * operations safely execute concurrently by multiple threads.
51 51 * Iterators are <i>weakly consistent</i>, returning elements
52 52 * reflecting the state of the set at some point at or since the
53 53 * creation of the iterator. They do <em>not</em> throw {@link
54 54 * ConcurrentModificationException}, and may proceed concurrently with
55 55 * other operations. Ascending ordered views and their iterators are
56 56 * faster than descending ones.
57 57 *
58 58 * <p>Beware that, unlike in most collections, the <tt>size</tt>
59 59 * method is <em>not</em> a constant-time operation. Because of the
60 60 * asynchronous nature of these sets, determining the current number
61 61 * of elements requires a traversal of the elements. Additionally, the
62 62 * bulk operations <tt>addAll</tt>, <tt>removeAll</tt>,
63 63 * <tt>retainAll</tt>, and <tt>containsAll</tt> are <em>not</em>
64 64 * guaranteed to be performed atomically. For example, an iterator
65 65 * operating concurrently with an <tt>addAll</tt> operation might view
66 66 * only some of the added elements.
67 67 *
68 68 * <p>This class and its iterators implement all of the
69 69 * <em>optional</em> methods of the {@link Set} and {@link Iterator}
70 70 * interfaces. Like most other concurrent collection implementations,
71 71 * this class does not permit the use of <tt>null</tt> elements,
72 72 * because <tt>null</tt> arguments and return values cannot be reliably
73 73 * distinguished from the absence of elements.
74 74 *
75 75 * <p>This class is a member of the
76 76 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
77 77 * Java Collections Framework</a>.
78 78 *
79 79 * @author Doug Lea
80 80 * @param <E> the type of elements maintained by this set
81 81 * @since 1.6
82 82 */
83 83 public class ConcurrentSkipListSet<E>
84 84 extends AbstractSet<E>
85 85 implements NavigableSet<E>, Cloneable, java.io.Serializable {
86 86
87 87 private static final long serialVersionUID = -2479143111061671589L;
88 88
89 89 /**
90 90 * The underlying map. Uses Boolean.TRUE as value for each
91 91 * element. This field is declared final for the sake of thread
92 92 * safety, which entails some ugliness in clone()
93 93 */
94 94 private final ConcurrentNavigableMap<E,Object> m;
95 95
96 96 /**
97 97 * Constructs a new, empty set that orders its elements according to
98 98 * their {@linkplain Comparable natural ordering}.
99 99 */
100 100 public ConcurrentSkipListSet() {
101 101 m = new ConcurrentSkipListMap<E,Object>();
102 102 }
103 103
104 104 /**
105 105 * Constructs a new, empty set that orders its elements according to
106 106 * the specified comparator.
107 107 *
108 108 * @param comparator the comparator that will be used to order this set.
109 109 * If <tt>null</tt>, the {@linkplain Comparable natural
110 110 * ordering} of the elements will be used.
111 111 */
112 112 public ConcurrentSkipListSet(Comparator<? super E> comparator) {
113 113 m = new ConcurrentSkipListMap<E,Object>(comparator);
114 114 }
115 115
116 116 /**
117 117 * Constructs a new set containing the elements in the specified
118 118 * collection, that orders its elements according to their
119 119 * {@linkplain Comparable natural ordering}.
120 120 *
121 121 * @param c The elements that will comprise the new set
122 122 * @throws ClassCastException if the elements in <tt>c</tt> are
123 123 * not {@link Comparable}, or are not mutually comparable
124 124 * @throws NullPointerException if the specified collection or any
125 125 * of its elements are null
126 126 */
127 127 public ConcurrentSkipListSet(Collection<? extends E> c) {
128 128 m = new ConcurrentSkipListMap<E,Object>();
129 129 addAll(c);
130 130 }
131 131
132 132 /**
133 133 * Constructs a new set containing the same elements and using the
134 134 * same ordering as the specified sorted set.
135 135 *
136 136 * @param s sorted set whose elements will comprise the new set
137 137 * @throws NullPointerException if the specified sorted set or any
138 138 * of its elements are null
139 139 */
140 140 public ConcurrentSkipListSet(SortedSet<E> s) {
141 141 m = new ConcurrentSkipListMap<E,Object>(s.comparator());
142 142 addAll(s);
143 143 }
144 144
145 145 /**
146 146 * For use by submaps
147 147 */
148 148 ConcurrentSkipListSet(ConcurrentNavigableMap<E,Object> m) {
149 149 this.m = m;
150 150 }
151 151
152 152 /**
153 153 * Returns a shallow copy of this <tt>ConcurrentSkipListSet</tt>
154 154 * instance. (The elements themselves are not cloned.)
155 155 *
156 156 * @return a shallow copy of this set
157 157 */
158 158 public ConcurrentSkipListSet<E> clone() {
159 159 ConcurrentSkipListSet<E> clone = null;
160 160 try {
161 161 clone = (ConcurrentSkipListSet<E>) super.clone();
162 162 clone.setMap(new ConcurrentSkipListMap(m));
163 163 } catch (CloneNotSupportedException e) {
164 164 throw new InternalError();
165 165 }
166 166
167 167 return clone;
168 168 }
169 169
170 170 /* ---------------- Set operations -------------- */
171 171
172 172 /**
173 173 * Returns the number of elements in this set. If this set
174 174 * contains more than <tt>Integer.MAX_VALUE</tt> elements, it
175 175 * returns <tt>Integer.MAX_VALUE</tt>.
176 176 *
177 177 * <p>Beware that, unlike in most collections, this method is
178 178 * <em>NOT</em> a constant-time operation. Because of the
179 179 * asynchronous nature of these sets, determining the current
180 180 * number of elements requires traversing them all to count them.
181 181 * Additionally, it is possible for the size to change during
182 182 * execution of this method, in which case the returned result
183 183 * will be inaccurate. Thus, this method is typically not very
184 184 * useful in concurrent applications.
185 185 *
186 186 * @return the number of elements in this set
187 187 */
188 188 public int size() {
189 189 return m.size();
190 190 }
191 191
192 192 /**
193 193 * Returns <tt>true</tt> if this set contains no elements.
194 194 * @return <tt>true</tt> if this set contains no elements
195 195 */
196 196 public boolean isEmpty() {
197 197 return m.isEmpty();
198 198 }
199 199
200 200 /**
201 201 * Returns <tt>true</tt> if this set contains the specified element.
202 202 * More formally, returns <tt>true</tt> if and only if this set
203 203 * contains an element <tt>e</tt> such that <tt>o.equals(e)</tt>.
204 204 *
205 205 * @param o object to be checked for containment in this set
206 206 * @return <tt>true</tt> if this set contains the specified element
207 207 * @throws ClassCastException if the specified element cannot be
208 208 * compared with the elements currently in this set
209 209 * @throws NullPointerException if the specified element is null
210 210 */
211 211 public boolean contains(Object o) {
212 212 return m.containsKey(o);
213 213 }
214 214
215 215 /**
216 216 * Adds the specified element to this set if it is not already present.
217 217 * More formally, adds the specified element <tt>e</tt> to this set if
218 218 * the set contains no element <tt>e2</tt> such that <tt>e.equals(e2)</tt>.
219 219 * If this set already contains the element, the call leaves the set
220 220 * unchanged and returns <tt>false</tt>.
221 221 *
222 222 * @param e element to be added to this set
223 223 * @return <tt>true</tt> if this set did not already contain the
224 224 * specified element
225 225 * @throws ClassCastException if <tt>e</tt> cannot be compared
226 226 * with the elements currently in this set
227 227 * @throws NullPointerException if the specified element is null
228 228 */
229 229 public boolean add(E e) {
230 230 return m.putIfAbsent(e, Boolean.TRUE) == null;
231 231 }
232 232
233 233 /**
234 234 * Removes the specified element from this set if it is present.
235 235 * More formally, removes an element <tt>e</tt> such that
236 236 * <tt>o.equals(e)</tt>, if this set contains such an element.
237 237 * Returns <tt>true</tt> if this set contained the element (or
238 238 * equivalently, if this set changed as a result of the call).
239 239 * (This set will not contain the element once the call returns.)
240 240 *
241 241 * @param o object to be removed from this set, if present
242 242 * @return <tt>true</tt> if this set contained the specified element
243 243 * @throws ClassCastException if <tt>o</tt> cannot be compared
244 244 * with the elements currently in this set
245 245 * @throws NullPointerException if the specified element is null
246 246 */
247 247 public boolean remove(Object o) {
248 248 return m.remove(o, Boolean.TRUE);
249 249 }
250 250
251 251 /**
252 252 * Removes all of the elements from this set.
253 253 */
254 254 public void clear() {
255 255 m.clear();
256 256 }
257 257
258 258 /**
259 259 * Returns an iterator over the elements in this set in ascending order.
260 260 *
261 261 * @return an iterator over the elements in this set in ascending order
262 262 */
263 263 public Iterator<E> iterator() {
264 264 return m.navigableKeySet().iterator();
265 265 }
266 266
267 267 /**
268 268 * Returns an iterator over the elements in this set in descending order.
269 269 *
270 270 * @return an iterator over the elements in this set in descending order
271 271 */
272 272 public Iterator<E> descendingIterator() {
273 273 return m.descendingKeySet().iterator();
274 274 }
275 275
276 276
277 277 /* ---------------- AbstractSet Overrides -------------- */
278 278
279 279 /**
280 280 * Compares the specified object with this set for equality. Returns
281 281 * <tt>true</tt> if the specified object is also a set, the two sets
282 282 * have the same size, and every member of the specified set is
283 283 * contained in this set (or equivalently, every member of this set is
284 284 * contained in the specified set). This definition ensures that the
285 285 * equals method works properly across different implementations of the
286 286 * set interface.
287 287 *
288 288 * @param o the object to be compared for equality with this set
289 289 * @return <tt>true</tt> if the specified object is equal to this set
290 290 */
291 291 public boolean equals(Object o) {
292 292 // Override AbstractSet version to avoid calling size()
293 293 if (o == this)
294 294 return true;
295 295 if (!(o instanceof Set))
296 296 return false;
297 297 Collection<?> c = (Collection<?>) o;
298 298 try {
299 299 return containsAll(c) && c.containsAll(this);
300 300 } catch (ClassCastException unused) {
301 301 return false;
302 302 } catch (NullPointerException unused) {
303 303 return false;
304 304 }
305 305 }
306 306
307 307 /**
308 308 * Removes from this set all of its elements that are contained in
309 309 * the specified collection. If the specified collection is also
310 310 * a set, this operation effectively modifies this set so that its
311 311 * value is the <i>asymmetric set difference</i> of the two sets.
312 312 *
313 313 * @param c collection containing elements to be removed from this set
314 314 * @return <tt>true</tt> if this set changed as a result of the call
315 315 * @throws ClassCastException if the types of one or more elements in this
316 316 * set are incompatible with the specified collection
317 317 * @throws NullPointerException if the specified collection or any
318 318 * of its elements are null
319 319 */
320 320 public boolean removeAll(Collection<?> c) {
321 321 // Override AbstractSet version to avoid unnecessary call to size()
322 322 boolean modified = false;
323 323 for (Iterator<?> i = c.iterator(); i.hasNext(); )
324 324 if (remove(i.next()))
325 325 modified = true;
326 326 return modified;
327 327 }
328 328
329 329 /* ---------------- Relational operations -------------- */
330 330
331 331 /**
332 332 * @throws ClassCastException {@inheritDoc}
333 333 * @throws NullPointerException if the specified element is null
334 334 */
335 335 public E lower(E e) {
336 336 return m.lowerKey(e);
337 337 }
338 338
339 339 /**
340 340 * @throws ClassCastException {@inheritDoc}
341 341 * @throws NullPointerException if the specified element is null
342 342 */
343 343 public E floor(E e) {
344 344 return m.floorKey(e);
345 345 }
346 346
347 347 /**
348 348 * @throws ClassCastException {@inheritDoc}
349 349 * @throws NullPointerException if the specified element is null
350 350 */
351 351 public E ceiling(E e) {
352 352 return m.ceilingKey(e);
353 353 }
354 354
↓ open down ↓ |
354 lines elided |
↑ open up ↑ |
355 355 /**
356 356 * @throws ClassCastException {@inheritDoc}
357 357 * @throws NullPointerException if the specified element is null
358 358 */
359 359 public E higher(E e) {
360 360 return m.higherKey(e);
361 361 }
362 362
363 363 public E pollFirst() {
364 364 Map.Entry<E,Object> e = m.pollFirstEntry();
365 - return e == null? null : e.getKey();
365 + return (e == null) ? null : e.getKey();
366 366 }
367 367
368 368 public E pollLast() {
369 369 Map.Entry<E,Object> e = m.pollLastEntry();
370 - return e == null? null : e.getKey();
370 + return (e == null) ? null : e.getKey();
371 371 }
372 372
373 373
374 374 /* ---------------- SortedSet operations -------------- */
375 375
376 376
377 377 public Comparator<? super E> comparator() {
378 378 return m.comparator();
379 379 }
380 380
381 381 /**
382 382 * @throws NoSuchElementException {@inheritDoc}
383 383 */
384 384 public E first() {
385 385 return m.firstKey();
386 386 }
387 387
388 388 /**
389 389 * @throws NoSuchElementException {@inheritDoc}
390 390 */
391 391 public E last() {
392 392 return m.lastKey();
393 393 }
394 394
395 395 /**
396 396 * @throws ClassCastException {@inheritDoc}
397 397 * @throws NullPointerException if {@code fromElement} or
398 398 * {@code toElement} is null
399 399 * @throws IllegalArgumentException {@inheritDoc}
400 400 */
401 401 public NavigableSet<E> subSet(E fromElement,
402 402 boolean fromInclusive,
403 403 E toElement,
404 404 boolean toInclusive) {
405 405 return new ConcurrentSkipListSet<E>
406 406 (m.subMap(fromElement, fromInclusive,
407 407 toElement, toInclusive));
408 408 }
409 409
410 410 /**
411 411 * @throws ClassCastException {@inheritDoc}
412 412 * @throws NullPointerException if {@code toElement} is null
413 413 * @throws IllegalArgumentException {@inheritDoc}
414 414 */
415 415 public NavigableSet<E> headSet(E toElement, boolean inclusive) {
416 416 return new ConcurrentSkipListSet<E>(m.headMap(toElement, inclusive));
417 417 }
418 418
419 419 /**
420 420 * @throws ClassCastException {@inheritDoc}
421 421 * @throws NullPointerException if {@code fromElement} is null
422 422 * @throws IllegalArgumentException {@inheritDoc}
423 423 */
424 424 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
425 425 return new ConcurrentSkipListSet<E>(m.tailMap(fromElement, inclusive));
426 426 }
427 427
428 428 /**
429 429 * @throws ClassCastException {@inheritDoc}
430 430 * @throws NullPointerException if {@code fromElement} or
431 431 * {@code toElement} is null
432 432 * @throws IllegalArgumentException {@inheritDoc}
433 433 */
434 434 public NavigableSet<E> subSet(E fromElement, E toElement) {
435 435 return subSet(fromElement, true, toElement, false);
436 436 }
437 437
438 438 /**
439 439 * @throws ClassCastException {@inheritDoc}
440 440 * @throws NullPointerException if {@code toElement} is null
441 441 * @throws IllegalArgumentException {@inheritDoc}
442 442 */
443 443 public NavigableSet<E> headSet(E toElement) {
444 444 return headSet(toElement, false);
445 445 }
446 446
447 447 /**
448 448 * @throws ClassCastException {@inheritDoc}
449 449 * @throws NullPointerException if {@code fromElement} is null
450 450 * @throws IllegalArgumentException {@inheritDoc}
451 451 */
452 452 public NavigableSet<E> tailSet(E fromElement) {
453 453 return tailSet(fromElement, true);
454 454 }
455 455
456 456 /**
457 457 * Returns a reverse order view of the elements contained in this set.
458 458 * The descending set is backed by this set, so changes to the set are
459 459 * reflected in the descending set, and vice-versa.
460 460 *
461 461 * <p>The returned set has an ordering equivalent to
462 462 * <tt>{@link Collections#reverseOrder(Comparator) Collections.reverseOrder}(comparator())</tt>.
463 463 * The expression {@code s.descendingSet().descendingSet()} returns a
464 464 * view of {@code s} essentially equivalent to {@code s}.
465 465 *
466 466 * @return a reverse order view of this set
467 467 */
468 468 public NavigableSet<E> descendingSet() {
469 469 return new ConcurrentSkipListSet(m.descendingMap());
470 470 }
471 471
472 472 // Support for resetting map in clone
473 473 private static final Unsafe unsafe = Unsafe.getUnsafe();
474 474 private static final long mapOffset;
475 475 static {
476 476 try {
477 477 mapOffset = unsafe.objectFieldOffset
478 478 (ConcurrentSkipListSet.class.getDeclaredField("m"));
479 479 } catch (Exception ex) { throw new Error(ex); }
480 480 }
481 481 private void setMap(ConcurrentNavigableMap<E,Object> map) {
482 482 unsafe.putObjectVolatile(this, mapOffset, map);
483 483 }
484 484
485 485 }
↓ open down ↓ |
105 lines elided |
↑ open up ↑ |
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX