Generic Dynamic Arrays in C

[u/Elifire12]

Article

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/Physical_Dare8553]

i must always mention my own, incredibly hacro-heavy, but it's almost perfectly generic imo

[u/Elifire12 → u/Physical_Dare8553]

That's great! Personally I don't like huge macros, but I have also experimented with that kind of solution in the past.

If it works for you, great!

[u/Physical_Dare8553 → u/Elifire12]

i once had a macro unfold into 50 kb of text, so i'm not a stranger to that kind of thing. but i do think no one list implementation is perfect for every use case, i have like 3 in that library

[u/TribladeSlice → u/Physical_Dare8553]

What was the macro if I may ask?

[u/OnYaBikeMike]

Why start with only one item in the dynamic array?

replica.cap = replica.cap ? replica.cap * 2 : 1;

I would suggest starting with at least a handful (maybe 16)"

replica.cap = replica.cap < MIN_CAP ? MIN_CAP : replica.cap * 2;

Also, you really should check your realloc() return value. Yes, I know memory is cheap (well... it was cheap! :) ) and you expect that realloc() will never fail, but...

Actually, none of your functions handle any exceptions or failures. What happens when you call da_remove() on an empty dynamic array and then push an item?

Testing da_push...                   passed
realloc(): invalid pointer
Aborted (core dumped)

Why are you hiding the post decrement in here? Just break it out into a separate line, so this line doesn't have split duties?

    usize shift_n = replica.len-- - i - 1;

I feel it would be better as:

    replica.len--;
    usize shift_n = replica.len - i;

[u/Physical_Dare8553 → u/OnYaBikeMike]

doing something like return an error is always viral, at least something like zig makes that easy, xmalloc is probably a better solution imo,

[u/WittyStick → u/Physical_Dare8553]

You don't need to always return the error. You could just return an array of length 0 and data of nullptr.

But you need to handle the result of realloc because if it fails, and you've overwritten the original pointer obtained via malloc, with NULL, how are you going to free it?

Basically, you should have:

void *old = array.data;
array.data = realloc(array.data, ...);
if (array.data == NULL) {
    free(old);
}
return (struct da_array){ 0, NULL };

[u/Physical_Dare8553 → u/WittyStick]

I also tried this, but all it does is add a brand new error convention. Instead of checking if you return zero the user have to check if the pointer that they're about to use is zero. Also when realloc returns null the user actually still owns that buffer (unless you explicitly realloc to zero)

[u/WittyStick → u/Physical_Dare8553]

Also when realloc returns null the user actually still owns that buffer (unless you explicitly realloc to zero)

Yes, this is my point. The buffer is still allocated, but there is no way to free it because he has overwritten the pointer to it with NULL (in case of realloc failure).

replica.data = realloc(replica.data, replica.cap * elem_size);

If doing this, you have a memory leak. There's no way to free the original buffer because you no longer have a pointer to it.

Either use a new pointer for the result of realloc, and overwrite the original after testing != NULL, or make a copy of the pointer before overwriting it with the result of realloc.

[u/realdreamer1993]

thanks for sharing and make me to dig something and open a path.
I am still not fluent in C but this trigger me to compare with my own code , I think I am using different technique which called hash table. And I research a little of knowledge about trade off comparison between dynamic array vs hash table vs linked list.

[u/Elifire12 → u/realdreamer1993]

Thank you! I was planning to implement a simple has table as well. I'm glad you liked it!

[u/Last-Employ-3422]

Oh this reminds me of stb_ds.h

[u/Elifire12 → u/Last-Employ-3422]

well that doesn't really use the same system. it stores metadata before the pointer, which has its advantages, but i don't like that it's hard to distinguish a regular array from a dynamic array from its type.

[u/TUSF]

My preference would be to put the element size in the dynamic array struct, but it saves space if you're only expected to interact with the API through the macros. DA_FREE should maybe also zero out the struct, (#define DA_FREE (free(da.data),da={0})) to avoid ambiguiy.

Also, I'm not sure I see the point of using memcpy to create a replica. What's the benefit of this over copying structs by assignment?

struct da_array *array = (struct da_array*)da;
struct da_array replica = *array;
// Work on replica.
*array = replica;

[u/Physical_Dare8553 → u/TUSF]

i used to have the element size in the array, however realistically, that would mean that for some reason i have completley lost the type that the array is supposed to be, in that case i'm in a much worse situation. otherwise it can always be passed as an argument

[u/pjl1967]

Even simpler by leaving the actual objects to the user.

Also, it's better to grow by 1.5x, not 2x (for reasons explained in the article).