ArrayList.ensureCapacity should expand the default capacity empty array

[Alex Foster]

Hi,


I think that ensureCapacity should actually ensure the capacity by expanding 
the default capacity empty array, otherwise you could end up with a situation 
like this:

        List<ArrayList<Object>> ls = getLists();// Large list of ArrayLists
        ls.forEach(l -> l.ensureCapacity(10));
        //later...
        ArrayList<Object> a = ls.get(0);
        if(a.size() < 10) a.add(null); // throws OutOfMemoryError when array is 
allocated

I think it's still OK to not allocate the array directly in the no-arg 
constructor because if users actually care about the capacity they can call the 
constructor with an initialCapacity argument or ensureCapacity, but maybe a 
note should be added that it can be allocated lazily?

Also it's debatable if ensureCapacity should call grow or just resize the array 
to exactly the minCapacity argument, which might save space if the exact size 
needed is known, or maybe to max(minCapacity, DEFAULT_CAPACITY) if elementData 
== DEFAULTCAPACITY_EMPTY_ELEMENTDATA which would use more space but otherwise 
ensureCapacity could cause you to end up with lower than default capacity 
(which might be wanted).

diff --git a/src/java.base/share/classes/java/util/ArrayList.java 
b/src/java.base/share/classes/java/util/ArrayList.java
--- a/src/java.base/share/classes/java/util/ArrayList.java
+++ b/src/java.base/share/classes/java/util/ArrayList.java
@@ -210,11 +210,9 @@
      * @param minCapacity the desired minimum capacity
      */
     public void ensureCapacity(int minCapacity) {
-        if (minCapacity > elementData.length
-            && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
-                 && minCapacity <= DEFAULT_CAPACITY)) {
+        if (minCapacity > elementData.length) {
             modCount++;
-            grow(minCapacity);
+            elementData = Arrays.copyOf(elementData, minCapacity);
         }
     }

I noticed this while writing a similar method for ArrayDeque which could also 
be added to ArrayList:

    /**
     * Attempts to reallocate the backing array so that is has space for as 
close as
     * possible to, but not less than, minSize elements unless it already has 
space
     * for between minSize and maxSize elements. If the size() of this 
ArrayDeque is
     * greater than minSize then size() will be treated as minSize.
     *
     * <p>This method can be used to achieve the same result as {@link 
ArrayList#trimToSize}
     * by calling {@code reallocate(0, 0)} or {@link 
ArrayList#ensureCapacity(n)} by calling
     * {@code reallocate(n, Integer.MAX_VALUE)}.
     *
     * @param minSize the requested minimum capacity
     * @param maxSize the requested maximum capacity
     * @return the new (or unchanged) capacity
     * @throws IllegalArgumentException if minSize > maxSize (size() may be 
greater than maxSize
     * without throwing an exception)
     * @throws OutOfMemoryError if there is not enough memory available to 
allocate
     * the array or the array would be larger than an implementation defined 
limit
     */
    public int reallocate(int minSize, int maxSize){
        if(minSize > maxSize) throw new IllegalArgumentException(minSize + " > 
" + maxSize);
        int c = elements.length - 1, s = size();
        if(c < minSize){
            if(minSize + 1 < 0) throw new OutOfMemoryError();
        } else {
            if(c <= maxSize) return c;
            if(s > minSize){
                if(c == (minSize = s)) return c;
            }
        }
        elements = minSize == 0 ? EMPTY : copyElements(new Object[minSize + 1], 
head, tail);
        head = 0;
        tail = s;
        return minSize;
    }