Elenchi collegati singly e doubly

Elenchi collegati singly

Il sistema operativo offre il supporto predefinito per elenchi collegati in modo autonomo che usano strutture SINGLE_LIST_ENTRY . Un elenco collegato in modo singly è costituito da un capo elenco più un numero di voci di elenco. Il numero di voci di elenco è zero se l'elenco è vuoto. Ogni voce di elenco è rappresentata come struttura SINGLE_LIST_ENTRY . Il capo elenco è rappresentato anche come struttura SINGLE_LIST_ENTRY .

Ogni struttura SINGLE_LIST_ENTRY contiene un membro Next che punta a un'altra struttura SINGLE_LIST_ENTRY . Nella struttura SINGLE_LIST_ENTRY che rappresenta la testa dell'elenco, il membro Successivo punta alla prima voce dell'elenco o è NULL se l'elenco è vuoto. Nella struttura SINGLE_LIST_ENTRY che rappresenta una voce nell'elenco, il membro Successivo punta alla voce successiva dell'elenco o è NULL se questa voce è l'ultima nell'elenco.

Le routine che modificano un elenco collegato singly accettano un puntatore a un SINGLE_LIST_ENTRY che rappresenta la testa dell'elenco. Aggiornano il puntatore Avanti in modo che punti alla prima voce dell'elenco dopo l'operazione.

Si supponga che la variabile ListHead sia un puntatore alla struttura SINGLE_LIST_ENTRY che rappresenta la testa elenco. Un driver modifica ListHead come indicato di seguito:

  • Per inizializzare l'elenco come vuoto, impostare ListHead-Next> su NULL.

  • Per aggiungere una nuova voce all'elenco, allocare un SINGLE_LIST_ENTRY per rappresentare la nuova voce e quindi chiamare PushEntryList per aggiungere la voce all'inizio dell'elenco.

  • Visualizzare la prima voce dall'elenco usando PopEntryList.

Un SINGLE_LIST_ENTRY, per sé, ha solo un membro Next . Per archiviare i propri dati negli elenchi, incorporare il SINGLE_LIST_ENTRY come membro della struttura che descrive la voce dell'elenco, come indicato di seguito.

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

Per aggiungere una nuova voce all'elenco, allocare una struttura XXX_ENTRY e quindi passare un puntatore al membro SingleListEntry a PushEntryList. Per convertire un puntatore alla SINGLE_LIST_ENTRY in un XXX_ENTRY, usare CONTAINING_RECORD. Ecco un esempio di routine che inseriscono e rimuoveno voci definite dal driver da un elenco collegato singly.

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

Il sistema fornisce anche versioni atomice delle operazioni di elenco, ExInterlockedPopEntryList e ExInterlockedPushEntryList. Ogni oggetto accetta un parametro di blocco di spin aggiuntivo. La routine acquisisce il blocco di rotazione prima di aggiornare l'elenco e quindi la routine rilascia il blocco di rotazione dopo il completamento dell'operazione. Mentre il blocco viene mantenuto, gli interruzioni vengono disabilitati. Ogni operazione nell'elenco deve usare lo stesso blocco spin per assicurarsi che ogni operazione nell'elenco sia sincronizzata con ogni altra operazione. È necessario usare il blocco di spin solo con queste routine di elencoXxxexInterlocked . Non usare il blocco di rotazione per qualsiasi altro scopo. I driver possono usare lo stesso blocco per più elenchi, ma questo comportamento aumenta la contesa dei blocchi in modo che i driver debbano evitarlo.

Ad esempio, le routine ExInterlockedPopEntryList e ExInterlockedPushEntryList possono supportare la condivisione di un elenco collegato singly in esecuzione in IRQL = PASSIVE_LEVEL e un ISR in esecuzione in DIRQL. Queste routine disabilitano gli interruzioni quando si tiene il blocco di rotazione. Pertanto, il thread ISR e driver possono usare in modo sicuro lo stesso blocco spin nelle chiamate a queste routine Di elencoXxxexInterlocked senza rischiare un deadlock.

Non combinare le chiamate alle versioni atomiche e non atomiche delle operazioni di elenco nello stesso elenco. Se le versioni atomiche e non atomiche vengono eseguite contemporaneamente nello stesso elenco, la struttura dei dati potrebbe essere danneggiata e il computer potrebbe interrompere la risposta o la verifica dei bug, ovvero l'arresto anomalo. Non è possibile acquisire il blocco di spin durante la chiamata alla routine non atomica come alternativa alla combinazione di chiamate a versioni atomiche e non atomiche delle operazioni di elenco. L'uso del blocco di rotazione in questo modo non è supportato e potrebbe comunque causare il danneggiamento dell'elenco.

Il sistema fornisce anche un'implementazione alternativa degli elenchi collegati atomicamente collegati che è più efficiente. Per altre informazioni, vedere Elenchi collegati sequenziati.

Elenchi collegati doubly

Il sistema operativo offre il supporto predefinito per elenchi collegati doubly che usano strutture LIST_ENTRY . Un elenco collegato doubly è costituito da un elenco head più un numero di voci di elenco. Il numero di voci di elenco è zero se l'elenco è vuoto. Ogni voce di elenco è rappresentata come struttura LIST_ENTRY . Il capo elenco è rappresentato anche come struttura LIST_ENTRY .

Ogni struttura LIST_ENTRY contiene un membro Flink e un membro Blink . Entrambi i membri sono puntatori alle strutture LIST_ENTRY .

Nella struttura LIST_ENTRY che rappresenta la testa elenco, il membro Flink punta alla prima voce dell'elenco e il membro Blink punta all'ultima voce dell'elenco. Se l'elenco è vuoto, Flink e Blink del punto head dell'elenco alla testa dell'elenco stesso.

Nella struttura LIST_ENTRY che rappresenta una voce nell'elenco, il membro Flink punta alla voce successiva nell'elenco e il membro Blink punta alla voce precedente nell'elenco. Se la voce è l'ultima nell'elenco, Flink punta alla testa dell'elenco. Analogamente, se la voce è la prima nell'elenco, Blink punta alla testa dell'elenco.

Anche se queste regole potrebbero sembrare sorprendenti in primo luogo, consentono l'inserimento e la rimozione dell'elenco di operazioni di inserimento e rimozione per l'implementazione senza rami di codice condizionale.

Le routine che modificano un elenco collegato doubly accettano un puntatore a un LIST_ENTRY che rappresenta la testa dell'elenco. Queste routine aggiornano i membri Flink e Blink nella testa dell'elenco in modo che questi membri puntino alla prima e all'ultima voce nell'elenco risultante.

Si supponga che la variabile ListHead sia un puntatore alla struttura LIST_ENTRY che rappresenta la testa elenco. Un driver modifica ListHead come indicato di seguito:

  • Per inizializzare l'elenco come vuoto, usare InitializeListHead, che inizializza ListHead-Flink e ListHead-Blink>> per puntare a ListHead.

  • Per inserire una nuova voce nella parte iniziale dell'elenco, allocare un LIST_ENTRY per rappresentare la nuova voce e quindi chiamare InsertHeadList per inserire la voce all'inizio dell'elenco.

  • Per aggiungere una nuova voce alla parte finale dell'elenco, allocare un LIST_ENTRY per rappresentare la nuova voce e quindi chiamare InsertTailList per inserire la voce alla fine dell'elenco.

  • Per rimuovere la prima voce dall'elenco, usare RemoveHeadList. Restituisce un puntatore alla voce rimossa dall'elenco o a ListHead se l'elenco è vuoto.

  • Per rimuovere l'ultima voce dall'elenco, usare RemoveTailList. Restituisce un puntatore alla voce rimossa dall'elenco o a ListHead se l'elenco è vuoto.

  • Per rimuovere una voce specificata dall'elenco, usare RemoveEntryList.

  • Per verificare se un elenco è vuoto, usare IsListEmpty.

  • Per aggiungere un elenco alla parte finale di un altro elenco, usare AppendTailList.

Un LIST_ENTRY, da solo, dispone solo di membri Blink e Flink . Per archiviare i propri dati negli elenchi, incorporare la LIST_ENTRY come membro della struttura che descrive la voce dell'elenco, come indicato di seguito.

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

Per aggiungere una nuova voce a un elenco, allocare una struttura XXX_ENTRY e quindi passare un puntatore al membro ListEntry a InsertHeadList o InsertTailList. Per convertire un puntatore a un LIST_ENTRY in un XXX_ENTRY, usare CONTAINING_RECORD. Per un esempio di questa tecnica, usando elenchi collegati in modo singly, vedere Elenchi collegati singly sopra.

Il sistema fornisce anche versioni atomice delle operazioni di elenco, ExInterlockedInsertHeadList, ExInterlockedInsertTailList eExInterlockedRemoveHeadList. Si noti che non esiste alcuna versione atomica di RemoveTailList o RemoveEntryList. Ogni routine accetta un parametro di blocco di spin aggiuntivo. La routine acquisisce il blocco di rotazione prima di aggiornare l'elenco e quindi rilascia il blocco di rotazione dopo il completamento dell'operazione. Mentre il blocco viene mantenuto, gli interruzioni vengono disabilitati. Ogni operazione nell'elenco deve usare lo stesso blocco spin per assicurarsi che ogni operazione nell'elenco sia sincronizzata con ogni altra. È necessario usare il blocco di spin solo con queste routine di elencoXxxexInterlocked . Non usare il blocco di rotazione per qualsiasi altro scopo. I driver possono usare lo stesso blocco per più elenchi, ma questo comportamento aumenta la contesa dei blocchi in modo che i driver debbano evitarlo.

Ad esempio, le routine ExInterlockedInsertHeadList, ExInterlockedInsertTailList eExInterlockedRemoveHeadList possono supportare la condivisione di un elenco collegato doubly da un thread di driver in esecuzione in IRQL = PASSIVE_LEVEL e un ISR in esecuzione in DIRQL. Queste routine disabilitano gli interruzioni quando si tiene il blocco di rotazione. Pertanto, il thread ISR e driver possono usare in modo sicuro lo stesso blocco spin nelle chiamate a queste routine Di elencoXxxexInterlocked senza rischiare un deadlock.

Non combinare le chiamate alle versioni atomiche e non atomiche delle operazioni di elenco nello stesso elenco. Se le versioni atomiche e non atomiche vengono eseguite contemporaneamente nello stesso elenco, la struttura dei dati potrebbe diventare danneggiata e il computer potrebbe interrompere la risposta o la verifica dei bug , ovvero l'arresto anomalo. Non è possibile acquisire il blocco di spin durante la chiamata alla routine non atomica per evitare di combinare chiamate a versioni atomiche e non atomiche delle operazioni di elenco. L'uso del blocco di rotazione in questo modo non è supportato e potrebbe comunque causare il danneggiamento dell'elenco.

Elenchi collegati sequenziati

Un elenco collegato sequenziato è un'implementazione di elenchi collegati in modo sequenza che supportano le operazioni atomica. È più efficiente per le operazioni atomica rispetto all'implementazione di elenchi collegati singly descritti in Elenchi collegati Singly.

Una struttura SLIST_HEADER viene usata per descrivere la testa di un elenco collegato sequenziato, mentre SLIST_ENTRY viene utilizzata per descrivere una voce nell'elenco.

Un driver modifica l'elenco come indicato di seguito:

Un SLIST_ENTRY, per sé, ha solo un membro Next . Per archiviare i propri dati negli elenchi, incorporare il SLIST_ENTRY come membro della struttura che descrive la voce di elenco, come indicato di seguito.

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

} XXX_ENTRY;

Per aggiungere una nuova voce all'elenco, allocare una struttura XXX_ENTRY e quindi passare un puntatore al membro SListEntry a ExInterlockedPushEntrySList. Per convertire un puntatore al SLIST_ENTRY in un XXX_ENTRY, usare CONTAINING_RECORD. Per un esempio di questa tecnica, usando elenchi non collegati in sequenza, vedere Elenchi collegati Singly.

Avviso Per i sistemi operativi Microsoft Windows a 64 bit, le strutture SLIST_ENTRY devono essere allineate a 16 byte.

Windows XP e versioni successive di Windows forniscono versioni ottimizzate delle funzioni elenco collegate sequenziate che non sono disponibili in Windows 2000. Se il driver usa queste funzioni e deve essere eseguito anche con Windows 2000, il driver deve definire il flag _WIN2K_COMPAT_SLIST_USAGE, come indicato di seguito:

#define _WIN2K_COMPAT_SLIST_USAGE

Per i processori basati su x86, questo flag fa sì che il compilatore usi le versioni delle funzioni di elenco collegate sequenziate compatibili con Windows 2000.