Delen via

Enkelvoudig en dubbel gekoppelde lijsten

Enkelvoudig gekoppelde lijsten

Het besturingssysteem biedt ingebouwde ondersteuning voor eenvoudig gekoppelde lijsten die gebruikmaken van SINGLE_LIST_ENTRY structuren. Een singly linked list bestaat uit een lijstkop plus een aantal lijstitems. (Het aantal lijstitems is nul als de lijst leeg is.) Elke lijstvermelding wordt weergegeven als een SINGLE_LIST_ENTRY structuur. De lijstkop wordt ook weergegeven als een SINGLE_LIST_ENTRY structuur.

Elke SINGLE_LIST_ENTRY structuur bevat een volgend lid dat verwijst naar een andere SINGLE_LIST_ENTRY structuur. In de SINGLE_LIST_ENTRY structuur die het lijsthoofd vertegenwoordigt, verwijst het volgende lid naar het eerste item in de lijst of is NULL als de lijst leeg is. In de SINGLE_LIST_ENTRY structuur die een vermelding in de lijst vertegenwoordigt, verwijst het volgende lid naar het volgende item van de lijst of is NULL als dit item de laatste in de lijst is.

De routines die een enkelvoudig gekoppelde lijst manipuleren, nemen een pointer naar een SINGLE_LIST_ENTRY die de lijstkop vertegenwoordigt. Ze werken de volgende aanwijzer bij, zodat deze verwijst naar het eerste item van de lijst na de bewerking.

Stel dat de variabele ListHead een aanwijzer is naar de SINGLE_LIST_ENTRY structuur die de lijstkop vertegenwoordigt. Een stuurprogramma bewerkt ListHead als volgt:

  • Als u de lijst als leeg wilt initialiseren, stelt u ListHead-Next> in op NULL.

  • Als u een nieuw item aan de lijst wilt toevoegen, wijst u een SINGLE_LIST_ENTRY toe om de nieuwe vermelding aan te geven en roept u Vervolgens PushEntryList aan om de vermelding toe te voegen aan het begin van de lijst.

  • Haal de eerste vermelding uit de lijst met PopEntryList.

Een SINGLE_LIST_ENTRY heeft op zichzelf alleen een Next member. Als u uw eigen gegevens in de lijsten wilt opslaan, sluit u de SINGLE_LIST_ENTRY in als lid van de structuur waarin de lijstvermelding als volgt wordt beschreven.

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

Als u een nieuw item aan de lijst wilt toevoegen, wijst u een XXX_ENTRY structuur toe en geeft u een aanwijzer door aan het lid SingleListEntry aan PushEntryList. Als u een aanwijzer wilt converteren naar de SINGLE_LIST_ENTRY terug naar een XXX_ENTRY, gebruikt u CONTAINING_RECORD. Hier volgt een voorbeeld van routines waarmee door het stuurprogramma gedefinieerde vermeldingen worden ingevoegd en verwijderd uit een singly-gekoppelde lijst.

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

Het systeem biedt ook atomische versies van de lijstbewerkingen, ExInterlockedPopEntryList en ExInterlockedPushEntryList. Elk heeft een extra spin lock parameter. De routine verwerft de spinvergrendeling voordat de lijst wordt bijgewerkt, waarna de routine de spinvergrendeling vrijgeeft nadat de bewerking is voltooid. Terwijl de vergrendeling is vastgehouden, worden interrupts uitgeschakeld. Elke bewerking in de lijst moet dezelfde kringvergrendeling gebruiken om ervoor te zorgen dat elke bewerking in de lijst wordt gesynchroniseerd met elke andere bewerking. U moet de spin lock alleen gebruiken met deze ExInterlockedXxxList routines. Gebruik de spinvergrendeling niet voor een ander doel. Stuurprogramma's kunnen dezelfde vergrendeling voor meerdere lijsten gebruiken, maar dit gedrag verhoogt conflicten over de vergrendeling, zodat stuurprogramma's dit moeten vermijden.

De Routines ExInterlockedPopEntryList en ExInterlockedPushEntryList kunnen bijvoorbeeld het delen van een enkelvoudig verbonden lijst ondersteunen door een stuurprogrammathread die wordt uitgevoerd op IRQL = PASSIVE_LEVEL en een ISR die wordt uitgevoerd op DIRQL. Deze routines schakelen interrupts uit wanneer de spinlock wordt vastgehouden. De ISR- en driverthread kunnen dus veilig dezelfde spinvergrendeling gebruiken in hun aanroepen naar deze ExInterlockedXxxList-routines zonder een impasse te riskeren.

Meng geen aanroepen naar de atomische en niet-atomische versies van de lijstbewerkingen in dezelfde lijst. Als de atomische en niet-atomische versies gelijktijdig worden uitgevoerd op dezelfde lijst, kan de gegevensstructuur beschadigd raken en kan de computer stoppen met reageren of een systeemcrash krijgen (dat wil zeggen, crashen). (U kunt de spinvergrendeling niet verkrijgen tijdens het aanroepen van de niet-totomische routine als alternatief voor het mengen van aanroepen naar atomische en niet-atomische versies van lijstbewerkingen. Het gebruik van de spinvergrendeling op deze manier wordt niet ondersteund en kan nog steeds leiden tot beschadiging van de lijst.)

Het systeem biedt ook een alternatieve implementatie van atomische gekoppelde lijsten die efficiënter zijn. Zie Gesequentieerde enkelvoudig gekoppelde lijsten voor meer informatie.

Dubbel gekoppelde lijsten

Het besturingssysteem biedt ingebouwde ondersteuning voor dubbel gekoppelde lijsten die gebruikmaken van LIST_ENTRY structuren. Een dubbel gekoppelde lijst bestaat uit een lijstkop plus een aantal lijstitems. (Het aantal lijstitems is nul als de lijst leeg is.) Elke lijstvermelding wordt weergegeven als een LIST_ENTRY structuur. De lijstkop wordt ook weergegeven als een LIST_ENTRY structuur.

Elke LIST_ENTRY structuur bevat een Flink-lid en een Blink-lid . Beide leden verwijzen naar LIST_ENTRY structuren.

In de LIST_ENTRY structuur die het lijsthoofd vertegenwoordigt, wijst het Flink-lid naar het eerste item in de lijst en wijst het Blink-lid naar het laatste item in de lijst. Als de lijst leeg is, wijzen Flink en Blink van de lijstkop naar het lijsthoofd zelf.

In de LIST_ENTRY structuur die een vermelding in de lijst vertegenwoordigt, wijst het Flink-lid naar het volgende item in de lijst en wijst het Blink-lid naar het vorige item in de lijst. (Als het item de laatste in de lijst is, wijst Flink naar het lijsthoofd. Als de vermelding ook de eerste in de lijst is, verwijst Blink naar de lijstkop.)

Hoewel deze regels op het eerste gezicht misschien verrassend lijken, kunnen de invoeg- en verwijderingsbewerkingen van de lijst worden geïmplementeerd zonder voorwaardelijke codevertakkingen.

De routines die een dubbel gekoppelde lijst manipuleren, nemen een aanwijzer naar een LIST_ENTRY die de lijstkop vertegenwoordigt. Deze routines werken de Flink - en Blink-leden in de lijstkop bij, zodat deze leden verwijzen naar de eerste en laatste vermeldingen in de resulterende lijst.

Stel dat de variabele ListHead een aanwijzer is naar de LIST_ENTRY structuur die de lijstkop vertegenwoordigt. Een stuurprogramma bewerkt ListHead als volgt:

  • Als u de lijst als leeg wilt initialiseren, gebruikt u InitializeListHead, waarmee ListHead-Flink> en ListHead-Blink> worden geïnitialiseerd om naar ListHead te verwijzen.

  • Als u een nieuw item aan het hoofd van de lijst wilt invoegen, wijst u een LIST_ENTRY toe om het nieuwe item aan te geven en roept u InsertHeadList aan om de vermelding aan het begin van de lijst in te voegen.

  • Als u een nieuw item aan de staart van de lijst wilt toevoegen, wijst u een LIST_ENTRY toe om de nieuwe vermelding aan te geven en roept u InsertTailList aan om de vermelding aan het einde van de lijst in te voegen.

  • Als u de eerste vermelding uit de lijst wilt verwijderen, gebruikt u RemoveHeadList. Hiermee wordt een aanwijzer geretourneerd naar de verwijderde vermelding uit de lijst of naar ListHead als de lijst leeg is.

  • Als u het laatste item uit de lijst wilt verwijderen, gebruikt u RemoveTailList. Hiermee wordt een aanwijzer geretourneerd naar de verwijderde vermelding uit de lijst of naar ListHead als de lijst leeg is.

  • Als u een opgegeven vermelding uit de lijst wilt verwijderen, gebruikt u RemoveEntryList.

  • Als u wilt controleren of een lijst leeg is, gebruikt u IsListEmpty.

  • Als u een lijst wilt toevoegen aan de staart van een andere lijst, gebruikt u AppendTailList.

Een LIST_ENTRY heeft alleen Blink en Flink leden. Als u uw eigen gegevens in de lijsten wilt opslaan, sluit u de LIST_ENTRY in als lid van de structuur waarin de lijstvermelding als volgt wordt beschreven.

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

Als u een nieuw item aan een lijst wilt toevoegen, wijst u een XXX_ENTRY structuur toe en geeft u een aanwijzer door aan het lid ListEntry aan InsertHeadList of InsertTailList. Als u een aanwijzer wilt converteren naar een LIST_ENTRY terug naar een XXX_ENTRY, gebruikt u CONTAINING_RECORD. Voor een voorbeeld van deze techniek met behulp van enkelvoudig gekoppelde lijsten, zie bovenstaande.

Het systeem biedt ook atomische versies van de lijstbewerkingen, ExInterlockedInsertHeadList, ExInterlockedInsertTailList en ExInterlockedRemoveHeadList. Er is geen atomische versie van RemoveTailList of RemoveEntryList. Elke routine heeft een extra kringvergrendelingsparameter. De routine verkrijgt de spinvergrendeling voordat de lijst wordt bijgewerkt en geeft vervolgens de spinvergrendeling los nadat de bewerking is voltooid. Terwijl de vergrendeling is vastgehouden, worden interrupts uitgeschakeld. Elke bewerking in de lijst moet dezelfde kringvergrendeling gebruiken om ervoor te zorgen dat elke bewerking in de lijst met elkaar wordt gesynchroniseerd. U moet de spin lock alleen gebruiken met deze ExInterlockedXxxList routines. Gebruik de spinvergrendeling niet voor een ander doel. Stuurprogramma's kunnen dezelfde vergrendeling voor meerdere lijsten gebruiken, maar dit gedrag verhoogt conflicten over de vergrendeling, zodat stuurprogramma's dit moeten vermijden.

De routines ExInterlockedInsertHeadList, ExInterlockedInsertTailList en ExInterlockedRemoveHeadList kunnen bijvoorbeeld het delen van een dubbel gekoppelde lijst ondersteunen door een stuurprogrammathread die wordt uitgevoerd op IRQL = PASSIVE_LEVEL en een ISR die wordt uitgevoerd op DIRQL. Deze routines schakelen interrupts uit wanneer de spinlock wordt vastgehouden. De ISR- en driverthread kunnen dus veilig dezelfde spinvergrendeling gebruiken in hun aanroepen naar deze ExInterlockedXxxList-routines zonder een impasse te riskeren.

Meng geen aanroepen naar de atomische en niet-atomische versies van de lijstbewerkingen in dezelfde lijst. Als de atomische en niet-atomische versies gelijktijdig worden uitgevoerd op dezelfde lijst, kan de gegevensstructuur beschadigd raken en kan de computer stoppen met reageren of een foutcontrole uitvoeren (dat wil zeggen crashen). (U kunt de spinvergrendeling niet verkrijgen tijdens het aanroepen van de niet-totomische routine om te voorkomen dat aanroepen naar atomische en niet-atomische versies van de lijstbewerkingen worden gemengd. Het gebruik van de spinvergrendeling op deze manier wordt niet ondersteund en kan nog steeds leiden tot beschadiging van de lijst.)

Enkelvoudig gekoppelde gesequentieerde lijsten

Een gesequentieerde enkelvoudig gekoppelde lijst is een implementatie van enkelvoudig gekoppelde lijsten die atomische bewerkingen ondersteunen. Het is efficiënter voor atomische bewerkingen dan de implementatie van enkelvoudig gekoppelde lijsten die worden beschreven in Singly Linked Lists.

Een SLIST_HEADER structuur wordt gebruikt om het hoofd van een gesequentieerde gekoppelde lijst te beschrijven, terwijl SLIST_ENTRY wordt gebruikt om een vermelding in de lijst te beschrijven.

Een stuurprogramma bewerkt de lijst als volgt:

Op zichzelf heeft een SLIST_ENTRY slechts een Next-lid. Als u uw eigen gegevens in de lijsten wilt opslaan, sluit u de SLIST_ENTRY in als lid van de structuur waarin de lijstvermelding als volgt wordt beschreven.

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

} XXX_ENTRY;

Als u een nieuw item aan de lijst wilt toevoegen, wijst u een XXX_ENTRY structuur toe en geeft u vervolgens een aanwijzer door aan het lid SListEntry aan ExInterlockedPushEntrySList.

Als u een aanwijzer wilt converteren naar de SLIST_ENTRY terug naar een XXX_ENTRY, gebruikt u CONTAINING_RECORD. Zie Singly Linked Lists voor een voorbeeld van deze techniek, met behulp van niet-opeenvolgende gekoppelde lijsten.

Waarschuwing Voor 64-bits Microsoft Windows-besturingssystemen moeten SLIST_ENTRY structuren 16 byte zijn uitgelijnd.

  • Last updated on