Type-safe generic data structures in C

https://iafisher.com/blog/2020/06/type-safe-generics-in-c

by signa11 • 5 years ago

58 52 5 years ago

A much more simple alternative way of doing this is to use stretchy buffers.

Here's an example of a dynamic array in C in about 20 lines: http://nothings.org/stb/stretchy_buffer.txt

And here's a friendly explanation of how this technique works: https://ourmachinery.com/post/minimalist-container-library-i...

addaon• 5 years ago

But this entirely misses the "type safe" part...

tom_mellior4• 5 years ago

My understanding is that if you declare

    some_concrete_type *p;
    some_other_type x;

then, for example,

    sbpush(p, x);

will result in a type error as expected, since its core expands to:

    p[some_index] = x;

So this is kind of type safe. There is an assumption that

    ((int *) <guaranteed aligned pointer>) + 2

will still be correctly aligned for any type. That's a pretty fair assumption on modern hardware, except maybe for SIMD types.

lifthrasiir• 5 years ago

Say no to masqueraded pointers! They require a specific coding convention that can't be checked by compilers since it is effectively a linear (or affine if you are pedantic) type. Put in the other way, masqueraded pointers make many otherwise non-destructive operations destructive without you realizing.

Aanok2• 5 years ago

assert(p);
if (p) {

Do you want me to have an embolism?

tom_mellior4• 5 years ago

Haha. I was amused/bewildered by:

    void *p = realloc(...)
    // ... cast every other occurrence of p to (int *) ...

The concept may be interesting, but this particular implementation is needlessly horrible.

efficax3• 5 years ago

to be fair, if assert is removed in release code, you still have some protection with the `if`

efficax3• 5 years ago

Header only implementations of data structures are definitely the only way to accomplish type-safe generics in C, which is a great reason to avoid C! It's part of the reason why all C code bases eventually become a kind of unique, macro filled language of their own once they grow complex enough. It's not enough to know C to start working on this code, you have to know all the ins and outs of the weird macro expansions that form the boilerplate patterns and are unique to this codebase only.

Apart from being a pain in the ass to write (don't forget your escape slashes (\) for line endings!), using these macros makes debugging much harder - you no longer have a stack trace (although GDB is fairly smart about this, it's still less than ideal).

tediousdemise• 5 years ago

To add - the preprocessor is a pretty dated thing that merely uses text substitution, so you have no easy way to debug the code that the preprocessor passes to the compiler. Defines such as function-like macros throw away type safety and can have extremely unexpected behavior. For example, you might think this code will do what you want.

#define SQ(x) x*x

cout << SQ(2) // prints 4 since 2*2 = 4

cout << SQ(1+3) // prints 7 since 1+3*1+3 = 7

Macros are pretty much entirely unnecessary and should be avoided. Compilers inline nowadays, so you don’t really gain anything from using a macro when you could have just made a function that gives you type safety and intuitive behavior. If you are trying to define constants, use const, enum, or enum classes. If you are trying to define multiple versions of the same function, use polymorphism or templates. If you are trying to wrap around arbitrary code, use lambdas.

monocasa2• 5 years ago

I agree that you shouldn't be doing this stuff in production if you don't know the ends and outs of doing this idiomatically. For instance, the lack of parenthesis ala

   #define SQ(x) ((x)*(x))

set off my C spidey senses. I use them even for constants in pound defines just to be consistent.

That being said, there are benefits, like the type safety listed being one of them. No weird cast to void* and go to town on raw memory shenanigans you would have to do to use functions in intrusive collections in C.

anitil• 5 years ago

I've started moving to using python to generate what I need a lot of the time now in C. I'll either make a '.h' file, read it in and generate the boilerplate I need, or just do it using native python and emitting the C I need.

I'm never again hand-writing an my_enum_to_str routine.

Galanwe2• 5 years ago

I share your feelings, though some years ago I discovered the neat trick of "xmacros".

In a nutshell:

    #define COLOR_LIST \
      X( RED    )      \
      X( GREEN  )      \
      X( BLUE   )      \
      X( PURPLE )

    enum Color
    {
    #define X(code) code,
      COLOR_LIST
    #undef X
    };

    static const char* colorNames[] =
    {
    #define X(code) #code,
      COLOR_LIST
    #undef X
    };

You can even make it cleaner and store more metadata:

    // --- color.def
    X( RED,    "Red",   0xFF0000 )
    X( GREEN,  "Green", 0x00FF00 )
    X( BLUE,   "Blue",  0x0000FF )

    // --- color.h
    enum Color
    {
    #define X(code,name,mask) code,
    #  include "color.def"
    #endif
    };

    static const char* colorNames[] =
    {
    #define X(code,name,mask) name,
    #  include "color.def"
    #undef X
    };

    static unsigned int colorMasks[] =
    {
    #define X(code,name,mask) mask,
    #  include "color.def"
    #undef X
    };

witty_username• 5 years ago

Why would anyone use this when there is C++, Rust, etc? Genuinely curious.

macintux• 5 years ago

C is still, I have to imagine, the closest thing we have to a language available for all platforms that exist today, while C++ is heavily burdened with featuritis and Rust is limited in platform support.

bitwize2• 5 years ago

Rust is limited in platform support.

Rust supports everything you are likely to see in the wild outside of highly, highly specialized applications (e.g. ancient mainframes, satellites from the 80s or 90s, etc.).

For God's sake, it's becoming increasingly difficult to justify writing code that takes into account CPU endianness, because all CPUs that are likely to run your code are little endian!

retrac• 5 years ago

Sometimes there isn't C++ or Rust. Many embedded platforms only have a C compiler. And sometimes an existing codebase is written in C, and adding some C++ or Rust creates undesired new dependencies. See the Linux kernel debate on using those languages.

TheNewAndy2• 5 years ago

Calling C++ or Rust code from languages other than C++ or Rust respectively involved much more accidental complexity compared to calling them from C.

Even calling C++ code from compilers other than the one you were using (e.g. you are using a 3rd party precompiled library) is a risky proposition.

rurban2• 5 years ago

I favor the CTL over the STL anytime, because it compiles much faster, is much smaller, no indirect vtable calls, no bloated god objects, has no magic hooks attached, like dereferencing refs and ops, is clear on stack vs heap allocation.

The downside of course is that generics and iterators on those are a bit more troublesome, only compiler dependent goodies (mostly only clang, not gcc), like overloads or constexpr. C++ templates are ugly, and the STL is very buggy and limited. Also no security and no performance. They started on the wrong foot and had to keep it there.

Rust has an annoying syntax, but a much better library culture.

https://github.com/rurban/ctl

jcelerier4• 5 years ago

C++ templates are ugly, and the STL is very buggy and limited. Also no security and no performance.

source ? at least for performance, it seems that there's not a lot of difference from your own link:

https://raw.githubusercontent.com/rurban/ctl/master/docs/ima...

and with the stl you don't have to call

        vec_int_free(&a);

manually so I have a hard time seeing how this solution is more secure

codezero• 5 years ago

Off topic: the top of the page call to action to sign up for updates would normally be a distraction but the checkboxes that define your intended audiences make me feel like you know how important it is to keep your content targeted without being annoying. Thanks, that's cool, also you offer an alternative via RSS right in the call to action, so I'm not suspicious that you want my email for any other reason, not that I normally would, but it's become an instinct at this point :)

iafisher• 5 years ago

Author here. I wish I had made it clearer that the intent of the post was "this is an interesting and surprising thing you can achieve in C" and not "this is a good idea for a real software project" or "this is a reason to use C instead of C++/Rust/Go".

bitwize2• 5 years ago

Macros of this sort are indeed used to define stacks, queues, deques, and other generic data structures in the NetBSD (and presumably other BSDs) source code. So the pattern is used in real software projects.

anaerobicover• 5 years ago

Also OpenSSL

jcelerier4• 5 years ago

Author here. I wish I had made it clearer that the intent of the post was "this is an interesting and surprising thing you can achieve in C" and not "this is a good idea for a real software project" or "this is a reason to use C instead of C++/Rust/Go".

thanks, because from my experience edgy first year comp.sci. students will see that article and be like "see ! we don't need anything more than C!"

ganafagol• 5 years ago

By the way, the "safe" alternative in your post roughly describes how C++ started its life.

efficax3• 5 years ago

This is in fact a pretty common pattern in production code.

Here's an entire suite of type safe generic data structures in C: https://github.com/attractivechaos/klib

cperciva• 5 years ago

See also "elastic arrays":

https://github.com/Tarsnap/libcperciva/blob/master/datastruc... https://github.com/Tarsnap/libcperciva/blob/master/datastruc...

    ELASTICARRAY_DECL(STR, str, char);

creates a type "STR" and the functions str_init, str_resize, str_getsize, str_append, str_shrink, str_truncate, str_get, str_iter, str_free, str_export, and str_exportdup.

david2ndaccount• 5 years ago

A better pattern instead of declaring via a macro that expands to a large number of functions is to define the implementation in a file, require the user to #define STACK_T and then #include the file. At the bottom of the file, #undef STACK_T. As files can be included multiple times, you can do this for each generic structure you like. A sort of poor-man’s templates, that you can reasonably step through in a debugger.

Galanwe2• 5 years ago

Note that include guards become tricky then.

TheNewAndy2• 5 years ago

You don't use include guards with this pattern. See https://en.wikipedia.org/wiki/X_Macro for more.

ludocode• 5 years ago

Yes! The include style of templates in C is way better than the old way of huge macros to instantiate code. The template code can look mostly like idiomatic C, it interacts way better with a debugger, it gives better compiler errors... everything about it is better and it's finally starting to become more popular.

I've open sourced my own C template library here:

https://github.com/ludocode/pottery

Not only does it use the #include style of templates, but it actually makes the templates composable. It takes this idea pretty far, for example having a lifecycle template that lets you define operations on your type like move, copy, destroy, etc. This way the containers can fully manage the lifecycles of your types even if they're not bitwise movable.

There's also this other more popular C template library, one that tries to more directly port C++ templates to C but with a lot less features:

https://github.com/glouw/ctl/

chacham15• 5 years ago

OpenSSL does this in its STACK_OF concept: https://github.com/openssl/openssl/blob/a28d06f3e9cbc5594c79...

ginko• 5 years ago

The rise of a new generation of low-level programming languages like Rust, Go and Zig has caused C and its primitive type system to fall into some disrepute.

One of these things is not like the others. I never understood why Go, being a garbage collected language, is grouped with systems programming languages like C or Rust. If anything its direct competitors performance/productivity-wise are probably C# or Java.

frou_dh• 5 years ago

C is/was used for tons of Unix userspace programs that have no issue being written in something like Go. IMO this "systems" term has become a red herring and should be retired in favour of just naming concrete domains in a given discussion.

fulafel2• 5 years ago

I guess because it calls itself a systems language and GC works fine for most systems programming.

stkdump• 5 years ago

What is the defining characteristic of a 'systems language', and what is an example for a language that doesn't fulfill it?

mhh__2• 5 years ago

The vast majority of programs written in those languages are still relatively simple A->B things like grep or ls was when C was new. Go is a much simpler language than C# and Java - the GC isn't really the point.

Everyone likes to think, I can't use a GC for my work - I don't like garbage collection much either, but this is basically religion: it's just a tool, and it's a tool that makes programming easy.

Type-safe generic data structures in C

Related Stories