Listas vinculadas de Singly e Doubly

  • Artigo

Listas vinculadas do Singly

O sistema operacional fornece suporte interno para listas vinculadas que usam estruturas de SINGLE_LIST_ENTRY . Uma lista vinculada é composta por 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 de lista também é representado como uma estrutura de 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 membro Next aponta para a próxima entrada da lista ou é NULL se essa entrada for a última na lista.

As rotinas que manipulam uma lista vinculada com singly 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, 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 passe um ponteiro para o membro SingleListEntry para PushEntryList. Para converter um ponteiro para o SINGLE_LIST_ENTRY de volta em 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 adicional. 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 bloqueio de rotação somente com essas rotinas de ListaXxxExInterlocked . 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, portanto, os drivers devem evitá-lo.

Por exemplo, as rotinas ExInterlockedPopEntryList e ExInterlockedPushEntryList podem dar suporte ao compartilhamento de uma lista 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 do driver podem usar com segurança o mesmo bloqueio de rotação em suas chamadas para essas rotinas da ListaXxxExInterlocked sem correr o risco de um deadlock.

Não misture chamadas para as versões atômicas e não atômicas das operações de lista na mesma lista. Se as versões atômicas e não atômicas forem executadas simultaneamente na mesma lista, a estrutura de dados poderá ficar corrompida e o computador poderá parar de responder ou marcar de bugs (ou seja, falha). (Você não pode adquirir o bloqueio de rotação ao chamar a rotina não atômica como uma alternativa à combinação de chamadas a versões atômicas e não atô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 atômicas vinculadas de forma mais eficiente. Para obter mais informações, consulte Sequenced Singly Linked Lists.

Listas vinculadas duplamente

O sistema operacional fornece suporte interno para listas duplamente vinculadas que usam estruturas de LIST_ENTRY . Uma lista duplamente vinculada consiste em um cabeçalho de lista mais alguns números 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 de LIST_ENTRY . O cabeçalho de 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 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 da lista apontarão 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, Flink apontará para o cabeçalho da lista. Da mesma forma, se a entrada for a primeira na lista, 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 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 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 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 marcar para ver se uma lista está vazia, use IsListEmpty.

  • Para acrescentar uma lista à parte 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, 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 vinculadas, consulte Listas vinculadas do Singly acima.

O sistema também fornece versões atômicas das operações de lista, ExInterlockedInsertHeadList, ExInterlockedInsertTailList e ExInterlockedRemoveHeadList. (Observe que não há nenhuma versão atômica de RemoveTailList ou RemoveEntryList.) Cada rotina usa um parâmetro de bloqueio de rotação adicional. 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 bloqueio de rotação somente com essas rotinas de ListaXxxExInterlocked . 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, 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 do driver podem usar com segurança o mesmo bloqueio de rotação em suas chamadas para essas rotinas da ListaXxxExInterlocked sem correr o risco de um deadlock.

Não misture chamadas para as versões atômicas e não atômicas das operações de lista na mesma lista. Se as versões atômicas e não atômicas forem executadas simultaneamente na mesma lista, a estrutura de dados poderá ficar corrompida e o computador poderá parar de responder ou marcar de bugs (ou seja, falha). (Você não pode trabalhar para adquirir o bloqueio de rotação ao chamar a rotina não atômica para evitar a combinação de chamadas a versões atômicas e não atô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 vinculadas do Singly sequenciado

Uma lista vinculada em sequência é uma implementação de listas vinculadas com singly que dão suporte a operações atômicas. É mais eficiente para operações atômicas do que a implementação de listas vinculadas de forma singly descritas em Listas Vinculadas do Singly.

Uma estrutura SLIST_HEADER é usada para descrever o cabeçalho de uma lista vinculada sequenciadamente, 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 de XXX_ENTRY e passe um ponteiro para o membro SListEntry para ExInterlockedPushEntrySList. Para converter um ponteiro para o SLIST_ENTRY de volta em um XXX_ENTRY, use CONTAINING_RECORD. Para obter um exemplo dessa técnica, usando listas vinculadas sem sequência, consulte Listas vinculadas do Singly.

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

O Windows XP e versões posteriores do Windows fornecem versões otimizadas das funções de lista vinculadas sequenciadamente vinculadas que não estão disponíveis no Windows 2000. Se o driver usar essas funções e também precisar ser executado com o Windows 2000, o driver deverá definir o sinalizador _WIN2K_COMPAT_SLIST_USAGE, da seguinte maneira:

#define _WIN2K_COMPAT_SLIST_USAGE

Para processadores baseados em x86, esse sinalizador faz com que o compilador use versões das funções de lista sequenciadamente vinculadas que são compatíveis com o Windows 2000.