Source for java.util.concurrent.ConcurrentSkipListSet

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