# HG changeset patch
# User mduigou
# Date 1394651621 25200
# Node ID 75b332affee0fe5593ebcf4373d7cfa21c855120
# Parent 0de1e14447a8f91ec19a8d25ffba2b5732ebd926
8035584: ArrayList(c) should avoid inflation if c is empty
Reviewed-by: martin
diff -r 0de1e14447a8 -r 75b332affee0 jdk/src/share/classes/java/util/ArrayList.java
--- a/jdk/src/share/classes/java/util/ArrayList.java Fri Apr 25 10:30:35 2014 -0700
+++ b/jdk/src/share/classes/java/util/ArrayList.java Wed Mar 12 12:13:41 2014 -0700
@@ -30,33 +30,33 @@
import java.util.function.UnaryOperator;
/**
- * Resizable-array implementation of the List interface. Implements
+ * Resizable-array implementation of the {@code List} interface. Implements
* all optional list operations, and permits all elements, including
- * null. In addition to implementing the List interface,
+ * {@code null}. In addition to implementing the {@code List} interface,
* this class provides methods to manipulate the size of the array that is
* used internally to store the list. (This class is roughly equivalent to
- * Vector, except that it is unsynchronized.)
+ * {@code Vector}, except that it is unsynchronized.)
*
- * The size, isEmpty, get, set,
- * iterator, and listIterator operations run in constant
- * time. The add operation runs in amortized constant time,
+ *
The {@code size}, {@code isEmpty}, {@code get}, {@code set},
+ * {@code iterator}, and {@code listIterator} operations run in constant
+ * time. The {@code add} operation runs in amortized constant time,
* that is, adding n elements requires O(n) time. All of the other operations
* run in linear time (roughly speaking). The constant factor is low compared
- * to that for the LinkedList implementation.
+ * to that for the {@code LinkedList} implementation.
*
- *
Each ArrayList instance has a capacity. The capacity is
+ *
Each {@code ArrayList} instance has a capacity. The capacity is
* the size of the array used to store the elements in the list. It is always
* at least as large as the list size. As elements are added to an ArrayList,
* its capacity grows automatically. The details of the growth policy are not
* specified beyond the fact that adding an element has constant amortized
* time cost.
*
- *
An application can increase the capacity of an ArrayList instance
- * before adding a large number of elements using the ensureCapacity
+ *
An application can increase the capacity of an {@code ArrayList} instance
+ * before adding a large number of elements using the {@code ensureCapacity}
* operation. This may reduce the amount of incremental reallocation.
*
*
Note that this implementation is not synchronized.
- * If multiple threads access an ArrayList instance concurrently,
+ * If multiple threads access an {@code ArrayList} instance concurrently,
* and at least one of the threads modifies the list structurally, it
* must be synchronized externally. (A structural modification is
* any operation that adds or deletes one or more elements, or explicitly
@@ -94,6 +94,8 @@
*
* Java Collections Framework.
*
+ * @param the type of elements in this list
+ *
* @author Josh Bloch
* @author Neal Gafter
* @see Collection
@@ -119,10 +121,17 @@
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
+ * Shared empty array instance used for default sized empty instances. We
+ * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
+ * first element is added.
+ */
+ private static final Object[] DEFAULTCAPACITY_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. Any
- * empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
- * DEFAULT_CAPACITY when the first element is added.
+ * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
+ * will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access
@@ -141,19 +150,21 @@
* is negative
*/
public ArrayList(int initialCapacity) {
- super();
- if (initialCapacity < 0)
+ if (initialCapacity > 0) {
+ this.elementData = new Object[initialCapacity];
+ } else if (initialCapacity == 0) {
+ this.elementData = EMPTY_ELEMENTDATA;
+ } else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
- this.elementData = new Object[initialCapacity];
+ }
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
- super();
- this.elementData = EMPTY_ELEMENTDATA;
+ this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
@@ -166,37 +177,43 @@
*/
public ArrayList(Collection c) {
elementData = c.toArray();
- size = elementData.length;
- // c.toArray might (incorrectly) not return Object[] (see 6260652)
- if (elementData.getClass() != Object[].class)
- elementData = Arrays.copyOf(elementData, size, Object[].class);
+ if ((size = elementData.length) != 0) {
+ // c.toArray might (incorrectly) not return Object[] (see 6260652)
+ if (elementData.getClass() != Object[].class)
+ elementData = Arrays.copyOf(elementData, size, Object[].class);
+ } else {
+ // replace with empty array.
+ this.elementData = EMPTY_ELEMENTDATA;
+ }
}
/**
- * Trims the capacity of this ArrayList instance to be the
+ * Trims the capacity of this {@code ArrayList} instance to be the
* list's current size. An application can use this operation to minimize
- * the storage of an ArrayList instance.
+ * the storage of an {@code ArrayList} instance.
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
- elementData = Arrays.copyOf(elementData, size);
+ elementData = (size == 0)
+ ? EMPTY_ELEMENTDATA
+ : Arrays.copyOf(elementData, size);
}
}
/**
- * Increases the capacity of this ArrayList instance, if
+ * Increases the capacity of this {@code ArrayList} instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
public void ensureCapacity(int minCapacity) {
- int minExpand = (elementData != EMPTY_ELEMENTDATA)
- // any size if real element table
+ int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
+ // any size if not default element table
? 0
- // larger than default for empty table. It's already supposed to be
- // at default size.
+ // larger than default for default empty table. It's already
+ // supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
@@ -205,7 +222,7 @@
}
private void ensureCapacityInternal(int minCapacity) {
- if (elementData == EMPTY_ELEMENTDATA) {
+ if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
@@ -264,22 +281,22 @@
}
/**
- * Returns true if this list contains no elements.
+ * Returns {@code true} if this list contains no elements.
*
- * @return true if this list contains no elements
+ * @return {@code true} if this list contains no elements
*/
public boolean isEmpty() {
return size == 0;
}
/**
- * Returns true if this list contains the specified element.
- * More formally, returns true if and only if this list contains
- * at least one element e such that
+ * Returns {@code true} if this list contains the specified element.
+ * More formally, returns {@code true} if and only if this list contains
+ * at least one element {@code e} such that
* (o==null ? e==null : o.equals(e)).
*
* @param o element whose presence in this list is to be tested
- * @return true if this list contains the specified element
+ * @return {@code true} if this list contains the specified element
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
@@ -288,7 +305,7 @@
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
- * More formally, returns the lowest index i such that
+ * More formally, returns the lowest index {@code i} such that
* (o==null ? get(i)==null : o.equals(get(i))),
* or -1 if there is no such index.
*/
@@ -308,7 +325,7 @@
/**
* Returns the index of the last occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
- * More formally, returns the highest index i such that
+ * More formally, returns the highest index {@code i} such that
* (o==null ? get(i)==null : o.equals(get(i))),
* or -1 if there is no such index.
*/
@@ -326,10 +343,10 @@
}
/**
- * Returns a shallow copy of this ArrayList instance. (The
+ * Returns a shallow copy of this {@code ArrayList} instance. (The
* elements themselves are not copied.)
*
- * @return a clone of this ArrayList instance
+ * @return a clone of this {@code ArrayList} instance
*/
public Object clone() {
try {
@@ -372,7 +389,7 @@
* If the list fits in the specified array with room to spare
* (i.e., the array has more elements than the list), the element in
* the array immediately following the end of the collection is set to
- * null. (This is useful in determining the length of the
+ * {@code null}. (This is useful in determining the length of the
* list only if the caller knows that the list does not contain
* any null elements.)
*
@@ -437,7 +454,7 @@
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
- * @return true (as specified by {@link Collection#add})
+ * @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
@@ -492,14 +509,14 @@
* 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
- * i such that
+ * {@code i} such that
* (o==null ? get(i)==null : o.equals(get(i)))
- * (if such an element exists). Returns true if this list
+ * (if such an element exists). Returns {@code true} if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
- * @return true if this list contained the specified element
+ * @return {@code true} if this list contained the specified element
*/
public boolean remove(Object o) {
if (o == null) {
@@ -555,7 +572,7 @@
* list is nonempty.)
*
* @param c collection containing elements to be added to this list
- * @return true if this list changed as a result of the call
+ * @return {@code true} if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(Collection c) {
@@ -578,7 +595,7 @@
* @param index index at which to insert the first element from the
* specified collection
* @param c collection containing elements to be added to this list
- * @return true if this list changed as a result of the call
+ * @return {@code true} if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
@@ -736,12 +753,12 @@
}
/**
- * Save the state of the ArrayList instance to a stream (that
+ * Save the state of the {@code ArrayList} instance to a stream (that
* is, serialize it).
*
- * @serialData The length of the array backing the ArrayList
+ * @serialData The length of the array backing the {@code ArrayList}
* instance is emitted (int), followed by all of its elements
- * (each an Object) in the proper order.
+ * (each an {@code Object}) in the proper order.
*/
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
@@ -763,7 +780,7 @@
}
/**
- * Reconstitute the ArrayList instance from a stream (that is,
+ * Reconstitute the {@code ArrayList} instance from a stream (that is,
* deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)