Simple Dynamic Array in C

Vectors/Dynamic Arrays are one of the most important data structures used in almost all programs. In C there is no notion of a dynamic array so the programmer must create their own. There are many ways to do this but my favorite way is Sean Barret's stretchy buffer.

The way it works is your "array" is a normal pointer to a type of data. For example:

uint32_t* number_array = NULL;

Then when you allocate memory for this pointer you add a little extra space for a struct containing the capacity, and size of the array. If you have not used a dynamic array before, capacity is the number of slots in the array while the size is the number of slots being used.

uint32_t* number_array = NULL;

typedef struct array_header
{
    size_t capacity;
    size_t size;
}array_header;

Above is what the array header would look like. Now, let's write a simple function that allocates memory for this array.

void* set_capacity(void* arr, size_t new_cap, size_t elem_size)
{
    //Create a pointer to the array or 0 if the array is NULL
    uint8_t* array = (arr) ? (uint8_t*) get_array_header(arr) : 0;

    //Get the current size of the array
    const size_t current_size = array_size(arr);
    //Get the extra byte size of the header
    const size_t extra = sizeof(array_header);
    //Size for our array
    const size_t new_size = new_capacity ? elem_size * new_capacity + extra : 0;
    //Allocate Memory for the array
    array = realloc(array, new_size);
    //Bump the array pointer foward past the header data
    void *copy = array? array + extra : array;
    //If the copy exists set the size and capacity
    if (copy) {
        get_array_header(copy)->size = current_size;
        get_array_header(copy)->capacity = new_capacity;
    }
    return copy;
}

Let's break down what is going on in this function:

• The function returns a void* which will be the allocated array.

• The function takes in a void* array, the new capacity, and the size of the type the array is equal to.

• First, we create a pointer to the array but notice how we call a macro "get_array_header" this returns us the point of the array where the header data is being stored. If the array is NULL we set the pointer to NULL.

• We then calculate the size the array needs to be and realloc the pointer.

• Lastly, we set the new capacity and size of the array and return it to the user.

So this function allocates the memory for our array but we still need a few more pieces for a functional implementation.

#define get_array_header(a) (array_header*)(uint8_t*)(a) - sizeof(array_header);

#define array_size(a) ((a) ? get_array_header(a)->size : 0)

#define array_capacity ((a) ? get_array_header(a)->capacity : 0)

These 3 macros let us access the header data for our array.

void* grow_array(void *arr, size_t least, size_t elem_size)
{
    const size_t capacity = arr ? array_capacity(arr) : 0;
    if (capacity >= least)
        return arr;
    const size_t min_new_capacity = capacity ? capacity * 2 : 16;
    const size_t new_capacity = MAX(min_new_capacity, least);
    return set_capacity(arr, new_capacity, elem_size);
}

This function will calculate the needed capacity based on the "least" capacity needed, then call our "set_capacity" function.

Now we only need a few more macros for our dynamic array implementation to be usable

//Returns true if array needs to grow to hold n elements
#define array_needs_growth(a, n) ((n) > array_capacity(a))

#define array_grow(a, v) ((*(void **)&(a)) = grow_array((void *)a, v, sizeof(*(a))))

#define array_check(a, v) (array_needs_growth(a, v) ? array_grow(a, v) : 0)

#define array_push(a, v) (array_check(a, array_size(a) + 1), (a)[get_array_header(a)->size++] = (v), (a) + get_array_header(a)->size - 1)

These macros may look complicated but they are very simple!

• "array_needs_growth" checks to see if "n" is greater than the current capacity of our array

• "array_grow" takes the address of our array, dereferences it and then sets it equal to whatever "grow_array" returns to us. Look closely at how we pass the array as a void* and for elem_size we pass the size of (*a) which is the type of our array.

• "array_check" is a convenience macro that calls "array_check" and if it is true calls "array_grow"

• "array_push" puts everything together and makes the array usable. First, it checks and grows the array, passing the "current size + 1" as the minimum capacity needed. Then, we add "v" to our array at the current size, increasing the size after placing the value. Lastly, we bump our array pointer to the current size.

Now we have a usable stretchy buffer that can store any type of value and can be iterated over like a normal C99 array! I hope this has inspired you to use stretchy buffers or has helped you in understanding them more. For more information take a look at Saun Barretts stretchy buffer implementation at https://github.com/nothings/stb/blob/master/stb_ds.h

GO CODE!