Singly und Doubly Verknüpfte Listen

  • Artikel

Singly Verknüpfte Listen

Das Betriebssystem bietet integrierte Unterstützung für singly linked listen, die SINGLE_LIST_ENTRY-Strukturen verwenden. Eine eng verknüpfte Liste besteht aus einem Listenkopf und einer Reihe von 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 Next-Element , das auf eine andere SINGLE_LIST_ENTRY-Struktur verweist. In der SINGLE_LIST_ENTRY Struktur, die den Listenkopf darstellt, zeigt das Element Weiter 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, verweist das Element Weiter auf den nächsten Eintrag der Liste oder ist NULL, wenn dieser Eintrag der letzte in der Liste ist.

Die Routinen, die eine eng verknüpfte Liste bearbeiten, verwenden einen Zeiger auf eine SINGLE_LIST_ENTRY , die den Listenkopf darstellt. Sie aktualisieren den Nächsten Zeiger, sodass 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, ordnen Sie einen SINGLE_LIST_ENTRY zu, der den neuen Eintrag darstellt, und rufen Sie dann PushEntryList auf, um den Eintrag am Anfang der Liste hinzuzufügen.

  • Popen Sie den ersten Eintrag mithilfe von PopEntryList aus der Liste.

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

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

Um der Liste einen neuen Eintrag hinzuzufügen, ordnen Sie eine XXX_ENTRY-Struktur zu, und übergeben Sie dann einen Zeiger an das SingleListEntry-Element an PushEntryList. Verwenden Sie CONTAINING_RECORD, um einen Zeiger auf die SINGLE_LIST_ENTRY zurück in eine XXX_ENTRY zu konvertieren. Hier sehen Sie ein Beispiel für Routinen, die treiberdefinierte Einträge aus einer singly verknüpften Liste einfügen und daraus 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 atomische Versionen der Listenvorgänge, ExInterlockedPopEntryList und ExInterlockedPushEntryList. Jeder nimmt einen zusätzlichen Spin-Lock-Parameter an. Die Routine ruft die Spinsperre ab, bevor sie die Liste aktualisiert, und die Routine gibt die Spinsperre nach Abschluss des Vorgangs frei. Während die Sperre beibehalten wird, werden Unterbrechungen deaktiviert. Jeder Vorgang in der Liste muss dieselbe Drehsperre verwenden, um sicherzustellen, dass jeder dieser Vorgänge in der Liste mit jedem anderen Vorgang synchronisiert wird. Sie müssen die Drehsperre 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, aber dieses Verhalten erhöht die Sperrkonflikte, sodass Treiber dies vermeiden sollten.

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

Mischen Sie Aufrufe der atomaren und nicht-atomaren Versionen der Listenvorgänge in derselben Liste nicht. Wenn die atomische und die nicht-atomare Version gleichzeitig in derselben Liste ausgeführt werden, wird die Datenstruktur möglicherweise beschädigt, und der Computer reagiert möglicherweise nicht mehr, oder die Fehlerprüfung (d. o. Absturz). (Sie können die Spinsperre nicht abrufen, während Sie die nicht-atomare Routine als Alternative zum Mischen von Aufrufen von atomaren und nicht-atomaren Versionen von Listenvorgängen aufrufen. Die Verwendung der Spin-Sperre auf diese Weise wird nicht unterstützt und kann weiterhin zu Listenbeschädigungen führen.)

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

Doppelt verknüpfte Listen

Das Betriebssystem bietet integrierte Unterstützung für doppelt verknüpfte Listen, die LIST_ENTRY Strukturen verwenden. Eine doppelt verknüpfte Liste besteht aus einem Listenkopf und einer Reihe von 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 Member sind Zeiger auf LIST_ENTRY Strukturen.

In der LIST_ENTRY Struktur, die den Listenkopf darstellt, zeigt das Flink-Element auf den ersten Eintrag in der Liste und das Blink-Element 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, zeigt Flink auf den Listenkopf. Wenn es sich bei dem Eintrag um den ersten Eintrag in der Liste handelt, zeigt Blink auf den Listenkopf.)

(Diese Regeln mögen zwar auf den ersten Blick überraschend erscheinen, ermöglichen aber die Implementierung von Listeneinfügungs- und -entfernungsvorgängen ohne bedingte Code-Verzweigungen.)

Die Routinen, die eine doppelt verknüpfte Liste bearbeiten, verwenden einen Zeiger auf eine LIST_ENTRY , die den Listenkopf darstellt. Diese Routinen aktualisieren die Flink - und Blink-Member im Listenkopf, sodass diese Member auf den ersten und letzten Eintrag 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 zeigen.

  • Um einen neuen Eintrag am Anfang der Liste einzufügen, ordnen Sie einen LIST_ENTRY zu, der den neuen Eintrag darstellt, und rufen Sie dann InsertHeadList auf, um den Eintrag am Anfang der Liste einzufügen.

  • Um einen neuen Eintrag an das Ende der Liste anzufügen, ordnen Sie einen LIST_ENTRY zu, der den neuen Eintrag darstellt, 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 an das Ende einer anderen Liste anzufügen.

Ein LIST_ENTRY selbst verfügt nur über Blink - und Flink-Member . Um Ihre eigenen Daten in den Listen zu speichern, betten Sie den LIST_ENTRY wie folgt als Member der Struktur ein, die den Listeneintrag beschreibt.

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

Um einer Liste einen neuen Eintrag hinzuzufügen, ordnen Sie eine XXX_ENTRY-Struktur zu, und übergeben Sie dann einen Zeiger an das ListEntry-Element an InsertHeadList oder InsertTailList. Verwenden Sie CONTAINING_RECORD, um einen Zeiger in eine LIST_ENTRY zurück in eine XXX_ENTRY zu konvertieren. Ein Beispiel für dieses Verfahren finden Sie unter Singly Linked Lists weiter oben.

Das System bietet auch atomische Versionen der Listenvorgänge, ExInterlockedInsertHeadList, ExInterlockedInsertTailList und ExInterlockedRemoveHeadList. (Beachten Sie, dass es keine atomice Version von RemoveTailList oder RemoveEntryList gibt.) Jede Routine benötigt einen zusätzlichen Spin lock-Parameter. Die Routine ruft die Spinsperre ab, bevor die Liste aktualisiert wird, und gibt dann die Spinsperre frei, nachdem der Vorgang abgeschlossen ist. Während die Sperre beibehalten wird, werden Unterbrechungen deaktiviert. Jeder Vorgang in der Liste muss dieselbe Spin-Sperre verwenden, um sicherzustellen, dass jeder dieser Vorgänge in der Liste mit jedem anderen synchronisiert wird. Sie müssen die Drehsperre 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, aber dieses Verhalten erhöht die Sperrkonflikte, sodass Treiber dies vermeiden sollten.

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

Mischen Sie Aufrufe der atomaren und nicht-atomaren Versionen der Listenvorgänge in derselben Liste nicht. Wenn die atomische und die nicht-atomare Version gleichzeitig in derselben Liste ausgeführt werden, kann die Datenstruktur beschädigt werden, und der Computer reagiert möglicherweise nicht mehr, oder die Fehlerprüfung (d. s. Absturz). (Sie können nicht daran arbeiten, die Spinsperre beim Aufrufen der nicht-atomaren Routine abzurufen, um Aufrufe von atomaren und nicht-atomaren Versionen der Listenvorgänge zu vermeiden. Die Verwendung der Spin-Sperre auf diese Weise wird nicht unterstützt und kann weiterhin zu Listenbeschädigungen führen.)

Sequenzierte verknüpfte Listen

Eine sequenzierte, singly verknüpfte Liste ist eine Implementierung von singly verknüpften Listen, die atomare Vorgänge unterstützt. Es ist effizienter für atomische Vorgänge als die Implementierung von singly verknüpften Listen, die in Singly Linked Lists beschrieben werden.

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

Ein Treiber bearbeitet 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 wie folgt als Mitglied der Struktur ein, die den Listeneintrag beschreibt.

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 an das SListEntry-Element an ExInterlockedPushEntrySList. Verwenden Sie CONTAINING_RECORD, um einen Zeiger auf die SLIST_ENTRY zurück in eine XXX_ENTRY zu konvertieren. Ein Beispiel für dieses Verfahren unter Verwendung von nicht sequenzierten, singly verknüpften Listen finden Sie unter Singly Linked Lists.

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

Windows XP und höhere Versionen von Windows bieten optimierte Versionen der sequenzierten singly verknüpften Listenfunktionen, die in Windows 2000 nicht verfügbar sind. Wenn Ihr Treiber diese Funktionen verwendet und auch mit Windows 2000 ausgeführt werden muss, muss der Treiber das _WIN2K_COMPAT_SLIST_USAGE-Flag wie folgt definieren:

#define _WIN2K_COMPAT_SLIST_USAGE

Bei x86-basierten Prozessoren bewirkt dieses Flag, dass der Compiler Versionen der sequenzierten singly verknüpften Listenfunktionen verwendet, die mit Windows 2000 kompatibel sind.