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