Why is it desirable to realloc() memory for a growing array of pointers?

Question

typedef struct {
    void **head;
    size_t used_size;
    size_t free_size;
    size_t current_size;
    size_t size_increment;
} GrowingArray;

GrowingArray createEmptyGrowingArray(int initial_size, int size_increment) {
    GrowingArray empty_growing_array;
    empty_growing_array.head = malloc(initial_size * sizeof(void *));
    empty_growing_array.used_size = 0;
    empty_growing_array.free_size = initial_size;
    empty_growing_array.current_size = initial_size;
    empty_growing_array.size_increment = size_increment;

    return empty_growing_array;
}

GrowingArray appendToGrowingArray(GrowingArray growing_array, void *new_element) {

    void *new_head_of_array;

    if (growing_array.free_size == 0) {
        new_head_of_array = realloc(growing_array.head, (growing_array.current_size + growing_array.size_increment) * sizeof(void*));
        if (new_head_of_array == NULL) {
            printf("Reallocation failure.\n");
        }

        growing_array.free_size = growing_array.size_increment;
        growing_array.current_size += growing_array.size_increment;
        growing_array.head = new_head_of_array;
    }

    growing_array.head[growing_array.used_size++] = new_element;
    growing_array.free_size--;

    return growing_array;
}

void finalizeGrowingArrayMemory(GrowingArray growing_array) {
    growing_array.head = realloc(growing_array.head, growing_array.current_size * sizeof(void *));
}

void freeGrowingArray(GrowingArray growing_array) {
    free(growing_array.head);
}

int main(int argc, char* argv[]) {
    GrowingArray test_array = createEmptyGrowingArray(5, 1);

    int *test_integer = (int *)malloc(1 * sizeof(int));
    *test_integer = 4;

    int *another_integer = (int *)malloc(1 * sizeof(int));
    *another_integer = 6;

    int *yet_another_integer = (int *)malloc(sizeof(int));
    *yet_another_integer = 9;

    test_array = appendToGrowingArray(test_array, test_integer);
    test_array = appendToGrowingArray(test_array, another_integer);
    test_array = appendToGrowingArray(test_array, yet_another_integer);
    finalizeGrowingArrayMemory(test_array);

    printf("%x,", *(int *)test_array.head[0]);
    printf("%x,", *(int *)test_array.head[1]);
    printf("%x\n", *(int *)test_array.head[2]);

    freeGrowingArray(test_array);

    printf("Going to free %llx\n", (long long int)test_integer);
    free(test_integer);

    printf("Going to free %llx\n", (long long int)another_integer);
    free(another_integer);

    printf("Going to free %llx\n", (long long int)yet_another_integer);
    free(yet_another_integer);

    return 0;
}

I wrote this code based on example code provided in the correct answer to this question: How may I implement a generic, dynamically growing array in C?

The answer provided included a function which simply reallocated the array of pointers. The intended usage is that it be called after appending several items to the array, as seen in the answer's code.

I want to know why this should be done. What benefit does it provide? Does realloc() try to make predictions about how a block of memory is going to be used based on its prior usage and then move it where it thinks is best?

Thanks!

As an add-on yes or no question: Should I be using calloc() instead of malloc() inside createEmptyGrowingArray()?

Answer 1

I want to know why this should be done. What benefit does it provide?

I think you're asking why there's a function for it, or why there's a configurable increment:

• It's convenient to separate the reallocation details into its own area to avoid cluttering your code, and also to provide a re-usable resize operation that can be called from other forms of "insert" calls that you might implement.
• Having an increment configuration allows you to enlarge the array by more than one element, which prevents excessive reallocations.
• While your example doesn't do it, it's also useful to increase the increment size as well. This would allow constant amortized time complexity for array growth.

Does realloc() try to make predictions about how a block of memory is going to be used based on its prior usage and then move it where it thinks is best?

No, it doesn't know what your block is used for. It is just allocating a chunk of memory. If it can resize it without moving the memory, it will. But if there is not enough space, or it must be moved to a different allocation scheme (memory managers often split blocks into different areas depending on their size), then the pointer will move and the contents of that memory will be copied to the new location.

As an add-on yes or no question: Should I be using calloc() instead of malloc() inside createEmptyGrowingArray()?

It is reasonable practice to use calloc, but when you create an empty array remember that you're setting the current size to zero, so malloc would suffice because you're not going to use those uninitialized values until you initialize them later (after appending). Additionally, after calling realloc to grow the block, you are not currently zeroing pointers in the new memory so it doesn't provide conceptual parity with your "create" operation.

So in your case, I would argue to use malloc which will not give unrealistic expectations about the state of your unused data. If you want to use calloc when creating, then you should also use memset to zero-out new memory after growing.