一、双向链表list_head

Linux内核驱动开发会经常用到Linux内核中经典的双向链表list_head，以及它的拓展接口和宏定义：list_add、list_add_tail、list_del、list_entry、list_for_each等。

在内核源码中，list_head结构体的定义在文件source_code/include/linux/types.h文件中，结构体定义如下：

通过这个结构体开始构建链表，然后插入、删除节点，遍历整个链表等，内核已经提供好了现成的调用接口。

1、创建链表

Linux内核中提供了下面的接口来进行双向链表初始化：

可以通过LIST_HEAD(my_lsit)来进行一个双向链表的初始化，初始化后，my_list的prev和next指针都将指向自己，如下：

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

正常的链表都是为了遍历结构体中其它有意义的字段而创建的，但是上面定义的my_list中只有prev和next指针，因此没有实际意义的字段数据，所以，需要创建一个宿主结构，然后在此结构中嵌套my_list字段，宿主结构中又有其它的字段，例如：

struct my_task_lsit {　　int val;　　struct list_head my_list;}

然后通过下面的code创建出第一个节点：

struct my_task_list first_task = {    .val = 1,    .my_list = LIST_HEAD_INIT(first_task.my_list)};

这样子，宿主结构中的my_list的prev和next指针分别指向了自己，如下所示： 

 

2、添加节点

在Linux内核中已经提供了添加双向链表节点的函数接口了。

（1）list_add()函数

该函数的接口代码如下所示：

根据注释可以知道，是在链表头head的后方插入一个新的节点，而且该接口函数能利用实现堆栈，同时list_add函数再调用__list_add函数，函数代码如下所示：

函数实现的功能其实就是在head链表头和链表头后的第一个节点之间插入一个新节点，然后这个新的节点就变成了链表头后的第一个节点。

接下来，开始创建一个链表头head_task，并使用LIST_HEAD(head_task);进行初始化，如下所示：

然后创建实际的第一个节点：

struct my_task_list first_task = {    .val =1,    .my_list = LIST_HEAD_INIT(first_task.my_list)};

创建完成后，通过使用list_add接口将这个first_task节点插入到head_task之后：

list_add(&first_task.my_list, &head_task);

完成后，双向链表的指针指向如下所示：

然后继续创建第二个节点，同样把它插入到head_task之后：

struct my_task_list second_task = {    .val = 2,    .my_list = LIST_HEAD_INIT(second_task.my_list)};

然后调用list_add()添加节点：

list_add(&second_task.my_list, &head_task);

插入后指针指向如下所示：

以此类推，每次插入一个新的节点，都是紧靠着head_task节点的，而之前插入的节点以此排序靠后，所以最后的哪个节点是第一个插入head_task的哪个节点，所以结论是：先来的节点靠后，而后来的节点靠前，也就是先进后出，后进先出，类似于栈的结构。

（2）list_add_tail()函数

list_add接口是从链表头head后添加节点，同样，Linux内核也提供了从链表尾处向前添加节点的接口list_add_tail，具体实现代码如下所示：

从注释可以知道，该接口函数是从一个链表头前面插入一个节点，并且该接口适合于队列的实现，__list_add()函数展开如下所示：

由代码可以知道，list_add_tail就相当于在链表头的前方依次插入新的节点（也可以理解为在链表尾开始插入新的节点，head节点就是尾节点，保持不变）。

接下来，先开始创建一个链表头（链表尾），同时调用LIST_HEAD进行初始化：

struct my_task_list head_task = {    .val = 0,    .my_list = LIST_HEAD_INIT(&head_task.my_list)};

结构图形如下所示：

接下来，创建第一个节点first_task，并且调用list_add_tail函数将节点插入到链表头前面：

struct my_task_list first_task = {    .val = 1,    .my_list = LIST_HEAD_INIT(&first_task.my_list)};list_add_tail(&first_task.my_list, &head_task);

数据结构图形如下所示：

然后，继续创建第二个节点second_task，并且调用list_add_tail函数将节点添加到链表里面

struct my_task_list second_task = {    .val = 2,    .my_list = LIST_HEAD_INIT(&second_task.my_list)};list_add_tail(&second_task.my_list, &head_task);

添加完成后，数据结构图如下所示：

依次类推，每次插入的新节点都是紧靠着head的表尾，而插入的第一个节点first_task排在了第一位，second_task排在了第二位，也就是：先插入的节点排在前面，后插入的节点排在后面，也就是先进先出，后进后出，类似于队列的结构。

3、删除节点

Linux内核里面同样提供了删除双向链表节点的的接口list_del()函数，代码如下所示：

list_del()函数里面继续调用了__list_del_entry()接口，如下：

__list_del()的函数如下所示：

利用list_del()就可以删除掉链表中的任意节点，但是需要注意的是，前提条件是这个节点是已知的，也就是在链表中是真实存在的，其节点的prev和next指针都不为NULL。

4、链表的遍历

Linux内核里面同样提供了对list_head链表进行遍历的接口，分别有两种情况，第一种是同过next指针，从前向后进行遍历，函数接口为list_for_each，如下所示：

该接口为一个宏定义，有两个参数。第一个参数为struct list_head的循坏因子，第二个参数为链表头。另外一个接口是通过prev指针进行遍历的，如下：

传入参数和第一个接口类似。

5、节点替换

Linux内核里面提供了对链表的节点进行替换的接口，函数的实现如下所示：

list_replac接口的参数有两个，分别是旧的节点，也就是需要被替换的节点，第二个参数是新的节点，也就是替换的的节点，其实就是通过改变prev和next指针的指向从而达到替换的效果。

另外，内核里面还提供了其它的接口，例如list_move（节点移位），节点翻转，节点查找等接口，可以通过源码进行分析。

6、宿主结构

（1）找出宿主结构list_entry(ptr, type, member)

上面的操作都是基于struct list_head这个链表进行的，涉及到的结构体也都是如下结构体：

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

但是，应该真正关心的是包含list_head结构体字段的宿主结构体，因为只有定位到了宿主结构体的起始地址，才能够对宿主结构体中其它有意义的字段进行操作。

struct my_task_list {    int val;    struct list_head my_list;};

如何根据my_list这个字段的地址，寻找到my_task_list的地址呢？

在Linux内核中可以通过一个经典的宏定义：container_of(ptr, type, member)，list_entry()宏定义如下：

container_of宏定义如下所示：

其宏的注释为：

根据结构体中的一个成员变量地址导出包含这个成员变量member的struct结构体地址。

参数：

         ptr：成员变量member的地址

         type：包含成员变量member的宿主结构体类型

         member：宿主结构体中member成员变量的名称

使用举例为前面的strucr my_task_list:

struct my_task_list {    int val;    struct list_head my_list;};struct my_task_list first_task = {    .val = 1,    .my_list = LIST_HEAD(first_task.my_list)};

若使用container_of宏去寻找fitst_task的地址，则这样使用：

ptr = container_of(&first_task.my_list, struct my_task_list, my_list);

因此container_of宏的功能就是根据first_task.my_list字段得到的地址得出first_task结构的真实地址。

offsetof宏定义如下所示：

将宏进行展开，并将ptr、type和member里面的值代入，可以得到下面的表达式：

#define container_of(&first_task.my_list, struct my_task_list, my_list) ({          \　　void *__mptr = (void *)(&first_task.my_list);                                      \　　((struct my_task_list *)(__mptr - ((size_t) &((struct my_task_list *)0)->my_list))); })

因此，container_of这个宏就是包含了两个语句，第一个语句如下：

void *__mptr = (void *)(&first_task.my_list);

该语句的作用为，提取出first_task_list中my_list的地址，强制转换为(void *)类型后，并赋值给__mptr指针。

第二个语句如下：

((struct my_task_list *)(__mptr - ((size_t) &((struct my_task_list *)0)->my_list)));

第二个语句的作用为，使用__mptr这个地址减去my_task_list中的偏移（该偏移量是通过将0地址强制转换为struct my_task_list指针类型，然后取出my_list中的地址，也就是相对于0地址的偏移，也就是my_list字段相对于宿主结构struct my_task_list的偏移），两者相减之后，得到的就是first_task宿主结构的起始地址，最后将地址强制转换为(struct my_task_list *)类型并返回。

（2）宿主结构的遍历

在上面可以知道，通过container_of这个宏，能根据结构体中成员变量的地址找到宿主结构的地址，并且能通过对成员变量提供的链表进行遍历，同时，也可以通过Linux内核接口对宿主结构进行遍历。

list_for_each_entry()能够对宿主结构进行遍历，其定义如下：

该宏需要传入三个参数：

         pos：宿主结构体类型指针

         head：链表的表头

         member：结构体内链表成员变量的名称

宏内还调用了另外两个宏，分别是list_first_entry和list_next_entry，其定义如下：

由注释可以知道该宏是获取嵌入链表内第一个宿主结构体的地址。

该宏是获取嵌入链表内下一个宿主结构体的地址，通过这两个宏，便可以实现宿主结构的遍历。

首先，pos定位到第一个宿主结构的地址，然后循坏获取下一个宿主结构的地址，判断宿主结构中的member成员变量（宿主结构中struct list_head定义的字段）地址是否为head，是的话，退出循坏，从而实现了宿主结构的遍历，通过遍历，能对宿主结构的其它成员变量进行操作，例如：

struct my_task_list *pos_ptr = NULL; list_for_each_entry(pos_ptr, &head_task.my_list, my_list) {    printk(KERN_INFO “val = %d\n”, pos_ptr->val);}