Dela via

Sammanflätade singly länkade listor

  • Artikel

En sammanflätad länkad lista (SList) underlättar infogning och borttagning från en länkad lista. SLists implementeras med hjälp av en icke-blockeringsalgoritm för att tillhandahålla atomisk synkronisering, öka systemets prestanda och undvika problem som prioriterad inversion och låskonvojer.

SLists är enkla att implementera och använda i 32-bitars kod. Det är dock svårt att implementera dem i 64-bitars kod eftersom mängden data som kan utbytas av de interna sammankopplade exchange-primitiverna inte är dubbelt så stor som adressstorleken, som i 32-bitarskod. Därför möjliggör SLists portning av avancerade skalbara algoritmer till Windows.

Windows 8: Från och med Windows 8 är lämpliga interna sammankopplade exchange-primitiver tillgängliga för 64-bitarskod, till exempel InterlockedCompare64Exchange128.

Program kan använda SLists genom att anropa funktionen InitializeSListHead för att initiera listans huvud. Om du vill infoga objekt i listan använder du funktionen InterlockedPushEntrySList. Om du vill ta bort objekt från listan använder du funktionen InterlockedPopEntrySList.

Alla listobjekt måste vara justerade på en MEMORY_ALLOCATION_ALIGNMENT gräns. Ojusterade objekt kan orsaka oförutsägbara resultat. Se _aligned_malloc.

Ett exempel finns i Using Singly Linked Lists.

I följande tabell visas SList-funktionerna.

Funktion Beskrivning
InitializeSListHead Initierar huvudet för en singly länkad lista.
InterlockedFlushSList Rensar hela listan med objekt i en allsingly länkad lista.
InterlockedPopEntrySList Tar bort ett objekt från framsidan av en singly länkad lista.
InterlockedPushEntrySList Infogar ett objekt längst fram i en singly länkad lista.
InterlockedPushListSList Infogar en singly-länkad lista längst fram i en annan singly länkad lista.
InterlockedPushListSListEx Infogar en singly-länkad lista längst fram i en annan singly länkad lista. Den här versionen av metoden använder inte __fastcall-anropskonventionen.
RtlFirstEntrySList Hämtar den första posten i en singly länkad lista.
QueryDepthSList Hämtar antalet poster i den angivna singly länkade listan.