3.5　链表

链表作为内核开发中常见的数据结构，主要分为单向链表与双向链表，单向链表的链表节点中只有一个链表节点指针，该指针指向后面一个链表节点。相应地，双向链表指链表节点中有两个链表节点指针，分别指向前一个链表节点以及后一个链表节点。由于双向链表的节点指针分别指向了前后两个节点，所以双向链表在插入、移除等操作上比单向链表更为方便。

下面为读者重点介绍双向链表，单向链表作为双向链表的一个子集，请读者自行研究。在下面的篇幅中，所提及的“链表”均指双向链表。

WDK对链表的定义为：

LIST_ENTRY表示一个链表的节点，其中Flink成员指向当前节点的后一个节点，Blink成员指向当前节点的前一个节点。

刚接触LIST_ENTRY结构的读者可能会有疑问：该结构只是定义了前后两个指针，并没有其他实质性的内容，那么其他内容存在什么位置呢？LIST_ENTRY应该怎么使用呢？下面通过一个例子来为读者解答：

笔者定义了一个TestListEntry结构体，结构体里面有4个数据成员，现在需要把这个结构体作为链表的一个节点，具体做法是：把上面介绍的链表 LIST_ENTRY作为TestListEntry结构体的一个成员，如：

读者请注意，m_ListEntry可以放在结构体的任意位置，没有强制的要求，上面的例子m_ListEntry处于结构体的中间部分，读者完全可以把这个m_ListEntry放在结构体的开头或其他位置。在64位系统下，TestListEntry结构体的内存布局如图3-3所示。

从图中可以看到，m_ulDataA成员处于最低地址，m_ulDataD处于最高地址，而链表节点LIST_ENTRY的两个成员展开后在结构体中分别为Flink与Blink，其中Flink处于低地址，Blink处于高地址。

注意：Flink成员所在的地址实际上就是m_ListEntry的地址。多个TestListEntry组成链表时的结构如图3-4所示。

上图只画出了链表中的两个节点，假设为节点A与节点B，节点A的Blink指向前一个节点的Flink成员所在地址（图中未画出），节点A的Flink指向节点B的Flink所在地址；节点B的Flink指向节点B后一个节点的Flink成员所在地址（图中未画出），节点B的Blink指向节点A的Flink所在地址。从图中的关系可知，无论是Flink成员还是Blink成员，都指向后一个（或前一个）节点的Flink成员所在地址，而Flink成员所在地址，即是节点中LIST_ENTRY成员所在地址（在本例中为m_ListEntry）。

在实际情况下，为了方便操作，会定义一个链表头节点，头节点不包含任何内容，只是一个LIST_ENTRY结构。对于带头节点的链表，头节点与节点之前的关系如图3-5所示。

上面介绍了LIST_ENTRY与结构体之间的关系，相信读者对WDK提供的链表结构有了大致的认识与理解。下面为读者介绍LIST_ENTRY的具体操作，所介绍的操作均基于链表具有头节点的大前提。

3.5.1　头节点初始化

链表头节点不携带任何内容，只表示链表的头部，对链表的所有操作都是从头部开始的，当链表只有一个头节点而没有其他节点时，该链表就是一个空的链表，头节点的Flink与Blink指向头节点自身。

下面的代码定义了一个头节点，并对头节点进行初始化：

InitializeListHead函数初始化一个头节点，这里的初始化，实际上就是修改头节点的Flink以及Blink成员，使其指向自身。

InitializeListHead函数的原型如下：

函数只有一个参数ListHead，表示需要被初始化的头节点，从WDK的头文件中可以找到InitializeListHead函数的实现：

InitializeListHead函数的实现非常简单，请读者自行阅读理解。

3.5.2　节点插入

常见的节点插入操作有两种，一种是把节点插入到链表的第一个位置，另外一种是把节点插入到链表的最后一个位置。请注意，把节点插入到链表的第一个位置，准确来说是指把该节点插入到链表头节点的后面、第一个节点的前面。头节点只表示一个链表头部，并非链表“身体（BODY）”，所有链表的操作，都是基于链表“身体（BODY）”而言的。

InsertHeadList函数的作用是把一个节点插入到链表的第一个位置，相应地，InsertTailList函数的作用是把一个节点插入到链表的最后一个位置，两个函数的参数相同：

其中ListHead表示链表的头节点，即为需要被插入节点的链表头节点，Entry表示需要插入的链表节点。下面用一段代码来演示链表节点的插入：

上面的代码定义了一个头节点以及三个链表节点，首先对三个节点进行赋值，用于标识三个节点，然后通过InitializeListHead函数初始化链表头节点，接着使用InsertHeadList函数，把节点B插入到链表中，在插入前链表为空，插入后链表中存在一个节点B，紧接着使用InsertHeadList函数把节点A插入到链表最前面，此时链表中的节点为：头节点→节点A→节点B，最后使用InsertTailList函数，把节点C插入到链表的最后面，插入完成后的链表：头节点→节点A→节点B→节点C。

3.5.3　链表遍历

在大部分情况下，开发者需要在链表中查找某一个具体的节点，这个操作需要对链表进行遍历。链表遍历可以通过Flink指针从前往后遍历，也可以通过Blink从后往前遍历。如无特殊逻辑要求，一般是从前往后遍历，这样比较符合习惯。

下面的代码衔接3.5.2节的代码，通过遍历ListHeader 链表，把链表中每一个节点信息打印出来：

上面的代码定义了pListEntry 指针变量用于遍历，把ListHeader.Flink的值赋给pListEntry，此时pListEntry指向链表中的第一个节点。在while循环中，首先访问节点的具体信息，然后pListEntry 指向下一个节点，循环结束的条件是pListEntry == &ListHeader，读者可以结合图3-5进行代码阅读。

还需要提及的一点是pTestEntry指针的获取，在while循环块中，是通过pListEntry指针进行遍历的，而pListEntry指向的地址是TestListEntry结构体中的m_ListEntry地址，而m_ListEntry成员的地址并不是这个结构体的首地址，所以这里需要通过一个宏CONTAINING_RECORD把m_ListEntry的地址转换成结构体TestListEntry的首地址，CONTAINING_RECORD宏的用法如下：

其中Address表示LIST_ENTRY的地址，在本例中，就是pListEntry指向的地址（pListEntry指向的是结构体中m_ListEntry地址），Type表示类型，在本例中为TestListEntry，最后的Field表示结构体中LIST_ENTRY成员的名字，在本例中为m_ListEntry。

CONTAINING_RECORD宏通过Type与Field这两个成员，计算出Field成员距离结构体顶部的内存距离，然后结合具体的Address成员，算出最终的结构体首地址，WDK对CONTAINING_ RECORD宏的定义如下：

有兴趣的读者可以深入研究该宏的的实现原理。

对于本例代码，驱动运行后输出：

从输出的日志可以知道，ListPtr与Entry的距离，即m_ListEntry与结构体首地址的内存差距为8字节，与图3-3一致。

3.5.4　节点移除

移除节点有三种方式：移除链表中的第一个节点、移除链表中的最后一个节点、移除链表中特定的节点。

移除链表中第一个节点与最后一个节点分别使用RemoveHeadList以及RemoveTailList函数，这两个函数的用法基本一致：

函数仅有一个参数，表示所需要移除的链表头节点指针，这两个函数的返回值均为PLIST_ENTRY，成功移除则返回从链表移除的节点指针，如果无节点可以移除（如链表为空）则返回NULL。

在某些情况下，开发者需要移除某个特定节点，即可使用RemoveEntryList函数，函数原型如下：

Entry表示需要移除的链表节点指针，RemoveEntryList函数的返回值类型为BOOLEAN，节点被移除后，若链表变为空链表，RemoveEntryList返回TRUE，否则返回FALSE。

最后为读者介绍一下链表状态的判断方法，当链表中只有头节点，没有其他节点时，这个链表就是一个空链表，用IsListEmpty可以判断一个链表是否为空：

ListHead表示链表的头节点指针，IsListEmpty返回TRUE表示链表为空链表，返回FALSE表示链表非空。