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