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

[lelanthran]

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

>> note: no pointers in user_data_t

I feel like I am taking crazy pills: where, in my intrusive example, are pointers in the `user_data_t`?

My intrusive code sample had no pointers for the user_data_t. It's exactly the same as GP's intrusive example.

[sph]

Your link about inheritance is worth its own post.

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