Merging change 901123 from classlib trunk:
r901123 | hindessm | 2010-01-20 10:43:57 +0000 (Wed, 20 Jan 2010) | 8 lines
Reverting part of commit r794678:
Applying patch from "[#HARMONY-6262] Harmony's java.util.concurrent is
out of date".
to put back Harmony implementation of CopyOnWriteArrayList.
git-svn-id: https://svn.apache.org/repos/asf/harmony/enhanced/classlib/tags/5.0m12a@901631 13f79535-47bb-0310-9956-ffa450edef68
diff --git a/modules/concurrent/src/main/java/java/util/concurrent/CopyOnWriteArrayList.java b/modules/concurrent/src/main/java/java/util/concurrent/CopyOnWriteArrayList.java
index c1aea7c..6f58c50 100644
--- a/modules/concurrent/src/main/java/java/util/concurrent/CopyOnWriteArrayList.java
+++ b/modules/concurrent/src/main/java/java/util/concurrent/CopyOnWriteArrayList.java
@@ -1,1317 +1,1174 @@
/*
- * 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.
+ * 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.
*/
package java.util.concurrent;
-import java.util.*;
-import java.util.concurrent.locks.*;
-import java.lang.reflect.Array;
-import sun.misc.Unsafe;
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.Serializable;
+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;
/**
- * 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.
+ * 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.
*
- * <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>.
- *
- * @since 1.5
- * @author Doug Lea
- * @param <E> the type of elements held in this collection
+ * @param <E> the element type
*/
-public class CopyOnWriteArrayList<E>
- implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
+public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, Serializable {
+
private static final long serialVersionUID = 8673264195747942595L;
- /** The lock protecting all mutators */
- transient final ReentrantLock lock = new ReentrantLock();
-
- /** The array, accessed only via getArray/setArray. */
- private volatile transient Object[] array;
+ private transient volatile E[] arr;
/**
- * Gets the array. Non-private so as to also be accessible
- * from CopyOnWriteArraySet class.
+ * Lock for the queue write methods
*/
- final Object[] getArray() {
- return array;
- }
+ private final transient ReentrantLock lock = new ReentrantLock();
/**
- * Sets the array.
- */
- final void setArray(Object[] a) {
- array = a;
- }
-
- /**
- * Creates an empty list.
+ * Creates a new, empty instance of CopyOnWriteArrayList.
*/
public CopyOnWriteArrayList() {
- setArray(new Object[0]);
}
/**
- * Creates a list containing the elements of the specified
- * collection, in the order they are returned by the collection's
- * iterator.
+ * Creates a new instance of CopyOnWriteArrayList and fills it with the
+ * contents of a given Collection.
*
- * @param c the collection of initially held elements
- * @throws NullPointerException if the specified collection is null
+ * @param c the collection the elements of which are to be copied into
+ * the new instance.
*/
public CopyOnWriteArrayList(Collection<? extends E> c) {
- 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);
+ this((E[]) c.toArray());
}
/**
- * Creates a list holding a copy of the given array.
+ * Creates a new instance of CopyOnWriteArrayList and fills it with the
+ * contents of a given array.
*
- * @param toCopyIn the array (a copy of this array is used as the
- * internal array)
- * @throws NullPointerException if the specified array is null
+ * @param array the array the elements of which are to be copied into the
+ * new instance.
*/
- public CopyOnWriteArrayList(E[] toCopyIn) {
- setArray(Java6Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
- }
-
- /**
- * Returns the number of elements in this list.
- *
- * @return the number of elements in this list
- */
- public int size() {
- return getArray().length;
- }
-
- /**
- * Returns <tt>true</tt> if this list contains no elements.
- *
- * @return <tt>true</tt> if this list contains no elements
- */
- public boolean isEmpty() {
- return size() == 0;
- }
-
- /**
- * Test for equality, coping with nulls.
- */
- private static boolean eq(Object o1, Object 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.
- * @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;
+ public CopyOnWriteArrayList(E[] array) {
+ int size = array.length;
+ E[] data = newElementArray(size);
+ for (int i = 0; i < size; i++) {
+ data[i] = array[i];
}
- return -1;
+ arr = data;
}
- /**
- * static version of lastIndexOf.
- * @param o element to search for
- * @param elements the array
- * @param index first index to search
- * @return index of element, or -1 if absent
- */
- private static int lastIndexOf(Object o, Object[] elements, int index) {
- if (o == null) {
- for (int i = index; i >= 0; i--)
- if (elements[i] == null)
- return i;
- } else {
- for (int i = index; i >= 0; i--)
- if (o.equals(elements[i]))
- return i;
- }
- return -1;
- }
-
- /**
- * Returns <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;
- }
-
- /**
- * {@inheritDoc}
- */
- public int indexOf(Object o) {
- Object[] elements = getArray();
- return indexOf(o, elements, 0, elements.length);
- }
-
- /**
- * Returns the index of the first occurrence of the specified element in
- * this list, searching forwards from <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) {
- Object[] elements = getArray();
- return indexOf(e, elements, index, elements.length);
- }
-
- /**
- * {@inheritDoc}
- */
- public int lastIndexOf(Object o) {
- Object[] elements = getArray();
- return lastIndexOf(o, elements, elements.length - 1);
- }
-
- /**
- * Returns the index of the last occurrence of the specified element in
- * this list, searching backwards from <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);
- }
-
- /**
- * 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 an array containing all of the elements in this list
- * in proper sequence (from first to last element).
- *
- * <p>The returned array will be "safe" in that no references to it are
- * maintained by this list. (In other words, this method must allocate
- * a new array). The caller is thus free to modify the returned array.
- *
- * <p>This method acts as bridge between array-based and collection-based
- * APIs.
- *
- * @return an array containing all the elements in this list
- */
- public Object[] toArray() {
- Object[] elements = getArray();
- return Java6Arrays.copyOf(elements, elements.length);
- }
-
- /**
- * Returns an array containing all of the elements in this list in
- * proper sequence (from first to last element); the runtime type of
- * the returned array is that of the specified array. If the list fits
- * in the specified array, it is returned therein. Otherwise, a new
- * array is allocated with the runtime type of the specified array and
- * the size of this list.
- *
- * <p>If this list fits in the specified array with room to spare
- * (i.e., the array has more elements than this list), the element in
- * the array immediately following the end of the list is set to
- * <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;
- }
- }
-
- // Positional Access Operations
-
- @SuppressWarnings("unchecked")
- private E get(Object[] a, int index) {
- return (E) a[index];
- }
-
- /**
- * {@inheritDoc}
- *
- * @throws IndexOutOfBoundsException {@inheritDoc}
- */
- public E get(int index) {
- return get(getArray(), index);
- }
-
- /**
- * Replaces the element at the specified position in this list with the
- * specified element.
- *
- * @throws IndexOutOfBoundsException {@inheritDoc}
- */
- public E set(int index, E element) {
- final ReentrantLock lock = this.lock;
- lock.lock();
- try {
- 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);
- }
- return oldValue;
- } finally {
- lock.unlock();
- }
- }
-
- /**
- * 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 {
- Object[] elements = getArray();
- int len = elements.length;
- Object[] newElements = Java6Arrays.copyOf(elements, len + 1);
- newElements[len] = e;
- setArray(newElements);
+ 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();
}
}
- /**
- * 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;
+ public void add(int index, E e) {
lock.lock();
try {
- 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);
+ 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);
}
- newElements[index] = element;
- setArray(newElements);
+ setData(data);
} finally {
lock.unlock();
}
}
- /**
- * 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;
+ public boolean addAll(Collection<? extends E> c) {
+ Iterator it = c.iterator();
+ int ssize = c.size();
lock.lock();
try {
- 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);
+ 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();
}
- return oldValue;
+ setData(data);
} finally {
lock.unlock();
}
+ return true;
}
- /**
- * 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;
+ public boolean addAll(int index, Collection<? extends E> c) {
+ Iterator it = c.iterator();
+ int ssize = c.size();
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];
- }
-
- // special handling for last cell
- if (eq(o, elements[newlen])) {
- setArray(newElements);
- return true;
- }
+ 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();
}
- return false;
+ if (size > index) {
+ System.arraycopy(old, index, data, index + ssize, size - index);
+ }
+ setData(data);
} finally {
lock.unlock();
}
- }
-
- /**
- * 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;
-
- 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();
- }
- }
-
- /**
- * Append 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
- */
- 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();
- }
- }
-
- /**
- * Returns <tt>true</tt> 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
- * specified collection
- * @throws NullPointerException if the specified collection is null
- * @see #contains(Object)
- */
- public boolean containsAll(Collection<?> c) {
- Object[] elements = getArray();
- int len = elements.length;
- for (Object e : c) {
- if (indexOf(e, elements, 0, len) < 0)
- return false;
- }
return true;
}
/**
- * Removes from this list all of its elements that are contained in
- * the specified collection. This is a particularly expensive operation
- * in this class because of the need for an internal temporary array.
+ * Adds to this CopyOnWriteArrayList all those elements from a given
+ * collection that are not yet part of the list.
*
- * @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)
- */
- 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();
- }
- }
-
- /**
- * 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 the collection from which the potential new elements are
+ * taken.
*
- * @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)
- */
- 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();
- }
- }
-
- /**
- * 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)
+ * @return the number of elements actually added to this list.
*/
public int addAllAbsent(Collection<? extends E> c) {
- Object[] cs = c.toArray();
- if (cs.length == 0)
+ if (c.size() == 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
- Object e = cs[i];
- if (indexOf(e, elements, 0, len) < 0 &&
- indexOf(e, uniq, 0, added) < 0)
- uniq[added++] = e;
+ 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;
+ }
}
- if (added > 0) {
- Object[] newElements = Java6Arrays.copyOf(elements, len + added);
- System.arraycopy(uniq, 0, newElements, len, added);
- setArray(newElements);
- }
- return added;
+ 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();
}
}
/**
- * Removes all of the elements from this list.
- * The list will be empty after this call returns.
+ * Adds to this CopyOnWriteArrayList another element, given that this
+ * element is not yet part of the list.
+ *
+ * @param e the potential new element.
+ *
+ * @return true if the element was added, or false otherwise.
*/
+ 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 void clear() {
- final ReentrantLock lock = this.lock;
lock.lock();
try {
- setArray(new Object[0]);
+ setData(newElementArray(0));
} 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
- * @throws NullPointerException if the specified collection is null
- * @see #add(Object)
- */
- public boolean addAll(Collection<? extends E> c) {
- Object[] cs = c.toArray();
- if (cs.length == 0)
- return false;
- final ReentrantLock lock = this.lock;
- lock.lock();
+ @Override
+ public Object clone() {
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();
+ CopyOnWriteArrayList thisClone = (CopyOnWriteArrayList) super.clone();
+ thisClone.setData(this.getData());
+ return thisClone;
+ } catch (CloneNotSupportedException e) {
+ throw new RuntimeException("CloneNotSupportedException is not expected here");
}
}
- /**
- * 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)
- */
- 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();
- }
+ public boolean contains(Object o) {
+ return indexOf(o) >= 0;
}
- /**
- * Save the state of the list to a stream (i.e., serialize it).
- *
- * @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]);
+ public boolean containsAll(Collection<?> c) {
+ E[] data = getData();
+ return containsAll(c, data, 0, data.length);
}
- /**
- * 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 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)}.
- *
- * @return a string representation of this list
- */
- public String toString() {
- return Arrays.toString(getArray());
- }
-
- /**
- * Compares the specified object with this list for equality.
- * Returns {@code true} if the specified object is the same object
- * as this object, or if it is also a {@link List} and the sequence
- * of elements returned by an {@linkplain List#iterator() iterator}
- * over the specified list is the same as the sequence returned by
- * an iterator over this list. The two sequences are considered to
- * be the same if they have the same length and corresponding
- * elements at the same position in the sequence are <em>equal</em>.
- * Two elements {@code e1} and {@code e2} are considered
- * <em>equal</em> if {@code (e1==null ? e2==null : e1.equals(e2))}.
- *
- * @param o the object to be compared for equality with this list
- * @return {@code true} if the specified object is equal to this list
- */
public boolean equals(Object o) {
- if (o == this)
+ if (o == this) {
return true;
- if (!(o instanceof List))
+ }
+ 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()))
+ }
+ List l = (List) o;
+ Iterator it = l.listIterator();
+ Iterator ourIt = listIterator();
+ while (it.hasNext()) {
+ if (!ourIt.hasNext()) {
return false;
- if (it.hasNext())
+ }
+ Object thisListElem = it.next();
+ Object anotherListElem = ourIt.next();
+ if (!(thisListElem == null ? anotherListElem == null : thisListElem
+ .equals(anotherListElem))) {
+ return false;
+ }
+ }
+ if (ourIt.hasNext()) {
return false;
+ }
return true;
}
- /**
- * Returns the hash code value for this list.
- *
- * <p>This implementation uses the definition in {@link List#hashCode}.
- *
- * @return the hash code value for this list
- */
+ public E get(int index) {
+ E[] data = getData();
+ return data[index];
+ }
+
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());
+ Iterator it = listIterator();
+ while (it.hasNext()) {
+ Object obj = it.next();
+ hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode());
}
return hashCode;
}
/**
- * Returns an iterator over the elements in this list in proper sequence.
+ * Returns the index of a given element, starting the search from a given
+ * position in the list.
*
- * <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.
+ * @param e the element to search.
+ * @param index the index at which to start the search.
*
- * @return an iterator over the elements in this list in proper sequence
+ * @return the index of the element or null, if the element has not been
+ * found at or beyond the given start index.
*/
+ public int indexOf(E e, int index) {
+ E[] data = getData();
+ return indexOf(e, data, index, data.length - index);
+ }
+
+ public int indexOf(Object o) {
+ E[] data = getData();
+ return indexOf(o, data, 0, data.length);
+ }
+
+ public boolean isEmpty() {
+ return size() == 0;
+ }
+
public Iterator<E> iterator() {
- return new COWIterator<E>(getArray(), 0);
+ return new ListIteratorImpl(getData(), 0);
}
/**
- * {@inheritDoc}
+ * Returns the last index of a given element, starting the search from
+ * a given position in the list and going backwards.
*
- * <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.
+ * @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 before the given start index.
*/
+ public int lastIndexOf(E e, int index) {
+ E[] data = getData();
+ return lastIndexOf(e, data, 0, index);
+ }
+
+ public int lastIndexOf(Object o) {
+ E[] data = getData();
+ return lastIndexOf(o, data, 0, data.length);
+ }
+
public ListIterator<E> listIterator() {
- return new COWIterator<E>(getArray(), 0);
+ return new ListIteratorImpl(getData(), 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.
- *
- * @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);
-
- return new COWIterator<E>(elements, index);
+ public ListIterator<E> listIterator(int index) {
+ E[] data = getData();
+ checkIndexInclusive(index, data.length);
+ return new ListIteratorImpl(data, index);
}
- 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;
-
- private COWIterator(Object[] elements, int initialCursor) {
- cursor = initialCursor;
- snapshot = elements;
- }
-
- public boolean hasNext() {
- return cursor < snapshot.length;
- }
-
- public boolean hasPrevious() {
- return cursor > 0;
- }
-
- @SuppressWarnings("unchecked")
- public E next() {
- if (! hasNext())
- throw new NoSuchElementException();
- return (E) snapshot[cursor++];
- }
-
- @SuppressWarnings("unchecked")
- public E previous() {
- if (! hasPrevious())
- throw new NoSuchElementException();
- return (E) snapshot[--cursor];
- }
-
- public int nextIndex() {
- return cursor;
- }
-
- public int previousIndex() {
- return cursor-1;
- }
-
- /**
- * Not supported. Always throws UnsupportedOperationException.
- * @throws UnsupportedOperationException always; <tt>remove</tt>
- * is not supported by this iterator.
- */
- public void remove() {
- throw new UnsupportedOperationException();
- }
-
- /**
- * 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();
- }
+ public E remove(int index) {
+ return removeRange(index, 1);
}
- /**
- * 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}
- */
- public List<E> subList(int fromIndex, int toIndex) {
- final ReentrantLock lock = this.lock;
+ public boolean remove(Object o) {
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);
+ int index = indexOf(o);
+ if (index == -1) {
+ return false;
+ }
+ remove(index);
+ return true;
} finally {
lock.unlock();
}
}
+ public boolean removeAll(Collection<?> c) {
+ lock.lock();
+ try {
+ return removeAll(c, 0, getData().length) != 0;
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ public boolean retainAll(Collection<?> c) {
+ if (c == null) {
+ throw new NullPointerException();
+ }
+ lock.lock();
+ try {
+ return retainAll(c, 0, getData().length) != 0;
+ } finally {
+ lock.unlock();
+ }
+ }
+
+ public E set(int index, E e) {
+ 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;
+ } 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("[");
+
+ Iterator it = listIterator();
+ while (it.hasNext()) {
+ sb.append(String.valueOf(it.next()));
+ sb.append(", ");
+ }
+ if (sb.length() > 1) {
+ sb.setLength(sb.length() - 2);
+ }
+ sb.append("]");
+ return sb.toString();
+ }
+
+ // private and package private methods
+
+ @SuppressWarnings("unchecked")
+ private final E[] newElementArray(int size) {
+ return (E[])new Object[size];
+ }
+
/**
- * 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.
+ * sets the internal data array
+ *
+ * @param data array to set
*/
- 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;
+ private final void setData(E[] data) {
+ arr = data;
+ }
- // 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;
+ /**
+ * gets the internal data array
+ *
+ * @return the data array
+ */
+ final E[] getData() {
+ if (arr == null) {
+ return newElementArray(0);
+ }
+ return arr;
+ }
+
+ /**
+ * 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
+ */
+ 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];
+ }
+ }
+ 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
+ */
+ // 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];
+ }
+ }
+ 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
+ */
+ E removeRange(int start, int size) {
+ 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));
+ }
+ setData(data);
+ return old;
+ } 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
+ */
+ static Object[] toArray(Object[] data, int start, int size) {
+ Object[] result = new Object[size];
+ System.arraycopy(data, start, result, 0, size);
+ return result;
+ }
+
+ /**
+ * 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)
+ */
+ 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;
+ }
+ }
+ 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
+ */
+ 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) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * Returns the index in the specified range of the data array
+ * of the last occurrence of the specified element
+ *
+ * @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;
+ }
+
+ /**
+ * Returns the index in the specified range of the data array
+ * of the first occurrence of the specified element
+ *
+ * @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;
+ }
+
+ /**
+ * Throws <code>IndexOutOfBoundsException</code> if <code>index</code>
+ * is out of the list bounds.
+ *
+ * @param index element index to check.
+ */
+ static final void checkIndexInclusive(int index, int size) {
+ if (index < 0 || index > size) {
+ throw new IndexOutOfBoundsException("Index is " + index + ", size is " + size);
+ }
+ }
+
+ /**
+ * Throws <code>IndexOutOfBoundsException</code> if <code>index</code>
+ * is out of the list bounds. Excluding the last element.
+ *
+ * @param index element index to check.
+ */
+ static final void checkIndexExlusive(int index, int size) {
+ if (index < 0 || index >= size) {
+ throw new IndexOutOfBoundsException("Index is " + index + ", size is " + size);
+ }
+ }
+
+ /**
+ * list iterator implementation,
+ * when created gets snapshot of the list,
+ * so never throws ConcurrentModificationException
+ */
+ private static class ListIteratorImpl implements ListIterator {
+ private final Object[] arr;
+
+ private int current;
+
+ private final int size;
+
+ final int size() {
+ return size;
}
- // only call this holding l's lock
- private void checkForComodification() {
- if (l.getArray() != expectedArray)
+ public ListIteratorImpl(Object[] data, int current) {
+ this.current = current;
+ arr = data;
+ size = data.length;
+ }
+
+ public void add(Object o) {
+ throw new UnsupportedOperationException("Unsupported operation add");
+ }
+
+ public boolean hasNext() {
+ if (current < size) {
+ return true;
+ }
+ return false;
+ }
+
+ public boolean hasPrevious() {
+ return current > 0;
+ }
+
+ public Object next() {
+ if (hasNext()) {
+ return arr[current++];
+ }
+ throw new NoSuchElementException("pos is " + current + ", size is " + size);
+ }
+
+ public int nextIndex() {
+ return current;
+ }
+
+ public Object previous() {
+ if (hasPrevious()) {
+ return arr[--current];
+ }
+ throw new NoSuchElementException("pos is " + (current-1) + ", size is " + size);
+ }
+
+ public int previousIndex() {
+ return current - 1;
+ }
+
+ public void remove() {
+ throw new UnsupportedOperationException("Unsupported operation remove");
+ }
+
+ public void set(Object o) {
+ throw new UnsupportedOperationException("Unsupported operation set");
+ }
+
+ }
+
+ /**
+ * Keeps a state of sublist implementation,
+ * size and array declared as final,
+ * so we'll never get the unconsistent state
+ */
+ static final class SubListReadData {
+ final int size;
+
+ final Object[] data;
+
+ SubListReadData(int size, Object[] data) {
+ this.size = size;
+ this.data = data;
+ }
+ }
+
+ /**
+ * 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()) {
throw new ConcurrentModificationException();
- }
-
- // only call this holding l's lock
- private void rangeCheck(int index) {
- if (index<0 || index>=size)
- throw new IndexOutOfBoundsException("Index: "+index+
- ",Size: "+size);
- }
-
- public E set(int index, E element) {
- final ReentrantLock lock = l.lock;
- lock.lock();
- try {
- rangeCheck(index);
- checkForComodification();
- E x = l.set(index+offset, element);
- expectedArray = l.getArray();
- return x;
- } finally {
- lock.unlock();
}
}
- public E get(int index) {
- final ReentrantLock lock = l.lock;
- lock.lock();
+ /**
+ * @see java.util.List#listIterator(int)
+ */
+ public ListIterator listIterator(int startIdx) {
+ return new SubListIterator(startIdx, read);
+ }
+
+ /**
+ * @see java.util.List#set(int, java.lang.Object)
+ */
+ public Object set(int index, Object obj) {
+ list.lock.lock();
try {
- rangeCheck(index);
- checkForComodification();
- return l.get(index+offset);
+ checkIndexExlusive(index, read.size);
+ checkModifications();
+ Object result = list.set(index + start, obj);
+ read = new SubListReadData(read.size, list.getData());
+ return result;
} finally {
- lock.unlock();
+ list.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() {
- final ReentrantLock lock = l.lock;
- lock.lock();
+ return read.size;
+ }
+
+ /**
+ * @see java.util.List#remove(int)
+ */
+ public Object remove(int index) {
+ list.lock.lock();
try {
- checkForComodification();
- return size;
+ checkIndexExlusive(index, read.size);
+ checkModifications();
+ Object obj = list.remove(index + start);
+ read = new SubListReadData(read.size - 1, list.getData());
+ return obj;
} finally {
- lock.unlock();
+ list.lock.unlock();
}
}
- public void add(int index, E element) {
- final ReentrantLock lock = l.lock;
- lock.lock();
+ /**
+ * @see java.util.List#add(int, java.lang.Object)
+ */
+ public void add(int index, Object object) {
+ list.lock.lock();
try {
- checkForComodification();
- if (index<0 || index>size)
- throw new IndexOutOfBoundsException();
- l.add(index+offset, element);
- expectedArray = l.getArray();
- size++;
+ checkIndexInclusive(index, read.size);
+ checkModifications();
+ list.add(index + start, object);
+ read = new SubListReadData(read.size + 1, list.getData());
} finally {
- lock.unlock();
+ list.lock.unlock();
+ }
+ }
+
+ public boolean add(Object o) {
+ list.lock.lock();
+ try {
+ checkModifications();
+ list.add(start + read.size, o);
+ read = new SubListReadData(read.size + 1, list.getData());
+ return true;
+ } finally {
+ list.lock.unlock();
+ }
+ }
+
+ public boolean addAll(Collection c) {
+ list.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;
+ } finally {
+ list.lock.unlock();
}
}
public void clear() {
- final ReentrantLock lock = l.lock;
- lock.lock();
+ list.lock.lock();
try {
- checkForComodification();
- l.removeRange(offset, offset+size);
- expectedArray = l.getArray();
- size = 0;
+ checkModifications();
+ list.removeRange(start, read.size);
+ read = new SubListReadData(0, list.getData());
} finally {
- lock.unlock();
+ list.lock.unlock();
}
}
- public E remove(int index) {
- final ReentrantLock lock = l.lock;
- lock.lock();
- try {
- rangeCheck(index);
- checkForComodification();
- E result = l.remove(index+offset);
- expectedArray = l.getArray();
- size--;
- return result;
- } finally {
- 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)
+ list.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;
+ } finally {
+ list.lock.unlock();
+ }
+ }
+
+ public boolean removeAll(Collection c) {
+ list.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;
+ }
+ } finally {
+ list.lock.unlock();
+ }
+ return false;
+ }
+
+ public boolean retainAll(Collection c) {
+ list.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;
- remove(index);
- return true;
- }
-
- public Iterator<E> iterator() {
- final ReentrantLock lock = l.lock;
- lock.lock();
- try {
- checkForComodification();
- return new COWSubListIterator<E>(l, 0, offset, size);
} finally {
- lock.unlock();
+ list.lock.unlock();
}
}
- public ListIterator<E> listIterator(final int index) {
- final ReentrantLock lock = l.lock;
- lock.lock();
+ 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);
+ }
+
+ /**
+ * @see java.util.List#addAll(int, java.util.Collection)
+ */
+ public boolean addAll(int index, Collection collection) {
+ list.lock.lock();
try {
- checkForComodification();
- if (index<0 || index>size)
- throw new IndexOutOfBoundsException("Index: "+index+
- ", Size: "+size);
- return new COWSubListIterator<E>(l, index, offset, size);
+ 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 {
- lock.unlock();
+ list.lock.unlock();
}
}
- public List<E> subList(int fromIndex, int toIndex) {
- final ReentrantLock lock = l.lock;
- lock.lock();
- try {
- checkForComodification();
- if (fromIndex<0 || toIndex>size)
- throw new IndexOutOfBoundsException();
- return new COWSubList<E>(l, fromIndex + offset,
- toIndex + offset);
- } finally {
- lock.unlock();
+ /**
+ * 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;
+
+ /**
+ * 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;
+ }
+
+ /**
+ * @see java.util.ListIterator#nextIndex()
+ */
+ public int nextIndex() {
+ return super.nextIndex() - start;
+ }
+
+ /**
+ * @see java.util.ListIterator#previousIndex()
+ */
+ public int previousIndex() {
+ return super.previousIndex() - start;
+ }
+
+ /**
+ * @see java.util.Iterator#hasNext()
+ */
+ public boolean hasNext() {
+ return nextIndex() < dataR.size;
+ }
+
+ /**
+ * @see java.util.ListIterator#hasPrevious()
+ */
+ public boolean hasPrevious() {
+ return previousIndex() > -1;
}
}
}
-
- 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);
- }
-
- public boolean hasNext() {
- return nextIndex() < size;
- }
-
- public E next() {
- if (hasNext())
- return i.next();
- else
- throw new NoSuchElementException();
- }
-
- public boolean hasPrevious() {
- return previousIndex() >= 0;
- }
-
- public E previous() {
- if (hasPrevious())
- return i.previous();
- else
- throw new NoSuchElementException();
- }
-
- public int nextIndex() {
- return i.nextIndex() - offset;
- }
-
- public int previousIndex() {
- return i.previousIndex() - offset;
- }
-
- public void remove() {
- throw new UnsupportedOperationException();
- }
-
- public void set(E e) {
- throw new UnsupportedOperationException();
- }
-
- public void add(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]);
}
}
- // 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());
+ /**
+ * 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);
+ }
}
}
