Linux Device Drivers, Second Edition

Linked Lists

Operating system kernels, like many other programs, often need to maintain lists of data structures. The Linux kernel has, at times, been host to several linked list implementations at the same time. To reduce the amount of duplicated code, the kernel developers have created a standard implementation of circular, doubly-linked lists; others needing to manipulate lists are encouraged to use this facility, introduced in version 2.1.45 of the kernel.

To use the list mechanism, your driver must include the file <linux/list.h>. This file defines a simple structure of type list_head:

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

Linked lists used in real code are almost invariably made up of some type of structure, each one describing one entry in the list. To use the Linux list facility in your code, you need only embed a list_head inside the structures that make up the list. If your driver maintains a list of things to do, say, its declaration would look something like this:

struct todo_struct {
    struct list_head list;
    int priority; /* driver specific */
    /* ... add other driver-specific fields */
};

The head of the list must be a standalone list_head structure. List heads must be initialized prior to use with the INIT_LIST_HEAD macro. A “things to do” list head could be declared and initialized with:

struct list_head todo_list;

INIT_LIST_HEAD(&todo_list);

Alternatively, lists can be initialized at compile time as follows:

LIST_HEAD(todo_list);

Several functions ...