--- jsr166/src/main/java/util/ArrayList.java 2016/11/13 20:03:11 1.40 +++ jsr166/src/main/java/util/ArrayList.java 2018/05/16 16:18:00 1.60 @@ -1,5 +1,5 @@ /* - * Copyright (c) 1997, 2016, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 1997, 2018, 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,7 @@ package java.util; import java.util.function.Consumer; import java.util.function.Predicate; import java.util.function.UnaryOperator; +import jdk.internal.misc.SharedSecrets; /** * Resizable-array implementation of the {@code List} interface. Implements @@ -91,7 +92,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 @@ -313,14 +314,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 +343,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; } @@ -501,6 +520,7 @@ public class ArrayList extends Abstra s - index); elementData[index] = element; size = s + 1; + // checkInvariants(); } /** @@ -514,20 +534,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 @@ -541,33 +644,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; } /** @@ -576,12 +681,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; } /** @@ -609,6 +711,7 @@ public class ArrayList extends Abstra elementData = grow(s + numNew); System.arraycopy(a, 0, elementData, s, numNew); size = s + numNew; + // checkInvariants(); return true; } @@ -647,6 +750,7 @@ public class ArrayList extends Abstra numMoved); System.arraycopy(a, 0, elementData, index, numNew); size = s + numNew; + // checkInvariants(); return true; } @@ -669,16 +773,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; } /** @@ -748,48 +851,50 @@ public class ArrayList extends Abstra 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); - } + for (r = from;; r++) { + if (r == end) + return false; + if (c.contains(es[r]) != complement) + break; } - 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. @@ -803,8 +908,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 { @@ -817,6 +926,7 @@ public class ArrayList extends Abstra if (size > 0) { // like clone(), allocate array based upon size not capacity + SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size); Object[] elements = new Object[size]; // Read in all elements in the proper order. @@ -916,25 +1026,21 @@ public class ArrayList extends Abstra } @Override - @SuppressWarnings("unchecked") - public void forEachRemaining(Consumer consumer) { - Objects.requireNonNull(consumer); + public void forEachRemaining(Consumer 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() { @@ -1121,9 +1227,14 @@ 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); } @@ -1147,6 +1258,59 @@ public class ArrayList extends Abstra 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(); } @@ -1194,24 +1358,21 @@ public class ArrayList extends Abstra return (E) elementData[offset + (lastRet = i)]; } - @SuppressWarnings("unchecked") - public void forEachRemaining(Consumer consumer) { - Objects.requireNonNull(consumer); + public void forEachRemaining(Consumer 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() { @@ -1301,9 +1462,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 @@ -1317,12 +1477,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 action) { @@ -1364,7 +1523,7 @@ public class ArrayList extends Abstra } public long estimateSize() { - return (long) (getFence() - index); + return getFence() - index; } public int characteristics() { @@ -1374,18 +1533,19 @@ public class ArrayList extends Abstra } } + /** + * @throws NullPointerException {@inheritDoc} + */ @Override public void forEach(Consumer action) { Objects.requireNonNull(action); final int expectedModCount = modCount; final Object[] es = elementData; final int size = this.size; - for (int i = 0; modCount == expectedModCount && i < size; i++) { + for (int i = 0; modCount == expectedModCount && i < size; i++) action.accept(elementAt(es, i)); - } - if (modCount != expectedModCount) { + if (modCount != expectedModCount) throw new ConcurrentModificationException(); - } } /** @@ -1403,11 +1563,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 @@ -1441,15 +1601,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; @@ -1457,23 +1614,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 action) { @@ -1482,9 +1633,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; } @@ -1493,13 +1644,13 @@ public class ArrayList extends Abstra public void forEachRemaining(Consumer 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; @@ -1508,7 +1659,7 @@ public class ArrayList extends Abstra @SuppressWarnings("unchecked") E e = (E) a[i]; action.accept(e); } - if (lst.modCount == mc) + if (modCount == mc) return; } } @@ -1516,7 +1667,7 @@ public class ArrayList extends Abstra } public long estimateSize() { - return (long) (getFence() - index); + return getFence() - index; } public int characteristics() { @@ -1536,27 +1687,29 @@ public class ArrayList extends Abstra return (bits[i >> 6] & (1L << i)) == 0; } + /** + * @throws NullPointerException {@inheritDoc} + */ @Override public boolean removeIf(Predicate filter) { return removeIf(filter, 0, size); } - boolean removeIf(Predicate filter, - final int from, final int end) { + /** + * Removes all elements satisfying the given predicate, from index + * i (inclusive) to index end (exclusive). + */ + boolean removeIf(Predicate filter, int i, final int end) { Objects.requireNonNull(filter); int expectedModCount = modCount; final Object[] es = elementData; - final boolean modified; - int i; // Optimize for initial run of survivors - for (i = from; i < end && !filter.test(elementAt(es, i)); i++) + 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 (modified = (i < end)) { - expectedModCount++; - modCount++; + if (i < end) { final int beg = i; final long[] deathRow = nBits(end - beg); deathRow[0] = 1L; // set bit 0 @@ -1565,32 +1718,36 @@ public class ArrayList extends Abstra setBit(deathRow, i - beg); if (modCount != expectedModCount) throw new ConcurrentModificationException(); + modCount++; 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); + 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 public void replaceAll(UnaryOperator operator) { + replaceAllRange(operator, 0, size); + } + + private void replaceAllRange(UnaryOperator operator, int i, int end) { 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++) { + for (; modCount == expectedModCount && i < end; i++) es[i] = operator.apply(elementAt(es, i)); - } - if (modCount != expectedModCount) { + if (modCount != expectedModCount) throw new ConcurrentModificationException(); - } - modCount++; + // checkInvariants(); } @Override @@ -1598,9 +1755,14 @@ public class ArrayList extends Abstra public void sort(Comparator 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; } }