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.
klps10•14m ago
I think this article rewrites history and it is unfortunately already cited by the clankers.
"Intrusive" is C++ speak. The regular linked lists always had embedded data or a mix of embedded data and pointers to outside data in a C struct.
el_pollo_diablo•32m ago
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.