Skip to content

Instantly share code, notes, and snippets.

@gfx

gfx/openjdk7-android-ArrayList.java.diff

Last active April 13, 2016 23:57
Show Gist options
  • Save gfx/d6b9f9de793fc3ccabb77a52132947a4 to your computer and use it in GitHub Desktop.
Save gfx/d6b9f9de793fc3ccabb77a52132947a4 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
openjdk7-android-ArrayList.java.diff
diff --git a/var/folders/tw/sdhbgsb51lvb38tjhcd3_25w0000gn/T/cuMqek0FbI.java b/var/folders/tw/sdhbgsb51lvb38tjhcd3_25w0000gn/T/HSyD_0pwnD.java
index 14b0fbf..77aa035 100644
--- a/var/folders/tw/sdhbgsb51lvb38tjhcd3_25w0000gn/T/cuMqek0FbI.java
+++ b/var/folders/tw/sdhbgsb51lvb38tjhcd3_25w0000gn/T/HSyD_0pwnD.java
@@ -1,5 +1,6 @@
/*
- * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (C) 2014 The Android Open Source Project
+ * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
@@ -25,6 +26,10 @@
package java.util;
+import java.util.function.Consumer;
+import java.util.function.Predicate;
+import java.util.function.UnaryOperator;
+
/**
* Resizable-array implementation of the <tt>List</tt> interface. Implements
* all optional list operations, and permits all elements, including
@@ -66,9 +71,9 @@ package java.util;
* unsynchronized access to the list:<pre>
* List list = Collections.synchronizedList(new ArrayList(...));</pre>
*
- * <p><a name="fail-fast"/>
+ * <p><a name="fail-fast">
* The iterators returned by this class's {@link #iterator() iterator} and
- * {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:
+ * {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:</a>
* if the list is structurally modified at any time after the iterator is
* created, in any way except through the iterator's own
* {@link ListIterator#remove() remove} or
@@ -105,10 +110,24 @@ public class ArrayList<E> extends AbstractList<E>
private static final long serialVersionUID = 8683452581122892189L;
/**
+ * Default initial capacity.
+ */
+ private static final int DEFAULT_CAPACITY = 10;
+
+ /**
+ * Shared empty array instance used for empty instances.
+ */
+ private static final Object[] EMPTY_ELEMENTDATA = {};
+
+ /**
* The array buffer into which the elements of the ArrayList are stored.
- * The capacity of the ArrayList is the length of this array buffer.
+ * The capacity of the ArrayList is the length of this array buffer. Any
+ * empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
+ * DEFAULT_CAPACITY when the first element is added.
+ *
+ * Package private to allow access from java.util.Collections.
*/
- private transient Object[] elementData;
+ transient Object[] elementData;
/**
* The size of the ArrayList (the number of elements it contains).
@@ -136,7 +155,8 @@ public class ArrayList<E> extends AbstractList<E>
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
- this(10);
+ super();
+ this.elementData = EMPTY_ELEMENTDATA;
}
/**
@@ -162,8 +182,7 @@ public class ArrayList<E> extends AbstractList<E>
*/
public void trimToSize() {
modCount++;
- int oldCapacity = elementData.length;
- if (size < oldCapacity) {
+ if (size < elementData.length) {
elementData = Arrays.copyOf(elementData, size);
}
}
@@ -176,12 +195,29 @@ public class ArrayList<E> extends AbstractList<E>
* @param minCapacity the desired minimum capacity
*/
public void ensureCapacity(int minCapacity) {
- if (minCapacity > 0)
- ensureCapacityInternal(minCapacity);
+ int minExpand = (elementData != EMPTY_ELEMENTDATA)
+ // any size if real element table
+ ? 0
+ // larger than default for empty table. It's already supposed to be
+ // at default size.
+ : DEFAULT_CAPACITY;
+
+ if (minCapacity > minExpand) {
+ ensureExplicitCapacity(minCapacity);
+ }
}
private void ensureCapacityInternal(int minCapacity) {
+ if (elementData == EMPTY_ELEMENTDATA) {
+ minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
+ }
+
+ ensureExplicitCapacity(minCapacity);
+ }
+
+ private void ensureExplicitCapacity(int minCapacity) {
modCount++;
+
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
@@ -300,14 +336,13 @@ public class ArrayList<E> extends AbstractList<E>
*/
public Object clone() {
try {
- @SuppressWarnings("unchecked")
- ArrayList<E> v = (ArrayList<E>) super.clone();
+ ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
- throw new InternalError();
+ throw new InternalError(e);
}
}
@@ -364,13 +399,6 @@ public class ArrayList<E> extends AbstractList<E>
return a;
}
- // Positional Access Operations
-
- @SuppressWarnings("unchecked")
- E elementData(int index) {
- return (E) elementData[index];
- }
-
/**
* Returns the element at the specified position in this list.
*
@@ -379,9 +407,10 @@ public class ArrayList<E> extends AbstractList<E>
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
- rangeCheck(index);
+ if (index >= size)
+ throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
- return elementData(index);
+ return (E) elementData[index];
}
/**
@@ -394,9 +423,10 @@ public class ArrayList<E> extends AbstractList<E>
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
- rangeCheck(index);
+ if (index >= size)
+ throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
- E oldValue = elementData(index);
+ E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
@@ -423,7 +453,8 @@ public class ArrayList<E> extends AbstractList<E>
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
- rangeCheckForAdd(index);
+ if (index > size || index < 0)
+ throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
@@ -442,16 +473,17 @@ public class ArrayList<E> extends AbstractList<E>
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
- rangeCheck(index);
+ if (index >= size)
+ throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
modCount++;
- E oldValue = elementData(index);
+ E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
- elementData[--size] = null; // Let gc do its work
+ elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
@@ -496,7 +528,7 @@ public class ArrayList<E> extends AbstractList<E>
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
- elementData[--size] = null; // Let gc do its work
+ elementData[--size] = null; // clear to let GC do its work
}
/**
@@ -506,7 +538,7 @@ public class ArrayList<E> extends AbstractList<E>
public void clear() {
modCount++;
- // Let gc do its work
+ // clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
@@ -551,7 +583,8 @@ public class ArrayList<E> extends AbstractList<E>
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {
- rangeCheckForAdd(index);
+ if (index > size || index < 0)
+ throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
Object[] a = c.toArray();
int numNew = a.length;
@@ -582,34 +615,24 @@ public class ArrayList<E> extends AbstractList<E>
* toIndex < fromIndex})
*/
protected void removeRange(int fromIndex, int toIndex) {
+ // Android-changed : Throw an IOOBE if toIndex < fromIndex as documented.
+ // All the other cases (negative indices, or indices greater than the size
+ // will be thrown by System#arrayCopy.
+ if (toIndex < fromIndex) {
+ throw new IndexOutOfBoundsException("toIndex < fromIndex");
+ }
+
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
- // Let gc do its work
+ // clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
- while (size != newSize)
- elementData[--size] = null;
- }
-
- /**
- * Checks if the given index is in range. If not, throws an appropriate
- * runtime exception. This method does *not* check if the index is
- * negative: It is always used immediately prior to an array access,
- * which throws an ArrayIndexOutOfBoundsException if index is negative.
- */
- private void rangeCheck(int index) {
- if (index >= size)
- throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
+ for (int i = newSize; i < size; i++) {
+ elementData[i] = null;
}
-
- /**
- * A version of rangeCheck used by add and addAll.
- */
- private void rangeCheckForAdd(int index) {
- if (index > size || index < 0)
- throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
+ size = newSize;
}
/**
@@ -678,6 +701,7 @@ public class ArrayList<E> extends AbstractList<E>
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;
@@ -702,17 +726,17 @@ public class ArrayList<E> extends AbstractList<E>
int expectedModCount = modCount;
s.defaultWriteObject();
- // Write out array length
- s.writeInt(elementData.length);
+ // Write out size as capacity for behavioural compatibility with clone()
+ s.writeInt(size);
// Write out all elements in the proper order.
- for (int i=0; i<size; i++)
+ for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
+ }
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
-
}
/**
@@ -721,17 +745,25 @@ public class ArrayList<E> extends AbstractList<E>
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
+ elementData = EMPTY_ELEMENTDATA;
+
// Read in size, and any hidden stuff
s.defaultReadObject();
- // Read in array length and allocate array
- int arrayLength = s.readInt();
- Object[] a = elementData = new Object[arrayLength];
+ // Read in capacity
+ s.readInt(); // ignored
+ if (size > 0) {
+ // be like clone(), allocate array based upon size not capacity
+ ensureCapacityInternal(size);
+
+ Object[] a = elementData;
// Read in all elements in the proper order.
- for (int i=0; i<size; i++)
+ for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
+ }
+ }
/**
* Returns a list iterator over the elements in this list (in proper
@@ -778,19 +810,27 @@ public class ArrayList<E> extends AbstractList<E>
* An optimized version of AbstractList.Itr
*/
private class Itr implements Iterator<E> {
+ // The "limit" of this iterator. This is the size of the list at the time the
+ // iterator was created. Adding & removing elements will invalidate the iteration
+ // anyway (and cause next() to throw) so saving this value will guarantee that the
+ // value of hasNext() remains stable and won't flap between true and false when elements
+ // are added and removed from the list.
+ protected int limit = ArrayList.this.size;
+
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
public boolean hasNext() {
- return cursor != size;
+ return cursor < limit;
}
@SuppressWarnings("unchecked")
public E next() {
- checkForComodification();
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
int i = cursor;
- if (i >= size)
+ if (i >= limit)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
@@ -802,19 +842,40 @@ public class ArrayList<E> extends AbstractList<E>
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
- checkForComodification();
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
+ limit--;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
- final void checkForComodification() {
+ @Override
+ @SuppressWarnings("unchecked")
+ public void forEachRemaining(Consumer<? super E> consumer) {
+ Objects.requireNonNull(consumer);
+ 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++]);
+ }
+ // update once at end of iteration to reduce heap write traffic
+ cursor = i;
+ lastRet = i - 1;
+
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
@@ -843,7 +904,8 @@ public class ArrayList<E> extends AbstractList<E>
@SuppressWarnings("unchecked")
public E previous() {
- checkForComodification();
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
@@ -857,7 +919,8 @@ public class ArrayList<E> extends AbstractList<E>
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
- checkForComodification();
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
try {
ArrayList.this.set(lastRet, e);
@@ -867,7 +930,8 @@ public class ArrayList<E> extends AbstractList<E>
}
public void add(E e) {
- checkForComodification();
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
try {
int i = cursor;
@@ -875,6 +939,7 @@ public class ArrayList<E> extends AbstractList<E>
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
+ limit++;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
@@ -941,35 +1006,44 @@ public class ArrayList<E> extends AbstractList<E>
}
public E set(int index, E e) {
- rangeCheck(index);
- checkForComodification();
- E oldValue = ArrayList.this.elementData(offset + index);
+ if (index < 0 || index >= this.size)
+ throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
+ if (ArrayList.this.modCount != this.modCount)
+ throw new ConcurrentModificationException();
+ E oldValue = (E) ArrayList.this.elementData[offset + index];
ArrayList.this.elementData[offset + index] = e;
return oldValue;
}
public E get(int index) {
- rangeCheck(index);
- checkForComodification();
- return ArrayList.this.elementData(offset + index);
+ if (index < 0 || index >= this.size)
+ throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
+ if (ArrayList.this.modCount != this.modCount)
+ throw new ConcurrentModificationException();
+ return (E) ArrayList.this.elementData[offset + index];
}
public int size() {
- checkForComodification();
+ if (ArrayList.this.modCount != this.modCount)
+ throw new ConcurrentModificationException();
return this.size;
}
public void add(int index, E e) {
- rangeCheckForAdd(index);
- checkForComodification();
+ if (index < 0 || index > this.size)
+ throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
+ if (ArrayList.this.modCount != this.modCount)
+ throw new ConcurrentModificationException();
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
}
public E remove(int index) {
- rangeCheck(index);
- checkForComodification();
+ if (index < 0 || index >= this.size)
+ throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
+ if (ArrayList.this.modCount != this.modCount)
+ throw new ConcurrentModificationException();
E result = parent.remove(parentOffset + index);
this.modCount = parent.modCount;
this.size--;
@@ -977,7 +1051,8 @@ public class ArrayList<E> extends AbstractList<E>
}
protected void removeRange(int fromIndex, int toIndex) {
- checkForComodification();
+ if (ArrayList.this.modCount != this.modCount)
+ throw new ConcurrentModificationException();
parent.removeRange(parentOffset + fromIndex,
parentOffset + toIndex);
this.modCount = parent.modCount;
@@ -989,12 +1064,14 @@ public class ArrayList<E> extends AbstractList<E>
}
public boolean addAll(int index, Collection<? extends E> c) {
- rangeCheckForAdd(index);
+ if (index < 0 || index > this.size)
+ throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
int cSize = c.size();
if (cSize==0)
return false;
- checkForComodification();
+ if (ArrayList.this.modCount != this.modCount)
+ throw new ConcurrentModificationException();
parent.addAll(parentOffset + index, c);
this.modCount = parent.modCount;
this.size += cSize;
@@ -1006,8 +1083,10 @@ public class ArrayList<E> extends AbstractList<E>
}
public ListIterator<E> listIterator(final int index) {
- checkForComodification();
- rangeCheckForAdd(index);
+ if (ArrayList.this.modCount != this.modCount)
+ throw new ConcurrentModificationException();
+ if (index < 0 || index > this.size)
+ throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
final int offset = this.offset;
return new ListIterator<E>() {
@@ -1021,7 +1100,8 @@ public class ArrayList<E> extends AbstractList<E>
@SuppressWarnings("unchecked")
public E next() {
- checkForComodification();
+ if (expectedModCount != ArrayList.this.modCount)
+ throw new ConcurrentModificationException();
int i = cursor;
if (i >= SubList.this.size)
throw new NoSuchElementException();
@@ -1038,7 +1118,8 @@ public class ArrayList<E> extends AbstractList<E>
@SuppressWarnings("unchecked")
public E previous() {
- checkForComodification();
+ if (expectedModCount != ArrayList.this.modCount)
+ throw new ConcurrentModificationException();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
@@ -1049,6 +1130,27 @@ public class ArrayList<E> extends AbstractList<E>
return (E) elementData[offset + (lastRet = i)];
}
+ @SuppressWarnings("unchecked")
+ public void forEachRemaining(Consumer<? super E> consumer) {
+ Objects.requireNonNull(consumer);
+ final int size = SubList.this.size;
+ int i = cursor;
+ if (i >= size) {
+ return;
+ }
+ final Object[] elementData = ArrayList.this.elementData;
+ if (offset + i >= elementData.length) {
+ throw new ConcurrentModificationException();
+ }
+ while (i != size && modCount == expectedModCount) {
+ consumer.accept((E) elementData[offset + (i++)]);
+ }
+ // update once at end of iteration to reduce heap write traffic
+ lastRet = cursor = i;
+ if (expectedModCount != ArrayList.this.modCount)
+ throw new ConcurrentModificationException();
+ }
+
public int nextIndex() {
return cursor;
}
@@ -1060,7 +1162,8 @@ public class ArrayList<E> extends AbstractList<E>
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
- checkForComodification();
+ if (expectedModCount != ArrayList.this.modCount)
+ throw new ConcurrentModificationException();
try {
SubList.this.remove(lastRet);
@@ -1075,7 +1178,8 @@ public class ArrayList<E> extends AbstractList<E>
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
- checkForComodification();
+ if (expectedModCount != ArrayList.this.modCount)
+ throw new ConcurrentModificationException();
try {
ArrayList.this.set(offset + lastRet, e);
@@ -1085,7 +1189,8 @@ public class ArrayList<E> extends AbstractList<E>
}
public void add(E e) {
- checkForComodification();
+ if (expectedModCount != ArrayList.this.modCount)
+ throw new ConcurrentModificationException();
try {
int i = cursor;
@@ -1097,11 +1202,6 @@ public class ArrayList<E> extends AbstractList<E>
throw new ConcurrentModificationException();
}
}
-
- final void checkForComodification() {
- if (expectedModCount != ArrayList.this.modCount)
- throw new ConcurrentModificationException();
- }
};
}
@@ -1110,23 +1210,238 @@ public class ArrayList<E> extends AbstractList<E>
return new SubList(this, offset, fromIndex, toIndex);
}
- private void rangeCheck(int index) {
- if (index < 0 || index >= this.size)
- throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
+ private String outOfBoundsMsg(int index) {
+ return "Index: "+index+", Size: "+this.size;
}
- private void rangeCheckForAdd(int index) {
- if (index < 0 || index > this.size)
- throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
+ public Spliterator<E> spliterator() {
+ if (modCount != ArrayList.this.modCount)
+ throw new ConcurrentModificationException();
+ return new ArrayListSpliterator<E>(ArrayList.this, offset,
+ offset + this.size, this.modCount);
+ }
}
- private String outOfBoundsMsg(int index) {
- return "Index: "+index+", Size: "+this.size;
+ @Override
+ public void forEach(Consumer<? super E> action) {
+ Objects.requireNonNull(action);
+ final int expectedModCount = modCount;
+ @SuppressWarnings("unchecked")
+ final E[] elementData = (E[]) this.elementData;
+ final int size = this.size;
+ for (int i=0; modCount == expectedModCount && i < size; i++) {
+ action.accept(elementData[i]);
+ }
+ // Note
+ // Iterator will not throw a CME if we add something while iterating over the *last* element
+ // forEach will throw a CME in this case.
+ if (modCount != expectedModCount) {
+ throw new ConcurrentModificationException();
+ }
}
- private void checkForComodification() {
- if (ArrayList.this.modCount != this.modCount)
+ /**
+ * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
+ * and <em>fail-fast</em> {@link Spliterator} over the elements in this
+ * list.
+ *
+ * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
+ * {@link Spliterator#SUBSIZED}, and {@link Spliterator#ORDERED}.
+ * Overriding implementations should document the reporting of additional
+ * characteristic values.
+ *
+ * @return a {@code Spliterator} over the elements in this list
+ * @since 1.8
+ */
+ @Override
+ public Spliterator<E> spliterator() {
+ return new ArrayListSpliterator<>(this, 0, -1, 0);
+ }
+
+ /** Index-based split-by-two, lazily initialized Spliterator */
+ static final class ArrayListSpliterator<E> implements Spliterator<E> {
+
+ /*
+ * If ArrayLists were immutable, or structurally immutable (no
+ * adds, removes, etc), we could implement their spliterators
+ * with Arrays.spliterator. Instead we detect as much
+ * interference during traversal as practical without
+ * sacrificing much performance. We rely primarily on
+ * modCounts. These are not guaranteed to detect concurrency
+ * violations, and are sometimes overly conservative about
+ * within-thread interference, but detect enough problems to
+ * be worthwhile in practice. To carry this out, we (1) lazily
+ * initialize fence and expectedModCount until the latest
+ * point that we need to commit to the state we are checking
+ * against; thus improving precision. (This doesn't apply to
+ * SubLists, that create spliterators with current non-lazy
+ * values). (2) We perform only a single
+ * ConcurrentModificationException check at the end of forEach
+ * (the most performance-sensitive method). When using forEach
+ * (as opposed to iterators), we can normally only detect
+ * interference after actions, not before. Further
+ * CME-triggering checks apply to all other possible
+ * violations of assumptions for example null or too-small
+ * elementData array given its size(), that could only have
+ * occurred due to interference. This allows the inner loop
+ * of forEach to run without any further checks, and
+ * simplifies lambda-resolution. While this does entail a
+ * number of checks, note that in the common case of
+ * list.stream().forEach(a), no checks or other computation
+ * occur anywhere other than inside forEach itself. The other
+ * less-often-used methods cannot take advantage of most of
+ * these streamlinings.
+ */
+
+ private final ArrayList<E> list;
+ private int index; // current index, modified on advance/split
+ 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 */
+ ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
+ int expectedModCount) {
+ this.list = list; // OK if null unless traversed
+ this.index = origin;
+ this.fence = fence;
+ this.expectedModCount = expectedModCount;
+ }
+
+ private int getFence() { // initialize fence to size on first use
+ int hi; // (a specialized variant appears in method forEach)
+ ArrayList<E> lst;
+ if ((hi = fence) < 0) {
+ if ((lst = list) == null)
+ hi = fence = 0;
+ else {
+ expectedModCount = lst.modCount;
+ hi = fence = lst.size;
+ }
+ }
+ return hi;
+ }
+
+ public ArrayListSpliterator<E> trySplit() {
+ int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
+ return (lo >= mid) ? null : // divide range in half unless too small
+ new ArrayListSpliterator<E>(list, lo, index = mid,
+ expectedModCount);
+ }
+
+ public boolean tryAdvance(Consumer<? super E> action) {
+ if (action == null)
+ throw new NullPointerException();
+ int hi = getFence(), i = index;
+ if (i < hi) {
+ index = i + 1;
+ @SuppressWarnings("unchecked") E e = (E)list.elementData[i];
+ action.accept(e);
+ if (list.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return true;
+ }
+ return false;
+ }
+
+ public void forEachRemaining(Consumer<? super E> action) {
+ int i, hi, mc; // hoist accesses and checks from loop
+ ArrayList<E> lst; Object[] a;
+ if (action == null)
+ throw new NullPointerException();
+ if ((lst = list) != null && (a = lst.elementData) != null) {
+ if ((hi = fence) < 0) {
+ mc = lst.modCount;
+ hi = lst.size;
+ }
+ else
+ mc = expectedModCount;
+ if ((i = index) >= 0 && (index = hi) <= a.length) {
+ for (; i < hi; ++i) {
+ @SuppressWarnings("unchecked") E e = (E) a[i];
+ action.accept(e);
+ }
+ if (lst.modCount == mc)
+ return;
+ }
+ }
+ throw new ConcurrentModificationException();
+ }
+
+ public long estimateSize() {
+ return (long) (getFence() - index);
+ }
+
+ public int characteristics() {
+ return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
+ }
+ }
+
+ @Override
+ public boolean removeIf(Predicate<? super E> filter) {
+ Objects.requireNonNull(filter);
+ // figure out which elements are to be removed
+ // any exception thrown from the filter predicate at this stage
+ // will leave the collection unmodified
+ int removeCount = 0;
+ final BitSet removeSet = new BitSet(size);
+ final int expectedModCount = modCount;
+ final int size = this.size;
+ for (int i=0; modCount == expectedModCount && i < size; i++) {
+ @SuppressWarnings("unchecked")
+ final E element = (E) elementData[i];
+ if (filter.test(element)) {
+ removeSet.set(i);
+ removeCount++;
+ }
+ }
+ if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
+
+ // shift surviving elements left over the spaces left by removed elements
+ final boolean anyToRemove = removeCount > 0;
+ if (anyToRemove) {
+ final int newSize = size - removeCount;
+ for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
+ i = removeSet.nextClearBit(i);
+ elementData[j] = elementData[i];
+ }
+ for (int k=newSize; k < size; k++) {
+ elementData[k] = null; // Let gc do its work
+ }
+ this.size = newSize;
+ if (modCount != expectedModCount) {
+ throw new ConcurrentModificationException();
+ }
+ modCount++;
+ }
+
+ return anyToRemove;
+ }
+
+ @Override
+ @SuppressWarnings("unchecked")
+ public void replaceAll(UnaryOperator<E> operator) {
+ Objects.requireNonNull(operator);
+ final int expectedModCount = modCount;
+ final int size = this.size;
+ for (int i=0; modCount == expectedModCount && i < size; i++) {
+ elementData[i] = operator.apply((E) elementData[i]);
+ }
+ if (modCount != expectedModCount) {
+ throw new ConcurrentModificationException();
+ }
+ modCount++;
+ }
+
+ @Override
+ @SuppressWarnings("unchecked")
+ public void sort(Comparator<? super E> c) {
+ final int expectedModCount = modCount;
+ Arrays.sort((E[]) elementData, 0, size, c);
+ if (modCount != expectedModCount) {
+ throw new ConcurrentModificationException();
+ }
+ modCount++;
}
}
Raw
openjdk8-android-ArrayList.java.diff
diff --git a/var/folders/tw/sdhbgsb51lvb38tjhcd3_25w0000gn/T/dyQzrKtA4E.java b/var/folders/tw/sdhbgsb51lvb38tjhcd3_25w0000gn/T/HSyD_0pwnD.java
index dae280d..77aa035 100644
--- a/var/folders/tw/sdhbgsb51lvb38tjhcd3_25w0000gn/T/dyQzrKtA4E.java
+++ b/var/folders/tw/sdhbgsb51lvb38tjhcd3_25w0000gn/T/HSyD_0pwnD.java
@@ -1,4 +1,5 @@
/*
+ * Copyright (C) 2014 The Android Open Source Project
* Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
@@ -123,8 +124,10 @@ public class ArrayList<E> extends AbstractList<E>
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
* DEFAULT_CAPACITY when the first element is added.
+ *
+ * Package private to allow access from java.util.Collections.
*/
- transient Object[] elementData; // non-private to simplify nested class access
+ transient Object[] elementData;
/**
* The size of the ArrayList (the number of elements it contains).
@@ -396,13 +399,6 @@ public class ArrayList<E> extends AbstractList<E>
return a;
}
- // Positional Access Operations
-
- @SuppressWarnings("unchecked")
- E elementData(int index) {
- return (E) elementData[index];
- }
-
/**
* Returns the element at the specified position in this list.
*
@@ -411,9 +407,10 @@ public class ArrayList<E> extends AbstractList<E>
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
- rangeCheck(index);
+ if (index >= size)
+ throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
- return elementData(index);
+ return (E) elementData[index];
}
/**
@@ -426,9 +423,10 @@ public class ArrayList<E> extends AbstractList<E>
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
- rangeCheck(index);
+ if (index >= size)
+ throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
- E oldValue = elementData(index);
+ E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
@@ -455,7 +453,8 @@ public class ArrayList<E> extends AbstractList<E>
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
- rangeCheckForAdd(index);
+ if (index > size || index < 0)
+ throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
@@ -474,10 +473,11 @@ public class ArrayList<E> extends AbstractList<E>
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
- rangeCheck(index);
+ if (index >= size)
+ throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
modCount++;
- E oldValue = elementData(index);
+ E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0)
@@ -583,7 +583,8 @@ public class ArrayList<E> extends AbstractList<E>
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {
- rangeCheckForAdd(index);
+ if (index > size || index < 0)
+ throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
Object[] a = c.toArray();
int numNew = a.length;
@@ -614,6 +615,13 @@ public class ArrayList<E> extends AbstractList<E>
* toIndex < fromIndex})
*/
protected void removeRange(int fromIndex, int toIndex) {
+ // Android-changed : Throw an IOOBE if toIndex < fromIndex as documented.
+ // All the other cases (negative indices, or indices greater than the size
+ // will be thrown by System#arrayCopy.
+ if (toIndex < fromIndex) {
+ throw new IndexOutOfBoundsException("toIndex < fromIndex");
+ }
+
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
@@ -628,25 +636,6 @@ public class ArrayList<E> extends AbstractList<E>
}
/**
- * Checks if the given index is in range. If not, throws an appropriate
- * runtime exception. This method does *not* check if the index is
- * negative: It is always used immediately prior to an array access,
- * which throws an ArrayIndexOutOfBoundsException if index is negative.
- */
- private void rangeCheck(int index) {
- if (index >= size)
- throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
- }
-
- /**
- * A version of rangeCheck used by add and addAll.
- */
- private void rangeCheckForAdd(int index) {
- if (index > size || index < 0)
- throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
- }
-
- /**
* Constructs an IndexOutOfBoundsException detail message.
* Of the many possible refactorings of the error handling code,
* this "outlining" performs best with both server and client VMs.
@@ -671,7 +660,6 @@ public class ArrayList<E> extends AbstractList<E>
* @see Collection#contains(Object)
*/
public boolean removeAll(Collection<?> c) {
- Objects.requireNonNull(c);
return batchRemove(c, false);
}
@@ -692,7 +680,6 @@ public class ArrayList<E> extends AbstractList<E>
* @see Collection#contains(Object)
*/
public boolean retainAll(Collection<?> c) {
- Objects.requireNonNull(c);
return batchRemove(c, true);
}
@@ -823,19 +810,27 @@ public class ArrayList<E> extends AbstractList<E>
* An optimized version of AbstractList.Itr
*/
private class Itr implements Iterator<E> {
+ // The "limit" of this iterator. This is the size of the list at the time the
+ // iterator was created. Adding & removing elements will invalidate the iteration
+ // anyway (and cause next() to throw) so saving this value will guarantee that the
+ // value of hasNext() remains stable and won't flap between true and false when elements
+ // are added and removed from the list.
+ protected int limit = ArrayList.this.size;
+
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
public boolean hasNext() {
- return cursor != size;
+ return cursor < limit;
}
@SuppressWarnings("unchecked")
public E next() {
- checkForComodification();
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
int i = cursor;
- if (i >= size)
+ if (i >= limit)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
@@ -847,13 +842,15 @@ public class ArrayList<E> extends AbstractList<E>
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
- checkForComodification();
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
+ limit--;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
@@ -878,10 +875,7 @@ public class ArrayList<E> extends AbstractList<E>
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
- checkForComodification();
- }
- final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
@@ -910,7 +904,8 @@ public class ArrayList<E> extends AbstractList<E>
@SuppressWarnings("unchecked")
public E previous() {
- checkForComodification();
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
@@ -924,7 +919,8 @@ public class ArrayList<E> extends AbstractList<E>
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
- checkForComodification();
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
try {
ArrayList.this.set(lastRet, e);
@@ -934,7 +930,8 @@ public class ArrayList<E> extends AbstractList<E>
}
public void add(E e) {
- checkForComodification();
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
try {
int i = cursor;
@@ -942,6 +939,7 @@ public class ArrayList<E> extends AbstractList<E>
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
+ limit++;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
@@ -1008,35 +1006,44 @@ public class ArrayList<E> extends AbstractList<E>
}
public E set(int index, E e) {
- rangeCheck(index);
- checkForComodification();
- E oldValue = ArrayList.this.elementData(offset + index);
+ if (index < 0 || index >= this.size)
+ throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
+ if (ArrayList.this.modCount != this.modCount)
+ throw new ConcurrentModificationException();
+ E oldValue = (E) ArrayList.this.elementData[offset + index];
ArrayList.this.elementData[offset + index] = e;
return oldValue;
}
public E get(int index) {
- rangeCheck(index);
- checkForComodification();
- return ArrayList.this.elementData(offset + index);
+ if (index < 0 || index >= this.size)
+ throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
+ if (ArrayList.this.modCount != this.modCount)
+ throw new ConcurrentModificationException();
+ return (E) ArrayList.this.elementData[offset + index];
}
public int size() {
- checkForComodification();
+ if (ArrayList.this.modCount != this.modCount)
+ throw new ConcurrentModificationException();
return this.size;
}
public void add(int index, E e) {
- rangeCheckForAdd(index);
- checkForComodification();
+ if (index < 0 || index > this.size)
+ throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
+ if (ArrayList.this.modCount != this.modCount)
+ throw new ConcurrentModificationException();
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
}
public E remove(int index) {
- rangeCheck(index);
- checkForComodification();
+ if (index < 0 || index >= this.size)
+ throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
+ if (ArrayList.this.modCount != this.modCount)
+ throw new ConcurrentModificationException();
E result = parent.remove(parentOffset + index);
this.modCount = parent.modCount;
this.size--;
@@ -1044,7 +1051,8 @@ public class ArrayList<E> extends AbstractList<E>
}
protected void removeRange(int fromIndex, int toIndex) {
- checkForComodification();
+ if (ArrayList.this.modCount != this.modCount)
+ throw new ConcurrentModificationException();
parent.removeRange(parentOffset + fromIndex,
parentOffset + toIndex);
this.modCount = parent.modCount;
@@ -1056,12 +1064,14 @@ public class ArrayList<E> extends AbstractList<E>
}
public boolean addAll(int index, Collection<? extends E> c) {
- rangeCheckForAdd(index);
+ if (index < 0 || index > this.size)
+ throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
int cSize = c.size();
if (cSize==0)
return false;
- checkForComodification();
+ if (ArrayList.this.modCount != this.modCount)
+ throw new ConcurrentModificationException();
parent.addAll(parentOffset + index, c);
this.modCount = parent.modCount;
this.size += cSize;
@@ -1073,8 +1083,10 @@ public class ArrayList<E> extends AbstractList<E>
}
public ListIterator<E> listIterator(final int index) {
- checkForComodification();
- rangeCheckForAdd(index);
+ if (ArrayList.this.modCount != this.modCount)
+ throw new ConcurrentModificationException();
+ if (index < 0 || index > this.size)
+ throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
final int offset = this.offset;
return new ListIterator<E>() {
@@ -1088,7 +1100,8 @@ public class ArrayList<E> extends AbstractList<E>
@SuppressWarnings("unchecked")
public E next() {
- checkForComodification();
+ if (expectedModCount != ArrayList.this.modCount)
+ throw new ConcurrentModificationException();
int i = cursor;
if (i >= SubList.this.size)
throw new NoSuchElementException();
@@ -1105,7 +1118,8 @@ public class ArrayList<E> extends AbstractList<E>
@SuppressWarnings("unchecked")
public E previous() {
- checkForComodification();
+ if (expectedModCount != ArrayList.this.modCount)
+ throw new ConcurrentModificationException();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
@@ -1133,7 +1147,8 @@ public class ArrayList<E> extends AbstractList<E>
}
// update once at end of iteration to reduce heap write traffic
lastRet = cursor = i;
- checkForComodification();
+ if (expectedModCount != ArrayList.this.modCount)
+ throw new ConcurrentModificationException();
}
public int nextIndex() {
@@ -1147,7 +1162,8 @@ public class ArrayList<E> extends AbstractList<E>
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
- checkForComodification();
+ if (expectedModCount != ArrayList.this.modCount)
+ throw new ConcurrentModificationException();
try {
SubList.this.remove(lastRet);
@@ -1162,7 +1178,8 @@ public class ArrayList<E> extends AbstractList<E>
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
- checkForComodification();
+ if (expectedModCount != ArrayList.this.modCount)
+ throw new ConcurrentModificationException();
try {
ArrayList.this.set(offset + lastRet, e);
@@ -1172,7 +1189,8 @@ public class ArrayList<E> extends AbstractList<E>
}
public void add(E e) {
- checkForComodification();
+ if (expectedModCount != ArrayList.this.modCount)
+ throw new ConcurrentModificationException();
try {
int i = cursor;
@@ -1184,11 +1202,6 @@ public class ArrayList<E> extends AbstractList<E>
throw new ConcurrentModificationException();
}
}
-
- final void checkForComodification() {
- if (expectedModCount != ArrayList.this.modCount)
- throw new ConcurrentModificationException();
- }
};
}
@@ -1197,27 +1210,13 @@ public class ArrayList<E> extends AbstractList<E>
return new SubList(this, offset, fromIndex, toIndex);
}
- private void rangeCheck(int index) {
- if (index < 0 || index >= this.size)
- throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
- }
-
- private void rangeCheckForAdd(int index) {
- if (index < 0 || index > this.size)
- throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
- }
-
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+this.size;
}
- private void checkForComodification() {
- if (ArrayList.this.modCount != this.modCount)
- throw new ConcurrentModificationException();
- }
-
public Spliterator<E> spliterator() {
- checkForComodification();
+ if (modCount != ArrayList.this.modCount)
+ throw new ConcurrentModificationException();
return new ArrayListSpliterator<E>(ArrayList.this, offset,
offset + this.size, this.modCount);
}
@@ -1233,6 +1232,9 @@ public class ArrayList<E> extends AbstractList<E>
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
+ // Note
+ // Iterator will not throw a CME if we add something while iterating over the *last* element
+ // forEach will throw a CME in this case.
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment