Type Safe Generic Data Structures in C

(danielchasehooper.com)

93 points | by AlexeyBrin 2 days ago

8 comments

  • Panzerschrek 1 hour ago
    I don't understand people reinventing macro-based hacks in C to achieve what was achieved in other languages many years ago. Why not using C++, for example? It's available almost everywhere, introducing its usage in an existing C codebase is pretty simple. Sure, C++ has its own downsides, but is it better to create mess with macros in C rather then using exiting language facilities and standard library containers provided by C++?
    • uecker 44 minutes ago
      Having used C++ a lot in the past, I think the mess in C++ is way worse. I also contribute to projects that introduce C++ into a C code base, and I really wish they hadn't done this.

      Although there are C features I like that I would need to remove before introducing C++ to a codebase, so this may not always be so simple.

    • rwbt 51 minutes ago
      I'd rather not migrate my C codebase to C++ just to use an array container. Very hard to consistently limit the codebase to a strict subset of C++.
      • pjmlp 36 minutes ago
        It is called a linter, more devs should learn to use a tool that was originally created for C in 1979.
        • accelbred 0 minutes ago
          The only decent linters I know of for C++ are clang-tidy and coverity and they are not good enough.
    • Joker_vD 1 hour ago
      For one reason, it is because C++ runtime (and its standard library) is a whole own can of worms which most people would rather not touch if they can afford to. Which they mostly can.

      > Sure, C++ has its own downsides

      "Sure, getting your eyes gouged out has its downsides, but is it better to read that awful mess of macros in C instead?" The answer most people would give to this question may surprise you.

      • kccqzy 53 minutes ago
        Here we go again. Yes there are bad parts in the C++ standard library and there are good parts. But if you are just trying to do type safe generic data structures you are unlikely to touch the bad parts. LLVM forbids including <iostream>. You can forbid using parts of the standard library too.
        • Joker_vD 40 minutes ago
          > Yes there are bad parts in the C++ standard library and there are good parts.

          Okay, other than <vector>, what are the good parts? Because as the sibling comments rightfully point out, migrating your codebase from C to C++ just to be able to use <vector> is not worth it.

          The <map> is a sad joke played upon the C++ programmers by the standard committee.

          • pjmlp 34 minutes ago
            Strings, something that C still doesn't do properly, not even having something like SDS into the standard library.

            <map> does the work just fine, not everyone has winning microbenchmarks as part of their daily work.

            • Joker_vD 23 minutes ago
              > <map> does the work just fine

              It has a rather weird interface, at least until C++ 17 when some of the deficiencies were patched somewhat.

    • 0xbadcafebee 6 minutes ago
      [delayed]
  • lor_louis 2 hours ago
    I wrote a summarizing article on type safe container types a while back, but with some C23 specific changes and a few tweaks to work better for complex types.

    https://louissven.xyz/article/how_I_do_container_types_in_C....

    Feel free to flag/delete if this isn't the place.

  • tniemi 2 hours ago
    That `(1 ? (item) : (list)->payload)` was a neat trick. It gets optimized away, but the type comparison happens before that.

    Still feels a bit like a party trick, but if it works...

    • JdeBP 1 hour ago
      It's somewhat of a forced trick nowadays, I think.

      I actually thought from the title before I read the article that it was going to use _Generic, as in something like _Generic((item),__typeof__((list)->payload):...) .

    • Xirdus 2 hours ago
      Expressions that compile but never evaluate are bread and butter in C++ template metaprogramming.
  • randomNumber7 40 minutes ago
    As far as I know many C programmers think the addition of variable length arrays in C99 was a mistake. What would be the downside of this approach?
    • pjmlp 39 minutes ago
      So much so, that it was made optional annex in C11, while Google paid to remove all their use from the Linux kernel.
    • uecker 32 minutes ago
      I do not get the connection with a VLA in this context, but if you need a VLA, by all means use it. It is basically always better than the alternative.
      • randomNumber7 29 minutes ago
        > I do not get the connection with a VLA in this context

        The article uses a struct with a VLA as the last element.

        • uecker 20 minutes ago
          I see. This array of unknown length at the end of a struct is called a flexible array member and not a variable length array (although it also refers to an array of variable length it is a different language feature).
          • lukasgelbmann 12 minutes ago
            Yes, and variable length arrays were made an optional part of the standard in C11. Whereas flexible array members remain a standard required feature.

            Flexible array members don’t allocate a dynamic amount of memory on the stack.

  • veexx103 2 hours ago
    Is it feasible to create a new language by adding features to C

    just as was done with C++?

    • pornel 8 minutes ago
      It's not worth it. The value of C is in compatibility, availability of compilers, and familiarity.

      As soon as you change anything in a breaking way, start requiring your own compiler/transpiler, or introduce new idioms, you end up losing the things that keep C alive.

      Users of C either like it exactly the way it is, or have to use a specific C version due to a vendor dependency or compliance.

      An upgraded C not approved by the standards body gives you yet another niche language that is not C, but is still burdened with its old flaws.

    • FullGarden_S 6 minutes ago
      C3 might be it because C3 has full C ABI compatibility so unlike most modern C-like alternatives, it checks out.
    • pjmlp 2 hours ago
      And Objective-C, yet somehow people reinvent them badly in C.
    • nikbackm 2 hours ago
      There are already plenty of such languages, Zig among others.
      • peesem 1 hour ago
        zig doesn't "extend" C in the way that C++ does.
        • krior 17 minutes ago
          But C++ does not extend C as well.
        • christophilus 52 minutes ago
          C3?
          • pjmlp 33 minutes ago
            Nope, they went their own way now, see recent blog posts.
  • rramadass 3 hours ago
    Also see Templates in C by David Priver - https://www.davidpriver.com/ctemplates.html

    He also has other interesting C techniques, namely;

    Adding reflection to C - https://news.ycombinator.com/item?id=49964525

    _Generic for Type Reification in C - https://www.davidpriver.com/creification.html

    See also his C2y interpreter with REPL named "DrC" for the upcoming C29 standard (https://en.wikipedia.org/wiki/C29_(C_standard_revision)) - https://github.com/drpriver/drc

    PS: I really like his style of writing and presentation; concise and precise without unnecessary fluff and page beautifying.

    • david2ndaccount 39 minutes ago
      Hey that’s me! Cool to see people like my stuff.
      • warmwaffles 6 minutes ago
        I do wish to see comptime stuff in C some day. Or at a minimum your `defblock` implemented. I am so tired of having to escape new lines.
    • podocarp 2 hours ago
      Lol at some point just implement a small compiler in C… reflection is kinda a hilarious thing to have like I understand the use case for generics, since it's not that that that hard to do with macros and quite commonly wished for
  • carlos256 2 hours ago
    Jesus, I hate those macro hacks so much. Most of the time you only need a single container, so writing an ad-hoc implementation is cleaner than that.
    • pjmlp 2 hours ago
      The extent some will go to avoid touching C++.
      • uecker 37 minutes ago
        Indeed. After having suffered from C++ a lot, I am also really avoid touching it if I can.

        But if you compare some C++ template container to a C macro solution, I also do not find the macro solution to be more complex.

        • pjmlp 28 minutes ago
          I would not expect any other kind of answer.

          We will keep on agreeing to disagree.

          • uecker 17 minutes ago
            The difference between me and you is that I do not usually post under C++ articles something negative about C++. Instead I respect that people interested in C++ may have their own reasons. For some reason you find it appropriate to post something negative under each C article.

            I could tolerate it if it were at least some interesting criticism,.

  • nice_byte 1 hour ago
    I've tried doing this for a few years and it just sucks ass. Just use c++ and templates if you need proper generic data structures. C is a defective language.