Condividi tramite

Liste collegate singole e doppie

Liste concatenate semplici

Il sistema operativo fornisce supporto integrato per elenchi collegati singolarmente che usano strutture SINGLE_LIST_ENTRY. Una lista collegata semplicemente è costituita da una testa della lista e da un certo numero di voci. 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 una struttura di tipo SINGLE_LIST_ENTRY.

Ogni struttura SINGLE_LIST_ENTRY contiene un membro denominato Next che punta a un'altra struttura SINGLE_LIST_ENTRY. Nella struttura SINGLE_LIST_ENTRY che rappresenta l'intestazione dell'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 o è NULL se questa voce è l'ultima nell'elenco.

Le routine che modificano una lista concatenata singolarmente 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 segue:

  • 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.

  • Rimuovere la prima voce dall'elenco usando PopEntryList.

Un SINGLE_LIST_ENTRY, di per sé, ha solo un campo 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 al SINGLE_LIST_ENTRY in un XXX_ENTRY, utilizzare CONTAINING_RECORD. Ecco un esempio di routine che inseriscono e rimuovono voci definite dal driver da una lista collegata singolarmente.

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. Ognuno accetta un parametro di blocco spin aggiuntivo. La routine acquisisce il blocco di selezione prima di aggiornare l'elenco e quindi la routine rilascia il blocco di selezione dopo il completamento dell'operazione. Mentre il blocco viene mantenuto, gli interrupt sono disabilitati. Ogni operazione nell'elenco deve usare lo stesso spin lock per assicurarsi che ogni operazione nell'elenco sia sincronizzata con ogni altra operazione. Devi usare il blocco di spin solo con queste routine ExInterlockedXxxList. Non usare il blocco di rotazione per altri scopi. I driver possono usare lo stesso blocco per più elenchi, ma questo comportamento aumenta la contenzione del blocco e i driver dovrebbero evitarlo.

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

Non combinare le chiamate alle versioni atomiche e non tomiche delle operazioni di elenco nello stesso elenco. Se le versioni atomiche e nonatomiche vengono eseguite contemporaneamente nello stesso elenco, la struttura dei dati potrebbe essere 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 nonatomica come alternativa alla combinazione di chiamate a versioni atomiche e nonatomiche 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 atomicamente che è più efficiente. Per ulteriori informazioni, vedere Sequenced Singly Linked Lists.

Liste doppiamente collegate

Il sistema operativo fornisce il supporto predefinito per liste doppiamente collegate che usano strutture LIST_ENTRY. Una lista doppiamente collegata è costituita da una testa della lista più un certo numero di elementi della lista. Il numero di voci di elenco è zero se l'elenco è vuoto. Ogni voce di elenco è rappresentata come struttura LIST_ENTRY . L'intestazione dell'elenco è rappresentata anche da una 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 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 della testa dell'elenco puntano alla testa stessa dell'elenco.

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.

Sebbene queste regole possano sembrare sorprendenti a prima vista, consentono l'implementazione delle operazioni di inserimento e rimozione degli elenchi senza rami di codice condizionale.

Le routine che modificano un elenco doppiamente collegato prendono un puntatore a un LIST_ENTRY che rappresenta la testa della lista. 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 segue:

  • Per inizializzare l'elenco come vuoto, usare InitializeListHead, che inizializza ListHead->Flink e ListHead->Blink per puntare 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, utilizzare RemoveEntryList.

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

  • Per aggiungere un elenco alla fine 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 di 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 liste collegate singolarmente, vedere Lista Collegata Singolarmente sopra.

Il sistema fornisce anche versioni atomice delle operazioni di elenco, ExInterlockedInsertHeadList, ExInterlockedInsertTailList e ExInterlockedRemoveHeadList. Non esiste alcuna versione atomica di RemoveTailList o RemoveEntryList. Ogni routine accetta un parametro di blocco spin aggiuntivo. La routine acquisisce il blocco di selezione prima di aggiornare l'elenco e quindi rilascia il blocco di selezione dopo il completamento dell'operazione. Mentre il blocco viene mantenuto, gli interrupt sono disabilitati. Ogni operazione nell'elenco deve usare lo stesso spin lock per assicurarsi che ciascuna operazione sia sincronizzata con le altre. Devi usare il blocco di spin solo con queste routine ExInterlockedXxxList. Non usare il blocco di rotazione per altri scopi. I driver possono usare lo stesso blocco per più elenchi, ma questo comportamento aumenta la contenzione del blocco e i driver dovrebbero 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 si tiene il blocco di selezione. Pertanto, il thread ISR e driver possono usare in modo sicuro lo stesso blocco spin nelle chiamate a queste routine ExInterlockedXxxList senza rischiare un deadlock.

Non combinare le chiamate alle versioni atomiche e non tomiche 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 danneggiarsi e il computer potrebbe smettere di rispondere o verificare la presenza di bug (cioè, arresto anomalo). Non è possibile acquisire il blocco di selezione durante la chiamata alla routine nonatomica per evitare di combinare le chiamate alle versioni atomiche e nonatomiche delle operazioni di elenco. L'uso del blocco di selezione in questo modo non è supportato e potrebbe comunque causare il danneggiamento dell'elenco.

Liste concatenate semplici sequenziate

Una lista sequenziata è un'implementazione di liste semplicemente concatenate che supportano operazioni atomiche. È più efficiente per le operazioni atomiche che l'implementazione di liste collegate singolarmente descritta in Liste collegate singolarmente.

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 nel modo seguente:

Un elemento 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 dell'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 nel SLIST_ENTRY in un XXX_ENTRY, usare CONTAINING_RECORD. Per un esempio di questa tecnica, usando liste concatenate singolarmente senza sequenza, vedere Liste concatenate singolarmente.

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

  • Last updated on