realloc of array inside a struct

Question

I'm trying to write a function that uses realloc() to extend the array as pointed to within in instance of a struct, however I can't seem to get it to work.

The relevant part of my code is:

struct data_t {
  int data_size;
  uint16_t *data;
};

void extend_data(data_t container, uint16_t value) {
    // adds an additional uint16_t to the array of DATA, updates its internal
    // variables, and initialises the new uint to VALUE.

    int len_data = sizeof(*(container->data)) / sizeof(uint16_t);
    printf("LENGTH OF DATA: %d\n", len_data);

    container->data = realloc(container->data, sizeof(*(container->data))+sizeof(uint16_t));
    container->data_size++;
    container->data[container->data_size-1] = value;

    len_data = sizeof(*(container->data)) / sizeof(uint16_t);
    printf("LENGTH OF DATA: %d\n", len_data);
    printf("data_size: %d\n", container->data_size);

    return;
}

Can anybody see what the problem is with this?

Answer 1

You don't calculate the new size correctly. Consider this:

typedef struct {
    size_t  size;
    int    *data;
} int_array;
#define  INT_ARRAY_INIT  { 0, NULL}

void int_array_resize(int_array *const  array,
                      const size_t      newsize)
{
    if (!array) {
        fprintf(stderr, "int_array_resize(): NULL int_array.\n");
        exit(EXIT_FAILURE);
    }
    if (!newsize) {
        free(array->data);
        array->data = 0;
        array->size = 0;
    } else
    if (newsize != array->size) {
        void *temp;

        temp = realloc(array->data, newsize * sizeof array->data[0]);
        if (!temp) {
            fprintf(stderr, "int_array_resize(): Out of memory.\n");
            exit(EXIT_FAILURE);
        }
        array->data = temp;
        array->size = newsize;
    }
}

/* int_array  my_array = INT_ARRAY_INIT;
      is equivalent to
   int_array  my_array;
   int_array_init(&my_array);
*/
void int_array_init(int_array *const array)
{
    if (array) {
        array->size = 0;
        array->data = NULL;
    }
}

void int_array_free(int_array *const array)
{
    if (array) {
        free(array->data);
        array->size = 0;
        array->data = NULL;
    }
}

The key point is newsize * sizeof array->data[0]. This is the number of chars needed for newsize elements of whatever type array->data[0] has. Both malloc() and realloc() take the size in chars.

If you initialize new structures of that type using int_array my_array = INT_ARRAY_INIT; you can just call int_array_resize() to resize it. (realloc(NULL, size) is equivalent to malloc(size); free(NULL) is safe and does nothing.)

The int_array_init() and int_array_free() are just helper functions to initialize and free such arrays.

---

Personally, whenever I have dynamically resized arrays, I keep both the allocated size (size) and the size used (used):

typedef struct {
    size_t  size;   /* Number of elements allocated for */
    size_t  used;   /* Number of elements used */
    int    *data;
} int_array;
#define  INT_ARRAY_INIT { 0, 0, NULL }

A function that ensures there are at least need elements that can be added is then particularly useful. To avoid unnecessary reallocations, the function implements a policy that calculates the new size to allocate for, as a balance between amount of memory "wasted" (allocated but not used) and number of potentially slow realloc() calls:

void int_array_need(int_array *const  array,
                    const size_t      need)
{
    size_t  size;
    void   *data;

    if (!array) {
        fprintf(stderr, "int_array_need(): NULL int_array.\n");
        exit(EXIT_FAILURE);
    }

    /* Large enough already? */
    if (array->size >= array->used + need)
        return;

    /* Start with the minimum size. */
    size = array->used + need;

    /* Apply growth/reallocation policy. This is mine. */
    if (size < 256)
        size = (size | 15) + 1;
    else
    if (size < 2097152)
        size = (3 * size) / 2;
    else
        size = (size | 1048575) + 1048577 - 8;

    /* TODO: Verify (size * sizeof array->data[0]) does not overflow. */

    data = realloc(array->data, size * sizeof array->data[0]);
    if (!data) {
        /* Fallback: Try minimum allocation. */
        size = array->used + need;
        data = realloc(array->data, size * sizeof array->data[0]);
    }
    if (!data) {
        fprintf(stderr, "int_array_need(): Out of memory.\n");
        exit(EXIT_FAILURE);
    }

    array->data = data;
    array->size = size;
}

There are many opinions on what kind of reallocation policy you should use, but it really depends on the use case.

There are three things in the balance: number of realloc() calls, as they might be "slow"; memory fragmentation if different arrays are grown requiring many realloc() calls; and amount of memory allocated but not used.

My policy above tries to do many things at once. For small allocations (up to 256 elements), it rounds the size up to the next multiple of 16. That is my attempt at a good balance between memory used for small arrays, and not very many realloc() calls.

For larger allocations, 50% is added to the size. This reduces the number of realloc() calls, while keeping the allocated but unused/unneeded memory below 50%.

For really large allocations, when you have 2²¹ elements or more, the size is rounded up to the next multiple of 2²⁰, less a few elements. This caps the number of allocated but unused elements to about 2²¹, or two million elements.

(Why less a few elements? Because it does not harm on any systems, and on certain systems it may help a lot. Some systems, including x86-64 (64-bit Intel/AMD) on certain operating systems and configurations, support large ("huge") pages that can be more efficient in some ways than normal pages. If they are used to satisfy an allocation, I want to avoid the case where an extra large page is allocated just to cater for the few bytes the C library needs internally for the allocation metadata.)

Answer 2

Edit

As R. Sahu points out, container is not a pointer in this function - when you said the code "wasn't working", I assumed you meant that you weren't growing your array, but what you've written here won't even compile.

Are you sure you've copied this code correctly? If so, does "not working" mean you're getting a compile-time error, a run-time error, or just unexpected output?

If you've copied the code as written, then the first thing you need to do is change the function prototype to

void extend_data(data_t *container, uint16_t value) {

and make sure you're passing a pointer to your data_t type, otherwise the update won't be reflected in calling code.

Original

In the line

container->data = realloc(container->data, sizeof(*(container->data))+sizeof(uint16_t));

sizeof(*(container->data)) evaluates to sizeof (uint16_t). container->data is a pointer to, not an array of, uint16_t; sizeof will give you the size of the pointer object, not the number of elements you've allocated. What you want to do is something like the following:

/**
 * Don't assign the result of a realloc call back to the original
 * pointer - if the call fails, realloc will return NULL and you'll
 * lose the reference to your original buffer.  Assign the result to
 * a temporary, then after making sure the temporary is not NULL,
 * assign that back to your original pointer.
 */
uint16_t *tmp = realloc(container-data, sizeof *container->data * (container->data_size + 1) );
if ( tmp ) 
{
  /**
   * Only add to container->data and update the value of container->data_size
   * if the realloc call succeeded.
   */
  container->data = tmp;
  container->data[container->data_size++] = value;
}

Answer 3

void extend_data(data_t container, ...

In your function container is not the pointer but the struct itself passed by the value so you cant use the -> operator.

The realloced memory will be lost as you work on the local copy of the passed strucure and it will be lost on the function return.

sizeof(*(container.data)) / sizeof(uint16_t)

it will be always 1 as the *(uint16_t *) / sizeof(uint16_t) is always one.

Why: data member is pointer to the uint16_t. *data has the type of uint16_t

sizeof is calculated during the compilation not the runtime and it does not return the ammount of memory allocated by the malloc.

Answer 4

It appears you aren't using sizeof correctly. In your struct you've defined a uint16_t pointer, not an array. The size of the uint16_t* data type is the size of a pointer on your system. You need to store the size of the allocated memory along with the pointer if you want to be able to accurately resize it. It appears you already have a field for this with data_size. Your example might be able to be fixed as,

// I was unsure of the typedef-ing happening with data_t so I made it more explicit in this example
typedef struct {
    int data_size;
    uint16_t* data;
} data_t;

void extend_data(data_t* container, uint16_t value) {
    // adds an additional uint16_t to the array of DATA, updates its internal
    // variables, and initialises the new uint to VALUE.

    // CURRENT LENGTH OF DATA
    int len_data = container->data_size * sizeof(uint16_t);
    printf("LENGTH OF DATA: %d\n", len_data);

    uint16_t* tmp = realloc(container->data, (container->data_size + 1) * sizeof(uint16_t));
    if (tmp) {
        // realloc could fail and return false.
        // If this is not handled it could overwrite the pointer in `container` and cause a memory leak
        container->data = tmp;
        container->data_size++;
        container->data[container->data_size-1] = value;
    } else {
        // Handle allocation failure
    }

    len_data = container->data_size * sizeof(uint16_t);
    printf("LENGTH OF DATA: %d\n", len_data);
    printf("data_size: %d\n", container->data_size);

    return;
}