Can't understand the possibility of overflow when resizing ArrayList in Java

Question

The quoted code snippet from the JDK 7 java.util.ArrayList class confuses me. I can't for the life of me understand how can it possibly result in overflow. The areas which I'm confused in are marked with <--- what do they mean by this?. Can someone please help me out in understanding the circumstances under which this logic might overflow? TIA.

public void ensureCapacity(int minCapacity) {
    if (minCapacity > 0)
        ensureCapacityInternal(minCapacity);
}  

private void ensureCapacityInternal(int minCapacity) {
    modCount++;
    // overflow-conscious code <--- what do they mean by this?
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
    // overflow-conscious code <--- what do they mean by this?
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow <--- what do they mean by this?
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

EDIT: My main concern is: how can hugeCapacity ever receive a negative size?

It's not a "stack overflow" overflow if that is your concern with the comments in the Java code. It is about the managed capacity of the internal array. — Paul Jowett
– Paul Jowett, Commented Dec 19, 2011 at 6:30
@jowierun: You are right, stack overflow is not my concern here. I'm pretty sure the comments speak of datatype overflow/capacity overflow. The new new OutOfMemoryError() in hugeCapacity() method is the one which has got me confused. — sasuke
– sasuke, Commented Dec 19, 2011 at 6:35

Zohaib · Accepted Answer · 2011-12-19 06:27:24Z

2

an overflow results when a calculated value is larger than the number of bytes allowed for its type.

After performing some operations on oldCapacity value is being assigned to newCapacity, if these operationf result into some value that does not fit into int then overflow will occur. I guess thats why this code is commented as overflow consious code.

answered Dec 19, 2011 at 6:27

Zohaib

7,1263 gold badges29 silver badges35 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

sasuke Over a year ago

OK, point taken. But why does hugeCapacity() method have to check for capacity < 0? What are the cases in which hugeCapacity will receive a negative value?

Zohaib Over a year ago

I have not gone through the complete code, sorry for that, but yes minCapacity can be less than zero. For example if some calculations were performed on minCapacity and the result was higher then it can for into minCapacity. So java will drop some of the higher order bits to make it fit into the int. While doing this, the sign bit might get turned on. thus making it a negative value. @sasuke

sasuke Over a year ago

But shouldn't the public method ensureCapacity which checks for size > 0 (as per the code posted in my question) filter out such cases?

Buhake Sindi · Accepted Answer · 2011-12-19 07:02:38Z

1

The OutOfMemoryError() (in ArrayList) is thrown for 2 conditions:

The minCapacity is less that zero. That means that a memory array allocation cannot be created, i.e. elementData array size cannot be less that zero.
The capacity of the array has exceeeded the VM memory heap space. The VM cannot create memory (grow()) to allocate more object in the array.

Hence why hugeCapacity() ensures that memory is allocated safely.

grow() and hugeCapacity() is only used within ensureCapacityInternal(), so one can say that the minCapacity < 0 is unecessary. I believe it's a safety check put in place, just to render the growing of array safe. Any discrepency, rather throw an error.

edited Dec 19, 2011 at 7:02

answered Dec 19, 2011 at 6:41

Buhake Sindi

89.5k30 gold badges176 silver badges234 bronze badges

2 Comments

sasuke Over a year ago

Maybe I was not clear, but given that there already is a check for capacity > 0 in the public ensureCapacity method, how can minCapacity be less than 0?

sasuke Over a year ago

+1, thanks for the reply. I have been trying so hard (playing around with values) to ensure that the control goes in minCapacity < 0 block but can't think of any scenario wherein that can happen. Not sure why the check is in place...

Stephen C · Accepted Answer · 2011-12-19 07:22:35Z

0

I suspect that this code may have at some point been modified to work with arrays where array.length is a long. (Of course, that ain't regular Java ... as we know it.)

answered Dec 19, 2011 at 7:22

Stephen C

723k95 gold badges849 silver badges1.3k bronze badges

Comments

Xinwen Gao · Accepted Answer · 2018-01-09 12:13:26Z

I found the situation where minCapacity < 0. Suppose there are two long size ArrayLists, when you add one to another, the size + numNew will overflow.

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

For example, the code below will throw an OutOfMemoryError.

int oneSize = Integer.MAX_VALUE - 16;
int twoSize = oneSize >> 1;
List<Byte> one = new ArrayList<>(oneSize);
for (int i = 0; i < oneSize; i++) {
    one.add((byte) 1);
}
List<Byte> two = new ArrayList<>(twoSize);
for (int i = 0; i < twoSize; i++) {
    two.add((byte) 2);
}

one.addAll(two);

can · Accepted Answer · 2020-03-04 08:56:38Z

0

it's about the representations of the number. If Integer.MAX_VALUE adds one, it would be a negative number,-2147483648. So, if the array is big enough, we grow it again will cause minCapacity less than 0.

answered Mar 4, 2020 at 8:56

can

1

Collectives™ on Stack Overflow

Can't understand the possibility of overflow when resizing ArrayList in Java

5 Answers 5

3 Comments

2 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

3 Comments

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related