> go back

Rambling: Implementing a Dynamic Array in C

Have you ever wanted C to have a fully featured, easy-to-use, generic dynamic array, which can be implemennted in a small of time?

What if I told you that C can have a full, easy-to-use, generic dynamic array, which can be implemented in a small amount of time? Because it can. I wrote the whole thing without testing, and it worked almost first try.

Let's start with the creation of a dynamic array. You might need to scroll horizontally if your screen is teensy weensy.

#define DA_MIN_CAP 8

// Wrap the function in a macro to make it a little nicer to use.
#define da_create(T, init_cap) \
  ((T*)_da_create(sizeof(T), init_cap))

void* _da_create(size_t type_size, int init_cap) {
  // Ensure a mimimum capacity.
  init_cap = init_cap < DA_MIN_CAP
    ? DA_MIN_CAP
    : init_cap;

  // Those + 2 ints are our length and capacity. You can use
  // whatever integer type you want; int is fine for this use-case.
  int* arr = (int*)malloc(type_size * init_cap + sizeof(int) * 2);

  // Which we assign here.
  arr[0] = 0;
  arr[1] = init_cap;

  return (void*)(arr + 2);
}

So, we define a function _da_create(). It takes in the size of the type you want to create, and how many elements to reserve space for. It allocates that space, plus space for two integers.

Those two integers are your array length and array capacity. They are placed in front of the array.

And then we return the pointer we allocated, but offset to point to the start of your data. Finally, we wrap all this in a nice little macro called da_create() so we don't need to explicitly pass the size and cast the resulting pointer.

Tada! You now have a generic dynamic array. Okay, well not really. You have a heap-allocated array with two useless integers in front. Now, we need to be able to access those integers in order to make them useful:

#define da_len_ptr(arr) ((int*)arr - 2)
#define da_len(arr) (*da_len_ptr(arr))

#define da_cap_ptr(arr) ((int*)arr - 1)
#define da_cap(arr) (*da_cap_ptr(arr))

And now you have access to them. We have a separate macro to get a pointer to the length/capacity so we can assign it. But anyway, how do you append? Well, like so:

// This fancy lil macro just gets the pointer that
// we actually alloc'd.
#define da_base(arr) ((void*)arr - 2)

// Of course, we wrap it in a macro for convenience.
#define da_append_slot(T, arr) 
  ((T*)_da_append_slot(sizeof(T), (void*)arr))

// This function returns the slot it just appended.
void* _da_append_slot(size_t type_size, void** arr) {
  int cap = da_cap_ptr(*arr);
  int len = da_len_ptr(*arr);

  (*len)++;

  // If we need space, grow the array.
  if (*len > *cap) {
    // This won't work if the initial capacity is 0, which
    // is why we implemented a minimum.
    *cap *= 2;

    // The base array is what realloc expects.
    void* base = da_base(*arr);
    base = realloc(base, (type_size * *cap) + sizeof(int) * 2);
    assert(base != NULL); // Just to handle the case.
    *arr = (void*)((int*)base + 2);

    // Update the length so we don't get a use-after-free later.
    len = da_len_ptr(*arr);
  }

  return *arr + ((*len - 1) * type_size);
}

So this doesn't actually really truly append anything. It ensures the existence of a new slot at the end of the array, increments the length, and returns a pointer to the last element. I didn't want to name it something like da_ensure_one(), because it does a bit more than just make sure there's space for your new element.

Anyway, you can append an element onto the end of the array by doing something like this:

int* arr = da_create(int, 0);
*da_append_slot(int, &arr) = 5;

Which you might notice can be wrapped up in a macro:

#define da_append(T, arr, elem) (*da_append_slot(T, arr) = elem)

And tada, you now can append elements to your very own dynamic array. And best of all, you don't need to care too much about the internals in your usage. You don't need to use some bespoke array data type. You don't need to worry about storing the length and capacity; it's all already handled for you.

But before I finish, we need to clean up the array, of course:

void da_free(void* arr) {
  void* base = da_base(arr);
  free(base);
}

Here's a fancy schmancy example of how to use it:

int main(void) {
  uint64_t* arr = da_create(uint64_t, 0);

  // Append some stuff.
  for (int i = 0; i < 20; i++) {
    da_append(uint64_t, &arr, 900000000000000 + i);
  }

  // Show some data.
  printf("capacity: %d, length: %d\n", da_cap(arr), da_len(arr));
  for (int i = 0; i < da_len(arr); i++) {
    printf("[%d] = %lu\n", i, arr[i]);
  }
  
  da_free(arr);
}

I'll leave implementing extra methods like da_remove() and da_find() as an exercise to the reader. If you know the basics of C, this shouldn't be too hard, since as you might've noticed, the code for this dynamic array is pretty similar to how someone would usually implement one.

For those interested, here's the full source code:

#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

#define DA_MIN_CAP 8

#define da_create(T, init_capacity) \
  ((T*)_da_create(sizeof(T), init_capacity))

#define da_len_ptr(arr) ((int*)arr - 2)
#define da_len(arr) (*da_len_ptr(arr))

#define da_cap_ptr(arr) ((int*)arr - 1)
#define da_cap(arr) (*da_cap_ptr(arr))

#define da_base(arr) ((void*)da_len_ptr(arr))

#define da_append_slot(T, arr) \
  ((T*)_da_append_slot(sizeof(T), (void**)arr))

#define da_append(T, arr, elem) (*da_append_slot(T, arr) = elem)

void* _da_create(size_t type_size, int init_cap) {
  init_cap = init_cap < DA_MIN_CAP
    ? DA_MIN_CAP
    : init_cap;

  int* arr = (int*)malloc(type_size * init_cap + sizeof(int) * 2);
  
  arr[0] = 0;
  arr[1] = init_cap;
  return (void*)(arr + 2);
}

void* _da_append_slot(size_t type_size, void** arr) {
  int* cap = da_cap_ptr(*arr);
  int* len = da_len_ptr(*arr);

  (*len)++;

  if (*len > *cap) {
    *cap *= 2;

    void* base = da_base(*arr);
    base = realloc(base, (type_size * *cap) + sizeof(int) * 2);
    assert(base != NULL);
    *arr = (void*)((int*)base + 2);

    len = da_len_ptr(*arr);
  }

  return *arr + ((*len - 1) * type_size);
}

void da_free(void* arr) {
  void* base = da_base(arr);
  free(base);
}

int main(void) {
  uint64_t* arr = da_create(uint64_t, 0);

  int* len = da_len_ptr(arr);
  for (int i = 0; i < 20; i++) {
    da_append(uint64_t, &arr, 900000000000000 + i);
  }

  printf("capacity: %d, length: %d\n", da_cap(arr), da_len(arr));
  for (int i = 0; i < da_len(arr); i++) {
    printf("[%d] = %lu\n", i, arr[i]);
  }
  
  da_free(arr);
}

And to be clear: I'm aware of how basic this article is. I just wrote it to fill out space on my website.