Поделиться через

Связные и двусвязные списки

Односвязные списки

Операционная система предоставляет встроенную поддержку для последовательно связанных списков, использующих структуры SINGLE_LIST_ENTRY . Односвязный список состоит из головы списка и некоторого числа записей списка. (Число записей списка равно нулю, если список пуст.) Каждая запись списка представлена в виде SINGLE_LIST_ENTRY структуры. Головка списка также представлена в виде структуры SINGLE_LIST_ENTRY.

Каждая SINGLE_LIST_ENTRY структура содержит следующий элемент, указывающий на другую SINGLE_LIST_ENTRY структуру. В структуре SINGLE_LIST_ENTRY , представляющей головку списка, следующий член указывает на первую запись в списке или имеет значение NULL, если список пуст. В структуре SINGLE_LIST_ENTRY , представляющей запись в списке, следующий элемент указывает на следующую запись списка или значение NULL, если эта запись является последней в списке.

Подпрограммы, которые управляют последовательно связанным списком, принимают указатель на SINGLE_LIST_ENTRY , представляющий голову списка. Они обновляют указатель далее , чтобы он указывал на первую запись списка после операции.

Предположим, что переменная ListHead является указателем на структуру SINGLE_LIST_ENTRY , представляющую головку списка. Драйвер управляет ListHead следующим образом:

  • Чтобы инициализировать список как пустой, задайте ListHead->Next значение NULL.

  • Чтобы добавить новую запись в список, выделите SINGLE_LIST_ENTRY для представления новой записи, а затем вызовите PushEntryList , чтобы добавить запись в начало списка.

  • Удалите первую запись из списка с помощью PopEntryList.

У SINGLE_LIST_ENTRY есть только следующий член. Чтобы сохранить собственные данные в списках, внедрите SINGLE_LIST_ENTRY в качестве члена структуры, описывающей запись списка, следующим образом.

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

Чтобы добавить новую запись в список, создайте структуру XXX_ENTRY, а затем передайте указатель на элемент SingleListEntry в PushEntryList. Чтобы преобразовать указатель на SINGLE_LIST_ENTRY обратно в XXX_ENTRY, используйте CONTAINING_RECORD. Ниже приведен пример подпрограмм, которые вставляют и удаляют определяемые драйвером записи из последовательно связанного списка.

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

Система также предоставляет атомарные версии операций списка, ExInterlockedPopEntryList и ExInterlockedPushEntryList. Каждый принимает дополнительный параметр спинлок. Подпрограмма получает спин-блокировку перед обновлением списка, а затем освобождает её после завершения операции. Пока блокировка удерживается, прерывания отключены. Каждая операция со списком должна использовать одинаковую spinlock блокировку, чтобы гарантировать, что каждая такая операция со списком синхронизирована с любой другой операцией. Необходимо использовать спин-блокировку только с этими подпрограммами ExInterlockedXxxList. Не используйте спиновую блокировку для других целей. Драйверы могут использовать одну блокировку для нескольких списков, но это поведение увеличивает конфликт блокировки, поэтому драйверы должны избежать его.

Например, подпрограммы ExInterlockedPopEntryList и ExInterlockedPushEntryList могут поддерживать совместное использование односвязного списка потоком драйвера, работающим при IRQL = PASSIVE_LEVEL, и ISR, работающей при DIRQL. Эти подпрограммы отключают прерывания, когда удерживается спиновая блокировка. Таким образом, поток ISR и драйвера может безопасно использовать ту же спиновую блокировку в вызовах этих подпрограмм ExInterlockedXxxList без риска взаимоблокировки.

Не смешивайте вызовы атомарных и неатомических версий операций над одним и тем же списком. Если атомарные и неатомные версии выполняются одновременно в одном списке, структура данных может стать поврежденной, и компьютер может перестать отвечать на запросы или проверять ошибки (то есть сбой). Вы не можете захватить спин-блокировку при вызове неатомарной процедуры вместо смешивания вызовов атомарных и неатомарных версий операций со списком. Использование спин-блокировки таким образом не поддерживается и всё равно может привести к повреждению списка.

Система также обеспечивает альтернативную реализацию атомарных последовательно связанных списков, которые более эффективны. Дополнительные сведения см. в разделе "Последовательность последовательно связанных списков".

Двоякие связанные списки

Операционная система обеспечивает встроенную поддержку вдвойне связанных списков, использующих структуры LIST_ENTRY . Двусвязный список состоит из головного элемента списка и нескольких элементов списка. (Число записей списка равно нулю, если список пуст.) Каждая запись списка представлена в виде LIST_ENTRY структуры. Заголовок списка также представлен как структура LIST_ENTRY.

Каждая LIST_ENTRY структура содержит элемент Flink и элемент Blink . Оба элемента являются указателями на LIST_ENTRY структуры.

В структуре LIST_ENTRY , представляющей голову списка, элемент Flink указывает на первую запись в списке, а член Blink указывает на последнюю запись в списке. Если список пуст, то Flink и Blink головного элемента списка указывают на сам головной элемент.

В структуре LIST_ENTRY , представляющей запись в списке, элемент Flink указывает на следующую запись в списке, а член Blink указывает на предыдущую запись в списке. (Если запись является последней в списке, Flink указывает на голову списка. Аналогичным образом, если запись является первой в списке, Blink указывает на голову списка.)

Хотя эти правила могут показаться удивительными на первый взгляд, они позволяют выполнять операции вставки и удаления списка без ветвей условного кода.

Процедуры, которые управляют двусвязным списком, принимают указатель на LIST_ENTRY, представляющий голову списка. Эти процедуры обновляют элементы Flink и Blink в голове списка, чтобы они указывали на первые и последние записи в результирующем списке.

Предположим, что переменная ListHead является указателем на структуру LIST_ENTRY , представляющую головку списка. Драйвер управляет ListHead следующим образом:

  • Чтобы инициализировать список как пустой, используйте InitializeListHead, который инициализирует ListHead->Flink и ListHead->Blink так, чтобы они указывали на ListHead.

  • Чтобы вставить новую запись в голову списка, выделите LIST_ENTRY для представления новой записи, а затем вызовите InsertHeadList , чтобы вставить запись в начале списка.

  • Чтобы добавить новую запись в хвост списка, выделите LIST_ENTRY для представления новой записи, а затем вызовите InsertTailList , чтобы вставить запись в конце списка.

  • Чтобы удалить первую запись из списка, используйте RemoveHeadList. Возвращает указатель на удаленную запись из списка или в ListHead , если список пуст.

  • Чтобы удалить последнюю запись из списка, используйте RemoveTailList. Возвращает указатель на удаленную запись из списка или в ListHead , если список пуст.

  • Чтобы удалить указанную запись из списка, используйте RemoveEntryList.

  • Чтобы проверить, является ли список пустым, используйте IsListEmpty.

  • Чтобы добавить список к хвосту другого списка, используйте AppendTailList.

В LIST_ENTRY содержится только элементы Blink и Flink. Чтобы сохранить собственные данные в списках, внедрить LIST_ENTRY в качестве члена структуры, описывающей запись списка, как показано ниже.

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

Чтобы добавить новую запись в список, выделите структуру XXX_ENTRY и передайте указатель на элемент ListEntry в InsertHeadList или InsertTailList. Чтобы преобразовать указатель на LIST_ENTRY обратно в XXX_ENTRY, используйте CONTAINING_RECORD. Пример этого метода с использованием последовательно связанных списков см. в разделе "Singly Linked Lists" выше.

Система также предоставляет атомарные версии операций списка, ExInterlockedInsertHeadList, ExInterlockedInsertTailList и ExInterlockedRemoveHeadList. Атомарная версия RemoveTailList или RemoveEntryList отсутствует. Каждая рутина принимает дополнительный параметр spinlock. Процедура получает спин-блокировку перед обновлением списка, а затем освобождает её после завершения операции. Пока блокировка удерживается, прерывания отключены. Каждая операция в списке должна использовать один и тот же спинлок, чтобы убедиться, что каждая такая операция в списке синхронизирована с каждой другой операцией на нём. Необходимо использовать спиновую блокировку только с этими подпрограммами ExInterlockedXxxList. Не используйте спинлок для других целей. Драйверы могут использовать одну блокировку для нескольких списков, но это поведение увеличивает конфликт блокировки, поэтому драйверы должны избежать его.

Например, подпрограммы ExInterlockedInsertHeadList, ExInterlockedInsertTailList и ExInterlockedRemoveHeadList могут поддерживать совместное использование вдвойне связанного списка между потоком драйвера, работающего на уровне IRQL = PASSIVE_LEVEL, и ISR, работающего на уровне DIRQL. Эти подпрограммы отключают прерывания при удержании спин-блокировки. Таким образом, потоки ISR и драйвера могут безопасно использовать один и тот же спинлок при вызове этих подпрограмм ExInterlockedXxxList без риска взаимоблокировки.

Не смешивайте вызовы атомарных и неатомических версий операций списка в одном списке. Если атомарные и неатомные версии выполняются одновременно в одном списке, структура данных может стать поврежденной, и компьютер может перестать отвечать на запросы или проверять ошибки (то есть сбой). (Вы не можете приобрести блокировку спина при вызове неатомической подпрограммы, чтобы избежать смешивания вызовов атомарных и неатомических версий операций списка. Использование блокировки спина в этом режиме не поддерживается и может по-прежнему вызвать повреждение списка.)

Последовательные односвязные списки

Последовательно связанный список представляет собой реализацию последовательно связанных списков, поддерживающих атомарные операции. Это более эффективно для атомарных операций, чем реализация последовательно связанных списков, описанных в Singly Linked Lists.

Структура SLIST_HEADER используется для описания головы последовательно связанного списка, а SLIST_ENTRY используется для описания записи в списке.

Драйвер управляет списком следующим образом:

  • Чтобы инициализировать структуру SLIST_HEADER , используйте ExInitializeSListHead.

  • Чтобы добавить новую запись в список, выделите SLIST_ENTRY для представления новой записи, а затем вызовите ExInterlockedPushEntrySList , чтобы добавить запись в начало списка.

  • Извлеките первую запись из списка с помощью ExInterlockedPopEntrySList.

  • Чтобы полностью очистить список, используйте ExInterlockedFlushSList.

  • Чтобы определить количество записей в списке, используйте ExQueryDepthSList.

У SLIST_ENTRY есть только элемент Next . Чтобы сохранить собственные данные в списках, внедрить SLIST_ENTRY в качестве члена структуры, описывающей запись списка, как показано ниже.

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

} XXX_ENTRY;

Чтобы добавить новую запись в список, выделите XXX_ENTRY структуру, а затем передайте указатель на элемент SListEntry в ExInterlockedPushEntrySList.

Чтобы преобразовать указатель на SLIST_ENTRY обратно в XXX_ENTRY, используйте CONTAINING_RECORD. Пример этой техники с использованием неупорядоченных односвязных списков, см. в разделе "Singly Linked Lists".

Предупреждение Для 64-разрядных операционных систем Microsoft Windows SLIST_ENTRY структуры должны быть выровнены по 16 байтам.