· KLDP.org · KLDP.net · KLDP Wiki · KLDP BBS ·
Linked List

Linux Kernel's Linked List Implementation

The Linked-List Structure

The linked-list code is declared in <linux/list.h> and the data structure is simple:
struct list_head {
        struct list_head *next
        struct list_head *prev;

Note the curious name, list_head. The name takes a cue from the fact that there is no head node. Instead, because the list can be traversed starting with any given element, each element is in effect a head. Thus, the individual nodes are all called list heads.

A list_head by itself is worthless; it is normally embedded inside your own structure:
struct my_struct {
        struct list_head list;
        unsigned long dog;
        void *cat;

The list needs to be initialized before it can be used. Because most of the elements are created dynamically (probably why you need a linked list), the most common way of initializing the linked list is at runtime:
struct my_struct *p;
/* allocate my_struct .. */
p->dog = 0;
p->cat = NULL;

If the structure is statically created at compile time, and you have a direct reference to it, you can simply do this:
struct my_struct mine = {
  .list  = LIST_HEAD_INIT(mine.list),
  .dog  = 0,
  .cat  = NULL

To declare and initialize a static list directly, use
static LIST_HEAD(fox);

This declares and initializes a static list named fox.

A family of functions is provided to manipulate linked lists. all these functions are O(1)

To add a node to a linked list:
list_add(struct list_head *new, struct list_head *head)

This function adds the new node to the given list immediately after the head node. Because the list is circular and generally has no concept of first or last nodes, you can pass any element for head. If you do pass the "last" element, however, this function can be used to implement a stack.

To add a node to the end of a linked list:
list_add_tail(struct list_head *new, struct list_head *head)

This function adds the new node to the given list immediately before the head node. As with list_add(), because the lists are circular you can generally pass any element for head. This function can be used to implement a queue, however, if you do indeed pass the "first" element.

To delete a node from a linked list,
list_del(struct list_head *entry)

This function removes the element entry from the list. Note, it does not free any memory belonging to enTRy or the data structure in which it is embedded; this function merely removes the element from the list. After calling this, you would typically destroy your data structure and the list_head inside it.

To delete a node from a linked list and reinitialize it,
list_del_init(struct list_head *entry)

This function is the same as list_del(), except it also reinitializes the given list_head with the rationale that you no longer want the entry in the list, but you can reuse the data structure itself.

To move a node from one list to another,
list_move(struct list_head *list, struct list_head *head)

This function removes the list entry from its linked list and adds it to the given list after the head element.

To move a node from one list to the end of another,
list_move_tail(struct list_head *list, struct list_head *head)

This function does the same as list_move(), but inserts the list element before the head enTRy.

To check if a list is empty,
list_empty(struct list_head *head)

This returns nonzero if the given list is empty; otherwise it returns zero.

Traversing Linked Lists

struct list_head *p;
struct my_struct *my;

list_for_each(p, &mine->list) {
        /* my points to the structure in which the list is embedded */
        my = list_entry(p, struct my_struct, list);

The list_for_each() macro expands to a simple for loop. For example, the previous use expands to
for (p = mine->list->next; p != mine->list; p = p->next)

The list_for_each() macro also uses processor prefetching, if the processor supports such a feature, to prefetch subsequent entries into memory before they are actually referenced. Prefetching improves memory bus utilization on modern pipelined processors. To not perform prefetching, the macro __list_for_each() works just identically to this for loop. Unless you know the list is very small or empty, you should always use the prefetching version. You should never hand code the loop; always use the provided macros.

If you need to iterate through the list backward, you can use list_for_each_prev(), which follows the prev pointers instead of the next pointer.

Note that nothing prevents removal of list entries from the list while you are traversing it. Normally, the list needs some sort of lock to prevent concurrent access. The macro list_for_each_safe(), however, uses temporary storage to make traversing the list safe from removals:
struct list_head *p, *n;
struct my_struct *my;
list_for_each_safe(p, n, &mine->list) {
        /* my points to each my_struct in the list */
        my = list_entry(p, struct my_struct, list);

This macro provides protection from only removals. You probably require additional locking protection to prevent concurrent manipulation of the actual list data.

sponsored by andamiro
sponsored by cdnetworks
sponsored by HP

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2006-05-21 12:08:04
Processing time 0.0045 sec