The C standard doesn’t guarantee that arbitrary integer values converted to a pointer and back result in the same integer values again. It only guarantees the other direction, that a valid pointer to void, when converted to uintptr_t and back again, will result in a pointer that compares equal to the original. The conversion from uintptr_t to pointer may for example clear or truncate some of the bits of the integer value, or normalize it in some other way.
A generic dynamic array in C that stores no capacity and needs no struct
31–38 of 38 posts
Re: A generic dynamic array in C that stores no capacity and needs no struct
#32Strictly speaking, the capacity is still stored internally to the allocation (it needs to be, in order to implement realloc)
You don't, as the capacity is always the next power of 2 of the length.
If you were to implement your own realloc for the purpose of this data structure, you could do that. However, a generic realloc implementation needs to know how many bytes to copy, and generally that means storing the capacity just in front of the allocated region. I don't think there is another feasible way. On e.g. glibc, you can use `malloc_usable_size` to extract this information (modulo certain caveats).
Re: A generic dynamic array in C that stores no capacity and needs no struct
#33Clever!
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].
Re: A generic dynamic array in C that stores no capacity and needs no struct
#34The most idiomatic and elegant 'dynamic array in C' solution is stb_ds.h, it's as simple as that :) 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).
Thanks for mentioning it, I've heard about stb, but this time around I actually looked at the code. Their approach is very nice.
Re: A generic dynamic array in C that stores no capacity and needs no struct
#35No 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.
Good point! Added `vec_ptr[vec]` and `vec_len[vec]` helpers to mitigate this somewhat.
Re: A generic dynamic array in C that stores no capacity and needs no struct
#36The C standard doesn’t guarantee that arbitrary integer values converted to a pointer and back result in the same integer values again. It only guarantees the other direction, that a valid pointer to void , when converted to uintptr_t and back again, will result in a pointer that compares equal to the original. The conversion from uintptr_t to pointer may for example clear or truncate some of the bits of the integer…
You're right, I added some more clarity in the README.
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.
Re: A generic dynamic array in C that stores no capacity and needs no struct
#37capacity 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.
Thank you! I implemented this pattern initially about a year ago, but decided to write about it now. Since you liked it, it wasn't for nothing. :)
Re: A generic dynamic array in C that stores no capacity and needs no struct
#38Enjoy 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.
Yeah, I've added macros `vec_len` and `vec_ptr` (or, enums, actually), which help somewhat.
`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 A compiler will not be able to flag `vec_len[ints]` though, which is unfortunate.