单向和双向链接列表

单链表

作系统为使用 SINGLE_LIST_ENTRY 结构的单向链接列表提供内置支持。 单向链接列表由列表头以及一些列表条目组成。 （如果列表为空，则列表项数为零。每个列表项都表示为 SINGLE_LIST_ENTRY 结构。 列表头也表示为 SINGLE_LIST_ENTRY 结构。

每个SINGLE_LIST_ENTRY结构都包含指向另一个SINGLE_LIST_ENTRY结构的 Next 成员。 在表示列表头的 SINGLE_LIST_ENTRY 结构中， 下一 个成员指向列表中的第一个条目，如果列表为空，则为 NULL。 在表示列表中的条目的 SINGLE_LIST_ENTRY 结构中， “下一个 ”成员指向列表的下一个条目，如果该条目是列表中的最后一个条目，则为 NULL。

作单向链接列表的例程将指针指向表示列表头 的SINGLE_LIST_ENTRY 。 更新Next指针，使其在操作后指向列表的第一个条目。

假设 ListHead 变量是指向表示列表头 的SINGLE_LIST_ENTRY 结构的指针。 驱动程序按如下方式操作 ListHead：

• 若要将列表初始化为空，请将 ListHead-Next> 设置为 NULL。

• 若要向列表添加新条目，请分配 一个SINGLE_LIST_ENTRY 来表示新条目，然后调用 PushEntryList 将条目添加到列表的开头。

• 使用 PopEntryList 从列表中弹出第一个条目。

SINGLE_LIST_ENTRY 本身只有一个 Next 成员。 若要在列表中存储自己的数据，请将 SINGLE_LIST_ENTRY 嵌入为描述列表条目的结构的成员，如下所示。

typedef struct {
  // driver-defined members
  .
  .
  .
  SINGLE_LIST_ENTRY SingleListEntry;
 
  // other driver-defined members
  .
  .
  .
} XXX_ENTRY;

若要向列表添加新条目，请分配 XXX_ENTRY 结构，然后将指向 SingleListEntry 成员的指针传递给 PushEntryList。 若要将指向 SINGLE_LIST_ENTRY 的指针转换回 XXX_ENTRY，请使用 CONTAINING_RECORD。 下面是从单向链接列表中插入和删除驱动程序定义条目的例程示例。

typedef struct {
  PVOID DriverData1;
  SINGLE_LIST_ENTRY SingleListEntry;
  ULONG DriverData2;
} XXX_ENTRY, *PXXX_ENTRY;

void
PushXxxEntry(PSINGLE_LIST_ENTRY ListHead, PXXX_ENTRY Entry)
{
    PushEntryList(ListHead, &(Entry->SingleListEntry));
}

PXXX_ENTRY
PopXxxEntry(PSINGLE_LIST_ENTRY ListHead)
{
    PSINGLE_LIST_ENTRY SingleListEntry;
    SingleListEntry = PopEntryList(ListHead);
    return CONTAINING_RECORD(SingleListEntry, XXX_ENTRY, SingleListEntry);
}

系统还提供列表操作的原子版本，即 ExInterlockedPopEntryList 和 ExInterlockedPushEntryList。 每个元素都接收额外的旋转锁参数。 该例程在更新列表之前获取旋转锁，然后在作完成后释放旋转锁。 锁定时，将禁用中断。 列表中的每个操作都必须使用相同的旋转锁，以确保列表中的每项操作都与其他所有操作同步。 必须仅在这些 ExInterlockedXxxList 函数中使用旋转锁。 不要将旋转锁用于任何其他目的。 驱动程序可以对多个列表使用相同的锁，但此行为会增加锁争用，因此驱动程序应避免。

例如，ExInterlockedPopEntryList 和 ExInterlockedPushEntryList 例程可以支持由在 IRQL = PASSIVE_LEVEL 下运行的驱动程序线程和在 DIRQL 下运行的 ISR 共享单向链表。 这些例程在保持旋转锁时禁用中断。 因此，ISR 和驱动程序线程可以在调用这些 ExInterlockedXxxList 例程时安全地使用相同的旋转锁，而不会造成死锁的风险。

不要将对同一列表上列表作的原子和非原子版本的调用混为一谈。 如果原子和非原子版本同时在同一列表中运行，则数据结构可能会损坏，并且计算机可能会停止响应或 bug 检查（即 崩溃）。 （不能在调用非原子例程时获取旋转锁，作为混合调用原子和非原子版本的列表作的替代方法。不支持以这种方式使用旋转锁，但仍可能导致列表损坏。

该系统还提供原子单向链接列表的替代实现，效率更高。 有关详细信息，请参阅 排序的 Singly 链接列表。

多倍链接列表

操作系统为使用LIST_ENTRY结构的双向链表提供了内置支持。 一个双重链接的列表由列表头加上一些列表条目组成。 （如果列表为空，则列表项数为零。每个列表项都表示为 LIST_ENTRY 结构。 列表头也表示为 LIST_ENTRY 结构。

每个 LIST_ENTRY 结构都包含 Flink 成员和 Blink 成员。 这两个成员都是指向 LIST_ENTRY 结构的指针。

在表示列表头 的LIST_ENTRY 结构中， Flink 成员指向列表中的第一个条目， Blink 成员指向列表中的最后一个条目。 如果列表为空，则列表头的 Flink 和 Blink 指向列表头本身。

在表示列表中的条目 的LIST_ENTRY 结构中， Flink 成员指向列表中的下一个条目， Blink 成员指向列表中的上一项。 （如果条目是列表中的最后一个条目， 则 Flink 指向列表头。同样，如果条目是列表中的第一个条目， Blink 指向列表头。

虽然这些规则乍看之下可能令人惊讶，但它们允许在没有条件代码分支的情况下实现列表插入和删除操作。

将指针指向表示列表头的LIST_ENTRY的例程用于操作双向链表。 这些例程更新列表头中的 Flink 和 Blink 成员，以便这些成员指向生成的列表中的第一个和最后一个条目。

假设 ListHead 变量是指向表示列表头 的LIST_ENTRY 结构的指针。 驱动程序按如下方式操作 ListHead：

• 若要将列表初始化为空，请使用 InitializeListHead，它初始化 ListHead->Flink 和 ListHead->Blink 以指向 ListHead。

• 若要在列表头插入新条目，请分配 一个LIST_ENTRY 来表示新条目，然后调用 InsertHeadList 在列表开头插入该条目。

• 若要将新条目追加到列表尾部，请分配一个 LIST_ENTRY 来表示新条目，然后调用 InsertTailList 在列表末尾插入该条目。

• 若要从列表中删除第一个条目，请使用 RemoveHeadList。 这会返回指向列表中已删除条目的指针;如果列表为空，则返回 ListHead 。

• 若要从列表中删除最后一个条目，请使用 RemoveTailList。 这会返回指向列表中已删除条目的指针;如果列表为空，则返回 ListHead 。

• 若要从列表中删除指定条目，请使用 RemoveEntryList。

• 若要查看列表是否为空，请使用 IsListEmpty。

• 若要将列表追加到另一个列表的尾部，请使用 AppendTailList。

LIST_ENTRY 本身只拥有 Blink 和 Flink 这两个字段。 若要在列表中存储自己的数据，请将 LIST_ENTRY 嵌入为描述列表条目的结构的成员，如下所示。

typedef struct {
  // driver-defined members
  .
  .
  .
  LIST_ENTRY ListEntry;
 
  // other driver-defined members.
  .
  .
  .
} XXX_ENTRY;

若要向列表添加新条目，请分配 XXX_ENTRY 结构，然后将指向 ListEntry 成员的指针传递给 InsertHeadList 或 InsertTailList。 若要将指针从 LIST_ENTRY 转换回 XXX_ENTRY，请使用 CONTAINING_RECORD。 有关此方法的示例，使用单向链接列表，请参阅上面的 Singly 链接列表。

系统还提供列表操作的原子版本：ExInterlockedInsertHeadList、ExInterlockedInsertTailList 和 ExInterlockedRemoveHeadList。 没有 RemoveTailList 或 RemoveEntryList 的原子版本。 每个例程都采用额外的旋转锁参数。 该例程在更新列表之前获取旋转锁，然后在作完成后释放旋转锁。 锁定时，将禁用中断。 列表中的每个操作都必须使用相同的自旋锁，以确保列表中每个这样的操作都与其他操作同步。 必须仅在这些 ExInterlockedXxxList 函数中使用旋转锁。 不要将旋转锁用于任何其他目的。 驱动程序可以对多个列表使用相同的锁，但此行为会增加锁争用，因此驱动程序应避免。

例如，ExInterlockedInsertHeadList、ExInterlockedInsertTailList 和 ExInterlockedRemoveHeadList 例程可以支持一个在 IRQL = PASSIVE_LEVEL 运行的驱动程序线程与一个在 DIRQL 上运行的 ISR 共享双向链接列表。 这些例程在保持旋转锁时禁用中断。 因此，ISR 和驱动程序线程可以在调用这些 ExInterlockedXxxList 例程时安全地使用相同的旋转锁，而不会造成死锁的风险。

不要将对同一列表上列表作的原子和非原子版本的调用混为一谈。 如果原子和非原子版本同时在同一列表中运行，则数据结构可能会损坏，并且计算机可能会停止响应或 bug 检查（即 崩溃）。 调用非原子例程时无法获取自旋锁，以避免将调用混合到原子和非原子版本的列表操作中。不支持以这种方式使用自旋锁，仍可能导致列表损坏。

已排序的 Singly 链接列表

有序的单链表是支持原子操作的单链表的实现。 它在原子操作方面比单链表中描述的实现更高效。

SLIST_HEADER结构用于描述序列单向链接列表的头，而SLIST_ENTRY用于描述列表中的条目。

驱动按如下方式操作列表：

• 若要初始化 SLIST_HEADER 结构，请使用 ExInitializeSListHead。

• 若要向列表添加新条目，请分配 一个SLIST_ENTRY 来表示新条目，然后调用 ExInterlockedPushEntrySList 将条目添加到列表的开头。

• 使用 ExInterlockedPopEntrySList 从列表中弹出第一个条目。

• 若要完全清除列表，请使用 ExInterlockedFlushSList。

• 若要确定列表中的条目数，请使用 ExQueryDepthSList。

SLIST_ENTRY本身只有一个Next成员。 若要在列表中存储自己的数据，请将 SLIST_ENTRY 嵌入为描述列表条目的结构的成员，如下所示。

typedef struct 
{
  // driver-defined members
  .
  .
  .
  SLIST_ENTRY SListEntry;
  // other driver-defined members
  .
  .
  .

} XXX_ENTRY;

若要向列表添加新条目，请分配 XXX_ENTRY 结构，然后将指向 SListEntry 成员的指针传递给 ExInterlockedPushEntrySList。

若要将指向 SLIST_ENTRY 的指针转换回 XXX_ENTRY，请使用 CONTAINING_RECORD。 有关此技术的示例，使用非顺序的单链表，请参阅单链表。

警告 对于 64 位 Microsoft Windows 操作系统，SLIST_ENTRY 结构必须 16 字节对齐。