You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by hi...@apache.org on 2009/07/28 11:30:48 UTC
svn commit: r798469 [7/28] - in /harmony/enhanced/classlib/branches/java6:
./ depends/build/platform/ depends/files/ depends/jars/
depends/manifests/icu4j_4.0/ depends/manifests/icu4j_4.2.1/
depends/manifests/icu4j_4.2.1/META-INF/ make/ modules/accessi...
Modified: harmony/enhanced/classlib/branches/java6/modules/concurrent/src/main/java/java/util/concurrent/CopyOnWriteArrayList.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/branches/java6/modules/concurrent/src/main/java/java/util/concurrent/CopyOnWriteArrayList.java?rev=798469&r1=798468&r2=798469&view=diff
==============================================================================
--- harmony/enhanced/classlib/branches/java6/modules/concurrent/src/main/java/java/util/concurrent/CopyOnWriteArrayList.java (original)
+++ harmony/enhanced/classlib/branches/java6/modules/concurrent/src/main/java/java/util/concurrent/CopyOnWriteArrayList.java Tue Jul 28 09:30:33 2009
@@ -1,1174 +1,1317 @@
/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with this
- * work for additional information regarding copyright ownership. The ASF
- * licenses this file to you 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
- *
- * 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.
+ * Written by Doug Lea with assistance from members of JCP JSR-166
+ * Expert Group. Adapted and released, under explicit permission,
+ * from JDK ArrayList.java which carries the following copyright:
+ *
+ * Copyright 1997 by Sun Microsystems, Inc.,
+ * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
+ * All rights reserved.
+ *
+ * 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.
*/
package java.util.concurrent;
-
-import java.io.IOException;
-import java.io.ObjectInputStream;
-import java.io.ObjectOutputStream;
-import java.io.Serializable;
+import java.util.*;
+import java.util.concurrent.locks.*;
import java.lang.reflect.Array;
-import java.util.Collection;
-import java.util.ConcurrentModificationException;
-import java.util.Iterator;
-import java.util.List;
-import java.util.ListIterator;
-import java.util.NoSuchElementException;
-import java.util.RandomAccess;
-import java.util.concurrent.locks.ReentrantLock;
+
+import sun.misc.Unsafe;
/**
- * Implements a {@link java.util.ArrayList} variant that is thread-safe. All
- * write operation result in a new copy of the underlying data being created.
- * Iterators reflect the state of the CopyOnWriteArrayList at the time they were
- * created. They are not updated to reflect subsequent changes to the list. In
- * addition, these iterators cannot be used for modifying the underlying
- * CopyOnWriteArrayList.
+ * 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
+ * making a fresh copy of the underlying array.
+ *
+ * <p> This is ordinarily too costly, but may be <em>more</em> efficient
+ * than alternatives when traversal operations vastly outnumber
+ * mutations, and is useful when you cannot or don't want to
+ * synchronize traversals, yet need to preclude interference among
+ * concurrent threads. The "snapshot" style iterator method uses a
+ * reference to the state of the array at the point that the iterator
+ * was created. This array never changes during the lifetime of the
+ * iterator, so interference is impossible and the iterator is
+ * guaranteed not to throw <tt>ConcurrentModificationException</tt>.
+ * 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
+ * <tt>add</tt>) are not supported. These methods throw
+ * <tt>UnsupportedOperationException</tt>.
+ *
+ * <p>All elements are permitted, including <tt>null</tt>.
+ *
+ * <p>Memory consistency effects: As with other concurrent
+ * collections, actions in a thread prior to placing an object into a
+ * {@code CopyOnWriteArrayList}
+ * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a>
+ * actions subsequent to the access or removal of that element from
+ * the {@code CopyOnWriteArrayList} in another thread.
+ *
+ * <p>This class is a member of the
+ * <a href="{@docRoot}/../technotes/guides/collections/index.html">
+ * Java Collections Framework</a>.
*
- * @param <E> the element type
+ * @since 1.5
+ * @author Doug Lea
+ * @param <E> the type of elements held in this collection
*/
-public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, Serializable {
-
+public class CopyOnWriteArrayList<E>
+ implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
private static final long serialVersionUID = 8673264195747942595L;
- private transient volatile E[] arr;
+ /** The lock protecting all mutators */
+ transient final ReentrantLock lock = new ReentrantLock();
+
+ /** The array, accessed only via getArray/setArray. */
+ private volatile transient Object[] array;
+
+ /**
+ * Gets the array. Non-private so as to also be accessible
+ * from CopyOnWriteArraySet class.
+ */
+ final Object[] getArray() {
+ return array;
+ }
/**
- * Lock for the queue write methods
+ * Sets the array.
*/
- private final transient ReentrantLock lock = new ReentrantLock();
+ final void setArray(Object[] a) {
+ array = a;
+ }
/**
- * Creates a new, empty instance of CopyOnWriteArrayList.
+ * Creates an empty list.
*/
public CopyOnWriteArrayList() {
+ setArray(new Object[0]);
}
/**
- * Creates a new instance of CopyOnWriteArrayList and fills it with the
- * contents of a given Collection.
+ * 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 the elements of which are to be copied into
- * the new instance.
+ * @param c the collection of initially held elements
+ * @throws NullPointerException if the specified collection is null
*/
public CopyOnWriteArrayList(Collection<? extends E> c) {
- this((E[]) c.toArray());
+ Object[] elements = c.toArray();
+ // c.toArray might (incorrectly) not return Object[] (see 6260652)
+ if (elements.getClass() != Object[].class)
+ elements = Java6Arrays.copyOf(elements, elements.length, Object[].class);
+ setArray(elements);
}
/**
- * Creates a new instance of CopyOnWriteArrayList and fills it with the
- * contents of a given array.
+ * Creates a list holding a copy of the given array.
*
- * @param array the array the elements of which are to be copied into the
- * new instance.
+ * @param toCopyIn the array (a copy of this array is used as the
+ * internal array)
+ * @throws NullPointerException if the specified array is null
*/
- public CopyOnWriteArrayList(E[] array) {
- int size = array.length;
- E[] data = newElementArray(size);
- for (int i = 0; i < size; i++) {
- data[i] = array[i];
- }
- arr = data;
- }
-
- public boolean add(E e) {
- lock.lock();
- try {
- E[] data;
- E[] old = getData();
- int size = old.length;
- data = newElementArray(size + 1);
- System.arraycopy(old, 0, data, 0, size);
- data[size] = e;
- setData(data);
- return true;
- } finally {
- lock.unlock();
- }
- }
-
- public void add(int index, E e) {
- lock.lock();
- try {
- E[] data;
- E[] old = getData();
- int size = old.length;
- checkIndexInclusive(index, size);
- data = newElementArray(size+1);
- System.arraycopy(old, 0, data, 0, index);
- data[index] = e;
- if (size > index) {
- System.arraycopy(old, index, data, index + 1, size - index);
- }
- setData(data);
- } finally {
- lock.unlock();
- }
- }
-
- public boolean addAll(Collection<? extends E> c) {
- Iterator it = c.iterator();
- int ssize = c.size();
- lock.lock();
- try {
- int size = size();
- E[] data;
- E[] old = getData();
- int nSize = size + ssize;
- data = newElementArray(nSize);
- System.arraycopy(old, 0, data, 0, size);
- while (it.hasNext()) {
- data[size++] = (E) it.next();
- }
- setData(data);
- } finally {
- lock.unlock();
- }
- return true;
- }
-
- public boolean addAll(int index, Collection<? extends E> c) {
- Iterator it = c.iterator();
- int ssize = c.size();
- lock.lock();
- try {
- int size = size();
- checkIndexInclusive(index, size);
- E[] data;
- E[] old = getData();
- int nSize = size + ssize;
- data = newElementArray(nSize);
- System.arraycopy(old, 0, data, 0, index);
- int i = index;
- while (it.hasNext()) {
- data[i++] = (E) it.next();
- }
- if (size > index) {
- System.arraycopy(old, index, data, index + ssize, size - index);
- }
- setData(data);
- } finally {
- lock.unlock();
- }
- return true;
+ public CopyOnWriteArrayList(E[] toCopyIn) {
+ setArray(Java6Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}
/**
- * Adds to this CopyOnWriteArrayList all those elements from a given
- * collection that are not yet part of the list.
- *
- * @param c the collection from which the potential new elements are
- * taken.
+ * Returns the number of elements in this list.
*
- * @return the number of elements actually added to this list.
+ * @return the number of elements in this list
*/
- public int addAllAbsent(Collection<? extends E> c) {
- if (c.size() == 0) {
- return 0;
- }
- lock.lock();
- try {
- E[] old = getData();
- int size = old.length;
- E[] toAdd = newElementArray(c.size());
- int i = 0;
- for (Iterator it = c.iterator(); it.hasNext();) {
- E o = (E) it.next();
- if (indexOf(o) < 0) {
- toAdd[i++] = o;
- }
- }
- E[] data = newElementArray(size + i);
- System.arraycopy(old, 0, data, 0, size);
- System.arraycopy(toAdd, 0, data, size, i);
- setData(data);
- return i;
- } finally {
- lock.unlock();
- }
+ public int size() {
+ return getArray().length;
}
/**
- * Adds to this CopyOnWriteArrayList another element, given that this
- * element is not yet part of the list.
+ * Returns <tt>true</tt> if this list contains no elements.
*
- * @param e the potential new element.
- *
- * @return true if the element was added, or false otherwise.
+ * @return <tt>true</tt> if this list contains no elements
*/
- public boolean addIfAbsent(E e) {
- lock.lock();
- try {
- E[] data;
- E[] old = getData();
- int size = old.length;
- if (size != 0) {
- if (indexOf(e) >= 0) {
- return false;
- }
- }
- data = newElementArray(size + 1);
- System.arraycopy(old, 0, data, 0, size);
- data[size] = e;
- setData(data);
- return true;
- } finally {
- lock.unlock();
- }
+ public boolean isEmpty() {
+ return size() == 0;
}
- public void clear() {
- lock.lock();
- try {
- setData(newElementArray(0));
- } finally {
- lock.unlock();
- }
+ /**
+ * Test for equality, coping with nulls.
+ */
+ private static boolean eq(Object o1, Object o2) {
+ return (o1 == null ? o2 == null : o1.equals(o2));
}
- @Override
- public Object clone() {
- try {
- CopyOnWriteArrayList thisClone = (CopyOnWriteArrayList) super.clone();
- thisClone.setData(this.getData());
- return thisClone;
- } catch (CloneNotSupportedException e) {
- throw new RuntimeException("CloneNotSupportedException is not expected here");
+ /**
+ * 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;
}
- public boolean contains(Object o) {
- return indexOf(o) >= 0;
- }
-
- public boolean containsAll(Collection<?> c) {
- E[] data = getData();
- return containsAll(c, data, 0, data.length);
- }
-
- public boolean equals(Object o) {
- if (o == this) {
- return true;
- }
- if (!(o instanceof List)) {
- return false;
- }
- List l = (List) o;
- Iterator it = l.listIterator();
- Iterator ourIt = listIterator();
- while (it.hasNext()) {
- if (!ourIt.hasNext()) {
- return false;
- }
- Object thisListElem = it.next();
- Object anotherListElem = ourIt.next();
- if (!(thisListElem == null ? anotherListElem == null : thisListElem
- .equals(anotherListElem))) {
- return false;
- }
- }
- if (ourIt.hasNext()) {
- return false;
+ /**
+ * 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 true;
+ return -1;
}
- public E get(int index) {
- E[] data = getData();
- return data[index];
+ /**
+ * Returns <tt>true</tt> if this list contains the specified element.
+ * More formally, returns <tt>true</tt> if and only if this list contains
+ * at least one element <tt>e</tt> such that
+ * <tt>(o==null ? e==null : 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
+ */
+ public boolean contains(Object o) {
+ Object[] elements = getArray();
+ return indexOf(o, elements, 0, elements.length) >= 0;
}
- public int hashCode() {
- int hashCode = 1;
- Iterator it = listIterator();
- while (it.hasNext()) {
- Object obj = it.next();
- hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode());
- }
- return hashCode;
+ /**
+ * {@inheritDoc}
+ */
+ public int indexOf(Object o) {
+ Object[] elements = getArray();
+ return indexOf(o, elements, 0, elements.length);
}
/**
- * Returns the index of a given element, starting the search from a given
- * position in the list.
- *
- * @param e the element to search.
- * @param index the index at which to start the search.
- *
- * @return the index of the element or null, if the element has not been
- * found at or beyond the given start index.
+ * Returns the index of the first occurrence of the specified element in
+ * this list, searching forwards from <tt>index</tt>, or returns -1 if
+ * the element is not found.
+ * More formally, returns the lowest index <tt>i</tt> such that
+ * <tt>(i >= index && (e==null ? get(i)==null : 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;
+ * <tt>-1</tt> if the element is not found.
+ * @throws IndexOutOfBoundsException if the specified index is negative
*/
public int indexOf(E e, int index) {
- E[] data = getData();
- return indexOf(e, data, index, data.length - index);
+ Object[] elements = getArray();
+ return indexOf(e, elements, index, elements.length);
}
- public int indexOf(Object o) {
- E[] data = getData();
- return indexOf(o, data, 0, data.length);
+ /**
+ * {@inheritDoc}
+ */
+ public int lastIndexOf(Object o) {
+ Object[] elements = getArray();
+ return lastIndexOf(o, elements, elements.length - 1);
}
- public boolean isEmpty() {
- return size() == 0;
+ /**
+ * Returns the index of the last occurrence of the specified element in
+ * this list, searching backwards from <tt>index</tt>, or returns -1 if
+ * the element is not found.
+ * More formally, returns the highest index <tt>i</tt> such that
+ * <tt>(i <= index && (e==null ? get(i)==null : 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;
+ * -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);
}
- public Iterator<E> iterator() {
- return new ListIteratorImpl(getData(), 0);
+ /**
+ * Returns a shallow copy of this list. (The elements themselves
+ * are not copied.)
+ *
+ * @return a clone of this list
+ */
+ public Object clone() {
+ try {
+ CopyOnWriteArrayList c = (CopyOnWriteArrayList)(super.clone());
+ c.resetLock();
+ return c;
+ } catch (CloneNotSupportedException e) {
+ // this shouldn't happen, since we are Cloneable
+ throw new InternalError();
+ }
}
/**
- * Returns the last index of a given element, starting the search from
- * a given position in the list and going backwards.
+ * 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.
*
- * @param e the element to search.
- * @param index the index at which to start the search.
+ * <p>This method acts as bridge between array-based and collection-based
+ * APIs.
*
- * @return the index of the element or null, if the element has not been
- * found at or before the given start index.
+ * @return an array containing all the elements in this list
*/
- public int lastIndexOf(E e, int index) {
- E[] data = getData();
- return lastIndexOf(e, data, 0, index);
+ public Object[] toArray() {
+ Object[] elements = getArray();
+ return Java6Arrays.copyOf(elements, elements.length);
}
- public int lastIndexOf(Object o) {
- E[] data = getData();
- return lastIndexOf(o, data, 0, data.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
+ * <tt>null</tt>. (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.
+ * The following code can be used to dump the list into a newly
+ * allocated array of <tt>String</tt>:
+ *
+ * <pre>
+ * String[] y = x.toArray(new String[0]);</pre>
+ *
+ * Note that <tt>toArray(new Object[0])</tt> is identical in function to
+ * <tt>toArray()</tt>.
+ *
+ * @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[]) Java6Arrays.copyOf(elements, len, a.getClass());
+ else {
+ System.arraycopy(elements, 0, a, 0, len);
+ if (a.length > len)
+ a[len] = null;
+ return a;
+ }
}
- public ListIterator<E> listIterator() {
- return new ListIteratorImpl(getData(), 0);
- }
+ // Positional Access Operations
- public ListIterator<E> listIterator(int index) {
- E[] data = getData();
- checkIndexInclusive(index, data.length);
- return new ListIteratorImpl(data, index);
+ @SuppressWarnings("unchecked")
+ private E get(Object[] a, int index) {
+ return (E) a[index];
}
- public E remove(int index) {
- return removeRange(index, 1);
+ /**
+ * {@inheritDoc}
+ *
+ * @throws IndexOutOfBoundsException {@inheritDoc}
+ */
+ public E get(int index) {
+ return get(getArray(), index);
}
- public boolean remove(Object o) {
+ /**
+ * Replaces the element at the specified position in this list with the
+ * specified element.
+ *
+ * @throws IndexOutOfBoundsException {@inheritDoc}
+ */
+ public E set(int index, E element) {
+ final ReentrantLock lock = this.lock;
lock.lock();
try {
- int index = indexOf(o);
- if (index == -1) {
- return false;
+ Object[] elements = getArray();
+ E oldValue = get(elements, index);
+
+ if (oldValue != element) {
+ int len = elements.length;
+ Object[] newElements = Java6Arrays.copyOf(elements, len);
+ newElements[index] = element;
+ setArray(newElements);
+ } else {
+ // Not quite a no-op; ensures volatile write semantics
+ setArray(elements);
}
- remove(index);
- return true;
+ return oldValue;
} finally {
lock.unlock();
}
}
- public boolean removeAll(Collection<?> c) {
+ /**
+ * 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})
+ */
+ public boolean add(E e) {
+ final ReentrantLock lock = this.lock;
lock.lock();
try {
- return removeAll(c, 0, getData().length) != 0;
+ Object[] elements = getArray();
+ int len = elements.length;
+ Object[] newElements = Java6Arrays.copyOf(elements, len + 1);
+ newElements[len] = e;
+ setArray(newElements);
+ return true;
} finally {
lock.unlock();
}
}
- public boolean retainAll(Collection<?> c) {
- if (c == null) {
- throw new NullPointerException();
- }
+ /**
+ * 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) {
+ final ReentrantLock lock = this.lock;
lock.lock();
try {
- return retainAll(c, 0, getData().length) != 0;
+ Object[] elements = getArray();
+ int len = elements.length;
+ if (index > len || index < 0)
+ throw new IndexOutOfBoundsException("Index: "+index+
+ ", Size: "+len);
+ Object[] newElements;
+ int numMoved = len - index;
+ if (numMoved == 0)
+ newElements = Java6Arrays.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);
} finally {
lock.unlock();
}
}
- public E set(int index, E e) {
+ /**
+ * 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) {
+ final ReentrantLock lock = this.lock;
lock.lock();
try {
- int size = size();
- checkIndexExlusive(index, size);
- E[] data;
- data = newElementArray(size);
- E[] oldArr = getData();
- System.arraycopy(oldArr, 0, data, 0, size);
- E old = data[index];
- data[index] = e;
- setData(data);
- return old;
+ Object[] elements = getArray();
+ int len = elements.length;
+ E oldValue = get(elements, index);
+ int numMoved = len - index - 1;
+ if (numMoved == 0)
+ setArray(Java6Arrays.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;
} finally {
lock.unlock();
}
}
- public int size() {
- return getData().length;
- }
-
- public List<E> subList(int fromIndex, int toIndex) {
- return new SubList(this, fromIndex, toIndex);
- }
-
- public Object[] toArray() {
- E[] data = getData();
- return toArray(data, 0, data.length);
- }
-
- public <T> T[] toArray(T[] a) {
- E[] data = getData();
- return (T[]) toArray(a, data, 0, data.length);
- }
-
- @Override
- public String toString() {
- StringBuilder sb = new StringBuilder("[");
+ /**
+ * 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
+ * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
+ * (if such an element exists). Returns <tt>true</tt> 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
+ */
+ public boolean remove(Object o) {
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ Object[] elements = getArray();
+ int len = elements.length;
+ if (len != 0) {
+ // Copy while searching for element to remove
+ // This wins in the normal case of element being present
+ int newlen = len - 1;
+ Object[] newElements = new Object[newlen];
+
+ 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];
+ }
- Iterator it = listIterator();
- while (it.hasNext()) {
- sb.append(String.valueOf(it.next()));
- sb.append(", ");
- }
- if (sb.length() > 1) {
- sb.setLength(sb.length() - 2);
+ // special handling for last cell
+ if (eq(o, elements[newlen])) {
+ setArray(newElements);
+ return true;
+ }
+ }
+ return false;
+ } finally {
+ lock.unlock();
}
- sb.append("]");
- return sb.toString();
}
- // private and package private methods
+ /**
+ * Removes from this list all of the elements whose index is between
+ * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
+ * Shifts any succeeding elements to the left (reduces their index).
+ * This call shortens the list by <tt>(toIndex - fromIndex)</tt> elements.
+ * (If <tt>toIndex==fromIndex</tt>, 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})
+ */
+ private void removeRange(int fromIndex, int toIndex) {
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ Object[] elements = getArray();
+ int len = elements.length;
- @SuppressWarnings("unchecked")
- private final E[] newElementArray(int size) {
- return (E[])new Object[size];
+ if (fromIndex < 0 || toIndex > len || toIndex < fromIndex)
+ throw new IndexOutOfBoundsException();
+ int newlen = len - (toIndex - fromIndex);
+ int numMoved = len - toIndex;
+ if (numMoved == 0)
+ setArray(Java6Arrays.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);
+ }
+ } finally {
+ lock.unlock();
+ }
}
/**
- * sets the internal data array
+ * Append the element if not present.
*
- * @param data array to set
+ * @param e element to be added to this list, if absent
+ * @return <tt>true</tt> if the element was added
*/
- private final void setData(E[] data) {
- arr = data;
+ public boolean addIfAbsent(E e) {
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ // Copy while checking if already present.
+ // This wins in the most common case where it is not present
+ Object[] elements = getArray();
+ int len = elements.length;
+ Object[] newElements = new Object[len + 1];
+ for (int i = 0; i < len; ++i) {
+ if (eq(e, elements[i]))
+ return false; // exit, throwing away copy
+ else
+ newElements[i] = elements[i];
+ }
+ newElements[len] = e;
+ setArray(newElements);
+ return true;
+ } finally {
+ lock.unlock();
+ }
}
/**
- * gets the internal data array
+ * Returns <tt>true</tt> if this list contains all of the elements of the
+ * specified collection.
*
- * @return the data array
+ * @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
+ * specified collection
+ * @throws NullPointerException if the specified collection is null
+ * @see #contains(Object)
*/
- final E[] getData() {
- if (arr == null) {
- return newElementArray(0);
+ public boolean containsAll(Collection<?> c) {
+ Object[] elements = getArray();
+ int len = elements.length;
+ for (Object e : c) {
+ if (indexOf(e, elements, 0, len) < 0)
+ return false;
}
- return arr;
+ return true;
}
/**
- * Removes from the specified range of this list
- * all the elements that are contained in the specified collection
- * <p/>
- * !should be called under lock
- *
- * @return Returns the number of removed elements
+ * 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
+ * @throws ClassCastException if the class of an element of this list
+ * is incompatible with the specified collection (optional)
+ * @throws NullPointerException if this list contains a null element and the
+ * specified collection does not permit null elements (optional),
+ * or if the specified collection is null
+ * @see #remove(Object)
*/
- final int removeAll(Collection c, int start, int size) {
- int ssize = c.size();
- if (ssize == 0) {
- return 0;
- }
- Object[] old = getData();
- int arrsize = old.length;
- if (arrsize == 0) {
- return 0;
- }
- Object[] data = new Object[size];
- int j = 0;
- for (int i = start; i < (start + size); i++) {
- if (!c.contains(old[i])) {
- data[j++] = old[i];
+ public boolean removeAll(Collection<?> c) {
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ 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(Java6Arrays.copyOf(temp, newlen));
+ return true;
+ }
}
+ return false;
+ } finally {
+ lock.unlock();
}
- if (j != size) {
- E[] result = newElementArray(arrsize - (size - j));
- System.arraycopy(old, 0, result, 0, start);
- System.arraycopy(data, 0, result, start, j);
- System.arraycopy(old, start + size, result, start + j, arrsize
- - (start + size));
- setData(result);
- return (size - j);
- }
- return 0;
}
/**
- * Retains only the elements in the specified range of this list
- * that are contained in the specified collection
- *
- * @return Returns the number of removed 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
+ * @throws ClassCastException if the class of an element of this list
+ * is incompatible with the specified collection (optional)
+ * @throws NullPointerException if this list contains a null element and the
+ * specified collection does not permit null elements (optional),
+ * or if the specified collection is null
+ * @see #remove(Object)
*/
- // should be called under lock
- int retainAll(Collection c, int start, int size) {
- Object[] old = getData();
- if (size == 0) {
- return 0;
- }
- if (c.size() == 0) {
- E[] data;
- if (size == old.length) {
- data = newElementArray(0);
- } else {
- data = newElementArray(old.length - size);
- System.arraycopy(old, 0, data, 0, start);
- System.arraycopy(old, start + size, data, start, old.length
- - start - size);
- }
- setData(data);
- return size;
- }
- Object[] temp = new Object[size];
- int pos = 0;
- for (int i = start; i < (start + size); i++) {
- if (c.contains(old[i])) {
- temp[pos++] = old[i];
+ public boolean retainAll(Collection<?> c) {
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ 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(Java6Arrays.copyOf(temp, newlen));
+ return true;
+ }
}
+ return false;
+ } finally {
+ lock.unlock();
}
- if (pos == size) {
- return 0;
- }
- E[] data = newElementArray(pos + old.length - size);
- System.arraycopy(old, 0, data, 0, start);
- System.arraycopy(temp, 0, data, start, pos);
- System.arraycopy(old, start + size, data, start + pos, old.length
- - start - size);
- setData(data);
- return (size - pos);
}
/**
- * Removes specified range from this list
+ * Appends all of the elements in the specified collection that
+ * are not already contained in this list, to the end of
+ * this list, in the order that they are returned by the
+ * specified collection's iterator.
+ *
+ * @param c collection containing elements to be added to this list
+ * @return the number of elements added
+ * @throws NullPointerException if the specified collection is null
+ * @see #addIfAbsent(Object)
*/
- E removeRange(int start, int size) {
+ 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 {
- int sizeArr = size();
- checkIndexExlusive(start, sizeArr);
- checkIndexInclusive(start + size, sizeArr);
- E[] data;
- data = newElementArray(sizeArr - size);
- E[] oldArr = getData();
- System.arraycopy(oldArr, 0, data, 0, start);
- E old = oldArr[start];
- if (sizeArr > (start + size)) {
- System.arraycopy(oldArr, start + size, data, start, sizeArr
- - (start + size));
+ Object[] elements = getArray();
+ int len = elements.length;
+ int added = 0;
+ for (int i = 0; i < cs.length; ++i) { // scan for duplicates
+ Object e = cs[i];
+ if (indexOf(e, elements, 0, len) < 0 &&
+ indexOf(e, uniq, 0, added) < 0)
+ uniq[added++] = e;
+ }
+ if (added > 0) {
+ Object[] newElements = Java6Arrays.copyOf(elements, len + added);
+ System.arraycopy(uniq, 0, newElements, len, added);
+ setArray(newElements);
}
- setData(data);
- return old;
+ return added;
} finally {
lock.unlock();
}
}
- // some util static functions to use by iterators and methods
/**
- * Returns an array containing all of the elements
- * in the specified range of the array in proper sequence
+ * Removes all of the elements from this list.
+ * The list will be empty after this call returns.
*/
- static Object[] toArray(Object[] data, int start, int size) {
- Object[] result = new Object[size];
- System.arraycopy(data, start, result, 0, size);
- return result;
+ public void clear() {
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ setArray(new Object[0]);
+ } finally {
+ lock.unlock();
+ }
}
/**
- * Returns an array containing all of the elements
- * in the specified range of the array in proper sequence,
- * stores the result in the array, specified by first parameter
- * (as for public instance method toArray(Object[] to)
+ * 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
+ * @throws NullPointerException if the specified collection is null
+ * @see #add(Object)
*/
- static Object[] toArray(Object[] to, Object[] data, int start, int size) {
- int l = data.length;
- if (to.length < l) {
- to = (Object[]) Array.newInstance(to.getClass().getComponentType(),
- l);
- } else {
- if (to.length > l) {
- to[l] = null;
- }
+ public boolean addAll(Collection<? extends E> c) {
+ Object[] cs = 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 = Java6Arrays.copyOf(elements, len + cs.length);
+ System.arraycopy(cs, 0, newElements, len, cs.length);
+ setArray(newElements);
+ return true;
+ } finally {
+ lock.unlock();
}
- System.arraycopy(data, start, to, 0, size);
- return to;
}
/**
- * Checks if the specified range of the
- * array contains all of the elements in the collection
- *
- * @param c collection with elements
- * @param data array where to search the elements
- * @param start start index
- * @param size size of the range
+ * 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 <tt>true</tt> 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)
*/
- static final boolean containsAll(Collection c, Object[] data, int start,
- int size) {
- if (size == 0) {
- return false;
- }
- Iterator it = c.iterator();
- while (it.hasNext()) {
- Object next = it.next();
- if (indexOf(next, data, start, size) < 0) {
+ public boolean addAll(int index, Collection<? extends E> c) {
+ Object[] cs = c.toArray();
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ Object[] elements = getArray();
+ int len = elements.length;
+ if (index > len || index < 0)
+ throw new IndexOutOfBoundsException("Index: "+index+
+ ", Size: "+len);
+ if (cs.length == 0)
return false;
+ int numMoved = len - index;
+ Object[] newElements;
+ if (numMoved == 0)
+ newElements = Java6Arrays.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;
+ } finally {
+ lock.unlock();
}
- return true;
}
/**
- * Returns the index in the specified range of the data array
- * of the last occurrence of the specified element
+ * Save the state of the list to a stream (i.e., serialize it).
*
- * @param o element to search
- * @param data array where to search
- * @param start start index
- * @param size size of the range
- * @return
- */
- static final int lastIndexOf(Object o, Object[] data, int start, int size) {
- if (size == 0) {
- return -1;
- }
- if (o != null) {
- for (int i = start + size - 1; i > start - 1; i--) {
- if (o.equals(data[i])) {
- return i;
- }
- }
- } else {
- for (int i = start + size - 1; i > start - 1; i--) {
- if (data[i] == null) {
- return i;
- }
- }
- }
- return -1;
+ * @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.
+ * @param s the stream
+ */
+ private void writeObject(java.io.ObjectOutputStream s)
+ throws java.io.IOException{
+
+ // Write out element count, and any hidden stuff
+ s.defaultWriteObject();
+
+ Object[] elements = getArray();
+ int len = elements.length;
+ // Write out array length
+ s.writeInt(len);
+
+ // Write out all elements in the proper order.
+ for (int i = 0; i < len; i++)
+ s.writeObject(elements[i]);
+ }
+
+ /**
+ * Reconstitute the list from a stream (i.e., deserialize it).
+ * @param s the stream
+ */
+ private void readObject(java.io.ObjectInputStream s)
+ throws java.io.IOException, ClassNotFoundException {
+
+ // Read in size, and any hidden stuff
+ 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 the index in the specified range of the data array
- * of the first occurrence of the specified element
+ * 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
+ * the characters <tt>", "</tt> (comma and space). Elements are
+ * converted to strings as by {@link String#valueOf(Object)}.
*
- * @param o element to search
- * @param data array where to search
- * @param start start index
- * @param size end index
- * @return
- */
- static final int indexOf(Object o, Object[] data, int start, int size) {
- if (size == 0) {
- return -1;
- }
- if (o == null) {
- for (int i = start; i < start + size; i++) {
- if (data[i] == null) {
- return i;
- }
- }
- } else {
- for (int i = start; i < start + size; i++) {
- if (o.equals(data[i])) {
- return i;
- }
- }
- }
- return -1;
+ * @return a string representation of this list
+ */
+ public String toString() {
+ return Arrays.toString(getArray());
}
/**
- * Throws <code>IndexOutOfBoundsException</code> if <code>index</code>
- * is out of the list bounds.
+ * 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 (e1==null ? e2==null : e1.equals(e2))}.
*
- * @param index element index to check.
+ * @param o the object to be compared for equality with this list
+ * @return {@code true} if the specified object is equal to this list
*/
- static final void checkIndexInclusive(int index, int size) {
- if (index < 0 || index > size) {
- throw new IndexOutOfBoundsException("Index is " + index + ", size is " + size);
- }
+ 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();
+ int len = elements.length;
+ for (int i = 0; i < len; ++i)
+ if (!it.hasNext() || !eq(elements[i], it.next()))
+ return false;
+ if (it.hasNext())
+ return false;
+ return true;
}
/**
- * Throws <code>IndexOutOfBoundsException</code> if <code>index</code>
- * is out of the list bounds. Excluding the last element.
+ * Returns the hash code value for this list.
+ *
+ * <p>This implementation uses the definition in {@link List#hashCode}.
*
- * @param index element index to check.
+ * @return the hash code value for this list
*/
- static final void checkIndexExlusive(int index, int size) {
- if (index < 0 || index >= size) {
- throw new IndexOutOfBoundsException("Index is " + index + ", size is " + size);
+ public int hashCode() {
+ int hashCode = 1;
+ Object[] elements = getArray();
+ int len = elements.length;
+ for (int i = 0; i < len; ++i) {
+ Object obj = elements[i];
+ hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
}
+ return hashCode;
}
/**
- * list iterator implementation,
- * when created gets snapshot of the list,
- * so never throws ConcurrentModificationException
+ * 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.
+ *
+ * @return an iterator over the elements in this list in proper sequence
*/
- private static class ListIteratorImpl implements ListIterator {
- private final Object[] arr;
+ public Iterator<E> iterator() {
+ return new COWIterator<E>(getArray(), 0);
+ }
- private int current;
+ /**
+ * {@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.
+ */
+ public ListIterator<E> listIterator() {
+ return new COWIterator<E>(getArray(), 0);
+ }
- private final int size;
+ /**
+ * {@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.
+ *
+ * @throws IndexOutOfBoundsException {@inheritDoc}
+ */
+ public ListIterator<E> listIterator(final int index) {
+ Object[] elements = getArray();
+ int len = elements.length;
+ if (index<0 || index>len)
+ throw new IndexOutOfBoundsException("Index: "+index);
- final int size() {
- return size;
- }
+ return new COWIterator<E>(elements, index);
+ }
- public ListIteratorImpl(Object[] data, int current) {
- this.current = current;
- arr = data;
- size = data.length;
- }
+ private static 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;
- public void add(Object o) {
- throw new UnsupportedOperationException("Unsupported operation add");
+ private COWIterator(Object[] elements, int initialCursor) {
+ cursor = initialCursor;
+ snapshot = elements;
}
public boolean hasNext() {
- if (current < size) {
- return true;
- }
- return false;
+ return cursor < snapshot.length;
}
public boolean hasPrevious() {
- return current > 0;
+ return cursor > 0;
}
- public Object next() {
- if (hasNext()) {
- return arr[current++];
- }
- throw new NoSuchElementException("pos is " + current + ", size is " + size);
+ @SuppressWarnings("unchecked")
+ public E next() {
+ if (! hasNext())
+ throw new NoSuchElementException();
+ return (E) snapshot[cursor++];
}
- public int nextIndex() {
- return current;
+ @SuppressWarnings("unchecked")
+ public E previous() {
+ if (! hasPrevious())
+ throw new NoSuchElementException();
+ return (E) snapshot[--cursor];
}
- public Object previous() {
- if (hasPrevious()) {
- return arr[--current];
- }
- throw new NoSuchElementException("pos is " + (current-1) + ", size is " + size);
+ public int nextIndex() {
+ return cursor;
}
public int previousIndex() {
- return current - 1;
+ return cursor-1;
}
+ /**
+ * Not supported. Always throws UnsupportedOperationException.
+ * @throws UnsupportedOperationException always; <tt>remove</tt>
+ * is not supported by this iterator.
+ */
public void remove() {
- throw new UnsupportedOperationException("Unsupported operation remove");
+ throw new UnsupportedOperationException();
}
- public void set(Object o) {
- throw new UnsupportedOperationException("Unsupported operation set");
+ /**
+ * Not supported. Always throws UnsupportedOperationException.
+ * @throws UnsupportedOperationException always; <tt>set</tt>
+ * 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>
+ * is not supported by this iterator.
+ */
+ public void add(E e) {
+ throw new UnsupportedOperationException();
+ }
}
/**
- * Keeps a state of sublist implementation,
- * size and array declared as final,
- * so we'll never get the unconsistent state
+ * Returns a view of the portion of this list between
+ * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
+ * The returned list is backed by this list, so changes in the
+ * returned list are reflected in this list.
+ *
+ * <p>The semantics of the list returned by this method become
+ * undefined if the backing list (i.e., this list) is modified in
+ * any way other than via the returned list.
+ *
+ * @param fromIndex low endpoint (inclusive) of the subList
+ * @param toIndex high endpoint (exclusive) of the subList
+ * @return a view of the specified range within this list
+ * @throws IndexOutOfBoundsException {@inheritDoc}
*/
- static final class SubListReadData {
- final int size;
-
- final Object[] data;
-
- SubListReadData(int size, Object[] data) {
- this.size = size;
- this.data = data;
+ public List<E> subList(int fromIndex, int toIndex) {
+ final ReentrantLock lock = this.lock;
+ lock.lock();
+ try {
+ Object[] elements = getArray();
+ int len = elements.length;
+ if (fromIndex < 0 || toIndex > len || fromIndex > toIndex)
+ throw new IndexOutOfBoundsException();
+ return new COWSubList<E>(this, fromIndex, toIndex);
+ } finally {
+ lock.unlock();
}
}
/**
- * Represents a list returned by <code>sublist()</code>.
- */
- static class SubList implements List {
- private final CopyOnWriteArrayList list;
-
- private volatile SubListReadData read;
-
- private final int start;
-
- /**
- * Sublist constructor.
- *
- * @param list backing list.
- * @param fromIdx startingIndex, inclusive
- * @param toIdx endIndex, exclusive
- */
- public SubList(CopyOnWriteArrayList list, int fromIdx, int toIdx) {
- this.list = list;
- Object[] data = list.getData();
- int size = toIdx - fromIdx;
- checkIndexExlusive(fromIdx, data.length);
- checkIndexInclusive(toIdx, data.length);
- read = new SubListReadData(size, list.getData());
- start = fromIdx;
- }
-
- /**
- * throws ConcurrentModificationException when the list
- * is structurally modified in the other way other than via this subList
- * <p/>
- * Should be called under lock!
- */
- private void checkModifications() {
- if (read.data != list.getData()) {
+ * 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.
+ */
+ private static class COWSubList<E>
+ extends AbstractList<E>
+ implements RandomAccess
+ {
+ private final CopyOnWriteArrayList<E> l;
+ private final int offset;
+ private int size;
+ private Object[] expectedArray;
+
+ // only call this holding l's lock
+ COWSubList(CopyOnWriteArrayList<E> list,
+ int fromIndex, int toIndex) {
+ l = list;
+ expectedArray = l.getArray();
+ offset = fromIndex;
+ size = toIndex - fromIndex;
+ }
+
+ // only call this holding l's lock
+ private void checkForComodification() {
+ if (l.getArray() != expectedArray)
throw new ConcurrentModificationException();
- }
}
- /**
- * @see java.util.List#listIterator(int)
- */
- public ListIterator listIterator(int startIdx) {
- return new SubListIterator(startIdx, read);
+ // only call this holding l's lock
+ private void rangeCheck(int index) {
+ if (index<0 || index>=size)
+ throw new IndexOutOfBoundsException("Index: "+index+
+ ",Size: "+size);
}
- /**
- * @see java.util.List#set(int, java.lang.Object)
- */
- public Object set(int index, Object obj) {
- list.lock.lock();
+ public E set(int index, E element) {
+ final ReentrantLock lock = l.lock;
+ lock.lock();
try {
- checkIndexExlusive(index, read.size);
- checkModifications();
- Object result = list.set(index + start, obj);
- read = new SubListReadData(read.size, list.getData());
- return result;
+ rangeCheck(index);
+ checkForComodification();
+ E x = l.set(index+offset, element);
+ expectedArray = l.getArray();
+ return x;
} finally {
- list.lock.unlock();
+ lock.unlock();
}
}
- /**
- * @see java.util.List#get(int)
- */
- public Object get(int index) {
- SubListReadData data = read;
- if (data.data != list.getData()) {
- list.lock.lock();
- try {
- data = read;
- if (data.data != list.getData()) {
- throw new ConcurrentModificationException();
- }
- } finally {
- list.lock.unlock();
- }
- }
- checkIndexExlusive(index, data.size);
- return data.data[index + start];
- }
-
- /**
- * @see java.util.Collection#size()
- */
- public int size() {
- return read.size;
- }
-
- /**
- * @see java.util.List#remove(int)
- */
- public Object remove(int index) {
- list.lock.lock();
+ public E get(int index) {
+ final ReentrantLock lock = l.lock;
+ lock.lock();
try {
- checkIndexExlusive(index, read.size);
- checkModifications();
- Object obj = list.remove(index + start);
- read = new SubListReadData(read.size - 1, list.getData());
- return obj;
+ rangeCheck(index);
+ checkForComodification();
+ return l.get(index+offset);
} finally {
- list.lock.unlock();
+ lock.unlock();
}
}
- /**
- * @see java.util.List#add(int, java.lang.Object)
- */
- public void add(int index, Object object) {
- list.lock.lock();
+ public int size() {
+ final ReentrantLock lock = l.lock;
+ lock.lock();
try {
- checkIndexInclusive(index, read.size);
- checkModifications();
- list.add(index + start, object);
- read = new SubListReadData(read.size + 1, list.getData());
+ checkForComodification();
+ return size;
} finally {
- list.lock.unlock();
+ lock.unlock();
}
}
- public boolean add(Object o) {
- list.lock.lock();
+ public void add(int index, E element) {
+ final ReentrantLock lock = l.lock;
+ lock.lock();
try {
- checkModifications();
- list.add(start + read.size, o);
- read = new SubListReadData(read.size + 1, list.getData());
- return true;
+ checkForComodification();
+ if (index<0 || index>size)
+ throw new IndexOutOfBoundsException();
+ l.add(index+offset, element);
+ expectedArray = l.getArray();
+ size++;
} finally {
- list.lock.unlock();
+ lock.unlock();
}
}
- public boolean addAll(Collection c) {
- list.lock.lock();
+ public void clear() {
+ final ReentrantLock lock = l.lock;
+ lock.lock();
try {
- checkModifications();
- int d = list.size();
- list.addAll(start + read.size, c);
- read = new SubListReadData(read.size + (list.size() - d), list
- .getData());
- return true;
+ checkForComodification();
+ l.removeRange(offset, offset+size);
+ expectedArray = l.getArray();
+ size = 0;
} finally {
- list.lock.unlock();
+ lock.unlock();
}
}
- public void clear() {
- list.lock.lock();
+ public E remove(int index) {
+ final ReentrantLock lock = l.lock;
+ lock.lock();
try {
- checkModifications();
- list.removeRange(start, read.size);
- read = new SubListReadData(0, list.getData());
+ rangeCheck(index);
+ checkForComodification();
+ E result = l.remove(index+offset);
+ expectedArray = l.getArray();
+ size--;
+ return result;
} finally {
- list.lock.unlock();
+ lock.unlock();
}
}
- public boolean contains(Object o) {
- return indexOf(o) != -1;
- }
-
- public boolean containsAll(Collection c) {
- SubListReadData b = read;
- return CopyOnWriteArrayList.containsAll(c, b.data, start, b.size);
- }
-
- public int indexOf(Object o) {
- SubListReadData b = read;
- int ind = CopyOnWriteArrayList.indexOf(o, b.data, start, b.size)
- - start;
- return ind < 0 ? -1 : ind;
- }
-
- public boolean isEmpty() {
- return read.size == 0;
- }
-
- public Iterator iterator() {
- return new SubListIterator(0, read);
- }
-
- public int lastIndexOf(Object o) {
- SubListReadData b = read;
- int ind = CopyOnWriteArrayList
- .lastIndexOf(o, b.data, start, b.size)
- - start;
- return ind < 0 ? -1 : ind;
- }
-
- public ListIterator listIterator() {
- return new SubListIterator(0, read);
+ public boolean remove(Object o) {
+ int index = indexOf(o);
+ if (index == -1)
+ return false;
+ remove(index);
+ return true;
}
- public boolean remove(Object o) {
- list.lock.lock();
+ public Iterator<E> iterator() {
+ final ReentrantLock lock = l.lock;
+ lock.lock();
try {
- checkModifications();
- int i = indexOf(o);
- if (i == -1) {
- return false;
- }
- boolean result = list.remove(i + start) != null;
- if (result) {
- read = new SubListReadData(read.size - 1, list.getData());
- }
- return result;
+ checkForComodification();
+ return new COWSubListIterator<E>(l, 0, offset, size);
} finally {
- list.lock.unlock();
+ lock.unlock();
}
}
- public boolean removeAll(Collection c) {
- list.lock.lock();
+ public ListIterator<E> listIterator(final int index) {
+ final ReentrantLock lock = l.lock;
+ lock.lock();
try {
- checkModifications();
- int removed = list.removeAll(c, start, read.size);
- if (removed > 0) {
- read = new SubListReadData(read.size - removed, list
- .getData());
- return true;
- }
+ checkForComodification();
+ if (index<0 || index>size)
+ throw new IndexOutOfBoundsException("Index: "+index+
+ ", Size: "+size);
+ return new COWSubListIterator<E>(l, index, offset, size);
} finally {
- list.lock.unlock();
+ lock.unlock();
}
- return false;
}
- public boolean retainAll(Collection c) {
- list.lock.lock();
+ public List<E> subList(int fromIndex, int toIndex) {
+ final ReentrantLock lock = l.lock;
+ lock.lock();
try {
- checkModifications();
- int removed = list.retainAll(c, start, read.size);
- if (removed > 0) {
- read = new SubListReadData(read.size - removed, list
- .getData());
- return true;
- }
- return false;
+ checkForComodification();
+ if (fromIndex<0 || toIndex>size)
+ throw new IndexOutOfBoundsException();
+ return new COWSubList<E>(l, fromIndex + offset,
+ toIndex + offset);
} finally {
- list.lock.unlock();
+ lock.unlock();
}
}
- public List subList(int fromIndex, int toIndex) {
- return new SubList(list, start + fromIndex, start + toIndex);
- }
+ }
- public Object[] toArray() {
- SubListReadData r = read;
- return CopyOnWriteArrayList.toArray(r.data, start, r.size);
- }
- public Object[] toArray(Object[] a) {
- SubListReadData r = read;
- return CopyOnWriteArrayList.toArray(a, r.data, start, r.size);
+ private static class COWSubListIterator<E> implements ListIterator<E> {
+ private final ListIterator<E> i;
+ private final int index;
+ private final int offset;
+ private final int size;
+
+ COWSubListIterator(List<E> l, int index, int offset,
+ int size) {
+ this.index = index;
+ this.offset = offset;
+ this.size = size;
+ i = l.listIterator(index+offset);
}
- /**
- * @see java.util.List#addAll(int, java.util.Collection)
- */
- public boolean addAll(int index, Collection collection) {
- list.lock.lock();
- try {
- checkIndexInclusive(index, read.size);
- checkModifications();
- int d = list.size();
- boolean rt = list.addAll(index + start, collection);
- read = new SubListReadData(read.size + list.size() - d, list
- .getData());
- return rt;
- } finally {
- list.lock.unlock();
- }
+ public boolean hasNext() {
+ return nextIndex() < size;
}
- /**
- * Implementation of <code>ListIterator</code> for the
- * <code>SubList</code>
- * gets a snapshot of the sublist,
- * never throws ConcurrentModificationException
- */
- private class SubListIterator extends ListIteratorImpl {
- private final SubListReadData dataR;
+ public E next() {
+ if (hasNext())
+ return i.next();
+ else
+ throw new NoSuchElementException();
+ }
- /**
- * Constructs an iterator starting with the given index
- *
- * @param index index of the first element to iterate.
- */
- private SubListIterator(int index, SubListReadData d) {
- super(d.data, index + start);
- this.dataR = d;
- }
+ public boolean hasPrevious() {
+ return previousIndex() >= 0;
+ }
- /**
- * @see java.util.ListIterator#nextIndex()
- */
- public int nextIndex() {
- return super.nextIndex() - start;
- }
+ public E previous() {
+ if (hasPrevious())
+ return i.previous();
+ else
+ throw new NoSuchElementException();
+ }
- /**
- * @see java.util.ListIterator#previousIndex()
- */
- public int previousIndex() {
- return super.previousIndex() - start;
- }
+ public int nextIndex() {
+ return i.nextIndex() - offset;
+ }
- /**
- * @see java.util.Iterator#hasNext()
- */
- public boolean hasNext() {
- return nextIndex() < dataR.size;
- }
+ public int previousIndex() {
+ return i.previousIndex() - offset;
+ }
- /**
- * @see java.util.ListIterator#hasPrevious()
- */
- public boolean hasPrevious() {
- return previousIndex() > -1;
- }
+ public void remove() {
+ throw new UnsupportedOperationException();
}
- }
+ public void set(E e) {
+ throw new UnsupportedOperationException();
+ }
- //serialization support
- /**
- * Writes the object state to the ObjectOutputStream.
- *
- * @param oos ObjectOutputStream to write object to.
- * @throws IOException if an I/O error occur.
- */
- private void writeObject(ObjectOutputStream oos) throws IOException {
- E[] back = getData();
- int size = back.length;
- oos.defaultWriteObject();
- oos.writeInt(size);
- for (int i = 0; i < size; i++) {
- oos.writeObject(back[i]);
+ public void add(E e) {
+ throw new UnsupportedOperationException();
}
}
- /**
- * Reads the object state from the ObjectOutputStream.
- *
- * @param ois ObjectInputStream to read object from.
- * @throws IOException if an I/O error occur.
- */
- private void readObject(ObjectInputStream ois) throws IOException,
- ClassNotFoundException {
- ois.defaultReadObject();
- int length = ois.readInt();
- if (length == 0) {
- setData(newElementArray(0));
- } else {
- E[] back = newElementArray(length);
- for (int i = 0; i < back.length; i++) {
- back[i] = (E) ois.readObject();
- }
- setData(back);
- }
+ // Support for resetting lock while deserializing
+ private static final Unsafe unsafe = Unsafe.getUnsafe();
+ private static final long lockOffset;
+ static {
+ try {
+ lockOffset = unsafe.objectFieldOffset
+ (CopyOnWriteArrayList.class.getDeclaredField("lock"));
+ } catch (Exception ex) { throw new Error(ex); }
+ }
+ private void resetLock() {
+ unsafe.putObjectVolatile(this, lockOffset, new ReentrantLock());
}
}