Kernel Linked Lists (list_splice)

[Jeff Haran]

-----Original Message-----
From: kernelnewbies-bounces at kernelnewbies.org [mailto:kernelnewbies-bounces at kernelnewbies.org] On Behalf Of Leandro M Barbosa
Sent: Wednesday, March 25, 2015 2:41 PM
To: kernelnewbies at kernelnewbies.org
Subject: Re: Kernel Linked Lists (list_splice)

To clarify my doubt, it seems to me that it just sits there in memory without it being referenced anymore, is that right?

On Wed, Mar 25, 2015 at 6:38 PM, Leandro M Barbosa <lbarbosa at linux.com> wrote:
> Hello all!
>
> I was reading the __list_splice () function code and I had a doubt. The code is:
>
> 274 static inline void __list_splice(const struct list_head *list,
> 275                                  struct list_head *prev,
> 276                                  struct list_head *next)
> 277 {
> 278         struct list_head *first = list->next;
> 279         struct list_head *last = list->prev;
> 280
> 281         first->prev = prev;
> 282         prev->next = first;
> 283
> 284         last->next = next;
> 285         next->prev = last;
> 286 }
>
> What happens with the *list head? As I understood, when you call 
> list_splice (list_a, list_b, list_b->next), the code joins the two 
> lists together such that the list_a is put before list_b. The code 
> grabs list->next and list->prev but what about *list itself?
>
>
> --
> Leandro Moreira Barbosa

The linked list API represented in list.h allows the creation of linked lists in which a list of structures containing instances of struct list_head can be linked together and anchored by an instance of a struct list_head which is not a member of the structures in the list. Sometimes that anchor is a standalone instance of struct list_head. Other times it's an instance of list_head in another structure, for example:

struct foo {
	int data;
	struct list_head list;
};

struct bar {
	int other_data;
	struct list_head foo_list;
};

With the above you'd create a linked list of struct foos that is anchored (or headed) by the foo_list field in an instance of struct bar.

That means that when you splice the list of foos in one instance of bar A to the list of foos in another instance of bar B, you don't want to include the foo_list in the A in the list in B since it's not contained in a foo, but another bar.

This is different than the traditional linked lists that they taught me back in the stone age when I took CS101, but it enables a single object to be included in many lists.

Jeff Haran