Sdílet prostřednictvím

Jednoduché a dvojnásobné spojené seznamy

Jednosměrně propojené seznamy

Operační systém poskytuje integrovanou podporu pro jednoduše propojené seznamy, které používají struktury SINGLE_LIST_ENTRY. Jednosměrně propojený seznam se skládá z hlavy seznamu a určitého počtu položek seznamu. (Počet položek seznamu je nula, pokud je seznam prázdný.) Každá položka seznamu je reprezentována jako struktura SINGLE_LIST_ENTRY . Hlava seznamu je také reprezentována jako SINGLE_LIST_ENTRY struktura.

Každá SINGLE_LIST_ENTRY struktura obsahuje další člen , který odkazuje na jinou SINGLE_LIST_ENTRY strukturu. Ve struktuře SINGLE_LIST_ENTRY , která představuje záhlaví seznamu, další člen odkazuje na první položku v seznamu nebo má hodnotu NULL, pokud je seznam prázdný. Ve struktuře SINGLE_LIST_ENTRY , která představuje položku v seznamu, další člen odkazuje na další položku seznamu nebo má hodnotu NULL, pokud je tato položka poslední v seznamu.

Rutiny, které manipulují s jednosměrným propojeným seznamem, převezmou ukazatel na SINGLE_LIST_ENTRY, který představuje záhlaví seznamu. Aktualizují ukazatel Další tak, aby odkazovali na první položku seznamu po operaci.

Předpokládejme, že proměnná ListHead je ukazatel na strukturu SINGLE_LIST_ENTRY , která představuje záhlaví seznamu. Ovladač manipuluje s listHead následujícím způsobem:

  • Pokud chcete seznam inicializovat jako prázdný, nastavte ListHead-Next> na hodnotu NULL.

  • Chcete-li přidat novou položku do seznamu, přidělte SINGLE_LIST_ENTRY, aby představovala novou položku, a potom zavolejte funkci PushEntryList, abyste položku přidali na začátek seznamu.

  • Vyskočte první položku ze seznamu pomocí PopEntryList.

SINGLE_LIST_ENTRY má sám o sobě pouze Next člena. Pokud chcete do seznamů uložit vlastní data, vložte SINGLE_LIST_ENTRY jako člen struktury, která popisuje položku seznamu, následujícím způsobem.

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

Pokud chcete do seznamu přidat novou položku, přidělte strukturu XXX_ENTRY a pak předejte ukazatel na člena SingleListEntryPushEntryList. Pokud chcete převést ukazatel na SINGLE_LIST_ENTRY zpět na XXX_ENTRY, použijte CONTAINING_RECORD. Zde je příklad rutin, které vkládají a odebírají položky definované ovladačem z jednoduše propojeného seznamu.

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

Systém také poskytuje atomické verze operací seznamu, ExInterlockedPopEntryList a ExInterlockedPushEntryList. Každý z nich má další parametr spinlock. Rutina získá spinlock před aktualizací seznamu a uvolní ho po dokončení operace. Při držení zámku jsou přerušení zakázána. Každá operace v seznamu musí používat stejný spinlock, aby byla každá taková operace v seznamu synchronizovaná s každou jinou operací. Zámek otáčení je nutné použít pouze s těmito rutinami ExInterlockedXxxList . Spinlock nepoužívejte k žádnému jinému účelu. Ovladače můžou použít stejný zámek pro více seznamů, ale toto chování zvyšuje soutěžení o zámky, takže by se mu měli ovladače vyhnout.

Například rutiny ExInterlockedPopEntryList a ExInterlockedPushEntryList mohou podporovat sdílení singly propojeného seznamu pomocí vlákna ovladače spuštěného v IRQL = PASSIVE_LEVEL a ISR běžícího v DIRQL. Tyto rutiny vypnou přerušení, když je držen spinlock. Proto mohou vlákno ISR a vlákno ovladače bezpečně použít stejný spinový zámek při volání těchto rutin ExInterlockedXxxList bez rizika stavu zablokování.

Nekombinujte volání atomických a neatomických verzí operací seznamu ve stejném seznamu. Pokud se atomické a neatomické verze spouští současně ve stejném seznamu, může dojít k poškození datové struktury a počítač může přestat reagovat nebo kontrolovat chyby (to znamená chybové ukončení). (Spinlock nelze získat při volání neatomární rutiny jako alternativu ke kombinování volání atomárních a neatomárních verzí operací seznamu. Použití spinlocku tímto způsobem není podporováno a může způsobit poškození seznamu.)

Systém také poskytuje alternativní implementaci atomových jednokřídlých seznamů, který je efektivnější. Další informace najdete v tématu Uspořádané seznamy s jednosměrně propojenými seznamy.

Obousměrně propojené seznamy

Operační systém poskytuje integrovanou podporu pro dvojitě propojené seznamy, které používají struktury LIST_ENTRY. Doubly propojený seznam se skládá z hlavy seznamu a určitého počtu položek seznamu. (Počet položek seznamu je nula, pokud je seznam prázdný.) Každá položka seznamu je reprezentována jako struktura LIST_ENTRY . Hlava seznamu je také reprezentována jako LIST_ENTRY struktura.

Každá LIST_ENTRY struktura obsahuje člen Flink a Blink člen. Oba členy jsou ukazatele na struktury LIST_ENTRY.

V LIST_ENTRY struktuře , která představuje záhlaví seznamu, Flink člen odkazuje na první položku v seznamu a Blink člen odkazuje na poslední položku v seznamu. Pokud je seznam prázdný, Flink a Blink hlavičky seznamu ukazují na samotnou hlavičku seznamu.

V LIST_ENTRY struktuře , která představuje položku v seznamu, Flink člen odkazuje na další položku v seznamu a Blink člen odkazuje na předchozí položku v seznamu. (Pokud je položka poslední položkou v seznamu, Flink odkazuje na záhlaví seznamu. Podobně platí, že pokud je položka první položkou v seznamu, bliká na záhlaví seznamu.)

I když se tato pravidla na první pohled můžou zdát překvapivá, umožňují implementaci operací vložení a odebrání seznamu bez větví podmíněného kódu.

Rutiny, které manipulují s propojeným seznamem, převezmou ukazatel na LIST_ENTRY , který představuje záhlaví seznamu. Tyto rutiny aktualizují členy Flink a Blink v záhlaví seznamu tak, aby tyto členy ukazovaly na první a poslední položky ve výsledném seznamu.

Předpokládejme, že proměnná ListHead je ukazatel na strukturu LIST_ENTRY , která představuje záhlaví seznamu. Ovladač manipuluje s listHead následujícím způsobem:

  • Pokud chcete seznam inicializovat jako prázdný, použijte InitializeListHead, která inicializuje ListHead->Flink a ListHead->Blink, aby ukazovaly na ListHead.

  • Pokud chcete vložit novou položku do hlavy seznamu, přidělte LIST_ENTRY , která bude představovat novou položku, a potom zavoláte InsertHeadList pro vložení položky na začátek seznamu.

  • Chcete-li připojit novou položku na konec seznamu, alokujte LIST_ENTRY představující novou položku a poté zavolejte funkci InsertTailList, která vloží položku na konec seznamu.

  • Pokud chcete odebrat první položku ze seznamu, použijte RemoveHeadList. Vrátí ukazatel na odebranou položku ze seznamu nebo na ListHead , pokud je seznam prázdný.

  • Pokud chcete odebrat poslední položku ze seznamu, použijte RemoveTailList. Vrátí ukazatel na odebranou položku ze seznamu nebo na ListHead , pokud je seznam prázdný.

  • Pokud chcete ze seznamu odebrat zadanou položku, použijte RemoveEntryList.

  • Pokud chcete zjistit, jestli je seznam prázdný, použijte IsListEmpty.

  • Pokud chcete přidat seznam na konec jiného seznamu, použijte AppendTailList.

LIST_ENTRY má pouze Blink a Flink členy. Pokud chcete do seznamů uložit vlastní data, vložte LIST_ENTRY jako člen struktury, která popisuje položku seznamu, následujícím způsobem.

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

Pokud chcete do seznamu přidat novou položku, přidělte strukturu XXX_ENTRY a pak předejte ukazatel na člena ListEntryInsertHeadList nebo InsertTailList. Pokud chcete převést ukazatel na LIST_ENTRY zpět na XXX_ENTRY, použijte CONTAINING_RECORD. Příklad této techniky, použití jednosměrně propojených seznamů, viz výše Jednosměrně Propojené Seznamy.

Systém také poskytuje atomické verze operací seznamu, ExInterlockedInsertHeadList, ExInterlockedInsertTailList a ExInterlockedRemoveHeadList. Neexistuje žádná atomická verze RemoveTailList ani RemoveEntryList. Každá rutina přebírá další parametr spinlock. Rutina získá spinlock před aktualizací seznamu a potom uvolní spinlock po dokončení. Při držení zámku jsou přerušení zakázána. Každá operace v seznamu musí používat stejný spinlock, aby byla každá taková operace v seznamu synchronizována s ostatními. Zámek otáčení je nutné použít pouze s těmito rutinami ExInterlockedXxxList . Spinlock nepoužívejte k žádnému jinému účelu. Ovladače můžou použít stejný zámek pro více seznamů, ale toto chování zvyšuje soutěžení o zámky, takže by se mu měli ovladače vyhnout.

Například rutiny ExInterlockedInsertHeadList, ExInterlockedInsertTailList a ExInterlockedRemoveHeadList můžou podporovat sdílení doubly propojeného seznamu pomocí vlákna ovladače spuštěného v IRQL = PASSIVE_LEVEL a ISR běžící na DIRQL. Tyto rutiny vypnou přerušení, když je držen spinlock. Proto mohou vlákno ISR a vlákno ovladače bezpečně použít stejný spinový zámek při volání těchto rutin ExInterlockedXxxList bez rizika stavu zablokování.

Nekombinujte volání atomických a neatomických verzí operací seznamu ve stejném seznamu. Pokud se atomické a neatomické verze spouštějí současně ve stejném seznamu, může dojít k poškození datové struktury a počítač může přestat reagovat nebo se zhroutit (tj. havárie). (Zámek spin nelze získat při volání neatomové rutiny, abyste se vyhnuli kombinování volání atomových a neatomových verzí operací seznamu. Použití spin zámku tímto způsobem není podporováno a může způsobit poškození seznamu.)

Sekvencované seznamy s jednosměrně propojenými seznamy

Sekvencovaný singly propojený seznam je implementace singly propojených seznamů, která podporuje atomické operace. Je efektivnější pro atomické operace než implementace jednoduše propojených seznamů popsaných v Jednoduše propojené seznamy.

Struktura SLIST_HEADER slouží k popisu hlavy sekvenčně propojeného seznamu, zatímco SLIST_ENTRY slouží k popisu položky v seznamu.

Ovladač pracuje se seznamem následujícím způsobem:

SLIST_ENTRY má sám o sobě pouze člena Next. Pokud chcete do seznamů uložit vlastní data, vložte SLIST_ENTRY jako člen struktury, která popisuje položku seznamu, následujícím způsobem.

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

} XXX_ENTRY;

Pokud chcete do seznamu přidat novou položku, přidělte XXX_ENTRY strukturu a pak předejte ukazatel na SListEntry členu ExInterlockedPushEntrySList.

Pokud chcete převést ukazatel na SLIST_ENTRY zpět na XXX_ENTRY, použijte CONTAINING_RECORD. Příklad této techniky, využití nesekvenčních jednosměrně propojených seznamů, viz Jednosměrné propojené seznamy.

Varování V 64bitových operačních systémech Microsoft Windows musí být struktury SLIST_ENTRY zarovnané na 16 bajtů.

  • Last updated on