clinuxlinked-listlinux-kernellockless

Why does Linux kernel lock-less list have head and node structs?

I'm trying to understand the lock-less list in the Linux kernel. This is defined in llist.h. Why do they have two structs, to define a list:

struct llist_head {
    struct llist_node *first;
};

struct llist_node {
    struct llist_node *next;
};

Why not have just one struct that has a pointer to the next node? It would similar to the doubly linked list implementation in the kernel.

Solution

  • Why do they have two structs, to define a list?

    Because it is possible to use different struct (types) for different things (head and node correspondingly). Linux kernel tends to follow same convensions as for usual programming.

    In case of double linked lists, both head and node are forced to have the same type: by design, both next and prev fields of struct list_head may point either to node or to the head. Single type for them is not an advantage, but necessity.