Listes singly et Doubly Linked

  • Article

Listes liées de manière unique

Le système d’exploitation fournit une prise en charge intégrée des listes liées séparément qui utilisent des structures SINGLE_LIST_ENTRY . Une liste liée se compose d’une 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 . L’en-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 Next 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 Next 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 a la valeur NULL si cette entrée est la dernière de la liste.

Les routines qui manipulent une liste liée séparément prennent un pointeur vers un SINGLE_LIST_ENTRY qui représente l’en-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 l’en-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 un SINGLE_LIST_ENTRY pour représenter la nouvelle entrée, puis appelez PushEntryList pour ajouter l’entrée au début de la liste.

  • Ôtez 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 vers le membre SingleListEntry à PushEntryList. Pour convertir un pointeur en 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 liée isolément.

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 rotation 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 maintenu, les interruptions sont désactivées. Chaque opération de la liste doit utiliser le même verrou de rotation pour s’assurer que chaque opération de ce type sur la liste est synchronisée avec toutes les autres opérations. Vous devez utiliser le verrouillage 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 verrouillage. Les pilotes doivent donc l’éviter.

Par exemple, les routines ExInterlockedPopEntryList et ExInterlockedPushEntryList peuvent prendre en charge le partage d’une liste liée séparément par un thread de pilote s’exécutant sur IRQL = PASSIVE_LEVEL et un ISR exécuté sur DIRQL. Ces routines désactivent les interruptions lorsque le verrouillage de rotation est maintenu. Ainsi, l’ISR et le thread de pilote peuvent utiliser en toute sécurité le même verrou de rotation dans leurs appels à ces routines ExInterlockedXxxList sans risquer un interblocage.

Ne mélangez pas les appels aux versions atomiques et non atomiques des opérations de liste sur la même liste. Si les versions atomiques et non atomiques sont exécutées simultanément sur la même liste, la structure des données peut être endommagée et l’ordinateur peut cesser de répondre ou de bogues case activée (c’est-à-dire un incident). (Vous ne pouvez pas acquérir le verrou de rotation lors de l’appel de la routine non atomique comme alternative à la combinaison d’appels à des versions atomiques et non atomiques d’opérations de liste. L’utilisation du verrou tournant de cette façon n’est pas prise en charge et peut toujours entraîner une altération de la liste.)

Le système fournit également une implémentation alternative de listes liées de manière atomique qui est plus efficace. Pour plus d’informations, consultez Listes liées singly 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’une 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 . L’en-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 LIST_ENTRY structures.

Dans la structure LIST_ENTRY qui représente l’en-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 l’en-tête de liste elle-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 de la liste. (Si l’entrée est la dernière de la liste, Flink pointe vers l’en-tête de liste. De même, si l’entrée est la première de la liste, Blink pointe vers l’en-tête de liste.)

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

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

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

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

  • Pour insérer une nouvelle entrée en haut de la liste, allouez un 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 un 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. Cela 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. Cela 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 case activée de voir 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, n’a que des membres Blink et Flink . Pour stocker vos propres données dans les listes, incorporez le 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 transmettez un pointeur au membre ListEntry à InsertHeadList ou InsertTailList. Pour convertir un pointeur en LIST_ENTRY en XXX_ENTRY, utilisez CONTAINING_RECORD. Pour obtenir un exemple de cette technique, à l’aide de listes liées séparément, consultez Listes liées séparément ci-dessus.

Le système fournit également des versions atomiques des opérations de liste, ExInterlockedInsertHeadList, ExInterlockedInsertTailList et ExInterlockedRemoveHeadList. (Notez qu’il n’existe aucune version atomique de RemoveTailList ou RemoveEntryList.) Chaque routine prend un paramètre de verrouillage de 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 maintenu, les interruptions sont désactivées. Chaque opération de la liste doit utiliser le même verrou de rotation pour s’assurer que chaque opération de ce type sur la liste est synchronisée avec toutes les autres. Vous devez utiliser le verrouillage 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 verrouillage. Les pilotes doivent donc 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 sur IRQL = PASSIVE_LEVEL et un ISR exécuté sur DIRQL. Ces routines désactivent les interruptions lorsque le verrouillage de rotation est maintenu. Ainsi, l’ISR et le thread de pilote peuvent utiliser en toute sécurité le même verrou de rotation dans leurs appels à ces routines ExInterlockedXxxList sans risquer un interblocage.

Ne mélangez pas les appels aux versions atomiques et non atomiques des opérations de liste sur la même liste. Si les versions atomiques et non atomiques 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 d’case activée de bogues (autrement dit, un incident). (Vous ne pouvez pas acquérir le verrou de rotation lors de l’appel de la routine non atomique pour éviter de mélanger les appels aux versions atomiques et non atomiques des opérations de liste. L’utilisation du verrou tournant de cette façon n’est pas prise en charge et peut toujours entraîner 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 séparément qui prend en charge les opérations atomiques. Il est plus efficace pour les opérations atomiques que l’implémentation de listes liées isolément décrites dans Listes liées isolément.

Une structure SLIST_HEADER est utilisée pour décrire l’en-tête d’une liste séquencée, tandis que SLIST_ENTRY est utilisé pour décrire une entrée dans la liste.

Un pilote manipule la liste comme suit :

Un SLIST_ENTRY, en soi, n’a qu’un membre Next . Pour stocker vos propres données dans les listes, incorporez le 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 vers le membre SListEntry vers ExInterlockedPushEntrySList. Pour convertir un pointeur en SLIST_ENTRY en XXX_ENTRY, utilisez CONTAINING_RECORD. Pour obtenir un exemple de cette technique, à l’aide de listes liées séparément non séquencées, consultez Listes liées singly.

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

Windows XP et les versions ultérieures de Windows fournissent des versions optimisées des fonctions de liste liées séquencées qui ne sont pas disponibles dans Windows 2000. Si votre pilote utilise ces fonctions et doit également s’exécuter avec Windows 2000, il doit définir l’indicateur _WIN2K_COMPAT_SLIST_USAGE, comme suit :

#define _WIN2K_COMPAT_SLIST_USAGE

Pour les processeurs x86, cet indicateur oblige le compilateur à utiliser des versions des fonctions de liste liées séquencées qui sont compatibles avec Windows 2000.