realloc invalid next size for array-CodePudding

Hello I keep getting invalid next size when using realloc to allocate more memory to an array which im trying to add 100,000 numbers too. I dont know why because im not understanding why it wont work. My code is here below.

int main() 
{
    printf("starting");
    int i;
    int *bubbleSortArray = (int *)malloc(sizeof(int));
    int numberOfElements = 0;
    int randomNumber;
    srand(time(NULL));
    int j;
    for (int j = 0; j <= 100000; j = j  1)
    {
        randomNumber = rand();
        if(numberOfElements != 0)
        {
            bubbleSortArray = (int *) realloc(bubbleSortArray, numberOfElements * sizeof(int));
        }
        bubbleSortArray[numberOfElements] = randomNumber;
        numberOfElements = numberOfElements   1; 
    }

}

CodePudding user response：

In the statement you need to write at least like

bubbleSortArray = (int *) realloc(bubbleSortArray, ( numberOfElements   1 )* sizeof(int));

Otherwise this statement

bubbleSortArray[numberOfElements] = randomNumber;

invokes undefined behavior.

Also you need to use an intermediate pointer to store the return value of the call of realloc because the function can return a null pointer. In this case the previous value stored in the pointer bubbleSortArray will be lost and you will not have an access to the already allocated memory.

So it would be better to write

int *tmp = (int *) realloc(bubbleSortArray, ( numberOfElements   1 )* sizeof(int));

if ( tmp != NULL )
{
    bubbleSortArray = tmp;
}
else
{
    // some other code
}

Pay attention to that these declarations

int i;
int j;

are redundant because the declared variables are not used.

CodePudding user response：

Oh, this is kind of scary. I'm not sure why you're not allocating enough space up front. But this code is going to realloc 100,000 times, which is an insane thing to do. Do you know what realloc does under the hood? I'll explain.

First, it does a NEW alloc of the amount of data. So the first time you loop, numberOfElements is zero, and you use your malloc'd space. But the second time it allocates space for 2 integers, then 3 integers, then 4, et cetera.

So it allocates 8 bytes. It remembers how much it allocated last time (4 bytes -- the size of an int on most systems), and it then does a memcpy of that much space.

Then it memcpy's 8 bytes. then it memcpy's 12 bytes, and so on and so on.

Bad, bad, bad.

What most people do is keep track of two values -- the amount of space allocated (capacity) and the amount used (count or numberOfElements).

So it looks something like this:

int capacity = 16;
int *bubbleSortArray = (int *)malloc(capacity * sizeof(int));
...
if (numberOfElements >= capacity) {
     // Increase capacity by whatever means you want.
     // You can double it. Or you can:
     capacity  = 16;
     bubbleSortArray = (int *) realloc(bubbleSortArray, capacity * sizeof(int));
}

Ah, and as I cut & pasted your code, I see that you used numberOfElements. So you were consistently undersizing your realloc by 1, anyway.