Singly и вдвойне связанные списки

Singly Linked Lists

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Последовательно связанный список — это реализация последовательно связанных списков, поддерживающих атомарные операции. Более эффективно для атомарных операций, чем реализация последовательно связанных списков, описанных в списке 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 байтам.

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

#define _WIN2K_COMPAT_SLIST_USAGE

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