Elenchi collegati da singly e doubly

  • Articolo

Elenchi collegati singly

Il sistema operativo offre il supporto predefinito per elenchi collegati cane che usano strutture SINGLE_LIST_ENTRY . Un elenco collegato singly è costituito da una testa elenco più un certo 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 . L'intestazione dell'elenco è rappresentata 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 l'intestazione elenco, il membro Successivo punta alla prima voce dell'elenco oppure è 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 oppure è 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 l'intestazione 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 l'intestazione dell'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, da solo, 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 di 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 al SINGLE_LIST_ENTRY in un XXX_ENTRY, usare CONTAINING_RECORD. Di seguito è riportato un esempio di routine che inseriscono e rimuovono 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 parametro accetta un parametro di blocco spin aggiuntivo. La routine acquisisce il blocco spin prima di aggiornare l'elenco e quindi la routine rilascia il blocco di rotazione dopo il completamento dell'operazione. Mentre il blocco è mantenuto, le interruzioni sono disabilitate. Ogni operazione nell'elenco deve usare lo stesso blocco di selezione per garantire che ogni operazione nell'elenco sia sincronizzata con ogni altra operazione. È necessario utilizzare il blocco di selezione solo con queste routine ElencoXxxexInterlocked . Non usare il blocco di rotazione per altri scopi. I driver possono usare lo stesso blocco per più elenchi, ma questo comportamento aumenta la contesa di blocco in modo che i driver debbano evitarlo.

Ad esempio, le routine ExInterlockedPopEntryList e ExInterlockedPushEntryList possono supportare la condivisione di un elenco collegato singly da un thread driver in esecuzione in IRQL = PASSIVE_LEVEL e un ISR in esecuzione in DIRQL. Queste routine disabilitano gli interrupt quando viene mantenuto il blocco di rotazione. Pertanto, il thread ISR e driver possono usare in modo sicuro lo stesso blocco di rotazione nelle chiamate a queste routine 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 risultare danneggiata e il computer potrebbe smettere di rispondere o controllare il bug, ovvero l'arresto anomalo. Non è possibile acquisire il blocco di selezione 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 selezione in questo modo non è supportato e potrebbe comunque causare il danneggiamento dell'elenco.

Il sistema fornisce anche un'implementazione alternativa di elenchi collegati atomici 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 una testa elenco più un certo 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 . L'intestazione elenco è rappresentata anche come struttura LIST_ENTRY .

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

Nella struttura LIST_ENTRY che rappresenta l'intestazione dell'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 puntano all'intestazione dell'elenco stessa.

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 all'intestazione dell'elenco. Analogamente, se la voce è la prima nell'elenco, Blink punta all'intestazione dell'elenco.

Sebbene queste regole possano sembrare sorprendenti a prima vista, consentono di implementare le operazioni di inserimento e rimozione dell'elenco senza rami di codice condizionale.

Le routine che modificano un elenco collegato doubly accettano un puntatore a un LIST_ENTRY che rappresenta l'intestazione 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 l'intestazione dell'elenco. Un driver modifica ListHead come indicato di seguito:

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

  • Per inserire una nuova voce all'inizio 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, ha solo membri Blink e Flink . Per archiviare i propri dati negli elenchi, incorporare il 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 in 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 e ExInterlockedRemoveHeadList. Si noti che non esiste alcuna versione atomica di RemoveTailList o RemoveEntryList. Ogni routine accetta un parametro di blocco spin aggiuntivo. La routine acquisisce il blocco di rotazione prima di aggiornare l'elenco e quindi rilascia il blocco di selezione dopo il completamento dell'operazione. Mentre il blocco è mantenuto, le interruzioni sono disabilitate. Ogni operazione nell'elenco deve usare lo stesso blocco di selezione per garantire che ogni operazione nell'elenco sia sincronizzata tra loro. È necessario utilizzare il blocco di selezione solo con queste routine ElencoXxxexInterlocked . Non usare il blocco di rotazione per altri scopi. I driver possono usare lo stesso blocco per più elenchi, ma questo comportamento aumenta la contesa di blocco in modo che i driver debbano evitarlo.

Ad esempio, le routine ExInterlockedInsertHeadList, ExInterlockedInsertTailList e ExInterlockedRemoveHeadList possono supportare la condivisione di un elenco collegato doubly da un thread driver in esecuzione in IRQL = PASSIVE_LEVEL e un ISR in esecuzione in DIRQL. Queste routine disabilitano gli interrupt quando viene mantenuto il blocco di rotazione. Pertanto, il thread ISR e driver possono usare in modo sicuro lo stesso blocco di rotazione nelle chiamate a queste routine 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 smettere di rispondere o controllare il bug ( ovvero , arresto anomalo). Non è possibile acquisire il blocco di selezione 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 selezione 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 caningly che supportano 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 utilizzata per descrivere l'intestazione di un elenco collegato sequenziato, mentre SLIST_ENTRY viene utilizzata per descrivere una voce nell'elenco.

Un driver modifica l'elenco come segue:

Un SLIST_ENTRY, di 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.