| /* |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. Oracle designates this |
| * particular file as subject to the "Classpath" exception as provided |
| * by Oracle in the LICENSE file that accompanied this code. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| */ |
| |
| /* |
| * Written by Doug Lea with assistance from members of JCP JSR-166 |
| * Expert Group. Adapted and released, under explicit permission, |
| * from JDK ArrayList.java which carries the following copyright: |
| * |
| * Copyright 1997 by Sun Microsystems, Inc., |
| * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A. |
| * All rights reserved. |
| */ |
| |
| package java.util.concurrent; |
| |
| import java.lang.reflect.Field; |
| import java.util.AbstractList; |
| import java.util.Arrays; |
| import java.util.Collection; |
| import java.util.Comparator; |
| import java.util.ConcurrentModificationException; |
| import java.util.Iterator; |
| import java.util.List; |
| import java.util.ListIterator; |
| import java.util.NoSuchElementException; |
| import java.util.Objects; |
| import java.util.RandomAccess; |
| import java.util.Spliterator; |
| import java.util.Spliterators; |
| import java.util.function.Consumer; |
| import java.util.function.Predicate; |
| import java.util.function.UnaryOperator; |
| |
| /** |
| * A thread-safe variant of {@link java.util.ArrayList} in which all mutative |
| * operations ({@code add}, {@code set}, and so on) are implemented by |
| * making a fresh copy of the underlying array. |
| * |
| * <p>This is ordinarily too costly, but may be <em>more</em> efficient |
| * than alternatives when traversal operations vastly outnumber |
| * mutations, and is useful when you cannot or don't want to |
| * synchronize traversals, yet need to preclude interference among |
| * concurrent threads. The "snapshot" style iterator method uses a |
| * reference to the state of the array at the point that the iterator |
| * was created. This array never changes during the lifetime of the |
| * iterator, so interference is impossible and the iterator is |
| * guaranteed not to throw {@code ConcurrentModificationException}. |
| * The iterator will not reflect additions, removals, or changes to |
| * the list since the iterator was created. Element-changing |
| * operations on iterators themselves ({@code remove}, {@code set}, and |
| * {@code add}) are not supported. These methods throw |
| * {@code UnsupportedOperationException}. |
| * |
| * <p>All elements are permitted, including {@code null}. |
| * |
| * <p>Memory consistency effects: As with other concurrent |
| * collections, actions in a thread prior to placing an object into a |
| * {@code CopyOnWriteArrayList} |
| * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a> |
| * actions subsequent to the access or removal of that element from |
| * the {@code CopyOnWriteArrayList} in another thread. |
| * |
| * <p>This class is a member of the |
| * <a href="{@docRoot}/../technotes/guides/collections/index.html"> |
| * Java Collections Framework</a>. |
| * |
| * @since 1.5 |
| * @author Doug Lea |
| * @param <E> the type of elements held in this list |
| */ |
| public class CopyOnWriteArrayList<E> |
| implements List<E>, RandomAccess, Cloneable, java.io.Serializable { |
| private static final long serialVersionUID = 8673264195747942595L; |
| |
| /** |
| * The lock protecting all mutators. (We have a mild preference |
| * for builtin monitors over ReentrantLock when either will do.) |
| */ |
| final transient Object lock = new Object(); |
| |
| /** The array, accessed only via getArray/setArray. */ |
| private transient volatile Object[] array; |
| |
| /** |
| * Gets the array. Non-private so as to also be accessible |
| * from CopyOnWriteArraySet class. |
| */ |
| final Object[] getArray() { |
| return array; |
| } |
| |
| /** |
| * Sets the array. |
| */ |
| final void setArray(Object[] a) { |
| array = a; |
| } |
| |
| /** |
| * Creates an empty list. |
| */ |
| public CopyOnWriteArrayList() { |
| setArray(new Object[0]); |
| } |
| |
| /** |
| * Creates a list containing the elements of the specified |
| * collection, in the order they are returned by the collection's |
| * iterator. |
| * |
| * @param c the collection of initially held elements |
| * @throws NullPointerException if the specified collection is null |
| */ |
| public CopyOnWriteArrayList(Collection<? extends E> c) { |
| Object[] elements; |
| if (c.getClass() == CopyOnWriteArrayList.class) |
| elements = ((CopyOnWriteArrayList<?>)c).getArray(); |
| else { |
| elements = c.toArray(); |
| // defend against c.toArray (incorrectly) not returning Object[] |
| // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652) |
| if (elements.getClass() != Object[].class) |
| elements = Arrays.copyOf(elements, elements.length, Object[].class); |
| } |
| setArray(elements); |
| } |
| |
| /** |
| * Creates a list holding a copy of the given array. |
| * |
| * @param toCopyIn the array (a copy of this array is used as the |
| * internal array) |
| * @throws NullPointerException if the specified array is null |
| */ |
| public CopyOnWriteArrayList(E[] toCopyIn) { |
| setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class)); |
| } |
| |
| /** |
| * Returns the number of elements in this list. |
| * |
| * @return the number of elements in this list |
| */ |
| public int size() { |
| return getArray().length; |
| } |
| |
| /** |
| * Returns {@code true} if this list contains no elements. |
| * |
| * @return {@code true} if this list contains no elements |
| */ |
| public boolean isEmpty() { |
| return size() == 0; |
| } |
| |
| /** |
| * static version of indexOf, to allow repeated calls without |
| * needing to re-acquire array each time. |
| * @param o element to search for |
| * @param elements the array |
| * @param index first index to search |
| * @param fence one past last index to search |
| * @return index of element, or -1 if absent |
| */ |
| private static int indexOf(Object o, Object[] elements, |
| int index, int fence) { |
| if (o == null) { |
| for (int i = index; i < fence; i++) |
| if (elements[i] == null) |
| return i; |
| } else { |
| for (int i = index; i < fence; i++) |
| if (o.equals(elements[i])) |
| return i; |
| } |
| return -1; |
| } |
| |
| /** |
| * static version of lastIndexOf. |
| * @param o element to search for |
| * @param elements the array |
| * @param index first index to search |
| * @return index of element, or -1 if absent |
| */ |
| private static int lastIndexOf(Object o, Object[] elements, int index) { |
| if (o == null) { |
| for (int i = index; i >= 0; i--) |
| if (elements[i] == null) |
| return i; |
| } else { |
| for (int i = index; i >= 0; i--) |
| if (o.equals(elements[i])) |
| return i; |
| } |
| return -1; |
| } |
| |
| /** |
| * Returns {@code true} if this list contains the specified element. |
| * More formally, returns {@code true} if and only if this list contains |
| * at least one element {@code e} such that {@code Objects.equals(o, e)}. |
| * |
| * @param o element whose presence in this list is to be tested |
| * @return {@code true} if this list contains the specified element |
| */ |
| public boolean contains(Object o) { |
| Object[] elements = getArray(); |
| return indexOf(o, elements, 0, elements.length) >= 0; |
| } |
| |
| /** |
| * {@inheritDoc} |
| */ |
| public int indexOf(Object o) { |
| Object[] elements = getArray(); |
| return indexOf(o, elements, 0, elements.length); |
| } |
| |
| /** |
| * Returns the index of the first occurrence of the specified element in |
| * this list, searching forwards from {@code index}, or returns -1 if |
| * the element is not found. |
| * More formally, returns the lowest index {@code i} such that |
| * {@code i >= index && Objects.equals(get(i), e)}, |
| * or -1 if there is no such index. |
| * |
| * @param e element to search for |
| * @param index index to start searching from |
| * @return the index of the first occurrence of the element in |
| * this list at position {@code index} or later in the list; |
| * {@code -1} if the element is not found. |
| * @throws IndexOutOfBoundsException if the specified index is negative |
| */ |
| public int indexOf(E e, int index) { |
| Object[] elements = getArray(); |
| return indexOf(e, elements, index, elements.length); |
| } |
| |
| /** |
| * {@inheritDoc} |
| */ |
| public int lastIndexOf(Object o) { |
| Object[] elements = getArray(); |
| return lastIndexOf(o, elements, elements.length - 1); |
| } |
| |
| /** |
| * Returns the index of the last occurrence of the specified element in |
| * this list, searching backwards from {@code index}, or returns -1 if |
| * the element is not found. |
| * More formally, returns the highest index {@code i} such that |
| * {@code i <= index && Objects.equals(get(i), e)}, |
| * or -1 if there is no such index. |
| * |
| * @param e element to search for |
| * @param index index to start searching backwards from |
| * @return the index of the last occurrence of the element at position |
| * less than or equal to {@code index} in this list; |
| * -1 if the element is not found. |
| * @throws IndexOutOfBoundsException if the specified index is greater |
| * than or equal to the current size of this list |
| */ |
| public int lastIndexOf(E e, int index) { |
| Object[] elements = getArray(); |
| return lastIndexOf(e, elements, index); |
| } |
| |
| /** |
| * Returns a shallow copy of this list. (The elements themselves |
| * are not copied.) |
| * |
| * @return a clone of this list |
| */ |
| public Object clone() { |
| try { |
| @SuppressWarnings("unchecked") |
| CopyOnWriteArrayList<E> clone = |
| (CopyOnWriteArrayList<E>) super.clone(); |
| clone.resetLock(); |
| return clone; |
| } catch (CloneNotSupportedException e) { |
| // this shouldn't happen, since we are Cloneable |
| throw new InternalError(); |
| } |
| } |
| |
| /** |
| * Returns an array containing all of the elements in this list |
| * in proper sequence (from first to last element). |
| * |
| * <p>The returned array will be "safe" in that no references to it are |
| * maintained by this list. (In other words, this method must allocate |
| * a new array). The caller is thus free to modify the returned array. |
| * |
| * <p>This method acts as bridge between array-based and collection-based |
| * APIs. |
| * |
| * @return an array containing all the elements in this list |
| */ |
| public Object[] toArray() { |
| Object[] elements = getArray(); |
| return Arrays.copyOf(elements, elements.length); |
| } |
| |
| /** |
| * Returns an array containing all of the elements in this list in |
| * proper sequence (from first to last element); the runtime type of |
| * the returned array is that of the specified array. If the list fits |
| * in the specified array, it is returned therein. Otherwise, a new |
| * array is allocated with the runtime type of the specified array and |
| * the size of this list. |
| * |
| * <p>If this list fits in the specified array with room to spare |
| * (i.e., the array has more elements than this list), the element in |
| * the array immediately following the end of the list is set to |
| * {@code null}. (This is useful in determining the length of this |
| * list <i>only</i> if the caller knows that this list does not contain |
| * any null elements.) |
| * |
| * <p>Like the {@link #toArray()} method, this method acts as bridge between |
| * array-based and collection-based APIs. Further, this method allows |
| * precise control over the runtime type of the output array, and may, |
| * under certain circumstances, be used to save allocation costs. |
| * |
| * <p>Suppose {@code x} is a list known to contain only strings. |
| * The following code can be used to dump the list into a newly |
| * allocated array of {@code String}: |
| * |
| * <pre> {@code String[] y = x.toArray(new String[0]);}</pre> |
| * |
| * Note that {@code toArray(new Object[0])} is identical in function to |
| * {@code toArray()}. |
| * |
| * @param a the array into which the elements of the list are to |
| * be stored, if it is big enough; otherwise, a new array of the |
| * same runtime type is allocated for this purpose. |
| * @return an array containing all the elements in this list |
| * @throws ArrayStoreException if the runtime type of the specified array |
| * is not a supertype of the runtime type of every element in |
| * this list |
| * @throws NullPointerException if the specified array is null |
| */ |
| @SuppressWarnings("unchecked") |
| public <T> T[] toArray(T[] a) { |
| Object[] elements = getArray(); |
| int len = elements.length; |
| if (a.length < len) |
| return (T[]) Arrays.copyOf(elements, len, a.getClass()); |
| else { |
| System.arraycopy(elements, 0, a, 0, len); |
| if (a.length > len) |
| a[len] = null; |
| return a; |
| } |
| } |
| |
| // Positional Access Operations |
| |
| @SuppressWarnings("unchecked") |
| static <E> E elementAt(Object[] a, int index) { |
| return (E) a[index]; |
| } |
| |
| static String outOfBounds(int index, int size) { |
| return "Index: " + index + ", Size: " + size; |
| } |
| |
| /** |
| * {@inheritDoc} |
| * |
| * @throws IndexOutOfBoundsException {@inheritDoc} |
| */ |
| public E get(int index) { |
| return elementAt(getArray(), index); |
| } |
| |
| /** |
| * Replaces the element at the specified position in this list with the |
| * specified element. |
| * |
| * @throws IndexOutOfBoundsException {@inheritDoc} |
| */ |
| public E set(int index, E element) { |
| synchronized (lock) { |
| Object[] elements = getArray(); |
| E oldValue = elementAt(elements, index); |
| |
| if (oldValue != element) { |
| int len = elements.length; |
| Object[] newElements = Arrays.copyOf(elements, len); |
| newElements[index] = element; |
| setArray(newElements); |
| } else { |
| // Not quite a no-op; ensures volatile write semantics |
| setArray(elements); |
| } |
| return oldValue; |
| } |
| } |
| |
| /** |
| * Appends the specified element to the end of this list. |
| * |
| * @param e element to be appended to this list |
| * @return {@code true} (as specified by {@link Collection#add}) |
| */ |
| public boolean add(E e) { |
| synchronized (lock) { |
| Object[] elements = getArray(); |
| int len = elements.length; |
| Object[] newElements = Arrays.copyOf(elements, len + 1); |
| newElements[len] = e; |
| setArray(newElements); |
| return true; |
| } |
| } |
| |
| /** |
| * Inserts the specified element at the specified position in this |
| * list. Shifts the element currently at that position (if any) and |
| * any subsequent elements to the right (adds one to their indices). |
| * |
| * @throws IndexOutOfBoundsException {@inheritDoc} |
| */ |
| public void add(int index, E element) { |
| synchronized (lock) { |
| Object[] elements = getArray(); |
| int len = elements.length; |
| if (index > len || index < 0) |
| throw new IndexOutOfBoundsException(outOfBounds(index, len)); |
| Object[] newElements; |
| int numMoved = len - index; |
| if (numMoved == 0) |
| newElements = Arrays.copyOf(elements, len + 1); |
| else { |
| newElements = new Object[len + 1]; |
| System.arraycopy(elements, 0, newElements, 0, index); |
| System.arraycopy(elements, index, newElements, index + 1, |
| numMoved); |
| } |
| newElements[index] = element; |
| setArray(newElements); |
| } |
| } |
| |
| /** |
| * Removes the element at the specified position in this list. |
| * Shifts any subsequent elements to the left (subtracts one from their |
| * indices). Returns the element that was removed from the list. |
| * |
| * @throws IndexOutOfBoundsException {@inheritDoc} |
| */ |
| public E remove(int index) { |
| synchronized (lock) { |
| Object[] elements = getArray(); |
| int len = elements.length; |
| E oldValue = elementAt(elements, index); |
| int numMoved = len - index - 1; |
| if (numMoved == 0) |
| setArray(Arrays.copyOf(elements, len - 1)); |
| else { |
| Object[] newElements = new Object[len - 1]; |
| System.arraycopy(elements, 0, newElements, 0, index); |
| System.arraycopy(elements, index + 1, newElements, index, |
| numMoved); |
| setArray(newElements); |
| } |
| return oldValue; |
| } |
| } |
| |
| /** |
| * Removes the first occurrence of the specified element from this list, |
| * if it is present. If this list does not contain the element, it is |
| * unchanged. More formally, removes the element with the lowest index |
| * {@code i} such that {@code Objects.equals(o, get(i))} |
| * (if such an element exists). Returns {@code true} if this list |
| * contained the specified element (or equivalently, if this list |
| * changed as a result of the call). |
| * |
| * @param o element to be removed from this list, if present |
| * @return {@code true} if this list contained the specified element |
| */ |
| public boolean remove(Object o) { |
| Object[] snapshot = getArray(); |
| int index = indexOf(o, snapshot, 0, snapshot.length); |
| return (index < 0) ? false : remove(o, snapshot, index); |
| } |
| |
| /** |
| * A version of remove(Object) using the strong hint that given |
| * recent snapshot contains o at the given index. |
| */ |
| private boolean remove(Object o, Object[] snapshot, int index) { |
| synchronized (lock) { |
| Object[] current = getArray(); |
| int len = current.length; |
| if (snapshot != current) findIndex: { |
| int prefix = Math.min(index, len); |
| for (int i = 0; i < prefix; i++) { |
| if (current[i] != snapshot[i] |
| && Objects.equals(o, current[i])) { |
| index = i; |
| break findIndex; |
| } |
| } |
| if (index >= len) |
| return false; |
| if (current[index] == o) |
| break findIndex; |
| index = indexOf(o, current, index, len); |
| if (index < 0) |
| return false; |
| } |
| Object[] newElements = new Object[len - 1]; |
| System.arraycopy(current, 0, newElements, 0, index); |
| System.arraycopy(current, index + 1, |
| newElements, index, |
| len - index - 1); |
| setArray(newElements); |
| return true; |
| } |
| } |
| |
| /** |
| * Removes from this list all of the elements whose index is between |
| * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. |
| * Shifts any succeeding elements to the left (reduces their index). |
| * This call shortens the list by {@code (toIndex - fromIndex)} elements. |
| * (If {@code toIndex==fromIndex}, this operation has no effect.) |
| * |
| * @param fromIndex index of first element to be removed |
| * @param toIndex index after last element to be removed |
| * @throws IndexOutOfBoundsException if fromIndex or toIndex out of range |
| * ({@code fromIndex < 0 || toIndex > size() || toIndex < fromIndex}) |
| */ |
| void removeRange(int fromIndex, int toIndex) { |
| synchronized (lock) { |
| Object[] elements = getArray(); |
| int len = elements.length; |
| |
| if (fromIndex < 0 || toIndex > len || toIndex < fromIndex) |
| throw new IndexOutOfBoundsException(); |
| int newlen = len - (toIndex - fromIndex); |
| int numMoved = len - toIndex; |
| if (numMoved == 0) |
| setArray(Arrays.copyOf(elements, newlen)); |
| else { |
| Object[] newElements = new Object[newlen]; |
| System.arraycopy(elements, 0, newElements, 0, fromIndex); |
| System.arraycopy(elements, toIndex, newElements, |
| fromIndex, numMoved); |
| setArray(newElements); |
| } |
| } |
| } |
| |
| /** |
| * Appends the element, if not present. |
| * |
| * @param e element to be added to this list, if absent |
| * @return {@code true} if the element was added |
| */ |
| public boolean addIfAbsent(E e) { |
| Object[] snapshot = getArray(); |
| return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false : |
| addIfAbsent(e, snapshot); |
| } |
| |
| /** |
| * A version of addIfAbsent using the strong hint that given |
| * recent snapshot does not contain e. |
| */ |
| private boolean addIfAbsent(E e, Object[] snapshot) { |
| synchronized (lock) { |
| Object[] current = getArray(); |
| int len = current.length; |
| if (snapshot != current) { |
| // Optimize for lost race to another addXXX operation |
| int common = Math.min(snapshot.length, len); |
| for (int i = 0; i < common; i++) |
| if (current[i] != snapshot[i] |
| && Objects.equals(e, current[i])) |
| return false; |
| if (indexOf(e, current, common, len) >= 0) |
| return false; |
| } |
| Object[] newElements = Arrays.copyOf(current, len + 1); |
| newElements[len] = e; |
| setArray(newElements); |
| return true; |
| } |
| } |
| |
| /** |
| * Returns {@code true} if this list contains all of the elements of the |
| * specified collection. |
| * |
| * @param c collection to be checked for containment in this list |
| * @return {@code true} if this list contains all of the elements of the |
| * specified collection |
| * @throws NullPointerException if the specified collection is null |
| * @see #contains(Object) |
| */ |
| public boolean containsAll(Collection<?> c) { |
| Object[] elements = getArray(); |
| int len = elements.length; |
| for (Object e : c) { |
| if (indexOf(e, elements, 0, len) < 0) |
| return false; |
| } |
| return true; |
| } |
| |
| /** |
| * Removes from this list all of its elements that are contained in |
| * the specified collection. This is a particularly expensive operation |
| * in this class because of the need for an internal temporary array. |
| * |
| * @param c collection containing elements to be removed from this list |
| * @return {@code true} if this list changed as a result of the call |
| * @throws ClassCastException if the class of an element of this list |
| * is incompatible with the specified collection |
| * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>) |
| * @throws NullPointerException if this list contains a null element and the |
| * specified collection does not permit null elements |
| * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>), |
| * or if the specified collection is null |
| * @see #remove(Object) |
| */ |
| public boolean removeAll(Collection<?> c) { |
| Objects.requireNonNull(c); |
| return bulkRemove(e -> c.contains(e)); |
| } |
| |
| /** |
| * Retains only the elements in this list that are contained in the |
| * specified collection. In other words, removes from this list all of |
| * its elements that are not contained in the specified collection. |
| * |
| * @param c collection containing elements to be retained in this list |
| * @return {@code true} if this list changed as a result of the call |
| * @throws ClassCastException if the class of an element of this list |
| * is incompatible with the specified collection |
| * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>) |
| * @throws NullPointerException if this list contains a null element and the |
| * specified collection does not permit null elements |
| * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>), |
| * or if the specified collection is null |
| * @see #remove(Object) |
| */ |
| public boolean retainAll(Collection<?> c) { |
| Objects.requireNonNull(c); |
| return bulkRemove(e -> !c.contains(e)); |
| } |
| |
| /** |
| * Appends all of the elements in the specified collection that |
| * are not already contained in this list, to the end of |
| * this list, in the order that they are returned by the |
| * specified collection's iterator. |
| * |
| * @param c collection containing elements to be added to this list |
| * @return the number of elements added |
| * @throws NullPointerException if the specified collection is null |
| * @see #addIfAbsent(Object) |
| */ |
| public int addAllAbsent(Collection<? extends E> c) { |
| Object[] cs = c.toArray(); |
| if (cs.length == 0) |
| return 0; |
| synchronized (lock) { |
| Object[] elements = getArray(); |
| int len = elements.length; |
| int added = 0; |
| // uniquify and compact elements in cs |
| for (int i = 0; i < cs.length; ++i) { |
| Object e = cs[i]; |
| if (indexOf(e, elements, 0, len) < 0 && |
| indexOf(e, cs, 0, added) < 0) |
| cs[added++] = e; |
| } |
| if (added > 0) { |
| Object[] newElements = Arrays.copyOf(elements, len + added); |
| System.arraycopy(cs, 0, newElements, len, added); |
| setArray(newElements); |
| } |
| return added; |
| } |
| } |
| |
| /** |
| * Removes all of the elements from this list. |
| * The list will be empty after this call returns. |
| */ |
| public void clear() { |
| synchronized (lock) { |
| setArray(new Object[0]); |
| } |
| } |
| |
| /** |
| * Appends all of the elements in the specified collection to the end |
| * of this list, in the order that they are returned by the specified |
| * collection's iterator. |
| * |
| * @param c collection containing elements to be added to this list |
| * @return {@code true} if this list changed as a result of the call |
| * @throws NullPointerException if the specified collection is null |
| * @see #add(Object) |
| */ |
| public boolean addAll(Collection<? extends E> c) { |
| Object[] cs = (c.getClass() == CopyOnWriteArrayList.class) ? |
| ((CopyOnWriteArrayList<?>)c).getArray() : c.toArray(); |
| if (cs.length == 0) |
| return false; |
| synchronized (lock) { |
| Object[] elements = getArray(); |
| int len = elements.length; |
| if (len == 0 && cs.getClass() == Object[].class) |
| setArray(cs); |
| else { |
| Object[] newElements = Arrays.copyOf(elements, len + cs.length); |
| System.arraycopy(cs, 0, newElements, len, cs.length); |
| setArray(newElements); |
| } |
| return true; |
| } |
| } |
| |
| /** |
| * Inserts all of the elements in the specified collection into this |
| * list, starting at the specified position. Shifts the element |
| * currently at that position (if any) and any subsequent elements to |
| * the right (increases their indices). The new elements will appear |
| * in this list in the order that they are returned by the |
| * specified collection's iterator. |
| * |
| * @param index index at which to insert the first element |
| * from the specified collection |
| * @param c collection containing elements to be added to this list |
| * @return {@code true} if this list changed as a result of the call |
| * @throws IndexOutOfBoundsException {@inheritDoc} |
| * @throws NullPointerException if the specified collection is null |
| * @see #add(int,Object) |
| */ |
| public boolean addAll(int index, Collection<? extends E> c) { |
| Object[] cs = c.toArray(); |
| synchronized (lock) { |
| Object[] elements = getArray(); |
| int len = elements.length; |
| if (index > len || index < 0) |
| throw new IndexOutOfBoundsException(outOfBounds(index, len)); |
| if (cs.length == 0) |
| return false; |
| int numMoved = len - index; |
| Object[] newElements; |
| if (numMoved == 0) |
| newElements = Arrays.copyOf(elements, len + cs.length); |
| else { |
| newElements = new Object[len + cs.length]; |
| System.arraycopy(elements, 0, newElements, 0, index); |
| System.arraycopy(elements, index, |
| newElements, index + cs.length, |
| numMoved); |
| } |
| System.arraycopy(cs, 0, newElements, index, cs.length); |
| setArray(newElements); |
| return true; |
| } |
| } |
| |
| /** |
| * @throws NullPointerException {@inheritDoc} |
| */ |
| public void forEach(Consumer<? super E> action) { |
| Objects.requireNonNull(action); |
| for (Object x : getArray()) { |
| @SuppressWarnings("unchecked") E e = (E) x; |
| action.accept(e); |
| } |
| } |
| |
| /** |
| * @throws NullPointerException {@inheritDoc} |
| */ |
| public boolean removeIf(Predicate<? super E> filter) { |
| Objects.requireNonNull(filter); |
| return bulkRemove(filter); |
| } |
| |
| // A tiny bit set implementation |
| |
| private static long[] nBits(int n) { |
| return new long[((n - 1) >> 6) + 1]; |
| } |
| private static void setBit(long[] bits, int i) { |
| bits[i >> 6] |= 1L << i; |
| } |
| private static boolean isClear(long[] bits, int i) { |
| return (bits[i >> 6] & (1L << i)) == 0; |
| } |
| |
| private boolean bulkRemove(Predicate<? super E> filter) { |
| synchronized (lock) { |
| return bulkRemove(filter, 0, getArray().length); |
| } |
| } |
| |
| boolean bulkRemove(Predicate<? super E> filter, int i, int end) { |
| // assert Thread.holdsLock(lock); |
| final Object[] es = getArray(); |
| // Optimize for initial run of survivors |
| for (; i < end && !filter.test(elementAt(es, i)); i++) |
| ; |
| if (i < end) { |
| final int beg = i; |
| final long[] deathRow = nBits(end - beg); |
| int deleted = 1; |
| deathRow[0] = 1L; // set bit 0 |
| for (i = beg + 1; i < end; i++) |
| if (filter.test(elementAt(es, i))) { |
| setBit(deathRow, i - beg); |
| deleted++; |
| } |
| // Did filter reentrantly modify the list? |
| if (es != getArray()) |
| throw new ConcurrentModificationException(); |
| final Object[] newElts = Arrays.copyOf(es, es.length - deleted); |
| int w = beg; |
| for (i = beg; i < end; i++) |
| if (isClear(deathRow, i - beg)) |
| newElts[w++] = es[i]; |
| System.arraycopy(es, i, newElts, w, es.length - i); |
| setArray(newElts); |
| return true; |
| } else { |
| if (es != getArray()) |
| throw new ConcurrentModificationException(); |
| return false; |
| } |
| } |
| |
| public void replaceAll(UnaryOperator<E> operator) { |
| Objects.requireNonNull(operator); |
| synchronized (lock) { |
| replaceAll(operator, 0, getArray().length); |
| } |
| } |
| |
| void replaceAll(UnaryOperator<E> operator, int i, int end) { |
| // assert Thread.holdsLock(lock); |
| final Object[] es = getArray().clone(); |
| for (; i < end; i++) |
| es[i] = operator.apply(elementAt(es, i)); |
| setArray(es); |
| } |
| |
| public void sort(Comparator<? super E> c) { |
| synchronized (lock) { |
| sort(c, 0, getArray().length); |
| } |
| } |
| |
| @SuppressWarnings("unchecked") |
| void sort(Comparator<? super E> c, int i, int end) { |
| // assert Thread.holdsLock(lock); |
| final Object[] es = getArray().clone(); |
| Arrays.sort(es, i, end, (Comparator<Object>)c); |
| setArray(es); |
| } |
| |
| /** |
| * Saves this list to a stream (that is, serializes it). |
| * |
| * @param s the stream |
| * @throws java.io.IOException if an I/O error occurs |
| * @serialData The length of the array backing the list is emitted |
| * (int), followed by all of its elements (each an Object) |
| * in the proper order. |
| */ |
| private void writeObject(java.io.ObjectOutputStream s) |
| throws java.io.IOException { |
| |
| s.defaultWriteObject(); |
| |
| Object[] elements = getArray(); |
| // Write out array length |
| s.writeInt(elements.length); |
| |
| // Write out all elements in the proper order. |
| for (Object element : elements) |
| s.writeObject(element); |
| } |
| |
| /** |
| * Reconstitutes this list from a stream (that is, deserializes it). |
| * @param s the stream |
| * @throws ClassNotFoundException if the class of a serialized object |
| * could not be found |
| * @throws java.io.IOException if an I/O error occurs |
| */ |
| private void readObject(java.io.ObjectInputStream s) |
| throws java.io.IOException, ClassNotFoundException { |
| |
| s.defaultReadObject(); |
| |
| // bind to new lock |
| resetLock(); |
| |
| // Read in array length and allocate array |
| int len = s.readInt(); |
| Object[] elements = new Object[len]; |
| |
| // Read in all elements in the proper order. |
| for (int i = 0; i < len; i++) |
| elements[i] = s.readObject(); |
| setArray(elements); |
| } |
| |
| /** |
| * Returns a string representation of this list. The string |
| * representation consists of the string representations of the list's |
| * elements in the order they are returned by its iterator, enclosed in |
| * square brackets ({@code "[]"}). Adjacent elements are separated by |
| * the characters {@code ", "} (comma and space). Elements are |
| * converted to strings as by {@link String#valueOf(Object)}. |
| * |
| * @return a string representation of this list |
| */ |
| public String toString() { |
| return Arrays.toString(getArray()); |
| } |
| |
| /** |
| * Compares the specified object with this list for equality. |
| * Returns {@code true} if the specified object is the same object |
| * as this object, or if it is also a {@link List} and the sequence |
| * of elements returned by an {@linkplain List#iterator() iterator} |
| * over the specified list is the same as the sequence returned by |
| * an iterator over this list. The two sequences are considered to |
| * be the same if they have the same length and corresponding |
| * elements at the same position in the sequence are <em>equal</em>. |
| * Two elements {@code e1} and {@code e2} are considered |
| * <em>equal</em> if {@code Objects.equals(e1, e2)}. |
| * |
| * @param o the object to be compared for equality with this list |
| * @return {@code true} if the specified object is equal to this list |
| */ |
| public boolean equals(Object o) { |
| if (o == this) |
| return true; |
| if (!(o instanceof List)) |
| return false; |
| |
| List<?> list = (List<?>)o; |
| Iterator<?> it = list.iterator(); |
| Object[] elements = getArray(); |
| for (int i = 0, len = elements.length; i < len; i++) |
| if (!it.hasNext() || !Objects.equals(elements[i], it.next())) |
| return false; |
| if (it.hasNext()) |
| return false; |
| return true; |
| } |
| |
| /** |
| * Returns the hash code value for this list. |
| * |
| * <p>This implementation uses the definition in {@link List#hashCode}. |
| * |
| * @return the hash code value for this list |
| */ |
| public int hashCode() { |
| int hashCode = 1; |
| for (Object x : getArray()) |
| hashCode = 31 * hashCode + (x == null ? 0 : x.hashCode()); |
| return hashCode; |
| } |
| |
| /** |
| * Returns an iterator over the elements in this list in proper sequence. |
| * |
| * <p>The returned iterator provides a snapshot of the state of the list |
| * when the iterator was constructed. No synchronization is needed while |
| * traversing the iterator. The iterator does <em>NOT</em> support the |
| * {@code remove} method. |
| * |
| * @return an iterator over the elements in this list in proper sequence |
| */ |
| public Iterator<E> iterator() { |
| return new COWIterator<E>(getArray(), 0); |
| } |
| |
| /** |
| * {@inheritDoc} |
| * |
| * <p>The returned iterator provides a snapshot of the state of the list |
| * when the iterator was constructed. No synchronization is needed while |
| * traversing the iterator. The iterator does <em>NOT</em> support the |
| * {@code remove}, {@code set} or {@code add} methods. |
| */ |
| public ListIterator<E> listIterator() { |
| return new COWIterator<E>(getArray(), 0); |
| } |
| |
| /** |
| * {@inheritDoc} |
| * |
| * <p>The returned iterator provides a snapshot of the state of the list |
| * when the iterator was constructed. No synchronization is needed while |
| * traversing the iterator. The iterator does <em>NOT</em> support the |
| * {@code remove}, {@code set} or {@code add} methods. |
| * |
| * @throws IndexOutOfBoundsException {@inheritDoc} |
| */ |
| public ListIterator<E> listIterator(int index) { |
| Object[] elements = getArray(); |
| int len = elements.length; |
| if (index < 0 || index > len) |
| throw new IndexOutOfBoundsException(outOfBounds(index, len)); |
| |
| return new COWIterator<E>(elements, index); |
| } |
| |
| /** |
| * Returns a {@link Spliterator} over the elements in this list. |
| * |
| * <p>The {@code Spliterator} reports {@link Spliterator#IMMUTABLE}, |
| * {@link Spliterator#ORDERED}, {@link Spliterator#SIZED}, and |
| * {@link Spliterator#SUBSIZED}. |
| * |
| * <p>The spliterator provides a snapshot of the state of the list |
| * when the spliterator was constructed. No synchronization is needed while |
| * operating on the spliterator. |
| * |
| * @return a {@code Spliterator} over the elements in this list |
| * @since 1.8 |
| */ |
| public Spliterator<E> spliterator() { |
| return Spliterators.spliterator |
| (getArray(), Spliterator.IMMUTABLE | Spliterator.ORDERED); |
| } |
| |
| static final class COWIterator<E> implements ListIterator<E> { |
| /** Snapshot of the array */ |
| private final Object[] snapshot; |
| /** Index of element to be returned by subsequent call to next. */ |
| private int cursor; |
| |
| COWIterator(Object[] elements, int initialCursor) { |
| cursor = initialCursor; |
| snapshot = elements; |
| } |
| |
| public boolean hasNext() { |
| return cursor < snapshot.length; |
| } |
| |
| public boolean hasPrevious() { |
| return cursor > 0; |
| } |
| |
| @SuppressWarnings("unchecked") |
| public E next() { |
| if (! hasNext()) |
| throw new NoSuchElementException(); |
| return (E) snapshot[cursor++]; |
| } |
| |
| @SuppressWarnings("unchecked") |
| public E previous() { |
| if (! hasPrevious()) |
| throw new NoSuchElementException(); |
| return (E) snapshot[--cursor]; |
| } |
| |
| public int nextIndex() { |
| return cursor; |
| } |
| |
| public int previousIndex() { |
| return cursor-1; |
| } |
| |
| /** |
| * Not supported. Always throws UnsupportedOperationException. |
| * @throws UnsupportedOperationException always; {@code remove} |
| * is not supported by this iterator. |
| */ |
| public void remove() { |
| throw new UnsupportedOperationException(); |
| } |
| |
| /** |
| * Not supported. Always throws UnsupportedOperationException. |
| * @throws UnsupportedOperationException always; {@code set} |
| * is not supported by this iterator. |
| */ |
| public void set(E e) { |
| throw new UnsupportedOperationException(); |
| } |
| |
| /** |
| * Not supported. Always throws UnsupportedOperationException. |
| * @throws UnsupportedOperationException always; {@code add} |
| * is not supported by this iterator. |
| */ |
| public void add(E e) { |
| throw new UnsupportedOperationException(); |
| } |
| |
| @Override |
| @SuppressWarnings("unchecked") |
| public void forEachRemaining(Consumer<? super E> action) { |
| Objects.requireNonNull(action); |
| final int size = snapshot.length; |
| for (int i = cursor; i < size; i++) { |
| action.accept((E) snapshot[i]); |
| } |
| cursor = size; |
| } |
| } |
| |
| /** |
| * Returns a view of the portion of this list between |
| * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. |
| * The returned list is backed by this list, so changes in the |
| * returned list are reflected in this list. |
| * |
| * <p>The semantics of the list returned by this method become |
| * undefined if the backing list (i.e., this list) is modified in |
| * any way other than via the returned list. |
| * |
| * @param fromIndex low endpoint (inclusive) of the subList |
| * @param toIndex high endpoint (exclusive) of the subList |
| * @return a view of the specified range within this list |
| * @throws IndexOutOfBoundsException {@inheritDoc} |
| */ |
| public List<E> subList(int fromIndex, int toIndex) { |
| synchronized (lock) { |
| Object[] elements = getArray(); |
| int len = elements.length; |
| if (fromIndex < 0 || toIndex > len || fromIndex > toIndex) |
| throw new IndexOutOfBoundsException(); |
| return new COWSubList<E>(this, fromIndex, toIndex); |
| } |
| } |
| |
| /** |
| * Sublist for CopyOnWriteArrayList. |
| */ |
| private static class COWSubList<E> |
| extends AbstractList<E> |
| implements RandomAccess |
| { |
| private final CopyOnWriteArrayList<E> l; |
| private final int offset; |
| private int size; |
| private Object[] expectedArray; |
| |
| // only call this holding l's lock |
| COWSubList(CopyOnWriteArrayList<E> list, |
| int fromIndex, int toIndex) { |
| // assert Thread.holdsLock(list.lock); |
| l = list; |
| expectedArray = l.getArray(); |
| offset = fromIndex; |
| size = toIndex - fromIndex; |
| } |
| |
| // only call this holding l's lock |
| private void checkForComodification() { |
| // assert Thread.holdsLock(l.lock); |
| if (l.getArray() != expectedArray) |
| throw new ConcurrentModificationException(); |
| } |
| |
| private Object[] getArrayChecked() { |
| // assert Thread.holdsLock(l.lock); |
| Object[] a = l.getArray(); |
| if (a != expectedArray) |
| throw new ConcurrentModificationException(); |
| return a; |
| } |
| |
| // only call this holding l's lock |
| private void rangeCheck(int index) { |
| // assert Thread.holdsLock(l.lock); |
| if (index < 0 || index >= size) |
| throw new IndexOutOfBoundsException(outOfBounds(index, size)); |
| } |
| |
| public E set(int index, E element) { |
| synchronized (l.lock) { |
| rangeCheck(index); |
| checkForComodification(); |
| E x = l.set(offset + index, element); |
| expectedArray = l.getArray(); |
| return x; |
| } |
| } |
| |
| public E get(int index) { |
| synchronized (l.lock) { |
| rangeCheck(index); |
| checkForComodification(); |
| return l.get(offset + index); |
| } |
| } |
| |
| public int size() { |
| synchronized (l.lock) { |
| checkForComodification(); |
| return size; |
| } |
| } |
| |
| public boolean add(E element) { |
| synchronized (l.lock) { |
| checkForComodification(); |
| l.add(offset + size, element); |
| expectedArray = l.getArray(); |
| size++; |
| } |
| return true; |
| } |
| |
| public void add(int index, E element) { |
| synchronized (l.lock) { |
| checkForComodification(); |
| if (index < 0 || index > size) |
| throw new IndexOutOfBoundsException |
| (outOfBounds(index, size)); |
| l.add(offset + index, element); |
| expectedArray = l.getArray(); |
| size++; |
| } |
| } |
| |
| public boolean addAll(Collection<? extends E> c) { |
| synchronized (l.lock) { |
| final Object[] oldArray = getArrayChecked(); |
| boolean modified = l.addAll(offset + size, c); |
| size += (expectedArray = l.getArray()).length - oldArray.length; |
| return modified; |
| } |
| } |
| |
| public void clear() { |
| synchronized (l.lock) { |
| checkForComodification(); |
| l.removeRange(offset, offset + size); |
| expectedArray = l.getArray(); |
| size = 0; |
| } |
| } |
| |
| public E remove(int index) { |
| synchronized (l.lock) { |
| rangeCheck(index); |
| checkForComodification(); |
| E result = l.remove(offset + index); |
| expectedArray = l.getArray(); |
| size--; |
| return result; |
| } |
| } |
| |
| public boolean remove(Object o) { |
| synchronized (l.lock) { |
| checkForComodification(); |
| int index = indexOf(o); |
| if (index == -1) |
| return false; |
| remove(index); |
| return true; |
| } |
| } |
| |
| public Iterator<E> iterator() { |
| synchronized (l.lock) { |
| checkForComodification(); |
| return new COWSubListIterator<E>(l, 0, offset, size); |
| } |
| } |
| |
| public ListIterator<E> listIterator(int index) { |
| synchronized (l.lock) { |
| checkForComodification(); |
| if (index < 0 || index > size) |
| throw new IndexOutOfBoundsException |
| (outOfBounds(index, size)); |
| return new COWSubListIterator<E>(l, index, offset, size); |
| } |
| } |
| |
| public List<E> subList(int fromIndex, int toIndex) { |
| synchronized (l.lock) { |
| checkForComodification(); |
| if (fromIndex < 0 || toIndex > size || fromIndex > toIndex) |
| throw new IndexOutOfBoundsException(); |
| return new COWSubList<E>(l, fromIndex + offset, |
| toIndex + offset); |
| } |
| } |
| |
| public void forEach(Consumer<? super E> action) { |
| Objects.requireNonNull(action); |
| int i, end; final Object[] es; |
| synchronized (l.lock) { |
| es = getArrayChecked(); |
| i = offset; |
| end = i + size; |
| } |
| for (; i < end; i++) |
| action.accept(elementAt(es, i)); |
| } |
| |
| public void replaceAll(UnaryOperator<E> operator) { |
| Objects.requireNonNull(operator); |
| synchronized (l.lock) { |
| checkForComodification(); |
| l.replaceAll(operator, offset, offset + size); |
| expectedArray = l.getArray(); |
| } |
| } |
| |
| public void sort(Comparator<? super E> c) { |
| synchronized (l.lock) { |
| checkForComodification(); |
| l.sort(c, offset, offset + size); |
| expectedArray = l.getArray(); |
| } |
| } |
| |
| public boolean removeAll(Collection<?> c) { |
| Objects.requireNonNull(c); |
| return bulkRemove(e -> c.contains(e)); |
| } |
| |
| public boolean retainAll(Collection<?> c) { |
| Objects.requireNonNull(c); |
| return bulkRemove(e -> !c.contains(e)); |
| } |
| |
| public boolean removeIf(Predicate<? super E> filter) { |
| Objects.requireNonNull(filter); |
| return bulkRemove(filter); |
| } |
| |
| private boolean bulkRemove(Predicate<? super E> filter) { |
| synchronized (l.lock) { |
| final Object[] oldArray = getArrayChecked(); |
| boolean modified = l.bulkRemove(filter, offset, offset + size); |
| size += (expectedArray = l.getArray()).length - oldArray.length; |
| return modified; |
| } |
| } |
| |
| public Spliterator<E> spliterator() { |
| synchronized (l.lock) { |
| return Spliterators.spliterator( |
| getArrayChecked(), offset, offset + size, |
| Spliterator.IMMUTABLE | Spliterator.ORDERED); |
| } |
| } |
| |
| } |
| |
| private static class COWSubListIterator<E> implements ListIterator<E> { |
| private final ListIterator<E> it; |
| private final int offset; |
| private final int size; |
| |
| COWSubListIterator(List<E> l, int index, int offset, int size) { |
| this.offset = offset; |
| this.size = size; |
| it = l.listIterator(index+offset); |
| } |
| |
| public boolean hasNext() { |
| return nextIndex() < size; |
| } |
| |
| public E next() { |
| if (hasNext()) |
| return it.next(); |
| else |
| throw new NoSuchElementException(); |
| } |
| |
| public boolean hasPrevious() { |
| return previousIndex() >= 0; |
| } |
| |
| public E previous() { |
| if (hasPrevious()) |
| return it.previous(); |
| else |
| throw new NoSuchElementException(); |
| } |
| |
| public int nextIndex() { |
| return it.nextIndex() - offset; |
| } |
| |
| public int previousIndex() { |
| return it.previousIndex() - offset; |
| } |
| |
| public void remove() { |
| throw new UnsupportedOperationException(); |
| } |
| |
| public void set(E e) { |
| throw new UnsupportedOperationException(); |
| } |
| |
| public void add(E e) { |
| throw new UnsupportedOperationException(); |
| } |
| |
| @Override |
| @SuppressWarnings("unchecked") |
| public void forEachRemaining(Consumer<? super E> action) { |
| Objects.requireNonNull(action); |
| while (nextIndex() < size) { |
| action.accept(it.next()); |
| } |
| } |
| } |
| |
| /** Initializes the lock; for use when deserializing or cloning. */ |
| private void resetLock() { |
| Field lockField = java.security.AccessController.doPrivileged( |
| (java.security.PrivilegedAction<Field>) () -> { |
| try { |
| Field f = CopyOnWriteArrayList.class |
| .getDeclaredField("lock"); |
| f.setAccessible(true); |
| return f; |
| } catch (ReflectiveOperationException e) { |
| throw new Error(e); |
| }}); |
| try { |
| lockField.set(this, new Object()); |
| } catch (IllegalAccessException e) { |
| throw new Error(e); |
| } |
| } |
| } |
