Linked Lists in Linux ¶

Author:: Nicolas Frattaroli <nicolas.frattaroli@collabora.com>

Introduction ¶

Linked lists are one of the most basic data structures used in many programs.The Linux kernel implements several different flavours of linked lists. Thepurpose of this document is not to explain linked lists in general, but to shownew kernel developers how to use the Linux kernel implementations of linkedlists.

Please note that while linked lists certainly are ubiquitous, they are rarelythe best data structure to use in cases where a simple array doesn’t alreadysuffice. In particular, due to their poor data locality, linked lists are a badchoice in situations where performance may be of consideration. Familiarizingoneself with other in-kernel generic data structures, especially for concurrentaccesses, is highly encouraged.

Linux implementation of doubly linked lists ¶

Linux’s linked list implementations can be used by including the header file<linux/list.h>.

The doubly-linked list will likely be the most familiar to many readers. It’s alist that can efficiently be traversed forwards and backwards.

The Linux kernel’s doubly-linked list is circular in nature. This means that toget from the head node to the tail, we can just travel one edge backwards.Similarly, to get from the tail node to the head, we can simply travel forwards“beyond” the tail and arrive back at the head.

Declaring a node ¶

A node in a doubly-linked list is declared by adding astructlist_headmember to the data structure you wish to be contained in the list:

structclown{unsignedlonglongshoe_size;constchar*name;structlist_headnode;/* the aforementioned member */};

This may be an unfamiliar approach to some, as the classical explanation of alinked list is a list node data structure with pointers to the previous and nextlist node, as well the payload data. Linux chooses this approach because itallows for generic list modification code regardless of what data structure iscontained within the list. Since thestructlist_head member is not a pointerbut part of the data structure proper, thecontainer_of() pattern can be used bythe list implementation to access the payload data regardless of its type, whilestaying oblivious to what said type actually is.

Declaring and initializing a list ¶

A doubly-linked list can then be declared as just anotherstructlist_head,and initialized with theLIST_HEAD_INIT() macro during initial assignment, orwith theINIT_LIST_HEAD() function later:

structclown_car{inttyre_pressure[4];structlist_headclowns;/* Looks like a node! */};/* ... Somewhere later in our driver ... */staticintcircus_init(structcircus_priv*circus){structclown_carother_car={.tyre_pressure={10,12,11,9},.clowns=LIST_HEAD_INIT(other_car.clowns)};INIT_LIST_HEAD(&circus->car.clowns);return0;}

A further point of confusion to some may be that the list itself doesn’t reallyhave its own type. The concept of the entire linked list and astructlist_head member that points to other entries in the list are one andthe same.

Adding nodes to the list ¶

Adding a node to the linked list is done through thelist_add() macro.

We’ll return to our clown car example to illustrate how nodes get added to thelist:

staticintcircus_fill_car(structcircus_priv*circus){structclown_car*car=&circus->car;structclown*grock;structclown*dimitri;/* State 1 */grock=kzalloc(sizeof(*grock),GFP_KERNEL);if(!grock)return-ENOMEM;grock->name="Grock";grock->shoe_size=1000;/* Note that we're adding the "node" member */list_add(&grock->node,&car->clowns);/* State 2 */dimitri=kzalloc(sizeof(*dimitri),GFP_KERNEL);if(!dimitri)return-ENOMEM;dimitri->name="Dimitri";dimitri->shoe_size=50;list_add(&dimitri->node,&car->clowns);/* State 3 */return0;}

In State 1, our list of clowns is still empty:

     .------.     v      |.--------.  || clowns |--''--------'

This diagram shows the singular “clowns” node pointing at itself. In thisdiagram, and all following diagrams, only the forward edges are shown, to aid inclarity.

In State 2, we’ve added Grock after the list head:

     .--------------------.     v                    |.--------.     .-------.  || clowns |---->| Grock |--''--------'     '-------'

This diagram shows the “clowns” node pointing at a new node labeled “Grock”.The Grock node is pointing back at the “clowns” node.

In State 3, we’ve added Dimitri after the list head, resulting in the following:

     .------------------------------------.     v                                    |.--------.     .---------.     .-------.  || clowns |---->| Dimitri |---->| Grock |--''--------'     '---------'     '-------'

This diagram shows the “clowns” node pointing at a new node labeled “Dimitri”,which then points at the node labeled “Grock”. The “Grock” node still pointsback at the “clowns” node.

If we wanted to have Dimitri inserted at the end of the list instead, we’d uselist_add_tail(). Our code would then look like this:

staticintcircus_fill_car(structcircus_priv*circus){/* ... */list_add_tail(&dimitri->node,&car->clowns);/* State 3b */return0;}

This results in the following list:

     .------------------------------------.     v                                    |.--------.     .-------.     .---------.  || clowns |---->| Grock |---->| Dimitri |--''--------'     '-------'     '---------'

This diagram shows the “clowns” node pointing at the node labeled “Grock”,which points at the new node labeled “Dimitri”. The node labeled “Dimitri”points back at the “clowns” node.

Traversing the list ¶

To iterate the list, we can loop through all nodes within the list withlist_for_each().

In our clown example, this results in the following somewhat awkward code:

staticunsignedlonglongcircus_get_max_shoe_size(structcircus_priv*circus){unsignedlonglongres=0;structclown*e;structlist_head*cur;list_for_each(cur,&circus->car.clowns){e=list_entry(cur,structclown,node);if(e->shoe_size>res)res=e->shoe_size;}returnres;}

Thelist_entry() macro internally uses the aforementionedcontainer_of() toretrieve the data structure instance thatnode is a member of.

Note how the additionallist_entry() call is a little awkward here. It’s onlythere because we’re iterating through thenode members, but we really wantto iterate through the payload, i.e. thestructclown that contains eachnode’sstructlist_head. For this reason, there is a second macro:list_for_each_entry()

Using it would change our code to something like this:

staticunsignedlonglongcircus_get_max_shoe_size(structcircus_priv*circus){unsignedlonglongres=0;structclown*e;list_for_each_entry(e,&circus->car.clowns,node){if(e->shoe_size>res)res=e->shoe_size;}returnres;}

This eliminates the need for thelist_entry() step, and our loop cursor is nowof the type of our payload. The macro is given the member name that correspondsto the list’sstructlist_head within the clown data structure so that it canstill walk the list.

Removing nodes from the list ¶

Thelist_del() function can be used to remove entries from the list. It not onlyremoves the given entry from the list, but poisons the entry’sprev andnext pointers, so that unintended use of the entry after removal does notgo unnoticed.

We can extend our previous example to remove one of the entries:

staticintcircus_fill_car(structcircus_priv*circus){/* ... */list_add(&dimitri->node,&car->clowns);/* State 3 */list_del(&dimitri->node);/* State 4 */return0;}

The result of this would be this:

     .--------------------.     v                    |.--------.     .-------.  |      .---------.| clowns |---->| Grock |--'      | Dimitri |'--------'     '-------'         '---------'

This diagram shows the “clowns” node pointing at the node labeled “Grock”,which points back at the “clowns” node. Off to the side is a lone node labeled“Dimitri”, which has no arrows pointing anywhere.

Note how the Dimitri node does not point to itself; its pointers areintentionally set to a “poison” value that the list code refuses to traverse.

If we wanted to reinitialize the removed node instead to make it point at itselfagain like an empty list head, we can uselist_del_init() instead:

staticintcircus_fill_car(structcircus_priv*circus){/* ... */list_add(&dimitri->node,&car->clowns);/* State 3 */list_del_init(&dimitri->node);/* State 4b */return0;}

This results in the deleted node pointing to itself again:

     .--------------------.           .-------.     v                    |           v       |.--------.     .-------.  |      .---------.  || clowns |---->| Grock |--'      | Dimitri |--''--------'     '-------'         '---------'

This diagram shows the “clowns” node pointing at the node labeled “Grock”,which points back at the “clowns” node. Off to the side is a lone node labeled“Dimitri”, which points to itself.

Traversing whilst removing nodes ¶

Deleting entries while we’re traversing the list will cause problems if we uselist_for_each() andlist_for_each_entry(), as deleting the current entry wouldmodify thenext pointer of it, which means the traversal can’t properlyadvance to the next list entry.

There is a solution to this however:list_for_each_safe() andlist_for_each_entry_safe(). These take an additional parameter of a pointer toastructlist_head to use as temporary storage for the next entry duringiteration, solving the issue.

An example of how to use it:

staticvoidcircus_eject_insufficient_clowns(structcircus_priv*circus){structclown*e;structclown*n;/* temporary storage for safe iteration */list_for_each_entry_safe(e,n,&circus->car.clowns,node){if(e->shoe_size<500)list_del(&e->node);}}

Proper memory management (i.e. freeing the deleted node while making surenothing still references it) in this case is left as an exercise to the reader.

Cutting a list ¶

There are two helper functions to cut lists with. Both take elements from thelisthead, and replace the contents of the listlist.

The first such function islist_cut_position(). It removes all list entries fromhead up to and includingentry, placing them inlist instead.

In this example, it’s assumed we start with the following list:

     .----------------------------------------------------------------.     v                                                                |.--------.     .-------.     .---------.     .-----.     .---------.  || clowns |---->| Grock |---->| Dimitri |---->| Pic |---->| Alfredo |--''--------'     '-------'     '---------'     '-----'     '---------'

With the following code, every clown up to and including “Pic” is moved fromthe “clowns” list head to a separatestructlist_head initialized at localstack variableretirement:

staticvoidcircus_retire_clowns(structcircus_priv*circus){structlist_headretirement=LIST_HEAD_INIT(retirement);structclown*grock,*dimitri,*pic,*alfredo;structclown_car*car=&circus->car;/* ... clown initialization, list adding ... */list_cut_position(&retirement,&car->clowns,&pic->node);/* State 1 */}

The resultingcar->clowns list would be this:

     .----------------------.     v                      |.--------.     .---------.  || clowns |---->| Alfredo |--''--------'     '---------'

Meanwhile, theretirement list is transformed to the following:

       .--------------------------------------------------.       v                                                  |.------------.     .-------.     .---------.     .-----.  || retirement |---->| Grock |---->| Dimitri |---->| Pic |--''------------'     '-------'     '---------'     '-----'

The second function,list_cut_before(), is much the same, except it cuts beforetheentry node, i.e. it removes all list entries fromhead up to butexcludingentry, placing them inlist instead. This example assumes thesame initial starting list as the previous example:

staticvoidcircus_retire_clowns(structcircus_priv*circus){structlist_headretirement=LIST_HEAD_INIT(retirement);structclown*grock,*dimitri,*pic,*alfredo;structclown_car*car=&circus->car;/* ... clown initialization, list adding ... */list_cut_before(&retirement,&car->clowns,&pic->node);/* State 1b */}

The resultingcar->clowns list would be this:

     .----------------------------------.     v                                  |.--------.     .-----.     .---------.  || clowns |---->| Pic |---->| Alfredo |--''--------'     '-----'     '---------'

Meanwhile, theretirement list is transformed to the following:

       .--------------------------------------.       v                                      |.------------.     .-------.     .---------.  || retirement |---->| Grock |---->| Dimitri |--''------------'     '-------'     '---------'

It should be noted that both functions will destroy links to any existing nodesin the destinationstructlist_head*list.

Moving entries and partial lists ¶

Thelist_move() andlist_move_tail() functions can be used to move an entryfrom one list to another, to either the start or end respectively.

In the following example, we’ll assume we start with two lists (“clowns” and“sidewalk” in the following initial state “State 0”:

     .----------------------------------------------------------------.     v                                                                |.--------.     .-------.     .---------.     .-----.     .---------.  || clowns |---->| Grock |---->| Dimitri |---->| Pic |---->| Alfredo |--''--------'     '-------'     '---------'     '-----'     '---------'      .-------------------.      v                   |.----------.     .-----.  || sidewalk |---->| Pio |--''----------'     '-----'

We apply the following example code to the two lists:

staticvoidcircus_clowns_exit_car(structcircus_priv*circus){structlist_headsidewalk=LIST_HEAD_INIT(sidewalk);structclown*grock,*dimitri,*pic,*alfredo,*pio;structclown_car*car=&circus->car;/* ... clown initialization, list adding ... *//* State 0 */list_move(&pic->node,&sidewalk);/* State 1 */list_move_tail(&dimitri->node,&sidewalk);/* State 2 */}

In State 1, we arrive at the following situation:

    .-----------------------------------------------------.    |                                                     |    v                                                     |.--------.     .-------.     .---------.     .---------.  || clowns |---->| Grock |---->| Dimitri |---->| Alfredo |--''--------'     '-------'     '---------'     '---------'      .-------------------------------.      v                               |.----------.     .-----.     .-----.  || sidewalk |---->| Pic |---->| Pio |--''----------'     '-----'     '-----'

In State 2, after we’ve moved Dimitri to the tail of sidewalk, the situationchanges as follows:

    .-------------------------------------.    |                                     |    v                                     |.--------.     .-------.     .---------.  || clowns |---->| Grock |---->| Alfredo |--''--------'     '-------'     '---------'      .-----------------------------------------------.      v                                               |.----------.     .-----.     .-----.     .---------.  || sidewalk |---->| Pic |---->| Pio |---->| Dimitri |--''----------'     '-----'     '-----'     '---------'

As long as the source and destination list head are part of the same list, wecan also efficiently bulk move a segment of the list to the tail end of thelist. We continue the previous example by adding alist_bulk_move_tail() afterState 2, moving Pic and Pio to the tail end of the sidewalk list.

staticvoidcircus_clowns_exit_car(structcircus_priv*circus){structlist_headsidewalk=LIST_HEAD_INIT(sidewalk);structclown*grock,*dimitri,*pic,*alfredo,*pio;structclown_car*car=&circus->car;/* ... clown initialization, list adding ... *//* State 0 */list_move(&pic->node,&sidewalk);/* State 1 */list_move_tail(&dimitri->node,&sidewalk);/* State 2 */list_bulk_move_tail(&sidewalk,&pic->node,&pio->node);/* State 3 */}

For the sake of brevity, only the altered “sidewalk” list at State 3 is depictedin the following diagram:

      .-----------------------------------------------.      v                                               |.----------.     .---------.     .-----.     .-----.  || sidewalk |---->| Dimitri |---->| Pic |---->| Pio |--''----------'     '---------'     '-----'     '-----'

Do note thatlist_bulk_move_tail() does not do any checking as to whether allthree suppliedstructlist_head* parameters really do belong to the samelist. If you use it outside the constraints the documentation gives, then theresult is a matter between you and the implementation.

Rotating entries ¶

A common write operation on lists, especially when using them as queues, isto rotate it. A list rotation means entries at the front are sent to the back.

For rotation, Linux provides us with two functions:list_rotate_left() andlist_rotate_to_front(). The former can be pictured like a bicycle chain, takingthe entry after the suppliedstructlist_head* and moving it to the tail,which in essence means the entire list, due to its circular nature, rotates byone position.

The latter,list_rotate_to_front(), takes the same concept one step further:instead of advancing the list by one entry, it advances ituntil the specifiedentry is the new front.

In the following example, our starting state, State 0, is the following:

     .-----------------------------------------------------------------.     v                                                                 |.--------.   .-------.   .---------.   .-----.   .---------.   .-----. || clowns |-->| Grock |-->| Dimitri |-->| Pic |-->| Alfredo |-->| Pio |-''--------'   '-------'   '---------'   '-----'   '---------'   '-----'

The example code being used to demonstrate list rotations is the following:

staticvoidcircus_clowns_rotate(structcircus_priv*circus){structclown*grock,*dimitri,*pic,*alfredo,*pio;structclown_car*car=&circus->car;/* ... clown initialization, list adding ... *//* State 0 */list_rotate_left(&car->clowns);/* State 1 */list_rotate_to_front(&alfredo->node,&car->clowns);/* State 2 */}

In State 1, we arrive at the following situation:

     .-----------------------------------------------------------------.     v                                                                 |.--------.   .---------.   .-----.   .---------.   .-----.   .-------. || clowns |-->| Dimitri |-->| Pic |-->| Alfredo |-->| Pio |-->| Grock |-''--------'   '---------'   '-----'   '---------'   '-----'   '-------'

Next, after thelist_rotate_to_front() call, we arrive in the followingState 2:

     .-----------------------------------------------------------------.     v                                                                 |.--------.   .---------.   .-----.   .-------.   .---------.   .-----. || clowns |-->| Alfredo |-->| Pio |-->| Grock |-->| Dimitri |-->| Pic |-''--------'   '---------'   '-----'   '-------'   '---------'   '-----'

As is hopefully evident from the diagrams, the entries in front of “Alfredo”were cycled to the tail end of the list.

Swapping entries ¶

Another common operation is that two entries need to be swapped with each other.

For this, Linux provides us withlist_swap().

In the following example, we have a list with three entries, and swap two ofthem. This is our starting state in “State 0”:

     .-----------------------------------------.     v                                         |.--------.   .-------.   .---------.   .-----. || clowns |-->| Grock |-->| Dimitri |-->| Pic |-''--------'   '-------'   '---------'   '-----'

staticvoidcircus_clowns_swap(structcircus_priv*circus){structclown*grock,*dimitri,*pic;structclown_car*car=&circus->car;/* ... clown initialization, list adding ... *//* State 0 */list_swap(&dimitri->node,&pic->node);/* State 1 */}

The resulting list at State 1 is the following:

     .-----------------------------------------.     v                                         |.--------.   .-------.   .-----.   .---------. || clowns |-->| Grock |-->| Pic |-->| Dimitri |-''--------'   '-------'   '-----'   '---------'

As is evident by comparing the diagrams, the “Pic” and “Dimitri” nodes havetraded places.

Splicing two lists together ¶

Say we have two lists, in the following example one represented by a list headwe call “knie” and one we call “stey”. In a hypothetical circus acquisition,the two list of clowns should be spliced together. The following is oursituation in “State 0”:

    .-----------------------------------------.    |                                         |    v                                         |.------.   .-------.   .---------.   .-----.  || knie |-->| Grock |-->| Dimitri |-->| Pic |--''------'   '-------'   '---------'   '-----'    .-----------------------------.    v                             |.------.   .---------.   .-----.  || stey |-->| Alfredo |-->| Pio |--''------'   '---------'   '-----'

The function to splice these two lists together islist_splice(). Our examplecode is as follows:

staticvoidcircus_clowns_splice(void){structclown*grock,*dimitri,*pic,*alfredo,*pio;structlist_headknie=LIST_HEAD_INIT(knie);structlist_headstey=LIST_HEAD_INIT(stey);/* ... Clown allocation and initialization here ... */list_add_tail(&grock->node,&knie);list_add_tail(&dimitri->node,&knie);list_add_tail(&pic->node,&knie);list_add_tail(&alfredo->node,&stey);list_add_tail(&pio->node,&stey);/* State 0 */list_splice(&stey,&dimitri->node);/* State 1 */}

Thelist_splice() call here adds all the entries instey to the listdimitri’snode list_head is in, after thenode ofdimitri. Asomewhat surprising diagram of the resulting “State 1” follows:

    .-----------------------------------------------------------------.    |                                                                 |    v                                                                 |.------.   .-------.   .---------.   .---------.   .-----.   .-----.  || knie |-->| Grock |-->| Dimitri |-->| Alfredo |-->| Pio |-->| Pic |--''------'   '-------'   '---------'   '---------'   '-----'   '-----'                                          ^          .-------------------------------'          |.------.  || stey |--''------'

Traversing thestey list no longer results in correct behavior. A call oflist_for_each() onstey results in an infinite loop, as it never returnsback to thestey list head.

This is becauselist_splice() did not reinitialize the list_head it tookentries from, leaving its pointer pointing into what is now a different list.

If we want to avoid this situation,list_splice_init() can be used. It does thesame thing aslist_splice(), except reinitalizes the donor list_head after thetransplant.

Concurrency considerations ¶

Concurrent access and modification of a list needs to be protected with a lockin most cases. Alternatively and preferably, one may use the RCU primitives forlists in read-mostly use-cases, where read accesses to the list are common butmodifications to the list less so. SeeUsing RCU to Protect Read-Mostly Linked Lists for moredetails.

Full List API ¶

LIST_HEAD_INIT¶

LIST_HEAD_INIT(name)

initialize astructlist_head’s links to point to itself

Parameters

name: name of the list_head

LIST_HEAD¶

LIST_HEAD(name)

definition of astructlist_head with initialization values

Parameters

name: name of the list_head

voidINIT_LIST_HEAD(structlist_head*list)¶: Initialize a list_head structure

Parameters

structlist_head*list: list_head structure to be initialized.

Description

Initializes the list_head to point to itself. If it is a list header,the result is an empty list.

voidlist_add(structlist_head*new,structlist_head*head)¶: add a new entry

Parameters

structlist_head*new: new entry to be added
structlist_head*head: list head to add it after

Description

Insert a new entry after the specified head.This is good for implementing stacks.

voidlist_add_tail(structlist_head*new,structlist_head*head)¶: add a new entry

Parameters

structlist_head*new: new entry to be added
structlist_head*head: list head to add it before

Description

Insert a new entry before the specified head.This is useful for implementing queues.

voidlist_del(structlist_head*entry)¶: deletes entry from list.

Parameters

structlist_head*entry: the element to delete from the list.

Note

list_empty() on entry does not return true after this, the entry isin an undefined state.

voidlist_replace(structlist_head*old,structlist_head*new)¶: replace old entry by new one

Parameters

structlist_head*old: the element to be replaced
structlist_head*new: the new element to insert

Description

Ifold was empty, it will be overwritten.

voidlist_replace_init(structlist_head*old,structlist_head*new)¶: replace old entry by new one and initialize the old one

Parameters

structlist_head*old: the element to be replaced
structlist_head*new: the new element to insert

Description

Ifold was empty, it will be overwritten.

voidlist_swap(structlist_head*entry1,structlist_head*entry2)¶: replace entry1 with entry2 and re-add entry1 at entry2’s position

Parameters

structlist_head*entry1: the location to place entry2
structlist_head*entry2: the location to place entry1

voidlist_del_init(structlist_head*entry)¶: deletes entry from list and reinitialize it.

Parameters

structlist_head*entry: the element to delete from the list.

voidlist_move(structlist_head*list,structlist_head*head)¶: delete from one list and add as another’s head

Parameters

structlist_head*list: the entry to move
structlist_head*head: the head that will precede our entry

voidlist_move_tail(structlist_head*list,structlist_head*head)¶: delete from one list and add as another’s tail

Parameters

structlist_head*list: the entry to move
structlist_head*head: the head that will follow our entry

voidlist_bulk_move_tail(structlist_head*head,structlist_head*first,structlist_head*last)¶: move a subsection of a list to its tail

Parameters

structlist_head*head: the head that will follow our entry
structlist_head*first: first entry to move
structlist_head*last: last entry to move, can be the same as first

Description

Move all entries betweenfirst and includinglast beforehead.All three entries must belong to the same linked list.

intlist_is_first(conststructlist_head*list,conststructlist_head*head)¶

tests whetherlist is the first entry in listhead

Parameters

conststructlist_head*list: the entry to test
conststructlist_head*head: the head of the list

intlist_is_last(conststructlist_head*list,conststructlist_head*head)¶: tests whetherlist is the last entry in listhead

Parameters

conststructlist_head*list: the entry to test
conststructlist_head*head: the head of the list

intlist_is_head(conststructlist_head*list,conststructlist_head*head)¶: tests whetherlist is the listhead

Parameters

conststructlist_head*list: the entry to test
conststructlist_head*head: the head of the list

intlist_empty(conststructlist_head*head)¶: tests whether a list is empty

Parameters

conststructlist_head*head: the list to test.

voidlist_del_init_careful(structlist_head*entry)¶: deletes entry from list and reinitialize it.

Parameters

structlist_head*entry: the element to delete from the list.

Description

This is the same aslist_del_init(), except designed to be usedtogether withlist_empty_careful() in a way to guarantee orderingof other memory operations.

Any memory operations done before alist_del_init_careful() areguaranteed to be visible after alist_empty_careful() test.

intlist_empty_careful(conststructlist_head*head)¶: tests whether a list is empty and not being modified

Parameters

conststructlist_head*head: the list to test

Description

tests whether a list is empty _and_ checks that no other CPU might bein the process of modifying either member (next or prev)

NOTE

usinglist_empty_careful() without synchronizationcan only be safe if the only activity that can happento the list entry islist_del_init(). Eg. it cannot be usedif another CPU could re-list_add() it.

voidlist_rotate_left(structlist_head*head)¶: rotate the list to the left

Parameters

structlist_head*head: the head of the list

voidlist_rotate_to_front(structlist_head*list,structlist_head*head)¶: Rotate list to specific item.

Parameters

structlist_head*list: The desired new front of the list.
structlist_head*head: The head of the list.

Description

Rotates list so thatlist becomes the new front of the list.

intlist_is_singular(conststructlist_head*head)¶: tests whether a list has just one entry.

Parameters

conststructlist_head*head: the list to test.

voidlist_cut_position(structlist_head*list,structlist_head*head,structlist_head*entry)¶: cut a list into two

Parameters

structlist_head*list: a new list to add all removed entries
structlist_head*head: a list with entries
structlist_head*entry: an entry within head, could be the head itselfand if so we won’t cut the list

Description

This helper moves the initial part ofhead, up to andincludingentry, fromhead tolist. You shouldpass onentry an element you know is onhead.listshould be an empty list or a list you do not care aboutlosing its data.

voidlist_cut_before(structlist_head*list,structlist_head*head,structlist_head*entry)¶: cut a list into two, before given entry

Parameters

structlist_head*list: a new list to add all removed entries
structlist_head*head: a list with entries
structlist_head*entry: an entry within head, could be the head itself

Description

This helper moves the initial part ofhead, up to butexcludingentry, fromhead tolist. You should passinentry an element you know is onhead.list shouldbe an empty list or a list you do not care about losingits data.Ifentry ==head, all entries onhead are moved tolist.

voidlist_splice(conststructlist_head*list,structlist_head*head)¶: join two lists, this is designed for stacks

Parameters

conststructlist_head*list: the new list to add.
structlist_head*head: the place to add it in the first list.

voidlist_splice_tail(structlist_head*list,structlist_head*head)¶: join two lists, each list being a queue

Parameters

structlist_head*list: the new list to add.
structlist_head*head: the place to add it in the first list.

voidlist_splice_init(structlist_head*list,structlist_head*head)¶: join two lists and reinitialise the emptied list.

Parameters

structlist_head*list: the new list to add.
structlist_head*head: the place to add it in the first list.

Description

The list atlist is reinitialised

voidlist_splice_tail_init(structlist_head*list,structlist_head*head)¶: join two lists and reinitialise the emptied list

Parameters

structlist_head*list: the new list to add.
structlist_head*head: the place to add it in the first list.

Description

Each of the lists is a queue.The list atlist is reinitialised

list_entry¶

list_entry(ptr,type,member)

get the struct for this entry

Parameters

ptr: thestructlist_head pointer.
type: the type of thestructthis is embedded in.
member: the name of the list_head within the struct.

list_first_entry¶

list_first_entry(ptr,type,member)

get the first element from a list

Parameters

ptr: the list head to take the element from.
type: the type of thestructthis is embedded in.
member: the name of the list_head within the struct.

Description

Note, that list is expected to be not empty.

list_last_entry¶

list_last_entry(ptr,type,member)

get the last element from a list

Parameters

ptr: the list head to take the element from.
type: the type of thestructthis is embedded in.
member: the name of the list_head within the struct.

Description

Note, that list is expected to be not empty.

list_first_entry_or_null¶

list_first_entry_or_null(ptr,type,member)

get the first element from a list

Parameters

ptr: the list head to take the element from.
type: the type of thestructthis is embedded in.
member: the name of the list_head within the struct.

Description

Note that if the list is empty, it returns NULL.

list_last_entry_or_null¶

list_last_entry_or_null(ptr,type,member)

get the last element from a list

Parameters

ptr: the list head to take the element from.
type: the type of thestructthis is embedded in.
member: the name of the list_head within the struct.

Description

Note that if the list is empty, it returns NULL.

list_next_entry¶

list_next_entry(pos,member)

get the next element in list

Parameters

pos: the type * to cursor
member: the name of the list_head within the struct.

list_next_entry_circular¶

list_next_entry_circular(pos,head,member)

get the next element in list

Parameters

pos: the type * to cursor.
head: the list head to take the element from.
member: the name of the list_head within the struct.

Description

Wraparound if pos is the last element (return the first element).Note, that list is expected to be not empty.

list_prev_entry¶

list_prev_entry(pos,member)

get the prev element in list

Parameters

pos: the type * to cursor
member: the name of the list_head within the struct.

list_prev_entry_circular¶

list_prev_entry_circular(pos,head,member)

get the prev element in list

Parameters

pos: the type * to cursor.
head: the list head to take the element from.
member: the name of the list_head within the struct.

Description

Wraparound if pos is the first element (return the last element).Note, that list is expected to be not empty.

list_for_each¶

list_for_each(pos,head)

iterate over a list

Parameters

pos: thestructlist_head to use as a loop cursor.
head: the head for your list.

list_for_each_continue¶

list_for_each_continue(pos,head)

continue iteration over a list

Parameters

pos: thestructlist_head to use as a loop cursor.
head: the head for your list.

Description

Continue to iterate over a list, continuing after the current position.

list_for_each_prev¶

list_for_each_prev(pos,head)

iterate over a list backwards

Parameters

pos: thestructlist_head to use as a loop cursor.
head: the head for your list.

list_for_each_safe¶

list_for_each_safe(pos,n,head)

iterate over a list safe against removal of list entry

Parameters

pos: thestructlist_head to use as a loop cursor.
n: anotherstructlist_head to use as temporary storage
head: the head for your list.

list_for_each_prev_safe¶

list_for_each_prev_safe(pos,n,head)

iterate over a list backwards safe against removal of list entry

Parameters

pos: thestructlist_head to use as a loop cursor.
n: anotherstructlist_head to use as temporary storage
head: the head for your list.

size_tlist_count_nodes(structlist_head*head)¶: count nodes in the list

Parameters

structlist_head*head: the head for your list.

list_entry_is_head¶

list_entry_is_head(pos,head,member)

test if the entry points to the head of the list

Parameters

pos: the type * to cursor
head: the head for your list.
member: the name of the list_head within the struct.

list_for_each_entry¶

list_for_each_entry(pos,head,member)

iterate over list of given type

Parameters

pos: the type * to use as a loop cursor.
head: the head for your list.
member: the name of the list_head within the struct.

list_for_each_entry_reverse¶

list_for_each_entry_reverse(pos,head,member)

iterate backwards over list of given type.

Parameters

pos: the type * to use as a loop cursor.
head: the head for your list.
member: the name of the list_head within the struct.

list_prepare_entry¶

list_prepare_entry(pos,head,member)

prepare a pos entry for use inlist_for_each_entry_continue()

Parameters

pos: the type * to use as a start point
head: the head of the list
member: the name of the list_head within the struct.

Description

Prepares a pos entry for use as a start point inlist_for_each_entry_continue().

list_for_each_entry_continue¶

list_for_each_entry_continue(pos,head,member)

continue iteration over list of given type

Parameters

pos: the type * to use as a loop cursor.
head: the head for your list.
member: the name of the list_head within the struct.

Description

Continue to iterate over list of given type, continuing afterthe current position.

list_for_each_entry_continue_reverse¶

list_for_each_entry_continue_reverse(pos,head,member)

iterate backwards from the given point

Parameters

pos: the type * to use as a loop cursor.
head: the head for your list.
member: the name of the list_head within the struct.

Description

Start to iterate over list of given type backwards, continuing afterthe current position.

list_for_each_entry_from¶

list_for_each_entry_from(pos,head,member)

iterate over list of given type from the current point

Parameters

pos: the type * to use as a loop cursor.
head: the head for your list.
member: the name of the list_head within the struct.

Description

Iterate over list of given type, continuing from current position.

list_for_each_entry_from_reverse¶

list_for_each_entry_from_reverse(pos,head,member)

iterate backwards over list of given type from the current point

Parameters

pos: the type * to use as a loop cursor.
head: the head for your list.
member: the name of the list_head within the struct.

Description

Iterate backwards over list of given type, continuing from current position.

list_for_each_entry_safe¶

list_for_each_entry_safe(pos,n,head,member)

iterate over list of given type safe against removal of list entry

Parameters

pos: the type * to use as a loop cursor.
n: another type * to use as temporary storage
head: the head for your list.
member: the name of the list_head within the struct.

list_for_each_entry_safe_continue¶

list_for_each_entry_safe_continue(pos,n,head,member)

continue list iteration safe against removal

Parameters

pos: the type * to use as a loop cursor.
n: another type * to use as temporary storage
head: the head for your list.
member: the name of the list_head within the struct.

Description

Iterate over list of given type, continuing after current point,safe against removal of list entry.

list_for_each_entry_safe_from¶

list_for_each_entry_safe_from(pos,n,head,member)

iterate over list from current point safe against removal

Parameters

pos: the type * to use as a loop cursor.
n: another type * to use as temporary storage
head: the head for your list.
member: the name of the list_head within the struct.

Description

Iterate over list of given type from current point, safe againstremoval of list entry.

list_for_each_entry_safe_reverse¶

list_for_each_entry_safe_reverse(pos,n,head,member)

iterate backwards over list safe against removal

Parameters

pos: the type * to use as a loop cursor.
n: another type * to use as temporary storage
head: the head for your list.
member: the name of the list_head within the struct.

Description

Iterate backwards over list of given type, safe against removalof list entry.

list_safe_reset_next¶

list_safe_reset_next(pos,n,member)

reset a stale list_for_each_entry_safe loop

Parameters

pos: the loop cursor used in the list_for_each_entry_safe loop
n: temporary storage used in list_for_each_entry_safe
member: the name of the list_head within the struct.

Description

list_safe_reset_next is not safe to use in general if the list may bemodified concurrently (eg. the lock is dropped in the loop body). Anexception to this is if the cursor element (pos) is pinned in the list,and list_safe_reset_next is called after re-taking the lock and beforecompleting the current iteration of the loop body.

inthlist_unhashed(conststructhlist_node*h)¶: Has node been removed from list and reinitialized?

Parameters

conststructhlist_node*h: Node to be checked

Description

Not that not all removal functions will leave a node in unhashedstate. For example,hlist_nulls_del_init_rcu() does leave thenode in unhashed state, buthlist_nulls_del() does not.

inthlist_unhashed_lockless(conststructhlist_node*h)¶: Version of hlist_unhashed for lockless use

Parameters

conststructhlist_node*h: Node to be checked

Description

This variant ofhlist_unhashed() must be used in lockless contextsto avoid potential load-tearing. TheREAD_ONCE() is paired with thevariousWRITE_ONCE() in hlist helpers that are defined below.

inthlist_empty(conststructhlist_head*h)¶: Is the specified hlist_head structure an empty hlist?

Parameters

conststructhlist_head*h: Structure to check.

voidhlist_del(structhlist_node*n)¶: Delete the specified hlist_node from its list

Parameters

structhlist_node*n: Node to delete.

Description

Note that this function leaves the node in hashed state. Usehlist_del_init() or similar instead to unhashn.

voidhlist_del_init(structhlist_node*n)¶: Delete the specified hlist_node from its list and initialize

Parameters

structhlist_node*n: Node to delete.

Description

Note that this function leaves the node in unhashed state.

voidhlist_add_head(structhlist_node*n,structhlist_head*h)¶: add a new entry at the beginning of the hlist

Parameters

structhlist_node*n: new entry to be added
structhlist_head*h: hlist head to add it after

Description

Insert a new entry after the specified head.This is good for implementing stacks.

voidhlist_add_before(structhlist_node*n,structhlist_node*next)¶: add a new entry before the one specified

Parameters

structhlist_node*n: new entry to be added
structhlist_node*next: hlist node to add it before, which must be non-NULL

voidhlist_add_behind(structhlist_node*n,structhlist_node*prev)¶: add a new entry after the one specified

Parameters

structhlist_node*n: new entry to be added
structhlist_node*prev: hlist node to add it after, which must be non-NULL

voidhlist_add_fake(structhlist_node*n)¶: create a fake hlist consisting of a single headless node

Parameters

structhlist_node*n: Node to make a fake list out of

Description

This makesn appear to be its own predecessor on a headless hlist.The point of this is to allow things likehlist_del() to work correctlyin cases where there is no list.

boolhlist_fake(structhlist_node*h)¶: Is this node a fake hlist?

Parameters

structhlist_node*h: Node to check for being a self-referential fake hlist.

boolhlist_is_singular_node(structhlist_node*n,structhlist_head*h)¶: is node the only element of the specified hlist?

Parameters

structhlist_node*n: Node to check for singularity.
structhlist_head*h: Header for potentially singular list.

Description

Check whether the node is the only node of the head withoutaccessing head, thus avoiding unnecessary cache misses.

voidhlist_move_list(structhlist_head*old,structhlist_head*new)¶: Move an hlist

Parameters

structhlist_head*old: hlist_head for old list.
structhlist_head*new: hlist_head for new list.

Description

Move a list from one list head to another. Fixup the pprevreference of the first entry if it exists.

voidhlist_splice_init(structhlist_head*from,structhlist_node*last,structhlist_head*to)¶: move all entries from one list to another

Parameters

structhlist_head*from: hlist_head from which entries will be moved
structhlist_node*last: last entry on thefrom list
structhlist_head*to: hlist_head to which entries will be moved

Description

to can be empty,from must contain at leastlast.

hlist_for_each_entry¶

hlist_for_each_entry(pos,head,member)

iterate over list of given type

Parameters

pos: the type * to use as a loop cursor.
head: the head for your list.
member: the name of the hlist_node within the struct.

hlist_for_each_entry_continue¶

hlist_for_each_entry_continue(pos,member)

iterate over a hlist continuing after current point

Parameters

pos: the type * to use as a loop cursor.
member: the name of the hlist_node within the struct.

hlist_for_each_entry_from¶

hlist_for_each_entry_from(pos,member)

iterate over a hlist continuing from current point

Parameters

pos: the type * to use as a loop cursor.
member: the name of the hlist_node within the struct.

hlist_for_each_entry_safe¶

hlist_for_each_entry_safe(pos,n,head,member)

iterate over list of given type safe against removal of list entry

Parameters

pos: the type * to use as a loop cursor.
n: astructhlist_node to use as temporary storage
head: the head for your list.
member: the name of the hlist_node within the struct.

size_thlist_count_nodes(structhlist_head*head)¶: count nodes in the hlist

Parameters

structhlist_head*head: the head for your hlist.

Movatterモバイル変換

Linked Lists in Linux ¶

Introduction ¶

Linux implementation of doubly linked lists ¶

Declaring a node ¶

Declaring and initializing a list ¶

Adding nodes to the list ¶

Traversing the list ¶

Removing nodes from the list ¶

Traversing whilst removing nodes ¶

Cutting a list ¶

Moving entries and partial lists ¶

Rotating entries ¶

Swapping entries ¶

Splicing two lists together ¶

Concurrency considerations ¶

Further reading ¶

Full List API ¶