Brilliant insight. This is the first time I've seen this observation in over 3 decades of working with C.
Usually, dynamic arrays aim for amortized constant time for append and pop. This trick loses that property.
More disappointing is that libc still forces us to use the free(p) API, without a length argument, meaning we are still paying to store a(n approximation of) the length somewhere in the allocation metadata.
The capacity as bit_ceil(len) ensures that at most, half of the allocated space is wasted - excess space is O(n).
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.
I know about XOR-linked lists and a few other tricks for very efficient memory usage in embedded systems, but it's my first time seeing implicit allocation lengths.
You can use the trick if the array can shrink as long as you always shrink the allocation when length goes below the next power of 2 not greater than len (which may make use of stdc_bit_floor).
The 'public handle' is a pointer to the array elements so it has the same semantics as a regular C array, the meta-data (capacity and length) are stored directly in front of the array items. Growing the array has the same behaviour as realloc (e.g. you may get a new pointer back).
With some clever use of _Generic you could even build specialised functions for that type and get pretty good type checking
#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;Interestingly, I think my approach will work fine on CHERI, since the pointer is never dereferenced, but I didn't test this. But yeah, there are some architectures where it would fail.
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
`arr[3]` should be flagged by the compiler it is known to the compiler that you're operating on an array.
You can pass `arr` as `&arr` to functions, then compiler will know the length of the array since the type would be `T ()[2]`.
And you can then use it like this:
void f(int *(*ints)[2]) {
for (size_t i = 0; i < (size_t)vec_len[*ints]; i++) printf("f: %d\n", vec_ptr[*ints][i]);
}
A compiler will not be able to flag `vec_len[ints]` though, which is unfortunate.
However, using an 2-element array to avoid using a struct is silly.
https://github.com/gritzko/libabc/blob/main/S.md
ABC uses s[2] for slices, g[3] for gauges, b[4] for (ring) buffers. Also containers on top of those (heaps, hash sets, etc etc)
I don't like the use of uintptr_t, though. Why not storing the array begin in v[0] and a pointer to the first free item in v[1]? You avoid casts by defining len as ptrdiff_t and calculating it as v[1]-v[0].