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
7 package java.util.concurrent;
9 import sun.misc.Unsafe;
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.
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.
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.
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.
46 * <p>This class is a member of the
47 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
48 * Java Collections Framework</a>.
51 * @param <E> the type of elements maintained by this set
54 public class ConcurrentSkipListSet<E>
55 extends AbstractSet<E>
56 implements NavigableSet<E>, Cloneable, java.io.Serializable {
58 private static final long serialVersionUID = -2479143111061671589L;
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()
65 private final ConcurrentNavigableMap<E,Object> m;
68 * Constructs a new, empty set that orders its elements according to
69 * their {@linkplain Comparable natural ordering}.
71 public ConcurrentSkipListSet() {
72 m = new ConcurrentSkipListMap<E,Object>();
76 * Constructs a new, empty set that orders its elements according to
77 * the specified comparator.
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.
83 public ConcurrentSkipListSet(Comparator<? super E> comparator) {
84 m = new ConcurrentSkipListMap<E,Object>(comparator);
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}.
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
98 public ConcurrentSkipListSet(Collection<? extends E> c) {
99 m = new ConcurrentSkipListMap<E,Object>();
104 * Constructs a new set containing the same elements and using the
105 * same ordering as the specified sorted set.
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
111 public ConcurrentSkipListSet(SortedSet<E> s) {
112 m = new ConcurrentSkipListMap<E,Object>(s.comparator());
119 ConcurrentSkipListSet(ConcurrentNavigableMap<E,Object> m) {
124 * Returns a shallow copy of this <tt>ConcurrentSkipListSet</tt>
125 * instance. (The elements themselves are not cloned.)
127 * @return a shallow copy of this set
129 public ConcurrentSkipListSet<E> clone() {
130 ConcurrentSkipListSet<E> clone = null;
132 clone = (ConcurrentSkipListSet<E>) super.clone();
133 clone.setMap(new ConcurrentSkipListMap(m));
134 } catch (CloneNotSupportedException e) {
135 throw new InternalError();
141 /* ---------------- Set operations -------------- */
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>.
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.
157 * @return the number of elements in this set
164 * Returns <tt>true</tt> if this set contains no elements.
165 * @return <tt>true</tt> if this set contains no elements
167 public boolean isEmpty() {
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>.
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
182 public boolean contains(Object o) {
183 return m.containsKey(o);
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>.
193 * @param e element to be added to this set
194 * @return <tt>true</tt> if this set did not already contain the
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
200 public boolean add(E e) {
201 return m.putIfAbsent(e, Boolean.TRUE) == null;
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.)
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
218 public boolean remove(Object o) {
219 return m.remove(o, Boolean.TRUE);
223 * Removes all of the elements from this set.
225 public void clear() {
230 * Returns an iterator over the elements in this set in ascending order.
232 * @return an iterator over the elements in this set in ascending order
234 public Iterator<E> iterator() {
235 return m.navigableKeySet().iterator();
239 * Returns an iterator over the elements in this set in descending order.
241 * @return an iterator over the elements in this set in descending order
243 public Iterator<E> descendingIterator() {
244 return m.descendingKeySet().iterator();
248 /* ---------------- AbstractSet Overrides -------------- */
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
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
262 public boolean equals(Object o) {
263 // Override AbstractSet version to avoid calling size()
266 if (!(o instanceof Set))
268 Collection<?> c = (Collection<?>) o;
270 return containsAll(c) && c.containsAll(this);
271 } catch (ClassCastException unused) {
273 } catch (NullPointerException unused) {
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.
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
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()))
300 /* ---------------- Relational operations -------------- */
303 * @throws ClassCastException {@inheritDoc}
304 * @throws NullPointerException if the specified element is null
306 public E lower(E e) {
307 return m.lowerKey(e);
311 * @throws ClassCastException {@inheritDoc}
312 * @throws NullPointerException if the specified element is null
314 public E floor(E e) {
315 return m.floorKey(e);
319 * @throws ClassCastException {@inheritDoc}
320 * @throws NullPointerException if the specified element is null
322 public E ceiling(E e) {
323 return m.ceilingKey(e);
327 * @throws ClassCastException {@inheritDoc}
328 * @throws NullPointerException if the specified element is null
330 public E higher(E e) {
331 return m.higherKey(e);
334 public E pollFirst() {
335 Map.Entry<E,Object> e = m.pollFirstEntry();
336 return e == null? null : e.getKey();
339 public E pollLast() {
340 Map.Entry<E,Object> e = m.pollLastEntry();
341 return e == null? null : e.getKey();
345 /* ---------------- SortedSet operations -------------- */
348 public Comparator<? super E> comparator() {
349 return m.comparator();
353 * @throws NoSuchElementException {@inheritDoc}
360 * @throws NoSuchElementException {@inheritDoc}
367 * @throws ClassCastException {@inheritDoc}
368 * @throws NullPointerException if {@code fromElement} or
369 * {@code toElement} is null
370 * @throws IllegalArgumentException {@inheritDoc}
372 public NavigableSet<E> subSet(E fromElement,
373 boolean fromInclusive,
375 boolean toInclusive) {
376 return new ConcurrentSkipListSet<E>
377 (m.subMap(fromElement, fromInclusive,
378 toElement, toInclusive));
382 * @throws ClassCastException {@inheritDoc}
383 * @throws NullPointerException if {@code toElement} is null
384 * @throws IllegalArgumentException {@inheritDoc}
386 public NavigableSet<E> headSet(E toElement, boolean inclusive) {
387 return new ConcurrentSkipListSet<E>(m.headMap(toElement, inclusive));
391 * @throws ClassCastException {@inheritDoc}
392 * @throws NullPointerException if {@code fromElement} is null
393 * @throws IllegalArgumentException {@inheritDoc}
395 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
396 return new ConcurrentSkipListSet<E>(m.tailMap(fromElement, inclusive));
400 * @throws ClassCastException {@inheritDoc}
401 * @throws NullPointerException if {@code fromElement} or
402 * {@code toElement} is null
403 * @throws IllegalArgumentException {@inheritDoc}
405 public NavigableSet<E> subSet(E fromElement, E toElement) {
406 return subSet(fromElement, true, toElement, false);
410 * @throws ClassCastException {@inheritDoc}
411 * @throws NullPointerException if {@code toElement} is null
412 * @throws IllegalArgumentException {@inheritDoc}
414 public NavigableSet<E> headSet(E toElement) {
415 return headSet(toElement, false);
419 * @throws ClassCastException {@inheritDoc}
420 * @throws NullPointerException if {@code fromElement} is null
421 * @throws IllegalArgumentException {@inheritDoc}
423 public NavigableSet<E> tailSet(E fromElement) {
424 return tailSet(fromElement, true);
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.
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}.
437 * @return a reverse order view of this set
439 public NavigableSet<E> descendingSet() {
440 return new ConcurrentSkipListSet(m.descendingMap());
443 // Support for resetting map in clone
444 private static final Unsafe unsafe = Unsafe.getUnsafe();
445 private static final long mapOffset;
448 mapOffset = unsafe.objectFieldOffset
449 (ConcurrentSkipListSet.class.getDeclaredField("m"));
450 } catch (Exception ex) { throw new Error(ex); }
452 private void setMap(ConcurrentNavigableMap<E,Object> map) {
453 unsafe.putObjectVolatile(this, mapOffset, map);