Dynamic arrays in C

Many programming languages support dynamic arrays which can grow or shrink as elements are added and removed. For example, in PHP you can create an empty array and then add an element to it with:

$arr = [];
$arr[] = 1;

This is not possible in C - array sizes must be fixed at compile time in most cases. You can create Variable Length Arrays whose size is determined at run time, however these are still not resizable. They also have the following disadvantages:

Memory is allocated on the stack. For small arrays this is not a problem, but larger ones could overflow the stack as it usually has a limited size. Valgrind warning: client switching stacks is an example of this.

Changing standardisation. VLAs weren’t in C89, were introduced in C99, made optional in C11 and then made mandatory again (but only in some circumstances) in C23.

Compiler support. Microsoft’s compiler (MSVC) did not support VLAs even when they were part of C99.

As C does not support dynamic arrays natively or via the standard library, we have to implement our own (or use a third party library - of which there are many - but that would mean not learning and experimenting). A good starting point is the slice type in Go - this is a native data type which contains the following:

Length. The number of elements in the slice.

Capacity. The size of the array.

An array of fixed size. Contains the data.

The capacity is always greater than or equal to the length. When the capacity is exceeded, Go creates a new array with a larger capacity and copies all the data across, then updates the slice to point at the new array. Effectively the slice is a wrapper around an array which hides the complexity of how and when to expand the array - to the user it is exposed as a dynamic array.

The Go model seems a sensible one to follow, as it was designed by people with a background in C. Whilst it won’t be possible to completely hide the implementation, we can produce something similar.

To start with, we need a data structure that defines a slice:

typedef struct slice {
    size_t length;
    size_t capacity;
    void **data;
} slice_t;

The purpose of each struct field is as follows:

We use void * to point to each element, as this allows us to have a generic slice which can be used with any data type. void **data allows us to treat the elements like an array, e.g. we can use array indexing such as data[0] to get the first element.

Whilst we could manipulate the slice directly by changing the struct in our calling code, we should write some helper functions to do this for us. Some third party library authors choose to implement their dynamic arrays using macros, however this tends to lead to messy and unreadable code, as well as being reliant on the preprocessor. Using functions is clearer as we can see what code will be run, whereas it is harder to see what a macro will expand to.

First of all, we need a function to create a new slice with an initial capacity.

slice_t *slice_new(size_t initial_capacity) {
    slice_t *slice = calloc(1, sizeof(slice_t));

    slice->length = 0;
    slice->capacity = initial_capacity;
    slice->data = NULL;

    if (slice->capacity > 0) {
        slice->data = calloc(slice->capacity, sizeof(void *));
    }

    return slice;
}

This is very simple, we allocate memory for a new slice (only the slice itself, not the data it points to) and set its length to zero. The data is set to NULL because currently it contains no elements. This is a very lazy initialisation, as we don’t allocate any memory for the data - effectively we are deferring this step until the first time we append an element. If the slice is never used, no memory is allocated, other than for the slice itself. If we wanted to always take the allocation hit immediately, we can set the capacity to something other than zero and then memory will be allocated.

In most cases it doesn’t matter when the allocation occurs, but if we were operating in a constrained environment (e.g. an embedded device that needs to respond in real time), we might choose to set an initial capacity so that the allocation takes place at a specific known point. If we knew the maximum number of elements, we could generate a slice with that capacity and never have to do any further allocations.

The next most common operation is to append an element to an existing slice:

bool slice_append(slice_t *slice, void *element_data) {
    if (slice->length == slice->capacity) {
        size_t new_capacity = slice->capacity += 5;
        void *new_data = realloc(slice->data, new_capacity * sizeof(void *));

        if (new_data == NULL) {
            return false;
        }

        slice->data = new_data;
        slice->capacity = new_capacity;
    }

    slice->data[slice->length] = element_data;
    slice->length++;

    return true;
}

Before we append an element, we have to check if there is enough capacity by comparing it to the length. If the capacity is fully utilised, we increase it by 5 and use realloc to copy the existing data to the new, larger, memory location. If realloc fails, we return false and do not modify the existing slice. Once we’ve performed or skipped the capacity increase, we can store the new element (or rather a pointer to it) in the last location. As ‘arrays’ are zero-indexed in C, we store it at slice->length, e.g. if an array has 10 elements, these will be [0..9], so [10] will be the first free slot.

Something else which is often useful is to concatenate two slices. This is straightforward, as we simply create a new slice and then append each item of the two slices to concatenate.

slice_t *slice_concat(slice_t *a, slice_t *b) {
    // Capacity of concatenated slice is always the same as the length of the two inputs
    slice_t *concat = slice_new(a->length + b->length);

    for (size_t i = 0; i < a->length; i++) {
        slice_append(concat, a->data[i]);
    }

    for (size_t i = 0; i < b->length; i++) {
        slice_append(concat, b->data[i]);
    }

    return concat;
}

Note that so far we have not freed any of the memory allocated, either for the slice structure or the data. Our error handling is also extremely limited - we should check for failures of calls to calloc and similar functions. Also, two slices may contain pointers to the same data, so we cannot safely call free on all the elements in a slice, because that could invalidate other slices.