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