--- jsr166/src/main/java/util/ArrayList.java 2016/11/30 03:31:47 1.45 +++ jsr166/src/main/java/util/ArrayList.java 2018/01/08 21:51:07 1.55 @@ -1,5 +1,5 @@ /* - * Copyright (c) 1997, 2016, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 1997, 2017, 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 @@ -515,15 +516,10 @@ 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; @@ -543,33 +539,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; } /** @@ -578,8 +576,9 @@ public class ArrayList extends Abstra */ public void clear() { modCount++; - Arrays.fill(elementData, 0, size, null); - size = 0; + final Object[] es = elementData; + for (int to = size, i = size = 0; i < to; i++) + es[i] = null; } /** @@ -669,13 +668,17 @@ public class ArrayList extends Abstra outOfBoundsMsg(fromIndex, toIndex)); } modCount++; - final Object[] es = elementData; - final int oldSize = size; - System.arraycopy(es, toIndex, es, fromIndex, oldSize - toIndex); - Arrays.fill(es, size -= (toIndex - fromIndex), oldSize, null); + 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; + } + /** * A version of rangeCheck used by add and addAll. */ @@ -743,49 +746,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; + } + 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 modified; + 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. @@ -799,8 +803,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 { @@ -813,6 +821,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. @@ -1362,6 +1371,9 @@ public class ArrayList extends Abstra } } + /** + * @throws NullPointerException {@inheritDoc} + */ @Override public void forEach(Consumer action) { Objects.requireNonNull(action); @@ -1431,7 +1443,7 @@ public class ArrayList extends Abstra private int fence; // -1 until used; then one past last index private int expectedModCount; // initialized when fence set - /** Create new spliterator covering the given range */ + /** Creates new spliterator covering the given range. */ ArrayListSpliterator(int origin, int fence, int expectedModCount) { this.index = origin; this.fence = fence; @@ -1513,6 +1525,9 @@ 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); @@ -1541,15 +1556,12 @@ public class ArrayList extends Abstra setBit(deathRow, i - beg); if (modCount != expectedModCount) throw new ConcurrentModificationException(); - expectedModCount++; 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 {