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