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