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

41–50 of 196 posts

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

#41

Post by rectang »

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 language (.cfh "Clownfish Header" files).

Here's some generated code for invoking the CharBuf version of the "Clone" method defined in parent class "Obj":

    typedef cfish_CharBuf*
    (*CFISH_CharBuf_Clone_t)(cfish_CharBuf* self);

    extern uint32_t CFISH_CharBuf_Clone_OFFSET;

    static inline cfish_CharBuf*
    CFISH_CharBuf_Clone(cfish_CharBuf* self) {
        const CFISH_CharBuf_Clone_t method
            = (CFISH_CharBuf_Clone_t)cfish_obj_method(
                self,
                CFISH_CharBuf_Clone_OFFSET
            );
        return method(self);
    }
Usage:

    cfish_CharBuf *charbuf = cfish_CharBuf_new();
    cfish_CharBuf *clone = CFISH_CharBuf_Clone(charbuf);
We had our reasons for going to these extremes: the point of Clownfish was to provide a least-common-denominator object model for bindings to multiple dynamic languages (similar problem domain to SWIG), and the .cfh files also were used to derive types for the binding languages. But there was truly an absurd amount of boilerplate being generated to get around the issue you identify.

This is why almost everybody just uses casts to void* for the invocant, skipping type safety.

[1] https://github.com/apache/lucy-clownfish

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

#43

Post by eqvinox »

uecker wrote: post #30
eqvinox wrote: post #13

Earlier quoted context omitted.

I guess if anyone might know it might be you—do you see any way of doing this for intrusive data structures, embedding the node struct in the data (and as side effect supporting an object to be on multiple containers) rather than the data in the node like you're doing there?

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 the clunky "#define, #define, #define, #include" inside a macro…

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

#44

Post by n_plus_1_acc »

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…

This is also problematic, because there might be padding and the calculated size might be too small:

`malloc(sizeof(*node) + data_size);`

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

#45

Post by kccqzy »

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…

> 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++.

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

#46

Post by rectang »

Snarwin wrote: post #39
rectang wrote: post #37

Earlier quoted context omitted.

Writing extensions for projects that support C extensions but may not support C++ extensions, e.g. many dynamic languages.

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.

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

#47

Post by adastra22 »

teraflop wrote: post #40
adastra22 wrote: post #35

Earlier quoted context omitted.

Embedded systems, for example.

I know it used to be, but is it really still common for embedded systems to use weird architectures that G++/Clang don't support?

Unless it is a popular system or common architecture, yes.

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

#48

Post by tedunangst »

kccqzy wrote: post #45
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…

> 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.

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

#50

Post by o11c »

n_plus_1_acc wrote: post #44
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…

This is also problematic, because there might be padding and the calculated size might be too small: `malloc(sizeof(*node) + data_size);`

There's no a problem with the author's current code, since the padding is already included in the node size, but it would be a problem after doing alignment more intelligently.
Post reply on HN