001 /*
002 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
003 *
004 * This code is free software; you can redistribute it and/or modify it
005 * under the terms of the GNU General Public License version 2 only, as
006 * published by the Free Software Foundation. Sun designates this
007 * particular file as subject to the "Classpath" exception as provided
008 * by Sun in the LICENSE file that accompanied this code.
009 *
010 * This code is distributed in the hope that it will be useful, but WITHOUT
011 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
012 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
013 * version 2 for more details (a copy is included in the LICENSE file that
014 * accompanied this code).
015 *
016 * You should have received a copy of the GNU General Public License version
017 * 2 along with this work; if not, write to the Free Software Foundation,
018 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
019 *
020 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
021 * CA 95054 USA or visit www.sun.com if you need additional information or
022 * have any questions.
023 */
024
025 /*
026 * This file is available under and governed by the GNU General Public
027 * License version 2 only, as published by the Free Software Foundation.
028 * However, the following notice accompanied the original version of this
029 * file:
030 *
031 * Written by Doug Lea with assistance from members of JCP JSR-166
032 * Expert Group and released to the public domain, as explained at
033 * http://creativecommons.org/licenses/publicdomain
034 */
035
036 package java.util.concurrent;
037
038 import java.util.*;
039 import sun.misc.Unsafe;
040
041 /**
042 * A scalable concurrent {@link NavigableSet} implementation based on
043 * a {@link ConcurrentSkipListMap}. The elements of the set are kept
044 * sorted according to their {@linkplain Comparable natural ordering},
045 * or by a {@link Comparator} provided at set creation time, depending
046 * on which constructor is used.
047 *
048 * <p>This implementation provides expected average <i>log(n)</i> time
049 * cost for the <tt>contains</tt>, <tt>add</tt>, and <tt>remove</tt>
050 * operations and their variants. Insertion, removal, and access
051 * operations safely execute concurrently by multiple threads.
052 * Iterators are <i>weakly consistent</i>, returning elements
053 * reflecting the state of the set at some point at or since the
054 * creation of the iterator. They do <em>not</em> throw {@link
055 * ConcurrentModificationException}, and may proceed concurrently with
056 * other operations. Ascending ordered views and their iterators are
057 * faster than descending ones.
058 *
059 * <p>Beware that, unlike in most collections, the <tt>size</tt>
060 * method is <em>not</em> a constant-time operation. Because of the
061 * asynchronous nature of these sets, determining the current number
062 * of elements requires a traversal of the elements. Additionally, the
063 * bulk operations <tt>addAll</tt>, <tt>removeAll</tt>,
064 * <tt>retainAll</tt>, and <tt>containsAll</tt> are <em>not</em>
065 * guaranteed to be performed atomically. For example, an iterator
066 * operating concurrently with an <tt>addAll</tt> operation might view
067 * only some of the added elements.
068 *
069 * <p>This class and its iterators implement all of the
070 * <em>optional</em> methods of the {@link Set} and {@link Iterator}
071 * interfaces. Like most other concurrent collection implementations,
072 * this class does not permit the use of <tt>null</tt> elements,
073 * because <tt>null</tt> arguments and return values cannot be reliably
074 * distinguished from the absence of elements.
075 *
076 * <p>This class is a member of the
077 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
078 * Java Collections Framework</a>.
079 *
080 * @author Doug Lea
081 * @param <E> the type of elements maintained by this set
082 * @since 1.6
083 */
084 public class ConcurrentSkipListSet<E> extends AbstractSet<E> implements
085 NavigableSet<E>, Cloneable, java.io.Serializable {
086
087 private static final long serialVersionUID = -2479143111061671589L;
088
089 /**
090 * The underlying map. Uses Boolean.TRUE as value for each
091 * element. This field is declared final for the sake of thread
092 * safety, which entails some ugliness in clone()
093 */
094 private final ConcurrentNavigableMap<E, Object> m;
095
096 /**
097 * Constructs a new, empty set that orders its elements according to
098 * their {@linkplain Comparable natural ordering}.
099 */
100 public ConcurrentSkipListSet() {
101 m = new ConcurrentSkipListMap<E, Object>();
102 }
103
104 /**
105 * Constructs a new, empty set that orders its elements according to
106 * the specified comparator.
107 *
108 * @param comparator the comparator that will be used to order this set.
109 * If <tt>null</tt>, the {@linkplain Comparable natural
110 * ordering} of the elements will be used.
111 */
112 public ConcurrentSkipListSet(Comparator<? super E> comparator) {
113 m = new ConcurrentSkipListMap<E, Object>(comparator);
114 }
115
116 /**
117 * Constructs a new set containing the elements in the specified
118 * collection, that orders its elements according to their
119 * {@linkplain Comparable natural ordering}.
120 *
121 * @param c The elements that will comprise the new set
122 * @throws ClassCastException if the elements in <tt>c</tt> are
123 * not {@link Comparable}, or are not mutually comparable
124 * @throws NullPointerException if the specified collection or any
125 * of its elements are null
126 */
127 public ConcurrentSkipListSet(Collection<? extends E> c) {
128 m = new ConcurrentSkipListMap<E, Object>();
129 addAll(c);
130 }
131
132 /**
133 * Constructs a new set containing the same elements and using the
134 * same ordering as the specified sorted set.
135 *
136 * @param s sorted set whose elements will comprise the new set
137 * @throws NullPointerException if the specified sorted set or any
138 * of its elements are null
139 */
140 public ConcurrentSkipListSet(SortedSet<E> s) {
141 m = new ConcurrentSkipListMap<E, Object>(s.comparator());
142 addAll(s);
143 }
144
145 /**
146 * For use by submaps
147 */
148 ConcurrentSkipListSet(ConcurrentNavigableMap<E, Object> m) {
149 this .m = m;
150 }
151
152 /**
153 * Returns a shallow copy of this <tt>ConcurrentSkipListSet</tt>
154 * instance. (The elements themselves are not cloned.)
155 *
156 * @return a shallow copy of this set
157 */
158 public ConcurrentSkipListSet<E> clone() {
159 ConcurrentSkipListSet<E> clone = null;
160 try {
161 clone = (ConcurrentSkipListSet<E>) super .clone();
162 clone.setMap(new ConcurrentSkipListMap(m));
163 } catch (CloneNotSupportedException e) {
164 throw new InternalError();
165 }
166
167 return clone;
168 }
169
170 /* ---------------- Set operations -------------- */
171
172 /**
173 * Returns the number of elements in this set. If this set
174 * contains more than <tt>Integer.MAX_VALUE</tt> elements, it
175 * returns <tt>Integer.MAX_VALUE</tt>.
176 *
177 * <p>Beware that, unlike in most collections, this method is
178 * <em>NOT</em> a constant-time operation. Because of the
179 * asynchronous nature of these sets, determining the current
180 * number of elements requires traversing them all to count them.
181 * Additionally, it is possible for the size to change during
182 * execution of this method, in which case the returned result
183 * will be inaccurate. Thus, this method is typically not very
184 * useful in concurrent applications.
185 *
186 * @return the number of elements in this set
187 */
188 public int size() {
189 return m.size();
190 }
191
192 /**
193 * Returns <tt>true</tt> if this set contains no elements.
194 * @return <tt>true</tt> if this set contains no elements
195 */
196 public boolean isEmpty() {
197 return m.isEmpty();
198 }
199
200 /**
201 * Returns <tt>true</tt> if this set contains the specified element.
202 * More formally, returns <tt>true</tt> if and only if this set
203 * contains an element <tt>e</tt> such that <tt>o.equals(e)</tt>.
204 *
205 * @param o object to be checked for containment in this set
206 * @return <tt>true</tt> if this set contains the specified element
207 * @throws ClassCastException if the specified element cannot be
208 * compared with the elements currently in this set
209 * @throws NullPointerException if the specified element is null
210 */
211 public boolean contains(Object o) {
212 return m.containsKey(o);
213 }
214
215 /**
216 * Adds the specified element to this set if it is not already present.
217 * More formally, adds the specified element <tt>e</tt> to this set if
218 * the set contains no element <tt>e2</tt> such that <tt>e.equals(e2)</tt>.
219 * If this set already contains the element, the call leaves the set
220 * unchanged and returns <tt>false</tt>.
221 *
222 * @param e element to be added to this set
223 * @return <tt>true</tt> if this set did not already contain the
224 * specified element
225 * @throws ClassCastException if <tt>e</tt> cannot be compared
226 * with the elements currently in this set
227 * @throws NullPointerException if the specified element is null
228 */
229 public boolean add(E e) {
230 return m.putIfAbsent(e, Boolean.TRUE) == null;
231 }
232
233 /**
234 * Removes the specified element from this set if it is present.
235 * More formally, removes an element <tt>e</tt> such that
236 * <tt>o.equals(e)</tt>, if this set contains such an element.
237 * Returns <tt>true</tt> if this set contained the element (or
238 * equivalently, if this set changed as a result of the call).
239 * (This set will not contain the element once the call returns.)
240 *
241 * @param o object to be removed from this set, if present
242 * @return <tt>true</tt> if this set contained the specified element
243 * @throws ClassCastException if <tt>o</tt> cannot be compared
244 * with the elements currently in this set
245 * @throws NullPointerException if the specified element is null
246 */
247 public boolean remove(Object o) {
248 return m.remove(o, Boolean.TRUE);
249 }
250
251 /**
252 * Removes all of the elements from this set.
253 */
254 public void clear() {
255 m.clear();
256 }
257
258 /**
259 * Returns an iterator over the elements in this set in ascending order.
260 *
261 * @return an iterator over the elements in this set in ascending order
262 */
263 public Iterator<E> iterator() {
264 return m.navigableKeySet().iterator();
265 }
266
267 /**
268 * Returns an iterator over the elements in this set in descending order.
269 *
270 * @return an iterator over the elements in this set in descending order
271 */
272 public Iterator<E> descendingIterator() {
273 return m.descendingKeySet().iterator();
274 }
275
276 /* ---------------- AbstractSet Overrides -------------- */
277
278 /**
279 * Compares the specified object with this set for equality. Returns
280 * <tt>true</tt> if the specified object is also a set, the two sets
281 * have the same size, and every member of the specified set is
282 * contained in this set (or equivalently, every member of this set is
283 * contained in the specified set). This definition ensures that the
284 * equals method works properly across different implementations of the
285 * set interface.
286 *
287 * @param o the object to be compared for equality with this set
288 * @return <tt>true</tt> if the specified object is equal to this set
289 */
290 public boolean equals(Object o) {
291 // Override AbstractSet version to avoid calling size()
292 if (o == this )
293 return true;
294 if (!(o instanceof Set))
295 return false;
296 Collection<?> c = (Collection<?>) o;
297 try {
298 return containsAll(c) && c.containsAll(this );
299 } catch (ClassCastException unused) {
300 return false;
301 } catch (NullPointerException unused) {
302 return false;
303 }
304 }
305
306 /**
307 * Removes from this set all of its elements that are contained in
308 * the specified collection. If the specified collection is also
309 * a set, this operation effectively modifies this set so that its
310 * value is the <i>asymmetric set difference</i> of the two sets.
311 *
312 * @param c collection containing elements to be removed from this set
313 * @return <tt>true</tt> if this set changed as a result of the call
314 * @throws ClassCastException if the types of one or more elements in this
315 * set are incompatible with the specified collection
316 * @throws NullPointerException if the specified collection or any
317 * of its elements are null
318 */
319 public boolean removeAll(Collection<?> c) {
320 // Override AbstractSet version to avoid unnecessary call to size()
321 boolean modified = false;
322 for (Iterator<?> i = c.iterator(); i.hasNext();)
323 if (remove(i.next()))
324 modified = true;
325 return modified;
326 }
327
328 /* ---------------- Relational operations -------------- */
329
330 /**
331 * @throws ClassCastException {@inheritDoc}
332 * @throws NullPointerException if the specified element is null
333 */
334 public E lower(E e) {
335 return m.lowerKey(e);
336 }
337
338 /**
339 * @throws ClassCastException {@inheritDoc}
340 * @throws NullPointerException if the specified element is null
341 */
342 public E floor(E e) {
343 return m.floorKey(e);
344 }
345
346 /**
347 * @throws ClassCastException {@inheritDoc}
348 * @throws NullPointerException if the specified element is null
349 */
350 public E ceiling(E e) {
351 return m.ceilingKey(e);
352 }
353
354 /**
355 * @throws ClassCastException {@inheritDoc}
356 * @throws NullPointerException if the specified element is null
357 */
358 public E higher(E e) {
359 return m.higherKey(e);
360 }
361
362 public E pollFirst() {
363 Map.Entry<E, Object> e = m.pollFirstEntry();
364 return e == null ? null : e.getKey();
365 }
366
367 public E pollLast() {
368 Map.Entry<E, Object> e = m.pollLastEntry();
369 return e == null ? null : e.getKey();
370 }
371
372 /* ---------------- SortedSet operations -------------- */
373
374 public Comparator<? super E> comparator() {
375 return m.comparator();
376 }
377
378 /**
379 * @throws NoSuchElementException {@inheritDoc}
380 */
381 public E first() {
382 return m.firstKey();
383 }
384
385 /**
386 * @throws NoSuchElementException {@inheritDoc}
387 */
388 public E last() {
389 return m.lastKey();
390 }
391
392 /**
393 * @throws ClassCastException {@inheritDoc}
394 * @throws NullPointerException if {@code fromElement} or
395 * {@code toElement} is null
396 * @throws IllegalArgumentException {@inheritDoc}
397 */
398 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
399 E toElement, boolean toInclusive) {
400 return new ConcurrentSkipListSet<E>(m.subMap(fromElement,
401 fromInclusive, toElement, toInclusive));
402 }
403
404 /**
405 * @throws ClassCastException {@inheritDoc}
406 * @throws NullPointerException if {@code toElement} is null
407 * @throws IllegalArgumentException {@inheritDoc}
408 */
409 public NavigableSet<E> headSet(E toElement, boolean inclusive) {
410 return new ConcurrentSkipListSet<E>(m.headMap(toElement,
411 inclusive));
412 }
413
414 /**
415 * @throws ClassCastException {@inheritDoc}
416 * @throws NullPointerException if {@code fromElement} is null
417 * @throws IllegalArgumentException {@inheritDoc}
418 */
419 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
420 return new ConcurrentSkipListSet<E>(m.tailMap(fromElement,
421 inclusive));
422 }
423
424 /**
425 * @throws ClassCastException {@inheritDoc}
426 * @throws NullPointerException if {@code fromElement} or
427 * {@code toElement} is null
428 * @throws IllegalArgumentException {@inheritDoc}
429 */
430 public NavigableSet<E> subSet(E fromElement, E toElement) {
431 return subSet(fromElement, true, toElement, false);
432 }
433
434 /**
435 * @throws ClassCastException {@inheritDoc}
436 * @throws NullPointerException if {@code toElement} is null
437 * @throws IllegalArgumentException {@inheritDoc}
438 */
439 public NavigableSet<E> headSet(E toElement) {
440 return headSet(toElement, false);
441 }
442
443 /**
444 * @throws ClassCastException {@inheritDoc}
445 * @throws NullPointerException if {@code fromElement} is null
446 * @throws IllegalArgumentException {@inheritDoc}
447 */
448 public NavigableSet<E> tailSet(E fromElement) {
449 return tailSet(fromElement, true);
450 }
451
452 /**
453 * Returns a reverse order view of the elements contained in this set.
454 * The descending set is backed by this set, so changes to the set are
455 * reflected in the descending set, and vice-versa.
456 *
457 * <p>The returned set has an ordering equivalent to
458 * <tt>{@link Collections#reverseOrder(Comparator) Collections.reverseOrder}(comparator())</tt>.
459 * The expression {@code s.descendingSet().descendingSet()} returns a
460 * view of {@code s} essentially equivalent to {@code s}.
461 *
462 * @return a reverse order view of this set
463 */
464 public NavigableSet<E> descendingSet() {
465 return new ConcurrentSkipListSet(m.descendingMap());
466 }
467
468 // Support for resetting map in clone
469 private static final Unsafe unsafe = Unsafe.getUnsafe();
470 private static final long mapOffset;
471 static {
472 try {
473 mapOffset = unsafe
474 .objectFieldOffset(ConcurrentSkipListSet.class
475 .getDeclaredField("m"));
476 } catch (Exception ex) {
477 throw new Error(ex);
478 }
479 }
480
481 private void setMap(ConcurrentNavigableMap<E, Object> map) {
482 unsafe.putObjectVolatile(this, mapOffset, map);
483 }
484
485 }
|