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 /** 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 * Additionally, the bulk operations {@code addAll}, 74 * {@code removeAll}, {@code retainAll}, {@code containsAll}, 75 * {@code equals}, and {@code toArray} are <em>not</em> guaranteed 76 * to be performed atomically. For example, an iterator operating 77 * concurrently with an {@code addAll} operation might view only some 78 * 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}/../technotes/guides/collections/index.html"> 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 unused) { 313 return false; 314 } catch (NullPointerException unused) { 315 return false; 316 } 317 } 318 319 /** 320 * Removes from this set all of its elements that are contained in 321 * the specified collection. If the specified collection is also 322 * a set, this operation effectively modifies this set so that its 323 * value is the <i>asymmetric set difference</i> of the two sets. 324 * 325 * @param c collection containing elements to be removed from this set 326 * @return {@code true} if this set changed as a result of the call 327 * @throws ClassCastException if the class of an element of this set 328 * is incompatible with the specified collection 329 * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>) 330 * @throws NullPointerException if the specified collection or any 331 * of its elements are null 332 */ 333 public boolean removeAll(Collection<?> c) { 334 // Override AbstractSet version to avoid unnecessary call to size() 335 boolean modified = false; 336 for (Object e : c) 337 if (remove(e)) 338 modified = true; 339 return modified; 340 } 341 342 /* ---------------- Relational operations -------------- */ 343 344 /** 345 * @throws ClassCastException {@inheritDoc} 346 * @throws NullPointerException if the specified element is null 347 */ 348 public E lower(E e) { 349 return m.lowerKey(e); 350 } 351 352 /** 353 * @throws ClassCastException {@inheritDoc} 354 * @throws NullPointerException if the specified element is null 355 */ 356 public E floor(E e) { 357 return m.floorKey(e); 358 } 359 360 /** 361 * @throws ClassCastException {@inheritDoc} 362 * @throws NullPointerException if the specified element is null 363 */ 364 public E ceiling(E e) { 365 return m.ceilingKey(e); 366 } 367 368 /** 369 * @throws ClassCastException {@inheritDoc} 370 * @throws NullPointerException if the specified element is null 371 */ 372 public E higher(E e) { 373 return m.higherKey(e); 374 } 375 376 public E pollFirst() { 377 Map.Entry<E,Object> e = m.pollFirstEntry(); 378 return (e == null) ? null : e.getKey(); 379 } 380 381 public E pollLast() { 382 Map.Entry<E,Object> e = m.pollLastEntry(); 383 return (e == null) ? null : e.getKey(); 384 } 385 386 387 /* ---------------- SortedSet operations -------------- */ 388 389 public Comparator<? super E> comparator() { 390 return m.comparator(); 391 } 392 393 /** 394 * @throws java.util.NoSuchElementException {@inheritDoc} 395 */ 396 public E first() { 397 return m.firstKey(); 398 } 399 400 /** 401 * @throws java.util.NoSuchElementException {@inheritDoc} 402 */ 403 public E last() { 404 return m.lastKey(); 405 } 406 407 /** 408 * @throws ClassCastException {@inheritDoc} 409 * @throws NullPointerException if {@code fromElement} or 410 * {@code toElement} is null 411 * @throws IllegalArgumentException {@inheritDoc} 412 */ 413 public NavigableSet<E> subSet(E fromElement, 414 boolean fromInclusive, 415 E toElement, 416 boolean toInclusive) { 417 return new ConcurrentSkipListSet<E> 418 (m.subMap(fromElement, fromInclusive, 419 toElement, toInclusive)); 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, boolean inclusive) { 428 return new ConcurrentSkipListSet<E>(m.headMap(toElement, inclusive)); 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, boolean inclusive) { 437 return new ConcurrentSkipListSet<E>(m.tailMap(fromElement, inclusive)); 438 } 439 440 /** 441 * @throws ClassCastException {@inheritDoc} 442 * @throws NullPointerException if {@code fromElement} or 443 * {@code toElement} is null 444 * @throws IllegalArgumentException {@inheritDoc} 445 */ 446 public NavigableSet<E> subSet(E fromElement, E toElement) { 447 return subSet(fromElement, true, toElement, false); 448 } 449 450 /** 451 * @throws ClassCastException {@inheritDoc} 452 * @throws NullPointerException if {@code toElement} is null 453 * @throws IllegalArgumentException {@inheritDoc} 454 */ 455 public NavigableSet<E> headSet(E toElement) { 456 return headSet(toElement, false); 457 } 458 459 /** 460 * @throws ClassCastException {@inheritDoc} 461 * @throws NullPointerException if {@code fromElement} is null 462 * @throws IllegalArgumentException {@inheritDoc} 463 */ 464 public NavigableSet<E> tailSet(E fromElement) { 465 return tailSet(fromElement, true); 466 } 467 468 /** 469 * Returns a reverse order view of the elements contained in this set. 470 * The descending set is backed by this set, so changes to the set are 471 * reflected in the descending set, and vice-versa. 472 * 473 * <p>The returned set has an ordering equivalent to 474 * {@link Collections#reverseOrder(Comparator) Collections.reverseOrder}{@code (comparator())}. 475 * The expression {@code s.descendingSet().descendingSet()} returns a 476 * view of {@code s} essentially equivalent to {@code s}. 477 * 478 * @return a reverse order view of this set 479 */ 480 public NavigableSet<E> descendingSet() { 481 return new ConcurrentSkipListSet<E>(m.descendingMap()); 482 } 483 484 /** 485 * Returns a {@link Spliterator} over the elements in this set. 486 * 487 * <p>The {@code Spliterator} reports {@link Spliterator#CONCURRENT}, 488 * {@link Spliterator#NONNULL}, {@link Spliterator#DISTINCT}, 489 * {@link Spliterator#SORTED} and {@link Spliterator#ORDERED}, with an 490 * encounter order that is ascending order. Overriding implementations 491 * should document the reporting of additional characteristic values. 492 * 493 * <p>The spliterator's comparator (see 494 * {@link java.util.Spliterator#getComparator()}) is {@code null} if 495 * the set's comparator (see {@link #comparator()}) is {@code null}. 496 * Otherwise, the spliterator's comparator is the same as or imposes the 497 * same total ordering as the set's comparator. 498 * 499 * @return a {@code Spliterator} over the elements in this set 500 * @since 1.8 501 */ 502 public Spliterator<E> spliterator() { 503 return (m instanceof ConcurrentSkipListMap) 504 ? ((ConcurrentSkipListMap<E,?>)m).keySpliterator() 505 : ((ConcurrentSkipListMap.SubMap<E,?>)m).new SubMapKeyIterator(); 506 } 507 508 // Support for resetting map in clone 509 private void setMap(ConcurrentNavigableMap<E,Object> map) { 510 U.putObjectVolatile(this, MAP, map); 511 } 512 513 private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe(); 514 private static final long MAP; 515 static { 516 try { 517 MAP = U.objectFieldOffset 518 (ConcurrentSkipListSet.class.getDeclaredField("m")); 519 } catch (ReflectiveOperationException e) { 520 throw new Error(e); 521 } 522 } 523 }