Generic Containers in C: Vec (uecker.codeberg.page)

Towards safe containers in C.

Here's a generic vector used in real world code: https://gitlab.com/nbdkit/nbdkit/-/blob/master/common/utils/...

I doubt I'd want to use a dynamic array in C without a custom allocator.

And if I want a vec(int *)? These token pasting 'generic' macros never work for non-trivial types.

I think the overwhelmingly better approach for C is codegen here. Better ergonomics, tab completion, less error prone, etc. As long as your codegen is solid!

Why do you need to pass the type to vec_push? Can't T be replaced by typeof(v->data[0]) ?

Here is my version of this concept, I tried to keep it as simple as possible: https://github.com/camel-cdr/cauldron/blob/main/cauldron/str...

> Many vector types include a capacity field, so that resizing on every push can be avoided. I do not include one, because simplicity is more important to me and realloc often does this already internally. In most scenarios, the performance is already good enough.

I think this is the wrong decision (for a generic array library).

The post is more of a quick-n-dirty (and rather trivial) proof of concept as the code includes only sporadical checks for allocation errors and then adds a hand-wavy disclaimer to improve it as needed.

E.g. in production code this

  if (!vec_ptr) // memory out
    abort();

  for (int i = 0; i < 10; i++)
    vec_push(int, &vec_ptr, i);

should really be

  if (!vec_ptr) // memory out
    abort();

  for (int i = 0; i < 10; i++)
    if (! vec_push(int, &vec_ptr, i))
      abort();

but it doesn't really roll of the tongue.

It's amazing how many people try to write generic containers for C, when there is already a perfect solution for that, called C++. It's impossible to write generic type-safe code in C, and this version resorts to using GCC extensions to the language (note the ({…}) expressions).

For those afraid of C++: you don't have to use all of it at once, and compilers have been great for the last few decades. You can easily port C code to C++ (often you don't have to do anything at all). Just try it out and reassess the objections you have.

Many C programmers need proper generic programming mechanisms (perhaps something like Zig's comptime) in C, but macros are the worst possible approach, and they don't want to switch to a different language like C++. As a result, they struggle with these issues. This is what I think the standardization committee should focus on, but instead, they introduced _Generic.

The authoritative treatise of this topic is "C - Interfaces and Implementations" (known as CII) by David R. Hanson.

His code is here: https://github.com/drh/cii

I made a pretty convenient C vector library a while back that lets you use the [] operator directly on the vector pointers: https://github.com/Mashpoe/c-vector

A neat project that was posted here a while back uses it: https://x.com/kotsoft/status/1792295331582869891

By far the best implementation for type-safe containers in C I found is stb_ds, it provides both a vector and a hashmap (including a string one).

https://nothings.org/stb_ds

I do something similar, but I don't implement the logic in a macro, instead I have a Vec struct which looks like

    struct Vec {
        void *data;
        size_t len;
        size_t cap;
        size_t sizeof_ty;
    }

I then use a macro to define a new type

    IntVec {
        struct Vec inner;
        int ty[0];
    }

Using the zero sized filed I can do typeof(*ty) to get some type safety back.

All of the methods are implemented on the base Vec type and have a small wrapper which casts/assets the type of the things you are trying to push.

From my experience, trying to make C type safe is counter productive.

It's perfectly possible to do generic vectors in C without twisting the language. This implementation isn't as safe as alternatives in other languages, but plays well on C's strengths.

https://github.com/codr7/hacktical-c/tree/main/vector

An important property of C++ templates is that their instantiations are de-duplicated at link-time.

If you have two dependencies in C which both use the same generic container macros, and both instantiate vec(int) you'll fail-out with redefinition errors.

Why just copy the code by yourself?

What is an array? It's 3 variables: base, length and capacity. So why not decide that an array is just that. 3 variables of the right size and type.

    #define ARRAY(T,S) T S;size_t S##_length;size_t S##_capacity

Then you can make one like this:

    ARRAY(int,xs);

You'll also need to initialise and these destroy array "objects".

    #define ARRAY_INIT(S)     \
        do {                  \
            S=NULL;           \
            (S##_length)=0;   \
            (S##_capacity)=0; \
        } while(0)

    #define ARRAY_DESTROY(S) \
        do {                 \
            Array_Free(S);   \
            ARRAY_INIT(S);   \
        } while(0)

Add you'll probably want to add an item to an array too.

    #define ARRAY_ADD(S,X)                     \
        do {                                   \
            if((S##_length)>=(S##_capacity)) { \
                S=Array_Grow(S,                \
                             sizeof *S,        \
                             &(S##_length),    \
                             &(S##_capacity)); \
            }                                  \
            S[S##_length++]=(X);               \
        } while(0)

So you might use them like this:

    ARRAY(int,xs);
    ARRAY_INIT(xs);
    for(int i=0;i<100;++i)
        ARRAY_ADD(xs,i);
    ARRAY_DESTROY(xs);

Array_Free is very simple, and Array_Grow is barely more complicated (however I wrote it off the cuff, so of course it could still be wrong). Both of these mainly exist just to keep stdlib.h out of the header.

    void Array_Free(void *p) {
        free(p);
    }

    void *Array_Grow(void *base,size_t stride,size_t *length,size_t *capacity) {
        *capacity+=*capacity/2;
        *capacity=MAX(*capacity,MAX(MIN_CAPACITY,*length));
        return realloc(base,*capacity*stride);
    }

Array accesses and iteration and the like are just done in the traditional way. Even performs nicely with -O0.

    for(size_t i=0;i<xs_length;++i) {
        printf("%d\n",xs[i]);
    }

You might want to hide the size naming policy behind a macro:

    #define ARRAY_LENGTH(S) (S##_length)

But it'd often be shorter just to type the name out. (On the other hand, if attempting to fully productize this, maybe it'd be nice to let the consumer customize the naming convention - and now you'd have the option. ARRAY_LENGTH would hide the details, you'd fix up ARRAY_ADD (etc.) to use it, and now you could have the size variable called arraySize (or whatever) and everything would fall into line.)

For a full implementation you'll probably also need a way of generating a static array. (I mainly found myself needing this for test code, which uses globals for convenience; most arrays I create normally are locals, or parts of structs.)

You'll also need a parameters list for use in a function declaration or definition, and a macro that expands to all 3 variables.

    #define ARRAY_PARAMS(T,S) T *S,size_t S##_length,size_t S##_capacity
    #define ARRAY_ARG(S) S,S##_length,S##_capacity

Like then you might have a function that takes a pointer to an "array":

    void FunctionThatTakesAnArray(ARRAY_PARAMS(T,*p));

And you call it like this:

    ARRAY(T,myarray);
    FunctionThatTakesAnArray(ARRAY_ARG(&myarray));

(I found this cropped up often enough that I needed the macro, but it was less common than I thought.)

There's more you can do, but the above is the long and the short of it.

This might all look terrible - or perhaps it sort of looks OK, but you're just not sure that it would actually work - but I've used this in a prototype project and thought it worked out well. (I mainly do C++ nowadays, but I had a good stint of C before that. So even if I&#x...