harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From hinde...@apache.org
Subject svn commit: r794678 [4/19] - in /harmony/enhanced/classlib/trunk/modules/concurrent/src: main/java/java/util/concurrent/ main/java/java/util/concurrent/atomic/ main/java/java/util/concurrent/locks/ test/java/
Date Thu, 16 Jul 2009 14:01:17 GMT
Modified: harmony/enhanced/classlib/trunk/modules/concurrent/src/main/java/java/util/concurrent/CopyOnWriteArrayList.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/concurrent/src/main/java/java/util/concurrent/CopyOnWriteArrayList.java?rev=794678&r1=794677&r2=794678&view=diff
==============================================================================
--- harmony/enhanced/classlib/trunk/modules/concurrent/src/main/java/java/util/concurrent/CopyOnWriteArrayList.java (original)
+++ harmony/enhanced/classlib/trunk/modules/concurrent/src/main/java/java/util/concurrent/CopyOnWriteArrayList.java Thu Jul 16 14:01:15 2009
@@ -1,1174 +1,1317 @@
 /*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with this
- * work for additional information regarding copyright ownership. The ASF
- * licenses this file to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- * 
- * http://www.apache.org/licenses/LICENSE-2.0
- * 
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
- * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
- * License for the specific language governing permissions and limitations under
- * the License.
+ * Written by Doug Lea with assistance from members of JCP JSR-166
+ * Expert Group.  Adapted and released, under explicit permission,
+ * from JDK ArrayList.java which carries the following copyright:
+ *
+ * Copyright 1997 by Sun Microsystems, Inc.,
+ * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
+ * All rights reserved.
+ *
+ * This software is the confidential and proprietary information
+ * of Sun Microsystems, Inc. ("Confidential Information").  You
+ * shall not disclose such Confidential Information and shall use
+ * it only in accordance with the terms of the license agreement
+ * you entered into with Sun.
  */
 
 package java.util.concurrent;
-
-import java.io.IOException;
-import java.io.ObjectInputStream;
-import java.io.ObjectOutputStream;
-import java.io.Serializable;
+import java.util.*;
+import java.util.concurrent.locks.*;
 import java.lang.reflect.Array;
-import java.util.Collection;
-import java.util.ConcurrentModificationException;
-import java.util.Iterator;
-import java.util.List;
-import java.util.ListIterator;
-import java.util.NoSuchElementException;
-import java.util.RandomAccess;
-import java.util.concurrent.locks.ReentrantLock;
+
+import sun.misc.Unsafe;
 
 /**
- * Implements a {@link java.util.ArrayList} variant that is thread-safe. All
- * write operation result in a new copy of the underlying data being created.
- * Iterators reflect the state of the CopyOnWriteArrayList at the time they were
- * created. They are not updated to reflect subsequent changes to the list. In
- * addition, these iterators cannot be used for modifying the underlying
- * CopyOnWriteArrayList.
+ * A thread-safe variant of {@link java.util.ArrayList} in which all mutative
+ * operations (<tt>add</tt>, <tt>set</tt>, and so on) are implemented by
+ * making a fresh copy of the underlying array.
+ *
+ * <p> This is ordinarily too costly, but may be <em>more</em> efficient
+ * than alternatives when traversal operations vastly outnumber
+ * mutations, and is useful when you cannot or don't want to
+ * synchronize traversals, yet need to preclude interference among
+ * concurrent threads.  The "snapshot" style iterator method uses a
+ * reference to the state of the array at the point that the iterator
+ * was created. This array never changes during the lifetime of the
+ * iterator, so interference is impossible and the iterator is
+ * guaranteed not to throw <tt>ConcurrentModificationException</tt>.
+ * The iterator will not reflect additions, removals, or changes to
+ * the list since the iterator was created.  Element-changing
+ * operations on iterators themselves (<tt>remove</tt>, <tt>set</tt>, and
+ * <tt>add</tt>) are not supported. These methods throw
+ * <tt>UnsupportedOperationException</tt>.
+ *
+ * <p>All elements are permitted, including <tt>null</tt>.
+ *
+ * <p>Memory consistency effects: As with other concurrent
+ * collections, actions in a thread prior to placing an object into a
+ * {@code CopyOnWriteArrayList}
+ * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a>
+ * actions subsequent to the access or removal of that element from
+ * the {@code CopyOnWriteArrayList} in another thread.
+ *
+ * <p>This class is a member of the
+ * <a href="{@docRoot}/../technotes/guides/collections/index.html">
+ * Java Collections Framework</a>.
  *
- * @param <E> the element type
+ * @since 1.5
+ * @author Doug Lea
+ * @param <E> the type of elements held in this collection
  */
-public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, Serializable {
-
+public class CopyOnWriteArrayList<E>
+    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
     private static final long serialVersionUID = 8673264195747942595L;
 
-    private transient volatile E[] arr;
+    /** The lock protecting all mutators */
+    transient final ReentrantLock lock = new ReentrantLock();
+
+    /** The array, accessed only via getArray/setArray. */
+    private volatile transient Object[] array;
+
+    /**
+     * Gets the array.  Non-private so as to also be accessible
+     * from CopyOnWriteArraySet class.
+     */
+    final Object[] getArray() {
+        return array;
+    }
 
     /**
-     * Lock for the queue write methods
+     * Sets the array.
      */
-    private final transient ReentrantLock lock = new ReentrantLock();
+    final void setArray(Object[] a) {
+        array = a;
+    }
 
     /**
-     * Creates a new, empty instance of CopyOnWriteArrayList.
+     * Creates an empty list.
      */
     public CopyOnWriteArrayList() {
+        setArray(new Object[0]);
     }
 
     /**
-     * Creates a new instance of CopyOnWriteArrayList and fills it with the
-     * contents of a given Collection.
+     * Creates a list containing the elements of the specified
+     * collection, in the order they are returned by the collection's
+     * iterator.
      *
-     * @param c     the collection the elements of which are to be copied into
-     *              the new instance.
+     * @param c the collection of initially held elements
+     * @throws NullPointerException if the specified collection is null
      */
     public CopyOnWriteArrayList(Collection<? extends E> c) {
-        this((E[]) c.toArray());
+        Object[] elements = c.toArray();
+        // c.toArray might (incorrectly) not return Object[] (see 6260652)
+        if (elements.getClass() != Object[].class)
+            elements = Java6Arrays.copyOf(elements, elements.length, Object[].class);
+        setArray(elements);
     }
 
     /**
-     * Creates a new instance of CopyOnWriteArrayList and fills it with the
-     * contents of a given array.
+     * Creates a list holding a copy of the given array.
      *
-     * @param array the array the elements of which are to be copied into the
-     *              new instance.
+     * @param toCopyIn the array (a copy of this array is used as the
+     *        internal array)
+     * @throws NullPointerException if the specified array is null
      */
-    public CopyOnWriteArrayList(E[] array) {
-        int size = array.length;
-        E[] data = newElementArray(size);
-        for (int i = 0; i < size; i++) {
-            data[i] = array[i];
-        }
-        arr = data;
-    }
-
-    public boolean add(E e) {
-        lock.lock();
-        try {
-            E[] data;
-            E[] old = getData();
-            int size = old.length;
-            data = newElementArray(size + 1);
-            System.arraycopy(old, 0, data, 0, size);
-            data[size] = e;
-            setData(data);
-            return true;
-        } finally {
-            lock.unlock();
-        }
-    }
-
-    public void add(int index, E e) {
-        lock.lock();
-        try {
-            E[] data;
-            E[] old = getData();
-            int size = old.length;
-            checkIndexInclusive(index, size);
-            data = newElementArray(size+1);
-            System.arraycopy(old, 0, data, 0, index);
-            data[index] = e;
-            if (size > index) {
-                System.arraycopy(old, index, data, index + 1, size - index);
-            }
-            setData(data);
-        } finally {
-            lock.unlock();
-        }
-    }
-
-    public boolean addAll(Collection<? extends E> c) {
-        Iterator it = c.iterator();
-        int ssize = c.size();
-        lock.lock();
-        try {
-            int size = size();
-            E[] data;
-            E[] old = getData();
-            int nSize = size + ssize;
-            data = newElementArray(nSize);
-            System.arraycopy(old, 0, data, 0, size);
-            while (it.hasNext()) {
-                data[size++] = (E) it.next();
-            }
-            setData(data);
-        } finally {
-            lock.unlock();
-        }
-        return true;
-    }
-
-    public boolean addAll(int index, Collection<? extends E> c) {
-        Iterator it = c.iterator();
-        int ssize = c.size();
-        lock.lock();
-        try {
-            int size = size();
-            checkIndexInclusive(index, size);
-            E[] data;
-            E[] old = getData();
-            int nSize = size + ssize;
-            data = newElementArray(nSize);
-            System.arraycopy(old, 0, data, 0, index);
-            int i = index;
-            while (it.hasNext()) {
-                data[i++] = (E) it.next();
-            }
-            if (size > index) {
-                System.arraycopy(old, index, data, index + ssize, size - index);
-            }
-            setData(data);
-        } finally {
-            lock.unlock();
-        }
-        return true;
+    public CopyOnWriteArrayList(E[] toCopyIn) {
+        setArray(Java6Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
     }
 
     /**
-     * Adds to this CopyOnWriteArrayList all those elements from a given
-     * collection that are not yet part of the list.
-     *
-     * @param c     the collection from which the potential new elements are
-     *              taken.
+     * Returns the number of elements in this list.
      *
-     * @return the number of elements actually added to this list.
+     * @return the number of elements in this list
      */
-    public int addAllAbsent(Collection<? extends E> c) {
-        if (c.size() == 0) {
-            return 0;
-        }
-        lock.lock();
-        try {
-            E[] old = getData();
-            int size = old.length;
-            E[] toAdd = newElementArray(c.size());
-            int i = 0;
-            for (Iterator it = c.iterator(); it.hasNext();) {
-                E o = (E) it.next();
-                if (indexOf(o) < 0) {
-                    toAdd[i++] = o;
-                }
-            }
-            E[] data = newElementArray(size + i);
-            System.arraycopy(old, 0, data, 0, size);
-            System.arraycopy(toAdd, 0, data, size, i);
-            setData(data);
-            return i;
-        } finally {
-            lock.unlock();
-        }
+    public int size() {
+        return getArray().length;
     }
 
     /**
-     * Adds to this CopyOnWriteArrayList another element, given that this
-     * element is not yet part of the list.
+     * Returns <tt>true</tt> if this list contains no elements.
      *
-     * @param e     the potential new element.
-     *
-     * @return true if the element was added, or false otherwise.
+     * @return <tt>true</tt> if this list contains no elements
      */
-    public boolean addIfAbsent(E e) {
-        lock.lock();
-        try {
-            E[] data;
-            E[] old = getData();
-            int size = old.length;
-            if (size != 0) {
-                if (indexOf(e) >= 0) {
-                    return false;
-                }
-            }
-            data = newElementArray(size + 1);
-            System.arraycopy(old, 0, data, 0, size);
-            data[size] = e;
-            setData(data);
-            return true;
-        } finally {
-            lock.unlock();
-        }
+    public boolean isEmpty() {
+        return size() == 0;
     }
 
-    public void clear() {
-        lock.lock();
-        try {
-            setData(newElementArray(0));
-        } finally {
-            lock.unlock();
-        }
+    /**
+     * Test for equality, coping with nulls.
+     */
+    private static boolean eq(Object o1, Object o2) {
+        return (o1 == null ? o2 == null : o1.equals(o2));
     }
 
-    @Override
-    public Object clone() {
-        try {
-            CopyOnWriteArrayList thisClone = (CopyOnWriteArrayList) super.clone();
-            thisClone.setData(this.getData());
-            return thisClone;
-        } catch (CloneNotSupportedException e) {
-            throw new RuntimeException("CloneNotSupportedException is not expected here");
+    /**
+     * static version of indexOf, to allow repeated calls without
+     * needing to re-acquire array each time.
+     * @param o element to search for
+     * @param elements the array
+     * @param index first index to search
+     * @param fence one past last index to search
+     * @return index of element, or -1 if absent
+     */
+    private static int indexOf(Object o, Object[] elements,
+                               int index, int fence) {
+        if (o == null) {
+            for (int i = index; i < fence; i++)
+                if (elements[i] == null)
+                    return i;
+        } else {
+            for (int i = index; i < fence; i++)
+                if (o.equals(elements[i]))
+                    return i;
         }
+        return -1;
     }
 
-    public boolean contains(Object o) {
-        return indexOf(o) >= 0;
-    }
-
-    public boolean containsAll(Collection<?> c) {
-        E[] data = getData();
-        return containsAll(c, data, 0, data.length);
-    }
-
-    public boolean equals(Object o) {
-        if (o == this) {
-            return true;
-        }
-        if (!(o instanceof List)) {
-            return false;
-        }
-        List l = (List) o;
-        Iterator it = l.listIterator();
-        Iterator ourIt = listIterator();
-        while (it.hasNext()) {
-            if (!ourIt.hasNext()) {
-                return false;
-            }
-            Object thisListElem = it.next();
-            Object anotherListElem = ourIt.next();
-            if (!(thisListElem == null ? anotherListElem == null : thisListElem
-                    .equals(anotherListElem))) {
-                return false;
-            }
-        }
-        if (ourIt.hasNext()) {
-            return false;
+    /**
+     * static version of lastIndexOf.
+     * @param o element to search for
+     * @param elements the array
+     * @param index first index to search
+     * @return index of element, or -1 if absent
+     */
+    private static int lastIndexOf(Object o, Object[] elements, int index) {
+        if (o == null) {
+            for (int i = index; i >= 0; i--)
+                if (elements[i] == null)
+                    return i;
+        } else {
+            for (int i = index; i >= 0; i--)
+                if (o.equals(elements[i]))
+                    return i;
         }
-        return true;
+        return -1;
     }
 
-    public E get(int index) {
-        E[] data = getData();
-        return data[index];
+    /**
+     * Returns <tt>true</tt> if this list contains the specified element.
+     * More formally, returns <tt>true</tt> if and only if this list contains
+     * at least one element <tt>e</tt> such that
+     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
+     *
+     * @param o element whose presence in this list is to be tested
+     * @return <tt>true</tt> if this list contains the specified element
+     */
+    public boolean contains(Object o) {
+        Object[] elements = getArray();
+        return indexOf(o, elements, 0, elements.length) >= 0;
     }
 
-    public int hashCode() {
-        int hashCode = 1;
-        Iterator it = listIterator();
-        while (it.hasNext()) {
-            Object obj = it.next();
-            hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode());
-        }
-        return hashCode;
+    /**
+     * {@inheritDoc}
+     */
+    public int indexOf(Object o) {
+        Object[] elements = getArray();
+        return indexOf(o, elements, 0, elements.length);
     }
 
     /**
-     * Returns the index of a given element, starting the search from a given
-     * position in the list.
-     *
-     * @param e     the element to search.
-     * @param index the index at which to start the search.
-     *
-     * @return the index of the element or null, if the element has not been
-     * found at or beyond the given start index.
+     * Returns the index of the first occurrence of the specified element in
+     * this list, searching forwards from <tt>index</tt>, or returns -1 if
+     * the element is not found.
+     * More formally, returns the lowest index <tt>i</tt> such that
+     * <tt>(i&nbsp;&gt;=&nbsp;index&nbsp;&amp;&amp;&nbsp;(e==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;e.equals(get(i))))</tt>,
+     * or -1 if there is no such index.
+     *
+     * @param e element to search for
+     * @param index index to start searching from
+     * @return the index of the first occurrence of the element in
+     *         this list at position <tt>index</tt> or later in the list;
+     *         <tt>-1</tt> if the element is not found.
+     * @throws IndexOutOfBoundsException if the specified index is negative
      */
     public int indexOf(E e, int index) {
-        E[] data = getData();
-        return indexOf(e, data, index, data.length - index);
+        Object[] elements = getArray();
+        return indexOf(e, elements, index, elements.length);
     }
 
-    public int indexOf(Object o) {
-        E[] data = getData();
-        return indexOf(o, data, 0, data.length);
+    /**
+     * {@inheritDoc}
+     */
+    public int lastIndexOf(Object o) {
+        Object[] elements = getArray();
+        return lastIndexOf(o, elements, elements.length - 1);
     }
 
-    public boolean isEmpty() {
-        return size() == 0;
+    /**
+     * Returns the index of the last occurrence of the specified element in
+     * this list, searching backwards from <tt>index</tt>, or returns -1 if
+     * the element is not found.
+     * More formally, returns the highest index <tt>i</tt> such that
+     * <tt>(i&nbsp;&lt;=&nbsp;index&nbsp;&amp;&amp;&nbsp;(e==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;e.equals(get(i))))</tt>,
+     * or -1 if there is no such index.
+     *
+     * @param e element to search for
+     * @param index index to start searching backwards from
+     * @return the index of the last occurrence of the element at position
+     *         less than or equal to <tt>index</tt> in this list;
+     *         -1 if the element is not found.
+     * @throws IndexOutOfBoundsException if the specified index is greater
+     *         than or equal to the current size of this list
+     */
+    public int lastIndexOf(E e, int index) {
+        Object[] elements = getArray();
+        return lastIndexOf(e, elements, index);
     }
 
-    public Iterator<E> iterator() {
-        return new ListIteratorImpl(getData(), 0);
+    /**
+     * Returns a shallow copy of this list.  (The elements themselves
+     * are not copied.)
+     *
+     * @return a clone of this list
+     */
+    public Object clone() {
+        try {
+            CopyOnWriteArrayList c = (CopyOnWriteArrayList)(super.clone());
+            c.resetLock();
+            return c;
+        } catch (CloneNotSupportedException e) {
+            // this shouldn't happen, since we are Cloneable
+            throw new InternalError();
+        }
     }
 
     /**
-     * Returns the last index of a given element, starting the search from
-     * a given position in the list and going backwards.
+     * Returns an array containing all of the elements in this list
+     * in proper sequence (from first to last element).
+     *
+     * <p>The returned array will be "safe" in that no references to it are
+     * maintained by this list.  (In other words, this method must allocate
+     * a new array).  The caller is thus free to modify the returned array.
      *
-     * @param e     the element to search.
-     * @param index the index at which to start the search.
+     * <p>This method acts as bridge between array-based and collection-based
+     * APIs.
      *
-     * @return the index of the element or null, if the element has not been
-     * found at or before the given start index.
+     * @return an array containing all the elements in this list
      */
-    public int lastIndexOf(E e, int index) {
-        E[] data = getData();
-        return lastIndexOf(e, data, 0, index);
+    public Object[] toArray() {
+        Object[] elements = getArray();
+        return Java6Arrays.copyOf(elements, elements.length);
     }
 
-    public int lastIndexOf(Object o) {
-        E[] data = getData();
-        return lastIndexOf(o, data, 0, data.length);
+    /**
+     * Returns an array containing all of the elements in this list in
+     * proper sequence (from first to last element); the runtime type of
+     * the returned array is that of the specified array.  If the list fits
+     * in the specified array, it is returned therein.  Otherwise, a new
+     * array is allocated with the runtime type of the specified array and
+     * the size of this list.
+     *
+     * <p>If this list fits in the specified array with room to spare
+     * (i.e., the array has more elements than this list), the element in
+     * the array immediately following the end of the list is set to
+     * <tt>null</tt>.  (This is useful in determining the length of this
+     * list <i>only</i> if the caller knows that this list does not contain
+     * any null elements.)
+     *
+     * <p>Like the {@link #toArray()} method, this method acts as bridge between
+     * array-based and collection-based APIs.  Further, this method allows
+     * precise control over the runtime type of the output array, and may,
+     * under certain circumstances, be used to save allocation costs.
+     *
+     * <p>Suppose <tt>x</tt> is a list known to contain only strings.
+     * The following code can be used to dump the list into a newly
+     * allocated array of <tt>String</tt>:
+     *
+     * <pre>
+     *     String[] y = x.toArray(new String[0]);</pre>
+     *
+     * Note that <tt>toArray(new Object[0])</tt> is identical in function to
+     * <tt>toArray()</tt>.
+     *
+     * @param a the array into which the elements of the list are to
+     *          be stored, if it is big enough; otherwise, a new array of the
+     *          same runtime type is allocated for this purpose.
+     * @return an array containing all the elements in this list
+     * @throws ArrayStoreException if the runtime type of the specified array
+     *         is not a supertype of the runtime type of every element in
+     *         this list
+     * @throws NullPointerException if the specified array is null
+     */
+    @SuppressWarnings("unchecked")
+    public <T> T[] toArray(T a[]) {
+        Object[] elements = getArray();
+        int len = elements.length;
+        if (a.length < len)
+            return (T[]) Java6Arrays.copyOf(elements, len, a.getClass());
+        else {
+            System.arraycopy(elements, 0, a, 0, len);
+            if (a.length > len)
+                a[len] = null;
+            return a;
+        }
     }
 
-    public ListIterator<E> listIterator() {
-        return new ListIteratorImpl(getData(), 0);
-    }
+    // Positional Access Operations
 
-    public ListIterator<E> listIterator(int index) {
-        E[] data = getData();
-        checkIndexInclusive(index, data.length);
-        return new ListIteratorImpl(data, index);
+    @SuppressWarnings("unchecked")
+    private E get(Object[] a, int index) {
+        return (E) a[index];
     }
 
-    public E remove(int index) {
-        return removeRange(index, 1);
+    /**
+     * {@inheritDoc}
+     *
+     * @throws IndexOutOfBoundsException {@inheritDoc}
+     */
+    public E get(int index) {
+        return get(getArray(), index);
     }
 
-    public boolean remove(Object o) {
+    /**
+     * Replaces the element at the specified position in this list with the
+     * specified element.
+     *
+     * @throws IndexOutOfBoundsException {@inheritDoc}
+     */
+    public E set(int index, E element) {
+        final ReentrantLock lock = this.lock;
         lock.lock();
         try {
-            int index = indexOf(o);
-            if (index == -1) {
-                return false;
+            Object[] elements = getArray();
+            E oldValue = get(elements, index);
+
+            if (oldValue != element) {
+                int len = elements.length;
+                Object[] newElements = Java6Arrays.copyOf(elements, len);
+                newElements[index] = element;
+                setArray(newElements);
+            } else {
+                // Not quite a no-op; ensures volatile write semantics
+                setArray(elements);
             }
-            remove(index);
-            return true;
+            return oldValue;
         } finally {
             lock.unlock();
         }
     }
 
-    public boolean removeAll(Collection<?> c) {
+    /**
+     * Appends the specified element to the end of this list.
+     *
+     * @param e element to be appended to this list
+     * @return <tt>true</tt> (as specified by {@link Collection#add})
+     */
+    public boolean add(E e) {
+        final ReentrantLock lock = this.lock;
         lock.lock();
         try {
-            return removeAll(c, 0, getData().length) != 0;
+            Object[] elements = getArray();
+            int len = elements.length;
+            Object[] newElements = Java6Arrays.copyOf(elements, len + 1);
+            newElements[len] = e;
+            setArray(newElements);
+            return true;
         } finally {
             lock.unlock();
         }
     }
 
-    public boolean retainAll(Collection<?> c) {
-        if (c == null) {
-            throw new NullPointerException();
-        }
+    /**
+     * Inserts the specified element at the specified position in this
+     * list. Shifts the element currently at that position (if any) and
+     * any subsequent elements to the right (adds one to their indices).
+     *
+     * @throws IndexOutOfBoundsException {@inheritDoc}
+     */
+    public void add(int index, E element) {
+        final ReentrantLock lock = this.lock;
         lock.lock();
         try {
-            return retainAll(c, 0, getData().length) != 0;
+            Object[] elements = getArray();
+            int len = elements.length;
+            if (index > len || index < 0)
+                throw new IndexOutOfBoundsException("Index: "+index+
+                                                    ", Size: "+len);
+            Object[] newElements;
+            int numMoved = len - index;
+            if (numMoved == 0)
+                newElements = Java6Arrays.copyOf(elements, len + 1);
+            else {
+                newElements = new Object[len + 1];
+                System.arraycopy(elements, 0, newElements, 0, index);
+                System.arraycopy(elements, index, newElements, index + 1,
+                                 numMoved);
+            }
+            newElements[index] = element;
+            setArray(newElements);
         } finally {
             lock.unlock();
         }
     }
 
-    public E set(int index, E e) {
+    /**
+     * Removes the element at the specified position in this list.
+     * Shifts any subsequent elements to the left (subtracts one from their
+     * indices).  Returns the element that was removed from the list.
+     *
+     * @throws IndexOutOfBoundsException {@inheritDoc}
+     */
+    public E remove(int index) {
+        final ReentrantLock lock = this.lock;
         lock.lock();
         try {
-            int size = size();
-            checkIndexExlusive(index, size);
-            E[] data;
-            data = newElementArray(size);
-            E[] oldArr = getData();
-            System.arraycopy(oldArr, 0, data, 0, size);
-            E old = data[index];
-            data[index] = e;
-            setData(data);
-            return old;
+            Object[] elements = getArray();
+            int len = elements.length;
+            E oldValue = get(elements, index);
+            int numMoved = len - index - 1;
+            if (numMoved == 0)
+                setArray(Java6Arrays.copyOf(elements, len - 1));
+            else {
+                Object[] newElements = new Object[len - 1];
+                System.arraycopy(elements, 0, newElements, 0, index);
+                System.arraycopy(elements, index + 1, newElements, index,
+                                 numMoved);
+                setArray(newElements);
+            }
+            return oldValue;
         } finally {
             lock.unlock();
         }
     }
 
-    public int size() {
-        return getData().length;
-    }
-
-    public List<E> subList(int fromIndex, int toIndex) {
-        return new SubList(this, fromIndex, toIndex);
-    }
-
-    public Object[] toArray() {
-        E[] data = getData();
-        return toArray(data, 0, data.length);
-    }
-
-    public <T> T[] toArray(T[] a) {
-        E[] data = getData();
-        return (T[]) toArray(a, data, 0, data.length);
-    }
-
-    @Override
-    public String toString() {
-        StringBuilder sb = new StringBuilder("[");
+    /**
+     * Removes the first occurrence of the specified element from this list,
+     * if it is present.  If this list does not contain the element, it is
+     * unchanged.  More formally, removes the element with the lowest index
+     * <tt>i</tt> such that
+     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
+     * (if such an element exists).  Returns <tt>true</tt> if this list
+     * contained the specified element (or equivalently, if this list
+     * changed as a result of the call).
+     *
+     * @param o element to be removed from this list, if present
+     * @return <tt>true</tt> if this list contained the specified element
+     */
+    public boolean remove(Object o) {
+        final ReentrantLock lock = this.lock;
+        lock.lock();
+        try {
+            Object[] elements = getArray();
+            int len = elements.length;
+            if (len != 0) {
+                // Copy while searching for element to remove
+                // This wins in the normal case of element being present
+                int newlen = len - 1;
+                Object[] newElements = new Object[newlen];
+
+                for (int i = 0; i < newlen; ++i) {
+                    if (eq(o, elements[i])) {
+                        // found one;  copy remaining and exit
+                        for (int k = i + 1; k < len; ++k)
+                            newElements[k-1] = elements[k];
+                        setArray(newElements);
+                        return true;
+                    } else
+                        newElements[i] = elements[i];
+                }
 
-        Iterator it = listIterator();
-        while (it.hasNext()) {
-            sb.append(String.valueOf(it.next()));
-            sb.append(", ");
-        }
-        if (sb.length() > 1) {
-            sb.setLength(sb.length() - 2);
+                // special handling for last cell
+                if (eq(o, elements[newlen])) {
+                    setArray(newElements);
+                    return true;
+                }
+            }
+            return false;
+        } finally {
+            lock.unlock();
         }
-        sb.append("]");
-        return sb.toString();
     }
 
-    // private and package private methods
+    /**
+     * Removes from this list all of the elements whose index is between
+     * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
+     * Shifts any succeeding elements to the left (reduces their index).
+     * This call shortens the list by <tt>(toIndex - fromIndex)</tt> elements.
+     * (If <tt>toIndex==fromIndex</tt>, this operation has no effect.)
+     *
+     * @param fromIndex index of first element to be removed
+     * @param toIndex index after last element to be removed
+     * @throws IndexOutOfBoundsException if fromIndex or toIndex out of range
+     *         (@code{fromIndex < 0 || toIndex > size() || toIndex < fromIndex})
+     */
+    private void removeRange(int fromIndex, int toIndex) {
+        final ReentrantLock lock = this.lock;
+        lock.lock();
+        try {
+            Object[] elements = getArray();
+            int len = elements.length;
 
-    @SuppressWarnings("unchecked")
-    private final E[] newElementArray(int size) {
-        return (E[])new Object[size];
+            if (fromIndex < 0 || toIndex > len || toIndex < fromIndex)
+                throw new IndexOutOfBoundsException();
+            int newlen = len - (toIndex - fromIndex);
+            int numMoved = len - toIndex;
+            if (numMoved == 0)
+                setArray(Java6Arrays.copyOf(elements, newlen));
+            else {
+                Object[] newElements = new Object[newlen];
+                System.arraycopy(elements, 0, newElements, 0, fromIndex);
+                System.arraycopy(elements, toIndex, newElements,
+                                 fromIndex, numMoved);
+                setArray(newElements);
+            }
+        } finally {
+            lock.unlock();
+        }
     }
 
     /**
-     * sets the internal data array
+     * Append the element if not present.
      *
-     * @param data array to set
+     * @param e element to be added to this list, if absent
+     * @return <tt>true</tt> if the element was added
      */
-    private final void setData(E[] data) {
-        arr = data;
+    public boolean addIfAbsent(E e) {
+        final ReentrantLock lock = this.lock;
+        lock.lock();
+        try {
+            // Copy while checking if already present.
+            // This wins in the most common case where it is not present
+            Object[] elements = getArray();
+            int len = elements.length;
+            Object[] newElements = new Object[len + 1];
+            for (int i = 0; i < len; ++i) {
+                if (eq(e, elements[i]))
+                    return false; // exit, throwing away copy
+                else
+                    newElements[i] = elements[i];
+            }
+            newElements[len] = e;
+            setArray(newElements);
+            return true;
+        } finally {
+            lock.unlock();
+        }
     }
 
     /**
-     * gets the internal data array
+     * Returns <tt>true</tt> if this list contains all of the elements of the
+     * specified collection.
      *
-     * @return the data array
+     * @param c collection to be checked for containment in this list
+     * @return <tt>true</tt> if this list contains all of the elements of the
+     *         specified collection
+     * @throws NullPointerException if the specified collection is null
+     * @see #contains(Object)
      */
-    final E[] getData() {
-        if (arr == null) {
-            return newElementArray(0);
+    public boolean containsAll(Collection<?> c) {
+        Object[] elements = getArray();
+        int len = elements.length;
+        for (Object e : c) {
+            if (indexOf(e, elements, 0, len) < 0)
+                return false;
         }
-        return arr;
+        return true;
     }
 
     /**
-     * Removes from the specified range of this list
-     * all the elements that are contained in the specified collection
-     * <p/>
-     * !should be called under lock
-     *
-     * @return Returns the number of removed elements
+     * Removes from this list all of its elements that are contained in
+     * the specified collection. This is a particularly expensive operation
+     * in this class because of the need for an internal temporary array.
+     *
+     * @param c collection containing elements to be removed from this list
+     * @return <tt>true</tt> if this list changed as a result of the call
+     * @throws ClassCastException if the class of an element of this list
+     *         is incompatible with the specified collection (optional)
+     * @throws NullPointerException if this list contains a null element and the
+     *         specified collection does not permit null elements (optional),
+     *         or if the specified collection is null
+     * @see #remove(Object)
      */
-    final int removeAll(Collection c, int start, int size) {
-        int ssize = c.size();
-        if (ssize == 0) {
-            return 0;
-        }
-        Object[] old = getData();
-        int arrsize = old.length;
-        if (arrsize == 0) {
-            return 0;
-        }
-        Object[] data = new Object[size];
-        int j = 0;
-        for (int i = start; i < (start + size); i++) {
-            if (!c.contains(old[i])) {
-                data[j++] = old[i];
+    public boolean removeAll(Collection<?> c) {
+        final ReentrantLock lock = this.lock;
+        lock.lock();
+        try {
+            Object[] elements = getArray();
+            int len = elements.length;
+            if (len != 0) {
+                // temp array holds those elements we know we want to keep
+                int newlen = 0;
+                Object[] temp = new Object[len];
+                for (int i = 0; i < len; ++i) {
+                    Object element = elements[i];
+                    if (!c.contains(element))
+                        temp[newlen++] = element;
+                }
+                if (newlen != len) {
+                    setArray(Java6Arrays.copyOf(temp, newlen));
+                    return true;
+                }
             }
+            return false;
+        } finally {
+            lock.unlock();
         }
-        if (j != size) {
-            E[] result = newElementArray(arrsize - (size - j));
-            System.arraycopy(old, 0, result, 0, start);
-            System.arraycopy(data, 0, result, start, j);
-            System.arraycopy(old, start + size, result, start + j, arrsize
-                    - (start + size));
-            setData(result);
-            return (size - j);
-        }
-        return 0;
     }
 
     /**
-     * Retains only the elements in the specified range of this list
-     * that are contained in the specified collection
-     *
-     * @return Returns the number of removed elements
+     * Retains only the elements in this list that are contained in the
+     * specified collection.  In other words, removes from this list all of
+     * its elements that are not contained in the specified collection.
+     *
+     * @param c collection containing elements to be retained in this list
+     * @return <tt>true</tt> if this list changed as a result of the call
+     * @throws ClassCastException if the class of an element of this list
+     *         is incompatible with the specified collection (optional)
+     * @throws NullPointerException if this list contains a null element and the
+     *         specified collection does not permit null elements (optional),
+     *         or if the specified collection is null
+     * @see #remove(Object)
      */
-    // should be called under lock
-    int retainAll(Collection c, int start, int size) {
-        Object[] old = getData();
-        if (size == 0) {
-            return 0;
-        }
-        if (c.size() == 0) {
-            E[] data;
-            if (size == old.length) {
-                data = newElementArray(0);
-            } else {
-                data = newElementArray(old.length - size);
-                System.arraycopy(old, 0, data, 0, start);
-                System.arraycopy(old, start + size, data, start, old.length
-                        - start - size);
-            }
-            setData(data);
-            return size;
-        }
-        Object[] temp = new Object[size];
-        int pos = 0;
-        for (int i = start; i < (start + size); i++) {
-            if (c.contains(old[i])) {
-                temp[pos++] = old[i];
+    public boolean retainAll(Collection<?> c) {
+        final ReentrantLock lock = this.lock;
+        lock.lock();
+        try {
+            Object[] elements = getArray();
+            int len = elements.length;
+            if (len != 0) {
+                // temp array holds those elements we know we want to keep
+                int newlen = 0;
+                Object[] temp = new Object[len];
+                for (int i = 0; i < len; ++i) {
+                    Object element = elements[i];
+                    if (c.contains(element))
+                        temp[newlen++] = element;
+                }
+                if (newlen != len) {
+                    setArray(Java6Arrays.copyOf(temp, newlen));
+                    return true;
+                }
             }
+            return false;
+        } finally {
+            lock.unlock();
         }
-        if (pos == size) {
-            return 0;
-        }
-        E[] data = newElementArray(pos + old.length - size);
-        System.arraycopy(old, 0, data, 0, start);
-        System.arraycopy(temp, 0, data, start, pos);
-        System.arraycopy(old, start + size, data, start + pos, old.length
-                - start - size);
-        setData(data);
-        return (size - pos);
     }
 
     /**
-     * Removes specified range from this list
+     * Appends all of the elements in the specified collection that
+     * are not already contained in this list, to the end of
+     * this list, in the order that they are returned by the
+     * specified collection's iterator.
+     *
+     * @param c collection containing elements to be added to this list
+     * @return the number of elements added
+     * @throws NullPointerException if the specified collection is null
+     * @see #addIfAbsent(Object)
      */
-    E removeRange(int start, int size) {
+    public int addAllAbsent(Collection<? extends E> c) {
+        Object[] cs = c.toArray();
+        if (cs.length == 0)
+            return 0;
+        Object[] uniq = new Object[cs.length];
+        final ReentrantLock lock = this.lock;
         lock.lock();
         try {
-            int sizeArr = size();
-            checkIndexExlusive(start, sizeArr);
-            checkIndexInclusive(start + size, sizeArr);
-            E[] data;
-            data = newElementArray(sizeArr - size);
-            E[] oldArr = getData();
-            System.arraycopy(oldArr, 0, data, 0, start);
-            E old = oldArr[start];
-            if (sizeArr > (start + size)) {
-                System.arraycopy(oldArr, start + size, data, start, sizeArr
-                        - (start + size));
+            Object[] elements = getArray();
+            int len = elements.length;
+            int added = 0;
+            for (int i = 0; i < cs.length; ++i) { // scan for duplicates
+                Object e = cs[i];
+                if (indexOf(e, elements, 0, len) < 0 &&
+                    indexOf(e, uniq, 0, added) < 0)
+                    uniq[added++] = e;
+            }
+            if (added > 0) {
+                Object[] newElements = Java6Arrays.copyOf(elements, len + added);
+                System.arraycopy(uniq, 0, newElements, len, added);
+                setArray(newElements);
             }
-            setData(data);
-            return old;
+            return added;
         } finally {
             lock.unlock();
         }
     }
 
-    // some util static functions to use by iterators and methods
     /**
-     * Returns an array containing all of the elements
-     * in the specified range of the array in proper sequence
+     * Removes all of the elements from this list.
+     * The list will be empty after this call returns.
      */
-    static Object[] toArray(Object[] data, int start, int size) {
-        Object[] result = new Object[size];
-        System.arraycopy(data, start, result, 0, size);
-        return result;
+    public void clear() {
+        final ReentrantLock lock = this.lock;
+        lock.lock();
+        try {
+            setArray(new Object[0]);
+        } finally {
+            lock.unlock();
+        }
     }
 
     /**
-     * Returns an array containing all of the elements
-     * in the specified range of the array in proper sequence,
-     * stores the result in the array, specified by first parameter
-     * (as for public instance method toArray(Object[] to)
+     * Appends all of the elements in the specified collection to the end
+     * of this list, in the order that they are returned by the specified
+     * collection's iterator.
+     *
+     * @param c collection containing elements to be added to this list
+     * @return <tt>true</tt> if this list changed as a result of the call
+     * @throws NullPointerException if the specified collection is null
+     * @see #add(Object)
      */
-    static Object[] toArray(Object[] to, Object[] data, int start, int size) {
-        int l = data.length;
-        if (to.length < l) {
-            to = (Object[]) Array.newInstance(to.getClass().getComponentType(),
-                    l);
-        } else {
-            if (to.length > l) {
-                to[l] = null;
-            }
+    public boolean addAll(Collection<? extends E> c) {
+        Object[] cs = c.toArray();
+        if (cs.length == 0)
+            return false;
+        final ReentrantLock lock = this.lock;
+        lock.lock();
+        try {
+            Object[] elements = getArray();
+            int len = elements.length;
+            Object[] newElements = Java6Arrays.copyOf(elements, len + cs.length);
+            System.arraycopy(cs, 0, newElements, len, cs.length);
+            setArray(newElements);
+            return true;
+        } finally {
+            lock.unlock();
         }
-        System.arraycopy(data, start, to, 0, size);
-        return to;
     }
 
     /**
-     * Checks if the specified range of the
-     * array contains all of the elements in the collection
-     *
-     * @param c     collection with elements
-     * @param data  array where to search the elements
-     * @param start start index
-     * @param size  size of the range
+     * Inserts all of the elements in the specified collection into this
+     * list, starting at the specified position.  Shifts the element
+     * currently at that position (if any) and any subsequent elements to
+     * the right (increases their indices).  The new elements will appear
+     * in this list in the order that they are returned by the
+     * specified collection's iterator.
+     *
+     * @param index index at which to insert the first element
+     *        from the specified collection
+     * @param c collection containing elements to be added to this list
+     * @return <tt>true</tt> if this list changed as a result of the call
+     * @throws IndexOutOfBoundsException {@inheritDoc}
+     * @throws NullPointerException if the specified collection is null
+     * @see #add(int,Object)
      */
-    static final boolean containsAll(Collection c, Object[] data, int start,
-                                     int size) {
-        if (size == 0) {
-            return false;
-        }
-        Iterator it = c.iterator();
-        while (it.hasNext()) {
-            Object next = it.next();
-            if (indexOf(next, data, start, size) < 0) {
+    public boolean addAll(int index, Collection<? extends E> c) {
+        Object[] cs = c.toArray();
+        final ReentrantLock lock = this.lock;
+        lock.lock();
+        try {
+            Object[] elements = getArray();
+            int len = elements.length;
+            if (index > len || index < 0)
+                throw new IndexOutOfBoundsException("Index: "+index+
+                                                    ", Size: "+len);
+            if (cs.length == 0)
                 return false;
+            int numMoved = len - index;
+            Object[] newElements;
+            if (numMoved == 0)
+                newElements = Java6Arrays.copyOf(elements, len + cs.length);
+            else {
+                newElements = new Object[len + cs.length];
+                System.arraycopy(elements, 0, newElements, 0, index);
+                System.arraycopy(elements, index,
+                                 newElements, index + cs.length,
+                                 numMoved);
             }
+            System.arraycopy(cs, 0, newElements, index, cs.length);
+            setArray(newElements);
+            return true;
+        } finally {
+            lock.unlock();
         }
-        return true;
     }
 
     /**
-     * Returns the index in the specified range of the data array
-     * of the last occurrence of the specified element
+     * Save the state of the list to a stream (i.e., serialize it).
      *
-     * @param o     element to search
-     * @param data  array where to search
-     * @param start start index
-     * @param size  size of the range
-     * @return
-     */
-    static final int lastIndexOf(Object o, Object[] data, int start, int size) {
-        if (size == 0) {
-            return -1;
-        }
-        if (o != null) {
-            for (int i = start + size - 1; i > start - 1; i--) {
-                if (o.equals(data[i])) {
-                    return i;
-                }
-            }
-        } else {
-            for (int i = start + size - 1; i > start - 1; i--) {
-                if (data[i] == null) {
-                    return i;
-                }
-            }
-        }
-        return -1;
+     * @serialData The length of the array backing the list is emitted
+     *               (int), followed by all of its elements (each an Object)
+     *               in the proper order.
+     * @param s the stream
+     */
+    private void writeObject(java.io.ObjectOutputStream s)
+        throws java.io.IOException{
+
+        // Write out element count, and any hidden stuff
+        s.defaultWriteObject();
+
+        Object[] elements = getArray();
+        int len = elements.length;
+        // Write out array length
+        s.writeInt(len);
+
+        // Write out all elements in the proper order.
+        for (int i = 0; i < len; i++)
+            s.writeObject(elements[i]);
+    }
+
+    /**
+     * Reconstitute the list from a stream (i.e., deserialize it).
+     * @param s the stream
+     */
+    private void readObject(java.io.ObjectInputStream s)
+        throws java.io.IOException, ClassNotFoundException {
+
+        // Read in size, and any hidden stuff
+        s.defaultReadObject();
+
+        // bind to new lock
+        resetLock();
+
+        // Read in array length and allocate array
+        int len = s.readInt();
+        Object[] elements = new Object[len];
+
+        // Read in all elements in the proper order.
+        for (int i = 0; i < len; i++)
+            elements[i] = s.readObject();
+        setArray(elements);
     }
 
     /**
-     * Returns the index in the specified range of the data array
-     * of the first occurrence of the specified element
+     * Returns a string representation of this list.  The string
+     * representation consists of the string representations of the list's
+     * elements in the order they are returned by its iterator, enclosed in
+     * square brackets (<tt>"[]"</tt>).  Adjacent elements are separated by
+     * the characters <tt>", "</tt> (comma and space).  Elements are
+     * converted to strings as by {@link String#valueOf(Object)}.
      *
-     * @param o     element to search
-     * @param data  array where to search
-     * @param start start index
-     * @param size  end index
-     * @return
-     */
-    static final int indexOf(Object o, Object[] data, int start, int size) {
-        if (size == 0) {
-            return -1;
-        }
-        if (o == null) {
-            for (int i = start; i < start + size; i++) {
-                if (data[i] == null) {
-                    return i;
-                }
-            }
-        } else {
-            for (int i = start; i < start + size; i++) {
-                if (o.equals(data[i])) {
-                    return i;
-                }
-            }
-        }
-        return -1;
+     * @return a string representation of this list
+     */
+    public String toString() {
+        return Arrays.toString(getArray());
     }
 
     /**
-     * Throws <code>IndexOutOfBoundsException</code> if <code>index</code>
-     * is out of the list bounds.
+     * Compares the specified object with this list for equality.
+     * Returns {@code true} if the specified object is the same object
+     * as this object, or if it is also a {@link List} and the sequence
+     * of elements returned by an {@linkplain List#iterator() iterator}
+     * over the specified list is the same as the sequence returned by
+     * an iterator over this list.  The two sequences are considered to
+     * be the same if they have the same length and corresponding
+     * elements at the same position in the sequence are <em>equal</em>.
+     * Two elements {@code e1} and {@code e2} are considered
+     * <em>equal</em> if {@code (e1==null ? e2==null : e1.equals(e2))}.
      *
-     * @param index element index to check.
+     * @param o the object to be compared for equality with this list
+     * @return {@code true} if the specified object is equal to this list
      */
-    static final void checkIndexInclusive(int index, int size) {
-        if (index < 0 || index > size) {
-            throw new IndexOutOfBoundsException("Index is " + index + ", size is " + size);
-        }
+    public boolean equals(Object o) {
+        if (o == this)
+            return true;
+        if (!(o instanceof List))
+            return false;
+
+        List<?> list = (List<?>)(o);
+        Iterator<?> it = list.iterator();
+        Object[] elements = getArray();
+        int len = elements.length;
+        for (int i = 0; i < len; ++i)
+            if (!it.hasNext() || !eq(elements[i], it.next()))
+                return false;
+        if (it.hasNext())
+            return false;
+        return true;
     }
 
     /**
-     * Throws <code>IndexOutOfBoundsException</code> if <code>index</code>
-     * is out of the list bounds. Excluding the last element.
+     * Returns the hash code value for this list.
+     *
+     * <p>This implementation uses the definition in {@link List#hashCode}.
      *
-     * @param index element index to check.
+     * @return the hash code value for this list
      */
-    static final void checkIndexExlusive(int index, int size) {
-        if (index < 0 || index >= size) {
-            throw new IndexOutOfBoundsException("Index is " + index + ", size is " + size);
+    public int hashCode() {
+        int hashCode = 1;
+        Object[] elements = getArray();
+        int len = elements.length;
+        for (int i = 0; i < len; ++i) {
+            Object obj = elements[i];
+            hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
         }
+        return hashCode;
     }
 
     /**
-     * list iterator implementation,
-     * when created gets snapshot of the list,
-     * so never throws ConcurrentModificationException
+     * Returns an iterator over the elements in this list in proper sequence.
+     *
+     * <p>The returned iterator provides a snapshot of the state of the list
+     * when the iterator was constructed. No synchronization is needed while
+     * traversing the iterator. The iterator does <em>NOT</em> support the
+     * <tt>remove</tt> method.
+     *
+     * @return an iterator over the elements in this list in proper sequence
      */
-    private static class ListIteratorImpl implements ListIterator {
-        private final Object[] arr;
+    public Iterator<E> iterator() {
+        return new COWIterator<E>(getArray(), 0);
+    }
 
-        private int current;
+    /**
+     * {@inheritDoc}
+     *
+     * <p>The returned iterator provides a snapshot of the state of the list
+     * when the iterator was constructed. No synchronization is needed while
+     * traversing the iterator. The iterator does <em>NOT</em> support the
+     * <tt>remove</tt>, <tt>set</tt> or <tt>add</tt> methods.
+     */
+    public ListIterator<E> listIterator() {
+        return new COWIterator<E>(getArray(), 0);
+    }
 
-        private final int size;
+    /**
+     * {@inheritDoc}
+     *
+     * <p>The returned iterator provides a snapshot of the state of the list
+     * when the iterator was constructed. No synchronization is needed while
+     * traversing the iterator. The iterator does <em>NOT</em> support the
+     * <tt>remove</tt>, <tt>set</tt> or <tt>add</tt> methods.
+     *
+     * @throws IndexOutOfBoundsException {@inheritDoc}
+     */
+    public ListIterator<E> listIterator(final int index) {
+        Object[] elements = getArray();
+        int len = elements.length;
+        if (index<0 || index>len)
+            throw new IndexOutOfBoundsException("Index: "+index);
 
-        final int size() {
-            return size;
-        }
+        return new COWIterator<E>(elements, index);
+    }
 
-        public ListIteratorImpl(Object[] data, int current) {
-            this.current = current;
-            arr = data;
-            size = data.length;
-        }
+    private static class COWIterator<E> implements ListIterator<E> {
+        /** Snapshot of the array **/
+        private final Object[] snapshot;
+        /** Index of element to be returned by subsequent call to next.  */
+        private int cursor;
 
-        public void add(Object o) {
-            throw new UnsupportedOperationException("Unsupported operation add");
+        private COWIterator(Object[] elements, int initialCursor) {
+            cursor = initialCursor;
+            snapshot = elements;
         }
 
         public boolean hasNext() {
-            if (current < size) {
-                return true;
-            }
-            return false;
+            return cursor < snapshot.length;
         }
 
         public boolean hasPrevious() {
-            return current > 0;
+            return cursor > 0;
         }
 
-        public Object next() {
-            if (hasNext()) {
-                return arr[current++];
-            }
-            throw new NoSuchElementException("pos is " + current + ", size is " + size);
+        @SuppressWarnings("unchecked")
+        public E next() {
+            if (! hasNext())
+                throw new NoSuchElementException();
+            return (E) snapshot[cursor++];
         }
 
-        public int nextIndex() {
-            return current;
+        @SuppressWarnings("unchecked")
+        public E previous() {
+            if (! hasPrevious())
+                throw new NoSuchElementException();
+            return (E) snapshot[--cursor];
         }
 
-        public Object previous() {
-            if (hasPrevious()) {
-                return arr[--current];
-            }
-            throw new NoSuchElementException("pos is " + (current-1) + ", size is " + size);
+        public int nextIndex() {
+            return cursor;
         }
 
         public int previousIndex() {
-            return current - 1;
+            return cursor-1;
         }
 
+        /**
+         * Not supported. Always throws UnsupportedOperationException.
+         * @throws UnsupportedOperationException always; <tt>remove</tt>
+         *         is not supported by this iterator.
+         */
         public void remove() {
-            throw new UnsupportedOperationException("Unsupported operation remove");
+            throw new UnsupportedOperationException();
         }
 
-        public void set(Object o) {
-            throw new UnsupportedOperationException("Unsupported operation set");
+        /**
+         * Not supported. Always throws UnsupportedOperationException.
+         * @throws UnsupportedOperationException always; <tt>set</tt>
+         *         is not supported by this iterator.
+         */
+        public void set(E e) {
+            throw new UnsupportedOperationException();
         }
 
+        /**
+         * Not supported. Always throws UnsupportedOperationException.
+         * @throws UnsupportedOperationException always; <tt>add</tt>
+         *         is not supported by this iterator.
+         */
+        public void add(E e) {
+            throw new UnsupportedOperationException();
+        }
     }
 
     /**
-     * Keeps a state of sublist implementation,
-     * size and array declared as final,
-     * so we'll never get the unconsistent state
+     * Returns a view of the portion of this list between
+     * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
+     * The returned list is backed by this list, so changes in the
+     * returned list are reflected in this list.
+     *
+     * <p>The semantics of the list returned by this method become
+     * undefined if the backing list (i.e., this list) is modified in
+     * any way other than via the returned list.
+     *
+     * @param fromIndex low endpoint (inclusive) of the subList
+     * @param toIndex high endpoint (exclusive) of the subList
+     * @return a view of the specified range within this list
+     * @throws IndexOutOfBoundsException {@inheritDoc}
      */
-    static final class SubListReadData {
-        final int size;
-
-        final Object[] data;
-
-        SubListReadData(int size, Object[] data) {
-            this.size = size;
-            this.data = data;
+    public List<E> subList(int fromIndex, int toIndex) {
+        final ReentrantLock lock = this.lock;
+        lock.lock();
+        try {
+            Object[] elements = getArray();
+            int len = elements.length;
+            if (fromIndex < 0 || toIndex > len || fromIndex > toIndex)
+                throw new IndexOutOfBoundsException();
+            return new COWSubList<E>(this, fromIndex, toIndex);
+        } finally {
+            lock.unlock();
         }
     }
 
     /**
-     * Represents a list returned by <code>sublist()</code>.
-     */
-    static class SubList implements List {
-        private final CopyOnWriteArrayList list;
-
-        private volatile SubListReadData read;
-
-        private final int start;
-
-        /**
-         * Sublist constructor.
-         *
-         * @param list    backing list.
-         * @param fromIdx startingIndex, inclusive
-         * @param toIdx   endIndex, exclusive
-         */
-        public SubList(CopyOnWriteArrayList list, int fromIdx, int toIdx) {
-            this.list = list;
-            Object[] data = list.getData();
-            int size = toIdx - fromIdx;
-            checkIndexExlusive(fromIdx, data.length);
-            checkIndexInclusive(toIdx, data.length);
-            read = new SubListReadData(size, list.getData());
-            start = fromIdx;
-        }
-
-        /**
-         * throws ConcurrentModificationException when the list
-         * is structurally modified in the other way other than via this subList
-         * <p/>
-         * Should be called under lock!
-         */
-        private void checkModifications() {
-            if (read.data != list.getData()) {
+     * Sublist for CopyOnWriteArrayList.
+     * This class extends AbstractList merely for convenience, to
+     * avoid having to define addAll, etc. This doesn't hurt, but
+     * is wasteful.  This class does not need or use modCount
+     * mechanics in AbstractList, but does need to check for
+     * concurrent modification using similar mechanics.  On each
+     * operation, the array that we expect the backing list to use
+     * is checked and updated.  Since we do this for all of the
+     * base operations invoked by those defined in AbstractList,
+     * all is well.  While inefficient, this is not worth
+     * improving.  The kinds of list operations inherited from
+     * AbstractList are already so slow on COW sublists that
+     * adding a bit more space/time doesn't seem even noticeable.
+     */
+    private static class COWSubList<E>
+        extends AbstractList<E>
+        implements RandomAccess
+    {
+        private final CopyOnWriteArrayList<E> l;
+        private final int offset;
+        private int size;
+        private Object[] expectedArray;
+
+        // only call this holding l's lock
+        COWSubList(CopyOnWriteArrayList<E> list,
+                   int fromIndex, int toIndex) {
+            l = list;
+            expectedArray = l.getArray();
+            offset = fromIndex;
+            size = toIndex - fromIndex;
+        }
+
+        // only call this holding l's lock
+        private void checkForComodification() {
+            if (l.getArray() != expectedArray)
                 throw new ConcurrentModificationException();
-            }
         }
 
-        /**
-         * @see java.util.List#listIterator(int)
-         */
-        public ListIterator listIterator(int startIdx) {
-            return new SubListIterator(startIdx, read);
+        // only call this holding l's lock
+        private void rangeCheck(int index) {
+            if (index<0 || index>=size)
+                throw new IndexOutOfBoundsException("Index: "+index+
+                                                    ",Size: "+size);
         }
 
-        /**
-         * @see java.util.List#set(int, java.lang.Object)
-         */
-        public Object set(int index, Object obj) {
-            list.lock.lock();
+        public E set(int index, E element) {
+            final ReentrantLock lock = l.lock;
+            lock.lock();
             try {
-                checkIndexExlusive(index, read.size);
-                checkModifications();
-                Object result = list.set(index + start, obj);
-                read = new SubListReadData(read.size, list.getData());
-                return result;
+                rangeCheck(index);
+                checkForComodification();
+                E x = l.set(index+offset, element);
+                expectedArray = l.getArray();
+                return x;
             } finally {
-                list.lock.unlock();
+                lock.unlock();
             }
         }
 
-        /**
-         * @see java.util.List#get(int)
-         */
-        public Object get(int index) {
-            SubListReadData data = read;
-            if (data.data != list.getData()) {
-                list.lock.lock();
-                try {
-                    data = read;
-                    if (data.data != list.getData()) {
-                        throw new ConcurrentModificationException();
-                    }
-                } finally {
-                    list.lock.unlock();
-                }
-            }
-            checkIndexExlusive(index, data.size);
-            return data.data[index + start];
-        }
-
-        /**
-         * @see java.util.Collection#size()
-         */
-        public int size() {
-            return read.size;
-        }
-
-        /**
-         * @see java.util.List#remove(int)
-         */
-        public Object remove(int index) {
-            list.lock.lock();
+        public E get(int index) {
+            final ReentrantLock lock = l.lock;
+            lock.lock();
             try {
-                checkIndexExlusive(index, read.size);
-                checkModifications();
-                Object obj = list.remove(index + start);
-                read = new SubListReadData(read.size - 1, list.getData());
-                return obj;
+                rangeCheck(index);
+                checkForComodification();
+                return l.get(index+offset);
             } finally {
-                list.lock.unlock();
+                lock.unlock();
             }
         }
 
-        /**
-         * @see java.util.List#add(int, java.lang.Object)
-         */
-        public void add(int index, Object object) {
-            list.lock.lock();
+        public int size() {
+            final ReentrantLock lock = l.lock;
+            lock.lock();
             try {
-                checkIndexInclusive(index, read.size);
-                checkModifications();
-                list.add(index + start, object);
-                read = new SubListReadData(read.size + 1, list.getData());
+                checkForComodification();
+                return size;
             } finally {
-                list.lock.unlock();
+                lock.unlock();
             }
         }
 
-        public boolean add(Object o) {
-            list.lock.lock();
+        public void add(int index, E element) {
+            final ReentrantLock lock = l.lock;
+            lock.lock();
             try {
-                checkModifications();
-                list.add(start + read.size, o);
-                read = new SubListReadData(read.size + 1, list.getData());
-                return true;
+                checkForComodification();
+                if (index<0 || index>size)
+                    throw new IndexOutOfBoundsException();
+                l.add(index+offset, element);
+                expectedArray = l.getArray();
+                size++;
             } finally {
-                list.lock.unlock();
+                lock.unlock();
             }
         }
 
-        public boolean addAll(Collection c) {
-            list.lock.lock();
+        public void clear() {
+            final ReentrantLock lock = l.lock;
+            lock.lock();
             try {
-                checkModifications();
-                int d = list.size();
-                list.addAll(start + read.size, c);
-                read = new SubListReadData(read.size + (list.size() - d), list
-                        .getData());
-                return true;
+                checkForComodification();
+                l.removeRange(offset, offset+size);
+                expectedArray = l.getArray();
+                size = 0;
             } finally {
-                list.lock.unlock();
+                lock.unlock();
             }
         }
 
-        public void clear() {
-            list.lock.lock();
+        public E remove(int index) {
+            final ReentrantLock lock = l.lock;
+            lock.lock();
             try {
-                checkModifications();
-                list.removeRange(start, read.size);
-                read = new SubListReadData(0, list.getData());
+                rangeCheck(index);
+                checkForComodification();
+                E result = l.remove(index+offset);
+                expectedArray = l.getArray();
+                size--;
+                return result;
             } finally {
-                list.lock.unlock();
+                lock.unlock();
             }
         }
 
-        public boolean contains(Object o) {
-            return indexOf(o) != -1;
-        }
-
-        public boolean containsAll(Collection c) {
-            SubListReadData b = read;
-            return CopyOnWriteArrayList.containsAll(c, b.data, start, b.size);
-        }
-
-        public int indexOf(Object o) {
-            SubListReadData b = read;
-            int ind = CopyOnWriteArrayList.indexOf(o, b.data, start, b.size)
-                    - start;
-            return ind < 0 ? -1 : ind;
-        }
-
-        public boolean isEmpty() {
-            return read.size == 0;
-        }
-
-        public Iterator iterator() {
-            return new SubListIterator(0, read);
-        }
-
-        public int lastIndexOf(Object o) {
-            SubListReadData b = read;
-            int ind = CopyOnWriteArrayList
-                    .lastIndexOf(o, b.data, start, b.size)
-                    - start;
-            return ind < 0 ? -1 : ind;
-        }
-
-        public ListIterator listIterator() {
-            return new SubListIterator(0, read);
+        public boolean remove(Object o) {
+            int index = indexOf(o);
+            if (index == -1)
+                return false;
+            remove(index);
+            return true;
         }
 
-        public boolean remove(Object o) {
-            list.lock.lock();
+        public Iterator<E> iterator() {
+            final ReentrantLock lock = l.lock;
+            lock.lock();
             try {
-                checkModifications();
-                int i = indexOf(o);
-                if (i == -1) {
-                    return false;
-                }
-                boolean result = list.remove(i + start) != null;
-                if (result) {
-                    read = new SubListReadData(read.size - 1, list.getData());
-                }
-                return result;
+                checkForComodification();
+                return new COWSubListIterator<E>(l, 0, offset, size);
             } finally {
-                list.lock.unlock();
+                lock.unlock();
             }
         }
 
-        public boolean removeAll(Collection c) {
-            list.lock.lock();
+        public ListIterator<E> listIterator(final int index) {
+            final ReentrantLock lock = l.lock;
+            lock.lock();
             try {
-                checkModifications();
-                int removed = list.removeAll(c, start, read.size);
-                if (removed > 0) {
-                    read = new SubListReadData(read.size - removed, list
-                            .getData());
-                    return true;
-                }
+                checkForComodification();
+                if (index<0 || index>size)
+                    throw new IndexOutOfBoundsException("Index: "+index+
+                                                        ", Size: "+size);
+                return new COWSubListIterator<E>(l, index, offset, size);
             } finally {
-                list.lock.unlock();
+                lock.unlock();
             }
-            return false;
         }
 
-        public boolean retainAll(Collection c) {
-            list.lock.lock();
+        public List<E> subList(int fromIndex, int toIndex) {
+            final ReentrantLock lock = l.lock;
+            lock.lock();
             try {
-                checkModifications();
-                int removed = list.retainAll(c, start, read.size);
-                if (removed > 0) {
-                    read = new SubListReadData(read.size - removed, list
-                            .getData());
-                    return true;
-                }
-                return false;
+                checkForComodification();
+                if (fromIndex<0 || toIndex>size)
+                    throw new IndexOutOfBoundsException();
+                return new COWSubList<E>(l, fromIndex + offset,
+                                         toIndex + offset);
             } finally {
-                list.lock.unlock();
+                lock.unlock();
             }
         }
 
-        public List subList(int fromIndex, int toIndex) {
-            return new SubList(list, start + fromIndex, start + toIndex);
-        }
+    }
 
-        public Object[] toArray() {
-            SubListReadData r = read;
-            return CopyOnWriteArrayList.toArray(r.data, start, r.size);
-        }
 
-        public Object[] toArray(Object[] a) {
-            SubListReadData r = read;
-            return CopyOnWriteArrayList.toArray(a, r.data, start, r.size);
+    private static class COWSubListIterator<E> implements ListIterator<E> {
+        private final ListIterator<E> i;
+        private final int index;
+        private final int offset;
+        private final int size;
+
+        COWSubListIterator(List<E> l, int index, int offset,
+                           int size) {
+            this.index = index;
+            this.offset = offset;
+            this.size = size;
+            i = l.listIterator(index+offset);
         }
 
-        /**
-         * @see java.util.List#addAll(int, java.util.Collection)
-         */
-        public boolean addAll(int index, Collection collection) {
-            list.lock.lock();
-            try {
-                checkIndexInclusive(index, read.size);
-                checkModifications();
-                int d = list.size();
-                boolean rt = list.addAll(index + start, collection);
-                read = new SubListReadData(read.size + list.size() - d, list
-                        .getData());
-                return rt;
-            } finally {
-                list.lock.unlock();
-            }
+        public boolean hasNext() {
+            return nextIndex() < size;
         }
 
-        /**
-         * Implementation of <code>ListIterator</code> for the
-         * <code>SubList</code>
-         * gets a snapshot of the sublist,
-         * never throws ConcurrentModificationException
-         */
-        private class SubListIterator extends ListIteratorImpl {
-            private final SubListReadData dataR;
+        public E next() {
+            if (hasNext())
+                return i.next();
+            else
+                throw new NoSuchElementException();
+        }
 
-            /**
-             * Constructs an iterator starting with the given index
-             *
-             * @param index index of the first element to iterate.
-             */
-            private SubListIterator(int index, SubListReadData d) {
-                super(d.data, index + start);
-                this.dataR = d;
-            }
+        public boolean hasPrevious() {
+            return previousIndex() >= 0;
+        }
 
-            /**
-             * @see java.util.ListIterator#nextIndex()
-             */
-            public int nextIndex() {
-                return super.nextIndex() - start;
-            }
+        public E previous() {
+            if (hasPrevious())
+                return i.previous();
+            else
+                throw new NoSuchElementException();
+        }
 
-            /**
-             * @see java.util.ListIterator#previousIndex()
-             */
-            public int previousIndex() {
-                return super.previousIndex() - start;
-            }
+        public int nextIndex() {
+            return i.nextIndex() - offset;
+        }
 
-            /**
-             * @see java.util.Iterator#hasNext()
-             */
-            public boolean hasNext() {
-                return nextIndex() < dataR.size;
-            }
+        public int previousIndex() {
+            return i.previousIndex() - offset;
+        }
 
-            /**
-             * @see java.util.ListIterator#hasPrevious()
-             */
-            public boolean hasPrevious() {
-                return previousIndex() > -1;
-            }
+        public void remove() {
+            throw new UnsupportedOperationException();
         }
 
-    }
+        public void set(E e) {
+            throw new UnsupportedOperationException();
+        }
 
-    //serialization support
-    /**
-     * Writes the object state to the ObjectOutputStream.
-     *
-     * @param oos ObjectOutputStream to write object to.
-     * @throws IOException if an I/O error occur.
-     */
-    private void writeObject(ObjectOutputStream oos) throws IOException {
-        E[] back = getData();
-        int size = back.length;
-        oos.defaultWriteObject();
-        oos.writeInt(size);
-        for (int i = 0; i < size; i++) {
-            oos.writeObject(back[i]);
+        public void add(E e) {
+            throw new UnsupportedOperationException();
         }
     }
 
-    /**
-     * Reads the object state from the ObjectOutputStream.
-     *
-     * @param ois ObjectInputStream to read object from.
-     * @throws IOException if an I/O error occur.
-     */
-    private void readObject(ObjectInputStream ois) throws IOException,
-            ClassNotFoundException {
-        ois.defaultReadObject();
-        int length = ois.readInt();
-        if (length == 0) {
-            setData(newElementArray(0));
-        } else {
-            E[] back = newElementArray(length);
-            for (int i = 0; i < back.length; i++) {
-                back[i] = (E) ois.readObject();
-            }
-            setData(back);
-        }
+    // Support for resetting lock while deserializing
+    private static final Unsafe unsafe = Unsafe.getUnsafe();
+    private static final long lockOffset;
+    static {
+        try {
+            lockOffset = unsafe.objectFieldOffset
+                (CopyOnWriteArrayList.class.getDeclaredField("lock"));
+            } catch (Exception ex) { throw new Error(ex); }
+    }
+    private void resetLock() {
+        unsafe.putObjectVolatile(this, lockOffset, new ReentrantLock());
     }
 }



Mime
View raw message