--- jsr166/src/main/java/util/ArrayList.java	2016/10/31 23:02:42	1.36
+++ jsr166/src/main/java/util/ArrayList.java	2016/11/16 00:17:25	1.44
@@ -423,6 +423,11 @@ public class ArrayList<E> extends Abstra
         return (E) elementData[index];
     }
 
+    @SuppressWarnings("unchecked")
+    static <E> E elementAt(Object[] es, int index) {
+        return (E) es[index];
+    }
+
     /**
      * Returns the element at the specified position in this list.
      *
@@ -496,6 +501,7 @@ public class ArrayList<E> extends Abstra
                          s - index);
         elementData[index] = element;
         size = s + 1;
+        // checkInvariants();
     }
 
     /**
@@ -519,6 +525,7 @@ public class ArrayList<E> extends Abstra
                              numMoved);
         elementData[--size] = null; // clear to let GC do its work
 
+        // checkInvariants();
         return oldValue;
     }
 
@@ -552,7 +559,7 @@ public class ArrayList<E> extends Abstra
         return false;
     }
 
-    /*
+    /**
      * Private remove method that skips bounds checking and does not
      * return the value removed.
      */
@@ -571,11 +578,7 @@ public class ArrayList<E> extends Abstra
      */
     public void clear() {
         modCount++;
-
-        // clear to let GC do its work
-        for (int i = 0; i < size; i++)
-            elementData[i] = null;
-
+        Arrays.fill(elementData, 0, size, null);
         size = 0;
     }
 
@@ -604,6 +607,7 @@ public class ArrayList<E> extends Abstra
             elementData = grow(s + numNew);
         System.arraycopy(a, 0, elementData, s, numNew);
         size = s + numNew;
+        // checkInvariants();
         return true;
     }
 
@@ -642,6 +646,7 @@ public class ArrayList<E> extends Abstra
                              numMoved);
         System.arraycopy(a, 0, elementData, index, numNew);
         size = s + numNew;
+        // checkInvariants();
         return true;
     }
 
@@ -664,16 +669,11 @@ public class ArrayList<E> extends Abstra
                     outOfBoundsMsg(fromIndex, toIndex));
         }
         modCount++;
-        int numMoved = size - toIndex;
-        System.arraycopy(elementData, toIndex, elementData, fromIndex,
-                         numMoved);
-
-        // clear to let GC do its work
-        int newSize = size - (toIndex-fromIndex);
-        for (int i = newSize; i < size; i++) {
-            elementData[i] = null;
-        }
-        size = newSize;
+        final Object[] es = elementData;
+        final int oldSize = size;
+        System.arraycopy(es, toIndex, es, fromIndex, oldSize - toIndex);
+        Arrays.fill(es, size -= (toIndex - fromIndex), oldSize, null);
+        // checkInvariants();
     }
 
     /**
@@ -716,8 +716,7 @@ public class ArrayList<E> extends Abstra
      * @see Collection#contains(Object)
      */
     public boolean removeAll(Collection<?> c) {
-        Objects.requireNonNull(c);
-        return batchRemove(c, false);
+        return batchRemove(c, false, 0, size);
     }
 
     /**
@@ -737,36 +736,38 @@ public class ArrayList<E> extends Abstra
      * @see Collection#contains(Object)
      */
     public boolean retainAll(Collection<?> c) {
-        Objects.requireNonNull(c);
-        return batchRemove(c, true);
+        return batchRemove(c, true, 0, size);
     }
 
-    private boolean batchRemove(Collection<?> c, boolean complement) {
-        final Object[] elementData = this.elementData;
-        int r = 0, w = 0;
-        boolean modified = false;
-        try {
-            for (; r < size; r++)
-                if (c.contains(elementData[r]) == complement)
-                    elementData[w++] = elementData[r];
-        } finally {
-            // Preserve behavioral compatibility with AbstractCollection,
-            // even if c.contains() throws.
-            if (r != size) {
-                System.arraycopy(elementData, r,
-                                 elementData, w,
-                                 size - r);
-                w += size - r;
-            }
-            if (w != size) {
-                // clear to let GC do its work
-                for (int i = w; i < size; i++)
-                    elementData[i] = null;
-                modCount += size - w;
-                size = w;
-                modified = true;
+    boolean batchRemove(Collection<?> c, boolean complement,
+                        final int from, final int end) {
+        Objects.requireNonNull(c);
+        final Object[] es = elementData;
+        final boolean modified;
+        int r;
+        // Optimize for initial run of survivors
+        for (r = from; r < end && c.contains(es[r]) == complement; r++)
+            ;
+        if (modified = (r < end)) {
+            int w = r++;
+            try {
+                for (Object e; r < end; r++)
+                    if (c.contains(e = es[r]) == complement)
+                        es[w++] = e;
+            } catch (Throwable ex) {
+                // Preserve behavioral compatibility with AbstractCollection,
+                // even if c.contains() throws.
+                System.arraycopy(es, r, es, w, end - r);
+                w += end - r;
+                throw ex;
+            } finally {
+                final int oldSize = size, deleted = end - w;
+                modCount += deleted;
+                System.arraycopy(es, end, es, w, oldSize - end);
+                Arrays.fill(es, size -= deleted, oldSize, null);
             }
         }
+        // checkInvariants();
         return modified;
     }
 
@@ -911,25 +912,21 @@ public class ArrayList<E> extends Abstra
         }
 
         @Override
-        @SuppressWarnings("unchecked")
-        public void forEachRemaining(Consumer<? super E> consumer) {
-            Objects.requireNonNull(consumer);
+        public void forEachRemaining(Consumer<? super E> action) {
+            Objects.requireNonNull(action);
             final int size = ArrayList.this.size;
             int i = cursor;
-            if (i >= size) {
-                return;
-            }
-            final Object[] elementData = ArrayList.this.elementData;
-            if (i >= elementData.length) {
-                throw new ConcurrentModificationException();
-            }
-            while (i != size && modCount == expectedModCount) {
-                consumer.accept((E) elementData[i++]);
+            if (i < size) {
+                final Object[] es = elementData;
+                if (i >= es.length)
+                    throw new ConcurrentModificationException();
+                for (; i < size && modCount == expectedModCount; i++)
+                    action.accept(elementAt(es, i));
+                // update once at end to reduce heap write traffic
+                cursor = i;
+                lastRet = i - 1;
+                checkForComodification();
             }
-            // update once at end of iteration to reduce heap write traffic
-            cursor = i;
-            lastRet = i - 1;
-            checkForComodification();
         }
 
         final void checkForComodification() {
@@ -1116,6 +1113,33 @@ public class ArrayList<E> extends Abstra
             return true;
         }
 
+        public boolean removeAll(Collection<?> c) {
+            return batchRemove(c, false);
+        }
+
+        public boolean retainAll(Collection<?> c) {
+            return batchRemove(c, true);
+        }
+
+        private boolean batchRemove(Collection<?> c, boolean complement) {
+            checkForComodification();
+            int oldSize = root.size;
+            boolean modified =
+                root.batchRemove(c, complement, offset, offset + size);
+            if (modified)
+                updateSizeAndModCount(root.size - oldSize);
+            return modified;
+        }
+
+        public boolean removeIf(Predicate<? super E> filter) {
+            checkForComodification();
+            int oldSize = root.size;
+            boolean modified = root.removeIf(filter, offset, offset + size);
+            if (modified)
+                updateSizeAndModCount(root.size - oldSize);
+            return modified;
+        }
+
         public Iterator<E> iterator() {
             return listIterator();
         }
@@ -1163,24 +1187,21 @@ public class ArrayList<E> extends Abstra
                     return (E) elementData[offset + (lastRet = i)];
                 }
 
-                @SuppressWarnings("unchecked")
-                public void forEachRemaining(Consumer<? super E> consumer) {
-                    Objects.requireNonNull(consumer);
+                public void forEachRemaining(Consumer<? super E> action) {
+                    Objects.requireNonNull(action);
                     final int size = SubList.this.size;
                     int i = cursor;
-                    if (i >= size) {
-                        return;
-                    }
-                    final Object[] elementData = root.elementData;
-                    if (offset + i >= elementData.length) {
-                        throw new ConcurrentModificationException();
-                    }
-                    while (i != size && modCount == expectedModCount) {
-                        consumer.accept((E) elementData[offset + (i++)]);
+                    if (i < size) {
+                        final Object[] es = root.elementData;
+                        if (offset + i >= es.length)
+                            throw new ConcurrentModificationException();
+                        for (; i < size && modCount == expectedModCount; i++)
+                            action.accept(elementAt(es, offset + i));
+                        // update once at end to reduce heap write traffic
+                        cursor = i;
+                        lastRet = i - 1;
+                        checkForComodification();
                     }
-                    // update once at end of iteration to reduce heap write traffic
-                    lastRet = cursor = i;
-                    checkForComodification();
                 }
 
                 public int nextIndex() {
@@ -1347,15 +1368,12 @@ public class ArrayList<E> extends Abstra
     public void forEach(Consumer<? super E> action) {
         Objects.requireNonNull(action);
         final int expectedModCount = modCount;
-        @SuppressWarnings("unchecked")
-        final E[] elementData = (E[]) this.elementData;
+        final Object[] es = elementData;
         final int size = this.size;
-        for (int i=0; modCount == expectedModCount && i < size; i++) {
-            action.accept(elementData[i]);
-        }
-        if (modCount != expectedModCount) {
+        for (int i = 0; modCount == expectedModCount && i < size; i++)
+            action.accept(elementAt(es, i));
+        if (modCount != expectedModCount)
             throw new ConcurrentModificationException();
-        }
     }
 
     /**
@@ -1416,7 +1434,7 @@ public class ArrayList<E> extends Abstra
         private int fence; // -1 until used; then one past last index
         private int expectedModCount; // initialized when fence set
 
-        /** Create new spliterator covering the given  range */
+        /** Create new spliterator covering the given range */
         ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
                              int expectedModCount) {
             this.list = list; // OK if null unless traversed
@@ -1494,52 +1512,77 @@ public class ArrayList<E> extends Abstra
         }
     }
 
-    @SuppressWarnings("unchecked")
+    // A tiny bit set implementation
+
+    private static long[] nBits(int n) {
+        return new long[((n - 1) >> 6) + 1];
+    }
+    private static void setBit(long[] bits, int i) {
+        bits[i >> 6] |= 1L << i;
+    }
+    private static boolean isClear(long[] bits, int i) {
+        return (bits[i >> 6] & (1L << i)) == 0;
+    }
+
     @Override
     public boolean removeIf(Predicate<? super E> filter) {
+        return removeIf(filter, 0, size);
+    }
+
+    /**
+     * Removes all elements satisfying the given predicate, from index
+     * i (inclusive) to index end (exclusive).
+     */
+    boolean removeIf(Predicate<? super E> filter, int i, final int end) {
         Objects.requireNonNull(filter);
         int expectedModCount = modCount;
         final Object[] es = elementData;
-        final int size = this.size;
-        final boolean modified;
-        int r;
-        for (r = 0; r < size; r++)
-            if (filter.test((E) es[r]))
-                break;
-        if (modified = (r < size)) {
+        // Optimize for initial run of survivors
+        for (; i < end && !filter.test(elementAt(es, i)); i++)
+            ;
+        // Tolerate predicates that reentrantly access the collection for
+        // read (but writers still get CME), so traverse once to find
+        // elements to delete, a second pass to physically expunge.
+        if (i < end) {
+            final int beg = i;
+            final long[] deathRow = nBits(end - beg);
+            deathRow[0] = 1L;   // set bit 0
+            for (i = beg + 1; i < end; i++)
+                if (filter.test(elementAt(es, i)))
+                    setBit(deathRow, i - beg);
+            if (modCount != expectedModCount)
+                throw new ConcurrentModificationException();
             expectedModCount++;
             modCount++;
-            int w = r++;
-            try {
-                for (E e; r < size; r++)
-                    if (!filter.test(e = (E) es[r]))
-                        es[w++] = e;
-                Arrays.fill(es, (this.size = w), size, null);
-            } catch (Throwable ex) {
-                // copy remaining elements
-                System.arraycopy(es, r, es, w, size - r);
-                Arrays.fill(es, (this.size = w + size - r), size, null);
-                throw ex;
-            }
+            int w = beg;
+            for (i = beg; i < end; i++)
+                if (isClear(deathRow, i - beg))
+                    es[w++] = es[i];
+            final int oldSize = size;
+            System.arraycopy(es, end, es, w, oldSize - end);
+            Arrays.fill(es, size -= (end - w), oldSize, null);
+            // checkInvariants();
+            return true;
+        } else {
+            if (modCount != expectedModCount)
+                throw new ConcurrentModificationException();
+            // checkInvariants();
+            return false;
         }
-        if (modCount != expectedModCount)
-            throw new ConcurrentModificationException();
-        return modified;
     }
 
     @Override
-    @SuppressWarnings("unchecked")
     public void replaceAll(UnaryOperator<E> operator) {
         Objects.requireNonNull(operator);
         final int expectedModCount = modCount;
+        final Object[] es = elementData;
         final int size = this.size;
-        for (int i=0; modCount == expectedModCount && i < size; i++) {
-            elementData[i] = operator.apply((E) elementData[i]);
-        }
-        if (modCount != expectedModCount) {
+        for (int i = 0; modCount == expectedModCount && i < size; i++)
+            es[i] = operator.apply(elementAt(es, i));
+        if (modCount != expectedModCount)
             throw new ConcurrentModificationException();
-        }
         modCount++;
+        // checkInvariants();
     }
 
     @Override
@@ -1547,9 +1590,14 @@ public class ArrayList<E> extends Abstra
     public void sort(Comparator<? super E> c) {
         final int expectedModCount = modCount;
         Arrays.sort((E[]) elementData, 0, size, c);
-        if (modCount != expectedModCount) {
+        if (modCount != expectedModCount)
             throw new ConcurrentModificationException();
-        }
         modCount++;
+        // checkInvariants();
+    }
+
+    void checkInvariants() {
+        // assert size >= 0;
+        // assert size == elementData.length || elementData[size] == null;
     }
 }