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