--- jsr166/src/main/java/util/ArrayList.java 2016/11/04 03:09:27 1.37
+++ jsr166/src/main/java/util/ArrayList.java 2019/08/10 16:48:05 1.68
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 1997, 2016, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1997, 2019, 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
@@ -28,6 +28,8 @@ package java.util;
import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
+// OPENJDK import jdk.internal.access.SharedSecrets;
+import jdk.internal.util.ArraysSupport;
/**
* Resizable-array implementation of the {@code List} interface. Implements
@@ -91,7 +93,7 @@ import java.util.function.UnaryOperator;
* should be used only to detect bugs.
*
*
This class is a member of the
- *
+ *
* Java Collections Framework.
*
* @param the type of elements in this list
@@ -218,14 +220,6 @@ public class ArrayList extends Abstra
}
/**
- * The maximum size of array to allocate (unless necessary).
- * Some VMs reserve some header words in an array.
- * Attempts to allocate larger arrays may result in
- * OutOfMemoryError: Requested array size exceeds VM limit
- */
- private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
-
- /**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
@@ -233,8 +227,15 @@ public class ArrayList extends Abstra
* @throws OutOfMemoryError if minCapacity is less than zero
*/
private Object[] grow(int minCapacity) {
- return elementData = Arrays.copyOf(elementData,
- newCapacity(minCapacity));
+ int oldCapacity = elementData.length;
+ if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
+ int newCapacity = ArraysSupport.newLength(oldCapacity,
+ minCapacity - oldCapacity, /* minimum growth */
+ oldCapacity >> 1 /* preferred growth */);
+ return elementData = Arrays.copyOf(elementData, newCapacity);
+ } else {
+ return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
+ }
}
private Object[] grow() {
@@ -242,39 +243,6 @@ public class ArrayList extends Abstra
}
/**
- * Returns a capacity at least as large as the given minimum capacity.
- * Returns the current capacity increased by 50% if that suffices.
- * Will not return a capacity greater than MAX_ARRAY_SIZE unless
- * the given minimum capacity is greater than MAX_ARRAY_SIZE.
- *
- * @param minCapacity the desired minimum capacity
- * @throws OutOfMemoryError if minCapacity is less than zero
- */
- private int newCapacity(int minCapacity) {
- // overflow-conscious code
- int oldCapacity = elementData.length;
- int newCapacity = oldCapacity + (oldCapacity >> 1);
- if (newCapacity - minCapacity <= 0) {
- if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
- return Math.max(DEFAULT_CAPACITY, minCapacity);
- if (minCapacity < 0) // overflow
- throw new OutOfMemoryError();
- return minCapacity;
- }
- return (newCapacity - MAX_ARRAY_SIZE <= 0)
- ? newCapacity
- : hugeCapacity(minCapacity);
- }
-
- private static int hugeCapacity(int minCapacity) {
- if (minCapacity < 0) // overflow
- throw new OutOfMemoryError();
- return (minCapacity > MAX_ARRAY_SIZE)
- ? Integer.MAX_VALUE
- : MAX_ARRAY_SIZE;
- }
-
- /**
* Returns the number of elements in this list.
*
* @return the number of elements in this list
@@ -313,14 +281,23 @@ public class ArrayList extends Abstra
* or -1 if there is no such index.
*/
public int indexOf(Object o) {
+ return indexOfRange(o, 0, size);
+ }
+
+ int indexOfRange(Object o, int start, int end) {
+ Object[] es = elementData;
if (o == null) {
- for (int i = 0; i < size; i++)
- if (elementData[i]==null)
+ for (int i = start; i < end; i++) {
+ if (es[i] == null) {
return i;
+ }
+ }
} else {
- for (int i = 0; i < size; i++)
- if (o.equals(elementData[i]))
+ for (int i = start; i < end; i++) {
+ if (o.equals(es[i])) {
return i;
+ }
+ }
}
return -1;
}
@@ -333,14 +310,23 @@ public class ArrayList extends Abstra
* or -1 if there is no such index.
*/
public int lastIndexOf(Object o) {
+ return lastIndexOfRange(o, 0, size);
+ }
+
+ int lastIndexOfRange(Object o, int start, int end) {
+ Object[] es = elementData;
if (o == null) {
- for (int i = size-1; i >= 0; i--)
- if (elementData[i]==null)
+ for (int i = end - 1; i >= start; i--) {
+ if (es[i] == null) {
return i;
+ }
+ }
} else {
- for (int i = size-1; i >= 0; i--)
- if (o.equals(elementData[i]))
+ for (int i = end - 1; i >= start; i--) {
+ if (o.equals(es[i])) {
return i;
+ }
+ }
}
return -1;
}
@@ -423,6 +409,11 @@ public class ArrayList extends Abstra
return (E) elementData[index];
}
+ @SuppressWarnings("unchecked")
+ static E elementAt(Object[] es, int index) {
+ return (E) es[index];
+ }
+
/**
* Returns the element at the specified position in this list.
*
@@ -496,6 +487,7 @@ public class ArrayList extends Abstra
s - index);
elementData[index] = element;
size = s + 1;
+ // checkInvariants();
}
/**
@@ -509,20 +501,103 @@ public class ArrayList extends Abstra
*/
public E remove(int index) {
Objects.checkIndex(index, size);
+ final Object[] es = elementData;
- modCount++;
- E oldValue = elementData(index);
-
- int numMoved = size - index - 1;
- if (numMoved > 0)
- System.arraycopy(elementData, index+1, elementData, index,
- numMoved);
- elementData[--size] = null; // clear to let GC do its work
+ @SuppressWarnings("unchecked") E oldValue = (E) es[index];
+ fastRemove(es, index);
+ // checkInvariants();
return oldValue;
}
/**
+ * {@inheritDoc}
+ */
+ public boolean equals(Object o) {
+ if (o == this) {
+ return true;
+ }
+
+ if (!(o instanceof List)) {
+ return false;
+ }
+
+ final int expectedModCount = modCount;
+ // ArrayList can be subclassed and given arbitrary behavior, but we can
+ // still deal with the common case where o is ArrayList precisely
+ boolean equal = (o.getClass() == ArrayList.class)
+ ? equalsArrayList((ArrayList>) o)
+ : equalsRange((List>) o, 0, size);
+
+ checkForComodification(expectedModCount);
+ return equal;
+ }
+
+ boolean equalsRange(List> other, int from, int to) {
+ final Object[] es = elementData;
+ if (to > es.length) {
+ throw new ConcurrentModificationException();
+ }
+ var oit = other.iterator();
+ for (; from < to; from++) {
+ if (!oit.hasNext() || !Objects.equals(es[from], oit.next())) {
+ return false;
+ }
+ }
+ return !oit.hasNext();
+ }
+
+ private boolean equalsArrayList(ArrayList> other) {
+ final int otherModCount = other.modCount;
+ final int s = size;
+ boolean equal;
+ if (equal = (s == other.size)) {
+ final Object[] otherEs = other.elementData;
+ final Object[] es = elementData;
+ if (s > es.length || s > otherEs.length) {
+ throw new ConcurrentModificationException();
+ }
+ for (int i = 0; i < s; i++) {
+ if (!Objects.equals(es[i], otherEs[i])) {
+ equal = false;
+ break;
+ }
+ }
+ }
+ other.checkForComodification(otherModCount);
+ return equal;
+ }
+
+ private void checkForComodification(final int expectedModCount) {
+ if (modCount != expectedModCount) {
+ throw new ConcurrentModificationException();
+ }
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public int hashCode() {
+ int expectedModCount = modCount;
+ int hash = hashCodeRange(0, size);
+ checkForComodification(expectedModCount);
+ return hash;
+ }
+
+ int hashCodeRange(int from, int to) {
+ final Object[] es = elementData;
+ if (to > es.length) {
+ throw new ConcurrentModificationException();
+ }
+ int hashCode = 1;
+ for (int i = from; i < to; i++) {
+ Object e = es[i];
+ hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
+ }
+ return hashCode;
+ }
+
+ /**
* Removes the first occurrence of the specified element from this list,
* if it is present. If the list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
@@ -536,33 +611,35 @@ public class ArrayList extends Abstra
* @return {@code true} if this list contained the specified element
*/
public boolean remove(Object o) {
- if (o == null) {
- for (int index = 0; index < size; index++)
- if (elementData[index] == null) {
- fastRemove(index);
- return true;
- }
- } else {
- for (int index = 0; index < size; index++)
- if (o.equals(elementData[index])) {
- fastRemove(index);
- return true;
- }
+ final Object[] es = elementData;
+ final int size = this.size;
+ int i = 0;
+ found: {
+ if (o == null) {
+ for (; i < size; i++)
+ if (es[i] == null)
+ break found;
+ } else {
+ for (; i < size; i++)
+ if (o.equals(es[i]))
+ break found;
+ }
+ return false;
}
- return false;
+ fastRemove(es, i);
+ return true;
}
- /*
+ /**
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
- private void fastRemove(int index) {
+ private void fastRemove(Object[] es, int i) {
modCount++;
- int numMoved = size - index - 1;
- if (numMoved > 0)
- System.arraycopy(elementData, index+1, elementData, index,
- numMoved);
- elementData[--size] = null; // clear to let GC do its work
+ final int newSize;
+ if ((newSize = size - 1) > i)
+ System.arraycopy(es, i + 1, es, i, newSize - i);
+ es[size = newSize] = null;
}
/**
@@ -571,12 +648,9 @@ public class ArrayList extends Abstra
*/
public void clear() {
modCount++;
-
- // clear to let GC do its work
- for (int i = 0; i < size; i++)
- elementData[i] = null;
-
- size = 0;
+ final Object[] es = elementData;
+ for (int to = size, i = size = 0; i < to; i++)
+ es[i] = null;
}
/**
@@ -604,6 +678,7 @@ public class ArrayList extends Abstra
elementData = grow(s + numNew);
System.arraycopy(a, 0, elementData, s, numNew);
size = s + numNew;
+ // checkInvariants();
return true;
}
@@ -642,6 +717,7 @@ public class ArrayList extends Abstra
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size = s + numNew;
+ // checkInvariants();
return true;
}
@@ -664,16 +740,15 @@ public class ArrayList 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;
+ shiftTailOverGap(elementData, fromIndex, toIndex);
+ // checkInvariants();
+ }
+
+ /** Erases the gap from lo to hi, by sliding down following elements. */
+ private void shiftTailOverGap(Object[] es, int lo, int hi) {
+ System.arraycopy(es, hi, es, lo, size - hi);
+ for (int to = size, i = (size -= hi - lo); i < to; i++)
+ es[i] = null;
}
/**
@@ -716,7 +791,7 @@ public class ArrayList extends Abstra
* @see Collection#contains(Object)
*/
public boolean removeAll(Collection> c) {
- return batchRemove(c, false);
+ return batchRemove(c, false, 0, size);
}
/**
@@ -736,54 +811,57 @@ public class ArrayList extends Abstra
* @see Collection#contains(Object)
*/
public boolean retainAll(Collection> c) {
- return batchRemove(c, true);
+ return batchRemove(c, true, 0, size);
}
- private boolean batchRemove(Collection> c, boolean complement) {
+ boolean batchRemove(Collection> c, boolean complement,
+ final int from, final int end) {
Objects.requireNonNull(c);
final Object[] es = elementData;
- final int size = this.size;
- final boolean modified;
int r;
// Optimize for initial run of survivors
- for (r = 0; r < size; r++)
+ for (r = from;; r++) {
+ if (r == end)
+ return false;
if (c.contains(es[r]) != complement)
break;
- if (modified = (r < size)) {
- int w = r++;
- try {
- for (Object e; r < size; 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, size - r);
- w += size - r;
- throw ex;
- } finally {
- modCount += size - w;
- Arrays.fill(es, (this.size = w), size, null);
- }
}
- return modified;
+ 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 {
+ modCount += end - w;
+ shiftTailOverGap(es, w, end);
+ }
+ // checkInvariants();
+ return true;
}
/**
- * Save the state of the {@code ArrayList} instance to a stream (that
- * is, serialize it).
+ * Saves the state of the {@code ArrayList} instance to a stream
+ * (that is, serializes it).
*
+ * @param s the stream
+ * @throws java.io.IOException if an I/O error occurs
* @serialData The length of the array backing the {@code ArrayList}
* instance is emitted (int), followed by all of its elements
* (each an {@code Object}) in the proper order.
*/
private void writeObject(java.io.ObjectOutputStream s)
- throws java.io.IOException{
+ throws java.io.IOException {
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
- // Write out size as capacity for behavioural compatibility with clone()
+ // Write out size as capacity for behavioral compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
@@ -797,8 +875,12 @@ public class ArrayList extends Abstra
}
/**
- * Reconstitute the {@code ArrayList} instance from a stream (that is,
- * deserialize it).
+ * Reconstitutes the {@code ArrayList} instance from a stream (that is,
+ * deserializes it).
+ * @param s the stream
+ * @throws ClassNotFoundException if the class of a serialized object
+ * could not be found
+ * @throws java.io.IOException if an I/O error occurs
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
@@ -811,6 +893,7 @@ public class ArrayList extends Abstra
if (size > 0) {
// like clone(), allocate array based upon size not capacity
+ jsr166.Platform.checkArray(s, Object[].class, size);
Object[] elements = new Object[size];
// Read in all elements in the proper order.
@@ -910,25 +993,21 @@ public class ArrayList 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() {
@@ -1115,6 +1194,90 @@ public class ArrayList extends Abstra
return true;
}
+ public void replaceAll(UnaryOperator operator) {
+ root.replaceAllRange(operator, offset, offset + size);
+ }
+
+ 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 Object[] toArray() {
+ checkForComodification();
+ return Arrays.copyOfRange(root.elementData, offset, offset + size);
+ }
+
+ @SuppressWarnings("unchecked")
+ public T[] toArray(T[] a) {
+ checkForComodification();
+ if (a.length < size)
+ return (T[]) Arrays.copyOfRange(
+ root.elementData, offset, offset + size, a.getClass());
+ System.arraycopy(root.elementData, offset, a, 0, size);
+ if (a.length > size)
+ a[size] = null;
+ return a;
+ }
+
+ public boolean equals(Object o) {
+ if (o == this) {
+ return true;
+ }
+
+ if (!(o instanceof List)) {
+ return false;
+ }
+
+ boolean equal = root.equalsRange((List>)o, offset, offset + size);
+ checkForComodification();
+ return equal;
+ }
+
+ public int hashCode() {
+ int hash = root.hashCodeRange(offset, offset + size);
+ checkForComodification();
+ return hash;
+ }
+
+ public int indexOf(Object o) {
+ int index = root.indexOfRange(o, offset, offset + size);
+ checkForComodification();
+ return index >= 0 ? index - offset : -1;
+ }
+
+ public int lastIndexOf(Object o) {
+ int index = root.lastIndexOfRange(o, offset, offset + size);
+ checkForComodification();
+ return index >= 0 ? index - offset : -1;
+ }
+
+ public boolean contains(Object o) {
+ return indexOf(o) >= 0;
+ }
+
public Iterator iterator() {
return listIterator();
}
@@ -1162,24 +1325,21 @@ public class ArrayList 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() {
@@ -1269,9 +1429,8 @@ public class ArrayList extends Abstra
public Spliterator spliterator() {
checkForComodification();
- // ArrayListSpliterator is not used because late-binding logic
- // is different here
- return new Spliterator<>() {
+ // ArrayListSpliterator not used here due to late-binding
+ return new Spliterator() {
private int index = offset; // current index, modified on advance/split
private int fence = -1; // -1 until used; then one past last index
private int expectedModCount; // initialized when fence set
@@ -1285,12 +1444,11 @@ public class ArrayList extends Abstra
return hi;
}
- public ArrayListSpliterator trySplit() {
+ public ArrayList.ArrayListSpliterator trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
- // ArrayListSpliterator could be used here as the source is already bound
+ // ArrayListSpliterator can be used here as the source is already bound
return (lo >= mid) ? null : // divide range in half unless too small
- new ArrayListSpliterator<>(root, lo, index = mid,
- expectedModCount);
+ root.new ArrayListSpliterator(lo, index = mid, expectedModCount);
}
public boolean tryAdvance(Consumer super E> action) {
@@ -1332,7 +1490,7 @@ public class ArrayList extends Abstra
}
public long estimateSize() {
- return (long) (getFence() - index);
+ return getFence() - index;
}
public int characteristics() {
@@ -1342,19 +1500,19 @@ public class ArrayList extends Abstra
}
}
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
@Override
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();
- }
}
/**
@@ -1372,11 +1530,11 @@ public class ArrayList extends Abstra
*/
@Override
public Spliterator spliterator() {
- return new ArrayListSpliterator<>(this, 0, -1, 0);
+ return new ArrayListSpliterator(0, -1, 0);
}
/** Index-based split-by-two, lazily initialized Spliterator */
- static final class ArrayListSpliterator implements Spliterator {
+ final class ArrayListSpliterator implements Spliterator {
/*
* If ArrayLists were immutable, or structurally immutable (no
@@ -1410,15 +1568,12 @@ public class ArrayList extends Abstra
* these streamlinings.
*/
- private final ArrayList 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 list, int origin, int fence,
- int expectedModCount) {
- this.list = list; // OK if null unless traversed
+ /** Creates new spliterator covering the given range. */
+ ArrayListSpliterator(int origin, int fence, int expectedModCount) {
this.index = origin;
this.fence = fence;
this.expectedModCount = expectedModCount;
@@ -1426,23 +1581,17 @@ public class ArrayList extends Abstra
private int getFence() { // initialize fence to size on first use
int hi; // (a specialized variant appears in method forEach)
- ArrayList lst;
if ((hi = fence) < 0) {
- if ((lst = list) == null)
- hi = fence = 0;
- else {
- expectedModCount = lst.modCount;
- hi = fence = lst.size;
- }
+ expectedModCount = modCount;
+ hi = fence = size;
}
return hi;
}
- public ArrayListSpliterator trySplit() {
+ public ArrayListSpliterator trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
return (lo >= mid) ? null : // divide range in half unless too small
- new ArrayListSpliterator<>(list, lo, index = mid,
- expectedModCount);
+ new ArrayListSpliterator(lo, index = mid, expectedModCount);
}
public boolean tryAdvance(Consumer super E> action) {
@@ -1451,9 +1600,9 @@ public class ArrayList extends Abstra
int hi = getFence(), i = index;
if (i < hi) {
index = i + 1;
- @SuppressWarnings("unchecked") E e = (E)list.elementData[i];
+ @SuppressWarnings("unchecked") E e = (E)elementData[i];
action.accept(e);
- if (list.modCount != expectedModCount)
+ if (modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
@@ -1462,13 +1611,13 @@ public class ArrayList extends Abstra
public void forEachRemaining(Consumer super E> action) {
int i, hi, mc; // hoist accesses and checks from loop
- ArrayList lst; Object[] a;
+ Object[] a;
if (action == null)
throw new NullPointerException();
- if ((lst = list) != null && (a = lst.elementData) != null) {
+ if ((a = elementData) != null) {
if ((hi = fence) < 0) {
- mc = lst.modCount;
- hi = lst.size;
+ mc = modCount;
+ hi = size;
}
else
mc = expectedModCount;
@@ -1477,7 +1626,7 @@ public class ArrayList extends Abstra
@SuppressWarnings("unchecked") E e = (E) a[i];
action.accept(e);
}
- if (lst.modCount == mc)
+ if (modCount == mc)
return;
}
}
@@ -1485,7 +1634,7 @@ public class ArrayList extends Abstra
}
public long estimateSize() {
- return (long) (getFence() - index);
+ return getFence() - index;
}
public int characteristics() {
@@ -1493,54 +1642,81 @@ public class ArrayList 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;
+ }
+
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
@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;
// Optimize for initial run of survivors
- for (r = 0; r < size; r++)
- if (filter.test((E) es[r]))
- break;
- if (modified = (r < size)) {
- expectedModCount++;
+ 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();
modCount++;
- int w = r++;
- try {
- for (E e; r < size; r++)
- if (!filter.test(e = (E) es[r]))
- es[w++] = e;
- } catch (Throwable ex) {
- // copy remaining elements
- System.arraycopy(es, r, es, w, size - r);
- w += size - r;
- throw ex;
- } finally {
- Arrays.fill(es, (this.size = w), size, null);
- }
+ int w = beg;
+ for (i = beg; i < end; i++)
+ if (isClear(deathRow, i - beg))
+ es[w++] = es[i];
+ shiftTailOverGap(es, w, end);
+ // 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 operator) {
+ replaceAllRange(operator, 0, size);
+ // TODO(8203662): remove increment of modCount from ...
+ modCount++;
+ }
+
+ private void replaceAllRange(UnaryOperator operator, int i, int end) {
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) {
+ final Object[] es = elementData;
+ for (; modCount == expectedModCount && i < end; i++)
+ es[i] = operator.apply(elementAt(es, i));
+ if (modCount != expectedModCount)
throw new ConcurrentModificationException();
- }
- modCount++;
+ // checkInvariants();
}
@Override
@@ -1548,9 +1724,14 @@ public class ArrayList 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;
}
}