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 private final ConcurrentNavigableMap<E,Object> m; 107 108 /** 109 * Constructs a new, empty set that orders its elements according to 110 * their {@linkplain Comparable natural ordering}. 111 */ ConcurrentSkipListSet()112 public ConcurrentSkipListSet() { 113 m = new ConcurrentSkipListMap<E,Object>(); 114 } 115 116 /** 117 * Constructs a new, empty set that orders its elements according to 118 * the specified comparator. 119 * 120 * @param comparator the comparator that will be used to order this set. 121 * If {@code null}, the {@linkplain Comparable natural 122 * ordering} of the elements will be used. 123 */ ConcurrentSkipListSet(Comparator<? super E> comparator)124 public ConcurrentSkipListSet(Comparator<? super E> comparator) { 125 m = new ConcurrentSkipListMap<E,Object>(comparator); 126 } 127 128 /** 129 * Constructs a new set containing the elements in the specified 130 * collection, that orders its elements according to their 131 * {@linkplain Comparable natural ordering}. 132 * 133 * @param c The elements that will comprise the new set 134 * @throws ClassCastException if the elements in {@code c} are 135 * not {@link Comparable}, or are not mutually comparable 136 * @throws NullPointerException if the specified collection or any 137 * of its elements are null 138 */ ConcurrentSkipListSet(Collection<? extends E> c)139 public ConcurrentSkipListSet(Collection<? extends E> c) { 140 m = new ConcurrentSkipListMap<E,Object>(); 141 addAll(c); 142 } 143 144 /** 145 * Constructs a new set containing the same elements and using the 146 * same ordering as the specified sorted set. 147 * 148 * @param s sorted set whose elements will comprise the new set 149 * @throws NullPointerException if the specified sorted set or any 150 * of its elements are null 151 */ ConcurrentSkipListSet(SortedSet<E> s)152 public ConcurrentSkipListSet(SortedSet<E> s) { 153 m = new ConcurrentSkipListMap<E,Object>(s.comparator()); 154 addAll(s); 155 } 156 157 /** 158 * For use by submaps 159 */ ConcurrentSkipListSet(ConcurrentNavigableMap<E,Object> m)160 ConcurrentSkipListSet(ConcurrentNavigableMap<E,Object> m) { 161 this.m = m; 162 } 163 164 /** 165 * Returns a shallow copy of this {@code ConcurrentSkipListSet} 166 * instance. (The elements themselves are not cloned.) 167 * 168 * @return a shallow copy of this set 169 */ clone()170 public ConcurrentSkipListSet<E> clone() { 171 try { 172 @SuppressWarnings("unchecked") 173 ConcurrentSkipListSet<E> clone = 174 (ConcurrentSkipListSet<E>) super.clone(); 175 clone.setMap(new ConcurrentSkipListMap<E,Object>(m)); 176 return clone; 177 } catch (CloneNotSupportedException e) { 178 throw new InternalError(); 179 } 180 } 181 182 /* ---------------- Set operations -------------- */ 183 184 /** 185 * Returns the number of elements in this set. If this set 186 * contains more than {@code Integer.MAX_VALUE} elements, it 187 * returns {@code Integer.MAX_VALUE}. 188 * 189 * <p>Beware that, unlike in most collections, this method is 190 * <em>NOT</em> a constant-time operation. Because of the 191 * asynchronous nature of these sets, determining the current 192 * number of elements requires traversing them all to count them. 193 * Additionally, it is possible for the size to change during 194 * execution of this method, in which case the returned result 195 * will be inaccurate. Thus, this method is typically not very 196 * useful in concurrent applications. 197 * 198 * @return the number of elements in this set 199 */ size()200 public int size() { 201 return m.size(); 202 } 203 204 /** 205 * Returns {@code true} if this set contains no elements. 206 * @return {@code true} if this set contains no elements 207 */ isEmpty()208 public boolean isEmpty() { 209 return m.isEmpty(); 210 } 211 212 /** 213 * Returns {@code true} if this set contains the specified element. 214 * More formally, returns {@code true} if and only if this set 215 * contains an element {@code e} such that {@code o.equals(e)}. 216 * 217 * @param o object to be checked for containment in this set 218 * @return {@code true} if this set contains the specified element 219 * @throws ClassCastException if the specified element cannot be 220 * compared with the elements currently in this set 221 * @throws NullPointerException if the specified element is null 222 */ contains(Object o)223 public boolean contains(Object o) { 224 return m.containsKey(o); 225 } 226 227 /** 228 * Adds the specified element to this set if it is not already present. 229 * More formally, adds the specified element {@code e} to this set if 230 * the set contains no element {@code e2} such that {@code e.equals(e2)}. 231 * If this set already contains the element, the call leaves the set 232 * unchanged and returns {@code false}. 233 * 234 * @param e element to be added to this set 235 * @return {@code true} if this set did not already contain the 236 * specified element 237 * @throws ClassCastException if {@code e} cannot be compared 238 * with the elements currently in this set 239 * @throws NullPointerException if the specified element is null 240 */ add(E e)241 public boolean add(E e) { 242 return m.putIfAbsent(e, Boolean.TRUE) == null; 243 } 244 245 /** 246 * Removes the specified element from this set if it is present. 247 * More formally, removes an element {@code e} such that 248 * {@code o.equals(e)}, if this set contains such an element. 249 * Returns {@code true} if this set contained the element (or 250 * equivalently, if this set changed as a result of the call). 251 * (This set will not contain the element once the call returns.) 252 * 253 * @param o object to be removed from this set, if present 254 * @return {@code true} if this set contained the specified element 255 * @throws ClassCastException if {@code o} cannot be compared 256 * with the elements currently in this set 257 * @throws NullPointerException if the specified element is null 258 */ remove(Object o)259 public boolean remove(Object o) { 260 return m.remove(o, Boolean.TRUE); 261 } 262 263 /** 264 * Removes all of the elements from this set. 265 */ clear()266 public void clear() { 267 m.clear(); 268 } 269 270 /** 271 * Returns an iterator over the elements in this set in ascending order. 272 * 273 * @return an iterator over the elements in this set in ascending order 274 */ iterator()275 public Iterator<E> iterator() { 276 return m.navigableKeySet().iterator(); 277 } 278 279 /** 280 * Returns an iterator over the elements in this set in descending order. 281 * 282 * @return an iterator over the elements in this set in descending order 283 */ descendingIterator()284 public Iterator<E> descendingIterator() { 285 return m.descendingKeySet().iterator(); 286 } 287 288 289 /* ---------------- AbstractSet Overrides -------------- */ 290 291 /** 292 * Compares the specified object with this set for equality. Returns 293 * {@code true} if the specified object is also a set, the two sets 294 * have the same size, and every member of the specified set is 295 * contained in this set (or equivalently, every member of this set is 296 * contained in the specified set). This definition ensures that the 297 * equals method works properly across different implementations of the 298 * set interface. 299 * 300 * @param o the object to be compared for equality with this set 301 * @return {@code true} if the specified object is equal to this set 302 */ equals(Object o)303 public boolean equals(Object o) { 304 // Override AbstractSet version to avoid calling size() 305 if (o == this) 306 return true; 307 if (!(o instanceof Set)) 308 return false; 309 Collection<?> c = (Collection<?>) o; 310 try { 311 return containsAll(c) && c.containsAll(this); 312 } catch (ClassCastException | NullPointerException unused) { 313 return false; 314 } 315 } 316 317 /** 318 * Removes from this set all of its elements that are contained in 319 * the specified collection. If the specified collection is also 320 * a set, this operation effectively modifies this set so that its 321 * value is the <i>asymmetric set difference</i> of the two sets. 322 * 323 * @param c collection containing elements to be removed from this set 324 * @return {@code true} if this set changed as a result of the call 325 * @throws ClassCastException if the class of an element of this set 326 * is incompatible with the specified collection 327 * (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>) 328 * @throws NullPointerException if the specified collection or any 329 * of its elements are null 330 */ removeAll(Collection<?> c)331 public boolean removeAll(Collection<?> c) { 332 // Override AbstractSet version to avoid unnecessary call to size() 333 boolean modified = false; 334 for (Object e : c) 335 if (remove(e)) 336 modified = true; 337 return modified; 338 } 339 340 /* ---------------- Relational operations -------------- */ 341 342 /** 343 * @throws ClassCastException {@inheritDoc} 344 * @throws NullPointerException if the specified element is null 345 */ lower(E e)346 public E lower(E e) { 347 return m.lowerKey(e); 348 } 349 350 /** 351 * @throws ClassCastException {@inheritDoc} 352 * @throws NullPointerException if the specified element is null 353 */ floor(E e)354 public E floor(E e) { 355 return m.floorKey(e); 356 } 357 358 /** 359 * @throws ClassCastException {@inheritDoc} 360 * @throws NullPointerException if the specified element is null 361 */ ceiling(E e)362 public E ceiling(E e) { 363 return m.ceilingKey(e); 364 } 365 366 /** 367 * @throws ClassCastException {@inheritDoc} 368 * @throws NullPointerException if the specified element is null 369 */ higher(E e)370 public E higher(E e) { 371 return m.higherKey(e); 372 } 373 pollFirst()374 public E pollFirst() { 375 Map.Entry<E,Object> e = m.pollFirstEntry(); 376 return (e == null) ? null : e.getKey(); 377 } 378 pollLast()379 public E pollLast() { 380 Map.Entry<E,Object> e = m.pollLastEntry(); 381 return (e == null) ? null : e.getKey(); 382 } 383 384 385 /* ---------------- SortedSet operations -------------- */ 386 comparator()387 public Comparator<? super E> comparator() { 388 return m.comparator(); 389 } 390 391 /** 392 * @throws java.util.NoSuchElementException {@inheritDoc} 393 */ first()394 public E first() { 395 return m.firstKey(); 396 } 397 398 /** 399 * @throws java.util.NoSuchElementException {@inheritDoc} 400 */ last()401 public E last() { 402 return m.lastKey(); 403 } 404 405 /** 406 * @throws ClassCastException {@inheritDoc} 407 * @throws NullPointerException if {@code fromElement} or 408 * {@code toElement} is null 409 * @throws IllegalArgumentException {@inheritDoc} 410 */ subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)411 public NavigableSet<E> subSet(E fromElement, 412 boolean fromInclusive, 413 E toElement, 414 boolean toInclusive) { 415 return new ConcurrentSkipListSet<E> 416 (m.subMap(fromElement, fromInclusive, 417 toElement, toInclusive)); 418 } 419 420 /** 421 * @throws ClassCastException {@inheritDoc} 422 * @throws NullPointerException if {@code toElement} is null 423 * @throws IllegalArgumentException {@inheritDoc} 424 */ headSet(E toElement, boolean inclusive)425 public NavigableSet<E> headSet(E toElement, boolean inclusive) { 426 return new ConcurrentSkipListSet<E>(m.headMap(toElement, inclusive)); 427 } 428 429 /** 430 * @throws ClassCastException {@inheritDoc} 431 * @throws NullPointerException if {@code fromElement} is null 432 * @throws IllegalArgumentException {@inheritDoc} 433 */ tailSet(E fromElement, boolean inclusive)434 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) { 435 return new ConcurrentSkipListSet<E>(m.tailMap(fromElement, inclusive)); 436 } 437 438 /** 439 * @throws ClassCastException {@inheritDoc} 440 * @throws NullPointerException if {@code fromElement} or 441 * {@code toElement} is null 442 * @throws IllegalArgumentException {@inheritDoc} 443 */ subSet(E fromElement, E toElement)444 public NavigableSet<E> subSet(E fromElement, E toElement) { 445 return subSet(fromElement, true, toElement, false); 446 } 447 448 /** 449 * @throws ClassCastException {@inheritDoc} 450 * @throws NullPointerException if {@code toElement} is null 451 * @throws IllegalArgumentException {@inheritDoc} 452 */ headSet(E toElement)453 public NavigableSet<E> headSet(E toElement) { 454 return headSet(toElement, false); 455 } 456 457 /** 458 * @throws ClassCastException {@inheritDoc} 459 * @throws NullPointerException if {@code fromElement} is null 460 * @throws IllegalArgumentException {@inheritDoc} 461 */ tailSet(E fromElement)462 public NavigableSet<E> tailSet(E fromElement) { 463 return tailSet(fromElement, true); 464 } 465 466 /** 467 * Returns a reverse order view of the elements contained in this set. 468 * The descending set is backed by this set, so changes to the set are 469 * reflected in the descending set, and vice-versa. 470 * 471 * <p>The returned set has an ordering equivalent to 472 * {@link Collections#reverseOrder(Comparator) Collections.reverseOrder}{@code (comparator())}. 473 * The expression {@code s.descendingSet().descendingSet()} returns a 474 * view of {@code s} essentially equivalent to {@code s}. 475 * 476 * @return a reverse order view of this set 477 */ descendingSet()478 public NavigableSet<E> descendingSet() { 479 return new ConcurrentSkipListSet<E>(m.descendingMap()); 480 } 481 482 /** 483 * Returns a {@link Spliterator} over the elements in this set. 484 * 485 * <p>The {@code Spliterator} reports {@link Spliterator#CONCURRENT}, 486 * {@link Spliterator#NONNULL}, {@link Spliterator#DISTINCT}, 487 * {@link Spliterator#SORTED} and {@link Spliterator#ORDERED}, with an 488 * encounter order that is ascending order. Overriding implementations 489 * should document the reporting of additional characteristic values. 490 * 491 * <p>The {@linkplain Spliterator#getComparator() spliterator's comparator} 492 * is {@code null} if the {@linkplain #comparator() set's comparator} 493 * is {@code null}. 494 * Otherwise, the spliterator's comparator is the same as or imposes the 495 * same total ordering as the set's comparator. 496 * 497 * @return a {@code Spliterator} over the elements in this set 498 * @since 1.8 499 */ spliterator()500 public Spliterator<E> spliterator() { 501 return (m instanceof ConcurrentSkipListMap) 502 ? ((ConcurrentSkipListMap<E,?>)m).keySpliterator() 503 : ((ConcurrentSkipListMap.SubMap<E,?>)m).new SubMapKeyIterator(); 504 } 505 506 /** Initializes map field; for use in clone. */ setMap(ConcurrentNavigableMap<E,Object> map)507 private void setMap(ConcurrentNavigableMap<E,Object> map) { 508 Field mapField = java.security.AccessController.doPrivileged( 509 (java.security.PrivilegedAction<Field>) () -> { 510 try { 511 Field f = ConcurrentSkipListSet.class 512 .getDeclaredField("m"); 513 f.setAccessible(true); 514 return f; 515 } catch (ReflectiveOperationException e) { 516 throw new Error(e); 517 }}); 518 try { 519 mapField.set(this, map); 520 } catch (IllegalAccessException e) { 521 throw new Error(e); 522 } 523 } 524 } 525