7 ms·

Type-safe generic data structures in C

58 points by signa11 6y ago

lasagnaphil 6y 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 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-in-c-part-1/ https://ourmachinery.com/post/minimalist-container-library-i...
- addaon 6y ago
  But this entirely misses the "type safe" part...
  - tom_mellior 6y 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 6y 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.
- Aanok 6y ago
  > assert(p); > if (p) { Do you want me to have an embolism?
  - tom_mellior 6y 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.
    - Aanok 6y ago
      That's actually correct C pointer arithmetic. When you increment a pointer, it moves ahead by the sizeof the underlying concrete type. If the pointer is to void, there is no underlying type and in fact void pointer arithmetic is disallowed by the standard. GCC lets you do it with an extention: https://gcc.gnu.org/onlinedocs/gcc-4.8.0/gcc/Pointer-Arith.html https://gcc.gnu.org/onlinedocs/gcc-4.8.0/gcc/Pointer-Arith.h... So in this case, since the headers for the arrays are made up of two int's it's the right thing to do to move around by sizeof(int) memory address units. You do this with a cast before the arithmetic.
      - tom_mellior 6y ago
        My point was, why not declare the pointer as int * directly since that the only type it's used as?
  - efficax 6y ago
    to be fair, if assert is removed in release code, you still have some protection with the `if`
efficax 6y 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 6y 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.
  - monocasa 6y 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.
witty_username 6y ago
Why would anyone use this when there is C++, Rust, etc? Genuinely curious.
- macintux 6y 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.
  - bitwize 6y 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!
    - lionkor 6y ago
      > all CPUs that are likely to run your code are little endian Alright, I'll bite. How is ARM (commonly Bi-Endian) considered a (1) "highly specialized" or (2) little-endian architecture?
      - jcelerier 6y ago
        99% of ARM usage is done in little endian. all android & ios phones, all embedded boards that ship with linux, etc. are always configured in little endian.
        lionkor 6y ago
        Okay, assuming you're right, how much overhead is it to consider endianness? I've never had issues with it, unless I'm implementing something fully from scratch, and that's rare in a production environment.
codezero 6y 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 6y 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".
- deleted 6y ago
  [deleted]
- bitwize 6y 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 6y ago
    Also OpenSSL
- jcelerier 6y 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 6y ago
  By the way, the "safe" alternative in your post roughly describes how C++ started its life.
- efficax 6y 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 https://github.com/attractivechaos/klib
cperciva 6y ago
See also "elastic arrays": https://github.com/Tarsnap/libcperciva/blob/master/datastruct/elasticarray.c https://github.com/Tarsnap/libcperciva/blob/master/datastruc... https://github.com/Tarsnap/libcperciva/blob/master/datastruct/elasticarray.h 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 6y 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.
- Galanwe 6y ago
  Note that include guards become tricky then.
  - deleted 6y ago
    [deleted]
  - TheNewAndy 6y ago
    You don't use include guards with this pattern. See https://en.wikipedia.org/wiki/X_Macro https://en.wikipedia.org/wiki/X_Macro for more.
- ludocode 6y 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 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/ https://github.com/glouw/ctl/
chacham15 6y ago
OpenSSL does this in its STACK_OF concept: https://github.com/openssl/openssl/blob/a28d06f3e9cbc5594c7985c99a0c6bac5261ae67/doc/man3/DEFINE_STACK_OF.pod https://github.com/openssl/openssl/blob/a28d06f3e9cbc5594c79...
deleted 6y ago
[deleted]
ginko 6y 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 6y 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.
- fulafel 6y ago
  I guess because it calls itself a systems language and GC works fine for most systems programming.
  - stkdump 6y ago
    What is the defining characteristic of a 'systems language', and what is an example for a language that doesn't fulfill it?
    - tom_mellior 6y ago
      > What is the defining characteristic of a 'systems language' The precise technical definition is "whatever the speaker means by it". In other words, it's not a useful term. People will come up with definitions like "whatever you can write an OS kernel/a compiler/a database management system in". So languages like Haskell, OCaml, and Java are certainly included. I don't see why Go shouldn't be.
    - fulafel 6y ago
      Well, systems programming and apps programming are the domains in question, SP is about implementing the platform and infrastructure. There is no single defining characteristic since languages are used cross purposes, it's a term meant to characterise existing engineering practice. But if you really wanted an example of the least likely SP language, I'd say MATLAB or Prolog could be nominated. Lisp and Java have been used in SP roles even though people often think of them as apps languages. Probably most useful is to observe what usage languages see. Eg Go is used for many databases, K8s, gVisor, Docker etc.

58 points by signa11 6y 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 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-in-c-part-1/ https://ourmachinery.com/post/minimalist-container-library-i...

addaon 6y ago
But this entirely misses the "type safe" part...
- tom_mellior 6y 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 6y 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.
Aanok 6y ago
> assert(p); > if (p) { Do you want me to have an embolism?
- tom_mellior 6y 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.
  - Aanok 6y ago
    That's actually correct C pointer arithmetic. When you increment a pointer, it moves ahead by the sizeof the underlying concrete type. If the pointer is to void, there is no underlying type and in fact void pointer arithmetic is disallowed by the standard. GCC lets you do it with an extention: https://gcc.gnu.org/onlinedocs/gcc-4.8.0/gcc/Pointer-Arith.html https://gcc.gnu.org/onlinedocs/gcc-4.8.0/gcc/Pointer-Arith.h... So in this case, since the headers for the arrays are made up of two int's it's the right thing to do to move around by sizeof(int) memory address units. You do this with a cast before the arithmetic.
    - tom_mellior 6y ago
      My point was, why not declare the pointer as int * directly since that the only type it's used as?
- efficax 6y ago
  to be fair, if assert is removed in release code, you still have some protection with the `if`

efficax 6y 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 6y 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.
- monocasa 6y 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.

witty_username 6y ago

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

macintux 6y 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.
- bitwize 6y 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!
  - lionkor 6y ago
    > all CPUs that are likely to run your code are little endian Alright, I'll bite. How is ARM (commonly Bi-Endian) considered a (1) "highly specialized" or (2) little-endian architecture?
    - jcelerier 6y ago
      99% of ARM usage is done in little endian. all android & ios phones, all embedded boards that ship with linux, etc. are always configured in little endian.
      - lionkor 6y ago
        Okay, assuming you're right, how much overhead is it to consider endianness? I've never had issues with it, unless I'm implementing something fully from scratch, and that's rare in a production environment.

codezero 6y 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 6y 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".

deleted 6y ago
[deleted]
bitwize 6y 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 6y ago
  Also OpenSSL
jcelerier 6y 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 6y ago
By the way, the "safe" alternative in your post roughly describes how C++ started its life.
efficax 6y 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 https://github.com/attractivechaos/klib

cperciva 6y ago

See also "elastic arrays": https://github.com/Tarsnap/libcperciva/blob/master/datastruct/elasticarray.c https://github.com/Tarsnap/libcperciva/blob/master/datastruc... https://github.com/Tarsnap/libcperciva/blob/master/datastruct/elasticarray.h 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 6y 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.

Galanwe 6y ago
Note that include guards become tricky then.
- deleted 6y ago
  [deleted]
- TheNewAndy 6y ago
  You don't use include guards with this pattern. See https://en.wikipedia.org/wiki/X_Macro https://en.wikipedia.org/wiki/X_Macro for more.
ludocode 6y 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 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/ https://github.com/glouw/ctl/

chacham15 6y ago

OpenSSL does this in its STACK_OF concept: https://github.com/openssl/openssl/blob/a28d06f3e9cbc5594c7985c99a0c6bac5261ae67/doc/man3/DEFINE_STACK_OF.pod https://github.com/openssl/openssl/blob/a28d06f3e9cbc5594c79...

deleted 6y ago

[deleted]

ginko 6y 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 6y 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.
fulafel 6y ago
I guess because it calls itself a systems language and GC works fine for most systems programming.
- stkdump 6y ago
  What is the defining characteristic of a 'systems language', and what is an example for a language that doesn't fulfill it?
  - tom_mellior 6y ago
    > What is the defining characteristic of a 'systems language' The precise technical definition is "whatever the speaker means by it". In other words, it's not a useful term. People will come up with definitions like "whatever you can write an OS kernel/a compiler/a database management system in". So languages like Haskell, OCaml, and Java are certainly included. I don't see why Go shouldn't be.
  - fulafel 6y ago
    Well, systems programming and apps programming are the domains in question, SP is about implementing the platform and infrastructure. There is no single defining characteristic since languages are used cross purposes, it's a term meant to characterise existing engineering practice. But if you really wanted an example of the least likely SP language, I'd say MATLAB or Prolog could be nominated. Lisp and Java have been used in SP roles even though people often think of them as apps languages. Probably most useful is to observe what usage languages see. Eg Go is used for many databases, K8s, gVisor, Docker etc.