11.5. 链表 (LDD3)
时间：2007-01-14 来源：seawolf1979
11.5. 链表
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.
跟其他的程序一样，操作系统内核通常需要维护一系列数据结构。曾几何时，Linux内核在同一阶段提供了多种不同的链表实现方式。为了减少重复代码，内核开发者们已经提供了标准的循环链表和双向链表；建议程序员在需要用链表的地方也用标准的标准接口。
When working with the linked list interface, you should always bear in mind that the list functions perform no locking. If there is a possibility that your driver could attempt to perform concurrent operations on the same list, it is your responsibility to implement a locking scheme. The alternatives (corrupted list structures, data loss, kernel panics) tend to be difficult to diagnose.
当使用有关链表的函数时，一定要注意这些函数是没有锁机制的。如果驱动程序有可能会在同一个链表上执行并发操作，那么编写者必须实现锁机制。
To use the list mechanism, your driver must include the file <linux/list.h>. This file defines a simple structure of type list_head:
为了使用链表，驱动程序必须包含<linux/list.h>文件。这个文件定义了一个类型为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构成，每一个结构描述在链表中的一个入口。为了在代码种使用Linux提供的有关链表的函数，只需要在构成这个链表的sturct中嵌入一个list_head，也就是说，它的声明应当看起来像这样：
struct todo_struct {
struct list_head list;
int priority; /* driver specific */
/* ... add other driver-specific fields */
};
The head of the list is usually a standalone list_head structure. Figure 11-1 shows how the simple struct list_head is used to maintain a list of data structures.
链表头通常是一个单独的list_head结构。图11-1显示了如何使用这个简单的list_head结构来维护数据结构链表的。
Figure 11-1. The list_head data 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:
在使用INIT_LIST_HEAD宏之前必须先初始化链表头。一个“things to do”链表头可以这样声明和初始化：
struct list_head todo_list;
INIT_LIST_HEAD(&todo_list);
Alternatively, lists can be initialized at compile time:
也可以有另一种选择，在编译阶段初始化链表：
LIST_HEAD(todo_list);
Several functions are defined in <linux/list.h> that work with lists:
在<linux/list.h>里定义了一些函数来操作链表：
list_add(struct list_head *new, struct list_head *head);
Adds the new entry immediately after the list head—normally at the beginning of the list. Therefore, it can be used to build stacks. Note, however, that the head need not be the nominal head of the list; if you pass a list_head structure that happens to be in the middle of the list somewhere, the new entry goes immediately after it. Since Linux lists are circular, the head of the list is not generally different from any other entry.
紧跟链表头后插入一个new入口--也就是说在链表的开头处插入。因此，这种方法可以用来构建栈（stack）。然而请注意，这个head并不一定是链表的头；如果传递了一个list_head结构，而它恰好在这个链表中间的某个位置，那么这个new入口会紧跟其后。既然Linux中的链表是循环的，链表的头通常跟其他的入口没有什么区别。
list_add_tail(struct list_head *new, struct list_head *head);
Adds a new entry just before the given list head—at the end of the list, in other words. list_add_tail can, thus, be used to build first-in first-out queues.
在指定链表头前插入一个new入口--也就是在链表的结尾插入。list_add_tail能够用来构建FIFO（first-in first-out）队列
list_del(struct list_head *entry);
list_del_init(struct list_head *entry);
The given entry is removed from the list. If the entry might ever be reinserted into another list, you should use list_del_init, which reinitializes the linked list pointers.
从链表种删除指定的entry。如果这个入口可能会被重新插入到另一个链表，则应当使用list_del_init，它会重新初始化链表指针。
list_move(struct list_head *entry, struct list_head *head);
list_move_tail(struct list_head *entry, struct list_head *head);
The given entry is removed from its current list and added to the beginning of head. To put the entry at the end of the new list, use list_move_tail instead.
将指定的entry从它现在所在的链表移除，并加到head的开头处。如果要加到head的结尾处，那么使用list_move_tail。
list_empty(struct list_head *head);
Returns a nonzero value if the given list is empty.
如果给定链表为空，则返回非零值。
list_splice(struct list_head *list, struct list_head *head);
Joins two lists by inserting list immediately after head.
连接两个链表，即将list插入到head之后。
The list_head structures are good for implementing a list of like structures, but the invoking program is usually more interested in the larger structures that make up the list as a whole. A macro, list_entry, is provided that maps a list_head structure pointer back into a pointer to the structure that contains it. It is invoked as follows:
list_head结构对实现类似结构的链表很有用，但调用程序通常更关心构成整个链表的较大结构。list_entry是用来从list_head结构指针获得包含它的那个结构的指针（译注：见containerof函数）。调用形式如下：
list_entry(struct list_head *ptr, type_of_struct, field_name);
where ptr is a pointer to the struct list_head being used, type_of_struct is the type of the structure containing the ptr, and field_name is the name of the list field within the structure. In our todo_struct structure from before, the list field is called simply list. Thus, we would turn a list entry into its containing structure with a line such as:
ptr是指向正被使用的list_head的指针。type_of_struct是包含ptr的结构的类型，field_name是在这个结构中链表域的名字。在前面提到的todo_struct结构中，list域被称为simply list。因此，我们可以从list入口得到包含它的结构，代码如下：
struct todo_struct *todo_ptr =
list_entry(listptr, struct todo_struct, list);
The list_entry macro takes a little getting used to but is not that hard to use.
list_entry宏可能用起来不是那么习惯，但也不是太难用。
The traversal of linked lists is easy: one need only follow the prev and next pointers. As an example, suppose we want to keep the list of todo_struct items sorted in descending priority order. A function to add a new entry would look something like this:
链表的往回遍历是很容易的：只需要使用prev和next指针。例如，假使我们需要todo_struct结构中的priority条目按降序排列。增加一个入口的函数看起来像这样：
void todo_add_entry(struct todo_struct *new)
{
struct list_head *ptr;
struct todo_struct *entry;
for (ptr = todo_list.next; ptr != &todo_list; ptr = ptr->next) {
entry = list_entry(ptr, struct todo_struct, list);
if (entry->priority < new->priority) {
list_add_tail(&new->list, ptr);
return;
}
}
list_add_tail(&new->list, &todo_struct)
}
However, as a general rule, it is better to use one of a set of predefined macros for creating loops that iterate through lists. The previous loop, for example, could be coded as:
然而，一般来说，最好选择使用预先定义好的宏来创建循环从而遍历链表.前面提到的循环可以这样重新编写:
void todo_add_entry(struct todo_struct *new)
{
struct list_head *ptr;
struct todo_struct *entry;
list_for_each(ptr, &todo_list) {
entry = list_entry(ptr, struct todo_struct, list);
if (entry->priority < new->priority) {
list_add_tail(&new->list, ptr);
return;
}
}
list_add_tail(&new->list, &todo_struct)
}
Using the provided macros helps avoid simple programming errors; the developers of these macros have also put some effort into ensuring that they perform well. A few variants exist:
使用这些宏可以帮助避免简单的编程错误发生；毕竟这些宏的开发者们已经花了大力气来保证这些宏正确执行。类似的宏还有：
list_for_each(struct list_head *cursor, struct list_head *list)
This macro creates a for loop that executes once with cursor pointing at each successive entry in the list. Be careful about changing the list while iterating through it.
这个宏创建了一个for循环，在随着cursor遍历链表的每个条目时执行一次。[Robby]。遍历链表时如果要改变链表，必须小心谨慎。
list_for_each_prev(struct list_head *cursor, struct list_head *list)
This version iterates backward through the list.
这个版本用来反向遍历链表。
list_for_each_safe(struct list_head *cursor, struct list_head *next, struct
list_head *list)
If your loop may delete entries in the list, use this version. It simply stores the next entry in the list in next at the beginning of the loop, so it does not get confused if the entry pointed to by cursor is deleted.
如果你的循环需要删除链表中的条目，那么请使用这个版本。它将下一个条目放在next里（在循环的开头处），因此但cursor所指向的条目被删除时不会出现混乱。
list_for_each_entry(type *cursor, struct list_head *list, member)
list_for_each_entry_safe(type *cursor, type *next, struct list_head *list,
member)
These macros ease the process of dealing with a list containing a given type of structure. Here, cursor is a pointer to the containing structure type, and member is the name of the list_head structure within the containing structure. With these macros, there is no need to put list_entry calls inside the loop.
这些宏使得对包含给定type的结构的链表的处理容易些。cursor是执行包含结构的类型，member是在这个包含结构的list_head结构的名字。通过这些宏，就不需要在循环中调用list_entry了。
If you look inside <linux/list.h>, you see some additional declarations. The hlist type is a doubly linked list with a separate, single-pointer list head type; it is often used for creation of hash tables and similar structures. There are also macros for iterating through both types of lists that are intended to work with the read-copy-update mechanism (described in Section 5.7.5 in Chapter 5). These primitives are unlikely to be useful in device drivers; see the header file if you would like more information on how they work.
如果你查看<linux/list.h>，你会更多声明。hlist类型是具有单独的，单指针的，list head类型的双向链表，常被用来创建hash表，以及类似结构。还有一些宏是用来遍历两种类型的链表的，他们是针对RCU（read-copy-update）机制的（在第五章5.7.5节）。这些原语可能在设备驱动程序里可能用不上，如果想知道更多关于它们如何工作的信息，可以查看头文件。
全英文版可见：http://www.elinux.cn/book/ldd3/linuxdrive3-CHP-11-SECT-5.html
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.
跟其他的程序一样，操作系统内核通常需要维护一系列数据结构。曾几何时，Linux内核在同一阶段提供了多种不同的链表实现方式。为了减少重复代码，内核开发者们已经提供了标准的循环链表和双向链表；建议程序员在需要用链表的地方也用标准的标准接口。
When working with the linked list interface, you should always bear in mind that the list functions perform no locking. If there is a possibility that your driver could attempt to perform concurrent operations on the same list, it is your responsibility to implement a locking scheme. The alternatives (corrupted list structures, data loss, kernel panics) tend to be difficult to diagnose.
当使用有关链表的函数时，一定要注意这些函数是没有锁机制的。如果驱动程序有可能会在同一个链表上执行并发操作，那么编写者必须实现锁机制。
To use the list mechanism, your driver must include the file <linux/list.h>. This file defines a simple structure of type list_head:
为了使用链表，驱动程序必须包含<linux/list.h>文件。这个文件定义了一个类型为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构成，每一个结构描述在链表中的一个入口。为了在代码种使用Linux提供的有关链表的函数，只需要在构成这个链表的sturct中嵌入一个list_head，也就是说，它的声明应当看起来像这样：
struct todo_struct {
struct list_head list;
int priority; /* driver specific */
/* ... add other driver-specific fields */
};
The head of the list is usually a standalone list_head structure. Figure 11-1 shows how the simple struct list_head is used to maintain a list of data structures.
链表头通常是一个单独的list_head结构。图11-1显示了如何使用这个简单的list_head结构来维护数据结构链表的。
Figure 11-1. The list_head data 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:
在使用INIT_LIST_HEAD宏之前必须先初始化链表头。一个“things to do”链表头可以这样声明和初始化：
struct list_head todo_list;
INIT_LIST_HEAD(&todo_list);
Alternatively, lists can be initialized at compile time:
也可以有另一种选择，在编译阶段初始化链表：
LIST_HEAD(todo_list);
Several functions are defined in <linux/list.h> that work with lists:
在<linux/list.h>里定义了一些函数来操作链表：
list_add(struct list_head *new, struct list_head *head);
Adds the new entry immediately after the list head—normally at the beginning of the list. Therefore, it can be used to build stacks. Note, however, that the head need not be the nominal head of the list; if you pass a list_head structure that happens to be in the middle of the list somewhere, the new entry goes immediately after it. Since Linux lists are circular, the head of the list is not generally different from any other entry.
紧跟链表头后插入一个new入口--也就是说在链表的开头处插入。因此，这种方法可以用来构建栈（stack）。然而请注意，这个head并不一定是链表的头；如果传递了一个list_head结构，而它恰好在这个链表中间的某个位置，那么这个new入口会紧跟其后。既然Linux中的链表是循环的，链表的头通常跟其他的入口没有什么区别。
list_add_tail(struct list_head *new, struct list_head *head);
Adds a new entry just before the given list head—at the end of the list, in other words. list_add_tail can, thus, be used to build first-in first-out queues.
在指定链表头前插入一个new入口--也就是在链表的结尾插入。list_add_tail能够用来构建FIFO（first-in first-out）队列
list_del(struct list_head *entry);
list_del_init(struct list_head *entry);
The given entry is removed from the list. If the entry might ever be reinserted into another list, you should use list_del_init, which reinitializes the linked list pointers.
从链表种删除指定的entry。如果这个入口可能会被重新插入到另一个链表，则应当使用list_del_init，它会重新初始化链表指针。
list_move(struct list_head *entry, struct list_head *head);
list_move_tail(struct list_head *entry, struct list_head *head);
The given entry is removed from its current list and added to the beginning of head. To put the entry at the end of the new list, use list_move_tail instead.
将指定的entry从它现在所在的链表移除，并加到head的开头处。如果要加到head的结尾处，那么使用list_move_tail。
list_empty(struct list_head *head);
Returns a nonzero value if the given list is empty.
如果给定链表为空，则返回非零值。
list_splice(struct list_head *list, struct list_head *head);
Joins two lists by inserting list immediately after head.
连接两个链表，即将list插入到head之后。
The list_head structures are good for implementing a list of like structures, but the invoking program is usually more interested in the larger structures that make up the list as a whole. A macro, list_entry, is provided that maps a list_head structure pointer back into a pointer to the structure that contains it. It is invoked as follows:
list_head结构对实现类似结构的链表很有用，但调用程序通常更关心构成整个链表的较大结构。list_entry是用来从list_head结构指针获得包含它的那个结构的指针（译注：见containerof函数）。调用形式如下：
list_entry(struct list_head *ptr, type_of_struct, field_name);
where ptr is a pointer to the struct list_head being used, type_of_struct is the type of the structure containing the ptr, and field_name is the name of the list field within the structure. In our todo_struct structure from before, the list field is called simply list. Thus, we would turn a list entry into its containing structure with a line such as:
ptr是指向正被使用的list_head的指针。type_of_struct是包含ptr的结构的类型，field_name是在这个结构中链表域的名字。在前面提到的todo_struct结构中，list域被称为simply list。因此，我们可以从list入口得到包含它的结构，代码如下：
struct todo_struct *todo_ptr =
list_entry(listptr, struct todo_struct, list);
The list_entry macro takes a little getting used to but is not that hard to use.
list_entry宏可能用起来不是那么习惯，但也不是太难用。
The traversal of linked lists is easy: one need only follow the prev and next pointers. As an example, suppose we want to keep the list of todo_struct items sorted in descending priority order. A function to add a new entry would look something like this:
链表的往回遍历是很容易的：只需要使用prev和next指针。例如，假使我们需要todo_struct结构中的priority条目按降序排列。增加一个入口的函数看起来像这样：
void todo_add_entry(struct todo_struct *new)
{
struct list_head *ptr;
struct todo_struct *entry;
for (ptr = todo_list.next; ptr != &todo_list; ptr = ptr->next) {
entry = list_entry(ptr, struct todo_struct, list);
if (entry->priority < new->priority) {
list_add_tail(&new->list, ptr);
return;
}
}
list_add_tail(&new->list, &todo_struct)
}
However, as a general rule, it is better to use one of a set of predefined macros for creating loops that iterate through lists. The previous loop, for example, could be coded as:
然而，一般来说，最好选择使用预先定义好的宏来创建循环从而遍历链表.前面提到的循环可以这样重新编写:
void todo_add_entry(struct todo_struct *new)
{
struct list_head *ptr;
struct todo_struct *entry;
list_for_each(ptr, &todo_list) {
entry = list_entry(ptr, struct todo_struct, list);
if (entry->priority < new->priority) {
list_add_tail(&new->list, ptr);
return;
}
}
list_add_tail(&new->list, &todo_struct)
}
Using the provided macros helps avoid simple programming errors; the developers of these macros have also put some effort into ensuring that they perform well. A few variants exist:
使用这些宏可以帮助避免简单的编程错误发生；毕竟这些宏的开发者们已经花了大力气来保证这些宏正确执行。类似的宏还有：
list_for_each(struct list_head *cursor, struct list_head *list)
This macro creates a for loop that executes once with cursor pointing at each successive entry in the list. Be careful about changing the list while iterating through it.
这个宏创建了一个for循环，在随着cursor遍历链表的每个条目时执行一次。[Robby]。遍历链表时如果要改变链表，必须小心谨慎。
list_for_each_prev(struct list_head *cursor, struct list_head *list)
This version iterates backward through the list.
这个版本用来反向遍历链表。
list_for_each_safe(struct list_head *cursor, struct list_head *next, struct
list_head *list)
If your loop may delete entries in the list, use this version. It simply stores the next entry in the list in next at the beginning of the loop, so it does not get confused if the entry pointed to by cursor is deleted.
如果你的循环需要删除链表中的条目，那么请使用这个版本。它将下一个条目放在next里（在循环的开头处），因此但cursor所指向的条目被删除时不会出现混乱。
list_for_each_entry(type *cursor, struct list_head *list, member)
list_for_each_entry_safe(type *cursor, type *next, struct list_head *list,
member)
These macros ease the process of dealing with a list containing a given type of structure. Here, cursor is a pointer to the containing structure type, and member is the name of the list_head structure within the containing structure. With these macros, there is no need to put list_entry calls inside the loop.
这些宏使得对包含给定type的结构的链表的处理容易些。cursor是执行包含结构的类型，member是在这个包含结构的list_head结构的名字。通过这些宏，就不需要在循环中调用list_entry了。
If you look inside <linux/list.h>, you see some additional declarations. The hlist type is a doubly linked list with a separate, single-pointer list head type; it is often used for creation of hash tables and similar structures. There are also macros for iterating through both types of lists that are intended to work with the read-copy-update mechanism (described in Section 5.7.5 in Chapter 5). These primitives are unlikely to be useful in device drivers; see the header file if you would like more information on how they work.
如果你查看<linux/list.h>，你会更多声明。hlist类型是具有单独的，单指针的，list head类型的双向链表，常被用来创建hash表，以及类似结构。还有一些宏是用来遍历两种类型的链表的，他们是针对RCU（read-copy-update）机制的（在第五章5.7.5节）。这些原语可能在设备驱动程序里可能用不上，如果想知道更多关于它们如何工作的信息，可以查看头文件。
全英文版可见：http://www.elinux.cn/book/ldd3/linuxdrive3-CHP-11-SECT-5.html
相关阅读 更多 +
