Revert to android-specific CopyOnWriteArrayList
Bug: 27426599
Change-Id: Ibc4682a5d296d51f94494385aa2b0149e618a98b
diff --git a/luni/src/main/java/java/util/concurrent/CopyOnWriteArrayList.java b/luni/src/main/java/java/util/concurrent/CopyOnWriteArrayList.java
index c8e342e..798eaaf 100644
--- a/luni/src/main/java/java/util/concurrent/CopyOnWriteArrayList.java
+++ b/luni/src/main/java/java/util/concurrent/CopyOnWriteArrayList.java
@@ -1,1542 +1,783 @@
/*
- * 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 (C) 2010 The Android Open Source Project
*
- * Copyright 1997 by Sun Microsystems, Inc.,
- * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
- * All rights reserved.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
*
- * This software is the confidential and proprietary information
- * of Sun Microsystems, Inc. ("Confidential Information"). You
- * shall not disclose such Confidential Information and shall use
- * it only in accordance with the terms of the license agreement
- * you entered into with Sun.
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
*/
package java.util.concurrent;
-
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.Serializable;
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;
-import libcore.util.EmptyArray;
-// BEGIN android-note
-// removed link to collections framework docs from header
-// END android-note
+import libcore.util.EmptyArray;
+import libcore.util.Objects;
/**
- * 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.
+ * A thread-safe random-access list.
*
- * <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>Read operations (including {@link #get}) do not block and may overlap with
+ * update operations. Reads reflect the results of the most recently completed
+ * operations. Aggregate operations like {@link #addAll} and {@link #clear} are
+ * atomic; they never expose an intermediate state.
*
- * <p>All elements are permitted, including {@code null}.
+ * <p>Iterators of this list never throw {@link
+ * ConcurrentModificationException}. When an iterator is created, it keeps a
+ * copy of the list's contents. It is always safe to iterate this list, but
+ * iterations may not reflect the latest state of the list.
*
- * <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>Iterators returned by this list and its sub lists cannot modify the
+ * underlying list. In particular, {@link Iterator#remove}, {@link
+ * ListIterator#add} and {@link ListIterator#set} all throw {@link
+ * UnsupportedOperationException}.
*
- * @since 1.5
- * @author Doug Lea
- * @param <E> the type of elements held in this list
+ * <p>This class offers extended API beyond the {@link List} interface. It
+ * includes additional overloads for indexed search ({@link #indexOf} and {@link
+ * #lastIndexOf}) and methods for conditional adds ({@link #addIfAbsent} and
+ * {@link #addAllAbsent}).
*/
-public class CopyOnWriteArrayList<E>
- implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
+public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, 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.)
+ * Holds the latest snapshot of the list's data. This field is volatile so
+ * that data can be read without synchronization. As a consequence, all
+ * writes to this field must be atomic; it is an error to modify the
+ * contents of an array after it has been assigned to this field.
+ *
+ * Synchronization is required by all update operations. This defends
+ * against one update clobbering the result of another operation. For
+ * example, 100 threads simultaneously calling add() will grow the list's
+ * size by 100 when they have completed. No update operations are lost!
+ *
+ * Maintainers should be careful to read this field only once in
+ * non-blocking read methods. Write methods must be synchronized to avoid
+ * clobbering concurrent writes.
*/
- final transient Object lock = new Object();
-
- /** The array, accessed only via getArray/setArray. */
- private transient volatile Object[] array;
+ private transient volatile Object[] elements;
/**
- * 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.
+ * Creates a new empty instance.
*/
public CopyOnWriteArrayList() {
- setArray(new Object[0]);
+ elements = EmptyArray.OBJECT;
}
/**
- * 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
+ * Creates a new instance containing the elements of {@code collection}.
*/
- 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);
+ @SuppressWarnings("unchecked")
+ public CopyOnWriteArrayList(Collection<? extends E> collection) {
+ this((E[]) collection.toArray());
}
/**
- * 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
+ * Creates a new instance containing the elements of {@code array}.
*/
- public CopyOnWriteArrayList(E[] toCopyIn) {
- setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
+ public CopyOnWriteArrayList(E[] array) {
+ this.elements = Arrays.copyOf(array, array.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() {
+ @Override public Object clone() {
try {
- @SuppressWarnings("unchecked")
- CopyOnWriteArrayList<E> clone =
- (CopyOnWriteArrayList<E>) super.clone();
- clone.resetLock();
- return clone;
+ CopyOnWriteArrayList result = (CopyOnWriteArrayList) super.clone();
+ result.elements = result.elements.clone();
+ return result;
} catch (CloneNotSupportedException e) {
- // this shouldn't happen, since we are Cloneable
- throw new InternalError();
+ throw new AssertionError(e);
}
}
- /**
- * 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);
+ public int size() {
+ return 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")
- private E get(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 get(getArray(), index);
+ return (E) elements[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 = get(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;
- }
+ public boolean contains(Object o) {
+ return indexOf(o) != -1;
}
- /**
- * 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;
- }
+ public boolean containsAll(Collection<?> collection) {
+ Object[] snapshot = elements;
+ return containsAll(collection, snapshot, 0, snapshot.length);
}
- /**
- * 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 = get(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)
+ static boolean containsAll(Collection<?> collection, Object[] snapshot, int from, int to) {
+ for (Object o : collection) {
+ if (indexOf(o, snapshot, from, to) == -1) {
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.
+ * Searches this list for {@code object} and returns the index of the first
+ * occurrence that is at or after {@code from}.
*
- * @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}/../api/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}/../api/java/util/Collection.html#optional-restrictions">optional</a>),
- * or if the specified collection is null
- * @see #remove(Object)
+ * @return the index or -1 if the object was not found.
*/
- public boolean removeAll(Collection<?> c) {
- if (c == null) throw new NullPointerException();
- synchronized (lock) {
- Object[] elements = getArray();
- int len = elements.length;
- if (len != 0) {
- // temp array holds those elements we know we want to keep
- int newlen = 0;
- Object[] temp = new Object[len];
- for (int i = 0; i < len; ++i) {
- Object element = elements[i];
- if (!c.contains(element))
- temp[newlen++] = element;
- }
- if (newlen != len) {
- setArray(Arrays.copyOf(temp, newlen));
- return true;
- }
- }
- return false;
- }
+ public int indexOf(E object, int from) {
+ Object[] snapshot = elements;
+ return indexOf(object, snapshot, from, snapshot.length);
+ }
+
+ public int indexOf(Object object) {
+ Object[] snapshot = elements;
+ return indexOf(object, snapshot, 0, snapshot.length);
}
/**
- * 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.
+ * Searches this list for {@code object} and returns the index of the last
+ * occurrence that is before {@code to}.
*
- * @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}/../api/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}/../api/java/util/Collection.html#optional-restrictions">optional</a>),
- * or if the specified collection is null
- * @see #remove(Object)
+ * @return the index or -1 if the object was not found.
*/
- public boolean retainAll(Collection<?> c) {
- if (c == null) throw new NullPointerException();
- synchronized (lock) {
- Object[] elements = getArray();
- int len = elements.length;
- if (len != 0) {
- // temp array holds those elements we know we want to keep
- int newlen = 0;
- Object[] temp = new Object[len];
- for (int i = 0; i < len; ++i) {
- Object element = elements[i];
- if (c.contains(element))
- temp[newlen++] = element;
- }
- if (newlen != len) {
- setArray(Arrays.copyOf(temp, newlen));
- return true;
- }
- }
- return false;
- }
+ public int lastIndexOf(E object, int to) {
+ Object[] snapshot = elements;
+ return lastIndexOf(object, snapshot, 0, to);
+ }
+
+ public int lastIndexOf(Object object) {
+ Object[] snapshot = elements;
+ return lastIndexOf(object, snapshot, 0, snapshot.length);
+ }
+
+ public boolean isEmpty() {
+ return elements.length == 0;
}
/**
- * 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.
+ * Returns an {@link Iterator} that iterates over the elements of this list
+ * as they were at the time of this method call. Changes to the list made
+ * after this method call will not be reflected by the iterator, nor will
+ * they trigger a {@link ConcurrentModificationException}.
*
- * @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;
- }
- }
-
- public void forEach(Consumer<? super E> action) {
- if (action == null) throw new NullPointerException();
- for (Object x : getArray()) {
- @SuppressWarnings("unchecked") E e = (E) x;
- action.accept(e);
- }
- }
-
- public boolean removeIf(Predicate<? super E> filter) {
- if (filter == null) throw new NullPointerException();
- synchronized (lock) {
- final Object[] elements = getArray();
- final int len = elements.length;
- int i;
- for (i = 0; i < len; i++) {
- @SuppressWarnings("unchecked") E e = (E) elements[i];
- if (filter.test(e)) {
- int newlen = i;
- final Object[] newElements = new Object[len - 1];
- System.arraycopy(elements, 0, newElements, 0, newlen);
- for (i++; i < len; i++) {
- @SuppressWarnings("unchecked") E x = (E) elements[i];
- if (!filter.test(x))
- newElements[newlen++] = x;
- }
- setArray((newlen == len - 1)
- ? newElements // one match => one copy
- : Arrays.copyOf(newElements, newlen));
- return true;
- }
- }
- return false; // zero matches => zero copies
- }
- }
-
- public void replaceAll(UnaryOperator<E> operator) {
- if (operator == null) throw new NullPointerException();
- synchronized (lock) {
- Object[] elements = getArray();
- int len = elements.length;
- Object[] newElements = Arrays.copyOf(elements, len);
- for (int i = 0; i < len; ++i) {
- @SuppressWarnings("unchecked") E e = (E) elements[i];
- newElements[i] = operator.apply(e);
- }
- setArray(newElements);
- }
- }
-
- public void sort(Comparator<? super E> c) {
- synchronized (lock) {
- Object[] elements = getArray();
- Object[] newElements = Arrays.copyOf(elements, elements.length);
- @SuppressWarnings("unchecked") E[] es = (E[])newElements;
- Arrays.sort(es, c);
- setArray(newElements);
- }
- }
-
- /**
- * 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
+ * <p>The returned iterator does not support {@link Iterator#remove()}.
*/
public Iterator<E> iterator() {
- return new COWIterator<E>(getArray(), 0);
+ Object[] snapshot = elements;
+ return new CowIterator<E>(snapshot, 0, snapshot.length);
}
/**
- * {@inheritDoc}
+ * Returns a {@link ListIterator} that iterates over the elements of this
+ * list as they were at the time of this method call. Changes to the list
+ * made after this method call will not be reflected by the iterator, nor
+ * will they trigger a {@link ConcurrentModificationException}.
*
- * <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}
+ * <p>The returned iterator does not support {@link ListIterator#add},
+ * {@link ListIterator#set} or {@link Iterator#remove()},
*/
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);
+ Object[] snapshot = elements;
+ if (index < 0 || index > snapshot.length) {
+ throw new IndexOutOfBoundsException("index=" + index + ", length=" + snapshot.length);
+ }
+ CowIterator<E> result = new CowIterator<E>(snapshot, 0, snapshot.length);
+ result.index = index;
+ return result;
}
/**
- * 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
+ * Equivalent to {@code listIterator(0)}.
*/
- public Spliterator<E> spliterator() {
- return Spliterators.spliterator
- (getArray(), Spliterator.IMMUTABLE | Spliterator.ORDERED);
+ public ListIterator<E> listIterator() {
+ Object[] snapshot = elements;
+ return new CowIterator<E>(snapshot, 0, snapshot.length);
}
- 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 List<E> subList(int from, int to) {
+ Object[] snapshot = elements;
+ if (from < 0 || from > to || to > snapshot.length) {
+ throw new IndexOutOfBoundsException("from=" + from + ", to=" + to +
+ ", list size=" + snapshot.length);
}
+ return new CowSubList(snapshot, from, to);
+ }
- public boolean hasNext() {
- return cursor < snapshot.length;
+ public Object[] toArray() {
+ return elements.clone();
+ }
+
+ @SuppressWarnings({"unchecked","SuspiciousSystemArraycopy"})
+ public <T> T[] toArray(T[] contents) {
+ Object[] snapshot = elements;
+ if (snapshot.length > contents.length) {
+ return (T[]) Arrays.copyOf(snapshot, snapshot.length, contents.getClass());
}
-
- public boolean hasPrevious() {
- return cursor > 0;
+ System.arraycopy(snapshot, 0, contents, 0, snapshot.length);
+ if (snapshot.length < contents.length) {
+ contents[snapshot.length] = null;
}
+ return contents;
+ }
- @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]);
+ @Override public boolean equals(Object other) {
+ if (other instanceof CopyOnWriteArrayList) {
+ return this == other
+ || Arrays.equals(elements, ((CopyOnWriteArrayList<?>) other).elements);
+ } else if (other instanceof List) {
+ Object[] snapshot = elements;
+ Iterator<?> i = ((List<?>) other).iterator();
+ for (Object o : snapshot) {
+ if (!i.hasNext() || !Objects.equal(o, i.next())) {
+ return false;
+ }
}
- cursor = size;
+ return !i.hasNext();
+ } else {
+ return false;
}
}
+ @Override public int hashCode() {
+ return Arrays.hashCode(elements);
+ }
+
+ @Override public String toString() {
+ return Arrays.toString(elements);
+ }
+
+ public synchronized boolean add(E e) {
+ Object[] newElements = new Object[elements.length + 1];
+ System.arraycopy(elements, 0, newElements, 0, elements.length);
+ newElements[elements.length] = e;
+ elements = newElements;
+ return true;
+ }
+
+ public synchronized void add(int index, E e) {
+ Object[] newElements = new Object[elements.length + 1];
+ System.arraycopy(elements, 0, newElements, 0, index);
+ newElements[index] = e;
+ System.arraycopy(elements, index, newElements, index + 1, elements.length - index);
+ elements = newElements;
+ }
+
+ public synchronized boolean addAll(Collection<? extends E> collection) {
+ return addAll(elements.length, collection);
+ }
+
+ public synchronized boolean addAll(int index, Collection<? extends E> collection) {
+ Object[] toAdd = collection.toArray();
+ Object[] newElements = new Object[elements.length + toAdd.length];
+ System.arraycopy(elements, 0, newElements, 0, index);
+ System.arraycopy(toAdd, 0, newElements, index, toAdd.length);
+ System.arraycopy(elements, index,
+ newElements, index + toAdd.length, elements.length - index);
+ elements = newElements;
+ return toAdd.length > 0;
+ }
+
/**
- * 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.
+ * Adds the elements of {@code collection} that are not already present in
+ * this list. If {@code collection} includes a repeated value, at most one
+ * occurrence of that value will be added to this list. Elements are added
+ * at the end of 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}
+ * <p>Callers of this method may prefer {@link CopyOnWriteArraySet}, whose
+ * API is more appropriate for set operations.
*/
- 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);
+ public synchronized int addAllAbsent(Collection<? extends E> collection) {
+ Object[] toAdd = collection.toArray();
+ Object[] newElements = new Object[elements.length + toAdd.length];
+ System.arraycopy(elements, 0, newElements, 0, elements.length);
+ int addedCount = 0;
+ for (Object o : toAdd) {
+ if (indexOf(o, newElements, 0, elements.length + addedCount) == -1) {
+ newElements[elements.length + addedCount++] = o;
+ }
}
+ if (addedCount < toAdd.length) {
+ newElements = Arrays.copyOfRange(
+ newElements, 0, elements.length + addedCount); // trim to size
+ }
+ elements = newElements;
+ return addedCount;
}
/**
- * Sublist for CopyOnWriteArrayList.
- * This class extends AbstractList merely for convenience, to
- * avoid having to define addAll, etc. This doesn't hurt, but
- * is wasteful. This class does not need or use modCount
- * mechanics in AbstractList, but does need to check for
- * concurrent modification using similar mechanics. On each
- * operation, the array that we expect the backing list to use
- * is checked and updated. Since we do this for all of the
- * base operations invoked by those defined in AbstractList,
- * all is well. While inefficient, this is not worth
- * improving. The kinds of list operations inherited from
- * AbstractList are already so slow on COW sublists that
- * adding a bit more space/time doesn't seem even noticeable.
+ * Adds {@code object} to the end of this list if it is not already present.
+ *
+ * <p>Callers of this method may prefer {@link CopyOnWriteArraySet}, whose
+ * API is more appropriate for set operations.
*/
- 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;
+ public synchronized boolean addIfAbsent(E object) {
+ if (contains(object)) {
+ return false;
+ }
+ add(object);
+ return true;
+ }
- // 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;
+ @Override public synchronized void clear() {
+ elements = EmptyArray.OBJECT;
+ }
+
+ public synchronized E remove(int index) {
+ @SuppressWarnings("unchecked")
+ E removed = (E) elements[index];
+ removeRange(index, index + 1);
+ return removed;
+ }
+
+ public synchronized boolean remove(Object o) {
+ int index = indexOf(o);
+ if (index == -1) {
+ return false;
+ }
+ remove(index);
+ return true;
+ }
+
+ public synchronized boolean removeAll(Collection<?> collection) {
+ return removeOrRetain(collection, false, 0, elements.length) != 0;
+ }
+
+ public synchronized boolean retainAll(Collection<?> collection) {
+ return removeOrRetain(collection, true, 0, elements.length) != 0;
+ }
+
+ /**
+ * Removes or retains the elements in {@code collection}. Returns the number
+ * of elements removed.
+ */
+ private int removeOrRetain(Collection<?> collection, boolean retain, int from, int to) {
+ for (int i = from; i < to; i++) {
+ if (collection.contains(elements[i]) == retain) {
+ continue;
+ }
+
+ /*
+ * We've encountered an element that must be removed! Create a new
+ * array and copy in the surviving elements one by one.
+ */
+ Object[] newElements = new Object[elements.length - 1];
+ System.arraycopy(elements, 0, newElements, 0, i);
+ int newSize = i;
+ for (int j = i + 1; j < to; j++) {
+ if (collection.contains(elements[j]) == retain) {
+ newElements[newSize++] = elements[j];
+ }
+ }
+
+ /*
+ * Copy the elements after 'to'. This is only useful for sub lists,
+ * where 'to' will be less than elements.length.
+ */
+ System.arraycopy(elements, to, newElements, newSize, elements.length - to);
+ newSize += (elements.length - to);
+
+ if (newSize < newElements.length) {
+ newElements = Arrays.copyOfRange(newElements, 0, newSize); // trim to size
+ }
+ int removed = elements.length - newElements.length;
+ elements = newElements;
+ return removed;
}
- // only call this holding l's lock
- private void checkForComodification() {
- // assert Thread.holdsLock(l.lock);
- if (l.getArray() != expectedArray)
- throw new ConcurrentModificationException();
+ // we made it all the way through the loop without making any changes
+ return 0;
+ }
+
+ public synchronized E set(int index, E e) {
+ Object[] newElements = elements.clone();
+ @SuppressWarnings("unchecked")
+ E result = (E) newElements[index];
+ newElements[index] = e;
+ elements = newElements;
+ return result;
+ }
+
+ private void removeRange(int from, int to) {
+ Object[] newElements = new Object[elements.length - (to - from)];
+ System.arraycopy(elements, 0, newElements, 0, from);
+ System.arraycopy(elements, to, newElements, from, elements.length - to);
+ elements = newElements;
+ }
+
+ static int lastIndexOf(Object o, Object[] data, int from, int to) {
+ if (o == null) {
+ for (int i = to - 1; i >= from; i--) {
+ if (data[i] == null) {
+ return i;
+ }
+ }
+ } else {
+ for (int i = to - 1; i >= from; i--) {
+ if (o.equals(data[i])) {
+ return i;
+ }
+ }
+ }
+ return -1;
+ }
+
+ static int indexOf(Object o, Object[] data, int from, int to) {
+ if (o == null) {
+ for (int i = from; i < to; i++) {
+ if (data[i] == null) {
+ return i;
+ }
+ }
+ } else {
+ for (int i = from; i < to; i++) {
+ if (o.equals(data[i])) {
+ return i;
+ }
+ }
+ }
+ return -1;
+ }
+
+ final Object[] getArray() {
+ // CopyOnWriteArraySet needs this.
+ return elements;
+ }
+
+ /**
+ * The sub list is thread safe and supports non-blocking reads. Doing so is
+ * more difficult than in the full list, because each read needs to examine
+ * four fields worth of state:
+ * - the elements array of the full list
+ * - two integers for the bounds of this sub list
+ * - the expected elements array (to detect concurrent modification)
+ *
+ * This is accomplished by aggregating the sub list's three fields into a
+ * single snapshot object representing the current slice. This permits reads
+ * to be internally consistent without synchronization. This takes advantage
+ * of Java's concurrency semantics for final fields.
+ */
+ class CowSubList extends AbstractList<E> {
+
+ /*
+ * An immutable snapshot of a sub list's state. By gathering all three
+ * of the sub list's fields in an immutable object,
+ */
+ private volatile Slice slice;
+
+ public CowSubList(Object[] expectedElements, int from, int to) {
+ this.slice = new Slice(expectedElements, from, to);
}
- // 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));
+ @Override public int size() {
+ Slice slice = this.slice;
+ return slice.to - slice.from;
}
- public E set(int index, E element) {
- synchronized (l.lock) {
- rangeCheck(index);
- checkForComodification();
- E x = l.set(index+offset, element);
- expectedArray = l.getArray();
- return x;
+ @Override public boolean isEmpty() {
+ Slice slice = this.slice;
+ return slice.from == slice.to;
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override public E get(int index) {
+ Slice slice = this.slice;
+ Object[] snapshot = elements;
+ slice.checkElementIndex(index);
+ slice.checkConcurrentModification(snapshot);
+ return (E) snapshot[index + slice.from];
+ }
+
+ @Override public Iterator<E> iterator() {
+ return listIterator(0);
+ }
+
+ @Override public ListIterator<E> listIterator() {
+ return listIterator(0);
+ }
+
+ @Override public ListIterator<E> listIterator(int index) {
+ Slice slice = this.slice;
+ Object[] snapshot = elements;
+ slice.checkPositionIndex(index);
+ slice.checkConcurrentModification(snapshot);
+ CowIterator<E> result = new CowIterator<E>(snapshot, slice.from, slice.to);
+ result.index = slice.from + index;
+ return result;
+ }
+
+ @Override public int indexOf(Object object) {
+ Slice slice = this.slice;
+ Object[] snapshot = elements;
+ slice.checkConcurrentModification(snapshot);
+ int result = CopyOnWriteArrayList.indexOf(object, snapshot, slice.from, slice.to);
+ return (result != -1) ? (result - slice.from) : -1;
+ }
+
+ @Override public int lastIndexOf(Object object) {
+ Slice slice = this.slice;
+ Object[] snapshot = elements;
+ slice.checkConcurrentModification(snapshot);
+ int result = CopyOnWriteArrayList.lastIndexOf(object, snapshot, slice.from, slice.to);
+ return (result != -1) ? (result - slice.from) : -1;
+ }
+
+ @Override public boolean contains(Object object) {
+ return indexOf(object) != -1;
+ }
+
+ @Override public boolean containsAll(Collection<?> collection) {
+ Slice slice = this.slice;
+ Object[] snapshot = elements;
+ slice.checkConcurrentModification(snapshot);
+ return CopyOnWriteArrayList.containsAll(collection, snapshot, slice.from, slice.to);
+ }
+
+ @Override public List<E> subList(int from, int to) {
+ Slice slice = this.slice;
+ if (from < 0 || from > to || to > size()) {
+ throw new IndexOutOfBoundsException("from=" + from + ", to=" + to +
+ ", list size=" + size());
+ }
+ return new CowSubList(slice.expectedElements, slice.from + from, slice.from + to);
+ }
+
+ @Override public E remove(int index) {
+ synchronized (CopyOnWriteArrayList.this) {
+ slice.checkElementIndex(index);
+ slice.checkConcurrentModification(elements);
+ E removed = CopyOnWriteArrayList.this.remove(slice.from + index);
+ slice = new Slice(elements, slice.from, slice.to - 1);
+ return removed;
}
}
- public E get(int index) {
- synchronized (l.lock) {
- rangeCheck(index);
- checkForComodification();
- return l.get(index+offset);
+ @Override public void clear() {
+ synchronized (CopyOnWriteArrayList.this) {
+ slice.checkConcurrentModification(elements);
+ CopyOnWriteArrayList.this.removeRange(slice.from, slice.to);
+ slice = new Slice(elements, slice.from, slice.from);
}
}
- public int size() {
- synchronized (l.lock) {
- checkForComodification();
- return size;
+ @Override public void add(int index, E object) {
+ synchronized (CopyOnWriteArrayList.this) {
+ slice.checkPositionIndex(index);
+ slice.checkConcurrentModification(elements);
+ CopyOnWriteArrayList.this.add(index + slice.from, object);
+ slice = new Slice(elements, slice.from, slice.to + 1);
}
}
- public void add(int index, E element) {
- synchronized (l.lock) {
- checkForComodification();
- if (index < 0 || index > size)
- throw new IndexOutOfBoundsException
- (outOfBounds(index, size));
- l.add(index+offset, element);
- expectedArray = l.getArray();
- size++;
+ @Override public boolean add(E object) {
+ synchronized (CopyOnWriteArrayList.this) {
+ add(slice.to - slice.from, object);
+ return true;
}
}
- 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(index+offset);
- expectedArray = l.getArray();
- size--;
+ @Override public boolean addAll(int index, Collection<? extends E> collection) {
+ synchronized (CopyOnWriteArrayList.this) {
+ slice.checkPositionIndex(index);
+ slice.checkConcurrentModification(elements);
+ int oldSize = elements.length;
+ boolean result = CopyOnWriteArrayList.this.addAll(index + slice.from, collection);
+ slice = new Slice(elements, slice.from, slice.to + (elements.length - oldSize));
return result;
}
}
- public boolean remove(Object o) {
- 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);
+ @Override public boolean addAll(Collection<? extends E> collection) {
+ synchronized (CopyOnWriteArrayList.this) {
+ return addAll(size(), collection);
}
}
- 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);
+ @Override public E set(int index, E object) {
+ synchronized (CopyOnWriteArrayList.this) {
+ slice.checkElementIndex(index);
+ slice.checkConcurrentModification(elements);
+ E result = CopyOnWriteArrayList.this.set(index + slice.from, object);
+ slice = new Slice(elements, slice.from, slice.to);
+ return result;
}
}
- 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) {
- if (action == null) throw new NullPointerException();
- int lo = offset;
- int hi = offset + size;
- Object[] a = expectedArray;
- if (l.getArray() != a)
- throw new ConcurrentModificationException();
- if (lo < 0 || hi > a.length)
- throw new IndexOutOfBoundsException();
- for (int i = lo; i < hi; ++i) {
- @SuppressWarnings("unchecked") E e = (E) a[i];
- action.accept(e);
- }
- }
-
- public void replaceAll(UnaryOperator<E> operator) {
- if (operator == null) throw new NullPointerException();
- synchronized (l.lock) {
- int lo = offset;
- int hi = offset + size;
- Object[] elements = expectedArray;
- if (l.getArray() != elements)
- throw new ConcurrentModificationException();
- int len = elements.length;
- if (lo < 0 || hi > len)
- throw new IndexOutOfBoundsException();
- Object[] newElements = Arrays.copyOf(elements, len);
- for (int i = lo; i < hi; ++i) {
- @SuppressWarnings("unchecked") E e = (E) elements[i];
- newElements[i] = operator.apply(e);
+ @Override public boolean remove(Object object) {
+ synchronized (CopyOnWriteArrayList.this) {
+ int index = indexOf(object);
+ if (index == -1) {
+ return false;
}
- l.setArray(expectedArray = newElements);
+ remove(index);
+ return true;
}
}
- public void sort(Comparator<? super E> c) {
- synchronized (l.lock) {
- int lo = offset;
- int hi = offset + size;
- Object[] elements = expectedArray;
- if (l.getArray() != elements)
- throw new ConcurrentModificationException();
- int len = elements.length;
- if (lo < 0 || hi > len)
- throw new IndexOutOfBoundsException();
- Object[] newElements = Arrays.copyOf(elements, len);
- @SuppressWarnings("unchecked") E[] es = (E[])newElements;
- Arrays.sort(es, lo, hi, c);
- l.setArray(expectedArray = newElements);
+ @Override public boolean removeAll(Collection<?> collection) {
+ synchronized (CopyOnWriteArrayList.this) {
+ slice.checkConcurrentModification(elements);
+ int removed = removeOrRetain(collection, false, slice.from, slice.to);
+ slice = new Slice(elements, slice.from, slice.to - removed);
+ return removed != 0;
}
}
- public boolean removeAll(Collection<?> c) {
- if (c == null) throw new NullPointerException();
- boolean removed = false;
- synchronized (l.lock) {
- int n = size;
- if (n > 0) {
- int lo = offset;
- int hi = offset + n;
- Object[] elements = expectedArray;
- if (l.getArray() != elements)
- throw new ConcurrentModificationException();
- int len = elements.length;
- if (lo < 0 || hi > len)
- throw new IndexOutOfBoundsException();
- int newSize = 0;
- Object[] temp = new Object[n];
- for (int i = lo; i < hi; ++i) {
- Object element = elements[i];
- if (!c.contains(element))
- temp[newSize++] = element;
- }
- if (newSize != n) {
- Object[] newElements = new Object[len - n + newSize];
- System.arraycopy(elements, 0, newElements, 0, lo);
- System.arraycopy(temp, 0, newElements, lo, newSize);
- System.arraycopy(elements, hi, newElements,
- lo + newSize, len - hi);
- size = newSize;
- removed = true;
- l.setArray(expectedArray = newElements);
- }
- }
+ @Override public boolean retainAll(Collection<?> collection) {
+ synchronized (CopyOnWriteArrayList.this) {
+ slice.checkConcurrentModification(elements);
+ int removed = removeOrRetain(collection, true, slice.from, slice.to);
+ slice = new Slice(elements, slice.from, slice.to - removed);
+ return removed != 0;
}
- return removed;
}
-
- public boolean retainAll(Collection<?> c) {
- if (c == null) throw new NullPointerException();
- boolean removed = false;
- synchronized (l.lock) {
- int n = size;
- if (n > 0) {
- int lo = offset;
- int hi = offset + n;
- Object[] elements = expectedArray;
- if (l.getArray() != elements)
- throw new ConcurrentModificationException();
- int len = elements.length;
- if (lo < 0 || hi > len)
- throw new IndexOutOfBoundsException();
- int newSize = 0;
- Object[] temp = new Object[n];
- for (int i = lo; i < hi; ++i) {
- Object element = elements[i];
- if (c.contains(element))
- temp[newSize++] = element;
- }
- if (newSize != n) {
- Object[] newElements = new Object[len - n + newSize];
- System.arraycopy(elements, 0, newElements, 0, lo);
- System.arraycopy(temp, 0, newElements, lo, newSize);
- System.arraycopy(elements, hi, newElements,
- lo + newSize, len - hi);
- size = newSize;
- removed = true;
- l.setArray(expectedArray = newElements);
- }
- }
- }
- return removed;
- }
-
- public boolean removeIf(Predicate<? super E> filter) {
- if (filter == null) throw new NullPointerException();
- boolean removed = false;
- synchronized (l.lock) {
- int n = size;
- if (n > 0) {
- int lo = offset;
- int hi = offset + n;
- Object[] elements = expectedArray;
- if (l.getArray() != elements)
- throw new ConcurrentModificationException();
- int len = elements.length;
- if (lo < 0 || hi > len)
- throw new IndexOutOfBoundsException();
- int newSize = 0;
- Object[] temp = new Object[n];
- for (int i = lo; i < hi; ++i) {
- @SuppressWarnings("unchecked") E e = (E) elements[i];
- if (!filter.test(e))
- temp[newSize++] = e;
- }
- if (newSize != n) {
- Object[] newElements = new Object[len - n + newSize];
- System.arraycopy(elements, 0, newElements, 0, lo);
- System.arraycopy(temp, 0, newElements, lo, newSize);
- System.arraycopy(elements, hi, newElements,
- lo + newSize, len - hi);
- size = newSize;
- removed = true;
- l.setArray(expectedArray = newElements);
- }
- }
- }
- return removed;
- }
-
- public Spliterator<E> spliterator() {
- int lo = offset;
- int hi = offset + size;
- Object[] a = expectedArray;
- if (l.getArray() != a)
- throw new ConcurrentModificationException();
- if (lo < 0 || hi > a.length)
- throw new IndexOutOfBoundsException();
- return Spliterators.spliterator
- (a, lo, hi, 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;
+ static class Slice {
+ private final Object[] expectedElements;
+ private final int from;
+ private final int to;
- COWSubListIterator(List<E> l, int index, int offset, int size) {
- this.offset = offset;
- this.size = size;
- it = l.listIterator(index+offset);
+ Slice(Object[] expectedElements, int from, int to) {
+ this.expectedElements = expectedElements;
+ this.from = from;
+ this.to = to;
+ }
+
+ /**
+ * Throws if {@code index} doesn't identify an element in the array.
+ */
+ void checkElementIndex(int index) {
+ if (index < 0 || index >= to - from) {
+ throw new IndexOutOfBoundsException("index=" + index + ", size=" + (to - from));
+ }
+ }
+
+ /**
+ * Throws if {@code index} doesn't identify an insertion point in the
+ * array. Unlike element index, it's okay to add or iterate at size().
+ */
+ void checkPositionIndex(int index) {
+ if (index < 0 || index > to - from) {
+ throw new IndexOutOfBoundsException("index=" + index + ", size=" + (to - from));
+ }
+ }
+
+ void checkConcurrentModification(Object[] snapshot) {
+ if (expectedElements != snapshot) {
+ throw new ConcurrentModificationException();
+ }
+ }
+ }
+
+ /**
+ * Iterates an immutable snapshot of the list.
+ */
+ static class CowIterator<E> implements ListIterator<E> {
+ private final Object[] snapshot;
+ private final int from;
+ private final int to;
+ private int index = 0;
+
+ CowIterator(Object[] snapshot, int from, int to) {
+ this.snapshot = snapshot;
+ this.from = from;
+ this.to = to;
+ this.index = from;
+ }
+
+ public void add(E object) {
+ throw new UnsupportedOperationException();
}
public boolean hasNext() {
- return nextIndex() < size;
- }
-
- public E next() {
- if (hasNext())
- return it.next();
- else
- throw new NoSuchElementException();
+ return index < to;
}
public boolean hasPrevious() {
- return previousIndex() >= 0;
+ return index > from;
}
- public E previous() {
- if (hasPrevious())
- return it.previous();
- else
+ @SuppressWarnings("unchecked")
+ public E next() {
+ if (index < to) {
+ return (E) snapshot[index++];
+ } else {
throw new NoSuchElementException();
+ }
}
public int nextIndex() {
- return it.nextIndex() - offset;
+ return index;
+ }
+
+ @SuppressWarnings("unchecked")
+ public E previous() {
+ if (index > from) {
+ return (E) snapshot[--index];
+ } else {
+ throw new NoSuchElementException();
+ }
}
public int previousIndex() {
- return it.previousIndex() - offset;
+ return index - 1;
}
public void remove() {
throw new UnsupportedOperationException();
}
- public void set(E e) {
- throw new UnsupportedOperationException();
- }
-
- public void add(E e) {
+ public void set(E object) {
throw new UnsupportedOperationException();
}
@Override
- @SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> action) {
- Objects.requireNonNull(action);
- while (nextIndex() < size) {
- action.accept(it.next());
+ java.util.Objects.requireNonNull(action);
+ Object[] elements = snapshot;
+ for (int i = index; i < to; i++) {
+ @SuppressWarnings("unchecked") E e = (E) elements[i];
+ action.accept(e);
}
+ index = to;
}
}
- // Support for resetting lock while deserializing
- private void resetLock() {
- U.putObjectVolatile(this, LOCK, new Object());
- }
- private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
- private static final long LOCK;
- static {
- try {
- LOCK = U.objectFieldOffset
- (CopyOnWriteArrayList.class.getDeclaredField("lock"));
- } catch (ReflectiveOperationException e) {
- throw new Error(e);
+ private void writeObject(ObjectOutputStream out) throws IOException {
+ Object[] snapshot = elements;
+ out.defaultWriteObject();
+ out.writeInt(snapshot.length);
+ for (Object o : snapshot) {
+ out.writeObject(o);
}
}
+
+ private synchronized void readObject(ObjectInputStream in)
+ throws IOException, ClassNotFoundException {
+ in.defaultReadObject();
+ Object[] snapshot = new Object[in.readInt()];
+ for (int i = 0; i < snapshot.length; i++) {
+ snapshot[i] = in.readObject();
+ }
+ elements = snapshot;
+ }
}
