片方向および双方向リンク リスト

  • [アーティクル]

片方向リンクリスト

オペレーティングシステムは、 SINGLE_LIST_ENTRY 構造を使用する片方向リンクリストのビルトインサポートを提供します。 片方向リンクリストは、リストの先頭といくつかのリスト項目から構成されます。 (リストが空の場合、リスト項目の数は0です。)　リストの先頭は 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を提供します。 それぞれ追加のスピンロックパラメータを取ります。 ルーチンは、リストを更新する前にスピンロックを取得し、操作の完了後にスピンロックをリリースします。 ロックが保持されている間、割り込みは無効化されます。 リスト上の各操作が他のすべての操作と同期していることを保証するために、リスト上の各操作は同じスピンロックを使用しする必要があります。 スピンロックは、 ExInterlockedXxxList ルーチンのみで使用しなければなりません。 スピンロックを他の目的で使用しないでください。 ドライバは複数のリストに対して同じロックを使用できますが、この動作はロックの競合を増加させるため、ドライバはそれを避ける必要があります。

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

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

システムは、より効率的なアトミック片方向リンクリストの代替実装も提供しています。 詳細については、 Sequenced Singly Linked Listsを参照してください。

双方向リンクリスト

オペレーティングシステムは、 SINGLE_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を使います。 片方向リンクリストを使ったこのテクニックの例については、上記の片方向リンクリストを参照してください。

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

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

同じリストに対するアトミック版と非アトミック版のリスト操作の呼び出しを混在させないでください。 アトミック版と非アトミック版が同じリスト上で同時に実行されると、データ構造が破損し、コンピュータが応答しなくなったり、バグチェックが行われなくなったり（つまり、 crashする)可能性があります。 (アトミック版と非アトミック版のリスト操作の呼び出しが混在するのを避けるために、非アトミックルーチンを呼び出している間はスピンロックを取得する作業はできません。この方法でのスピンロックの使用はサポートされておらず、リストの破損を引き起こす可能性があります。)

順序付き片方向リンクリスト

順序付き片方向リンクリストは、アトミック操作をサポートする片方向リンクリストの実装です。 Singly Linked Listsで説明されている片方向リンクリストの実装よりも、アトミック操作に対して効率的です。

SLIST_HEADER 構造はシーケンシャル片方向リンクリストの先頭を記述するために使われ、 SLIST_ENTRY 構造はリストのエントリを記述するために使われます。

ドライバはリストを次のように操作します：

  • SLIST_HEADER 構造体を初期化するには、 ExInitializeSListHeadを使います。

  • リストに新しいエントリーを追加するには、 LIST_ENTRY を割り当てて新しいエントリーを表し、 ExInterlockedPushEntrySLi を呼び出してエントリーをリストの先頭に追加します。

  • ExInterlockedPopEntrySLisを使って、リストから最初のエントリーを削除します。

  • リストを完全に消去するには、 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を参照してください。

Warning 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と互換性のある順序付き片方向リンクリスト関数のバージョンを使用するようになります。