次の方法で共有

1 つのリストと 2 つのリンクされたリスト

単方向リンクリスト

オペレーティング システムは、 SINGLE_LIST_ENTRY 構造を使用する 1 つのリンクされたリストに対して組み込みのサポートを提供します。 1 つのリンク リストは、リスト ヘッドといくつかのリスト エントリで構成されます。 (リストが空の場合、リスト エントリの数は 0 です)。各リスト エントリは、 SINGLE_LIST_ENTRY 構造体として表されます。 リスト ヘッドは、 SINGLE_LIST_ENTRY 構造体としても表されます。

各SINGLE_LIST_ENTRY構造体には、別のSINGLE_LIST_ENTRY構造体を指す Next メンバーが含まれています。 リストの先頭を表す SINGLE_LIST_ENTRY 構造体では、 Next メンバーはリストの最初のエントリを指すか、リストが空の場合は NULL です。 リスト内 の エントリを表すSINGLE_LIST_ENTRY構造体では、 Next メンバーはリストの次のエントリを指します。このエントリがリストの最後のエントリの場合は NULL になります。

1 つのリンクされたリストを操作するルーチンは、リストの先頭を表す SINGLE_LIST_ENTRY へのポインターを受け取ります。 次 のポインター は、操作後にリストの最初のエントリを指すよう更新します。

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を使用します。 以下に、ドライバー定義のエントリを 1 つのリンク リストに挿入および削除するルーチンの例を示します。

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 による、1 つのリンクされたリストの共有をサポートできます。 これらのルーチンは、スピン ロックが保持されているときに割り込みを無効にします。 したがって、ISR とドライバー スレッドは、デッドロックを危険にさらすことなく、これらの ExInterlockedXxxList ルーチンの呼び出しで同じスピン ロックを安全に使用できます。

同じリストに対するリスト操作のアトミックバージョンと非原子バージョンの呼び出しを混在させないでください。 アトミックバージョンと非原子バージョンが同じリストで同時に実行されている場合、データ構造が破損し、コンピュータが応答を停止したりバグチェック( クラッシュ)したりする可能性があります。 (リスト操作のアトミックバージョンと非原子バージョンの呼び出しを混在させる代わりに、非原子ルーチンを呼び出している間はスピンロックを取得できません。この方法でスピン ロックを使用することはサポートされておらず、リストの破損が引き続き発生する可能性があります)。

システムは、より効率的なアトミックな単一リンクリストの代替実装も提供します。 詳細については、順序付けされた単方向リンクリストを参照してください。

二重リンク リスト

オペレーティング システムは、 LIST_ENTRY構造を 使用する二重リンク リストの組み込みサポートを提供します。 二重にリンクされたリストは、リストヘッドといくつかのリストエントリで構成されています。 (リストが空の場合、リスト エントリの数は 0 です)。各リスト エントリは、 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を使用します。 この手法の例として、1 つのリンクリストを使用する場合は、上記の「Singly Linked Lists」を参照してください。

システムには、リスト操作のアトミック バージョン、 ExInterlockedInsertHeadList、 ExInterlockedInsertTailList、 ExInterlockedRemoveHeadList も用意されています。 RemoveTailList または RemoveEntryList のアトミック バージョンはありません。 各ルーチンは、余分なスピン ロック パラメーターを受け取ります。 ルーチンは、リストを更新する前にスピン ロックを取得し、操作の完了後にスピン ロックを解放します。 ロックが保持されている間、割り込みは無効になります。 リストに対する各操作は、同じスピン ロックを使用して、リストに対する各操作が互いに同期されるようにする必要があります。 スピン ロックは、これらの ExInterlockedXxxList ルーチンでのみ使用する必要があります。 スピン ロックは他の目的には使用しないでください。 ドライバーは複数のリストに対して同じロックを使用できますが、この動作によりロックの競合が増加するため、ドライバーはそれを回避する必要があります。

たとえば、 ExInterlockedInsertHeadList、 ExInterlockedInsertTailList、 ExInterlockedRemoveHeadList ルーチンは、IRQL = PASSIVE_LEVEL で実行されているドライバー スレッドと DIRQL で実行されている ISR による二重リンク リストの共有をサポートできます。 これらのルーチンは、スピン ロックが保持されているときに割り込みを無効にします。 したがって、ISR とドライバー スレッドは、デッドロックを危険にさらすことなく、これらの ExInterlockedXxxList ルーチンの呼び出しで同じスピン ロックを安全に使用できます。

同じリストに対するリスト操作のアトミックバージョンと非原子バージョンの呼び出しを混在させないでください。 アトミックバージョンと非原子バージョンが同じリストで同時に実行されている場合、データ構造が破損し、コンピュータが応答を停止したりバグチェック( クラッシュ)したりする可能性があります。 (リスト操作のアトミックバージョンと非原子バージョンの呼び出しが混在しないように、非原子ルーチンを呼び出している間はスピンロックを取得できません。この方法でスピン ロックを使用することはサポートされておらず、リストの破損が引き続き発生する可能性があります)。

順序付けられた単一リンクリスト

単方向リンクリストの実装であるシーケンシャル化された単方向リンクリストは、アトミック操作をサポートします。 これは、単方向リンクリストで説明されている単方向リンクリストの実装よりも、アトミック操作に関して効率的です。

SLIST_HEADER構造体は、1 つの順序でリンクされたリストの先頭を記述するために使用され、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を使用します。 この手法の例として、非順序の単方向連結リストを使用する場合は、「Singly Linked Lists」を参照してください。

警告 64 ビットの Microsoft Windows オペレーティング システムの場合、 SLIST_ENTRY 構造体は 16 バイトでアラインされている必要があります。