1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/rt/emul/compact/src/main/java/java/util/concurrent/CopyOnWriteArraySet.java Sat Mar 19 10:46:31 2016 +0100
1.3 @@ -0,0 +1,392 @@
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 +
1.42 +/**
1.43 + * A {@link java.util.Set} that uses an internal {@link CopyOnWriteArrayList}
1.44 + * for all of its operations. Thus, it shares the same basic properties:
1.45 + * <ul>
1.46 + * <li>It is best suited for applications in which set sizes generally
1.47 + * stay small, read-only operations
1.48 + * vastly outnumber mutative operations, and you need
1.49 + * to prevent interference among threads during traversal.
1.50 + * <li>It is thread-safe.
1.51 + * <li>Mutative operations (<tt>add</tt>, <tt>set</tt>, <tt>remove</tt>, etc.)
1.52 + * are expensive since they usually entail copying the entire underlying
1.53 + * array.
1.54 + * <li>Iterators do not support the mutative <tt>remove</tt> operation.
1.55 + * <li>Traversal via iterators is fast and cannot encounter
1.56 + * interference from other threads. Iterators rely on
1.57 + * unchanging snapshots of the array at the time the iterators were
1.58 + * constructed.
1.59 + * </ul>
1.60 + *
1.61 + * <p> <b>Sample Usage.</b> The following code sketch uses a
1.62 + * copy-on-write set to maintain a set of Handler objects that
1.63 + * perform some action upon state updates.
1.64 + *
1.65 + * <pre> {@code
1.66 + * class Handler { void handle(); ... }
1.67 + *
1.68 + * class X {
1.69 + * private final CopyOnWriteArraySet<Handler> handlers
1.70 + * = new CopyOnWriteArraySet<Handler>();
1.71 + * public void addHandler(Handler h) { handlers.add(h); }
1.72 + *
1.73 + * private long internalState;
1.74 + * private synchronized void changeState() { internalState = ...; }
1.75 + *
1.76 + * public void update() {
1.77 + * changeState();
1.78 + * for (Handler handler : handlers)
1.79 + * handler.handle();
1.80 + * }
1.81 + * }}</pre>
1.82 + *
1.83 + * <p>This class is a member of the
1.84 + * <a href="{@docRoot}/../technotes/guides/collections/index.html">
1.85 + * Java Collections Framework</a>.
1.86 + *
1.87 + * @see CopyOnWriteArrayList
1.88 + * @since 1.5
1.89 + * @author Doug Lea
1.90 + * @param <E> the type of elements held in this collection
1.91 + */
1.92 +public class CopyOnWriteArraySet<E> extends AbstractSet<E>
1.93 + implements java.io.Serializable {
1.94 + private static final long serialVersionUID = 5457747651344034263L;
1.95 +
1.96 + private final CopyOnWriteArrayList<E> al;
1.97 +
1.98 + /**
1.99 + * Creates an empty set.
1.100 + */
1.101 + public CopyOnWriteArraySet() {
1.102 + al = new CopyOnWriteArrayList<E>();
1.103 + }
1.104 +
1.105 + /**
1.106 + * Creates a set containing all of the elements of the specified
1.107 + * collection.
1.108 + *
1.109 + * @param c the collection of elements to initially contain
1.110 + * @throws NullPointerException if the specified collection is null
1.111 + */
1.112 + public CopyOnWriteArraySet(Collection<? extends E> c) {
1.113 + al = new CopyOnWriteArrayList<E>();
1.114 + al.addAllAbsent(c);
1.115 + }
1.116 +
1.117 + /**
1.118 + * Returns the number of elements in this set.
1.119 + *
1.120 + * @return the number of elements in this set
1.121 + */
1.122 + public int size() {
1.123 + return al.size();
1.124 + }
1.125 +
1.126 + /**
1.127 + * Returns <tt>true</tt> if this set contains no elements.
1.128 + *
1.129 + * @return <tt>true</tt> if this set contains no elements
1.130 + */
1.131 + public boolean isEmpty() {
1.132 + return al.isEmpty();
1.133 + }
1.134 +
1.135 + /**
1.136 + * Returns <tt>true</tt> if this set contains the specified element.
1.137 + * More formally, returns <tt>true</tt> if and only if this set
1.138 + * contains an element <tt>e</tt> such that
1.139 + * <tt>(o==null ? e==null : o.equals(e))</tt>.
1.140 + *
1.141 + * @param o element whose presence in this set is to be tested
1.142 + * @return <tt>true</tt> if this set contains the specified element
1.143 + */
1.144 + public boolean contains(Object o) {
1.145 + return al.contains(o);
1.146 + }
1.147 +
1.148 + /**
1.149 + * Returns an array containing all of the elements in this set.
1.150 + * If this set makes any guarantees as to what order its elements
1.151 + * are returned by its iterator, this method must return the
1.152 + * elements in the same order.
1.153 + *
1.154 + * <p>The returned array will be "safe" in that no references to it
1.155 + * are maintained by this set. (In other words, this method must
1.156 + * allocate a new array even if this set is backed by an array).
1.157 + * The caller is thus free to modify the returned array.
1.158 + *
1.159 + * <p>This method acts as bridge between array-based and collection-based
1.160 + * APIs.
1.161 + *
1.162 + * @return an array containing all the elements in this set
1.163 + */
1.164 + public Object[] toArray() {
1.165 + return al.toArray();
1.166 + }
1.167 +
1.168 + /**
1.169 + * Returns an array containing all of the elements in this set; the
1.170 + * runtime type of the returned array is that of the specified array.
1.171 + * If the set fits in the specified array, it is returned therein.
1.172 + * Otherwise, a new array is allocated with the runtime type of the
1.173 + * specified array and the size of this set.
1.174 + *
1.175 + * <p>If this set fits in the specified array with room to spare
1.176 + * (i.e., the array has more elements than this set), the element in
1.177 + * the array immediately following the end of the set is set to
1.178 + * <tt>null</tt>. (This is useful in determining the length of this
1.179 + * set <i>only</i> if the caller knows that this set does not contain
1.180 + * any null elements.)
1.181 + *
1.182 + * <p>If this set makes any guarantees as to what order its elements
1.183 + * are returned by its iterator, this method must return the elements
1.184 + * in the same order.
1.185 + *
1.186 + * <p>Like the {@link #toArray()} method, this method acts as bridge between
1.187 + * array-based and collection-based APIs. Further, this method allows
1.188 + * precise control over the runtime type of the output array, and may,
1.189 + * under certain circumstances, be used to save allocation costs.
1.190 + *
1.191 + * <p>Suppose <tt>x</tt> is a set known to contain only strings.
1.192 + * The following code can be used to dump the set into a newly allocated
1.193 + * array of <tt>String</tt>:
1.194 + *
1.195 + * <pre>
1.196 + * String[] y = x.toArray(new String[0]);</pre>
1.197 + *
1.198 + * Note that <tt>toArray(new Object[0])</tt> is identical in function to
1.199 + * <tt>toArray()</tt>.
1.200 + *
1.201 + * @param a the array into which the elements of this set are to be
1.202 + * stored, if it is big enough; otherwise, a new array of the same
1.203 + * runtime type is allocated for this purpose.
1.204 + * @return an array containing all the elements in this set
1.205 + * @throws ArrayStoreException if the runtime type of the specified array
1.206 + * is not a supertype of the runtime type of every element in this
1.207 + * set
1.208 + * @throws NullPointerException if the specified array is null
1.209 + */
1.210 + public <T> T[] toArray(T[] a) {
1.211 + return al.toArray(a);
1.212 + }
1.213 +
1.214 + /**
1.215 + * Removes all of the elements from this set.
1.216 + * The set will be empty after this call returns.
1.217 + */
1.218 + public void clear() {
1.219 + al.clear();
1.220 + }
1.221 +
1.222 + /**
1.223 + * Removes the specified element from this set if it is present.
1.224 + * More formally, removes an element <tt>e</tt> such that
1.225 + * <tt>(o==null ? e==null : o.equals(e))</tt>,
1.226 + * if this set contains such an element. Returns <tt>true</tt> if
1.227 + * this set contained the element (or equivalently, if this set
1.228 + * changed as a result of the call). (This set will not contain the
1.229 + * element once the call returns.)
1.230 + *
1.231 + * @param o object to be removed from this set, if present
1.232 + * @return <tt>true</tt> if this set contained the specified element
1.233 + */
1.234 + public boolean remove(Object o) {
1.235 + return al.remove(o);
1.236 + }
1.237 +
1.238 + /**
1.239 + * Adds the specified element to this set if it is not already present.
1.240 + * More formally, adds the specified element <tt>e</tt> to this set if
1.241 + * the set contains no element <tt>e2</tt> such that
1.242 + * <tt>(e==null ? e2==null : e.equals(e2))</tt>.
1.243 + * If this set already contains the element, the call leaves the set
1.244 + * unchanged and returns <tt>false</tt>.
1.245 + *
1.246 + * @param e element to be added to this set
1.247 + * @return <tt>true</tt> if this set did not already contain the specified
1.248 + * element
1.249 + */
1.250 + public boolean add(E e) {
1.251 + return al.addIfAbsent(e);
1.252 + }
1.253 +
1.254 + /**
1.255 + * Returns <tt>true</tt> if this set contains all of the elements of the
1.256 + * specified collection. If the specified collection is also a set, this
1.257 + * method returns <tt>true</tt> if it is a <i>subset</i> of this set.
1.258 + *
1.259 + * @param c collection to be checked for containment in this set
1.260 + * @return <tt>true</tt> if this set contains all of the elements of the
1.261 + * specified collection
1.262 + * @throws NullPointerException if the specified collection is null
1.263 + * @see #contains(Object)
1.264 + */
1.265 + public boolean containsAll(Collection<?> c) {
1.266 + return al.containsAll(c);
1.267 + }
1.268 +
1.269 + /**
1.270 + * Adds all of the elements in the specified collection to this set if
1.271 + * they're not already present. If the specified collection is also a
1.272 + * set, the <tt>addAll</tt> operation effectively modifies this set so
1.273 + * that its value is the <i>union</i> of the two sets. The behavior of
1.274 + * this operation is undefined if the specified collection is modified
1.275 + * while the operation is in progress.
1.276 + *
1.277 + * @param c collection containing elements to be added to this set
1.278 + * @return <tt>true</tt> if this set changed as a result of the call
1.279 + * @throws NullPointerException if the specified collection is null
1.280 + * @see #add(Object)
1.281 + */
1.282 + public boolean addAll(Collection<? extends E> c) {
1.283 + return al.addAllAbsent(c) > 0;
1.284 + }
1.285 +
1.286 + /**
1.287 + * Removes from this set all of its elements that are contained in the
1.288 + * specified collection. If the specified collection is also a set,
1.289 + * this operation effectively modifies this set so that its value is the
1.290 + * <i>asymmetric set difference</i> of the two sets.
1.291 + *
1.292 + * @param c collection containing elements to be removed from this set
1.293 + * @return <tt>true</tt> if this set changed as a result of the call
1.294 + * @throws ClassCastException if the class of an element of this set
1.295 + * is incompatible with the specified collection (optional)
1.296 + * @throws NullPointerException if this set contains a null element and the
1.297 + * specified collection does not permit null elements (optional),
1.298 + * or if the specified collection is null
1.299 + * @see #remove(Object)
1.300 + */
1.301 + public boolean removeAll(Collection<?> c) {
1.302 + return al.removeAll(c);
1.303 + }
1.304 +
1.305 + /**
1.306 + * Retains only the elements in this set that are contained in the
1.307 + * specified collection. In other words, removes from this set all of
1.308 + * its elements that are not contained in the specified collection. If
1.309 + * the specified collection is also a set, this operation effectively
1.310 + * modifies this set so that its value is the <i>intersection</i> of the
1.311 + * two sets.
1.312 + *
1.313 + * @param c collection containing elements to be retained in this set
1.314 + * @return <tt>true</tt> if this set changed as a result of the call
1.315 + * @throws ClassCastException if the class of an element of this set
1.316 + * is incompatible with the specified collection (optional)
1.317 + * @throws NullPointerException if this set contains a null element and the
1.318 + * specified collection does not permit null elements (optional),
1.319 + * or if the specified collection is null
1.320 + * @see #remove(Object)
1.321 + */
1.322 + public boolean retainAll(Collection<?> c) {
1.323 + return al.retainAll(c);
1.324 + }
1.325 +
1.326 + /**
1.327 + * Returns an iterator over the elements contained in this set
1.328 + * in the order in which these elements were added.
1.329 + *
1.330 + * <p>The returned iterator provides a snapshot of the state of the set
1.331 + * when the iterator was constructed. No synchronization is needed while
1.332 + * traversing the iterator. The iterator does <em>NOT</em> support the
1.333 + * <tt>remove</tt> method.
1.334 + *
1.335 + * @return an iterator over the elements in this set
1.336 + */
1.337 + public Iterator<E> iterator() {
1.338 + return al.iterator();
1.339 + }
1.340 +
1.341 + /**
1.342 + * Compares the specified object with this set for equality.
1.343 + * Returns {@code true} if the specified object is the same object
1.344 + * as this object, or if it is also a {@link Set} and the elements
1.345 + * returned by an {@linkplain List#iterator() iterator} over the
1.346 + * specified set are the same as the elements returned by an
1.347 + * iterator over this set. More formally, the two iterators are
1.348 + * considered to return the same elements if they return the same
1.349 + * number of elements and for every element {@code e1} returned by
1.350 + * the iterator over the specified set, there is an element
1.351 + * {@code e2} returned by the iterator over this set such that
1.352 + * {@code (e1==null ? e2==null : e1.equals(e2))}.
1.353 + *
1.354 + * @param o object to be compared for equality with this set
1.355 + * @return {@code true} if the specified object is equal to this set
1.356 + */
1.357 + public boolean equals(Object o) {
1.358 + if (o == this)
1.359 + return true;
1.360 + if (!(o instanceof Set))
1.361 + return false;
1.362 + Set<?> set = (Set<?>)(o);
1.363 + Iterator<?> it = set.iterator();
1.364 +
1.365 + // Uses O(n^2) algorithm that is only appropriate
1.366 + // for small sets, which CopyOnWriteArraySets should be.
1.367 +
1.368 + // Use a single snapshot of underlying array
1.369 + Object[] elements = al.getArray();
1.370 + int len = elements.length;
1.371 + // Mark matched elements to avoid re-checking
1.372 + boolean[] matched = new boolean[len];
1.373 + int k = 0;
1.374 + outer: while (it.hasNext()) {
1.375 + if (++k > len)
1.376 + return false;
1.377 + Object x = it.next();
1.378 + for (int i = 0; i < len; ++i) {
1.379 + if (!matched[i] && eq(x, elements[i])) {
1.380 + matched[i] = true;
1.381 + continue outer;
1.382 + }
1.383 + }
1.384 + return false;
1.385 + }
1.386 + return k == len;
1.387 + }
1.388 +
1.389 + /**
1.390 + * Test for equality, coping with nulls.
1.391 + */
1.392 + private static boolean eq(Object o1, Object o2) {
1.393 + return (o1 == null ? o2 == null : o1.equals(o2));
1.394 + }
1.395 +}