Compartilhar via

Listas vinculadas Singly e Doubly

Listas Encadeadas Simples

O sistema operacional fornece suporte embutido para listas simplesmente encadeadas que usam estruturas SINGLE_LIST_ENTRY. Uma lista simplesmente encadeada consiste em um cabeçalho de lista mais algumas entradas de lista. (O número de entradas de lista será 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 da lista ou é NULL se a lista estiver vazia. Na estrutura SINGLE_LIST_ENTRY que representa uma entrada na lista , o próximo membro aponta para a próxima entrada da lista ou é NULL se essa entrada for a última na lista.

As rotinas que manipulam uma lista encadeada simples usam 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 a cabeçalho da lista. Um driver manipula o 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, em seguida, chame PushEntryList para adicionar a entrada ao início da lista.

  • Coloque a primeira entrada fora da lista usando PopEntryList.

Um SINGLE_LIST_ENTRY, por si só, tem apenas um membro Next . Para armazenar seus próprios dados nas listas, insira o SINGLE_LIST_ENTRY como um membro da estrutura que descreve a entrada de 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 no 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.

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 desabilitadas. Cada operação na lista deve usar o mesmo bloqueio de rotação para garantir que cada operação na lista seja sincronizada com todas as outras operações. Você deve usar o spin lock somente com essas rotinas de 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 do bloqueio, portanto, os drivers devem evitá-lo.

Por exemplo, as rotinas ExInterlockedPopEntryList e ExInterlockedPushEntryList podem dar suporte ao compartilhamento de uma lista simplesmente encadeada por uma thread do driver em execução no IRQL = PASSIVE_LEVEL e um ISR em execução no DIRQL. Essas rotinas desabilitam interrupções quando o bloqueio de rotação é mantido. Assim, o ISR e o thread de driver podem usar com segurança o mesmo bloqueio de rotação em suas chamadas para essas rotinas da ListaXxxExInterlocked sem arriscar um deadlock.

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

O sistema também fornece uma implementação alternativa de listas encadeadas simples atômicas, que é mais eficiente. Para obter mais informações, consulte Listas Ligadas Singulares Sequenciadas.

Listas vinculadas duplamente

O sistema operacional fornece suporte interno para listas vinculadas duplamente que usam estruturas de LIST_ENTRY . Uma lista duplamente vinculada consiste em um cabeçalho de lista mais um número de entradas de lista. (O número de entradas de lista será 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 ponteiros para as estruturas LIST_ENTRY.

Na estrutura LIST_ENTRY que representa o cabeçalho da lista, o membro Flink aponta para a primeira entrada da 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 cabeçalho da lista em si.

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 na lista, o Flink apontará para o cabeçalho da lista. Da mesma forma, se a entrada for a primeira na lista, o Blink apontará 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 condicional.

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 o ListHead da seguinte maneira:

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

  • Para inserir uma nova entrada no cabeçalho da lista, aloque 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, aloque 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 à parte final de outra lista, use AppendTailList.

Um LIST_ENTRY, por si só, tem apenas membros Blink e Flink . Para armazenar seus próprios dados nas listas, insira o LIST_ENTRY como um membro da estrutura que descreve a entrada de 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 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 simplesmente encadeadas, consulte Listas Simplesmente Encadeadas 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 de bloqueio de rotação extra. A rotina adquire o bloqueio de rotação antes de atualizar a lista e libera o bloqueio de rotação após a conclusão da operação. Enquanto o bloqueio é mantido, as interrupções são desabilitadas. Cada operação na lista deve usar o mesmo bloqueio de rotação para garantir que cada operação na lista seja sincronizada com todas as outras. Você deve usar o spin lock somente com essas rotinas de 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 do bloqueio, portanto, os drivers devem evitá-lo.

Por exemplo, as rotinas ExInterlockedInsertHeadList, ExInterlockedInsertTailList e ExInterlockedRemoveHeadList podem dar 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 no DIRQL. Essas rotinas desabilitam interrupções quando o bloqueio de rotação é mantido. Assim, o ISR e o thread de driver podem usar com segurança o mesmo bloqueio de rotação em suas chamadas para essas rotinas da ListaXxxExInterlocked sem arriscar um deadlock.

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

Listas Ligadas Simples Sequenciais

Uma lista vinculada sequenciada é uma implementação de listas vinculadas que dão suporte a operações atômicas. É mais eficiente para operações atômicas do que a implementação de listas simplesmente encadeadas descrita em Listas Simplesmente Encadeadas.

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

Um driver manipula a lista da seguinte maneira:

Um SLIST_ENTRY, por si só, tem apenas um membro Next . Para armazenar seus próprios dados nas listas, insira o SLIST_ENTRY como um membro da estrutura que descreve a entrada de 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 no SLIST_ENTRY de volta para um XXX_ENTRY, use CONTAINING_RECORD. Para obter um exemplo dessa técnica, usando listas encadeadas simples não sequenciais, consulte Listas Encadeadas Simples.

Aviso Para sistemas operacionais Microsoft Windows de 64 bits, as estruturas de SLIST_ENTRY devem estar alinhadas a 16 bytes.

  • Last updated on