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, see C++'s std::list. It is awkward in C, where the implementation has to be macro-generated. C naturally pushes towards an indirection through void *, which makes intrusive lists more attractive.

One other advantage of intrusive data structures is the ability to link a payload into several parallel collections without indirections (where traditional collections would require e.g. one collection owning the payloads, and the other collections merely holding non-owning pointers to them).

Las but not least, the defining property of intrusive data structures is that they leave the responsibility of allocating the elements to the user. The elements can be allocated on the heap, on the stack, in a global array (like "initholes" in the article), in a special arena, etc. It is even reasonable to use non-uniform allocation strategies; for example, for a circular list, allocate an anchor node on the stack and the other nodes (those embedded in payloads) on the heap.

▲ drdexebtjl 5 hours ago | parent | next [-]

> 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 separate metadata allocation.

The caveat is that the type of the pointer does not indicate provenance. For example, nothing stops you from calling list_next on an arbitrary pointer to data that is not on a list, and that would be UB. The same happens with realloc and free, where it's UB if you pass them a pointer that was not returned by the heap allocator.

▲ el_pollo_diablo 4 hours ago | parent [-]

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), but it is UB to access 'payload' in place as a T (as main does, by casting to struct point * and dereferencing). Oh, and 'payload' may not satisfy the alignment requirement of T.

There is no realistic strict-aliasing-abiding way around a distinct node type per payload type.

▲ Joker_vD 4 hours ago | parent | next [-]

> 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 trying to emulate) if the payload type has an alignment that's greater than the size of a pointer, and that pointer will be pointing at what would've been the padding in that struct.

▲ el_pollo_diablo 4 hours ago | parent [-]

> 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
    };

▲ Joker_vD 3 hours ago | parent [-]

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

▲ el_pollo_diablo 3 hours ago | parent [-]

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

You can certainly store an object of arbitrary type, but here it is done through a pointer to an object with pointer arithmetic going beyond the allowed bounds.

> memcpy takes a void pointer as its destination, sets the effective type of the storage behind it

And, in doing so, may very well overwrite the unspecified padding following 'payload' in the structure, thus instantly destroying the effective type of the structure object itself. Subsequent accesses to the structure or its members will be UB.

It seems to me that your argument hinges on two assumptions:

    - there is no padding following 'payload' (this would have to be statically asserted),
    - the pointer to 'payload' is indistinguishable from the pointer past the structure; in particular, provenance is not an issue.

That is a very interesting discussion.

▲

drdexebtjl 2 hours ago | parent [-]

If payload was ever dereferenced as a char array as well, I would buy the strict aliasing argument. But it’s not, it exists as a char pointer solely for pointer arithmetic.

AFAIK The purpose of strict aliasing rules is to let the compiler assume that dereferencing pointers of different types never refer to the same memory.

If ISO C treats this as UB, shouldn’t ISO C be fixed?

	▲	dcrazy 32 minutes ago \| parent [-]
		No, you should fix your code to be compliant with ISO C. The optimizer isn’t going to wait for you to convince WG14.

▲ drdexebtjl 4 hours ago | parent | prev [-]

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.

	▲	el_pollo_diablo 3 hours ago \| parent [-]
		> IIRC GCC and Clang lets character types alias to any type. It is always legal to access the memory representation of any object as an array of characters. The other way around (interpreting an array of characters as a T, even though it does not have effective type T) is not. > Otherwise glibc’s malloc also doesn’t abide to strict aliasing. It may not have to. From the point of view of C, malloc is special because it is part of the implementation. The compiler is free to handle UB as it sees fit. In particular, it can decide that aliasing has different semantics in malloc.c than outside it.

▲ dietr1ch 4 hours ago | parent | prev | next [-]

> One other advantage of intrusive data structures is the ability to link a payload into several parallel collections without indirections

My example here from the top of my head are intrusive heaps, which are provide a neat way of implementing A*. Here you combine a HashMap and a Heap (over a Vec) where the Heap has the data, and the HashMap maps SearchNodeId to Heap indices. This allows O(1) lookups by search node Id into the Heap (as opposed to a linear scan) despite elements in the heap being constantly shuffled around as search nodes enter and leave the heap.

I'm sure that using HashMaps as a parallel index to other collections can be useful in other scenarios, but I don't know if combination of other data structures works this well, the synchronisation cost might not be worth it.

▲ uecker 5 hours ago | parent | prev | next [-]

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.

▲ el_pollo_diablo 4 hours ago | parent [-]

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

▲ uecker 3 hours ago | parent | next [-]

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

▲ Joker_vD 4 hours ago | parent | prev [-]

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

▲ el_pollo_diablo 3 hours ago | parent [-]

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

▲ Joker_vD 3 hours ago | parent [-]

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

Oh, that's simple: just have empty struct tags.

> And what about typedefs?

The names introduced by the typedefs are irrelevant.

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

Huh?

    typedef struct { int x; } A;
    typedef struct { int x; } B;

    typedef struct { header_list header; A payload; } list_of_A;
    typedef struct { header_list header; B payload; } list_of_B;

The structs list_of_A and list_of_B are compatible.

▲

uecker 2 hours ago | parent | next [-]

No, any tagless type is unique, so neither A and B nor list_of_A and list_of_B are compatible.

This is what I like to fix in C2y outside of typedefs (and it would really help if you file wishlist bugs with compilers if you agree).

▲

el_pollo_diablo 2 hours ago | parent | prev [-]

> The structs list_of_A and list_of_B are compatible.

No, they are not. From C23, 6.7.3.4 Tags: Each declaration of a structure, union, or enumerated type which does not include a tag declares a distinct type.

▲

icedchai 2 hours ago | parent [-]

It depends what is meant by "compatible." Is the memory layout the same? Yes. Can I memcpy between them? Yes...

▲

el_pollo_diablo an hour ago | parent [-]

We mean compatible as defined by the C language standard. It is much more restrictive than having the same layout. In particular, you may not pass a pointer to a type where a pointer to an incompatible type is expected, even if the types have the same layout, which prevents the sort of sharing between two libraries that is being discussed.

Moreover, there is no guarantee that two distinct structure types with the same list of members have the same size or alignment (although in practice they do). The members must nevertheless be laid out in the same way (same offsets, and in the case of bit-fields, same layout inside storage units) due to an obscure constraint on common initial sequences. So the layouts of the structures may differ in the alignment requirement and the amount of trailing padding.

	▲	icedchai 9 minutes ago \| parent [-]
		Yes, I figured that's what you meant... I wasn't sure about the other guy.

▲ dahart 6 hours ago | parent | prev | next [-]

> It is awkward in C, where the implementation has to be macro-generated

I assume this is why they are putting the list pointer and payload in separate structs and doing pointer math to access the payload, so that it’s easy to build a set of macros that act like a generic list class for building lists out of any payload, right?

> One other advantage of intrusive data structures is the ability to link a payload into several parallel collections without indirections

Wait - how does this work? If I do address math on the pointer in order to find a payload, then isn’t the payload tied into exactly one next pointer, and thus exactly one list? For a minute I thought maybe this is why they put the pointer after the payload, but now I don’t see how to use a payload in more than one list, nor why they use subtract on the list pointer to find the payload instead of putting the list in front of the payload and adding (or using a type-cast pointer for direct access).

> the defining property of intrusive data structures is that they leave the responsibility of allocating elements to the user.

Indeed! This is why you see them in OS’s, in memory managers, and in embedded systems. We used to use them all the time in console video games before dynamic memory and heap allocations were common (or even allowed). Use of STL wasn’t allowed. Often the memory needed would be pre-allocated, and lists would be created and managed at run time without allocation, just by wiring up the pointers. Similar to what a memory manager has to do.

This was in C++, but back when (and before) EASTL was popular. EASTL was EA’s version of the STL without built-in heap allocation for container classes. We usually built payload classes with the list next pointer placed directly in the payload, and essentially did the list management as a one-off separately for each payload, because it was typically only a few lines of code and there weren’t enough list types for it to be a problem. This is the kind of intrusive list I’ve seen the most of, hence the questions about the particular C flavor shown here.

	▲	apple1417 5 hours ago \| parent [-]
		> If I do address math on the pointer in order to find a payload, then isn’t the payload tied into exactly one next pointer, and thus exactly one list? The container_of macro takes the type and member - so for a different member it can subtract a different offset. Going more basic, you could imagine creating something like: `struct Node { Node* next; Node* next_10th; Node* next_100th; };` The normal, 10ths, and 100ths lists are distinct collections, this is the basic idea. The macros just help generalise it and make it more usable.

▲ groundzeros2015 5 hours ago | parent | prev | next [-]

The C macro systems never last. Just write it! It’s no harder than a for loop.

▲ samatman 5 hours ago | parent | prev [-]

> This is easy to do with the proper support for monomorphized generics, see C++'s std::list. It is awkward in C, where the implementation has to be macro-generated.

Fairly pleasant in Zig, through abuse of @fieldParentPointer and a pinch of comptime.

https://github.com/mnemnion/zelda

It was a little nicer in the `usingnamespace` days. So it goes.

> The elements can be allocated on the heap, on the stack, in a global array (like "initholes" in the article), in a special arena, etc.

An "etc" worth mentioning specifically is a memory pool: they're useful for any same-sized struct which gets recycled a lot, but for linked lists there are further advantages. You don't have to cast the object to bytes and declare a link pointer, since it already has one: not really an advantage, casting is free, but: if you can arrange to give both sides of the list back, then recycling can be done on a per-list level by prepending the whole thing to the freelist.