Memory allocation/reallocation question

Question

I just finished working out a memory allocation problem with the current program I'm writing, but I am not happy with what I had to do to fix it.

In my program, I was building up an array of structs, reallocating space for the array every time I wanted to add a struct to it. Here is a generic version of my struct and the function that would add a struct to the array:

typedef struct Example {
    const char* name;
    int (*func)(int, int);
    int bool_switch;
}

int add_struct_to_array( Example **example_array, int *ex_array_size, int name, int (*func)(int, int), int bool_switch)
{
    // first, make a new struct
    Example *new_example = (Example *) calloc( 1, sizeof( Example ) );
    if( new_example != NULL ) {
        new_example->name = name;
        new_example->func = func;
        new_example->bool_switch = bool_switch;
        ( *ex_array_size )++;
    } else {
        printf( "Errror allocating %s\n", name );
        exit( -1 );
    }

    // now, realloc the array of structs and add the new member to it
    Example **temp_example_array = ( Example** )realloc( example_array, ( *ex_array_size ) * sizeof( Example* ) );
    if( temp_example_array != NULL ) {
        example_array = temp_example_array;
        example_array[ ( *ex_array_size ) - 1 ] = new_example;
    } else {
        printf( "Reallocation failed\n" )
        exit( -1 );
    }
    return 0;
}

And here is where I would call the functions (notice how I'm initially allocating the array of structs, cuz that's where the problem was)

#include "example_struct.h"

int main( int argc, char **argv )
{
    int ex_array_size = 0;
    Example **example_array = ( Example** )calloc( 0, sizeof( Example* ) );

    add_struct_to_array( example_array, &ex_array_size, "name", &function, 1 );
    ...
    ...
    add_struct_to_array( example_array, &ex_array_size, "other_name", &other_func, 0 );

    /* Do stuff here */

    example_array_free( example_array );

    return 0;
}

In my ignorance, I apparently thought that allocating the array with size 0 would be ok, since it was initially empty, and I could add structs to it after that. Obviously, this did not work, I would get runtime errors about error for object 0x100100080: pointer being reallocated was not allocated. The example_array was at address 0x100100080 and the first struct I would allocate for would be at address 0x100100090, and after a few reallocations the example_array would run out of room.

So, finally, to my question. I solved this problem by allocating more space for my example_array than I would need, but that seems very inelegant. Is there a better way to do this?

**EDIT**

Ok, so from the looks of most of the responses, I shouldn't be using pointers to pointers. So, I am trying it a slightly different way, mixing pmg and crypto's responses. Here is my code now:

/* example_struct.h */
int add_struct_to_array( Example *example_array, int *ex_array_size, int name, int (*func)(int, int), int bool_switch)
{
    Example temp_example_array = realloc( example_array, ( ( *ex_array_size ) + 1 ) * sizeof( Example ) );

    if( temp_example_array != NULL ) {
        example_array = temp_example_array;
        Example new_example;
        new_example.name = name;
        new_example.func = func;
        new_example.bool_switch = bool_switch;
        example_array[ ( *ex_array_size ) ] = new_example;
        ++( *ex_array_size );
    } else {
        fprintf( stderr, "Error reallocating for %s", name );
        exit( -1 );
    }
    return 0;
}



/* main.c */
...
...
#include "example_struct.h"
int main( int argc, char **argv )
{
    int ex_array_size = 0;
    Example *example_array = NULL;

    add_struct_to_array( example_array, &ex_array_size, "name", &func, 1 );
    add_struct_to_array( ... );
    ...
    add_struct_to_array( example_array, &ex_array_size, "other name", &other_func, 0 );

    example_free( example_array );
}

Everything compiles and realloc's alright, but I have trouble accessing the structs within the array.

/* main.c */
...
...
#include "example_struct.h"
int main( int argc, char **argv )
{
    int ex_array_size = 0;
    Example *example_array = NULL;

    add_struct_to_array( example_array, &ex_array_size, "name", &func, 1 );
    add_struct_to_array( ... );
    ...
    add_struct_to_array( example_array, &ex_array_size, "other name", &other_func, 0 );


    printf( "%s\n", example_array[0].name ) /* Segfault */


    example_free( example_array );
}

Thanks again for all your help.

Answer 1

realloc takes NULL as the pointer value very fine ... and does a malloc in that case

*p = NULL;
new = realloc(p, 42); /* same as new = malloc(42); */
if (!new) { /* error */ }
p = new;

So, forget about calloc (you will overwrite the zeroes right after, anyway), initialize your pointers to NULL and realloc at will.

int main(void) {
    Example *example_array = NULL;
    add_struct_to_array(&example_array, &ex_array_size, "name", function, 1);
    /* ... */
    free(example_array);
}

Answer 2

It seems like an std::vector would fit your needs perfectly. It's as fast as an array and knows how to manage the memory. A simple example is below.

A vector uses contiguous memory just as an array does. If you know how many Example objects are needed you can tell the vector how large it needs to be in the constructor. If you do not know how many there will be the vector will grow to meet your needs. If performance is important then try to allocate the total amoutn of memory in the constructor because when a vector reallocates it will create a new chunk of continous memory and then copy each object into the new memory area (Examples constructor's and destructor's will be executed when this happens).

Check out the different constructors, capacity(), and reserve() of a vector here.

#include <vector>

int function_1(int a, int b) {
    return 100;
}

int function_2(int a, int b) {
    return 200;
}

typedef struct  {
    int name;
    int (*func)(int, int);
    int bool_switch;
} example_t;

typedef std::vector<example_t> example_container_t;

int main() {
    example_container_t container;

    example_t example_1;
    example_1.name = 1;
    example_1.func = &function_1;
    example_1.bool_switch = true;
    container.push_back(example_1);

    example_t example_2;
    example_2.name = 1;
    example_2.func = &function_1;
    example_2.bool_switch = true;
    container.push_back(example_2);
    return 0;
}

Answer 3

Try the following changes. You wouldn't need to allocate any additional space.

Edit: Adding changes suggested by pmg & Bart van Ingen Schenau

int add_struct_to_array( Example ***example_array, int *ex_array_size, int name, int (*func)(int, int), int bool_switch)
{
     Example **temp_example_array = realloc(*example_array,((*ex_array_size) + 1) * sizeof(Example *) );
     Example *new_example = calloc(1, sizeof( Example ) );

    if( temp_example_array != NULL && new_example != NULL ) {
        *example_array = temp_example_array;
        *example_array[ *ex_array_size ] = new_example;
        new_example->name = name;
        new_example->func = func;
        new_example->bool_switch = bool_switch;
        ( *ex_array_size )++;
    } else {
        printf( "Error allocating %s\n", name );
        exit( -1 );
    }
    return 0;
}


#include "example_struct.h"

int main( int argc, char **argv )
{
    int ex_array_size = 0;
    Example **example_array = calloc( 0, sizeof( Example* ) );

    add_struct_to_array( &example_array, &ex_array_size, "name", &function, 1 );
    ...

    add_struct_to_array( &example_array, &ex_array_size, "other_name", &other_func, 0 );

    ...

    example_array_free( example_array );

    return 0;
}

To avoid breaking any of your other code, I have used the pointer-to-pointer example_array. Although, a better solution would be to simple use a pointer to the struct, & keep realloc()ing space to it.

Answer 4

Here's a minimum working version (with C++ keywords for lots of identifiers -- I kinda apologize, but it looked fun when I started and I couldn't stop or go back midway through) which also runs on ideone ( http://ideone.com/iMByR )

#include <stdio.h>
#include <stdlib.h>

struct protected {
  int this;
  int (*catch)(int, int);
  int friend;
};

int catch(int mutable, int virtual) {
  return mutable + virtual;
}

struct protected *add_one(struct protected **private,
                          int *explicit, int using,
                          int (*catch)(int, int), int friend) {
  struct protected *new;

  new = realloc(*private, (*explicit + 1) * sizeof *new);
  if (new) {
    *private = new;
    (*private)[*explicit].this = using;
    (*private)[*explicit].catch = catch;
    (*private)[*explicit].friend = friend;
    (*explicit)++;
  }
  return new;
}

/* create an array of structs using dynamic memory */
/* keep adding elements to it, and growing it as needed */
int main(void) {
  int using;
  /* explicit contains the number of elements in the try array */
  int explicit = 0;
  struct protected *try = NULL;

  /* create and grow */
  for (using = 0; using < 7; using++) {
    if (add_one(&try, &explicit, using + 1, catch, 0) == NULL) {
      fprintf(stderr, "failure at loop %d\n", using);
      exit(EXIT_FAILURE);
    }
  }

  /* verify */
  for (using = 0; using < explicit; using++) {
    printf("%d: %d\n", using, try[using].this);
  }

  free(try);
  return 0;
}