第十一章 内核数据类型(二) 链表

链表
操作系统内核常需要维护数据结构的链表。Linux 内核已经同时有几个链表实现。为减少复制代码的数量, 内核已经创建了一个标准环形双向链表，并鼓励需要操作链表的人使用这个设施.
使用链表接口时，应当记住列表函数没做加锁。若驱动可能同一个列表并发操作，就必须实现一个锁方案。
为使用链表机制，驱动必须包含文件  ，它定义了一个简单的list_head 类型 结构: 
struct list_head { struct list_head *next, *prev; }; 
实际代码中使用的链表几乎总是由某个结构类型组成, 每个结构描述链表中的一项. 为使用 Linux 链表，只需嵌入一个 list_head 在构成在这个链表的结构里面。链表头常常是一个独立的 list_head 结构。下图显示了这个简单的 struct list_head 是如何用来维护一个数据结构的列表的.

特别注意：内核链表与我们传统的链表的区别

传统链表：

struct student {

     char name[20];

     int num;

     struct student *prev,*next;

}

这里这个prev,next指针指向的是整个student这个大结构。

内核链表：

struct student {

     char name[20];

     int num;

     struct list_head list;

}

这里的prev，next(包含在list_head这个结构中，准确的说应是list->prev,

list->next)指针指向的student结构中的list这个结构。(由上图也易看出)

/*链表头必须在使用前初始化,有两种形式 */

struct list_head todo_list; 
INIT_LIST_HEAD(&todo_list); //运行时初始化 
LIST_HEAD(todo_list); //编译时初始化
list_add(struct list_head *new, struct list_head *head); //头插法(插在表头后面)
/*在紧接着链表 head 后面增加新项 。注意：head 不需要是链表名义上的头; 如果你传递一个 list_head 结构, 它在链表某处的中间, 新的项紧靠在它后面。 因为 Linux 链表是环形的, 链表头通常和任何其他的项没有区别*/
list_add_tail(struct list_head *new, struct list_head *head); //尾插法(插在表头前面)
/*在给定链表头前面增加新项，即在链表的尾部增加一个新项。*/
list_del(struct list_head *entry);
list_del_init(struct list_head *entry); 
/*删除链表中给定项。如果该给定项还可能被重新插入到另一个链表中, 则应使用 list_del_init, 它重新初始化这个链表指针.我的理解是list_del会释放该给定项的内存空间，而list_del_init不会*/
list_move(struct list_head *entry, struct list_head *head); 
list_move_tail(struct list_head *entry, struct list_head *head); 
/*把给定项移动链表的头的后面(头插)，如果要把给定项放到新链表的末尾，使用

list_move_tail*/
list_empty(struct list_head *head); 
/*如果给定链表为空, 返回真.*/
list_splice(struct list_head *list, struct list_head *head);
/*在head之后插入list来合并两个链表.*/

list_entry(struct list_head *ptr,type_of_struct,field_name)
/*list_entry是由一个 list_head 结构指针得到一个指向包含它的结构体的指针(返回值) 。*/

以前面的struct student为例：type_of_struct就是struct student,而field_name就是struct list_head 结构类型作为struct student的成员名即list。返回值为指向student结构体的指针。

在第三章字符设备驱动程序中一个宏 container_of 。list_entry就是其变体，在linux内核源码中就是如下定义：
#define list_entry(ptr, type, member)    container_of(ptr, type, member) 

以向一个按学号降序的链表插入一个元素为例：

struct student{

    char name[20];
    int num;
    struct list_head list;
}

struct list_head student_list;

void add_student(struct student *newstudent)
{
    struct list_head *ptr;
    struct student *entry;
    for(ptr=student_list->next;ptr!=student_list;ptr=ptr->next)
    {
        entry = list_entry(ptr, struct student, list);
        if(entry.num < newstudent.num)
        {
            list_add_tail(&(newstudent->list),ptr);
            return ;
        }
    }
    list_add_tail(&(newstudent->list),&student_list);
}

list_for_each(struct list_head *cursor,struct list_head *list)

这个宏是一个for循环(在linux内核源码list.h文件中有定义)类似于上面例子中的for(ptr=student_list->next;ptr!=student_list;ptr=ptr->next)所以该宏的作用就是用于遍历链表时指针的移动。

例子：