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

  • Статья

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

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

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

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

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

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

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

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

У SINGLE_LIST_ENTRY есть только элемент Next. Чтобы сохранить собственные данные в списках, внедрите 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. Каждый из них принимает дополнительный параметр spin lock. Подпрограмма получает блокировку спина перед обновлением списка, а затем подпрограмма освобождает спин-блокировку после завершения операции. Пока блокировка удерживается, прерывания отключаются. Каждая операция в списке должна использовать одну и ту же блокировку спина, чтобы убедиться, что каждая такая операция в списке синхронизирована с каждой другой операцией. Вы должны использовать спин-блокировку только с этими подпрограммами 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 отсутствует.) Каждая подпрограмма принимает дополнительный параметр спин-блокировки. Подпрограмма получает спиновую блокировку перед обновлением списка, а затем освобождает спиновую блокировку после завершения операции. Пока блокировка удерживается, прерывания отключаются. Каждая операция в списке должна использовать одну и ту же блокировку спина, чтобы обеспечить синхронизацию каждой такой операции в списке. Вы должны использовать спин-блокировку только с этими подпрограммами ExInterlockedXxxList . Не используйте спин-блокировку для других целей. Драйверы могут использовать одну и ту же блокировку для нескольких списков, но такое поведение увеличивает состязание за блокировку, поэтому драйверы должны избегать этого.

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

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

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

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

Структура 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. Пример этого метода использования неупорядоченных списков с поперемыкающими ссылками см. в разделе Единые связанные списки.

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

Windows XP и более поздние версии Windows предоставляют оптимизированные версии последовательно связанных функций списков, которые недоступны в Windows 2000. Если драйвер использует эти функции и также должен работать с Windows 2000, драйвер должен определить флаг _WIN2K_COMPAT_SLIST_USAGE следующим образом:

#define _WIN2K_COMPAT_SLIST_USAGE

Для процессоров на базе x86 этот флаг заставляет компилятор использовать версии последовательно связанных функций списков, совместимых с Windows 2000.