4 ms·

There's also the method used in the Linux kernel to embed the list information (struct list_head) within the type specific struct. https://kernelnewbies.org/FAQ

There's also the method used in the Linux kernel to embed the list information (struct list_head) within the type specific struct. https://kernelnewbies.org/FAQ/LinkedLists https://kernelnewbies.org/FAQ/LinkedLists

nixpulvis 1y ago
The naming of LIST_HEAD_INIT and INIT_LIST_HEAD is confusing to me.
- mfuzzey 1y ago
  The way I remember it is: INIT_LIST_HEAD is of form VERB_NOUN so is called from within a function to programatically initialise the list. LIST_HEAD_INIT is NOUN_VERB and is used within a structure initialiser not from a function. But my main point was to show the "embed the list in the data" approach rather than "embed the data in the list" or "point to the data from the list" and not to discuss the naming details in the kernel implementation of the concept.
- el_pollo_diablo 1y ago
  Not to mention that they insist on calling every entry of the list a "list head", which makes no sense (hysterical raisins, maybe?). The structure is made of a uniform loop of entries, one of which is used as the actual head & tail, or entry point into the structure.
  - RustyRussell 1y ago
    Yes, it's terrible, and the fact that their list_add takes parameters backwards from what one might expect, with no types to catch mistakes! See https://github.com/rustyrussell/ccan/blob/master/ccan/list/_info https://github.com/rustyrussell/ccan/blob/master/ccan/list/_...
    - el_pollo_diablo 1y ago
      Absolutely. Wrapping the distinguished entry point in a new structure type equipped with a thin type-safe wrapper API that covers the most common use case is the way to go.
  - antonvs 1y ago
    In general, there is no “actual” head and tail - you could have multiple references to different parts of the list, and each of them would have a different head. If you’re recursing through a list, at some point every node will be used as the head. This is a common pattern in recursive data structures, particularly in functional languages. Disclaimer: I haven’t looked at this author’s code, just pointing out that list nodes that consist of (head, tail) are a common pattern with a clear rationale.
    - el_pollo_diablo 1y ago
      Head and tail make sense for persistent lists in functional languages with value semantics, yes. The intrusive, mutable, doubly-linked loops with reference semantics under discussion are quite different. Although all entries behave identically in the structure itself, one of them is _used_ differently, as a standalone anchor point, while the others are embedded in the list's "elements".
  - deleted 1y ago
    [deleted]

nixpulvis 1y ago

The naming of LIST_HEAD_INIT and INIT_LIST_HEAD is confusing to me.

mfuzzey 1y ago
The way I remember it is: INIT_LIST_HEAD is of form VERB_NOUN so is called from within a function to programatically initialise the list. LIST_HEAD_INIT is NOUN_VERB and is used within a structure initialiser not from a function. But my main point was to show the "embed the list in the data" approach rather than "embed the data in the list" or "point to the data from the list" and not to discuss the naming details in the kernel implementation of the concept.
el_pollo_diablo 1y ago
Not to mention that they insist on calling every entry of the list a "list head", which makes no sense (hysterical raisins, maybe?). The structure is made of a uniform loop of entries, one of which is used as the actual head & tail, or entry point into the structure.
- RustyRussell 1y ago
  Yes, it's terrible, and the fact that their list_add takes parameters backwards from what one might expect, with no types to catch mistakes! See https://github.com/rustyrussell/ccan/blob/master/ccan/list/_info https://github.com/rustyrussell/ccan/blob/master/ccan/list/_...
  - el_pollo_diablo 1y ago
    Absolutely. Wrapping the distinguished entry point in a new structure type equipped with a thin type-safe wrapper API that covers the most common use case is the way to go.
- antonvs 1y ago
  In general, there is no “actual” head and tail - you could have multiple references to different parts of the list, and each of them would have a different head. If you’re recursing through a list, at some point every node will be used as the head. This is a common pattern in recursive data structures, particularly in functional languages. Disclaimer: I haven’t looked at this author’s code, just pointing out that list nodes that consist of (head, tail) are a common pattern with a clear rationale.
  - el_pollo_diablo 1y ago
    Head and tail make sense for persistent lists in functional languages with value semantics, yes. The intrusive, mutable, doubly-linked loops with reference semantics under discussion are quite different. Although all entries behave identically in the structure itself, one of them is _used_ differently, as a standalone anchor point, while the others are embedded in the list's "elements".
- deleted 1y ago
  [deleted]