| /* |
| * Written by Doug Lea with assistance from members of JCP JSR-166 |
| * Expert Group and released to the public domain, as explained at |
| * http://creativecommons.org/licenses/publicdomain |
| */ |
| |
| package java.util.concurrent; |
| |
| import java.util.AbstractSet; |
| import java.util.Collection; |
| import java.util.Collections; |
| import java.util.Comparator; |
| import java.util.ConcurrentModificationException; |
| import java.util.Iterator; |
| import java.util.Map; |
| import java.util.NavigableSet; |
| import java.util.NoSuchElementException; |
| import java.util.Set; |
| import java.util.SortedSet; |
| import sun.misc.Unsafe; |
| |
| /** |
| * A scalable concurrent {@link NavigableSet} implementation based on |
| * a {@link ConcurrentSkipListMap}. The elements of the set are kept |
| * sorted according to their {@linkplain Comparable natural ordering}, |
| * or by a {@link Comparator} provided at set creation time, depending |
| * on which constructor is used. |
| * |
| * <p>This implementation provides expected average <i>log(n)</i> time |
| * cost for the <tt>contains</tt>, <tt>add</tt>, and <tt>remove</tt> |
| * operations and their variants. Insertion, removal, and access |
| * operations safely execute concurrently by multiple threads. |
| * Iterators are <i>weakly consistent</i>, returning elements |
| * reflecting the state of the set at some point at or since the |
| * creation of the iterator. They do <em>not</em> throw {@link |
| * ConcurrentModificationException}, and may proceed concurrently with |
| * other operations. Ascending ordered views and their iterators are |
| * faster than descending ones. |
| * |
| * <p>Beware that, unlike in most collections, the <tt>size</tt> |
| * method is <em>not</em> a constant-time operation. Because of the |
| * asynchronous nature of these sets, determining the current number |
| * of elements requires a traversal of the elements. Additionally, the |
| * bulk operations <tt>addAll</tt>, <tt>removeAll</tt>, |
| * <tt>retainAll</tt>, and <tt>containsAll</tt> are <em>not</em> |
| * guaranteed to be performed atomically. For example, an iterator |
| * operating concurrently with an <tt>addAll</tt> operation might view |
| * only some of the added elements. |
| * |
| * <p>This class and its iterators implement all of the |
| * <em>optional</em> methods of the {@link Set} and {@link Iterator} |
| * interfaces. Like most other concurrent collection implementations, |
| * this class does not permit the use of <tt>null</tt> elements, |
| * because <tt>null</tt> arguments and return values cannot be reliably |
| * distinguished from the absence of elements. |
| * |
| * <p>This class is a member of the |
| * <a href="{@docRoot}/../technotes/guides/collections/index.html"> |
| * Java Collections Framework</a>. |
| * |
| * @author Doug Lea |
| * @param <E> the type of elements maintained by this set |
| * @since 1.6 |
| */ |
| public class ConcurrentSkipListSet<E> |
| extends AbstractSet<E> |
| implements NavigableSet<E>, Cloneable, java.io.Serializable { |
| |
| private static final long serialVersionUID = -2479143111061671589L; |
| |
| /** |
| * The underlying map. Uses Boolean.TRUE as value for each |
| * element. This field is declared final for the sake of thread |
| * safety, which entails some ugliness in clone() |
| */ |
| private final ConcurrentNavigableMap<E,Object> m; |
| |
| /** |
| * Constructs a new, empty set that orders its elements according to |
| * their {@linkplain Comparable natural ordering}. |
| */ |
| public ConcurrentSkipListSet() { |
| m = new ConcurrentSkipListMap<E,Object>(); |
| } |
| |
| /** |
| * Constructs a new, empty set that orders its elements according to |
| * the specified comparator. |
| * |
| * @param comparator the comparator that will be used to order this set. |
| * If <tt>null</tt>, the {@linkplain Comparable natural |
| * ordering} of the elements will be used. |
| */ |
| public ConcurrentSkipListSet(Comparator<? super E> comparator) { |
| m = new ConcurrentSkipListMap<E,Object>(comparator); |
| } |
| |
| /** |
| * Constructs a new set containing the elements in the specified |
| * collection, that orders its elements according to their |
| * {@linkplain Comparable natural ordering}. |
| * |
| * @param c The elements that will comprise the new set |
| * @throws ClassCastException if the elements in <tt>c</tt> are |
| * not {@link Comparable}, or are not mutually comparable |
| * @throws NullPointerException if the specified collection or any |
| * of its elements are null |
| */ |
| public ConcurrentSkipListSet(Collection<? extends E> c) { |
| m = new ConcurrentSkipListMap<E,Object>(); |
| addAll(c); |
| } |
| |
| /** |
| * Constructs a new set containing the same elements and using the |
| * same ordering as the specified sorted set. |
| * |
| * @param s sorted set whose elements will comprise the new set |
| * @throws NullPointerException if the specified sorted set or any |
| * of its elements are null |
| */ |
| public ConcurrentSkipListSet(SortedSet<E> s) { |
| m = new ConcurrentSkipListMap<E,Object>(s.comparator()); |
| addAll(s); |
| } |
| |
| /** |
| * For use by submaps |
| */ |
| ConcurrentSkipListSet(ConcurrentNavigableMap<E,Object> m) { |
| this.m = m; |
| } |
| |
| /** |
| * Returns a shallow copy of this <tt>ConcurrentSkipListSet</tt> |
| * instance. (The elements themselves are not cloned.) |
| * |
| * @return a shallow copy of this set |
| */ |
| public ConcurrentSkipListSet<E> clone() { |
| ConcurrentSkipListSet<E> clone = null; |
| try { |
| clone = (ConcurrentSkipListSet<E>) super.clone(); |
| clone.setMap(new ConcurrentSkipListMap(m)); |
| } catch (CloneNotSupportedException e) { |
| throw new InternalError(); |
| } |
| |
| return clone; |
| } |
| |
| /* ---------------- Set operations -------------- */ |
| |
| /** |
| * Returns the number of elements in this set. If this set |
| * contains more than <tt>Integer.MAX_VALUE</tt> elements, it |
| * returns <tt>Integer.MAX_VALUE</tt>. |
| * |
| * <p>Beware that, unlike in most collections, this method is |
| * <em>NOT</em> a constant-time operation. Because of the |
| * asynchronous nature of these sets, determining the current |
| * number of elements requires traversing them all to count them. |
| * Additionally, it is possible for the size to change during |
| * execution of this method, in which case the returned result |
| * will be inaccurate. Thus, this method is typically not very |
| * useful in concurrent applications. |
| * |
| * @return the number of elements in this set |
| */ |
| public int size() { |
| return m.size(); |
| } |
| |
| /** |
| * Returns <tt>true</tt> if this set contains no elements. |
| * @return <tt>true</tt> if this set contains no elements |
| */ |
| public boolean isEmpty() { |
| return m.isEmpty(); |
| } |
| |
| /** |
| * Returns <tt>true</tt> if this set contains the specified element. |
| * More formally, returns <tt>true</tt> if and only if this set |
| * contains an element <tt>e</tt> such that <tt>o.equals(e)</tt>. |
| * |
| * @param o object to be checked for containment in this set |
| * @return <tt>true</tt> if this set contains the specified element |
| * @throws ClassCastException if the specified element cannot be |
| * compared with the elements currently in this set |
| * @throws NullPointerException if the specified element is null |
| */ |
| public boolean contains(Object o) { |
| return m.containsKey(o); |
| } |
| |
| /** |
| * Adds the specified element to this set if it is not already present. |
| * More formally, adds the specified element <tt>e</tt> to this set if |
| * the set contains no element <tt>e2</tt> such that <tt>e.equals(e2)</tt>. |
| * If this set already contains the element, the call leaves the set |
| * unchanged and returns <tt>false</tt>. |
| * |
| * @param e element to be added to this set |
| * @return <tt>true</tt> if this set did not already contain the |
| * specified element |
| * @throws ClassCastException if <tt>e</tt> cannot be compared |
| * with the elements currently in this set |
| * @throws NullPointerException if the specified element is null |
| */ |
| public boolean add(E e) { |
| return m.putIfAbsent(e, Boolean.TRUE) == null; |
| } |
| |
| /** |
| * Removes the specified element from this set if it is present. |
| * More formally, removes an element <tt>e</tt> such that |
| * <tt>o.equals(e)</tt>, if this set contains such an element. |
| * Returns <tt>true</tt> if this set contained the element (or |
| * equivalently, if this set changed as a result of the call). |
| * (This set will not contain the element once the call returns.) |
| * |
| * @param o object to be removed from this set, if present |
| * @return <tt>true</tt> if this set contained the specified element |
| * @throws ClassCastException if <tt>o</tt> cannot be compared |
| * with the elements currently in this set |
| * @throws NullPointerException if the specified element is null |
| */ |
| public boolean remove(Object o) { |
| return m.remove(o, Boolean.TRUE); |
| } |
| |
| /** |
| * Removes all of the elements from this set. |
| */ |
| public void clear() { |
| m.clear(); |
| } |
| |
| /** |
| * Returns an iterator over the elements in this set in ascending order. |
| * |
| * @return an iterator over the elements in this set in ascending order |
| */ |
| public Iterator<E> iterator() { |
| return m.navigableKeySet().iterator(); |
| } |
| |
| /** |
| * Returns an iterator over the elements in this set in descending order. |
| * |
| * @return an iterator over the elements in this set in descending order |
| */ |
| public Iterator<E> descendingIterator() { |
| return m.descendingKeySet().iterator(); |
| } |
| |
| |
| /* ---------------- AbstractSet Overrides -------------- */ |
| |
| /** |
| * Compares the specified object with this set for equality. Returns |
| * <tt>true</tt> if the specified object is also a set, the two sets |
| * have the same size, and every member of the specified set is |
| * contained in this set (or equivalently, every member of this set is |
| * contained in the specified set). This definition ensures that the |
| * equals method works properly across different implementations of the |
| * set interface. |
| * |
| * @param o the object to be compared for equality with this set |
| * @return <tt>true</tt> if the specified object is equal to this set |
| */ |
| public boolean equals(Object o) { |
| // Override AbstractSet version to avoid calling size() |
| if (o == this) |
| return true; |
| if (!(o instanceof Set)) |
| return false; |
| Collection<?> c = (Collection<?>) o; |
| try { |
| return containsAll(c) && c.containsAll(this); |
| } catch (ClassCastException unused) { |
| return false; |
| } catch (NullPointerException unused) { |
| return false; |
| } |
| } |
| |
| /** |
| * Removes from this set all of its elements that are contained in |
| * the specified collection. If the specified collection is also |
| * a set, this operation effectively modifies this set so that its |
| * value is the <i>asymmetric set difference</i> of the two sets. |
| * |
| * @param c collection containing elements to be removed from this set |
| * @return <tt>true</tt> if this set changed as a result of the call |
| * @throws ClassCastException if the types of one or more elements in this |
| * set are incompatible with the specified collection |
| * @throws NullPointerException if the specified collection or any |
| * of its elements are null |
| */ |
| public boolean removeAll(Collection<?> c) { |
| // Override AbstractSet version to avoid unnecessary call to size() |
| boolean modified = false; |
| for (Iterator<?> i = c.iterator(); i.hasNext(); ) |
| if (remove(i.next())) |
| modified = true; |
| return modified; |
| } |
| |
| /* ---------------- Relational operations -------------- */ |
| |
| /** |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException if the specified element is null |
| */ |
| public E lower(E e) { |
| return m.lowerKey(e); |
| } |
| |
| /** |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException if the specified element is null |
| */ |
| public E floor(E e) { |
| return m.floorKey(e); |
| } |
| |
| /** |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException if the specified element is null |
| */ |
| public E ceiling(E e) { |
| return m.ceilingKey(e); |
| } |
| |
| /** |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException if the specified element is null |
| */ |
| public E higher(E e) { |
| return m.higherKey(e); |
| } |
| |
| public E pollFirst() { |
| Map.Entry<E,Object> e = m.pollFirstEntry(); |
| return e == null? null : e.getKey(); |
| } |
| |
| public E pollLast() { |
| Map.Entry<E,Object> e = m.pollLastEntry(); |
| return e == null? null : e.getKey(); |
| } |
| |
| |
| /* ---------------- SortedSet operations -------------- */ |
| |
| |
| public Comparator<? super E> comparator() { |
| return m.comparator(); |
| } |
| |
| /** |
| * @throws NoSuchElementException {@inheritDoc} |
| */ |
| public E first() { |
| return m.firstKey(); |
| } |
| |
| /** |
| * @throws NoSuchElementException {@inheritDoc} |
| */ |
| public E last() { |
| return m.lastKey(); |
| } |
| |
| /** |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException if {@code fromElement} or |
| * {@code toElement} is null |
| * @throws IllegalArgumentException {@inheritDoc} |
| */ |
| public NavigableSet<E> subSet(E fromElement, |
| boolean fromInclusive, |
| E toElement, |
| boolean toInclusive) { |
| return new ConcurrentSkipListSet<E> |
| (m.subMap(fromElement, fromInclusive, |
| toElement, toInclusive)); |
| } |
| |
| /** |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException if {@code toElement} is null |
| * @throws IllegalArgumentException {@inheritDoc} |
| */ |
| public NavigableSet<E> headSet(E toElement, boolean inclusive) { |
| return new ConcurrentSkipListSet<E>(m.headMap(toElement, inclusive)); |
| } |
| |
| /** |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException if {@code fromElement} is null |
| * @throws IllegalArgumentException {@inheritDoc} |
| */ |
| public NavigableSet<E> tailSet(E fromElement, boolean inclusive) { |
| return new ConcurrentSkipListSet<E>(m.tailMap(fromElement, inclusive)); |
| } |
| |
| /** |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException if {@code fromElement} or |
| * {@code toElement} is null |
| * @throws IllegalArgumentException {@inheritDoc} |
| */ |
| public NavigableSet<E> subSet(E fromElement, E toElement) { |
| return subSet(fromElement, true, toElement, false); |
| } |
| |
| /** |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException if {@code toElement} is null |
| * @throws IllegalArgumentException {@inheritDoc} |
| */ |
| public NavigableSet<E> headSet(E toElement) { |
| return headSet(toElement, false); |
| } |
| |
| /** |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException if {@code fromElement} is null |
| * @throws IllegalArgumentException {@inheritDoc} |
| */ |
| public NavigableSet<E> tailSet(E fromElement) { |
| return tailSet(fromElement, true); |
| } |
| |
| /** |
| * Returns a reverse order view of the elements contained in this set. |
| * The descending set is backed by this set, so changes to the set are |
| * reflected in the descending set, and vice-versa. |
| * |
| * <p>The returned set has an ordering equivalent to |
| * <tt>{@link Collections#reverseOrder(Comparator) Collections.reverseOrder}(comparator())</tt>. |
| * The expression {@code s.descendingSet().descendingSet()} returns a |
| * view of {@code s} essentially equivalent to {@code s}. |
| * |
| * @return a reverse order view of this set |
| */ |
| public NavigableSet<E> descendingSet() { |
| return new ConcurrentSkipListSet(m.descendingMap()); |
| } |
| |
| // Support for resetting map in clone |
| private static final Unsafe unsafe = Unsafe.getUnsafe(); |
| private static final long mapOffset; |
| static { |
| try { |
| mapOffset = unsafe.objectFieldOffset |
| (ConcurrentSkipListSet.class.getDeclaredField("m")); |
| } catch (Exception ex) { throw new Error(ex); } |
| } |
| private void setMap(ConcurrentNavigableMap<E,Object> map) { |
| unsafe.putObjectVolatile(this, mapOffset, map); |
| } |
| |
| } |
