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