jaroslav@1890: /* jaroslav@1890: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. jaroslav@1890: * jaroslav@1890: * This code is free software; you can redistribute it and/or modify it jaroslav@1890: * under the terms of the GNU General Public License version 2 only, as jaroslav@1890: * published by the Free Software Foundation. Oracle designates this jaroslav@1890: * particular file as subject to the "Classpath" exception as provided jaroslav@1890: * by Oracle in the LICENSE file that accompanied this code. jaroslav@1890: * jaroslav@1890: * This code is distributed in the hope that it will be useful, but WITHOUT jaroslav@1890: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or jaroslav@1890: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License jaroslav@1890: * version 2 for more details (a copy is included in the LICENSE file that jaroslav@1890: * accompanied this code). jaroslav@1890: * jaroslav@1890: * You should have received a copy of the GNU General Public License version jaroslav@1890: * 2 along with this work; if not, write to the Free Software Foundation, jaroslav@1890: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. jaroslav@1890: * jaroslav@1890: * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA jaroslav@1890: * or visit www.oracle.com if you need additional information or have any jaroslav@1890: * questions. jaroslav@1890: */ jaroslav@1890: jaroslav@1890: /* jaroslav@1890: * This file is available under and governed by the GNU General Public jaroslav@1890: * License version 2 only, as published by the Free Software Foundation. jaroslav@1890: * However, the following notice accompanied the original version of this jaroslav@1890: * file: jaroslav@1890: * jaroslav@1890: * Written by Doug Lea with assistance from members of JCP JSR-166 jaroslav@1890: * Expert Group and released to the public domain, as explained at jaroslav@1890: * http://creativecommons.org/publicdomain/zero/1.0/ jaroslav@1890: */ jaroslav@1890: jaroslav@1890: package java.util.concurrent; jaroslav@1890: import java.util.*; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * A {@link java.util.Set} that uses an internal {@link CopyOnWriteArrayList} jaroslav@1890: * for all of its operations. Thus, it shares the same basic properties: jaroslav@1890: * jaroslav@1890: * jaroslav@1890: *

Sample Usage. The following code sketch uses a jaroslav@1890: * copy-on-write set to maintain a set of Handler objects that jaroslav@1890: * perform some action upon state updates. jaroslav@1890: * jaroslav@1890: * 

 {@code
jaroslav@1890:  * class Handler { void handle(); ... }
jaroslav@1890:  *
jaroslav@1890:  * class X {
jaroslav@1890:  *   private final CopyOnWriteArraySet handlers
jaroslav@1890:  *     = new CopyOnWriteArraySet();
jaroslav@1890:  *   public void addHandler(Handler h) { handlers.add(h); }
jaroslav@1890:  *
jaroslav@1890:  *   private long internalState;
jaroslav@1890:  *   private synchronized void changeState() { internalState = ...; }
jaroslav@1890:  *
jaroslav@1890:  *   public void update() {
jaroslav@1890:  *     changeState();
jaroslav@1890:  *     for (Handler handler : handlers)
jaroslav@1890:  *        handler.handle();
jaroslav@1890:  *   }
jaroslav@1890:  * }}
jaroslav@1890: * jaroslav@1890: *

This class is a member of the jaroslav@1890: * jaroslav@1890: * Java Collections Framework. jaroslav@1890: * jaroslav@1890: * @see CopyOnWriteArrayList jaroslav@1890: * @since 1.5 jaroslav@1890: * @author Doug Lea jaroslav@1890: * @param the type of elements held in this collection jaroslav@1890: */ jaroslav@1890: public class CopyOnWriteArraySet extends AbstractSet jaroslav@1890: implements java.io.Serializable { jaroslav@1890: private static final long serialVersionUID = 5457747651344034263L; jaroslav@1890: jaroslav@1890: private final CopyOnWriteArrayList al; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Creates an empty set. jaroslav@1890: */ jaroslav@1890: public CopyOnWriteArraySet() { jaroslav@1890: al = new CopyOnWriteArrayList(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Creates a set containing all of the elements of the specified jaroslav@1890: * collection. jaroslav@1890: * jaroslav@1890: * @param c the collection of elements to initially contain jaroslav@1890: * @throws NullPointerException if the specified collection is null jaroslav@1890: */ jaroslav@1890: public CopyOnWriteArraySet(Collection c) { jaroslav@1890: al = new CopyOnWriteArrayList(); jaroslav@1890: al.addAllAbsent(c); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns the number of elements in this set. jaroslav@1890: * jaroslav@1890: * @return the number of elements in this set jaroslav@1890: */ jaroslav@1890: public int size() { jaroslav@1890: return al.size(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns true if this set contains no elements. jaroslav@1890: * jaroslav@1890: * @return true if this set contains no elements jaroslav@1890: */ jaroslav@1890: public boolean isEmpty() { jaroslav@1890: return al.isEmpty(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns true if this set contains the specified element. jaroslav@1890: * More formally, returns true if and only if this set jaroslav@1890: * contains an element e such that jaroslav@1890: * (o==null ? e==null : o.equals(e)). jaroslav@1890: * jaroslav@1890: * @param o element whose presence in this set is to be tested jaroslav@1890: * @return true if this set contains the specified element jaroslav@1890: */ jaroslav@1890: public boolean contains(Object o) { jaroslav@1890: return al.contains(o); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns an array containing all of the elements in this set. jaroslav@1890: * If this set makes any guarantees as to what order its elements jaroslav@1890: * are returned by its iterator, this method must return the jaroslav@1890: * elements in the same order. jaroslav@1890: * jaroslav@1890: *

The returned array will be "safe" in that no references to it jaroslav@1890: * are maintained by this set. (In other words, this method must jaroslav@1890: * allocate a new array even if this set is backed by an array). jaroslav@1890: * The caller is thus free to modify the returned array. jaroslav@1890: * jaroslav@1890: *

This method acts as bridge between array-based and collection-based jaroslav@1890: * APIs. jaroslav@1890: * jaroslav@1890: * @return an array containing all the elements in this set jaroslav@1890: */ jaroslav@1890: public Object[] toArray() { jaroslav@1890: return al.toArray(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns an array containing all of the elements in this set; the jaroslav@1890: * runtime type of the returned array is that of the specified array. jaroslav@1890: * If the set fits in the specified array, it is returned therein. jaroslav@1890: * Otherwise, a new array is allocated with the runtime type of the jaroslav@1890: * specified array and the size of this set. jaroslav@1890: * jaroslav@1890: *

If this set fits in the specified array with room to spare jaroslav@1890: * (i.e., the array has more elements than this set), the element in jaroslav@1890: * the array immediately following the end of the set is set to jaroslav@1890: * null. (This is useful in determining the length of this jaroslav@1890: * set only if the caller knows that this set does not contain jaroslav@1890: * any null elements.) jaroslav@1890: * jaroslav@1890: *

If this set makes any guarantees as to what order its elements jaroslav@1890: * are returned by its iterator, this method must return the elements jaroslav@1890: * in the same order. jaroslav@1890: * jaroslav@1890: *

Like the {@link #toArray()} method, this method acts as bridge between jaroslav@1890: * array-based and collection-based APIs. Further, this method allows jaroslav@1890: * precise control over the runtime type of the output array, and may, jaroslav@1890: * under certain circumstances, be used to save allocation costs. jaroslav@1890: * jaroslav@1890: *

Suppose x is a set known to contain only strings. jaroslav@1890: * The following code can be used to dump the set into a newly allocated jaroslav@1890: * array of String: jaroslav@1890: * jaroslav@1890: * 

jaroslav@1890:      *     String[] y = x.toArray(new String[0]);
jaroslav@1890: * jaroslav@1890: * Note that toArray(new Object[0]) is identical in function to jaroslav@1890: * toArray(). jaroslav@1890: * jaroslav@1890: * @param a the array into which the elements of this set are to be jaroslav@1890: * stored, if it is big enough; otherwise, a new array of the same jaroslav@1890: * runtime type is allocated for this purpose. jaroslav@1890: * @return an array containing all the elements in this set jaroslav@1890: * @throws ArrayStoreException if the runtime type of the specified array jaroslav@1890: * is not a supertype of the runtime type of every element in this jaroslav@1890: * set jaroslav@1890: * @throws NullPointerException if the specified array is null jaroslav@1890: */ jaroslav@1890: public T[] toArray(T[] a) { jaroslav@1890: return al.toArray(a); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Removes all of the elements from this set. jaroslav@1890: * The set will be empty after this call returns. jaroslav@1890: */ jaroslav@1890: public void clear() { jaroslav@1890: al.clear(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Removes the specified element from this set if it is present. jaroslav@1890: * More formally, removes an element e such that jaroslav@1890: * (o==null ? e==null : o.equals(e)), jaroslav@1890: * if this set contains such an element. Returns true if jaroslav@1890: * this set contained the element (or equivalently, if this set jaroslav@1890: * changed as a result of the call). (This set will not contain the jaroslav@1890: * element once the call returns.) jaroslav@1890: * jaroslav@1890: * @param o object to be removed from this set, if present jaroslav@1890: * @return true if this set contained the specified element jaroslav@1890: */ jaroslav@1890: public boolean remove(Object o) { jaroslav@1890: return al.remove(o); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Adds the specified element to this set if it is not already present. jaroslav@1890: * More formally, adds the specified element e to this set if jaroslav@1890: * the set contains no element e2 such that jaroslav@1890: * (e==null ? e2==null : e.equals(e2)). jaroslav@1890: * If this set already contains the element, the call leaves the set jaroslav@1890: * unchanged and returns false. jaroslav@1890: * jaroslav@1890: * @param e element to be added to this set jaroslav@1890: * @return true if this set did not already contain the specified jaroslav@1890: * element jaroslav@1890: */ jaroslav@1890: public boolean add(E e) { jaroslav@1890: return al.addIfAbsent(e); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns true if this set contains all of the elements of the jaroslav@1890: * specified collection. If the specified collection is also a set, this jaroslav@1890: * method returns true if it is a subset of this set. jaroslav@1890: * jaroslav@1890: * @param c collection to be checked for containment in this set jaroslav@1890: * @return true if this set contains all of the elements of the jaroslav@1890: * specified collection jaroslav@1890: * @throws NullPointerException if the specified collection is null jaroslav@1890: * @see #contains(Object) jaroslav@1890: */ jaroslav@1890: public boolean containsAll(Collection c) { jaroslav@1890: return al.containsAll(c); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Adds all of the elements in the specified collection to this set if jaroslav@1890: * they're not already present. If the specified collection is also a jaroslav@1890: * set, the addAll operation effectively modifies this set so jaroslav@1890: * that its value is the union of the two sets. The behavior of jaroslav@1890: * this operation is undefined if the specified collection is modified jaroslav@1890: * while the operation is in progress. jaroslav@1890: * jaroslav@1890: * @param c collection containing elements to be added to this set jaroslav@1890: * @return true if this set changed as a result of the call jaroslav@1890: * @throws NullPointerException if the specified collection is null jaroslav@1890: * @see #add(Object) jaroslav@1890: */ jaroslav@1890: public boolean addAll(Collection c) { jaroslav@1890: return al.addAllAbsent(c) > 0; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Removes from this set all of its elements that are contained in the jaroslav@1890: * specified collection. If the specified collection is also a set, jaroslav@1890: * this operation effectively modifies this set so that its value is the jaroslav@1890: * asymmetric set difference of the two sets. jaroslav@1890: * jaroslav@1890: * @param c collection containing elements to be removed from this set jaroslav@1890: * @return true if this set changed as a result of the call jaroslav@1890: * @throws ClassCastException if the class of an element of this set jaroslav@1890: * is incompatible with the specified collection (optional) jaroslav@1890: * @throws NullPointerException if this set contains a null element and the jaroslav@1890: * specified collection does not permit null elements (optional), jaroslav@1890: * or if the specified collection is null jaroslav@1890: * @see #remove(Object) jaroslav@1890: */ jaroslav@1890: public boolean removeAll(Collection c) { jaroslav@1890: return al.removeAll(c); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Retains only the elements in this set that are contained in the jaroslav@1890: * specified collection. In other words, removes from this set all of jaroslav@1890: * its elements that are not contained in the specified collection. If jaroslav@1890: * the specified collection is also a set, this operation effectively jaroslav@1890: * modifies this set so that its value is the intersection of the jaroslav@1890: * two sets. jaroslav@1890: * jaroslav@1890: * @param c collection containing elements to be retained in this set jaroslav@1890: * @return true if this set changed as a result of the call jaroslav@1890: * @throws ClassCastException if the class of an element of this set jaroslav@1890: * is incompatible with the specified collection (optional) jaroslav@1890: * @throws NullPointerException if this set contains a null element and the jaroslav@1890: * specified collection does not permit null elements (optional), jaroslav@1890: * or if the specified collection is null jaroslav@1890: * @see #remove(Object) jaroslav@1890: */ jaroslav@1890: public boolean retainAll(Collection c) { jaroslav@1890: return al.retainAll(c); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns an iterator over the elements contained in this set jaroslav@1890: * in the order in which these elements were added. jaroslav@1890: * jaroslav@1890: *

The returned iterator provides a snapshot of the state of the set jaroslav@1890: * when the iterator was constructed. No synchronization is needed while jaroslav@1890: * traversing the iterator. The iterator does NOT support the jaroslav@1890: * remove method. jaroslav@1890: * jaroslav@1890: * @return an iterator over the elements in this set jaroslav@1890: */ jaroslav@1890: public Iterator iterator() { jaroslav@1890: return al.iterator(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Compares the specified object with this set for equality. jaroslav@1890: * Returns {@code true} if the specified object is the same object jaroslav@1890: * as this object, or if it is also a {@link Set} and the elements jaroslav@1890: * returned by an {@linkplain List#iterator() iterator} over the jaroslav@1890: * specified set are the same as the elements returned by an jaroslav@1890: * iterator over this set. More formally, the two iterators are jaroslav@1890: * considered to return the same elements if they return the same jaroslav@1890: * number of elements and for every element {@code e1} returned by jaroslav@1890: * the iterator over the specified set, there is an element jaroslav@1890: * {@code e2} returned by the iterator over this set such that jaroslav@1890: * {@code (e1==null ? e2==null : e1.equals(e2))}. jaroslav@1890: * jaroslav@1890: * @param o object to be compared for equality with this set jaroslav@1890: * @return {@code true} if the specified object is equal to this set jaroslav@1890: */ jaroslav@1890: public boolean equals(Object o) { jaroslav@1890: if (o == this) jaroslav@1890: return true; jaroslav@1890: if (!(o instanceof Set)) jaroslav@1890: return false; jaroslav@1890: Set set = (Set)(o); jaroslav@1890: Iterator it = set.iterator(); jaroslav@1890: jaroslav@1890: // Uses O(n^2) algorithm that is only appropriate jaroslav@1890: // for small sets, which CopyOnWriteArraySets should be. jaroslav@1890: jaroslav@1890: // Use a single snapshot of underlying array jaroslav@1890: Object[] elements = al.getArray(); jaroslav@1890: int len = elements.length; jaroslav@1890: // Mark matched elements to avoid re-checking jaroslav@1890: boolean[] matched = new boolean[len]; jaroslav@1890: int k = 0; jaroslav@1890: outer: while (it.hasNext()) { jaroslav@1890: if (++k > len) jaroslav@1890: return false; jaroslav@1890: Object x = it.next(); jaroslav@1890: for (int i = 0; i < len; ++i) { jaroslav@1890: if (!matched[i] && eq(x, elements[i])) { jaroslav@1890: matched[i] = true; jaroslav@1890: continue outer; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: return false; jaroslav@1890: } jaroslav@1890: return k == len; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Test for equality, coping with nulls. jaroslav@1890: */ jaroslav@1890: private static boolean eq(Object o1, Object o2) { jaroslav@1890: return (o1 == null ? o2 == null : o1.equals(o2)); jaroslav@1890: } jaroslav@1890: }