5 ms·
Generic Containers in C: Vec
- uecker 1y agoTowards safe containers in C.
- rwmj 1y agoHere's a generic vector used in real world code: https://gitlab.com/nbdkit/nbdkit/-/blob/master/common/utils/vector.h?ref_type=heads https://gitlab.com/nbdkit/nbdkit/-/blob/master/common/utils/...
- senderista 1y agoI doubt I'd want to use a dynamic array in C without a custom allocator.
- teo_zero 1y agoYou don't need an explicit allocator: you can create an empty object and vec_push() does the magic of (re)allocating the memory when needed. Instead, what is missing is an automatic deallocator, one that's automatically called when the variable goes out of scope. For example: { vec(int) v={}; /* no extra room allocated */ vec_push(v,1); /* space allocated */ ... use v ... } /* here the space is dellocated, then v is released */ This example doesn't use the same definition of vec as TFA, but something more similar to 'span' by the same author.
- uecker 1y agoAnd you could easily add a version with a custom allocator if you need it.
- cv5005 1y agoAnd if I want a vec(int *)? These token pasting 'generic' macros never work for non-trivial types.
- teo_zero 1y agoCorrect, complex types must be typedef'd. At least, until c2y integrates _Record as per N3332: https://thephd.dev/_vendor/future_cxx/papers/C%20-%20_Record%20types.html https://thephd.dev/_vendor/future_cxx/papers/C%20-%20_Record...
- uecker 1y agoI am not terribly excited about this proposal. It is overly complex.
- teo_zero 1y agoI agree, but the current specification is complex too: two identical "tagged" structs are compatible, two identical "untagged" structs are not. And before C23 it was even worse, depending on whether the two structs were defined in the same file or not. We're applying a patch over a patch over a patch... no surprise the end result looks like a patchwork!
- uecker 1y agoSure, but _Record would add even more complexity. The tag rules I had changed in C23 were a step to remove complexity, so a step towards cleaning it up. I wasn't able to fix the untagged case, because WG14 had concerns, but I think these can be addressed, making another step. It is always much harder to undo complexity than to add it.
- hyperbolablabla 1y agoI think the overwhelmingly better approach for C is codegen here. Better ergonomics, tab completion, less error prone, etc. As long as your codegen is solid!
- uecker 1y agoWhy? I do not find the ergonomics bad. It is also not clear how you get tap completion with code generation. But you could also get tab completion here, somebody just has to add this to the tab completion logic.
- deleted 1y ago[deleted]
- teo_zero 1y agoWhy do you need to pass the type to vec_push? Can't T be replaced by typeof(v->data[0]) ?
- uecker 1y agoIt could. I like things being spelled out explicitly. Otherwise I would probably not use C.
- camel-cdr 1y agoHere is my version of this concept, I tried to keep it as simple as possible: https://github.com/camel-cdr/cauldron/blob/main/cauldron/stretchy-buffer.h https://github.com/camel-cdr/cauldron/blob/main/cauldron/str...
- petters 1y ago> Many vector types include a capacity field, so that resizing on every push can be avoided. I do not include one, because simplicity is more important to me and realloc often does this already internally. In most scenarios, the performance is already good enough. I think this is the wrong decision (for a generic array library).
- tialaramex 1y ago> realloc often does this already internally Is Martin claiming that realloc is "often" maintaining a O(1) growable array for us? That's what the analogous types in C++ or Rust, or indeed Java, Go, C# etc. provide.
- uecker 1y agoNo, I claim that the performance of realloc is good enough for most use cases because it also does not move the memory in case there is already enough space left. I then mention that for other use cases, you can maintain a capacity field only in the part of the code where you need this. Whether this is the right design for everybody, I do not know, but so far it is what I prefer for myself.
- tialaramex 1y agoI think the claim that it's good enough for "most use cases" to have an O(n) growable array container needs some serious backing data.
- eps 1y agoThe post is more of a quick-n-dirty (and rather trivial) proof of concept as the code includes only sporadical checks for allocation errors and then adds a hand-wavy disclaimer to improve it as needed. E.g. in production code this if (!vec_ptr) // memory out abort(); for (int i = 0; i < 10; i++) vec_push(int, &vec_ptr, i); should really be if (!vec_ptr) // memory out abort(); for (int i = 0; i < 10; i++) if (! vec_push(int, &vec_ptr, i)) abort(); but it doesn't really roll of the tongue.
- uecker 1y agoIf all you do is call abort anyway, you do not need an interface that makes you test for errors.
- johnisgood 1y agoIf this is in a library code, then I tend to disagree. As an user of a library, I would rather be able to handle errors the way I want, I do not want the library to decide this for me, so just return an error value, like "VEC_ERR_NOMEM", or whatever.
- gsliepen 1y agoIt's amazing how many people try to write generic containers for C, when there is already a perfect solution for that, called C++. It's impossible to write generic type-safe code in C, and this version resorts to using GCC extensions to the language (note the ({…}) expressions). For those afraid of C++: you don't have to use all of it at once, and compilers have been great for the last few decades. You can easily port C code to C++ (often you don't have to do anything at all). Just try it out and reassess the objections you have.
- serbuvlad 1y agoMy problem with C++, and maybe this is just me, is RAII. Now, Resource Aquisition Is Initialization is correct, but the corollary is not generally true, which is to say, my variable going out of scope does not generally mean I want to de-aquire that resource. So, sooner or later, everything gets wrapped in a reference counting smart pointer. And reference counting always seemed to me to be a primitive or last-resort memory managment strategy.
- secondcoming 1y agoIf you want to take back manual control, use the release() function
- gpderetta 1y agoYour problem is not with RAII, but with reference counting, which you correctly identified should be the last resort, not the default; at least for the applications typically written in C++.
- Levitating 1y agoWhy should reference counting be a last resort?
- rurban 1y agoBecause it's insanely slow, and doesn't support cyclic structures.
- jll29 1y agoThe authoritative treatise of this topic is "C - Interfaces and Implementations" (known as CII) by David R. Hanson. His code is here: https://github.com/drh/cii https://github.com/drh/cii
- cyber1 1y agoMany C programmers need proper generic programming mechanisms (perhaps something like Zig's comptime) in C, but macros are the worst possible approach, and they don't want to switch to a different language like C++. As a result, they struggle with these issues. This is what I think the standardization committee should focus on, but instead, they introduced _Generic.
- uecker 1y agoI don't struggle, I switch from C++ to C and find this much nicer.
- cyber1 1y agoI'm currently at a crossroads: C++ or Zig. One is very popular with a large community, amazing projects, but has lots of ugly design decisions and myriad rules you must know (this is a big pain, it seems like even Stroustrup can't handle all of them). The other is very close to what I want from C, but it's not stable and not popular.
- uecker 1y agoWhy not C? Its only real issue is that people will constantly tell you how bad it is and how their language of choice is so much better. But if you look at how things work out in practice, you can usually do things very nicely in C.
- mananaysiempre 1y agoMy choice in this situation is indeed C, but every once in a while I hit a problem that makes me yearn for better metaprogramming. Perfect hashing that you’d ideally use two different approaches for depending on whether the platform has a cheap popcount (hi AArch32), but to avoid complicating the build you give up and emulate popcount instead. Hundreds of thousands of lines of asynchronous I/O code written in a manual continuation-passing style, with random, occasionally problematic blocking synchronization sprinkled all over because the programmer simply could not be bothered anymore to untangle this nested loop, and with a dynamic allocation for each async frame because that’s the path of least resistance. The intense awkwardness of the state-machine / regular-expression code generators, well-developed as they are. Hoping the compiler will merge the `int` and `long` code paths when their machine representations are identical, but not seeing it happen because functions must have unique addresses. Resorting to .init_array—and slowing down startup—because the linker is too rigid to compute this one known-constant value. And yes, polymorphic datastructures. I don’t really see anybody do noticeably better than C; I think only Zig and Odin (perhaps also Hare and Virgil?) are even competing in the same category. But I can’t help feeling that things could be much better. Then I look at the graveyard of attempted extensions both special-purpose (CPC[1]) and general (Xoc[2]) and despair. [1] https://github.com/kerneis/cpc https://github.com/kerneis/cpc [2] https://pdos.csail.mit.edu/archive/xoc/ https://pdos.csail.mit.edu/archive/xoc/
- mashpoe 1y agoI made a pretty convenient C vector library a while back that lets you use the [] operator directly on the vector pointers: https://github.com/Mashpoe/c-vector https://github.com/Mashpoe/c-vector A neat project that was posted here a while back uses it: https://x.com/kotsoft/status/1792295331582869891 https://x.com/kotsoft/status/1792295331582869891
- itay2805 1y agoBy far the best implementation for type-safe containers in C I found is stb_ds, it provides both a vector and a hashmap (including a string one). https://nothings.org/stb_ds https://nothings.org/stb_ds
- lor_louis 1y agoI do something similar, but I don't implement the logic in a macro, instead I have a Vec struct which looks like struct Vec { void *data; size_t len; size_t cap; size_t sizeof_ty; } I then use a macro to define a new type IntVec { struct Vec inner; int ty[0]; } Using the zero sized filed I can do typeof(*ty) to get some type safety back. All of the methods are implemented on the base Vec type and have a small wrapper which casts/assets the type of the things you are trying to push.
- codr7 1y agoFrom my experience, trying to make C type safe is counter productive. It's perfectly possible to do generic vectors in C without twisting the language. This implementation isn't as safe as alternatives in other languages, but plays well on C's strengths. https://github.com/codr7/hacktical-c/tree/main/vector https://github.com/codr7/hacktical-c/tree/main/vector
- uecker 1y agoWhy would you think this? My implementation is type and bounds safe and nice to use.
- codr7 1y agoBecause that level of (type) safety and C is a bad fit.
- uecker 1y agoI assume you do not want to elaborate why you think it is a "bad fit". IMHO it is perfect.
- codr7 1y agoBecause you're using the pre-processor to create a new language, which we have pretty much agreed is a bad idea. If you want that level of safety, why not use a language that provides it for you?
- mwkaufma 1y agoAn important property of C++ templates is that their instantiations are de-duplicated at link-time. If you have two dependencies in C which both use the same generic container macros, and both instantiate vec(int) you'll fail-out with redefinition errors.
- minroot 1y agoWhy just copy the code by yourself?
- tom_ 1y agoWhat is an array? It's 3 variables: base, length and capacity. So why not decide that an array is just that. 3 variables of the right size and type. #define ARRAY(T,S) T S;size_t S##_length;size_t S##_capacity Then you can make one like this: ARRAY(int,xs); You'll also need to initialise and these destroy array "objects". #define ARRAY_INIT(S) \ do { \ S=NULL; \ (S##_length)=0; \ (S##_capacity)=0; \ } while(0) #define ARRAY_DESTROY(S) \ do { \ Array_Free(S); \ ARRAY_INIT(S); \ } while(0) Add you'll probably want to add an item to an array too. #define ARRAY_ADD(S,X) \ do { \ if((S##_length)>=(S##_capacity)) { \ S=Array_Grow(S, \ sizeof *S, \ &(S##_length), \ &(S##_capacity)); \ } \ S[S##_length++]=(X); \ } while(0) So you might use them like this: ARRAY(int,xs); ARRAY_INIT(xs); for(int i=0;i<100;++i) ARRAY_ADD(xs,i); ARRAY_DESTROY(xs); Array_Free is very simple, and Array_Grow is barely more complicated (however I wrote it off the cuff, so of course it could still be wrong). Both of these mainly exist just to keep stdlib.h out of the header. void Array_Free(void *p) { free(p); } void *Array_Grow(void *base,size_t stride,size_t *length,size_t *capacity) { *capacity+=*capacity/2; *capacity=MAX(*capacity,MAX(MIN_CAPACITY,*length)); return realloc(base,*capacity*stride); } Array accesses and iteration and the like are just done in the traditional way. Even performs nicely with -O0. for(size_t i=0;i<xs_length;++i) { printf("%d\n",xs[i]); } You might want to hide the size naming policy behind a macro: #define ARRAY_LENGTH(S) (S##_length) But it'd often be shorter just to type the name out. (On the other hand, if attempting to fully productize this, maybe it'd be nice to let the consumer customize the naming convention - and now you'd have the option. ARRAY_LENGTH would hide the details, you'd fix up ARRAY_ADD (etc.) to use it, and now you could have the size variable called arraySize (or whatever) and everything would fall into line.) For a full implementation you'll probably also need a way of generating a static array. (I mainly found myself needing this for test code, which uses globals for convenience; most arrays I create normally are locals, or parts of structs.) You'll also need a parameters list for use in a function declaration or definition, and a macro that expands to all 3 variables. #define ARRAY_PARAMS(T,S) T *S,size_t S##_length,size_t S##_capacity #define ARRAY_ARG(S) S,S##_length,S##_capacity Like then you might have a function that takes a pointer to an "array": void FunctionThatTakesAnArray(ARRAY_PARAMS(T,*p)); And you call it like this: ARRAY(T,myarray); FunctionThatTakesAnArray(ARRAY_ARG(&myarray)); (I found this cropped up often enough that I needed the macro, but it was less common than I thought.) There's more you can do, but the above is the long and the short of it. This might all look terrible - or perhaps it sort of looks OK, but you're just not sure that it would actually work - but I've used this in a prototype project and thought it worked out well. (I mainly do C++ nowadays, but I had a good stint of C before that. So even if I've got no taste, hopefully I've at least got a rough feel for what'll work out OK and what'll end up a disaster.)