3.7　链表

内核在很多内部数据结构中使用了环形双向链表。例如，系统中的所有进程使用EPROCESS结构进行管理，这些结构就用一个环形双向链表连接在一起，其中链表的头部存储在内核变量PsActiveProcessHead中。

所有这样的链表都使用相似的方式围绕着LIST_ENTRY结构进行构建。这个结构定义如下：

图3-2展示了一个这样的链表，它包含一个头和三个（LIST_ENTRY的）实例。

图3-2　环形链表

将一个LIST_ENTRY结构嵌入需要成为链表项的真正结构中。比如在EPROCESS结构中，ActiveProcessLinks字段就是LIST_ENTRY类型，指向后一个和前一个EPROCESS结构中的LIST_ENTRY对象。链表的头部另行存放，在进程中，是放在PsActiveProcessHead里。给出LIST_ENTRY的地址，可以用CONTAINING_RECORD宏获得指向真正的数据结构的指针。

举个例子，假设现在需要管理一个链表，链表的类型为MyDataItem结构，定义如下：

在操作这样的链表时，需要有一个存储在变量里的链表头部。这意味着最自然的遍历链表的方式是使用LIST_ENTRY的Flink字段，它指向链表中的下一个LIST_ENTRY。给定一个指向LIST_ENTRY的指针之后，我们接着想要的是包含这个LIST_ENTRY字段的MyDataItem结构。这里就要用到CONTAINING_RECORD宏了：

这个宏能够执行正确的偏移量计算，并对结果进行强制类型转换（本例中是转换成MyDataItem）。

表3-5显示了常见的链表操作函数。所有这些函数的执行时间都为常量。

表3-5　环形链表的操作函数

表3-5中的最后3个函数使用了一种称为自旋锁（spinlock）的同步原语来执行原子化的操作。自旋锁将在第6章中讨论。