单向和双向链接列表

单独链接列表

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

每个 SINGLE_LIST_ENTRY 结构都包含一个 Next 成员，该成员指向另一个 SINGLE_LIST_ENTRY 结构。 在表示列表头 的SINGLE_LIST_ENTRY 结构中， “下一个 ”成员指向列表中的第一个条目;如果列表为空，则为 NULL。 在表示列表中的项 的SINGLE_LIST_ENTRY 结构中， Next 成员指向列表的下一个条目;如果此条目是列表中的最后一个条目，则为 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。 每个参数都采用附加的旋转锁参数。 例程在更新列表之前获取旋转锁，然后该例程在操作完成后释放旋转锁。 保持锁定时，会禁用中断。 列表中的每个操作都必须使用相同的旋转锁，以确保列表中的每个此类操作都与所有其他操作同步。 必须仅对这些 ExInterlockedXxx列表 例程使用旋转锁。 请勿将旋转锁用于任何其他目的。 驱动程序可以对多个列表使用相同的锁，但此行为会增加锁争用，因此驱动程序应避免它。

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

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

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

双重链接列表

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

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

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

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

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

操作双重链接列表的例程将指针指向表示列表头 的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。 有关此方法的示例（使用单一链接列表），请参阅上面的单一链接列表。

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

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

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

序列单一链接列表

序列单一链接列表是支持原子操作的单独链接列表的实现。 与实现 单向链接列表中所述的单独链接列表相比，它对于原子操作更有效。

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 字节。

Windows XP 和更高版本的 Windows 提供在 Windows 2000 中不可用的经过排序的单独链接列表函数的优化版本。 如果驱动程序使用这些函数并且还必须使用 Windows 2000 运行，则驱动程序必须定义 _WIN2K_COMPAT_SLIST_USAGE 标志，如下所示：

#define _WIN2K_COMPAT_SLIST_USAGE

对于基于 x86 的处理器，此标志会导致编译器使用与 Windows 2000 兼容的序列单链接列表函数的版本。