6.6　颠覆传统链表的实现方法

由于Linux内核中有大量的数据结构都需要用到双向循环链表，若还采用以往那种传统双向循环链表的实现方式，就不得不为这些数据结构维护各自的链表，并且必须为每个链表设计插入、查找、删除等操作函数，这是因为常规链表中的前向指针prev和后向指针next都是指向对应类型的对象，一种数据结构的链表操作函数不能操作其他数据结构的链表。

为了解决传统链表中存在的上述问题，在Linux内核中将结构体中的前向指针prev和后向指针next从具体的数据结构中提取出来，构成一个通用的双向循环链表数据结构list_head。如果需要构造某类对象的特定链表，那么只需要在其结构体中定义一个类型为list_head类型的成员，通过这个list_head类型的成员将这类对象连接起来，形成所需的双向循环链表，进而通过通用链表函数对其进行操作。

显而易见，这种颠覆传统双向循环链表的实现方法，使我们无需为每个创建的双向循环链表编写专用函数，从而大大提高了代码的重用性。

由于VC编译器对部分操作符并不支持，所以本节的代码均在Linux环境下采用gcc编译运行。读者在开始学习本节之前，可以从网上先下载一个Linux内核双向循环链表的头文件list.h，同时鉴于内核版本的不同，下载的头文件可能有些细小的差别，但是这并不影响我们对双向循环链表的学习。对双向循环链表的讲解大致按照其头文件中代码的先后顺序进行。

6.6.1　头结点的创建

首先来看list_head结构的实现，代码如下：

struct list_head{

struct list_headnext，prev；

}；

在Linux内核双向循环链表中，用list_head类型定义一个变量，将该变量作为一个成员嵌入到宿主结构中。所谓的宿主结构体，就是所创建的双向循环链表中每个结点的结构体类型。可以将链表结构放在宿主结构内的任何地方，当然也可以为链表结构取任何可用的变量名。注意，list_head结构体类型中同样有在建立双向循环链表时所用到的前指针域和后指针域。我们可以用list_head中的成员和相对应的处理函数来对链表进行遍历操作，要想得到宿主结构的指针，可以使用list_entry计算出来，先别急着知道list_entry是什么，我们会在下面讲解，接着往下看。

在宿主结构体中定义了list_head之后，接下来当然要对所有创建的双向循环链表头结点进行初始化工作。

方法一：

define LIST_HEAD_INIT（name）{＆（name），＆（name）}

define LIST_HEAD（name）\

struct list_head name=LIST_HEAD_INIT（name）

方法二：

define INIT_LIST_HEAD（ptr）do{\

（ptr）-＞next=（ptr）；（ptr）-＞prev=（ptr）；\

}while（0）

对头结点进行初始化有两种方法：一种是使用INIT_LIST_HEAD（ptr）宏进行初始化，使用这种方法时需要先定义一个头结点；另外一种是使用LIST_HEAD（name）宏进行初始化，在使用该方法进行初始化的时候，无需定义头结点，只需给出宏中的参数，即给出需要进行初始化的头结点名。