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