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