Enjoy the annoying-to-debug errors when someone inevitably mixes arr[0] with arr[1] and tramples the heap (this could be mitigated by accessing the fields with macros), or writes arr[3] because they forgot this is not a regular array.
A generic dynamic array in C that stores no capacity and needs no struct
11–20 of 38 posts
Re: A generic dynamic array in C that stores no capacity and needs no struct
#12capacity isn't stored at all. Instead, it's computed on demand when the length of the vec is either zero or a power of two. Brilliant insight. This is the first time I've seen this observation in over 3 decades of working with C.
Really? It's been done plenty and I thought was quite common knowledge. Some of the provided functions are basically for this purpose.
stdc_bit_ceil(len) gets the smallest power of 2 not less than len, which is our capacity. This is usually implemented with a clz instruction.
stdc_has_single_bit(len) determines if it's a power of 2 - typically implemented with a popcount instruction (popcount(len)==1).
The approach isn't used in older (90s and earlier) texts because hardware support for popcount/clz wasn't commonplace and the cost to do it in software wasn't worth it, but it is mentioned in some texts.
Re: A generic dynamic array in C that stores no capacity and needs no struct
#13> First of all, structs aren't used so you don't have to invent names for them (e.g. there is no IntVec)
But since it’s storing a void pointer any way, they wouldn’t need separate names right? You could use one struct everywhere regardless of the type of the items
Which IMO is a better idea than using an array here because the fields can be properly named and typed to prevent accidental misuse
Re: A generic dynamic array in C that stores no capacity and needs no struct
#14Enjoy the annoying-to-debug errors when someone inevitably mixes arr[0] with arr[1] and tramples the heap (this could be mitigated by accessing the fields with macros), or writes arr[3] because they forgot this is not a regular array.
[deleted]
Re: A generic dynamic array in C that stores no capacity and needs no struct
#15This is just silly. You can't even reserve capacity because you only store size and capacity is implicitly the next power of 2 >= size.
The concept of not storing capacity isn't silly. If you need to reserve space then it's not the appropriate structure, but it's otherwise fine.
However, using an 2-element array to avoid using a struct is silly.
Re: A generic dynamic array in C that stores no capacity and needs no struct
#16Why would you want to avoid using a struct? Add a macro that declares the appropriate struct and get at least a tiny bit of type checking.
With some clever use of _Generic you could even build specialised functions for that type and get pretty good type checking
Re: A generic dynamic array in C that stores no capacity and needs no struct
#17capacity isn't stored at all. Instead, it's computed on demand when the length of the vec is either zero or a power of two. Brilliant insight. This is the first time I've seen this observation in over 3 decades of working with C.
Really? It's been done plenty and I thought was quite common knowledge. Some of the provided functions are basically for this purpose. stdc_bit_ceil(len) gets the smallest power of 2 not less than len, which is our capacity. This is usually implemented with a clz instruction. stdc_has_single_bit(len) determines if it's a power of 2 - typically implemented with a popcount instruction (popcount(len)==1). The approach i…
I think it was sarcasm. I have about as much experience as them in low-level C programming, and I was wondering why this is on front page. I've also discovered again a few things too, so I won't look down on OP. It's certainly better than vibe coding.
Re: A generic dynamic array in C that stores no capacity and needs no struct
#18No structs, just an array that accomplishes the same thing, without field names or other niceties. Enjoy the pleasure of not using a struct when you inevitably add/reduce/reorder fields later.
[dead]
The reason the struct is avoided here is so the array can be typed to its element type (rather than casting to and from `void*`).
With a struct we would need one struct for each element type - at least prior to C23 which provides a better approach where we can declare the same struct multiple times in a translation unit.
#define Array(T) struct array_##T { size_t len; T *elems; }
Re: A generic dynamic array in C that stores no capacity and needs no struct
#19Why would you want to avoid using a struct? Add a macro that declares the appropriate struct and get at least a tiny bit of type checking. With some clever use of _Generic you could even build specialised functions for that type and get pretty good type checking
In C23 this approach is nice, but in older versions of C we end up with awful macros where we need to define the structure before we use it.
#define Array(T) struct array_##T
#define DEFINE_ARRAY(T) struct array_##T { size_t len; T *elems; }
DEFINE_ARRAY(int);
Array(int) foo;
Array(int) bar;
#define Array(T) struct array_##T { size_t len; T *elems; }
Array(int) foo;
Array(int) bar;Re: A generic dynamic array in C that stores no capacity and needs no struct
#20> First of all, structs aren't used so you don't have to invent names for them (e.g. there is no IntVec) But since it’s storing a void pointer any way, they wouldn’t need separate names right? You could use one struct everywhere regardless of the type of the items Which IMO is a better idea than using an array here because the fields can be properly named and typed to prevent accidental misuse
If you use a struct with a `void*`, you also need to specify the type on usage, where here it's done with `typeof`.