1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/rt/emul/compact/src/main/java/java/util/concurrent/ConcurrentSkipListSet.java Sat Mar 19 10:46:31 2016 +0100
1.3 @@ -0,0 +1,491 @@
1.4 +/*
1.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.6 + *
1.7 + * This code is free software; you can redistribute it and/or modify it
1.8 + * under the terms of the GNU General Public License version 2 only, as
1.9 + * published by the Free Software Foundation. Oracle designates this
1.10 + * particular file as subject to the "Classpath" exception as provided
1.11 + * by Oracle in the LICENSE file that accompanied this code.
1.12 + *
1.13 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.14 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.15 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.16 + * version 2 for more details (a copy is included in the LICENSE file that
1.17 + * accompanied this code).
1.18 + *
1.19 + * You should have received a copy of the GNU General Public License version
1.20 + * 2 along with this work; if not, write to the Free Software Foundation,
1.21 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.22 + *
1.23 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.24 + * or visit www.oracle.com if you need additional information or have any
1.25 + * questions.
1.26 + */
1.27 +
1.28 +/*
1.29 + * This file is available under and governed by the GNU General Public
1.30 + * License version 2 only, as published by the Free Software Foundation.
1.31 + * However, the following notice accompanied the original version of this
1.32 + * file:
1.33 + *
1.34 + * Written by Doug Lea with assistance from members of JCP JSR-166
1.35 + * Expert Group and released to the public domain, as explained at
1.36 + * http://creativecommons.org/publicdomain/zero/1.0/
1.37 + */
1.38 +
1.39 +package java.util.concurrent;
1.40 +import java.util.*;
1.41 +import sun.misc.Unsafe;
1.42 +
1.43 +/**
1.44 + * A scalable concurrent {@link NavigableSet} implementation based on
1.45 + * a {@link ConcurrentSkipListMap}. The elements of the set are kept
1.46 + * sorted according to their {@linkplain Comparable natural ordering},
1.47 + * or by a {@link Comparator} provided at set creation time, depending
1.48 + * on which constructor is used.
1.49 + *
1.50 + * <p>This implementation provides expected average <i>log(n)</i> time
1.51 + * cost for the <tt>contains</tt>, <tt>add</tt>, and <tt>remove</tt>
1.52 + * operations and their variants. Insertion, removal, and access
1.53 + * operations safely execute concurrently by multiple threads.
1.54 + * Iterators are <i>weakly consistent</i>, returning elements
1.55 + * reflecting the state of the set at some point at or since the
1.56 + * creation of the iterator. They do <em>not</em> throw {@link
1.57 + * ConcurrentModificationException}, and may proceed concurrently with
1.58 + * other operations. Ascending ordered views and their iterators are
1.59 + * faster than descending ones.
1.60 + *
1.61 + * <p>Beware that, unlike in most collections, the <tt>size</tt>
1.62 + * method is <em>not</em> a constant-time operation. Because of the
1.63 + * asynchronous nature of these sets, determining the current number
1.64 + * of elements requires a traversal of the elements, and so may report
1.65 + * inaccurate results if this collection is modified during traversal.
1.66 + * Additionally, the bulk operations <tt>addAll</tt>,
1.67 + * <tt>removeAll</tt>, <tt>retainAll</tt>, <tt>containsAll</tt>,
1.68 + * <tt>equals</tt>, and <tt>toArray</tt> are <em>not</em> guaranteed
1.69 + * to be performed atomically. For example, an iterator operating
1.70 + * concurrently with an <tt>addAll</tt> operation might view only some
1.71 + * of the added elements.
1.72 + *
1.73 + * <p>This class and its iterators implement all of the
1.74 + * <em>optional</em> methods of the {@link Set} and {@link Iterator}
1.75 + * interfaces. Like most other concurrent collection implementations,
1.76 + * this class does not permit the use of <tt>null</tt> elements,
1.77 + * because <tt>null</tt> arguments and return values cannot be reliably
1.78 + * distinguished from the absence of elements.
1.79 + *
1.80 + * <p>This class is a member of the
1.81 + * <a href="{@docRoot}/../technotes/guides/collections/index.html">
1.82 + * Java Collections Framework</a>.
1.83 + *
1.84 + * @author Doug Lea
1.85 + * @param <E> the type of elements maintained by this set
1.86 + * @since 1.6
1.87 + */
1.88 +public class ConcurrentSkipListSet<E>
1.89 + extends AbstractSet<E>
1.90 + implements NavigableSet<E>, Cloneable, java.io.Serializable {
1.91 +
1.92 + private static final long serialVersionUID = -2479143111061671589L;
1.93 +
1.94 + /**
1.95 + * The underlying map. Uses Boolean.TRUE as value for each
1.96 + * element. This field is declared final for the sake of thread
1.97 + * safety, which entails some ugliness in clone()
1.98 + */
1.99 + private final ConcurrentNavigableMap<E,Object> m;
1.100 +
1.101 + /**
1.102 + * Constructs a new, empty set that orders its elements according to
1.103 + * their {@linkplain Comparable natural ordering}.
1.104 + */
1.105 + public ConcurrentSkipListSet() {
1.106 + m = new ConcurrentSkipListMap<E,Object>();
1.107 + }
1.108 +
1.109 + /**
1.110 + * Constructs a new, empty set that orders its elements according to
1.111 + * the specified comparator.
1.112 + *
1.113 + * @param comparator the comparator that will be used to order this set.
1.114 + * If <tt>null</tt>, the {@linkplain Comparable natural
1.115 + * ordering} of the elements will be used.
1.116 + */
1.117 + public ConcurrentSkipListSet(Comparator<? super E> comparator) {
1.118 + m = new ConcurrentSkipListMap<E,Object>(comparator);
1.119 + }
1.120 +
1.121 + /**
1.122 + * Constructs a new set containing the elements in the specified
1.123 + * collection, that orders its elements according to their
1.124 + * {@linkplain Comparable natural ordering}.
1.125 + *
1.126 + * @param c The elements that will comprise the new set
1.127 + * @throws ClassCastException if the elements in <tt>c</tt> are
1.128 + * not {@link Comparable}, or are not mutually comparable
1.129 + * @throws NullPointerException if the specified collection or any
1.130 + * of its elements are null
1.131 + */
1.132 + public ConcurrentSkipListSet(Collection<? extends E> c) {
1.133 + m = new ConcurrentSkipListMap<E,Object>();
1.134 + addAll(c);
1.135 + }
1.136 +
1.137 + /**
1.138 + * Constructs a new set containing the same elements and using the
1.139 + * same ordering as the specified sorted set.
1.140 + *
1.141 + * @param s sorted set whose elements will comprise the new set
1.142 + * @throws NullPointerException if the specified sorted set or any
1.143 + * of its elements are null
1.144 + */
1.145 + public ConcurrentSkipListSet(SortedSet<E> s) {
1.146 + m = new ConcurrentSkipListMap<E,Object>(s.comparator());
1.147 + addAll(s);
1.148 + }
1.149 +
1.150 + /**
1.151 + * For use by submaps
1.152 + */
1.153 + ConcurrentSkipListSet(ConcurrentNavigableMap<E,Object> m) {
1.154 + this.m = m;
1.155 + }
1.156 +
1.157 + /**
1.158 + * Returns a shallow copy of this <tt>ConcurrentSkipListSet</tt>
1.159 + * instance. (The elements themselves are not cloned.)
1.160 + *
1.161 + * @return a shallow copy of this set
1.162 + */
1.163 + public ConcurrentSkipListSet<E> clone() {
1.164 + ConcurrentSkipListSet<E> clone = null;
1.165 + try {
1.166 + clone = (ConcurrentSkipListSet<E>) super.clone();
1.167 + clone.setMap(new ConcurrentSkipListMap(m));
1.168 + } catch (CloneNotSupportedException e) {
1.169 + throw new InternalError();
1.170 + }
1.171 +
1.172 + return clone;
1.173 + }
1.174 +
1.175 + /* ---------------- Set operations -------------- */
1.176 +
1.177 + /**
1.178 + * Returns the number of elements in this set. If this set
1.179 + * contains more than <tt>Integer.MAX_VALUE</tt> elements, it
1.180 + * returns <tt>Integer.MAX_VALUE</tt>.
1.181 + *
1.182 + * <p>Beware that, unlike in most collections, this method is
1.183 + * <em>NOT</em> a constant-time operation. Because of the
1.184 + * asynchronous nature of these sets, determining the current
1.185 + * number of elements requires traversing them all to count them.
1.186 + * Additionally, it is possible for the size to change during
1.187 + * execution of this method, in which case the returned result
1.188 + * will be inaccurate. Thus, this method is typically not very
1.189 + * useful in concurrent applications.
1.190 + *
1.191 + * @return the number of elements in this set
1.192 + */
1.193 + public int size() {
1.194 + return m.size();
1.195 + }
1.196 +
1.197 + /**
1.198 + * Returns <tt>true</tt> if this set contains no elements.
1.199 + * @return <tt>true</tt> if this set contains no elements
1.200 + */
1.201 + public boolean isEmpty() {
1.202 + return m.isEmpty();
1.203 + }
1.204 +
1.205 + /**
1.206 + * Returns <tt>true</tt> if this set contains the specified element.
1.207 + * More formally, returns <tt>true</tt> if and only if this set
1.208 + * contains an element <tt>e</tt> such that <tt>o.equals(e)</tt>.
1.209 + *
1.210 + * @param o object to be checked for containment in this set
1.211 + * @return <tt>true</tt> if this set contains the specified element
1.212 + * @throws ClassCastException if the specified element cannot be
1.213 + * compared with the elements currently in this set
1.214 + * @throws NullPointerException if the specified element is null
1.215 + */
1.216 + public boolean contains(Object o) {
1.217 + return m.containsKey(o);
1.218 + }
1.219 +
1.220 + /**
1.221 + * Adds the specified element to this set if it is not already present.
1.222 + * More formally, adds the specified element <tt>e</tt> to this set if
1.223 + * the set contains no element <tt>e2</tt> such that <tt>e.equals(e2)</tt>.
1.224 + * If this set already contains the element, the call leaves the set
1.225 + * unchanged and returns <tt>false</tt>.
1.226 + *
1.227 + * @param e element to be added to this set
1.228 + * @return <tt>true</tt> if this set did not already contain the
1.229 + * specified element
1.230 + * @throws ClassCastException if <tt>e</tt> cannot be compared
1.231 + * with the elements currently in this set
1.232 + * @throws NullPointerException if the specified element is null
1.233 + */
1.234 + public boolean add(E e) {
1.235 + return m.putIfAbsent(e, Boolean.TRUE) == null;
1.236 + }
1.237 +
1.238 + /**
1.239 + * Removes the specified element from this set if it is present.
1.240 + * More formally, removes an element <tt>e</tt> such that
1.241 + * <tt>o.equals(e)</tt>, if this set contains such an element.
1.242 + * Returns <tt>true</tt> if this set contained the element (or
1.243 + * equivalently, if this set changed as a result of the call).
1.244 + * (This set will not contain the element once the call returns.)
1.245 + *
1.246 + * @param o object to be removed from this set, if present
1.247 + * @return <tt>true</tt> if this set contained the specified element
1.248 + * @throws ClassCastException if <tt>o</tt> cannot be compared
1.249 + * with the elements currently in this set
1.250 + * @throws NullPointerException if the specified element is null
1.251 + */
1.252 + public boolean remove(Object o) {
1.253 + return m.remove(o, Boolean.TRUE);
1.254 + }
1.255 +
1.256 + /**
1.257 + * Removes all of the elements from this set.
1.258 + */
1.259 + public void clear() {
1.260 + m.clear();
1.261 + }
1.262 +
1.263 + /**
1.264 + * Returns an iterator over the elements in this set in ascending order.
1.265 + *
1.266 + * @return an iterator over the elements in this set in ascending order
1.267 + */
1.268 + public Iterator<E> iterator() {
1.269 + return m.navigableKeySet().iterator();
1.270 + }
1.271 +
1.272 + /**
1.273 + * Returns an iterator over the elements in this set in descending order.
1.274 + *
1.275 + * @return an iterator over the elements in this set in descending order
1.276 + */
1.277 + public Iterator<E> descendingIterator() {
1.278 + return m.descendingKeySet().iterator();
1.279 + }
1.280 +
1.281 +
1.282 + /* ---------------- AbstractSet Overrides -------------- */
1.283 +
1.284 + /**
1.285 + * Compares the specified object with this set for equality. Returns
1.286 + * <tt>true</tt> if the specified object is also a set, the two sets
1.287 + * have the same size, and every member of the specified set is
1.288 + * contained in this set (or equivalently, every member of this set is
1.289 + * contained in the specified set). This definition ensures that the
1.290 + * equals method works properly across different implementations of the
1.291 + * set interface.
1.292 + *
1.293 + * @param o the object to be compared for equality with this set
1.294 + * @return <tt>true</tt> if the specified object is equal to this set
1.295 + */
1.296 + public boolean equals(Object o) {
1.297 + // Override AbstractSet version to avoid calling size()
1.298 + if (o == this)
1.299 + return true;
1.300 + if (!(o instanceof Set))
1.301 + return false;
1.302 + Collection<?> c = (Collection<?>) o;
1.303 + try {
1.304 + return containsAll(c) && c.containsAll(this);
1.305 + } catch (ClassCastException unused) {
1.306 + return false;
1.307 + } catch (NullPointerException unused) {
1.308 + return false;
1.309 + }
1.310 + }
1.311 +
1.312 + /**
1.313 + * Removes from this set all of its elements that are contained in
1.314 + * the specified collection. If the specified collection is also
1.315 + * a set, this operation effectively modifies this set so that its
1.316 + * value is the <i>asymmetric set difference</i> of the two sets.
1.317 + *
1.318 + * @param c collection containing elements to be removed from this set
1.319 + * @return <tt>true</tt> if this set changed as a result of the call
1.320 + * @throws ClassCastException if the types of one or more elements in this
1.321 + * set are incompatible with the specified collection
1.322 + * @throws NullPointerException if the specified collection or any
1.323 + * of its elements are null
1.324 + */
1.325 + public boolean removeAll(Collection<?> c) {
1.326 + // Override AbstractSet version to avoid unnecessary call to size()
1.327 + boolean modified = false;
1.328 + for (Iterator<?> i = c.iterator(); i.hasNext(); )
1.329 + if (remove(i.next()))
1.330 + modified = true;
1.331 + return modified;
1.332 + }
1.333 +
1.334 + /* ---------------- Relational operations -------------- */
1.335 +
1.336 + /**
1.337 + * @throws ClassCastException {@inheritDoc}
1.338 + * @throws NullPointerException if the specified element is null
1.339 + */
1.340 + public E lower(E e) {
1.341 + return m.lowerKey(e);
1.342 + }
1.343 +
1.344 + /**
1.345 + * @throws ClassCastException {@inheritDoc}
1.346 + * @throws NullPointerException if the specified element is null
1.347 + */
1.348 + public E floor(E e) {
1.349 + return m.floorKey(e);
1.350 + }
1.351 +
1.352 + /**
1.353 + * @throws ClassCastException {@inheritDoc}
1.354 + * @throws NullPointerException if the specified element is null
1.355 + */
1.356 + public E ceiling(E e) {
1.357 + return m.ceilingKey(e);
1.358 + }
1.359 +
1.360 + /**
1.361 + * @throws ClassCastException {@inheritDoc}
1.362 + * @throws NullPointerException if the specified element is null
1.363 + */
1.364 + public E higher(E e) {
1.365 + return m.higherKey(e);
1.366 + }
1.367 +
1.368 + public E pollFirst() {
1.369 + Map.Entry<E,Object> e = m.pollFirstEntry();
1.370 + return (e == null) ? null : e.getKey();
1.371 + }
1.372 +
1.373 + public E pollLast() {
1.374 + Map.Entry<E,Object> e = m.pollLastEntry();
1.375 + return (e == null) ? null : e.getKey();
1.376 + }
1.377 +
1.378 +
1.379 + /* ---------------- SortedSet operations -------------- */
1.380 +
1.381 +
1.382 + public Comparator<? super E> comparator() {
1.383 + return m.comparator();
1.384 + }
1.385 +
1.386 + /**
1.387 + * @throws NoSuchElementException {@inheritDoc}
1.388 + */
1.389 + public E first() {
1.390 + return m.firstKey();
1.391 + }
1.392 +
1.393 + /**
1.394 + * @throws NoSuchElementException {@inheritDoc}
1.395 + */
1.396 + public E last() {
1.397 + return m.lastKey();
1.398 + }
1.399 +
1.400 + /**
1.401 + * @throws ClassCastException {@inheritDoc}
1.402 + * @throws NullPointerException if {@code fromElement} or
1.403 + * {@code toElement} is null
1.404 + * @throws IllegalArgumentException {@inheritDoc}
1.405 + */
1.406 + public NavigableSet<E> subSet(E fromElement,
1.407 + boolean fromInclusive,
1.408 + E toElement,
1.409 + boolean toInclusive) {
1.410 + return new ConcurrentSkipListSet<E>
1.411 + (m.subMap(fromElement, fromInclusive,
1.412 + toElement, toInclusive));
1.413 + }
1.414 +
1.415 + /**
1.416 + * @throws ClassCastException {@inheritDoc}
1.417 + * @throws NullPointerException if {@code toElement} is null
1.418 + * @throws IllegalArgumentException {@inheritDoc}
1.419 + */
1.420 + public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1.421 + return new ConcurrentSkipListSet<E>(m.headMap(toElement, inclusive));
1.422 + }
1.423 +
1.424 + /**
1.425 + * @throws ClassCastException {@inheritDoc}
1.426 + * @throws NullPointerException if {@code fromElement} is null
1.427 + * @throws IllegalArgumentException {@inheritDoc}
1.428 + */
1.429 + public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1.430 + return new ConcurrentSkipListSet<E>(m.tailMap(fromElement, inclusive));
1.431 + }
1.432 +
1.433 + /**
1.434 + * @throws ClassCastException {@inheritDoc}
1.435 + * @throws NullPointerException if {@code fromElement} or
1.436 + * {@code toElement} is null
1.437 + * @throws IllegalArgumentException {@inheritDoc}
1.438 + */
1.439 + public NavigableSet<E> subSet(E fromElement, E toElement) {
1.440 + return subSet(fromElement, true, toElement, false);
1.441 + }
1.442 +
1.443 + /**
1.444 + * @throws ClassCastException {@inheritDoc}
1.445 + * @throws NullPointerException if {@code toElement} is null
1.446 + * @throws IllegalArgumentException {@inheritDoc}
1.447 + */
1.448 + public NavigableSet<E> headSet(E toElement) {
1.449 + return headSet(toElement, false);
1.450 + }
1.451 +
1.452 + /**
1.453 + * @throws ClassCastException {@inheritDoc}
1.454 + * @throws NullPointerException if {@code fromElement} is null
1.455 + * @throws IllegalArgumentException {@inheritDoc}
1.456 + */
1.457 + public NavigableSet<E> tailSet(E fromElement) {
1.458 + return tailSet(fromElement, true);
1.459 + }
1.460 +
1.461 + /**
1.462 + * Returns a reverse order view of the elements contained in this set.
1.463 + * The descending set is backed by this set, so changes to the set are
1.464 + * reflected in the descending set, and vice-versa.
1.465 + *
1.466 + * <p>The returned set has an ordering equivalent to
1.467 + * <tt>{@link Collections#reverseOrder(Comparator) Collections.reverseOrder}(comparator())</tt>.
1.468 + * The expression {@code s.descendingSet().descendingSet()} returns a
1.469 + * view of {@code s} essentially equivalent to {@code s}.
1.470 + *
1.471 + * @return a reverse order view of this set
1.472 + */
1.473 + public NavigableSet<E> descendingSet() {
1.474 + return new ConcurrentSkipListSet(m.descendingMap());
1.475 + }
1.476 +
1.477 + // Support for resetting map in clone
1.478 + private void setMap(ConcurrentNavigableMap<E,Object> map) {
1.479 + UNSAFE.putObjectVolatile(this, mapOffset, map);
1.480 + }
1.481 +
1.482 + private static final sun.misc.Unsafe UNSAFE;
1.483 + private static final long mapOffset;
1.484 + static {
1.485 + try {
1.486 + UNSAFE = sun.misc.Unsafe.getUnsafe();
1.487 + Class k = ConcurrentSkipListSet.class;
1.488 + mapOffset = UNSAFE.objectFieldOffset
1.489 + (k.getDeclaredField("m"));
1.490 + } catch (Exception e) {
1.491 + throw new Error(e);
1.492 + }
1.493 + }
1.494 +}