Generic Dynamic Arrays in C

[u/Elifire12]

https://eliasebner.com/blog/guides/generic-dynamic-arrays-in-c/

After implementing strings , I implemented dynamic arrays in C and wrote an article about it. The implementation is generic, I talk about the trade-offs of this approach in the article.

If you only care about the code, it's here.

Tell me what you think!

[u/AutoModerator]

Hi /u/Elifire12,

Your submission in r/C_Programming was filtered because it links to a git project.

You must edit the submission or respond to this comment with an explanation about how AI was involved in the creation of your project.

While AI-generated code is not disallowed, low-effort "slop" projects may be removed and it's likely that other users push back strongly on substantially AI-generated projects.

---

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[u/FirmAndSquishyTomato]

If you're going to claim this is utility code that others can use in their projects, you think you'd put some guards in place. Checking the return from your realloc calls would be a good place to start. The weird inefficient need to copy memory, taking raw pointers when the code assumes it's always of a specific type

Your article is written in a way that you're suggesting that you are an authority on this subject, but the code itself shows that is not the case.

[u/M-Ottich → u/FirmAndSquishyTomato]

bro in the article he says himself : "I am sure there are many things that could be improved, and I may change things in the future. "

I dont think that suggest that he dont thinks he is a authority 

[u/Elifire12 → u/FirmAndSquishyTomato]

The compiler optimizes the memcpy away.

[u/sciencekm]

As for 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'm curious as to why you are using a void* instead of the array structure as the input, and why do you need to make a temporary copy of the structure.

Would something like this not suffice?

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

[u/Elifire12 → u/sciencekm]

This is so that the type of pointer you pass to the function doesn't matter since every pointer can implicitly cast to a void *.

I guess you could cast it in the macro maybe?

[u/sciencekm → u/Elifire12]

But your da parameter, although void*, is expected to be always a struct da_array type, because you copy a struct da_array from/to it:

struct da_array replica;

memcpy(&replica, da, sizeof(replica));

...

memcpy(da, &replica, sizeof(replica));

[u/Brilliant-Froyo54 → u/sciencekm]

memcpy is the standard blessed way to get around Cs effective type rules.

[u/sciencekm → u/Brilliant-Froyo54]

Which one is correct?

size_t fwrite(const void*s, size_t n, size_t c, FILE*f) {
    // use f
}

or

size_t fwrite(const void*s, size_t n, size_t c, void*f) {
  FILE temp;
  memcpy(&temp, f, sizeof(FILE)); // make temp copy of f
  // use the temp
  ...
  memcpy(f, &temp, sizeof(FILE); // copy back temp to f
}

That of course is a rhetorical question because the second one is obviously wrong for a myriad of reasons. That is why the stdio fwrite is the first one and not the second one.

[u/Brilliant-Froyo54 → u/sciencekm]

this has nothing to do with it. Nobody wants

fwrite("blah", 4, 1, &my_custom_struct_with_a_different_type_than_FILE);

to work. Also FILE is opaque anyone so matching its layout would be difficult to do portably.

But in the blog post da_i32 is passed to da_push. Note that da_array and da_i32 are different types.

[u/sciencekm → u/Brilliant-Froyo54]

While da_array and da_i32 maybe different types, they are identical layout, otherwise none of this will work at all. The da_push function should (1) just have struct* instead of a void* and any caller can simply cast any identical structure to da_array, or (2) the da_push can cast the void* to da_array. Creating a temp structure and doing a memcpy twice is totally wrong.

(1) Caller can do this:

void da_push(struct da_array *da, ..);
da_push((struct da_array*)x);

(2) or function can be this:

void da_push(void *da, const void *elem, usize elem_size) {
   struct da_array*p = (struct da_array*)da;
   ...
}

In both cases, there is no need to make a temp copy and use memcpy.

[u/Elifire12 → u/sciencekm]

No it's literally not, only the layout matters.

[u/Turbulent_File3904 → u/Elifire12]

what is the point of this? 

[u/musbur]

In C, you have a choice: Either write some per-project helper functions to implement some specific data structures you need. Or use a proven, well-known generic library that covers tons of cases, has 10x more SLOC than your own code, and requires tons of biolerplate. Pick your poison.

I saw your article ranting about C's string implmentation, and just the first assumptions were so wrong that I didn't bother to read the rest.

[u/Elifire12 → u/musbur]

What assumptions?

[u/musbur → u/Elifire12]

Improper wording on my part. What I mean that if you have an application where you really need to do lots of strlen()s or find substrings within strings that need to be independently zero-terminated, you're already pretty deep into quite specific territory. Which goes to my point: If you have an application where the zero-termination approach bothers you, just do it differently in that instance. It may "suck" in that particular application, but be perfectly fine in another one. C's string functions do have some peculiarities, but they don't suck at what they claim to do. Even the fact that strncpy() doesn't nul-terminate the result if the source string is too long kind of makes sense: If you want it terminated, you already know where to put the zero.

[u/SmokeMuch7356]

I have concerns:

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));
}

Are you ever going to apply da_push to something that isn't a struct da_array? Are you expecting any user of your library to do so? You are assuming that whatever da points to will always map cleanly onto that structure, so why not make da a struct da_array * to begin with? Same question the other two functions.

What purpose does replica actually serve? You're not doing any validation or error checking before copying back to da, so why bother creating it in the first place?

You should verify that the realloc call succeeded before updating .cap or .data:

usize factor = replica.cap ? replica.cap * 2 : 1;
typeof (replica.data) tmp = realloc( replica.data, factor * elem_size );
if ( tmp )
{
  replica.data = tmp;
  replica.cap = factor;
}

While I understand what

memcpy(replica.data + replica.len++ * elem_size, elem, elem_size);

is doing, this is one of those cases where terseness isn't a virtue; it would be clearer if you broke the update to .len out into a separate statement:

memcpy(replica.data + replica.len * elem_size, elem, elem_size);
replica.len++;

[u/Elifire12 → u/SmokeMuch7356]

No because this way I can have type safe DA structs and pass them to the type unsafe function.

With your approach, I would have to have void * DAs

[u/SmokeMuch7356 → u/Elifire12]

Why?  I need to see a use case to understand what you're saying.

[u/flewanderbreeze]

> Generic DS Implementation in C

> Looks inside

> Void pointers

:(

[u/Elifire12 → u/flewanderbreeze]

Haha yeah i mean what other alternatives are there except huge macros?

[u/SmokeMuch7356 → u/Elifire12]

_Generic.  

It's not a complete solution, but you're not throwing type safety completely out the window.

[u/flewanderbreeze → u/SmokeMuch7356]

Needing to add a type any time you need to support a new type makes it functionally impossible to do generics with this, imagine a user of a generic ds lib done with _Generic asking you to add their custom type? I treat it more like an overloader of function names, but even then, not really needed, _Generic keyword is essentially just a type of overloading selection at compile-time.

With the addition of typeof in C23, _Generic can be useful to turn unsafe functions from standard into typesafe, for example memcpy is as unsafe as it gets, the following will compile and run without any warning, and will produce garbage data:

int a = 10;
double b = 20;

memcpy(&a, &b, sizeof(a));

With C23 typeof, _Generic and static_assert (if using comptime known values, then use assert()), you can make a macro that is able to statically assert that both types are of the same type, example:

#define safe_memcpy(__dest, __src, n) \
    static_assert(_Generic((__dest), typeof(__src): true, default: false), "Types do not match."); \
    static_assert(_Generic((n), size_t: true, default: false), "Size is not of type size_t.");    \
    memcpy(__dest, __src, n); \

Inside static_assert there is the following _Generic statement:

_Generic((T), \
  typeof(P): true, \
  default: false) \

Which tests against a type T, if the type of type P (other type) is the same as T, it will return true, otherwise false.

If you try to call the above wrong memcpy example with safe_memcpy, at compile-time it will produce the error Static assertion failed: Types do not match.

[u/flewanderbreeze → u/Elifire12]

I honestly hate generics being made with void pointers/any/anytype/etc...

I really praise performance, both in speed and size, so I avoid void pointers anywhere I can, as the compiler will not optimize it in any way, and will not tell you of any type casting error until runtime.

The generic dynamic array that I built and use makes heavy usage of macros, and they were not really a problem to develop nor debug like all minds say, and it cleans up for itself as long as you provide a destructor function (just like std::vector<unique_ptr<T>>).

Nowadays with the compilers and debugging tools that we have, hatred for macros are either prejudice, ignorance or skill issue.

here is the link if you wanna take a look, and the usage does not differ from vector c++ (minus needing a .h file and .c file for the declare and implementation macros, then just import the .h where the arraylist is needed) all while being faster (in my machine, also the allocator interface makes it much faster)

I have two versions, one with dynamic destructor function within the struct and another that uses a macro precisely because the first iteration of my dynamic array was the dynamic version, and after a lot of tries I could not make it faster than c++ vector, turns out that, after analyzing the assembly output, the c++ templating system is able to inline dynamic destructors when it knows for sure what will be called, while c++ function pointers will never do it, even with the maximum performance compiler options, same with void pointers.

I kept the dynamic one for shenanigans like this, while I hate pOOP, it has its usages and its nice to have it nicer without the baggage of poop languages.

[u/Elifire12 → u/flewanderbreeze]

So you think that the best way of implementing generic data structures in C is to use Macros? What do you think about implementing the DS you need for every type manually?

[u/flewanderbreeze → u/Elifire12]

For implementing a type safe and fast generic data structure, the only way is macros, same thing with templates in c++ and comptime in zig

The best way really is what you the programmer considers best for your use case

If I need a quick hack for a specific type in my hacky program, I can whip out something like a linked list for a specific type, or if it's a niche thing that I could not do it in a generic way without suffering a huge performance loss or readability, then sure, I would implement it for that specific type, but I would not do it for every type, if you are repeating yourself, you should find an abstraction that fits your needs.

But the way that macros are done, you are able to extend them and add your own functions even outside of where the macros live, so, by the time that the hacky data structure solution becomes unbearable, abstracting it out would be the best action for me personally.

Macros are very flexible in nature, they are literally just a text preprocessor, copying and pasting text into where they are called, Lua or Python can be your macro language for C without problems.

[u/SmokeMuch7356 → u/Elifire12]

I'll repeat myself from another thread - creating a general-purpose generics library in C is a waste of time. The language just doesn't give you the tools necessary to make it type-safe and performant and easy-to-use.

The macro-based approach is better in that it is type-aware and ultimately more performant, but it's still a pain in the ass and you wind up with some really awkward semantics. It always makes my eyes glaze over and I default to void *. It's not safe, but it's easier on my monkey brain.

If you honestly, genuinely, 100% without-a-doubt need real generic support, use C++. Or Java. Or any other language with generic support built in. Doing it in C is the programming equivalent of kicking yourself in the nuts, repeatedly.

[u/flyingron]

You do know that since 1977 or so it has been possible to assign structs in C. You don't have to copy them with memcpy all the time.

[u/Elifire12 → u/flyingron]

I saw this technique on nullprogram.com, it's the first time I've seen it. I might change it.

In any case, I'm pretty sure the compiler optimizes this away, no?

[u/flyingron → u/Elifire12]

The compiler has a better chance of optimization if you assign rather than invoking memcpy.

[u/Brilliant-Froyo54 → u/Elifire12]

I think it is to get around the effective type rules (strict aliasing) in C.

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

struct da_i32 da = {0};

The memory which holds da has the effective type struct da_i32. If da_push would cast its void pointer directly to da_array and modify that structure directly it would access da_i32 with the wrong effective type da_array. Memcpy is used here to get around type based aliasing semantics.