---

I came across this blog article, where a possible implementation of dynamic arrays was shown. I did not really like some aspects of it, I thought the macros were a bit “too much” (even though they were kept very minimal), and also I wanted to add some functionality, so I built my own.

I am sure there are many things that could be improved, and I may change things in the future, but for now this is all I need, and it works well for my use cases.

Repository

You can find the code for it here.

This repository contains different utilities written in C that I use in my projects. As of the time of writing, I only have an implementation for strings and dynamic arrays, but I am planning to add more utilities in the future.

I already wrote an article about the string implementation. You can find it here.

As I already mentioned in that article, I have recently started using unity builds. I’m not entirely sold on the idea yet, but I have been experimenting with them. This implies that the repository does not have any header files, and you are meant to #include the .c files directly. If you dislike this approach, you can always add your own simple header file (there are not that many definitions).

Remark

One remark before we get started is that I am aware that some individuals prefer to stay away from “pseudo-generic” code in C, since you always have some kind of trade-off between type-safety, performance, macro hell, and code reuse.

I decided to sacrifice a bit of type-safety for the sake of convenience, but this may or may not be the right choice for you. I try to avoid having very large macros. Also, I would like to avoid having to implement the da_push, da_remove and da_unordered_remove functions for every type that I need a dynamic array for.

It also has a slight overhead in terms of performance, but that is a compromise I am willing to make.

Types

As you may already know from my strings article, I typedef some built-in types:

#include <stdint.h>
#include <stddef.h>

typedef uint8_t     u8;
typedef uint16_t    u16;
typedef uint32_t    u32;
typedef uint64_t    u64;

typedef int8_t      i8;
typedef int16_t     i16;
typedef int32_t     i32;
typedef int64_t     i64;

typedef float       f32;
typedef double      f64;

typedef size_t      usize;

Implementation

Base Struct

We will cast all dynamic array types to this void * dynamic array. You will see how this works in a second.

struct da_array {
    void   *data;
    usize   len;
    usize   cap;
};

Macros

The best way of showing how it works is to just jump straight into the code.

There are four macros that allow you to interact with a dynamic array:

#define DA_PUSH(da, elem) da_push(&da, &(typeof(elem)){ elem }, sizeof(typeof(elem)))
#define DA_FREE(da) free(da.data)
#define DA_REMOVE(da, i) da_remove(&da, i, sizeof(*da.data))
#define DA_UNORDERED_REMOVE(da, i) da_unordered_remove(&da, i, sizeof(*da.data))

You can add and remove elements. I implemented a remove and unordered remove operation. If you are unfamiliar with this distinction, we will discuss it shortly. I also created a small wrapper to free a dynamic array.

These macros are simply wrappers that avoid having to pass the size of the element manually each time.

Also, the &(typeof(elem)){ elem } will make sense in a second.

Let us now look at each function implementation.

da_push

The implementation looks like this:

void da_push(void *da, const void *elem, usize elem_size) {
    struct da_array replica;
    memcpy(&replica, da, sizeof(replica));
    if (replica.len >= replica.cap) {
        replica.cap = replica.cap ? replica.cap * 2 : 1;
        replica.data = realloc(replica.data, replica.cap * elem_size);
    }
    memcpy(replica.data + replica.len++ * elem_size, elem, elem_size);
    memcpy(da, &replica, sizeof(replica));
}

I learned this technique from the article linked at the very start. In that article, it is referred to as “memcpy type punning”.

Basically, you use memcpy to copy the data to a generic void * version of the dynamic array. You work with it and do what you need to do, and then you copy the changed data back.

This is nice, because it allows you to accept a void * argument, while still retaining the struct’s general layout. The user of the function can pass whatever they want, and for them it can be typed. The only type-unsafe operations are scoped to this function.

One downside is that the caller has to make sure to append values to a dynamic array of the same type as the value. Also, you have to make sure that what you pass as the da argument of the function is an actual dynamic array with the right memory layout (that means that the first field must be a pointer, the second must be the length, and the third must be the capacity).

At this point, the rest is just standard. If you exceed the capacity, grow the capacity by a factor of 2. Copy the element over, and increase the length by 1.

Now you can also see why we used &(typeof(elem)){ elem } in the macro. I want the user to be able to pass a value - without having to create a variable for it - and append it directly to the dynamic array. If the user wants, he can have a variable, but it does not have to be the case.

To do this, you create what is called a “compound literal”. You can almost see it as a “temporary variable” which allows us to take its address and pass it as a void * parameter.

Keep in mind that typeof is a compiler extension that may or may not be available for the compiler you are using. The two most common compilers (gcc and clang) both support it.

The same thing holds for pointer arithmetic on void *. Both gcc and clang treat is as operations on char *, which is what we want, but technically, this is not standard C.

To make it more portable, you could cast the void * to a char *. I use clang, so I do not mind the portability issues.

da_remove

Removing an element from an array is similar:

void da_remove(void *da, usize i, usize elem_size) {
    struct da_array replica;
    memcpy(&replica, da, sizeof(replica));
    usize shift_n = replica.len-- - i - 1;
    if (shift_n > 0) {
        memmove(
            replica.data + i * elem_size,
            replica.data + (i + 1) * elem_size,
            shift_n * elem_size
        );
    }
    memcpy(da, &replica, sizeof(replica));
}

You basically shift all the elements after index i back by one, overwriting the element previously at index i. You also decrease len by 1.

da_unordered_remove

The da_remove operation has a time complexity of $O(n)$, which is the fastest way if we have to preserve the relative order of the items in the dynamic array, since you have to move each element back by one index.

If we can safely disregard the ordering, there is a nice optimization we can use. Basically, instead of filling the hole left by the removed element at index i with the element at index i + 1 (the one right after it), you move the last element in the array to index i, filling the hole in just $O(1)$ time.

void da_unordered_remove(void *da, usize i, usize elem_size) {
    struct da_array replica;
    memcpy(&replica, da, sizeof(replica));
    memcpy(
        replica.data + i * elem_size,
        replica.data + (replica.len-- - 1) * elem_size,
        elem_size
    );
    memcpy(da, &replica, sizeof(replica));
}

Usage Example

That’s it. I have written some tests in my codeberg repository, and we can use some of them as examples.

We create a typed dynamic array struct (remember that the ordering of the fields is of vital importance):

struct da_i32 {
    i32    *data;
    usize   len;
    usize   cap;
};

We then create a dynamic array and initialize it with a capacity and length of 0:

struct da_i32 da = {0};

We can then append elements to the dynamic array:

DA_PUSH(da, 1);
DA_PUSH(da, 2);
DA_PUSH(da, 3);
assert(da.len == 3);
assert(da.data[0] == 1);
assert(da.data[1] == 2);
assert(da.data[2] == 3);

We can remove values:

DA_REMOVE(da, 1);

We just removed the second value (the one with value 2 that we inserted above). Our dynamic array now only has two elements:

assert(da.len == 2);
assert(da.data[0] == 1);
assert(da.data[1] == 3);

We can append another value and use unordered remove:

DA_PUSH(da, 5);
DA_UNORDERED_REMOVE(da, 0);
assert(da.len == 2);
assert(da.data[0] == 5);
assert(da.data[1] == 3);

And we finally free it when we are done:

DA_FREE(da);

Conclusions

Whether you like this implementation and would like to use it in your own projects is up to you. In any case, you are free to copy the code and use it however you please.

I believe that this is a very simple implementation that can be enough in most use cases.

If you have any suggestions, you can reach out to me on my email:

info@eliasebner.com

Thanks for reading and see you next time!