1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
3 *
4 * This code is free software; you can redistribute it and/or modify it
5 * under the terms of the GNU General Public License version 2 only, as
6 * published by the Free Software Foundation. Oracle designates this
7 * particular file as subject to the "Classpath" exception as provided
8 * by Oracle in the LICENSE file that accompanied this code.
9 *
10 * This code is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 * version 2 for more details (a copy is included in the LICENSE file that
14 * accompanied this code).
15 *
16 * You should have received a copy of the GNU General Public License version
17 * 2 along with this work; if not, write to the Free Software Foundation,
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
38 import java.lang.reflect.Field;
39 import java.util.AbstractSet;
40 import java.util.Collection;
41 import java.util.Collections;
42 import java.util.Comparator;
43 import java.util.Iterator;
44 import java.util.Map;
45 import java.util.NavigableSet;
46 import java.util.Set;
47 import java.util.SortedSet;
48 import java.util.Spliterator;
49
50 /**
51 * A scalable concurrent {@link NavigableSet} implementation based on
52 * a {@link ConcurrentSkipListMap}. The elements of the set are kept
53 * sorted according to their {@linkplain Comparable natural ordering},
54 * or by a {@link Comparator} provided at set creation time, depending
55 * on which constructor is used.
56 *
57 * <p>This implementation provides expected average <i>log(n)</i> time
58 * cost for the {@code contains}, {@code add}, and {@code remove}
59 * operations and their variants. Insertion, removal, and access
60 * operations safely execute concurrently by multiple threads.
61 *
62 * <p>Iterators and spliterators are
63 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
64 *
65 * <p>Ascending ordered views and their iterators are faster than
66 * descending ones.
67 *
68 * <p>Beware that, unlike in most collections, the {@code size}
69 * method is <em>not</em> a constant-time operation. Because of the
70 * asynchronous nature of these sets, determining the current number
71 * of elements requires a traversal of the elements, and so may report
72 * inaccurate results if this collection is modified during traversal.
73 *
74 * <p>Bulk operations that add, remove, or examine multiple elements,
75 * such as {@link #addAll}, {@link #removeIf} or {@link #forEach},
76 * are <em>not</em> guaranteed to be performed atomically.
77 * For example, a {@code forEach} traversal concurrent with an {@code
78 * addAll} operation might observe only some of the added elements.
79 *
80 * <p>This class and its iterators implement all of the
81 * <em>optional</em> methods of the {@link Set} and {@link Iterator}
82 * interfaces. Like most other concurrent collection implementations,
83 * this class does not permit the use of {@code null} elements,
84 * because {@code null} arguments and return values cannot be reliably
85 * distinguished from the absence of elements.
86 *
87 * <p>This class is a member of the
88 * <a href="{@docRoot}/java/util/package-summary.html#CollectionsFramework">
89 * Java Collections Framework</a>.
90 *
91 * @author Doug Lea
92 * @param <E> the type of elements maintained by this set
93 * @since 1.6
94 */
95 public class ConcurrentSkipListSet<E>
96 extends AbstractSet<E>
97 implements NavigableSet<E>, Cloneable, java.io.Serializable {
98
99 private static final long serialVersionUID = -2479143111061671589L;
100
101 /**
102 * The underlying map. Uses Boolean.TRUE as value for each
103 * element. This field is declared final for the sake of thread
104 * safety, which entails some ugliness in clone().
105 */
106 private final ConcurrentNavigableMap<E,Object> m;
107
108 /**
109 * Constructs a new, empty set that orders its elements according to
110 * their {@linkplain Comparable natural ordering}.
111 */
112 public ConcurrentSkipListSet() {
113 m = new ConcurrentSkipListMap<E,Object>();
114 }
115
116 /**
117 * Constructs a new, empty set that orders its elements according to
118 * the specified comparator.
119 *
120 * @param comparator the comparator that will be used to order this set.
121 * If {@code null}, the {@linkplain Comparable natural
122 * ordering} of the elements will be used.
123 */
124 public ConcurrentSkipListSet(Comparator<? super E> comparator) {
125 m = new ConcurrentSkipListMap<E,Object>(comparator);
126 }
127
128 /**
129 * Constructs a new set containing the elements in the specified
130 * collection, that orders its elements according to their
131 * {@linkplain Comparable natural ordering}.
132 *
133 * @param c The elements that will comprise the new set
134 * @throws ClassCastException if the elements in {@code c} are
135 * not {@link Comparable}, or are not mutually comparable
136 * @throws NullPointerException if the specified collection or any
137 * of its elements are null
138 */
139 public ConcurrentSkipListSet(Collection<? extends E> c) {
140 m = new ConcurrentSkipListMap<E,Object>();
141 addAll(c);
142 }
143
144 /**
145 * Constructs a new set containing the same elements and using the
146 * same ordering as the specified sorted set.
147 *
148 * @param s sorted set whose elements will comprise the new set
149 * @throws NullPointerException if the specified sorted set or any
150 * of its elements are null
151 */
152 public ConcurrentSkipListSet(SortedSet<E> s) {
153 m = new ConcurrentSkipListMap<E,Object>(s.comparator());
154 addAll(s);
155 }
156
157 /**
158 * For use by submaps
159 */
160 ConcurrentSkipListSet(ConcurrentNavigableMap<E,Object> m) {
161 this.m = m;
162 }
163
164 /**
165 * Returns a shallow copy of this {@code ConcurrentSkipListSet}
166 * instance. (The elements themselves are not cloned.)
167 *
168 * @return a shallow copy of this set
169 */
170 public ConcurrentSkipListSet<E> clone() {
171 try {
172 @SuppressWarnings("unchecked")
173 ConcurrentSkipListSet<E> clone =
174 (ConcurrentSkipListSet<E>) super.clone();
175 clone.setMap(new ConcurrentSkipListMap<E,Object>(m));
176 return clone;
177 } catch (CloneNotSupportedException e) {
178 throw new InternalError();
179 }
180 }
181
182 /* ---------------- Set operations -------------- */
183
184 /**
185 * Returns the number of elements in this set. If this set
186 * contains more than {@code Integer.MAX_VALUE} elements, it
187 * returns {@code Integer.MAX_VALUE}.
188 *
189 * <p>Beware that, unlike in most collections, this method is
190 * <em>NOT</em> a constant-time operation. Because of the
191 * asynchronous nature of these sets, determining the current
192 * number of elements requires traversing them all to count them.
193 * Additionally, it is possible for the size to change during
194 * execution of this method, in which case the returned result
195 * will be inaccurate. Thus, this method is typically not very
196 * useful in concurrent applications.
197 *
198 * @return the number of elements in this set
199 */
200 public int size() {
201 return m.size();
202 }
203
204 /**
205 * Returns {@code true} if this set contains no elements.
206 * @return {@code true} if this set contains no elements
207 */
208 public boolean isEmpty() {
209 return m.isEmpty();
210 }
211
212 /**
213 * Returns {@code true} if this set contains the specified element.
214 * More formally, returns {@code true} if and only if this set
215 * contains an element {@code e} such that {@code o.equals(e)}.
216 *
217 * @param o object to be checked for containment in this set
218 * @return {@code true} if this set contains the specified element
219 * @throws ClassCastException if the specified element cannot be
220 * compared with the elements currently in this set
221 * @throws NullPointerException if the specified element is null
222 */
223 public boolean contains(Object o) {
224 return m.containsKey(o);
225 }
226
227 /**
228 * Adds the specified element to this set if it is not already present.
229 * More formally, adds the specified element {@code e} to this set if
230 * the set contains no element {@code e2} such that {@code e.equals(e2)}.
231 * If this set already contains the element, the call leaves the set
232 * unchanged and returns {@code false}.
233 *
234 * @param e element to be added to this set
235 * @return {@code true} if this set did not already contain the
236 * specified element
237 * @throws ClassCastException if {@code e} cannot be compared
238 * with the elements currently in this set
239 * @throws NullPointerException if the specified element is null
240 */
241 public boolean add(E e) {
242 return m.putIfAbsent(e, Boolean.TRUE) == null;
243 }
244
245 /**
246 * Removes the specified element from this set if it is present.
247 * More formally, removes an element {@code e} such that
248 * {@code o.equals(e)}, if this set contains such an element.
249 * Returns {@code true} if this set contained the element (or
250 * equivalently, if this set changed as a result of the call).
251 * (This set will not contain the element once the call returns.)
252 *
253 * @param o object to be removed from this set, if present
254 * @return {@code true} if this set contained the specified element
255 * @throws ClassCastException if {@code o} cannot be compared
256 * with the elements currently in this set
257 * @throws NullPointerException if the specified element is null
258 */
259 public boolean remove(Object o) {
260 return m.remove(o, Boolean.TRUE);
261 }
262
263 /**
264 * Removes all of the elements from this set.
265 */
266 public void clear() {
267 m.clear();
268 }
269
270 /**
271 * Returns an iterator over the elements in this set in ascending order.
272 *
273 * @return an iterator over the elements in this set in ascending order
274 */
275 public Iterator<E> iterator() {
276 return m.navigableKeySet().iterator();
277 }
278
279 /**
280 * Returns an iterator over the elements in this set in descending order.
281 *
282 * @return an iterator over the elements in this set in descending order
283 */
284 public Iterator<E> descendingIterator() {
285 return m.descendingKeySet().iterator();
286 }
287
288
289 /* ---------------- AbstractSet Overrides -------------- */
290
291 /**
292 * Compares the specified object with this set for equality. Returns
293 * {@code true} if the specified object is also a set, the two sets
294 * have the same size, and every member of the specified set is
295 * contained in this set (or equivalently, every member of this set is
296 * contained in the specified set). This definition ensures that the
297 * equals method works properly across different implementations of the
298 * set interface.
299 *
300 * @param o the object to be compared for equality with this set
301 * @return {@code true} if the specified object is equal to this set
302 */
303 public boolean equals(Object o) {
304 // Override AbstractSet version to avoid calling size()
305 if (o == this)
306 return true;
307 if (!(o instanceof Set))
308 return false;
309 Collection<?> c = (Collection<?>) o;
310 try {
311 return containsAll(c) && c.containsAll(this);
312 } catch (ClassCastException | NullPointerException unused) {
313 return false;
314 }
315 }
316
317 /**
318 * Removes from this set all of its elements that are contained in
319 * the specified collection. If the specified collection is also
320 * a set, this operation effectively modifies this set so that its
321 * value is the <i>asymmetric set difference</i> of the two sets.
322 *
323 * @param c collection containing elements to be removed from this set
324 * @return {@code true} if this set changed as a result of the call
325 * @throws ClassCastException if the class of an element of this set
326 * is incompatible with the specified collection
327 * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
328 * @throws NullPointerException if the specified collection or any
329 * of its elements are null
330 */
331 public boolean removeAll(Collection<?> c) {
332 // Override AbstractSet version to avoid unnecessary call to size()
333 boolean modified = false;
334 for (Object e : c)
335 if (remove(e))
336 modified = true;
337 return modified;
338 }
339
340 /* ---------------- Relational operations -------------- */
341
342 /**
343 * @throws ClassCastException {@inheritDoc}
344 * @throws NullPointerException if the specified element is null
345 */
346 public E lower(E e) {
347 return m.lowerKey(e);
348 }
349
350 /**
351 * @throws ClassCastException {@inheritDoc}
352 * @throws NullPointerException if the specified element is null
353 */
354 public E floor(E e) {
355 return m.floorKey(e);
356 }
357
358 /**
359 * @throws ClassCastException {@inheritDoc}
360 * @throws NullPointerException if the specified element is null
361 */
362 public E ceiling(E e) {
363 return m.ceilingKey(e);
364 }
365
366 /**
367 * @throws ClassCastException {@inheritDoc}
368 * @throws NullPointerException if the specified element is null
369 */
370 public E higher(E e) {
371 return m.higherKey(e);
372 }
373
374 public E pollFirst() {
375 Map.Entry<E,Object> e = m.pollFirstEntry();
376 return (e == null) ? null : e.getKey();
377 }
378
379 public E pollLast() {
380 Map.Entry<E,Object> e = m.pollLastEntry();
381 return (e == null) ? null : e.getKey();
382 }
383
384
385 /* ---------------- SortedSet operations -------------- */
386
387 public Comparator<? super E> comparator() {
388 return m.comparator();
389 }
390
391 /**
392 * @throws java.util.NoSuchElementException {@inheritDoc}
393 */
394 public E first() {
395 return m.firstKey();
396 }
397
398 /**
399 * @throws java.util.NoSuchElementException {@inheritDoc}
400 */
401 public E last() {
402 return m.lastKey();
403 }
404
405 /**
406 * @throws ClassCastException {@inheritDoc}
407 * @throws NullPointerException if {@code fromElement} or
408 * {@code toElement} is null
409 * @throws IllegalArgumentException {@inheritDoc}
410 */
411 public NavigableSet<E> subSet(E fromElement,
412 boolean fromInclusive,
413 E toElement,
414 boolean toInclusive) {
415 return new ConcurrentSkipListSet<E>
416 (m.subMap(fromElement, fromInclusive,
417 toElement, toInclusive));
418 }
419
420 /**
421 * @throws ClassCastException {@inheritDoc}
422 * @throws NullPointerException if {@code toElement} is null
423 * @throws IllegalArgumentException {@inheritDoc}
424 */
425 public NavigableSet<E> headSet(E toElement, boolean inclusive) {
426 return new ConcurrentSkipListSet<E>(m.headMap(toElement, inclusive));
427 }
428
429 /**
430 * @throws ClassCastException {@inheritDoc}
431 * @throws NullPointerException if {@code fromElement} is null
432 * @throws IllegalArgumentException {@inheritDoc}
433 */
434 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
435 return new ConcurrentSkipListSet<E>(m.tailMap(fromElement, inclusive));
436 }
437
438 /**
439 * @throws ClassCastException {@inheritDoc}
440 * @throws NullPointerException if {@code fromElement} or
441 * {@code toElement} is null
442 * @throws IllegalArgumentException {@inheritDoc}
443 */
444 public NavigableSet<E> subSet(E fromElement, E toElement) {
445 return subSet(fromElement, true, toElement, false);
446 }
447
448 /**
449 * @throws ClassCastException {@inheritDoc}
450 * @throws NullPointerException if {@code toElement} is null
451 * @throws IllegalArgumentException {@inheritDoc}
452 */
453 public NavigableSet<E> headSet(E toElement) {
454 return headSet(toElement, false);
455 }
456
457 /**
458 * @throws ClassCastException {@inheritDoc}
459 * @throws NullPointerException if {@code fromElement} is null
460 * @throws IllegalArgumentException {@inheritDoc}
461 */
462 public NavigableSet<E> tailSet(E fromElement) {
463 return tailSet(fromElement, true);
464 }
465
466 /**
467 * Returns a reverse order view of the elements contained in this set.
468 * The descending set is backed by this set, so changes to the set are
469 * reflected in the descending set, and vice-versa.
470 *
471 * <p>The returned set has an ordering equivalent to
472 * {@link Collections#reverseOrder(Comparator) Collections.reverseOrder}{@code (comparator())}.
473 * The expression {@code s.descendingSet().descendingSet()} returns a
474 * view of {@code s} essentially equivalent to {@code s}.
475 *
476 * @return a reverse order view of this set
477 */
478 public NavigableSet<E> descendingSet() {
479 return new ConcurrentSkipListSet<E>(m.descendingMap());
480 }
481
482 /**
483 * Returns a {@link Spliterator} over the elements in this set.
484 *
485 * <p>The {@code Spliterator} reports {@link Spliterator#CONCURRENT},
486 * {@link Spliterator#NONNULL}, {@link Spliterator#DISTINCT},
487 * {@link Spliterator#SORTED} and {@link Spliterator#ORDERED}, with an
488 * encounter order that is ascending order. Overriding implementations
489 * should document the reporting of additional characteristic values.
490 *
491 * <p>The {@linkplain Spliterator#getComparator() spliterator's comparator}
492 * is {@code null} if the {@linkplain #comparator() set's comparator}
493 * is {@code null}.
494 * Otherwise, the spliterator's comparator is the same as or imposes the
495 * same total ordering as the set's comparator.
496 *
497 * @return a {@code Spliterator} over the elements in this set
498 * @since 1.8
499 */
500 public Spliterator<E> spliterator() {
501 return (m instanceof ConcurrentSkipListMap)
502 ? ((ConcurrentSkipListMap<E,?>)m).keySpliterator()
503 : ((ConcurrentSkipListMap.SubMap<E,?>)m).new SubMapKeyIterator();
504 }
505
506 /** Initializes map field; for use in clone. */
507 private void setMap(ConcurrentNavigableMap<E,Object> map) {
508 Field mapField = java.security.AccessController.doPrivileged(
509 (java.security.PrivilegedAction<Field>) () -> {
510 try {
511 Field f = ConcurrentSkipListSet.class
512 .getDeclaredField("m");
513 f.setAccessible(true);
514 return f;
515 } catch (ReflectiveOperationException e) {
516 throw new Error(e);
517 }});
518 try {
519 mapField.set(this, map);
520 } catch (IllegalAccessException e) {
521 throw new Error(e);
522 }
523 }
524 }