[HOME] Dynamic Arrays In C

I'm writing a game in c.

Inevitably in c, you have to deal with the fact that c doesn't have std::vector. Or anything like it.

So there are a few current solutions to this. Here are some options:

stretchy_buffer.h implements a 'generic' dynamically resizing array in c using fat pointers and a set of macros.

// "Polymorphism Via Macros"
#include "stretchy_buffer.h"

int *array = 0;
array = sb_push(array, 5); // sb_push is a macro

stretchy_buffer is cool, and you should take a look at it. It will probably do the job. Alternatively, you can also do something like this:

// "Template Via Include"
#define TYPE int
#define NAME i
#include "c-array.h"

// Example Usage:
i_Array array = i_ArrayCreate(128);
i_ArrayPush(&array, 5);

to generate a set of structs and functions for any type you might need.

Alternatively, you could do something very similar like:

// "Template Via Macro"
#include "c-array.h"
INSTANTIATE_ARRAY(i, int)

// Example Usage:
i_Array array = i_ArrayCreate(128);
i_ArrayPush(&array, 5);

to 'also' generate a set of structs and functions for any type you might need.

Okay, but what if you want to avoid macros entirely? Even more, what if you don't want to poorly imitate the c++ template system? Well you could also interact with the 'array' entirely through void pointers:

// "Generics Via Void Pointers"
#include "c-array.h"
Array array = ArrayCreate(sizeof(int), 128);
int a = 5;
ArrayPush(&array, &a); // where void ArrayPush(void *addr_array, void *addr_item)

This is disappointing because you completely throw away type checking. And the particular semantics of usage mean you're likely run into that problem. Ex:

long long int a = 5;
ArrayPush(&array, &a); // no warning or error, but will create malformed data.

This article is about the way that I solved this problem, and is still the solution that I use today. If you want the quick version of the explanation, I use fat pointers, and mostly interact with the array through a void pointer interface. When it's time to add members, I use normal c array indexing.

Here's a more in depth explanation.

So the structure for my arrays look like this:

typedef struct ArrayInfo
{
size_t count;
size_t cap;
size_t itemSize;

/// other members of the data structure.
} ArrayInfo;

It is uniform across all types the array might store. In other words, there wouldn't be an i_ArrayInfo for ints or a f_ArrayInfo for float. All types use this structure and store their size in the '.itemSize' member during initialization.

Let's take a look at the initializer/allocator:

void *ArrayCreate(size_t itemSize, size_t initCap)
{
size_t initSize = itemSize*initCap + sizeof(ArrayInfo);
ArrayInfo *info = malloc(initSize);
*info = (ArrayInfo) {
.count = 0,
.cap = initCap,
.itemSize = itemSize
/// ...
};
return info+1;
}

So the array itself is a fat pointer with the member variables of the structure packed in front of the array proper.

In memory it looks something like this:

{ ArrayInfo } | item 0 (array pointer address) | item 1 | item 2 | item 3 | ...

So any function that needs to operate on the array, but not the members, operates using void pointers. But to add a member, you do this:

size_t index = ArrayReserveSlot(&array);
array[index] = item;

ArrayReserveSlot() resizes the array to make room if necessary, returns the next free index, and increments the arrays internal count. This allows you to add a member to the array with 2 lines of code. Having to use 2 lines is probably the most unfortunate part of the system.

Conveniently, if you need to reserve more than one slot, you could write ArrayReserveSlot() to operate this way:

// where void ArrayReserveSlot(void *addr_array, size_t slotCountToReserve);
size_t index = ArrayReserveSlot(&array, 20);
for (int i = 0; i < 20; i++)
{
array[index+i] = itemsToAdd[i];
}

Overall, the benefits are:

No pseudo-templates using macros.
Not implemented via series of function-like macro invocations.
Still have type checking.
Basic array operations are still reasonably small in code. (2 lines.)
Can be easily adapted for unity-builds or multiple translation units.
Because it isn't macro based, you have wide latitude to easily adapt it however you need.
Tends to play better with debuggers.

That's the solution I use.

Andrew Dunetz

Of course there is one more question, is this legal in C:

array[ArrayReserveSlot(&array, 1)] = item;

I looked at the C spec, and I'm still not sure. ArrayReserveSlot() can assign a new pointer to array, and I don't know if that is guaranteed to resolve before the array index occurs. I think it probably isn't. So I don't use it, but if anyone out there is more confident and can point to a part of the spec that clarifies about whether that statement's behaviour is undefined or not, please get in touch.