src/share/classes/java/util/concurrent/ConcurrentSkipListSet.java

Print this page




  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 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>


 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      */


 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);


 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 }


  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>


 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      */


 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);


 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 }