Return-Path: Delivered-To: apmail-harmony-commits-archive@www.apache.org Received: (qmail 55357 invoked from network); 28 Jul 2009 09:30:36 -0000 Received: from hermes.apache.org (HELO mail.apache.org) (140.211.11.3) by minotaur.apache.org with SMTP; 28 Jul 2009 09:30:36 -0000 Received: (qmail 62401 invoked by uid 500); 28 Jul 2009 09:31:53 -0000 Delivered-To: apmail-harmony-commits-archive@harmony.apache.org Received: (qmail 62369 invoked by uid 500); 28 Jul 2009 09:31:53 -0000 Mailing-List: contact commits-help@harmony.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@harmony.apache.org Delivered-To: mailing list commits@harmony.apache.org Received: (qmail 62360 invoked by uid 99); 28 Jul 2009 09:31:53 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 28 Jul 2009 09:31:53 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=10.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 28 Jul 2009 09:31:46 +0000 Received: by eris.apache.org (Postfix, from userid 65534) id 6EDBA23889C7; Tue, 28 Jul 2009 09:30:59 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: 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... Date: Tue, 28 Jul 2009 09:30:48 -0000 To: commits@harmony.apache.org From: hindessm@apache.org X-Mailer: svnmailer-1.0.8 Message-Id: <20090728093059.6EDBA23889C7@eris.apache.org> X-Virus-Checked: Checked by ClamAV on apache.org 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 (add, set, and so on) are implemented by + * making a fresh copy of the underlying array. + * + *

This is ordinarily too costly, but may be more 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 ConcurrentModificationException. + * The iterator will not reflect additions, removals, or changes to + * the list since the iterator was created. Element-changing + * operations on iterators themselves (remove, set, and + * add) are not supported. These methods throw + * UnsupportedOperationException. + * + *

All elements are permitted, including null. + * + *

Memory consistency effects: As with other concurrent + * collections, actions in a thread prior to placing an object into a + * {@code CopyOnWriteArrayList} + * happen-before + * actions subsequent to the access or removal of that element from + * the {@code CopyOnWriteArrayList} in another thread. + * + *

This class is a member of the + * + * Java Collections Framework. * - * @param the element type + * @since 1.5 + * @author Doug Lea + * @param the type of elements held in this collection */ -public class CopyOnWriteArrayList implements List, RandomAccess, Cloneable, Serializable { - +public class CopyOnWriteArrayList + implements List, 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 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 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 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 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 true if this list contains no elements. * - * @param e the potential new element. - * - * @return true if the element was added, or false otherwise. + * @return true 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 true if this list contains the specified element. + * More formally, returns true if and only if this list contains + * at least one element e such that + * (o==null ? e==null : o.equals(e)). + * + * @param o element whose presence in this list is to be tested + * @return true 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 index, or returns -1 if + * the element is not found. + * More formally, returns the lowest index i such that + * (i >= index && (e==null ? get(i)==null : e.equals(get(i)))), + * 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 index or later in the list; + * -1 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 index, or returns -1 if + * the element is not found. + * More formally, returns the highest index i such that + * (i <= index && (e==null ? get(i)==null : e.equals(get(i)))), + * 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 index in this list; + * -1 if the element is not found. + * @throws IndexOutOfBoundsException if the specified index is greater + * than or equal to the current size of this list + */ + public int lastIndexOf(E e, int index) { + Object[] elements = getArray(); + return lastIndexOf(e, elements, index); } - public Iterator 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). + * + *

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. + *

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. + * + *

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 + * null. (This is useful in determining the length of this + * list only if the caller knows that this list does not contain + * any null elements.) + * + *

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. + * + *

Suppose x is a list known to contain only strings. + * The following code can be used to dump the list into a newly + * allocated array of String: + * + * 

+     *     String[] y = x.toArray(new String[0]);
+ * + * Note that toArray(new Object[0]) is identical in function to + * toArray(). + * + * @param a the array into which the elements of the list are to + * be stored, if it is big enough; otherwise, a new array of the + * same runtime type is allocated for this purpose. + * @return an array containing all the elements in this list + * @throws ArrayStoreException if the runtime type of the specified array + * is not a supertype of the runtime type of every element in + * this list + * @throws NullPointerException if the specified array is null + */ + @SuppressWarnings("unchecked") + public T[] 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 listIterator() { - return new ListIteratorImpl(getData(), 0); - } + // Positional Access Operations - public ListIterator 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 true (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 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[] 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 + * i such that + * (o==null ? get(i)==null : o.equals(get(i))) + * (if such an element exists). Returns true if this list + * contained the specified element (or equivalently, if this list + * changed as a result of the call). + * + * @param o element to be removed from this list, if present + * @return true 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 + * fromIndex, inclusive, and toIndex, exclusive. + * Shifts any succeeding elements to the left (reduces their index). + * This call shortens the list by (toIndex - fromIndex) elements. + * (If toIndex==fromIndex, this operation has no effect.) + * + * @param fromIndex index of first element to be removed + * @param toIndex index after last element to be removed + * @throws IndexOutOfBoundsException if fromIndex or toIndex out of range + * (@code{fromIndex < 0 || toIndex > size() || toIndex < fromIndex}) + */ + 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 true 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 true 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 true 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 - *

- * !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 true if this list changed as a result of the call + * @throws ClassCastException if the class of an element of this list + * is incompatible with the specified collection (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 true if this list changed as a result of the call + * @throws ClassCastException if the class of an element of this list + * is incompatible with the specified collection (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 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 true 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 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 true if this list changed as a result of the call + * @throws IndexOutOfBoundsException {@inheritDoc} + * @throws NullPointerException if the specified collection is null + * @see #add(int,Object) */ - 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 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 ("[]"). Adjacent elements are separated by + * the characters ", " (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 IndexOutOfBoundsException if index - * 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 equal. + * Two elements {@code e1} and {@code e2} are considered + * equal 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 IndexOutOfBoundsException if index - * is out of the list bounds. Excluding the last element. + * Returns the hash code value for this list. + * + *

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. + * + *

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 NOT support the + * remove 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 iterator() { + return new COWIterator(getArray(), 0); + } - private int current; + /** + * {@inheritDoc} + * + *

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 NOT support the + * remove, set or add methods. + */ + public ListIterator listIterator() { + return new COWIterator(getArray(), 0); + } - private final int size; + /** + * {@inheritDoc} + * + *

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 NOT support the + * remove, set or add methods. + * + * @throws IndexOutOfBoundsException {@inheritDoc} + */ + public ListIterator 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(elements, index); + } - public ListIteratorImpl(Object[] data, int current) { - this.current = current; - arr = data; - size = data.length; - } + private static class COWIterator implements ListIterator { + /** 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; remove + * 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; set + * is not supported by this iterator. + */ + public void set(E e) { + throw new UnsupportedOperationException(); } + /** + * Not supported. Always throws UnsupportedOperationException. + * @throws UnsupportedOperationException always; add + * 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 + * fromIndex, inclusive, and toIndex, exclusive. + * The returned list is backed by this list, so changes in the + * returned list are reflected in this list. + * + *

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 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(this, fromIndex, toIndex); + } finally { + lock.unlock(); } } /** - * Represents a list returned by sublist(). - */ - 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 - *

- * 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 + extends AbstractList + implements RandomAccess + { + private final CopyOnWriteArrayList l; + private final int offset; + private int size; + private Object[] expectedArray; + + // only call this holding l's lock + COWSubList(CopyOnWriteArrayList 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 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(l, 0, offset, size); } finally { - list.lock.unlock(); + lock.unlock(); } } - public boolean removeAll(Collection c) { - list.lock.lock(); + public ListIterator 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(l, index, offset, size); } finally { - list.lock.unlock(); + lock.unlock(); } - return false; } - public boolean retainAll(Collection c) { - list.lock.lock(); + public List 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(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 implements ListIterator { + private final ListIterator i; + private final int index; + private final int offset; + private final int size; + + COWSubListIterator(List 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 ListIterator for the - * SubList - * 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()); } }