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