Partilhar via

Listas individuais e duplamente vinculadas

Listas Ligadas Simples

O sistema operacional fornece suporte interno para listas vinculadas individualmente que usam estruturas SINGLE_LIST_ENTRY . Uma lista vinculada individualmente consiste em um cabeçalho de lista mais algum número de entradas de lista. (O número de entradas da lista é zero se a lista estiver vazia.) Cada entrada de lista é representada como uma estrutura SINGLE_LIST_ENTRY . O cabeçalho da lista também é representado como uma estrutura SINGLE_LIST_ENTRY .

Cada estrutura SINGLE_LIST_ENTRY contém um membro Next que aponta para outra estrutura SINGLE_LIST_ENTRY . Na estrutura SINGLE_LIST_ENTRY que representa o cabeçalho da lista, o membro Next aponta para a primeira entrada na lista ou é NULL se a lista estiver vazia. Na estrutura SINGLE_LIST_ENTRY que representa uma entrada na lista, o membro Próximo aponta para a próxima entrada da lista ou é NULL se essa entrada for a última da lista.

As rotinas que manipulam uma lista vinculada individualmente levam um ponteiro para um SINGLE_LIST_ENTRY que representa o cabeçalho da lista. Eles atualizam o ponteiro Next para que ele aponte para a primeira entrada da lista após a operação.

Suponha que a variável ListHead seja um ponteiro para a estrutura SINGLE_LIST_ENTRY que representa o cabeçalho da lista. Um driver manipula ListHead da seguinte maneira:

  • Para inicializar a lista como vazia, defina ListHead-Next> como NULL.

  • Para adicionar uma nova entrada à lista, aloque um SINGLE_LIST_ENTRY para representar a nova entrada e chame PushEntryList para adicionar a entrada ao início da lista.

  • Remova a primeira entrada da lista usando PopEntryList.

Um SINGLE_LIST_ENTRY, por si só, só tem um membro Next . Para armazenar seus próprios dados nas listas, incorpore o SINGLE_LIST_ENTRY como um membro da estrutura que descreve a entrada da lista, da seguinte maneira.

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

Para adicionar uma nova entrada à lista, aloque uma estrutura XXX_ENTRY e, em seguida, passe um ponteiro para o membro SingleListEntry para PushEntryList. Para converter um ponteiro para o SINGLE_LIST_ENTRY de volta para um XXX_ENTRY, use CONTAINING_RECORD. Aqui está um exemplo de rotinas que inserem e removem entradas definidas pelo driver de uma lista vinculada individualmente.

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

O sistema também fornece versões atómicas das operações de lista, ExInterlockedPopEntryList e ExInterlockedPushEntryList. Cada um usa um parâmetro de bloqueio de rotação extra. A rotina adquire o bloqueio de rotação antes de atualizar a lista e, em seguida, a rotina libera o bloqueio de rotação após a conclusão da operação. Enquanto o bloqueio é mantido, as interrupções são desativadas. Cada operação na lista deve usar o mesmo bloqueio de rotação para garantir que cada uma dessas operações na lista seja sincronizada com todas as outras operações. Você deve usar o spin lock somente com essas rotinas ExInterlockedXxxList. Não use o bloqueio de rotação para qualquer outra finalidade. Os drivers podem usar o mesmo bloqueio para várias listas, mas esse comportamento aumenta a contenção de bloqueio, por isso os drivers devem evitá-lo.

Por exemplo, as rotinas ExInterlockedPopEntryList e ExInterlockedPushEntryList podem oferecer suporte ao compartilhamento de uma lista vinculada individualmente por um thread de driver em execução em IRQL = PASSIVE_LEVEL e um ISR em execução em DIRQL. Essas rotinas desativam interrupções quando o bloqueio de rotação é mantido. Assim, o ISR e o thread do driver podem usar com segurança o mesmo bloqueio de rotação em suas chamadas para essas rotinas ExInterlockedXxxList sem arriscar um impasse.

Não misture chamadas para as versões atómica e não atómica das operações de lista na mesma lista. Se as versões atômica e não atômica forem executadas simultaneamente na mesma lista, a estrutura de dados pode ficar corrompida e o computador pode parar de responder ou verificar bugs (ou seja, falhar). (Você não pode adquirir o bloqueio de rotação ao chamar a rotina não atômica como uma alternativa à mistura de chamadas para versões atômicas e não atômicas de operações de lista. O uso do bloqueio de rotação dessa maneira não é suportado e ainda pode causar corrupção na lista.)

O sistema também fornece uma implementação alternativa de listas atómicas ligadas individualmente que é mais eficiente. Para obter mais informações, consulte Listas vinculadas individualmente sequenciadas.

Listas duplamente vinculadas

O sistema operacional fornece suporte interno para listas duplamente vinculadas que usam estruturas LIST_ENTRY . Uma lista duplamente vinculada consiste em um cabeçalho de lista mais algum número de entradas de lista. (O número de entradas da lista é zero se a lista estiver vazia.) Cada entrada de lista é representada como uma estrutura LIST_ENTRY . O cabeçalho da lista também é representado como uma estrutura LIST_ENTRY .

Cada estrutura LIST_ENTRY contém um membro Flink e um membro Blink . Ambos os membros são apontadores para estruturas LIST_ENTRY.

Na estrutura LIST_ENTRY que representa o cabeçalho da lista, o membro Flink aponta para a primeira entrada na lista e o membro Blink aponta para a última entrada na lista. Se a lista estiver vazia, Flink e Blink do cabeçalho da lista apontam para o próprio cabeçalho da lista.

Na estrutura LIST_ENTRY que representa uma entrada na lista, o membro Flink aponta para a próxima entrada na lista e o membro Blink aponta para a entrada anterior na lista. (Se a entrada for a última da lista, Flink aponta para o cabeçalho da lista. Da mesma forma, se a entrada for a primeira da lista, Blink aponta para o cabeçalho da lista.)

Embora essas regras possam parecer surpreendentes à primeira vista, elas permitem que as operações de inserção e remoção de lista sejam implementadas sem ramificações de código condicionais.

As rotinas que manipulam uma lista duplamente vinculada levam um ponteiro para um LIST_ENTRY que representa o cabeçalho da lista. Essas rotinas atualizam os membros Flink e Blink no cabeçalho da lista para que esses membros apontem para a primeira e a última entradas na lista resultante.

Suponha que a variável ListHead seja um ponteiro para a estrutura LIST_ENTRY que representa o cabeçalho da lista. Um driver manipula ListHead da seguinte maneira:

  • Para inicializar a lista como vazia, use InitializeListHead, que inicializa ListHead->Flink e ListHead->Blink para indicar a ListHead.

  • Para inserir uma nova entrada no topo da lista, atribua um LIST_ENTRY para representar a nova entrada e, em seguida, chame InsertHeadList para inserir a entrada no início da lista.

  • Para acrescentar uma nova entrada à parte final da lista, atribua um LIST_ENTRY para representar a nova entrada e, em seguida, chame InsertTailList para inserir a entrada no final da lista.

  • Para remover a primeira entrada da lista, use RemoveHeadList. Isso retorna um ponteiro para a entrada removida da lista ou para ListHead se a lista estiver vazia.

  • Para remover a última entrada da lista, use RemoveTailList. Isso retorna um ponteiro para a entrada removida da lista ou para ListHead se a lista estiver vazia.

  • Para remover uma entrada especificada da lista, use RemoveEntryList.

  • Para verificar se uma lista está vazia, use IsListEmpty.

  • Para acrescentar uma lista ao final de outra lista, use AppendTailList.

Um LIST_ENTRY, por si só, só tem membros Blink e Flink . Para armazenar seus próprios dados nas listas, incorpore o LIST_ENTRY como um membro da estrutura que descreve a entrada da lista, da seguinte maneira.

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

Para adicionar uma nova entrada a uma lista, aloque uma estrutura XXX_ENTRY e, em seguida, passe um ponteiro para o membro ListEntry para InsertHeadList ou InsertTailList. Para converter um ponteiro em um LIST_ENTRY de volta para um XXX_ENTRY, use CONTAINING_RECORD. Para obter um exemplo dessa técnica, usando listas vinculadas individualmente, consulte Listas vinculadas individualmente acima.

O sistema também fornece versões atômicas das operações de lista, ExInterlockedInsertHeadList, ExInterlockedInsertTailList e ExInterlockedRemoveHeadList. Não há nenhuma versão atômica de RemoveTailList ou RemoveEntryList. Cada rotina usa um parâmetro extra de bloqueio de rotação. A rotina adquire o bloqueio de rotação antes de atualizar a lista e, em seguida, libera o bloqueio de rotação após a conclusão da operação. Enquanto o bloqueio é mantido, as interrupções são desativadas. Cada operação na lista deve usar o mesmo bloqueio de rotação para garantir que cada uma dessas operações na lista seja sincronizada com todas as outras. Você deve usar o spin lock somente com essas rotinas ExInterlockedXxxList. Não use o bloqueio de rotação para qualquer outra finalidade. Os drivers podem usar o mesmo bloqueio para várias listas, mas esse comportamento aumenta a contenção de bloqueio, por isso os drivers devem evitá-lo.

Por exemplo, as rotinas ExInterlockedInsertHeadList, ExInterlockedInsertTailList e ExInterlockedRemoveHeadList podem oferecer suporte ao compartilhamento de uma lista duplamente vinculada por um thread de driver em execução em IRQL = PASSIVE_LEVEL e um ISR em execução em DIRQL. Essas rotinas desativam interrupções quando o bloqueio de rotação é mantido. Assim, o ISR e o thread do driver podem usar com segurança o mesmo bloqueio de rotação em suas chamadas para essas rotinas ExInterlockedXxxList sem arriscar um impasse.

Não misture chamadas para as versões atómica e não atómica das operações de lista na mesma lista. Se as versões atômica e não atômica forem executadas simultaneamente na mesma lista, a estrutura de dados pode ficar corrompida e o computador pode parar de responder ou verificar bugs (ou seja, falhar). (Você não pode adquirir o bloqueio de rotação ao chamar a rotina não atômica para evitar misturar chamadas para versões atômicas e não atômicas das operações de lista. O uso do bloqueio de rotação dessa maneira não é suportado e ainda pode causar corrupção na lista.)

Listas Ligadas Simples Sequenciadas

Uma lista sequenciada ligada individualmente é uma implementação de listas ligadas individualmente que suporta operações atómicas. É mais eficiente para operações atômicas do que a implementação de listas vinculadas individualmente descritas em Listas vinculadas individualmente.

Uma estrutura SLIST_HEADER é usada para descrever o cabeçalho de uma lista sequenciada individualmente vinculada, enquanto SLIST_ENTRY é usada para descrever uma entrada na lista.

Um driver manipula a lista da seguinte maneira:

Uma estrutura SLIST_ENTRY, por si só, apenas possui um membro Next. Para armazenar seus próprios dados nas listas, incorpore o SLIST_ENTRY como um membro da estrutura que descreve a entrada da lista, da seguinte maneira.

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

} XXX_ENTRY;

Para adicionar uma nova entrada à lista, aloque uma estrutura XXX_ENTRY e, em seguida, passe um ponteiro para o membro SListEntry para ExInterlockedPushEntrySList.

Para converter um ponteiro para o SLIST_ENTRY de volta para um XXX_ENTRY, use CONTAINING_RECORD. Para obter um exemplo dessa técnica, usando listas vinculadas individualmente não sequenciadas, consulte Listas vinculadas individualmente.

Advertência Para sistemas operacionais Microsoft Windows de 64 bits, SLIST_ENTRY estruturas devem estar alinhadas a 16 bytes.

  • Last updated on