Type Safe Generic Data Structures in C

(danielchasehooper.com)

103 points | by AlexeyBrin 2 days ago

8 comments

  • Panzerschrek 2 hours 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++?
    • psyclobe 4 minutes ago
      Its rather hard to introduce c++ into legacy c projects. You basically have to decide on a subset of features to use, and then you'll have to explain to the teams why the same looking code now takes 10x more compute to build.

      Usually the way we do it here is we honor some interface then rewrite the subsystem in c++.

      And then there's the real hurdle and that is getting the c++ idiom correct as it is very easy to just open the floodgates and let everyone write code that looks vastly different.

    • uecker 1 hour 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.

      • Panzerschrek 16 minutes ago
        > the mess in C++ is way worse

        What is mess in C++? Yes, it has some shady parts and is more complex than C, but this complexity provides expressiveness and type safety. And you can always use only features from C++ you find useful.

        > also contribute to projects that introduce C++ into a C code base, and I really wish they hadn't done this.

        What is problematic in these projects other than unfamiliarity of C++ for developers previously used only C?

    • 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 1 hour 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. Many codebases forbids parts of the standard library, e.g. LLVM forbids including <iostream>. You can forbid using parts of the standard library too.
        • Joker_vD 1 hour 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.

          • kccqzy 4 minutes ago
            So what? You like <vector>, and make it the only allowed include. Write all other type safe generic data structures by hand using C++ syntax. Problem solved.
          • pjmlp 1 hour 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.

            • accelbred 42 minutes ago
              Many of the big C++ projects I've worked with have custom string types since the standard one was defficient for some reason or another.
              • jstimpfle 35 minutes ago
                Exactly, and a simple usable string type is just a struct MyString { char *buf; size_t len; }; away. Actual magic is in how you use it, where you allocate it, how you integrate allocation and formatting and logging and I/O... i.e. all the things that aren't solved by crufty complex std::string either.
            • Joker_vD 1 hour 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.

              • jstimpfle 38 minutes ago
                It's a slow generic data structure with an unintuitive API. You can use it for leetcode or for CRUD. For anything more demanding it's horrifically bloated and bad. std::string too. Whenever you see STL datatypes like even string and map, you have to deal with RAII, implicit allocations, weird operator syntax, unexpected mutation (invalidation) and so on.

                (Spporting or even encouraging destructive mutation, and by this I mean not incrementing counters or anything harmless but allowing iterator invalidations and crashes, are also why std::vector is bad in my opinion, these are idiomatic APIs for 90s and 2000s programming, which we should know better to avoid in 2026).

                • pif 0 minutes ago
                  > you have to deal with RAII

                  If you find that RAII is a problem, I pity how poor a programmer you must be...

                • Panzerschrek 11 minutes ago
                  > For anything more demanding it's horrifically bloated and bad

                  C++ containers are designed for average demands. If you need something more specific, you can always use an alternative implementation. And it's better than messing with macros in pure C.

                  > you have to deal with RAII

                  What's problematic with it?

                  > implicit allocations

                  Allocations aren't implicit. It's usually clear from the documentation where allocation takes place (like in concatenating strings or copying strings).

                  > unexpected mutation (invalidation)

                  It's not the case with standard library containers. Mutating methods aren't const-qualified, so that it's clear where mutation can take place. And in C++ it's strictly recommended to mark as const everything in regular user code which shouldn't be mutated.

        • accelbred 44 minutes ago
          You cant touch C++ without bringing the object lifetime stuff in. And unlike strict aliasing, theres no flag to turn it off.
          • jeffbee 35 minutes ago
            Object lifetime is the entire point of C++ and it solves ~100% of the emergent flaws in C programs.
            • accelbred 26 minutes ago
              I was just dealing with this: https://bugs.gentoo.org/show_bug.cgi?id=974323.

              Also std::start_lifetime_at is a hack and ive seen nobody using it in all the placed where it aught to be used.

              If optimizing based on object lifetimes could be turned off, itd be turned off everywhere for hardening like strict aliasing is.

              • jeffbee 15 minutes ago
                In my personal opinion, the fix[1] for that issue clearly implicates C-style habits polluting a C++ code base. No right-thinking knower of C++ initializes objects with memset! Also I believe that -Wall would have flagged that, and I know for certain that cppcoreguidelines-init-variables + cppcoreguidelines-pro-type-member-init would have flagged it.

                1: https://github.com/llvm/llvm-project/commit/905a88b923433eb8...

    • rwbt 1 hour 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 1 hour ago
        It is called a linter, more devs should learn to use a tool that was originally created for C in 1979.
        • accelbred 46 minutes ago
          The only decent linters I know of for C++ are clang-tidy and coverity and they are not good enough.
    • 0xbadcafebee 51 minutes ago
      If you want better tires on your car, why not just get a different car?
  • lor_louis 3 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 3 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 2 hours 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 3 hours ago
      Expressions that compile but never evaluate are bread and butter in C++ template metaprogramming.
  • veexx103 3 hours ago
    Is it feasible to create a new language by adding features to C

    just as was done with C++?

    • pornel 54 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.

    • accelbred 38 minutes ago
      I am working on a language that was C with extensions, transpiled to plain C, but the C syntax is kinda not great to work with (stuff like needing type tables and unbounded lookahead). At the point you clean up the syntax, you're not really C with extensions anymore.
    • pjmlp 2 hours ago
      And Objective-C, yet somehow people reinvent them badly in C.
    • FullGarden_S 52 minutes ago
      C3 might be it because C3 has full C ABI compatibility so unlike most modern C-like alternatives, it checks out.
    • nikbackm 2 hours ago
      There are already plenty of such languages, Zig among others.
      • peesem 2 hours ago
        zig doesn't "extend" C in the way that C++ does.
        • krior 1 hour ago
          But C++ does not extend C as well.
        • christophilus 1 hour ago
          C3?
          • pjmlp 1 hour ago
            Nope, they went their own way now, see recent blog posts.
  • randomNumber7 1 hour 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 1 hour 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 1 hour 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 1 hour 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 1 hour 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).
          • randomNumber7 18 minutes ago
            What happens when I put a variable of a struct type that contains a flexible array member on the stack?
          • lukasgelbmann 57 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.

            • uecker 40 minutes ago
              VLAs are supported by basically all modern C compilers though, and I do not think adding them was a mistake (I certainly use them a lot!). They got a bad reputation due to stack clash attacks, but in the past some compilers did not implement stack probing (clang was very late). But this was fixed a decade ago.
  • 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 1 hour ago
      Hey that’s me! Cool to see people like my stuff.
      • rramadass 38 minutes ago
        You should write more ;-)

        I also posted your "Adding Reflection to C" at https://news.ycombinator.com/item?id=49964525 and hope HN picks up on it and has a decent discussion.

        You definitely should add a detailed post on your "DrC" compiler/interpreter; usecase, scope, techniques used etc. Since this is looking forward to C2y/C29 with some more extensions, i think people will enjoy playing with it in the REPL format.

      • warmwaffles 52 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 3 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 1 hour 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 1 hour ago
          I would not expect any other kind of answer.

          We will keep on agreeing to disagree.

          • uecker 1 hour 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 2 hours 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.