GNU Classpath (0.98) | |
Frames | No Frames |
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: }
GNU Classpath (0.98) |