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.util.AbstractSet; 39 import java.util.Collection; 40 import java.util.Collections; 41 import java.util.Comparator; 42 import java.util.Iterator; 43 import java.util.Map; 44 import java.util.NavigableMap; 45 import java.util.NavigableSet; 46 import java.util.Set; 47 import java.util.SortedSet; 48 import java.util.Spliterator; 49 50 // BEGIN android-note 51 // removed link to collections framework docs 52 // fixed framework docs link to "Collection#optional" 53 // END android-note 54 55 /** 56 * A scalable concurrent {@link NavigableSet} implementation based on 57 * a {@link ConcurrentSkipListMap}. The elements of the set are kept 58 * sorted according to their {@linkplain Comparable natural ordering}, 59 * or by a {@link Comparator} provided at set creation time, depending 60 * on which constructor is used. 61 * 62 * <p>This implementation provides expected average <i>log(n)</i> time 63 * cost for the {@code contains}, {@code add}, and {@code remove} 64 * operations and their variants. Insertion, removal, and access 65 * operations safely execute concurrently by multiple threads. 66 * 67 * <p>Iterators and spliterators are 68 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 69 * 70 * <p>Ascending ordered views and their iterators are faster than 71 * descending ones. 72 * 73 * <p>Beware that, unlike in most collections, the {@code size} 74 * method is <em>not</em> a constant-time operation. Because of the 75 * asynchronous nature of these sets, determining the current number 76 * of elements requires a traversal of the elements, and so may report 77 * inaccurate results if this collection is modified during traversal. 78 * Additionally, the bulk operations {@code addAll}, 79 * {@code removeAll}, {@code retainAll}, {@code containsAll}, 80 * {@code equals}, and {@code toArray} are <em>not</em> guaranteed 81 * to be performed atomically. For example, an iterator operating 82 * concurrently with an {@code addAll} operation might view only some 83 * of the added elements. 84 * 85 * <p>This class and its iterators implement all of the 86 * <em>optional</em> methods of the {@link Set} and {@link Iterator} 87 * interfaces. Like most other concurrent collection implementations, 88 * this class does not permit the use of {@code null} elements, 89 * because {@code null} arguments and return values cannot be reliably 90 * distinguished from the absence of elements. 91 * 92 * @author Doug Lea 93 * @param <E> the type of elements maintained by this set 94 * @since 1.6 95 */ 96 public class ConcurrentSkipListSet<E> 97 extends AbstractSet<E> 98 implements NavigableSet<E>, Cloneable, java.io.Serializable { 99 100 private static final long serialVersionUID = -2479143111061671589L; 101 102 /** 103 * The underlying map. Uses Boolean.TRUE as value for each 104 * element. This field is declared final for the sake of thread 105 * safety, which entails some ugliness in clone(). 106 */ 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 unused) { 314 return false; 315 } catch (NullPointerException unused) { 316 return false; 317 } 318 } 319 320 /** 321 * Removes from this set all of its elements that are contained in 322 * the specified collection. If the specified collection is also 323 * a set, this operation effectively modifies this set so that its 324 * value is the <i>asymmetric set difference</i> of the two sets. 325 * 326 * @param c collection containing elements to be removed from this set 327 * @return {@code true} if this set changed as a result of the call 328 * @throws ClassCastException if the class of an element of this set 329 * is incompatible with the specified collection 330 * (<a href="../Collection.html#optional-restrictions">optional</a>) 331 * @throws NullPointerException if the specified collection or any 332 * of its elements are null 333 */ removeAll(Collection<?> c)334 public boolean removeAll(Collection<?> c) { 335 // Override AbstractSet version to avoid unnecessary call to size() 336 boolean modified = false; 337 for (Object e : c) 338 if (remove(e)) 339 modified = true; 340 return modified; 341 } 342 343 /* ---------------- Relational operations -------------- */ 344 345 /** 346 * @throws ClassCastException {@inheritDoc} 347 * @throws NullPointerException if the specified element is null 348 */ lower(E e)349 public E lower(E e) { 350 return m.lowerKey(e); 351 } 352 353 /** 354 * @throws ClassCastException {@inheritDoc} 355 * @throws NullPointerException if the specified element is null 356 */ floor(E e)357 public E floor(E e) { 358 return m.floorKey(e); 359 } 360 361 /** 362 * @throws ClassCastException {@inheritDoc} 363 * @throws NullPointerException if the specified element is null 364 */ ceiling(E e)365 public E ceiling(E e) { 366 return m.ceilingKey(e); 367 } 368 369 /** 370 * @throws ClassCastException {@inheritDoc} 371 * @throws NullPointerException if the specified element is null 372 */ higher(E e)373 public E higher(E e) { 374 return m.higherKey(e); 375 } 376 pollFirst()377 public E pollFirst() { 378 Map.Entry<E,Object> e = m.pollFirstEntry(); 379 return (e == null) ? null : e.getKey(); 380 } 381 pollLast()382 public E pollLast() { 383 Map.Entry<E,Object> e = m.pollLastEntry(); 384 return (e == null) ? null : e.getKey(); 385 } 386 387 388 /* ---------------- SortedSet operations -------------- */ 389 comparator()390 public Comparator<? super E> comparator() { 391 return m.comparator(); 392 } 393 394 /** 395 * @throws java.util.NoSuchElementException {@inheritDoc} 396 */ first()397 public E first() { 398 return m.firstKey(); 399 } 400 401 /** 402 * @throws java.util.NoSuchElementException {@inheritDoc} 403 */ last()404 public E last() { 405 return m.lastKey(); 406 } 407 408 /** 409 * @throws ClassCastException {@inheritDoc} 410 * @throws NullPointerException if {@code fromElement} or 411 * {@code toElement} is null 412 * @throws IllegalArgumentException {@inheritDoc} 413 */ subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)414 public NavigableSet<E> subSet(E fromElement, 415 boolean fromInclusive, 416 E toElement, 417 boolean toInclusive) { 418 return new ConcurrentSkipListSet<E> 419 (m.subMap(fromElement, fromInclusive, 420 toElement, toInclusive)); 421 } 422 423 /** 424 * @throws ClassCastException {@inheritDoc} 425 * @throws NullPointerException if {@code toElement} is null 426 * @throws IllegalArgumentException {@inheritDoc} 427 */ headSet(E toElement, boolean inclusive)428 public NavigableSet<E> headSet(E toElement, boolean inclusive) { 429 return new ConcurrentSkipListSet<E>(m.headMap(toElement, inclusive)); 430 } 431 432 /** 433 * @throws ClassCastException {@inheritDoc} 434 * @throws NullPointerException if {@code fromElement} is null 435 * @throws IllegalArgumentException {@inheritDoc} 436 */ tailSet(E fromElement, boolean inclusive)437 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) { 438 return new ConcurrentSkipListSet<E>(m.tailMap(fromElement, inclusive)); 439 } 440 441 /** 442 * @throws ClassCastException {@inheritDoc} 443 * @throws NullPointerException if {@code fromElement} or 444 * {@code toElement} is null 445 * @throws IllegalArgumentException {@inheritDoc} 446 */ subSet(E fromElement, E toElement)447 public NavigableSet<E> subSet(E fromElement, E toElement) { 448 return subSet(fromElement, true, toElement, false); 449 } 450 451 /** 452 * @throws ClassCastException {@inheritDoc} 453 * @throws NullPointerException if {@code toElement} is null 454 * @throws IllegalArgumentException {@inheritDoc} 455 */ headSet(E toElement)456 public NavigableSet<E> headSet(E toElement) { 457 return headSet(toElement, false); 458 } 459 460 /** 461 * @throws ClassCastException {@inheritDoc} 462 * @throws NullPointerException if {@code fromElement} is null 463 * @throws IllegalArgumentException {@inheritDoc} 464 */ tailSet(E fromElement)465 public NavigableSet<E> tailSet(E fromElement) { 466 return tailSet(fromElement, true); 467 } 468 469 /** 470 * Returns a reverse order view of the elements contained in this set. 471 * The descending set is backed by this set, so changes to the set are 472 * reflected in the descending set, and vice-versa. 473 * 474 * <p>The returned set has an ordering equivalent to 475 * {@link Collections#reverseOrder(Comparator) Collections.reverseOrder}{@code (comparator())}. 476 * The expression {@code s.descendingSet().descendingSet()} returns a 477 * view of {@code s} essentially equivalent to {@code s}. 478 * 479 * @return a reverse order view of this set 480 */ descendingSet()481 public NavigableSet<E> descendingSet() { 482 return new ConcurrentSkipListSet<E>(m.descendingMap()); 483 } 484 485 /** 486 * Returns a {@link Spliterator} over the elements in this set. 487 * 488 * <p>The {@code Spliterator} reports {@link Spliterator#CONCURRENT}, 489 * {@link Spliterator#NONNULL}, {@link Spliterator#DISTINCT}, 490 * {@link Spliterator#SORTED} and {@link Spliterator#ORDERED}, with an 491 * encounter order that is ascending order. Overriding implementations 492 * should document the reporting of additional characteristic values. 493 * 494 * <p>The spliterator's comparator (see 495 * {@link java.util.Spliterator#getComparator()}) is {@code null} if 496 * the set's comparator (see {@link #comparator()}) is {@code null}. 497 * Otherwise, the spliterator's comparator is the same as or imposes the 498 * same total ordering as the set's comparator. 499 * 500 * @return a {@code Spliterator} over the elements in this set 501 * @since 1.8 502 */ spliterator()503 public Spliterator<E> spliterator() { 504 return (m instanceof ConcurrentSkipListMap) 505 ? ((ConcurrentSkipListMap<E,?>)m).keySpliterator() 506 : ((ConcurrentSkipListMap.SubMap<E,?>)m).new SubMapKeyIterator(); 507 } 508 509 // Support for resetting map in clone setMap(ConcurrentNavigableMap<E,Object> map)510 private void setMap(ConcurrentNavigableMap<E,Object> map) { 511 U.putObjectVolatile(this, MAP, map); 512 } 513 514 private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe(); 515 private static final long MAP; 516 static { 517 try { 518 MAP = U.objectFieldOffset 519 (ConcurrentSkipListSet.class.getDeclaredField("m")); 520 } catch (ReflectiveOperationException e) { 521 throw new Error(e); 522 } 523 } 524 } 525