path: root/ramblings/c-is-the-best/index.md

\> [go back](/ramblings)

# 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.

```c
#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:

```c
#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:

```c
// 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:

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

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

```c
#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:

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

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

```c
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.

<hr>

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

```c
#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.