Freigeben über

Ineinander verschachtelte, singly verknüpfte Listen

  • Artikel

Eine verschachtelte Singly Verknüpfte Liste (SList) erleichtert das Einfügen und Löschen aus einer verknüpften Liste. SLists werden mithilfe eines Nichtblockierungsalgorithmus implementiert, um eine atomare Synchronisierung bereitzustellen, die Systemleistung zu erhöhen und Probleme wie Prioritätsinversion und Sperrkonvois zu vermeiden.

SLists sind einfach zu implementieren und in 32-Bit-Code zu verwenden. Es ist jedoch schwierig, sie in 64-Bit-Code zu implementieren, da die Menge an Daten, die von den nativen ineinandergreifenden Exchange-Primitiven ausgetauscht werden können, nicht doppelt so groß ist wie im 32-Bit-Code. Daher ermöglichen SLists die Portierung skalierbarer High-End-Algorithmen zu Windows.

Windows 8: Ab Windows 8 sind die entsprechenden nativen ineinandergreifenden Exchange-Grundtypen für 64-Bit-Code verfügbar, z. B. InterlockedCompare64Exchange128.

Anwendungen können SLists verwenden, indem sie die InitializeSListHead-Funktion aufrufen, um den Kopf der Liste zu initialisieren. Um Elemente in die Liste einzufügen, verwenden Sie die Funktion InterlockedPushEntrySList . Um Elemente aus der Liste zu löschen, verwenden Sie die Funktion InterlockedPopEntrySList .

Alle Listenelemente müssen an einer MEMORY_ALLOCATION_ALIGNMENT Grenze ausgerichtet werden. Nicht ausgerichtete Elemente können zu unvorhersehbaren Ergebnissen führen. Siehe _aligned_malloc.

Ein Beispiel finden Sie unter Verwenden von singly verknüpften Listen.

In der folgenden Tabelle sind die SList-Funktionen aufgeführt.

Funktion BESCHREIBUNG
InitializeSListHead Initialisiert den Kopf einer einfach verknüpften Liste.
InterlockedFlushSList Löscht die gesamte Liste der Elemente in einer einfach verknüpften Liste.
InterlockedPopEntrySList Entfernt ein Element von der Vorderseite einer einfach verknüpften Liste.
InterlockedPushEntrySList Fügt ein Element an der Vorderseite einer einfach verknüpften Liste ein.
InterlockedPushListSList Fügt eine singly-verknüpfte Liste an der Vorderseite einer anderen singly verknüpften Liste ein.
InterlockedPushListSListEx Fügt eine singly-verknüpfte Liste an der Vorderseite einer anderen singly verknüpften Liste ein. Diese Version der Methode verwendet nicht die __fastcall Aufrufkonvention.
RtlFirstEntrySList Ruft den ersten Eintrag in einer einfach verknüpften Liste ab.
QueryDepthSList Ruft die Anzahl der Einträge in der angegebenen singly verknüpften Liste ab.