jdk-sandbox: comparison jdk/src/share/classes/java/util/concurrent/CopyOnWriteArrayList.java

equal deleted inserted replaced

-:28c62f5e9a47
+:6214297bf27d
 /*
-* Copyright (c) 2003, 2012, Oracle and/or its affiliates. All rights reserved.
 * 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
 * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
 * All rights reserved.
 */
 package java.util.concurrent;
-import java.util.*;
+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.concurrent.locks.ReentrantLock;
 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 (<tt>add</tt>, <tt>set</tt>, and so on) are implemented by
+* 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
+* <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 <tt>ConcurrentModificationException</tt>.
+* 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 (<tt>remove</tt>, <tt>set</tt>, and
+* operations on iterators themselves ({@code remove}, {@code set}, and
-* <tt>add</tt>) are not supported. These methods throw
+* {@code add}) are not supported. These methods throw
-* <tt>UnsupportedOperationException</tt>.
+* {@code UnsupportedOperationException}.
 *
-* <p>All elements are permitted, including <tt>null</tt>.
+* <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>
 public class CopyOnWriteArrayList<E>
 implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
 private static final long serialVersionUID = 8673264195747942595L;
 /** The lock protecting all mutators */
-transient final ReentrantLock lock = new ReentrantLock();
+final transient ReentrantLock lock = new ReentrantLock();
 /** The array, accessed only via getArray/setArray. */
-private volatile transient Object[] array;
+private transient volatile Object[] array;
 /**
 * Gets the array.  Non-private so as to also be accessible
 * from CopyOnWriteArraySet class.
 */
 *
 * @param c the collection of initially held elements
 * @throws NullPointerException if the specified collection is null
 */
 public CopyOnWriteArrayList(Collection<? extends E> c) {
-Object[] elements = c.toArray();
+Object[] elements;
-// c.toArray might (incorrectly) not return Object[] (see 6260652)
+if (c.getClass() == CopyOnWriteArrayList.class)
-if (elements.getClass() != Object[].class)
+elements = ((CopyOnWriteArrayList<?>)c).getArray();
-elements = Arrays.copyOf(elements, elements.length, Object[].class);
+else {
+elements = c.toArray();
+// c.toArray might (incorrectly) not return Object[] (see 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.
 public int size() {
 return getArray().length;
 }
 /**
-* Returns <tt>true</tt> if this list contains no elements.
+* Returns {@code true} if this list contains no elements.
 *
-* @return <tt>true</tt> if this list contains no elements
+* @return {@code true} if this list contains no elements
 */
 public boolean isEmpty() {
 return size() == 0;
 }
 /**
 * Tests for equality, coping with nulls.
 */
 private static boolean eq(Object o1, Object o2) {
-return (o1 == null ? o2 == null : o1.equals(o2));
+return (o1 == null) ? o2 == null : o1.equals(o2);
 }
 /**
 * static version of indexOf, to allow repeated calls without
 * needing to re-acquire array each time.
 }
 return -1;
 }
 /**
-* Returns <tt>true</tt> if this list contains the specified element.
+* Returns {@code true} if this list contains the specified element.
-* More formally, returns <tt>true</tt> if and only if this list contains
+* More formally, returns {@code true} if and only if this list contains
-* at least one element <tt>e</tt> such that
+* at least one element {@code e} such that
 * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
 *
 * @param o element whose presence in this list is to be tested
-* @return <tt>true</tt> if this list contains the specified element
+* @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;
 }
 return indexOf(o, elements, 0, elements.length);
 }
 /**
 * Returns the index of the first occurrence of the specified element in
-* this list, searching forwards from <tt>index</tt>, or returns -1 if
+* this list, searching forwards from {@code index}, or returns -1 if
 * the element is not found.
-* More formally, returns the lowest index <tt>i</tt> such that
+* More formally, returns the lowest index {@code i} such that
 * <tt>(i&nbsp;&gt;=&nbsp;index&nbsp;&amp;&amp;&nbsp;(e==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;e.equals(get(i))))</tt>,
 * 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 <tt>index</tt> or later in the list;
+*         this list at position {@code index} or later in the list;
-*         <tt>-1</tt> if the element is not found.
+*         {@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);
 return lastIndexOf(o, elements, elements.length - 1);
 }
 /**
 * Returns the index of the last occurrence of the specified element in
-* this list, searching backwards from <tt>index</tt>, or returns -1 if
+* this list, searching backwards from {@code index}, or returns -1 if
 * the element is not found.
-* More formally, returns the highest index <tt>i</tt> such that
+* More formally, returns the highest index {@code i} such that
 * <tt>(i&nbsp;&lt;=&nbsp;index&nbsp;&amp;&amp;&nbsp;(e==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;e.equals(get(i))))</tt>,
 * 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 <tt>index</tt> in this list;
+*         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) {
 * 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
-* <tt>null</tt>.  (This is useful in determining the length of this
+* {@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 <tt>x</tt> is a list known to contain only strings.
+* <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 <tt>String</tt>:
+* allocated array of {@code String}:
 *
 *  <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
 *
-* Note that <tt>toArray(new Object[0])</tt> is identical in function to
+* Note that {@code toArray(new Object[0])} is identical in function to
-* <tt>toArray()</tt>.
+* {@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
 /**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
-* @return <tt>true</tt> (as specified by {@link Collection#add})
+* @return {@code true} (as specified by {@link Collection#add})
 */
 public boolean add(E e) {
 final ReentrantLock lock = this.lock;
 lock.lock();
 try {
 /**
 * 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
-* <tt>i</tt> such that
+* {@code i} such that
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
-* (if such an element exists).  Returns <tt>true</tt> if this list
+* (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 <tt>true</tt> if this list contained the specified element
+* @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) {
 final ReentrantLock lock = this.lock;
 lock.lock();
 try {
-Object[] elements = getArray();
+Object[] current = getArray();
-int len = elements.length;
+int len = current.length;
-if (len != 0) {
+if (snapshot != current) findIndex: {
-// Copy while searching for element to remove
+int prefix = Math.min(index, len);
-// This wins in the normal case of element being present
+for (int i = 0; i < prefix; i++) {
-int newlen = len - 1;
+if (current[i] != snapshot[i] && eq(o, current[i])) {
-Object[] newElements = new Object[newlen];
+index = i;
+break findIndex;
-for (int i = 0; i < newlen; ++i) {
+}
-if (eq(o, elements[i])) {
-// found one;  copy remaining and exit
-for (int k = i + 1; k < len; ++k)
-newElements[k-1] = elements[k];
-setArray(newElements);
-return true;
-} else
-newElements[i] = elements[i];
 }
+if (index >= len)
-// special handling for last cell
+return false;
-if (eq(o, elements[newlen])) {
+if (current[index] == o)
-setArray(newElements);
+break findIndex;
-return true;
+index = indexOf(o, current, index, len);
-}
+if (index < 0)
-}
+return false;
-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;
 } finally {
 lock.unlock();
 }
 }
 /**
 * Removes from this list all of the elements whose index is between
-* <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
+* {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
 * Shifts any succeeding elements to the left (reduces their index).
-* This call shortens the list by <tt>(toIndex - fromIndex)</tt> elements.
+* This call shortens the list by {@code (toIndex - fromIndex)} elements.
-* (If <tt>toIndex==fromIndex</tt>, this operation has no effect.)
+* (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})
 /**
 * Appends the element, if not present.
 *
 * @param e element to be added to this list, if absent
-* @return <tt>true</tt> if the element was added
+* @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) {
 final ReentrantLock lock = this.lock;
 lock.lock();
 try {
-// Copy while checking if already present.
+Object[] current = getArray();
-// This wins in the most common case where it is not present
+int len = current.length;
-Object[] elements = getArray();
+if (snapshot != current) {
-int len = elements.length;
+// Optimize for lost race to another addXXX operation
-Object[] newElements = new Object[len + 1];
+int common = Math.min(snapshot.length, len);
-for (int i = 0; i < len; ++i) {
+for (int i = 0; i < common; i++)
-if (eq(e, elements[i]))
+if (current[i] != snapshot[i] && eq(e, current[i]))
-return false; // exit, throwing away copy
+return false;
-else
+if (indexOf(e, current, common, len) >= 0)
-newElements[i] = elements[i];
+return false;
 }
+Object[] newElements = Arrays.copyOf(current, len + 1);
 newElements[len] = e;
 setArray(newElements);
 return true;
 } finally {
 lock.unlock();
 }
 }
 /**
-* Returns <tt>true</tt> if this list contains all of the elements of the
+* 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 <tt>true</tt> if this list contains all of the elements of the
+* @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) {
 * 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 <tt>true</tt> if this list changed as a result of the call
+* @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="../Collection.html#optional-restrictions">optional</a>)
 * @throws NullPointerException if this list contains a null element and the
 *         specified collection does not permit null elements
 * 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 <tt>true</tt> if this list changed as a result of the call
+* @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="../Collection.html#optional-restrictions">optional</a>)
 * @throws NullPointerException if this list contains a null element and the
 *         specified collection does not permit null elements
 */
 public int addAllAbsent(Collection<? extends E> c) {
 Object[] cs = c.toArray();
 if (cs.length == 0)
 return 0;
-Object[] uniq = new Object[cs.length];
 final ReentrantLock lock = this.lock;
 lock.lock();
 try {
 Object[] elements = getArray();
 int len = elements.length;
 int added = 0;
-for (int i = 0; i < cs.length; ++i) { // scan for duplicates
+// 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, uniq, 0, added) < 0)
+indexOf(e, cs, 0, added) < 0)
-uniq[added++] = e;
+cs[added++] = e;
 }
 if (added > 0) {
 Object[] newElements = Arrays.copyOf(elements, len + added);
-System.arraycopy(uniq, 0, newElements, len, added);
+System.arraycopy(cs, 0, newElements, len, added);
 setArray(newElements);
 }
 return added;
 } finally {
 lock.unlock();
 * 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 <tt>true</tt> if this list changed as a result of the call
+* @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.toArray();
+Object[] cs = (c.getClass() == CopyOnWriteArrayList.class) ?
+((CopyOnWriteArrayList<?>)c).getArray() : c.toArray();
 if (cs.length == 0)
 return false;
 final ReentrantLock lock = this.lock;
 lock.lock();
 try {
 Object[] elements = getArray();
 int len = elements.length;
-Object[] newElements = Arrays.copyOf(elements, len + cs.length);
+if (len == 0 && cs.getClass() == Object[].class)
-System.arraycopy(cs, 0, newElements, len, cs.length);
+setArray(cs);
-setArray(newElements);
+else {
+Object[] newElements = Arrays.copyOf(elements, len + cs.length);
+System.arraycopy(cs, 0, newElements, len, cs.length);
+setArray(newElements);
+}
 return true;
 } finally {
 lock.unlock();
 }
 }
 * 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 <tt>true</tt> if this list changed as a result of the call
+* @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) {
 } finally {
 lock.unlock();
 }
 }
+public void forEach(Consumer<? super E> action) {
+if (action == null) throw new NullPointerException();
+Object[] elements = getArray();
+int len = elements.length;
+for (int i = 0; i < len; ++i) {
+@SuppressWarnings("unchecked") E e = (E) elements[i];
+action.accept(e);
+}
+}
+public boolean removeIf(Predicate<? super E> filter) {
+if (filter == null) throw new NullPointerException();
+final ReentrantLock lock = this.lock;
+lock.lock();
+try {
+Object[] elements = getArray();
+int len = elements.length;
+if (len != 0) {
+int newlen = 0;
+Object[] temp = new Object[len];
+for (int i = 0; i < len; ++i) {
+@SuppressWarnings("unchecked") E e = (E) elements[i];
+if (!filter.test(e))
+temp[newlen++] = e;
+}
+if (newlen != len) {
+setArray(Arrays.copyOf(temp, newlen));
+return true;
+}
+}
+return false;
+} finally {
+lock.unlock();
+}
+}
+public void replaceAll(UnaryOperator<E> operator) {
+if (operator == null) throw new NullPointerException();
+final ReentrantLock lock = this.lock;
+lock.lock();
+try {
+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);
+} finally {
+lock.unlock();
+}
+}
+public void sort(Comparator<? super E> c) {
+final ReentrantLock lock = this.lock;
+lock.lock();
+try {
+Object[] elements = getArray();
+Object[] newElements = Arrays.copyOf(elements, elements.length);
+@SuppressWarnings("unchecked") E[] es = (E[])newElements;
+Arrays.sort(es, c);
+setArray(newElements);
+} finally {
+lock.unlock();
+}
+}
 /**
 * Saves this list to a stream (that is, serializes it).
 *
 * @serialData The length of the array backing the list is emitted
 *               (int), followed by all of its elements (each an Object)
 /**
 * 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 (<tt>"[]"</tt>).  Adjacent elements are separated by
+* square brackets ({@code "[]"}).  Adjacent elements are separated by
-* the characters <tt>", "</tt> (comma and space).  Elements are
+* 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() {
 * 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
-* <tt>remove</tt> method.
+* {@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
-* <tt>remove</tt>, <tt>set</tt> or <tt>add</tt> methods.
+* {@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
-* <tt>remove</tt>, <tt>set</tt> or <tt>add</tt> methods.
+* {@code remove}, {@code set} or {@code add} methods.
 *
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
 public ListIterator<E> listIterator(final int index) {
 Object[] elements = getArray();
 throw new IndexOutOfBoundsException("Index: "+index);
 return new COWIterator<E>(elements, index);
 }
-private static class COWIterator<E> implements ListIterator<E> {
+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;
 return cursor-1;
 }
 /**
 * Not supported. Always throws UnsupportedOperationException.
-* @throws UnsupportedOperationException always; <tt>remove</tt>
+* @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; <tt>set</tt>
+* @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; <tt>add</tt>
+* @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;
+Object[] elements = snapshot;
-for (int i=cursor; i < size; i++) {
+final int size = elements.length;
-action.accept((E) snapshot[i]);
+for (int i = cursor; i < size; i++) {
+@SuppressWarnings("unchecked") E e = (E) elements[i];
+action.accept(e);
 }
 cursor = size;
 }
 }
 /**
 * Returns a view of the portion of this list between
-* <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
+* {@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
 } finally {
 lock.unlock();
 }
 }
-@Override
 public void forEach(Consumer<? super E> action) {
-@SuppressWarnings("unchecked")
+if (action == null) throw new NullPointerException();
-final E[] elements = (E[]) l.getArray();
+int lo = offset;
-checkForComodification();
+int hi = offset + size;
-l.forEach(action, elements, offset, offset + size);
+Object[] a = expectedArray;
-}
+if (l.getArray() != a)
+throw new ConcurrentModificationException();
-@Override
+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();
+final ReentrantLock lock = l.lock;
+lock.lock();
+try {
+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);
+}
+l.setArray(expectedArray = newElements);
+} finally {
+lock.unlock();
+}
+}
 public void sort(Comparator<? super E> c) {
 final ReentrantLock lock = l.lock;
 lock.lock();
 try {
-checkForComodification();
+int lo = offset;
-l.sort(c, offset, offset + size);
+int hi = offset + size;
-expectedArray = l.getArray();
+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);
 } finally {
 lock.unlock();
 }
 }
-@Override
+public boolean removeAll(Collection<?> c) {
-public boolean removeIf(Predicate<? super E> filter) {
+if (c == null) throw new NullPointerException();
-Objects.requireNonNull(filter);
+boolean removed = false;
 final ReentrantLock lock = l.lock;
 lock.lock();
 try {
-checkForComodification();
+int n = size;
-final int removeCount =
+if (n > 0) {
-l.removeIf(filter, offset, offset + size);
+int lo = offset;
-expectedArray = l.getArray();
+int hi = offset + n;
-size -= removeCount;
+Object[] elements = expectedArray;
-return removeCount > 0;
+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);
+}
+}
 } finally {
 lock.unlock();
 }
-}
+return removed;
+}
-@Override
-public void replaceAll(UnaryOperator<E> operator) {
+public boolean retainAll(Collection<?> c) {
+if (c == null) throw new NullPointerException();
+boolean removed = false;
 final ReentrantLock lock = l.lock;
 lock.lock();
 try {
-checkForComodification();
+int n = size;
-l.replaceAll(operator, offset, offset + size);
+if (n > 0) {
-expectedArray = l.getArray();
+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);
+}
+}
 } finally {
 lock.unlock();
 }
+return removed;
+}
+public boolean removeIf(Predicate<? super E> filter) {
+if (filter == null) throw new NullPointerException();
+boolean removed = false;
+final ReentrantLock lock = l.lock;
+lock.lock();
+try {
+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);
+}
+}
+} finally {
+lock.unlock();
+}
+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;
 public void add(E e) {
 throw new UnsupportedOperationException();
 }
 @Override
-@SuppressWarnings("unchecked")
 public void forEachRemaining(Consumer<? super E> action) {
 Objects.requireNonNull(action);
-while (nextIndex() < size) {
+int s = size;
-action.accept(it.next());
+ListIterator<E> i = it;
+while (nextIndex() < s) {
+action.accept(i.next());
 }
 }
 }
 // Support for resetting lock while deserializing
 (k.getDeclaredField("lock"));
 } catch (Exception e) {
 throw new Error(e);
 }
 }
-@Override
-@SuppressWarnings("unchecked")
-public void forEach(Consumer<? super E> action) {
-forEach(action, (E[]) getArray(), 0, size());
-}
-private void forEach(Consumer<? super E> action,
-final E[] elements,
-final int from, final int to) {
-Objects.requireNonNull(action);
-for (int i = from; i < to; i++) {
-action.accept(elements[i]);
-}
-}
-@Override
-public void sort(Comparator<? super E> c) {
-final ReentrantLock lock = this.lock;
-lock.lock();
-try {
-sort(c, 0, size());
-} finally {
-lock.unlock();
-}
-}
-// must be called with this.lock held
-@SuppressWarnings("unchecked")
-private void sort(Comparator<? super E> c, final int from, final int to) {
-final E[] elements = (E[]) getArray();
-final E[] newElements = Arrays.copyOf(elements, elements.length);
-// only elements [from, to) are sorted
-Arrays.sort(newElements, from, to, c);
-setArray(newElements);
-}
-@Override
-public boolean removeIf(Predicate<? super E> filter) {
-Objects.requireNonNull(filter);
-final ReentrantLock lock = this.lock;
-lock.lock();
-try {
-return removeIf(filter, 0, size()) > 0;
-} finally {
-lock.unlock();
-}
-}
-// must be called with this.lock held
-private int removeIf(Predicate<? super E> filter, final int from, final int to) {
-Objects.requireNonNull(filter);
-final ReentrantLock lock = this.lock;
-lock.lock();
-try {
-@SuppressWarnings("unchecked")
-final E[] elements = (E[]) getArray();
-// figure out which elements are to be removed
-// any exception thrown from the filter predicate at this stage
-// will leave the collection unmodified
-int removeCount = 0;
-final int range = to - from;
-final BitSet removeSet = new BitSet(range);
-for (int i = 0; i < range; i++) {
-final E element = elements[from + i];
-if (filter.test(element)) {
-// removeSet is zero-based to keep its size small
-removeSet.set(i);
-removeCount++;
-}
-}
-// copy surviving elements into a new array
-if (removeCount > 0) {
-final int newSize = elements.length - removeCount;
-final int newRange = newSize - from;
-@SuppressWarnings("unchecked")
-final E[] newElements = (E[]) new Object[newSize];
-// copy elements before [from, to) unmodified
-for (int i = 0; i < from; i++) {
-newElements[i] = elements[i];
-}
-// elements [from, to) are subject to removal
-int j = 0;
-for (int i = 0; (i < range) && (j < newRange); i++) {
-i = removeSet.nextClearBit(i);
-if (i >= range) {
-break;
-}
-newElements[from + (j++)] = elements[from + i];
-}
-// copy any remaining elements beyond [from, to)
-j += from;
-for (int i = to; (i < elements.length) && (j < newSize); i++) {
-newElements[j++] = elements[i];
-}
-setArray(newElements);
-}
-return removeCount;
-} finally {
-lock.unlock();
-}
-}
-@Override
-public void replaceAll(UnaryOperator<E> operator) {
-Objects.requireNonNull(operator);
-final ReentrantLock lock = this.lock;
-lock.lock();
-try {
-replaceAll(operator, 0, size());
-} finally {
-lock.unlock();
-}
-}
-// must be called with this.lock held
-@SuppressWarnings("unchecked")
-private void replaceAll(UnaryOperator<E> operator, final int from, final int to) {
-final E[] elements = (E[]) getArray();
-final E[] newElements = (E[]) new Object[elements.length];
-for (int i = 0; i < from; i++) {
-newElements[i] = elements[i];
-}
-// the operator is only applied to elements [from, to)
-for (int i = from; i < to; i++) {
-newElements[i] = operator.apply(elements[i]);
-}
-for (int i = to; i < elements.length; i++) {
-newElements[i] = elements[i];
-}
-setArray(newElements);
-}
 }

changeset 18767	6214297bf27d
parent 17180	f568bc4ece21
child 19428	83f87aff7b07