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

Intrusive linked lists (2019)

data-structures-in-practice.com

Post reply on HN
Print view View original

31–40 of 80 posts

Re: Intrusive linked lists (2019)

#31

Post by el_pollo_diablo »

uecker wrote: post #14
el_pollo_diablo wrote: post #2

The go a bit further than the article on the advantages of intrusive data structures, taking linked lists as an example: As the article mentions, intrusive data structures naturally lead to one fewer indirection. To do the same with a traditional list (where the list node owns the payload), a different node type is needed for each payload type. This is easy to do with the proper support for monomorphized generics, se…

I do not think a type-safe macro-generated list in C is any more awkward to implement or inferior to a C++ template version. The issue is more than there is no standardized version directly available except perhaps the old BSD ones and those are not ideal. I agree with the rest of your comment.

> I do not think a type-safe macro-generated list in C is any more awkward to implement or inferior to a C++ template version.

I have some experience with this, and while this is one of these things that are feasible, I find them significantly inferior to templates in practice.

For one thing, footguns are everywhere in C macro-based metaprogramming. E.g. do not declare the payload as 'payload_type payload;' in the node structure, but choose 'typeof(payload_type) payload;' instead, as someone may pass an array type or function pointer type for 'payload_type'. Speaking of array types, how do you deal with the fact that you cannot pass them by value? I will choose C++ templates' semantic substitution over C macros' textual substitution.

Anyway, to me, the biggest limitation of macro-generation compared to templates is that there is no centralized monomorphization. If an application uses two libraries, each of which handles lists of int, each library will have to independently macro-generate its separate list implementation, and because C's type system is nominal, the generated types will be isomorphic but incompatible. Contrast this with C++ templates, where two independent libraries can happily share std::list values.

Re: Intrusive linked lists (2019)

#32

Post by el_pollo_diablo »

Joker_vD wrote: post #28
el_pollo_diablo wrote: post #27

Earlier quoted context omitted.

Zero-sized arrays are not standard. Accessing an array out of bounds is UB. At the very least, you should use a flexible array member instead (char payload[];). But even if you did that, strict aliasing implies that 'payload' can only be accessed as an array of character type. It is correct to memcpy between 'payload' and another object of arbitrary type T of the appropriate size (as list_push_ does in your example),…

> Accessing an array out of bounds is UB. There is no OoB access of an array; the calculated pointer is pointing to the payload object that's residing in the malloc-returned storage right after the node struct. I think the actual problem is the alignment; that malloc-returned storage simply can't have enough space to hold a "struct { struct node header; PAYLOAD_TYPE payload; }" (which is what the parent comment is tr…

> There is no OoB access of an array

Yes, there is. It does not matter that storage happens to be allocated beyond the end of said array. Strict aliasing implies that it is UB to reinterpret the array as anything else. And it is UB to access an array out of bounds.

Flexible array members specifically exist for these dynamically-allocated trailing arrays. They do not solve the strict aliasing problem, though.

> if the payload type has an alignment that's greater than the size of a pointer

The amount of padding is implementation-defined. The only portable guarantee is that 'payload' is aligned for its element type, char. To over-align, use _Alignas, as in:

    struct node {
        struct node *next;
        _Alignas(max_align_t) char payload[]; // Satisfies all fundamental alignment requirements
    };

Re: Intrusive linked lists (2019)

#34

Post by Joker_vD »

el_pollo_diablo wrote: post #31
uecker wrote: post #14

Earlier quoted context omitted.

I do not think a type-safe macro-generated list in C is any more awkward to implement or inferior to a C++ template version. The issue is more than there is no standardized version directly available except perhaps the old BSD ones and those are not ideal. I agree with the rest of your comment.

> I do not think a type-safe macro-generated list in C is any more awkward to implement or inferior to a C++ template version. I have some experience with this, and while this is one of these things that are feasible, I find them significantly inferior to templates in practice. For one thing, footguns are everywhere in C macro-based metaprogramming. E.g. do not declare the payload as 'payload_type payload;' in the no…

> If an application uses two libraries, each of which handles lists of int, each library will have to independently macro-generate its separate list implementation, and because C's type system is nominal, the generated types will be isomorphic but incompatible.

Um, what? C89, 3.1.2.6: "Moreover, two structure, union, or enumeration types declared in separate translation units are compatible if they have the same number of members, the same member names, and compatible member types; for two structures, the members shall be in the same order".

There has been some minor changes over the years, but as long as the struct tags are the same, and the fields are in the same order and have compatible types, the two structs defined in separate compilation units are compatible.

Re: Intrusive linked lists (2019)

#35

Post by drdexebtjl »

el_pollo_diablo wrote: post #27
drdexebtjl wrote: post #21

Earlier quoted context omitted.

> It is awkward in C, where the implementation has to be macro-generated. You can avoid having the implementation be macro-generated by "hiding" the list pointers before a char payload[0]. See https://pastebin.com/DE69mbJD for an example. The same technique is used by glibc's malloc to store metadata about the allocation right next to your data, and then recover it when you call realloc/free, without needing a separa…

Zero-sized arrays are not standard. Accessing an array out of bounds is UB. At the very least, you should use a flexible array member instead (char payload[];). But even if you did that, strict aliasing implies that 'payload' can only be accessed as an array of character type. It is correct to memcpy between 'payload' and another object of arbitrary type T of the appropriate size (as list_push_ does in your example),…

In practice you wouldn’t have the payload in the struct at all, just a fixed offset aligned with the maximum alignment, but this is more illustrative of what’s happening for an example.

IIRC GCC and Clang lets character types alias to any type. Otherwise glibc’s malloc also doesn’t abide to strict aliasing.

Re: Intrusive linked lists (2019)

#36

Post by Joker_vD »

el_pollo_diablo wrote: post #32
Joker_vD wrote: post #28

Earlier quoted context omitted.

> Accessing an array out of bounds is UB. There is no OoB access of an array; the calculated pointer is pointing to the payload object that's residing in the malloc-returned storage right after the node struct. I think the actual problem is the alignment; that malloc-returned storage simply can't have enough space to hold a "struct { struct node header; PAYLOAD_TYPE payload; }" (which is what the parent comment is tr…

> There is no OoB access of an array Yes, there is. It does not matter that storage happens to be allocated beyond the end of said array. Strict aliasing implies that it is UB to reinterpret the array as anything else. And it is UB to access an array out of bounds. Flexible array members specifically exist for these dynamically-allocated trailing arrays. They do not solve the strict aliasing problem, though. > if the…

> It does not matter that storage happens to be allocated beyond the end of said array.

It does matter, for malloc-returned storage. You can put whatever objects you want into that storage as long as it fits and the pointer is properly aligned.

> Strict aliasing

...is not violated; memcpy takes a void pointer as its destination, sets the effective type of the storage behind it, and the treats it as an array of unsigned chars.

Re: Intrusive linked lists (2019)

#37

Post by el_pollo_diablo »

Joker_vD wrote: post #34
el_pollo_diablo wrote: post #31

Earlier quoted context omitted.

> I do not think a type-safe macro-generated list in C is any more awkward to implement or inferior to a C++ template version. I have some experience with this, and while this is one of these things that are feasible, I find them significantly inferior to templates in practice. For one thing, footguns are everywhere in C macro-based metaprogramming. E.g. do not declare the payload as 'payload_type payload;' in the no…

> If an application uses two libraries, each of which handles lists of int, each library will have to independently macro-generate its separate list implementation, and because C's type system is nominal, the generated types will be isomorphic but incompatible. Um, what? C89, 3.1.2.6: "Moreover, two structure, union, or enumeration types declared in separate translation units are compatible if they have the same numb…

> as long as the struct tags are the same

Exactly. Now you have a naming problem. You need a naming convention that every user of the list library must follow, or else their types will be incompatible. And what about typedefs? If A is a typedef of B, or more generally A and B are typedef-related (their normal forms, obtained by following all typedefs, are the same), lists of A and B will be incompatible unless users agree on a common name. The only realistic choice is the normal form, but then this actively works against the abstraction provided by typedef.

And this is just for types. What about functions? While it is legal to do identical definitions of struct list_int, it is not for list_int_init() and list_int_add(). Or global variables: it is legal to do several identical extern declarations, but there can only be one definition; which compilation unit gets to do it?

Re: Intrusive linked lists (2019)

#39

Post by uecker »

el_pollo_diablo wrote: post #31
uecker wrote: post #14

Earlier quoted context omitted.

I do not think a type-safe macro-generated list in C is any more awkward to implement or inferior to a C++ template version. The issue is more than there is no standardized version directly available except perhaps the old BSD ones and those are not ideal. I agree with the rest of your comment.

> I do not think a type-safe macro-generated list in C is any more awkward to implement or inferior to a C++ template version. I have some experience with this, and while this is one of these things that are feasible, I find them significantly inferior to templates in practice. For one thing, footguns are everywhere in C macro-based metaprogramming. E.g. do not declare the payload as 'payload_type payload;' in the no…

You are right that it is not perfect, but it is fine for me and usability is not worse than for C++. I use the rule that only identifiers (typedef names) can be passed. Then the macro can synthesize a tag and list type is then compatible between different libraries.

It could look like this: https://codeberg.org/uecker/noplate/src/branch/main/tests/li...

The predeclarations are not needed anymore in C23 and I hope for the next version of C we can also get rid of the limitation that an identifier needs to be passed to the macro (by making the type system fully structural).

Re: Intrusive linked lists (2019)

#40

Post by blt »

Another benefit the article doesn't mention: these intrusive lists seem a good soft defense against use-after-free bugs in C. The node struct knows about all containers to which it belongs, so writing the "destructor" is very local. With the pointer array equivalent, one can only identify the arrays that point to the object by understanding the surrounding codebase.

(Disclaimer: I am not speaking from experience here. My C background is mostly static allocation.)

Post reply on HN