Delen via

Gekoppelde lijsten met vergrendelingen

  • Artikel

Een gekoppelde lijst met knooppunten (SList) vereenvoudigt de taak van invoegen en verwijderen uit een gekoppelde lijst. SLists worden geïmplementeerd met behulp van een niet-blokkerend algoritme om atomische synchronisatie te bieden, de systeemprestaties te verbeteren en problemen zoals prioriteitinversion en vergrendelingsconvoy's te voorkomen.

SLists zijn eenvoudig te implementeren en te gebruiken in 32-bits code. Het is echter lastig om ze te implementeren in 64-bits code, omdat de hoeveelheid gegevens die kan worden uitgewisseld door de systeemeigen interlocked exchange primitieven niet de dubbele adresgrootte is, omdat deze zich in de 32-bits code bevindt. Daarom maken SLists het mogelijk om schaalbare high-end algoritmen naar Windows te overzetten.

Windows 8: Vanaf Windows 8 zijn de juiste systeemeigen uitwisselingsprimitieven beschikbaar voor 64-bits code, bijvoorbeeld InterlockedCompare64Exchange128.

Toepassingen kunnen SLists gebruiken door de functie InitializeSListHead aan te roepen om het hoofd van de lijst te initialiseren. Als u items in de lijst wilt invoegen, gebruikt u de functie InterlockedPushEntrySList. Als u items uit de lijst wilt verwijderen, gebruikt u de functie InterlockedPopEntrySList.

Alle lijstitems moeten worden uitgelijnd op een MEMORY_ALLOCATION_ALIGNMENT grens. Niet-uitgelijnde items kunnen onvoorspelbare resultaten veroorzaken. Zie _aligned_malloc.

Zie voor een voorbeeld Singly Linked Lists gebruiken.

De volgende tabel bevat de SList-functies.

Functie Beschrijving
InitializeSListHead Initialiseert het hoofd van een zanglijst.
InterlockedFlushSList Hiermee wordt de hele lijst met items in een singly gekoppelde lijst leeggemaakt.
InterlockedPopEntrySList Hiermee verwijdert u een item aan de voorzijde van een ingly-gekoppelde lijst.
InterlockedPushEntrySList Hiermee voegt u een item aan de voorzijde van een ingly-gekoppelde lijst in.
InterlockedPushListSList Hiermee voegt u een singly-gekoppelde lijst toe aan de voorzijde van een andere ingly-gekoppelde lijst.
InterlockedPushListSListSListEx- Hiermee voegt u een singly-gekoppelde lijst toe aan de voorzijde van een andere ingly-gekoppelde lijst. Deze versie van de methode maakt geen gebruik van de __fastcall aanroepconventie.
RtlFirstEntrySList Hiermee haalt u het eerste item op in een singly gekoppelde lijst.
QueryDepthSList Hiermee haalt u het aantal vermeldingen op in de opgegeven singly gekoppelde lijst.