realloc invalid old size

Question

Disclaimer: This is homework. I am attempting it and do not expect or want anyone to do it for me. Just a few pointers (hehe) where I'm going wrong would be appreciated.

The homework requires me to create an int* array that holds 10 elements, and then attempt to insert a million ints into it. Each insertion checks if the array needs to be resized, and if it does, I increase it's size so 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've commented it so it's easily readable.

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;
}

Sinh

Answer 1

The error is probably because you properly use realloc to change arr in the function add, but this modified value is lost when add returns. So the next call to add will receive the old, now bad value.

Also I can't understand why you're using a the for loop to search. You know you want to add at the last element, so why search? Just reallocate the array and plug the new value in the new slot.

Incidentally I'm pretty sure your teacher is trying to get you to see that reallocating for each member causes an asymptotic run time problem. Most implementations of realloc will do a lot of copying with this algorithm. This is why real programs grow the array size by a factor greater than one (often 1.5 or 2) rather than by fixed amounts.

The usual idiom is to abstract the variable size array in a struct:

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());
  }

  ...

}

Illustrious

Should add be receiving an int** to not cause this issue? – Sinh

Yes, you said you didn't want the answer, and I respect that. You're correct. – Illustrious

You're right about what the teacher is getting us to see. We're writing two versions, one that reallocates by growing by a factor of 2, and the other that grows by 1. – Sinh

Thanks. Your help got me going. I also had to change my assignments to *(*arr + i). – Sinh

Answer 2

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

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

And calling it....

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

Note that that your code (and my suggested change) is not doing any error checking. You should be checking the return value of malloc and realloc for NULL.

Zymotic