--- jsr166/src/main/java/util/ArrayList.java 2016/12/05 00:08:01 1.47 +++ jsr166/src/main/java/util/ArrayList.java 2020/07/24 20:57:26 1.71 @@ -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 @@ -107,6 +109,7 @@ import java.util.function.UnaryOperator; public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable { + // OPENJDK @java.io.Serial private static final long serialVersionUID = 8683452581122892189L; /** @@ -175,15 +178,16 @@ public class ArrayList extends Abstra * @throws NullPointerException if the specified collection is null */ public ArrayList(Collection c) { - elementData = c.toArray(); - if ((size = elementData.length) != 0) { - // defend against c.toArray (incorrectly) not returning Object[] - // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652) - if (elementData.getClass() != Object[].class) - elementData = Arrays.copyOf(elementData, size, Object[].class); + Object[] a = c.toArray(); + if ((size = a.length) != 0) { + if (c.getClass() == ArrayList.class) { + elementData = a; + } else { + elementData = Arrays.copyOf(a, size, Object[].class); + } } else { // replace with empty array. - this.elementData = EMPTY_ELEMENTDATA; + elementData = EMPTY_ELEMENTDATA; } } @@ -218,14 +222,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 +229,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 +245,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 +283,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 +312,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; } @@ -515,21 +503,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 @@ -543,33 +613,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; } /** @@ -748,30 +820,31 @@ 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 { - modCount += end - w; - shiftTailOverGap(es, w, end); - } + 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; } /** @@ -784,13 +857,14 @@ public class ArrayList extends Abstra * instance is emitted (int), followed by all of its elements * (each an {@code Object}) in the proper order. */ + // OPENJDK @java.io.Serial private void writeObject(java.io.ObjectOutputStream s) 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. @@ -811,6 +885,7 @@ public class ArrayList extends Abstra * could not be found * @throws java.io.IOException if an I/O error occurs */ + // OPENJDK @java.io.Serial private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { @@ -822,6 +897,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. @@ -1064,7 +1140,7 @@ public class ArrayList extends Abstra this.parent = parent; this.offset = parent.offset + fromIndex; this.size = toIndex - fromIndex; - this.modCount = root.modCount; + this.modCount = parent.modCount; } public E set(int index, E element) { @@ -1122,6 +1198,10 @@ 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); } @@ -1149,6 +1229,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(); } @@ -1160,7 +1293,7 @@ public class ArrayList extends Abstra return new ListIterator() { int cursor = index; int lastRet = -1; - int expectedModCount = root.modCount; + int expectedModCount = SubList.this.modCount; public boolean hasNext() { return cursor != SubList.this.size; @@ -1204,7 +1337,7 @@ public class ArrayList extends Abstra final Object[] es = root.elementData; if (offset + i >= es.length) throw new ConcurrentModificationException(); - for (; i < size && modCount == expectedModCount; i++) + for (; i < size && root.modCount == expectedModCount; i++) action.accept(elementAt(es, offset + i)); // update once at end to reduce heap write traffic cursor = i; @@ -1230,7 +1363,7 @@ public class ArrayList extends Abstra SubList.this.remove(lastRet); cursor = lastRet; lastRet = -1; - expectedModCount = root.modCount; + expectedModCount = SubList.this.modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } @@ -1256,7 +1389,7 @@ public class ArrayList extends Abstra SubList.this.add(i, e); cursor = i + 1; lastRet = -1; - expectedModCount = root.modCount; + expectedModCount = SubList.this.modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } @@ -1371,6 +1504,9 @@ public class ArrayList extends Abstra } } + /** + * @throws NullPointerException {@inheritDoc} + */ @Override public void forEach(Consumer action) { Objects.requireNonNull(action); @@ -1440,7 +1576,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; @@ -1522,6 +1658,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); @@ -1550,7 +1689,6 @@ 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++) @@ -1569,15 +1707,19 @@ public class ArrayList extends Abstra @Override 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 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) throw new ConcurrentModificationException(); - modCount++; // checkInvariants(); }