10 ms·
A generic dynamic array in C that stores no capacity and needs no struct
- senderista 3mo agoThis is just silly. You can't even reserve capacity because you only store size and capacity is implicitly the next power of 2 >= size.
- sparkie 3mo agoThe 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.
- teo_zero 3mo agoClever! 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].
- t-3 3mo agoNo 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.
- alurm 3mo agoGood point! Added `vec_ptr[vec]` and `vec_len[vec]` helpers to mitigate this somewhat.
- hibberl7 3mo ago[dead]
- sparkie 3mo agoThe 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; } We can use `Array(int)` in multiple places in the same TU - but in C11 or earlier, this is an error.
- gritzko 3mo agohttps://github.com/gritzko/libabc/blob/main/Sx.h https://github.com/gritzko/libabc/blob/main/Sx.h https://github.com/gritzko/libabc/blob/main/S.md 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)
- userbinator 3mo agocapacity 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.
- alurm 3mo agoThank 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. :)
- sparkie 3mo agoReally? It's been done plenty and I thought was quite common knowledge. Some of the <stdbit.h> 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.
- astrobe_ 3mo agoI 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.
- userbinator 3mo agoNo, I'm being serious. 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.
- OskarS 3mo agoEveryone knows about bit-fiddling functions, what the poster was referring to is using this trick to not have to store the capacity for a dynamic vector. Which is genuinely very clever and rare, I don’t think I’ve ever seen it done quite like this either. I think that’s probably because it’s not really that good of an idea, if the vector can shrink, you really should store the capacity.
- Akronymus 3mo agoThat's pretty clever code. Too clever for my tastes.
- deleted 3mo ago[deleted]
- deleted 3mo ago[deleted]
- dooglius 3mo agoStrictly speaking, the capacity is still stored internally to the allocation (it needs to be, in order to implement realloc)
- rurban 3mo agoYou don't, as the capacity is always the next power of 2 of the length.
- dooglius 3mo agoIf 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).
- lefra 3mo agoEnjoy 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.
- alurm 3mo agoYeah, 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 < (size_t)vec_len[*ints]; i++) printf("f: %d\n", vec_ptr[*ints][i]); } Curiously, this is a rare case where the "inverted" `a[b]` requires less typing compared to `(b)[a]`. A compiler will not be able to flag `vec_len[ints]` though, which is unfortunate.
- deleted 3mo ago[deleted]
- dwroberts 3mo ago> 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
- sparkie 3mo agoIf you use a struct with a `void*`, you also need to specify the type on usage, where here it's done with `typeof`.
- procaryote 3mo agoWhy 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
- sparkie 3mo agoIn 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; C23 has relaxed rules for redefining the same struct, so we can avoid having to create the struct up front. #define Array(T) struct array_##T { size_t len; T *elems; } Array(int) foo; Array(int) bar;
- flohofwoe 3mo agoThe 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).
- alurm 3mo agoThanks for mentioning it, I've heard about stb, but this time around I actually looked at the code. Their approach is very nice.
- layer8 3mo agoThe 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.
- alurm 3mo agoYou'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.