Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

I write type-safe generic data structures in C

danielchasehooper.com

Post reply on HN
Print view View original

51–60 of 196 posts

Re: I write type-safe generic data structures in C

#51

Post by wahern »

dhooper wrote: post #6
HexDecOctBin wrote: post #5

The key idea here seems to be to use function pointer's type to enforce type safety rather than using the data "handle" type (that is often found in implementations inspired by Sean Barrett's strechy_buffers). > One annoying thing about C is that it does not consider these two variables to have the same type C23 solves that too: https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3037.pdf Supported by latest GCC and Cl…

Author here. Not quite. The key idea is about using a union to associate type information with a generic data type. Type casting a function is not the only way to use that type information. I discuss that as well as the C23 changes in the footnotes and the "typeof on old compilers" section.

FWIW, as far back as 2015 my feature check library documents Visual Studio as supporting "__typeof".[1] Note the leading but not trailing underscores. Perhaps I was mistaken, but I usually tested that sort of thing. It's also possible __typeof had slightly different semantics.

[1] See https://github.com/wahern/autoguess/blob/b44556e4/config.h.g... (that's the 2015 revision, but HEAD has the same code).

Re: I write type-safe generic data structures in C

#52

Post by uecker »

eqvinox wrote: post #43
uecker wrote: post #30

Earlier quoted context omitted.

You could put the dummy member into the embedded node. But for intrusive data structures you often want them to erase the type so that you write generic algorithms as regular functions. In this case, it makes more sense to have a run-time check do to down casts. I do this with my variadic type which has an intrusive "super" member: https://godbolt.org/z/ofdKe7Pfv The overhead is often completely removed by the compil…

Mhm. Putting the dummy member into the embedded node doesn't give a path from the proper object to find the embedded node "mid-struct". run-time checks are the "easy way out". We/I'll stick to macro soup probably, so we have compile-time checks. btw. For ISO C WG14… has anyone suggested adding _Include to the preprocessor, along the lines of _Pragma? It'd really help with doing this kind of really long macros, hiding…

I don't think anybody has proposed this, at least not recently. There is a proposal for multi-line macros: https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3531.txt

Re: I write type-safe generic data structures in C

#53

Post by uecker »

rectang wrote: post #46
Snarwin wrote: post #39

Earlier quoted context omitted.

You can still write the extension in C++ and expose an extern "C" interface.

That's possible, but then the people building your extension need a C++ toolchain. The question was "please provide examples where switching to C++ involves jumping through even more hoops", and in my view requiring downstream to use a C++ environment when they're expecting to use a C environment qualifies.

True. For me, C++ itself is the maze of hoops I would rather want to avoid.

Re: I write type-safe generic data structures in C

#54

Post by WalterBright »

Here's how to do it in D:

    struct ListNode(T) {
        ListNode* next;
        T data;
    }

    T!int node;
Why suffer the C preprocessor? Using preprocessor macros is like using a hammer for finish carpentry, rather than a nail gun. A nail gun is 10x faster, drives the nail perfectly every time, and no half moon dents in your work.

Re: I write type-safe generic data structures in C

#55

Post by dhooper »

wahern wrote: post #51
dhooper wrote: post #6

Earlier quoted context omitted.

Author here. Not quite. The key idea is about using a union to associate type information with a generic data type. Type casting a function is not the only way to use that type information. I discuss that as well as the C23 changes in the footnotes and the "typeof on old compilers" section.

FWIW, as far back as 2015 my feature check library documents Visual Studio as supporting "__typeof".[1] Note the leading but not trailing underscores. Perhaps I was mistaken, but I usually tested that sort of thing. It's also possible __typeof had slightly different semantics. [1] See https://github.com/wahern/autoguess/blob/b44556e4/config.h.g... (that's the 2015 revision, but HEAD has the same code).

msvc 19.39 is the first to support it, which I mention in the article. You can confirm it didn't work up through 19.38 in godbolt [1]. I don't use Visual Studio, so I don't know what version of that first started using msvc 19.39

[1] https://godbolt.org/z/M7zPYdssP

Re: I write type-safe generic data structures in C

#56

Post by dhooper »

WalterBright wrote: post #54

Here's how to do it in D: struct ListNode(T) { ListNode* next; T data; } T!int node; Why suffer the C preprocessor? Using preprocessor macros is like using a hammer for finish carpentry, rather than a nail gun. A nail gun is 10x faster, drives the nail perfectly every time, and no half moon dents in your work.

Thanks, this post is about C.

On some projects you must use C.

Re: I write type-safe generic data structures in C

#57

Post by s3graham »

tedunangst wrote: post #48
kccqzy wrote: post #45

Earlier quoted context omitted.

> it should be `int main() { List(Foo) foo_list = {NULL};` In C `int main()` means the function takes an unknown number of arguments. You need `int main(void)` to mean it doesn't take any arguments. This is a fact frequently forgotten by those who write C++.

This is incorrect. In a function definition, an empty list means it takes no parameters. 6.7.5.3 Function declarators > 14. An empty list in a function declarator that is part of a definition of that function specifies that the function has no parameters.

As you surely know if you're quoting the standard, it depends on which standard!

Re: I write type-safe generic data structures in C

#58

Post by WalterBright »

dhooper wrote: post #56
WalterBright wrote: post #54

Here's how to do it in D: struct ListNode(T) { ListNode* next; T data; } T!int node; Why suffer the C preprocessor? Using preprocessor macros is like using a hammer for finish carpentry, rather than a nail gun. A nail gun is 10x faster, drives the nail perfectly every time, and no half moon dents in your work.

Thanks, this post is about C. On some projects you must use C.

If I may may be provocative :-) this post isn't about C. It's about layering on a custom language using C preprocessor macros.

My compilers were originally written in C. I started using the C preprocessor to do metaprogramming. After some years I got fed up with it and removed nearly all of the preprocessor use, and never looked back. My code was much easier to understand.

An amusing story: long ago, a friend of mine working for Microsoft was told by a team leader that a 50K program had a bug in it, and sadly the developer was long gone. He'd assigned programmer after programmer to it, who could not fix it. My friend said he'd give it a try, and had it fixed in 2 hours.

The source code was written in Microsoft MASM, where the M stood for "Macro". You can guess where this is going. The developer had invented his own high level language using the macro system (which was much more powerful than C's). Unfortunately, he neglected to document it, and the other programmers spent weeks studying it and could not figure it out.

The leader, astonished, asked him how he figured it out in 2 hours? My friend said simple. He assembled it to object code, then disassembled the object code with obj2asm (a disassembler I wrote that converts object code back to source code). He then immediately found and fixed the bug, and checked in the "new" source code which was the disassembled version.

I've seen many very smart and clever uses of the C macros, the article is one of them. But isn't it time to move on?

Re: I write type-safe generic data structures in C

#60

Post by zem »

rectang wrote: post #41
o11c wrote: post #12

For your level 2 code, `uint64_t data[];` is wrong for types whose alignment is greater than `uint64_t`, and also wasteful for types whose alignment is smaller (for example, under an ilp32 ABI on 64-bit architectures). For your level 3 code, it should be `int main() { List(Foo) foo_list = {NULL};` Note that working around a lack of `typeof` means you can't return anything. Also, your particular workaround allows `con…

> Delegating to an external vtable (mandatory to avoid overhead) means that you have to forward-declare all of the types you'll ever use a vtable with. We went down the rabbit hole of writing a compiler for this as part of a project I used to work on (Apache Clownfish[1], a subproject of the retired Apache Lucy project). We started off parsing .h files, but eventually it made sense to create our own small header lang…

i am firmly of the opinion that compiling to c is a better route than doing clever c tricks to sort of get what you want. the compiler can be pretty minimal and as you note it pays for itself.
Post reply on HN