Linked list start and end

Posted Sep 16, 2022 7:49 UTC (Fri) by epa (subscriber, #39769)
Parent article: The perils of pinning

As an example, initializing a list_head structure to indicate an empty list is done by setting both the next and prev fields to point to the structure itself.

Why is this done? Wouldn't it make more sense to set these two fields to null?

Linked list start and end

Posted Sep 16, 2022 9:33 UTC (Fri) by rvolgers (guest, #63218) [Link] (4 responses)

The list_head structure implements a circularly linked list, meaning it can be iterated fully starting from any node in the list. That means that if you want to loop over the whole list, you loop until you are back at the node you started. Logically this means a list of size 1 will contain a list_head where both prev and next point to the node itself.

Linked list start and end

Posted Sep 16, 2022 11:01 UTC (Fri) by mathstuf (subscriber, #69389) [Link] (3 responses)

> Logically this means a list of size 1 will contain a list_head where both prev and next point to the node itself.

But per the article, that's how an *empty* list is indicated. What is the actual encoding for a linked list of length 1?

Linked list start and end

Posted Sep 16, 2022 11:12 UTC (Fri) by Wol (subscriber, #4433) [Link] (1 responses)

An empty list clearly contains ONE null entry.

So, and I'm GUESSING, a list with one value contains one entry with the value, and one null entry.

iiuc, this is how it knows where the head of the list is - it's the null entry.

Cheers,
Wol

Linked list start and end

Posted Sep 16, 2022 23:14 UTC (Fri) by wahern (subscriber, #37304) [Link]

NULL isn't used as a sentinel for this type of list, the head itself is the sentinel. See, e.g., https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/linux/list.h?h=v6.0-rc5#n290

static inline int list_empty(const struct list_head *head)
{
	return READ_ONCE(head->next) == head;
}

and https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/linux/list.h?h=v6.0-rc5#n368

static inline int list_is_singular(const struct list_head *head)
{
	return !list_empty(head) && (head->next == head->prev);
}

Linked list start and end

Posted Sep 17, 2022 2:46 UTC (Sat) by ejr (subscriber, #51652) [Link]

Consider a list with entries being added atomically. If you start walking from a pointer X and return to the pointer X, you are done walking the entries that existed when you started as well as some of those added before you were finished.

Removals / deletions remain the pain point. Hence the RCU mechanisms.