4 ms·

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

• flohofwoe 2y ago
  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 2y ago
    > 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 2y ago
      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 2y ago
        > 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 2y ago
          > 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 2y ago
            > 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.
            • Zambyte 2y ago
              It is not you that is crazy, I have been exhausted. My bad.
• sph 2y ago
  Your link about inheritance is worth its own post. EDIT: Previously: https://news.ycombinator.com/item?id=26988839 https://news.ycombinator.com/item?id=26988839