Author: R. Koucha
Last update: 31-Mar-2008


Back to main page
Back to previous page

Using linked list in the Linux kernel










s

About the author




The service is defined in <linux/list.h>

A list link is defined as:

struct list_head
{
    struct list_head *next, *prev;
};

                 +----------+
                 |   next   |
                 |   prev   |
                 +----------+

To define and initialize a head of list:

LIST_HEAD(hdr);

This defines "hdr" as an empty list:

struct list_head hdr =  { &hdr, &hdr };


            +--------------------+
            |        hdr         |
            +--->+----------+    |
            |    |   next   |----+
            |    |          |
            |    |   prev   |
----+
            |    +----------+    |
            |                    |
            +--------------------+
   
To initialize an element that is destined to be inserted in a list.

struct list_head elt;
...
INIT_LIST_HEAD(&elt);



So, an empty list is a list for which the header points on itself: p->next = p->prev = p. The service "list_empty()" returns 0 if a list is not empty and non 0 otherwise:


LIST_HEAD(hdr);

...
if (list_empty(&hdr))
{
  /* The list is empty */
}
else
{
  /* The list is not empty */
}


list_add() inserts an element at the beginning of the list (i.e. just after the specified head):

LIST_HEAD(hdr);
struct list_head elt;

...
list_add(&elt, &hdr);

            +----------------------------------------------+
            |        hdr                        elt        |
            +--->+----------+    +-----+--->+----------+   |
            |    |   next   |----+     |    |   next   |---+
            |    |          |          |    |          |
            |    |   prev   |
----------+    |   prev   |---+
            |    +----------+               +----------+   |
            |                                              |
            +----------------------------------------------+

list_add_tail() inserts an element at the end of the list (i.e. just before the specified head):

LIST_HEAD(hdr);
struct list_head elt;

...
list_add_tail(&elt, &hdr);

            +----------------------------------------------+
            |        elt                        hdr        |
            +--->+----------+    +-----+--->+----------+   |
            |    |   next   |----+     |    |   next   |---+
            |    |          |          |    |          |
            |    |   prev   |
----------+    |   prev   |---+
            |    +----------+               +----------+   |
            |                                              |
            +----------------------------------------------+

list_del_init() removes an element from the list it is linked to and reinitialize the element:

LIST_HEAD(hdr);
struct list_head elt;
struct list_head *p;
...

/* Add elt into the list 'hdr' */
list_add_tail(&elt, &hdr);

...
p = elt;
...
/* Suppress 'elt' from the list */
list_del_init(p);


list_move() moves an element from its current list to the beginning of another list:

LIST_HEAD(hdr);
LIST_HEAD(hdr1);
struct list_head elt;
struct list_head *p;
...

/* Add elt into the list 'hdr' */
list_add_tail(&elt, &hdr);

...
p = &elt;
...
/* Move 'elt' from the list 'hdr' to 'hdr1' */
list_move(p, &hdr1);


list_move_tail() has the same interface as list_move() but moves an element from its current list to the end of another list.

list_splice() appends a list to another. list_splice_init() does the same operation but reinitializes the head of the emptied list.

LIST_HEAD(hdr);
LIST_HEAD(hdr1);
...
/* Append list 'hdr1' to 'hdr' */
list_splice(&hdr1, &hdr);


When the 'list_head' structures are embedded into high level structures, it is possible to retrieve the high level structure from a pointer on a 'list_head' through list_entry():

typedef struct
{
int f;
struct list_head link;
} high_level_t;

LIST_HEAD(hdr);
high_level_t elt;
struct list_head *p;
high_level_t *phl;
...
/* Insert the high level structure into the list */
list_add(&(elt.link), &hdr);
...
/* Retrieve the high level information from the list links */
p = &(elt.link);
phl = list_entry(p,
high_level_t, link);

list_for_each() iterates over a list from the beginning to the end of the list:

typedef struct
{
int f;
struct list_head link;
} high_level_t;

LIST_HEAD(hdr);

struct list_head *p;
high_level_t *phl;
...
list_for_each(p, &hdr)
{
  p
hl = list_entry(p, high_level_t, link);
  printf("f = %d\n", phl->f);
} /* End for list */

list_for_each_entry() is an extension of list_for_each() as it iterates over a list using a pointer on a high level structure:

typedef struct
{
int f;
struct list_head link;
} high_level_t;

LIST_HEAD(hdr);

high_level_t *phl;
...
list_for_each_entry(phl, &hdr, link)
{

  printf("f = %d\n", phl->f);
} /* End for list */

list_for_each_entry_reverse() does the same as list_for_each_entry() but iterates over the list from the end to the beginning.

list_for_each_entry_continue() used along with list_prepare_entry() iterates over a list from a given element to the end of the list:

typedef struct
{
int f;
struct list_head link;
} high_level_t;

LIST_HEAD(hdr);

high_level_t *phl, *p;
...
phl = NULL;

/* Point on some element in the list */
p = &elt;

/* Loop from element 'p' to the end of the list (if 'p' is NULL, 'phl' will point on the beginning of the list) */
phl = list_prepare_entry(p, &hdr, link);
list_for_each_entry_continue(phl, &hdr, link)
{

  printf("f = %d\n", phl->f);
} /* End for list */


About the author

The author is an engineer in computer sciences located in France. He can be contacted here or you can have a look at his WEB home page.


Back to main page
Back to previous page