Freigeben über

Einfach und doppelt verkettete Listen

Einfach verkettete Listen

Das Betriebssystem bietet integrierte Unterstützung für verknüpfte Listen, die SINGLE_LIST_ENTRY Strukturen verwenden. Eine einfach verkettete Liste besteht aus einem Listenkopf plus einigen Listeneinträgen. (Die Anzahl der Listeneinträge ist null, wenn die Liste leer ist.) Jeder Listeneintrag wird als SINGLE_LIST_ENTRY Struktur dargestellt. Der Listenkopf wird auch als SINGLE_LIST_ENTRY Struktur dargestellt.

Jede SINGLE_LIST_ENTRY-Struktur enthält ein Element "Weiter" , das auf eine andere SINGLE_LIST_ENTRY Struktur verweist. In der SINGLE_LIST_ENTRY Struktur, die den Listenkopf darstellt, verweist das nächste Element auf den ersten Eintrag in der Liste oder ist NULL, wenn die Liste leer ist. In der SINGLE_LIST_ENTRY Struktur, die einen Eintrag in der Liste darstellt, zeigt das Nächste Element auf den nächsten Eintrag der Liste oder ist NULL, wenn dieser Eintrag der letzte in der Liste ist.

Die Routinen, mit denen eine singly verknüpfte Liste bearbeitet wird, verweisen auf eine SINGLE_LIST_ENTRY , die den Listenkopf darstellt. Sie aktualisieren den Nächsten Zeiger so, dass er auf den ersten Eintrag der Liste nach dem Vorgang verweist.

Angenommen, die ListHead-Variable ist ein Zeiger auf die SINGLE_LIST_ENTRY Struktur, die den Listenkopf darstellt. Ein Treiber bearbeitet ListHead wie folgt:

  • Um die Liste als leer zu initialisieren, legen Sie ListHead-Next> auf NULL fest.

  • Um der Liste einen neuen Eintrag hinzuzufügen, weisen Sie einen SINGLE_LIST_ENTRY zu, um den neuen Eintrag darzustellen, und rufen Sie dann PushEntryList auf, um den Eintrag am Anfang der Liste hinzuzufügen.

  • Entfernen Sie den ersten Eintrag aus der Liste, indem Sie PopEntryList verwenden.

Ein SINGLE_LIST_ENTRY selbst hat nur ein Nächstes Mitglied. Um Ihre eigenen Daten in den Listen zu speichern, betten Sie die SINGLE_LIST_ENTRY als Element der Struktur ein, die den Listeneintrag beschreibt, wie folgt.

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

Um der Liste einen neuen Eintrag hinzuzufügen, weisen Sie eine XXX_ENTRY-Struktur zu, und übergeben Sie dann einen Zeiger auf das SingleListEntry-Element, der an PushEntryList weitergegeben wird. Verwenden Sie CONTAINING_RECORD, um einen Zeiger von SINGLE_LIST_ENTRY wieder in XXX_ENTRY umzuwandeln. Nachfolgend finden Sie ein Beispiel für Routinen, die treiberdefinierte Einträge aus einer verknüpften Liste einfügen und entfernen.

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);
}

Das System bietet auch atome Versionen der Listenvorgänge, ExInterlockedPopEntryList und ExInterlockedPushEntryList. Jedes erfordert einen zusätzlichen Spin-Lock-Parameter. Die Routine erhält die Drehsperre, bevor sie die Liste aktualisiert, und dann gibt die Routine die Drehsperre nach Abschluss des Vorgangs frei. Während die Sperre aktiv ist, sind Unterbrechungen deaktiviert. Jeder Vorgang in der Liste muss dieselbe Drehsperre verwenden, um sicherzustellen, dass jeder solche Vorgang in der Liste mit jedem anderen Vorgang synchronisiert wird. Sie müssen den Spinlock nur mit diesen ExInterlockedXxxList-Routinen verwenden. Verwenden Sie die Drehsperre nicht für andere Zwecke. Treiber können dieselbe Sperre für mehrere Listen verwenden, jedoch erhöht dieses Verhalten den Lock-Wettbewerb, daher sollten Treiber dies vermeiden.

Beispielsweise können die ExInterlockedPopEntryList und ExInterlockedPushEntryList-Routinen die Freigabe einer einfach verketteten Liste durch einen Treiberthread unterstützen, der bei IRQL = PASSIVE_LEVEL ausgeführt wird, und eine ISR, die bei DIRQL ausgeführt wird. Diese Routinen deaktivieren Unterbrechungen, wenn die Drehsperre gehalten wird. Daher kann der ISR- und Treiberthread die gleiche Drehsperre in ihren Aufrufen dieser ExInterlockedXxxList-Routinen sicher verwenden, ohne ein Deadlock zu riskieren.

Mischen Sie keine Aufrufe an die atomischen und nichtatomischen Versionen der Listenvorgänge in derselben Liste. Wenn die atomaren und nichtatomaren Versionen gleichzeitig in derselben Liste ausgeführt werden, kann die Datenstruktur ggf. beschädigt werden, und der Computer könnte nicht mehr antworten oder einen Fehlerüberprüfungsprozess durchführt (d. h. Absturz). (Sie können den Spinlock nicht erwerben, während Sie die nichtatomare Routine aufrufen, denn das Mischen von Aufrufen atomarer und nichtatomarer Versionen von Listenvorgängen ist nicht als Alternativmethode unterstützt. Die Verwendung des Spinlocks auf diese Weise wird nicht unterstützt und kann weiterhin zu Listenbeschädigungen führen.)

Das System bietet auch eine alternative Implementierung von atomar einfach verketteten Listen, die effizienter ist. Weitere Informationen finden Sie unter Sequenzierte verknüpfte Listen.

Doppelt verkettete Listen

Das Betriebssystem bietet integrierte Unterstützung für doppelt verkettete Listen, die LIST_ENTRY-Strukturen verwenden. Eine doppelt verkettete Liste besteht aus einem Listenkopf und mehreren Listeneinträgen. (Die Anzahl der Listeneinträge ist null, wenn die Liste leer ist.) Jeder Listeneintrag wird als LIST_ENTRY Struktur dargestellt. Der Listenkopf wird auch als LIST_ENTRY Struktur dargestellt.

Jede LIST_ENTRY Struktur enthält ein Flink-Element und ein Blink-Element . Beide Mitglieder sind Zeiger auf LIST_ENTRY-Strukturen.

In der LIST_ENTRY Struktur, die den Listenkopf darstellt, verweist das Flink-Element auf den ersten Eintrag in der Liste, und das Blink-Element verweist auf den letzten Eintrag in der Liste. Wenn die Liste leer ist, zeigen Flink und Blink des Listenkopfs auf den Listenkopf selbst.

In der LIST_ENTRY Struktur, die einen Eintrag in der Liste darstellt, zeigt das Flink-Element auf den nächsten Eintrag in der Liste, und das Blink-Element verweist auf den vorherigen Eintrag in der Liste. (Wenn der Eintrag der letzte in der Liste ist, verweist Flink auf den Listenkopf. Wenn der Eintrag der erste in der Liste ist, verweist Blink auf den Listenkopf.)

Obwohl diese Regeln auf den ersten Blick überraschend erscheinen, lassen sie die Einfüge- und Entfernungsvorgänge der Liste ohne bedingte Codeverzweigungen implementieren.

Die Routinen, die eine doppelt verkettete Liste bearbeiten, nehmen einen Zeiger auf eine LIST_ENTRY entgegen, die den Listenkopf darstellt. Diese Routinen aktualisieren die Flink - und Blink-Mitglieder im Listenkopf so, dass diese Mitglieder auf die ersten und letzten Einträge in der resultierenden Liste verweisen.

Angenommen, die ListHead-Variable ist ein Zeiger auf die LIST_ENTRY Struktur, die den Listenkopf darstellt. Ein Treiber bearbeitet ListHead wie folgt:

  • Um die Liste als leer zu initialisieren, verwenden Sie InitializeListHead, wodurch ListHead->Flink und ListHead->Blink initialisiert werden, um auf ListHead zu verweisen.

  • Um einen neuen Eintrag an der Kopfzeile der Liste einzufügen, weisen Sie eine LIST_ENTRY zu, um den neuen Eintrag darzustellen, und rufen Sie dann InsertHeadList auf, um den Eintrag am Anfang der Liste einzufügen.

  • Um einen neuen Eintrag am Ende der Liste anzufügen, weisen Sie eine LIST_ENTRY zu, um den neuen Eintrag darzustellen, und rufen Sie dann InsertTailList auf, um den Eintrag am Ende der Liste einzufügen.

  • Verwenden Sie RemoveHeadList, um den ersten Eintrag aus der Liste zu entfernen. Dadurch wird ein Zeiger auf den entfernten Eintrag aus der Liste oder auf ListHead zurückgegeben, wenn die Liste leer ist.

  • Verwenden Sie RemoveTailList, um den letzten Eintrag aus der Liste zu entfernen. Dadurch wird ein Zeiger auf den entfernten Eintrag aus der Liste oder auf ListHead zurückgegeben, wenn die Liste leer ist.

  • Verwenden Sie RemoveEntryList, um einen angegebenen Eintrag aus der Liste zu entfernen.

  • Um zu überprüfen, ob eine Liste leer ist, verwenden Sie IsListEmpty.

  • Verwenden Sie AppendTailList, um eine Liste am Ende einer anderen Liste anzufügen.

Ein LIST_ENTRY hat an sich nur die Mitglieder Blink und Flink. Um Ihre eigenen Daten in den Listen zu speichern, betten Sie die LIST_ENTRY als Mitglied der Struktur ein, die den Listeneintrag wie folgt beschreibt.

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

Um einer Liste einen neuen Eintrag hinzuzufügen, weisen Sie eine XXX_ENTRY Struktur zu, und übergeben Sie dann einen Zeiger an das ListEntry-Element an InsertHeadList oder InsertTailList. Wenn Sie einen Zeiger von einer LIST_ENTRY zurück in eine XXX_ENTRY konvertieren möchten, verwenden Sie CONTAINING_RECORD. Ein Beispiel für dieses Verfahren finden Sie unter Verwendung von singly verknüpften Listen oben unter "Verknüpfte Listen mit Singly Linked Lists".

Das System stellt außerdem atomische Versionen der Listenvorgänge, ExInterlockedInsertHeadList, ExInterlockedInsertTailList und ExInterlockedRemoveHeadList bereit. Es gibt keine Atomversion von RemoveTailList oder RemoveEntryList. Jede Routine verwendet einen zusätzlichen Spin-Lock-Parameter. Die Routine erwirbt den Spinlock vor dem Aktualisieren der Liste und gibt ihn nach Abschluss des Vorgangs wieder frei. Während die Sperre aktiv ist, sind Unterbrechungen deaktiviert. Jeder Vorgang in der Liste muss dieselbe Drehsperre verwenden, um sicherzustellen, dass jeder solche Vorgang in der Liste mit jedem anderen synchronisiert wird. Sie müssen den Spinlock nur mit diesen ExInterlockedXxxList-Routinen verwenden. Verwenden Sie die Drehsperre nicht für andere Zwecke. Treiber können dieselbe Sperre für mehrere Listen verwenden, jedoch erhöht dieses Verhalten den Lock-Wettbewerb, daher sollten Treiber dies vermeiden.

Beispielsweise können die Routinen "ExInterlockedInsertHeadList", "ExInterlockedInsertTailList" und "ExInterlockedRemoveHeadList" die Freigabe einer doppelt verknüpften Liste unterstützen durch einen Treiberthread, der bei IRQL = PASSIVE_LEVEL ausgeführt wird, und ein ISR, das bei DIRQL ausgeführt wird. Diese Routinen deaktivieren Unterbrechungen, wenn die Drehsperre gehalten wird. Daher kann der ISR- und Treiberthread die gleiche Drehsperre in ihren Aufrufen dieser ExInterlockedXxxList-Routinen sicher verwenden, ohne ein Deadlock zu riskieren.

Mischen Sie keine Aufrufe an die atomischen und nichtatomischen Versionen der Listenvorgänge in derselben Liste. Wenn die atomischen und nichtatomischen Versionen gleichzeitig in derselben Liste ausgeführt werden, kann die Datenstruktur beschädigt werden, und der Computer reagiert nicht mehr oder es kommt zu einem Fehlercheck (d. h. Absturz). (Sie können die Drehsperre nicht abrufen, während Sie die nichtatomische Routine aufrufen, um zu vermeiden, dass Aufrufe an atomische und nichtatomische Versionen der Listenvorgänge gemischt werden. Die Verwendung der Drehungssperre in dieser Weise wird nicht unterstützt und kann weiterhin zu Listenbeschädigung führen.)

Sequenzierte einfach verkettete Listen

Eine sequenzierte, einfach verkettete Liste ist eine Implementierung von einfach verketteten Listen, die atomare Operationen unterstützt. Es ist effizienter für Atomvorgänge als die Implementierung von singly linked lists beschrieben in Singly Linked Lists.

Eine SLIST_HEADER Struktur wird verwendet, um den Kopf einer sequenzierten verknüpften Liste zu beschreiben, während SLIST_ENTRY verwendet wird, um einen Eintrag in der Liste zu beschreiben.

Ein Treiber ändert die Liste wie folgt:

Ein SLIST_ENTRY selbst verfügt nur über ein Next-Element. Um Ihre eigenen Daten in den Listen zu speichern, betten Sie die SLIST_ENTRY als Mitglied der Struktur ein, die den Listeneintrag beschreibt, wie folgt.

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

} XXX_ENTRY;

Um der Liste einen neuen Eintrag hinzuzufügen, weisen Sie eine XXX_ENTRY Struktur zu, und übergeben Sie dann einen Zeiger auf das SListEntry-Element an ExInterlockedPushEntrySList.

Verwenden Sie CONTAINING_RECORD, um einen Zeiger vom SLIST_ENTRY zurück zu einer XXX_ENTRY zu konvertieren. Ein Beispiel für diese Technik finden Sie unter Verwendung von nicht sequenzierten einfach verketteten Listen unter Singly Linked Lists.

Warnung Bei 64-Bit-Microsoft Windows-Betriebssystemen müssen SLIST_ENTRY Strukturen 16-Byte ausgerichtet sein.