[flohofwoe]

It's not at all unusual for intrusive linked lists though?

On AmigaOS (which is entirely built out of intrusive doubly linked list) the list node is placed at the start of a struct, so the pointer to the node is also the pointer to the linked item. There's also no 'coupling' because the list manipulation functions take pointers to the list node structs, but they don't need to know the 'outer' item struct.

Zig's @fieldParentPtr is more flexible since the node struct can be anywhere in the parent struct and you still can get from the node pointer to the item base pointer (and more importantly, it makes it trivial to link the same item into multiple linked lists).

[Joker_vD]

It's not unusual at all, it's just... should it be exposed? I personally prefer having "Node struct with next pointer + inlined generic data" design when it can be encapsulated away since, well, it can be encapsulated away, and the result data layout is the same. And when you expose this design, well, you end with all sorts of disasters, including OOP inheritance (no, really: [0]).

[0] https://catern.com/inheritance.html

[flohofwoe]

If the node embeds the data item you can't link the item into multiple linked lists, but if the data item embeds the node(s) suddenly that's trivial.

I don't know if this was the motiviation for the design change though, but IMHO intrusive linked list are the 'proper' linked list design, and C++-style "nodes with payload" are a weird outlier.

Another reason might be that generic code leads to a lot of code duplication in the binary (which may or may not be optimized away by the compiler though - but at the cost of increased build times though).

[lelanthran]

> If the node embeds the data item you can't link the item into multiple linked lists, but if the data item embeds the node(s) suddenly that's trivial.

Perhaps I'm missing something, but isn't it the other way around? In C, this is what I'd expect for the intrusive and extrusive:

    // Intrusive
    struct user_data_t {
       struct user_data_t *next;
       struct user_data_t *prev;
       // The object's fields
    };

    // Extrusive
    struct node_t {
       struct node_t *next;
       struct node_t *prev;
       struct user_data_t *payload;
    };

The intrusive one obviously can't be shared between lists.

[flohofwoe]

No, intrusive would be (note: no pointers in user_data_t):

    typedef struct { node_t* next } node_t;

    typedef struct { ... } payload_t;

    typedef struct {
        node_t node;
        payload_t payload;
    } user_data_t;

...and if you want user_data_t to be included into multiple lists:

    typedef struct {
        node_t list1_node;
        node_t list2_node;
        node_t list3_node;
        payload_t payload;
    } user_data_t;

...of course in C now it gets tricky to get to the start of user_data_t given a pointer to `list3_node`, but that's where @fieldParentPtr comes in.

The advantage versus your extrusive example is that the payload doesn't need to be referenced through a pointer, which drastically simplifies lifetime tracking / memory management.

[lelanthran]

> No, intrusive would be (note: no pointers in user_data_t):

    typedef struct { node_t* next } node_t;

    typedef struct { ... } payload_t;

    typedef struct {
        node_t node;
        payload_t payload;
    } user_data_t;

That's exactly the same as my intrusive structure, no?

> typedef struct { node_t list1_node; node_t list2_node; node_t list3_node; payload_t payload; } user_data_t;

In C, at any rate, that doesn't give you "inclusion into multiple lists". It gives you "inclusion into at most 3 lists. The extrusive example I posted gives "inclusion into multiple lists".

So, yeah, I'm still not seeing your point.

[Zambyte]

> That's exactly the same as my intrusive structure, no?

It's not, for the reason they put in parentheses:

> note: no pointers in user_data_t

An allocation of user_data_t also allocates space for payload_t, rather than just allocating space for a pointer to payload_t. Your structure requires an additional allocation to point the payload_t* at something. The fact that they hid the next node_t* in a struct doesn't matter though.

[sph]

Your link about inheritance is worth its own post.

EDIT: Previously: https://news.ycombinator.com/item?id=26988839

[codr7]

This approach is also common in C:

https://github.com/codr7/hacktical-c/tree/main/list

One pretty big advantage is you get some help from the compiler making sure you mean what you say. As opposed to just blindly casting items and assuming no one forgot to put the list in their struct. Also the possibility to be part of multiple lists.