Partager via

Listes liées simples et doubles

Listes chaînées simples

Le système d’exploitation fournit une prise en charge intégrée des listes liées simplement qui utilisent les structures SINGLE_LIST_ENTRY. Une liste chaînée simplement se compose d’un en-tête de liste et d’un certain nombre d’entrées de liste. (Le nombre d’entrées de liste est égal à zéro si la liste est vide.) Chaque entrée de liste est représentée sous la forme d’une structure SINGLE_LIST_ENTRY . La tête de liste est également représentée sous la forme d’une structure SINGLE_LIST_ENTRY .

Chaque structure SINGLE_LIST_ENTRY contient un membre suivant qui pointe vers une autre structure SINGLE_LIST_ENTRY . Dans la structure SINGLE_LIST_ENTRY qui représente l’en-tête de liste, le membre suivant pointe vers la première entrée de la liste ou a la valeur NULL si la liste est vide. Dans la structure SINGLE_LIST_ENTRY qui représente une entrée dans la liste, le membre suivant pointe vers l’entrée suivante de la liste, ou est NULL si cette entrée est la dernière dans la liste.

Les routines qui manipulent une liste chaînée simplement prennent un pointeur vers un SINGLE_LIST_ENTRY qui représente la tête de liste. Ils mettent à jour le pointeur suivant afin qu’il pointe vers la première entrée de la liste après l’opération.

Supposons que la variable ListHead soit un pointeur vers la structure SINGLE_LIST_ENTRY qui représente la tête de liste. Un pilote manipule ListHead comme suit :

  • Pour initialiser la liste comme vide, définissez ListHead-Next> sur NULL.

  • Pour ajouter une nouvelle entrée à la liste, allouez une SINGLE_LIST_ENTRY pour représenter la nouvelle entrée, puis appelez PushEntryList pour ajouter l’entrée au début de la liste.

  • Retirez la première entrée de la liste à l’aide de PopEntryList.

Un SINGLE_LIST_ENTRY, par lui-même, n’a qu’un membre Next . Pour stocker vos propres données dans les listes, incorporez le SINGLE_LIST_ENTRY en tant que membre de la structure qui décrit l’entrée de liste, comme suit.

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

Pour ajouter une nouvelle entrée à la liste, allouez une structure XXX_ENTRY , puis passez un pointeur au membre SingleListEntry à PushEntryList. Pour convertir un pointeur vers le SINGLE_LIST_ENTRY en XXX_ENTRY, utilisez CONTAINING_RECORD. Voici un exemple de routines qui insèrent et suppriment des entrées définies par le pilote d’une liste chaînée simple.

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

Le système fournit également des versions atomiques des opérations de liste, ExInterlockedPopEntryList et ExInterlockedPushEntryList. Chacun prend un paramètre de verrouillage de spin supplémentaire. La routine acquiert le verrou de rotation avant de mettre à jour la liste, puis la routine libère le verrou de rotation une fois l’opération terminée. Pendant que le verrou est conservé, les interruptions sont désactivées. Chaque opération de la liste doit utiliser le même verrou de rotation pour s’assurer que chacune de ces opérations de la liste est synchronisée avec toutes les autres opérations. Vous devez utiliser le verrou de rotation uniquement avec ces routines ExInterlockedXxxList . N’utilisez pas le verrou de rotation à d’autres fins. Les pilotes peuvent utiliser le même verrou pour plusieurs listes, mais ce comportement augmente la contention de verrou afin que les pilotes puissent l’éviter.

Par exemple, les routines ExInterlockedPopEntryList et ExInterlockedPushEntryList peuvent supporter le partage d'une liste chaînée simple, entre un thread de pilote fonctionnant à un niveau IRQL = PASSIVE_LEVEL et un ISR s'exécutant au niveau DIRQL. Ces routines désactivent les interruptions lorsque le verrou de rotation est conservé. Ainsi, le thread ISR et le thread de pilote peuvent utiliser en toute sécurité le même verrou de rotation dans leurs appels à ces routines de liste Xxx ExInterlocked sans risquer d’interblocage.

Ne mélangez pas les appels aux versions atomiques et non atomiques des opérations sur une même liste. Si les versions atomiques et nonatomiques sont exécutées simultanément sur la même liste, la structure de données peut être endommagée et l’ordinateur peut cesser de répondre ou de vérifier les bogues (c’est-à-dire le blocage). (Vous ne pouvez pas acquérir le verrou de rotation lors de l’appel de la routine nonatomique comme alternative au mélange d’appels aux versions atomiques et nonatomiques des opérations de liste. L’utilisation du verrou de rotation de cette manière n’est pas prise en charge et peut encore provoquer une altération de la liste.)

Le système propose également une autre implémentation de listes chaînées atomiques, qui est plus performante. Pour plus d’informations, consultez Listes liées séquencées.

Listes doublement liées

Le système d’exploitation fournit une prise en charge intégrée des listes doublement liées qui utilisent des structures LIST_ENTRY . Une liste doublement liée se compose d’un en-tête de liste et d’un certain nombre d’entrées de liste. (Le nombre d’entrées de liste est égal à zéro si la liste est vide.) Chaque entrée de liste est représentée sous la forme d’une structure LIST_ENTRY . La tête de liste est également représentée sous la forme d’une structure LIST_ENTRY .

Chaque structure LIST_ENTRY contient un membre Flink et un membre Blink . Les deux membres sont des pointeurs vers des structures LIST_ENTRY .

Dans la structure LIST_ENTRY qui représente la tête de liste, le membre Flink pointe vers la première entrée de la liste et le membre Blink pointe vers la dernière entrée de la liste. Si la liste est vide, Flink et Blink de l’en-tête de liste pointent vers le chef de liste lui-même.

Dans la structure LIST_ENTRY qui représente une entrée dans la liste, le membre Flink pointe vers l’entrée suivante de la liste, et le membre Blink pointe vers l’entrée précédente dans la liste. (Si l’entrée est la dernière dans la liste, Flink pointe vers la tête de la liste. De même, si l’entrée est la première de la liste, Blink pointe vers la tête de la liste.)

Bien que ces règles semblent surprenantes à première vue, elles permettent d’implémenter les opérations d’insertion et de suppression de liste sans branches de code conditionnelles.

Les routines qui manipulent une liste doublement liée prennent un pointeur vers un LIST_ENTRY qui représente la tête de liste. Ces routines mettent à jour les membres Flink et Blink dans la tête de liste afin que ces membres pointent vers les premières et dernières entrées de la liste résultante.

Supposons que la variable ListHead soit un pointeur vers la structure LIST_ENTRY qui représente la tête de liste. Un pilote manipule ListHead comme suit :

  • Pour initialiser la liste comme vide, utilisez InitializeListHead, qui initialise > et ListHead-Blink> pour pointer vers ListHead.

  • Pour insérer une nouvelle entrée à la tête de la liste, allouez une LIST_ENTRY pour représenter la nouvelle entrée, puis appelez InsertHeadList pour insérer l’entrée au début de la liste.

  • Pour ajouter une nouvelle entrée à la fin de la liste, allouez une LIST_ENTRY pour représenter la nouvelle entrée, puis appelez InsertTailList pour insérer l’entrée à la fin de la liste.

  • Pour supprimer la première entrée de la liste, utilisez RemoveHeadList. Retourne un pointeur vers l’entrée supprimée de la liste ou vers ListHead si la liste est vide.

  • Pour supprimer la dernière entrée de la liste, utilisez RemoveTailList. Retourne un pointeur vers l’entrée supprimée de la liste ou vers ListHead si la liste est vide.

  • Pour supprimer une entrée spécifiée de la liste, utilisez RemoveEntryList.

  • Pour vérifier si une liste est vide, utilisez IsListEmpty.

  • Pour ajouter une liste à la fin d’une autre liste, utilisez AppendTailList.

Un LIST_ENTRY, par lui-même, ne contient que les membres Blink et Flink. Pour stocker vos propres données dans les listes, incorporez la LIST_ENTRY en tant que membre de la structure qui décrit l’entrée de liste, comme suit.

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

Pour ajouter une nouvelle entrée à une liste, allouez une structure XXX_ENTRY , puis passez un pointeur vers le membre ListEntry à InsertHeadList ou InsertTailList. Pour convertir un pointeur de LIST_ENTRY en XXX_ENTRY, utilisez CONTAINING_RECORD. Pour obtenir un exemple de cette technique, à l'aide de listes simplement chaînées, consultez Listes simplement chaînées ci-dessus.

Le système fournit également des versions atomiques des opérations de liste, ExInterlockedInsertHeadList, ExInterlockedInsertTailList et ExInterlockedRemoveHeadList. Il n’existe aucune version atomique de RemoveTailList ou RemoveEntryList. Chaque routine prend un paramètre de verrou à rotation supplémentaire. La routine acquiert le verrou de rotation avant de mettre à jour la liste, puis libère le verrou de rotation une fois l’opération terminée. Pendant que le verrou est conservé, les interruptions sont désactivées. Chaque opération de la liste doit utiliser le même verrou de rotation pour s’assurer que chacune de ces opérations de la liste est synchronisée avec l’autre. Vous devez utiliser le verrou de rotation uniquement avec ces routines ExInterlockedXxxList . N’utilisez pas le verrou de rotation à d’autres fins. Les pilotes peuvent utiliser le même verrou pour plusieurs listes, mais ce comportement augmente la contention de verrou afin que les pilotes puissent l’éviter.

Par exemple, les routines ExInterlockedInsertHeadList, ExInterlockedInsertTailList et ExInterlockedRemoveHeadList peuvent prendre en charge le partage d’une liste doublement liée par un thread de pilote s’exécutant à IRQL = PASSIVE_LEVEL et un ISR s’exécutant sur DIRQL. Ces routines désactivent les interruptions lorsque le verrou de rotation est conservé. Ainsi, le thread ISR et le thread de pilote peuvent utiliser en toute sécurité le même verrou de rotation dans leurs appels à ces routines de liste Xxx ExInterlocked sans risquer d’interblocage.

Ne mélangez pas les appels aux versions atomiques et non atomiques des opérations sur une même liste. Si les versions atomiques et nonatomiques sont exécutées simultanément sur la même liste, la structure de données risque de devenir endommagée et l’ordinateur peut cesser de répondre ou de vérifier les bogues (c’est-à-dire le blocage). (Vous ne pouvez pas acquérir le verrou de rotation lors de l’appel de la routine nonatomique pour éviter de mélanger les appels aux versions atomiques et nonatomiques des opérations de liste. L’utilisation du verrou de rotation de cette manière n’est pas prise en charge et peut encore provoquer une altération de la liste.)

Listes liées séquencées

Une liste liée séquencée est une implémentation de listes liées singly qui prend en charge les opérations atomiques. Il est plus efficace pour les opérations atomiques que l'implémentation de listes simplement chaînées décrites dans Les listes simplement chaînées.

Une structure SLIST_HEADER est utilisée pour décrire le chef d’une liste liée séquencée, tandis que SLIST_ENTRY est utilisée pour décrire une entrée dans la liste.

Un pilote manipule la liste comme suit :

Un SLIST_ENTRY, seul, possède uniquement le membre Next. Pour stocker vos propres données dans les listes, incorporez la SLIST_ENTRY en tant que membre de la structure qui décrit l’entrée de liste, comme suit.

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

} XXX_ENTRY;

Pour ajouter une nouvelle entrée à la liste, allouez une structure XXX_ENTRY , puis passez un pointeur au membre SListEntry à ExInterlockedPushEntrySList.

Pour convertir un pointeur vers le SLIST_ENTRY en XXX_ENTRY, utilisez CONTAINING_RECORD. Pour obtenir un exemple de cette technique, à l'aide de listes simplement chaînées non séquencées, consultez Listes simplement chaînées.

Avertissement Pour les systèmes d’exploitation Microsoft Windows 64 bits, SLIST_ENTRY structures doivent être alignées sur 16 octets.

  • Last updated on