Intrusive linked lists (2019)

Join the discussion

• Hacker News
• Now try to do them in safe Rust.
  by amelius
• Another benefit the article doesn't mention: these intrusive lists seem a good soft defense against use-after-free bugs in C. The node struct knows about all containers to which it belongs, so writing the "destructor" is very local. With the pointer array equivalent, one can only identify the arrays that point to the object by understanding the surrounding codebase.

  (Disclaimer: I am not speaking from experience here. My C background is mostly static allocation.)

  by blt
• Waiter, waiter! More optimization articles without benchmarks, please!
  by eventualcomp
• Doubly-linked lists -all data structures that have back pointers- are really difficult to mutate thread-safely.
  by cryptonector
• Is this sort of thing no longer part of a standard computer science or software engineering undergrad curriculum?
  by zahlman
• Hmm interesting, the doubly linked list presented here is missing the elegant 'overlapped list header' trick from AmigaOS (at least that's where I saw it first):

  E.g. an AmigaOS list node looks conventional, it has two pointers, one to the next node (succ), and one to the previous node (pred):

      struct Node {
          struct Node* ln_Succ;
          struct Node* ln_Pred;
      };
  

  Most AmigaOS structs embed such a Node struct at the start.

  ...but the list header has three pointers which basically form two overlapped Node structs:

      struct List {
          struct Node* lh_Head;
          struct Node* lh_Tail;
          struct Node* lh_TailPred;
      };
  

  In an empty list, lh_Head points to &lh_Tail, and lh_TailPred points to &lh_Head. The lh_Tail pointer is always null (this is the 'end marker').

  In a populated list, lh_Head points to the embedded Node struct of the first list node, and lh_TailPred points to the embedded Node struct of the last list node. The ln_Succ pointer of the last node points to the address of the list header's lh_Tail pointer (...which is always null).

  That way you only need an existing node pointer to walk forward and backward, or insert or remove a node. When walking the list by following the succ or pred pointers you know you've reached the end when encountering a null pointer.

  Apparently the Linux-style lists in the article require to know the address of the list header to detect when the end is reached which isn't needed for the Amiga style list (at the cost of an additional 'sentinel null pointer' in the list header).

  Pretty much all of AmigaOS was held together by such doubly linked lists.

  (I hope I got that all right, it's been a long time)

  by flohofwoe
• I was surprised to see the main benefit of intrusive linking mentioned as a bit of a side note: The ability to move data around between lists (and within a list) without copying. You also get O(1) removal from the middle of the list, assuming you have a pointer to the object somewhere else. As a result, when you have large state structs and you don't do a lot of list scans, intrusive linking makes things a lot faster than use of packed structures like vectors.
  by pclmulqdq
• 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.

  by el_pollo_diablo