Singly 和 Doubly 連結清單

  • 發行項

Singly 連結清單

作業系統提供內建支援使用 SINGLE_LIST_ENTRY 結構的單一連結清單。 單選連結清單是由清單前端加上一些清單專案所組成。 (如果清單是空的，則清單專案數目為零。) 每個清單專案都以 SINGLE_LIST_ENTRY 結構表示。 清單前端也會以 SINGLE_LIST_ENTRY 結構表示。

每個 SINGLE_LIST_ENTRY 結構都包含 一個 Next 成員，指向另一個 SINGLE_LIST_ENTRY 結構。 在代表清單前端 的SINGLE_LIST_ENTRY 結構中， Next 成員會指向清單中的第一個專案，如果清單是空的，則為 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 和驅動程式執行緒可以在這些 ExInterlockedXxx清單 常式的呼叫中安全地使用相同的微調鎖定，而不會有死結的風險。

請勿在相同清單上混合對清單作業不可部分完成和非不可部分完成版本的呼叫。 如果不可部分完成和非不可部分完成的版本同時在相同的清單上執行，資料結構可能會損毀，而且電腦可能會停止回應或錯誤檢查， (亦即當 機) 。 (您無法在呼叫非不可部分完成常式時取得微調鎖定，做為混合對不可部分完成和非不可部分完成版本的清單作業呼叫的替代方案。不支援以此方式使用微調鎖定，而且可能仍會導致清單損毀。)

系統也會提供更有效率之不可部分完成連結清單的替代實作。 如需詳細資訊，請參閱 循序連結清單。

多加連結的清單

作業系統會針對使用 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。 如需這項技術的範例，請使用 Singly 連結清單，請參閱上述的 Singly 連結清單。

系統也會提供清單作業的不可部分完成版本 、ExInterlockedInsertHeadList、 ExInterlockedInsertTailList和 ExInterlockedRemoveHeadList。 (請注意，沒有任何不可部分完成版本的 RemoveTailList 或 RemoveEntryList.) 每個常式都會採用額外的微調鎖定參數。 常式會在更新清單之前取得微調鎖定，然後在作業完成之後釋放微調鎖定。 保留鎖定時，會停用中斷。 清單上的每個作業都必須使用相同的微調鎖定，以確保清單中的每個這類作業彼此同步。 您只能搭配這些 ExInterlockedXxx清單 常式使用微調鎖定。 請勿將微調鎖定用於任何其他用途。 驅動程式可以針對多個清單使用相同的鎖定，但此行為會增加鎖定競爭，讓驅動程式應該避免。

例如， ExInterlockedInsertHeadList、 ExInterlockedInsertTailList和 ExInterlockedRemoveHeadList 常式可以支援由在 IRQL = PASSIVE_LEVEL和在 DIRQL 上執行的 ISR 共用多工連結清單。 這些常式會在保留微調鎖定時停用中斷。 因此，ISR 和驅動程式執行緒可以在這些 ExInterlockedXxx清單 常式的呼叫中安全地使用相同的微調鎖定，而不會有死結的風險。

請勿在相同清單上混合對清單作業不可部分完成和非不可部分完成版本的呼叫。 如果不可部分完成和非不可部分完成的版本同時在相同的清單上執行，資料結構可能會損毀，而且電腦可能會停止回應或錯誤 檢查， ( 即當機) 。 (您無法在呼叫非不可部分完成的常式時取得微調鎖定，以避免混合對清單作業不可部分完成和非不可部分完成版本的呼叫。不支援以此方式使用微調鎖定，而且可能仍會導致清單損毀。)

循序連結清單

循序連結清單是支援不可部分完成作業之單一連結清單的實作。 比起 Singly Linked Lists 中所述之 Singly linked 清單的實作，不可部分完成的作業更有效率。

SLIST_HEADER結構可用來描述循序連結清單的前端，而SLIST_ENTRY則用來描述清單中的專案。

驅動程式會動作清單，如下所示：

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。 如需這項技術的範例，使用非循序連結清單，請參閱 Singly 連結清單。

警告 對於 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 相容的循序清單函式版本。