Incorrect old realloc size

Question

Disclaimer: This is homework. I am trying to do this and do not expect or do not want anyone to do this for me. Just a few pointers (hehe) where I am wrong will be appreciated.

The homework requires me to create an int* array that contains 10 elements, and then try to insert a million ints into it. Each insert checks if the array needs to be resized, and if so, I increase its size so that it can hold one more element.

When I insert 10,000 elements, it works fine, but if I try 100,000 elements, I get the following error:

 *** glibc detected *** ./set2: realloc(): invalid old size: 0x00000000024dc010 *** 

This is the code I'm running. I commented on this so that it is easy to read.

 void main() { //begin with a size of 10 int currentsize = 10; int* arr = malloc(currentsize * sizeof(int)); int i; //initalize with all elements set to INT_MAX for(i = 0; i < currentsize; i++) { arr[i] = INT_MAX; } // insert random elements for(i = 0; i < 100000; i++) { currentsize = add(rand() % 100,arr,currentsize); } free(arr); } /* Method resizes array if needed, and returns the new size of the array Also inserts the element into the array */ int add(int x, int* arr, int size) { //find the first available location int newSize = size; int i; for(i = 0; i < size; i++) { if (arr[i] == INT_MAX) break; } if (i >= size) { //need to realloc newSize++; arr = realloc(arr, newSize * sizeof(int) ); } arr[i] = x; return newSize; } 

Answer 1

The error is probably due to the fact that you are using realloc correctly to change arr in the add function, but this changed value is lost when add returned. So the next call to add will get the old, now bad value.

Also, I don't understand why you are using a for loop to search. You know what you want to add to the last element, so why look? Just redistribute the array and plug in the new value in the new slot.

By the way, I'm pretty sure that your teacher is trying to make you see that reallocation for each member causes asymptotic execution time. Most realloc implementations will make many copies using this algorithm. That is why real programs increase the size of the array by more than one (often 1.5 or 2), and not by fixed amounts.

The usual idiom is to abstract the array of variables in the structure:

 typedef struct array_s { int *elts; int size; } VARIABLE_ARRAY; void init(VARIABLE_ARRAY *a) { a->size = 10; a->elts = malloc(a->size * sizeof a->elts[0]); // CHECK FOR NULL RETURN FROM malloc() HERE } void ensure_size(VARIABLE_ARRAY *a, size_t size) { if (a->size < size) { // RESET size HERE TO INCREASE BY FACTOR OF OLD SIZE // size = 2 * a->size; a->elts = realloc(size * sizeof a->elts[0]); a->size = size; // CHECK FOR NULL RETURN FROM realloc() HERE } } // Set the i'th position of array a. If there wasn't // enough space, expand the array so there is. void set(VARIABLE_ARRAY *a, int i, int val) { ensure_size(a, i + 1); a->elts[i] = val; } void test(void) { VARIABLE_ARRAY a; init(&a); for (int i = 0; i < 100000; i++) { set(&a, i, rand()); } ... } 

Answer 2

I would pass arr to add() as a pointer (to a pointer) so that it can be changed inside add()

 int add(int x, int** arr, int size) { // ... *arr = realloc(*arr, newSize * sizeof(int) ); } 

And calling him ....

 currentsize = add(rand() % 100, &arr, currentsize); 

Please note that your code (and my proposed change) does not perform error checking. You should check the return value of malloc and realloc for NULL .