A generic dynamic array in C that stores no capacity and needs no struct

README.md

A generic dynamic array in C that stores no capacity and needs no struct

The following header shows a way to make a generic dynamic array in C with an array of two pointers:

• one pointer (accessible as vec_ptr[vec]) points to the data;
• the other pointer (accessible as vec_len[vec]) encodes the length of the array in the pointer. Thus, (size_t)vec_len[vec] returns the len as size_t.

So, int *vec[2] = { 0 }; is an empty dynamic array of ints. struct person *people[2] = { 0 }; is an empty dynamic array of people.

The vec_push(vec, value) macro pushes a value at the end of a dynamic array. It returns true if pushing succeeded, and false otherwise. Note that the dynamic array is not automatically freed on failure.

This code is C23 with statement expressions (a GNU C feature).

(If you're wondering why vec_ptr[vec] works, it's because a[b] and b[a] both evaluate to *(a + b) in C.)

Why is this interesting

First of all, structs aren't used so you don't have to invent names for them (e.g. there is no IntVec), because a pointer is used to encode the length of a dynamic array. Caveat: this design assumes pointers have no trap representations and round-trip integer values, so it may fail on architectures where this assumption doesn't hold.

Second of all, capacity isn't stored at all by default. Instead, it's computed on demand when the length of a vec is either zero or a power of two at the time vec_push is called. In this case realloc is called with capacity equal to the next power of two greater than the length. The drawback is that it's more difficult to "reserve" elements: during pushing, when the length reaches a power of two, realloc is called for the next power of two no matter what, so a larger manual reservation is effectively discarded.

Support for optional capacity

Plot twist! It's possible to store capacity if the declared array contains three elements, e.g. int *vec[3] = { 0 };. vec_push is generic (in the _Generic sense) and handles such arrays automatically. If the given array has a capacity, realloc will be called only if the length becomes equal to the capacity, as opposed to calling it every time the length of a vec is either zero or a power of two at the time vec_push is called. This may be desired in some use cases. vec_cap[vec] can be used to access the capacity of such dynamic arrays.

main.c

// Note: this is a demo to show the API. We don't handle all possible errors.

#include <stdint.h>
#include <stdio.h>
#include "vec.h"

// A dummy function to print a vec of ints.
// We could've accepted a vec as `int **` instead.
// Accepting it as `int *(*)[2]` preserves more type information.
void f(int *(*ints)[2]) {
    // Notice how `vec_ptr[*ints]` is less typing than `(*ints)[vec_ptr]`.
    for (size_t i = 0; i < (size_t)vec_len[*ints]; i++) printf("f: %d\n", vec_ptr[*ints][i]);
}

int main() {
    int *ints[2] = { 0 };

    for (size_t i = 0; i < 5; i++) if (!vec_push(ints, i + 42)) {
        return 1;
    }

    // 42, 43, 44, 45, 46.
    for (size_t i = 0; i < (size_t)vec_len[ints]; i++) printf("%d\n", vec_ptr[ints][i]);

    // Passing a vec by `&` so more type information is preserved.
    // The main drawback is that this is awkward with capped vecs and a little bit more typing.
    f(&ints);

    // Shrinking works.
    vec_len[ints] = (void *)3;
    // You can only reclaim memory down to the next power of two greater than or equal to the length.
    // Otherwise pushing will break.
    vec_ptr[ints] = realloc(vec_ptr[ints], sizeof(**ints) * 4);

    // 42, 43, 44.
    for (size_t i = 0; i < (size_t)vec_len[ints]; i++) printf("%d\n", vec_ptr[ints][i]);

    free(vec_ptr[ints]);

    struct person {
        char *name;
        int age;
    } *people[2] = { 0 };

    vec_push(people, ((struct person){ "Bob", 21 }));
    vec_push(people, ((struct person){ "Joe", 42 }));

    // Bob: 21, Joe: 42.
    for (size_t i = 0; i < (size_t)vec_len[people]; i++) printf("%s: %d\n", vec_ptr[people][i].name, vec_ptr[people][i].age);

    free(vec_ptr[people]);

    // A vec with capacity.
    // Unlike vecs without capacity, this one only reallocs when its len is equal to its cap.
    // (I.e. it doesn't necessarily realloc when an element is inserted at an index which is a power of two.)
    int *capped[3] = { 0 };
    vec_cap[capped] = (void *)1000;
    vec_ptr[capped] = malloc(sizeof(int) * (size_t)vec_cap[capped]);

    vec_push(capped, 1);
    vec_push(capped, 2);
    vec_push(capped, 3);

    for (size_t i = 0; i < (size_t)vec_len[capped]; i++) printf("%d\n", vec_ptr[capped][i]);

    free(vec_ptr[capped]);
}

vec.h

#ifndef VEC_H
#define VEC_H

#include <stdint.h> // `uintptr_t`, `SIZE_MAX`.
#include <stdlib.h> // `realloc`.

enum {
    vec_ptr,
    vec_len,
    // The capacity is optional.
    vec_cap,
};

// Pushes the value at the end of the vec. Returns true if pushing succeeded, and false otherwise.
// Note that the vec is not automatically freed on failure.
#define vec_push(vec_expr, value_expr) ({ \
    auto vec_ = (vec_expr); \
    typeof(**vec_) value_ = (value_expr); \
    /* The end of expansions. Variable names from this point can be normal. */ \
    auto ok = true; \
    auto len = (uintptr_t)vec_len[vec_]; \
    /* A vec has capacity if it's an array of three elements. */ \
    auto has_cap = _Generic( \
        &(vec_expr), \
        typeof(*(vec_expr)) (*)[2]: false, \
        typeof(*(vec_expr)) (*)[3]: true \
    ); \
    /* If the len is either zero or a power of two, or if the vec is capped, realloc to the next power of two. */ \
    if (has_cap ? len == (uintptr_t)vec_cap[vec_] : (len & (len - 1)) == 0) { \
        auto cap = len ? len * 2 : 1; \
        /* Check for overflow. */ \
        if (cap > SIZE_MAX / sizeof **vec_ || cap <= len) ok = false; \
        else { \
            auto allocation = realloc(vec_ptr[vec_], sizeof **vec_ * cap); \
            if (allocation == nullptr) ok = false; \
            else { \
                vec_ptr[vec_] = allocation; \
                if (has_cap) vec_cap[vec_] = (typeof(vec_cap[vec_]))cap; \
            } \
        } \
    } \
    if (ok) { \
        vec_ptr[vec_][len] = value_; \
        vec_len[vec_] = (typeof(vec_len[vec_]))(len + 1); \
    } \
    ok; \
})

#endif

This seems like too much inline bloat, i.e. including the rare/slow paths.
Those should be a function call.

@jaykrell, thanks for your comment, it's quite a lot of bloat indeed. It does optimize somewhat nicely though. I tried different approaches with helper functions after seeing your comment and haven't thought of anything which I'd like, so I think I'll just leave this as is (I added some other changes though to be clear). But you're right.