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

Ядрам операционной системы, как и многим другим программам, часто необходимо вести списки структур данных. Ядро Linux, порой, содержит в одно и то же время несколько реализаций связного списка. Чтобы уменьшить количество дублирующегося кода, разработчики ядра создали стандартную реализацию кругового, двойного связного списка; другим нуждающимся в манипулировании списками рекомендуется использовать это средство.

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

Чтобы использовать механизм списка, ваш драйвер должен подключить файл <linux/list.h>. Этот файл определяет простую структуру типа list_head:

struct list_head {

    struct list_head *next, *prev;

};

Связные списки, используемые в реальном коде, почти неизменно составлены из структуры одного типа, каждая из которых описывает одну запись в списке. Для использования в вашем коде средства списка Linux, необходимо лишь вставлять list_head внутри структур, входящих в список. Если ваш драйвер, скажем, поддерживает список того, что делать, его декларация будет выглядеть следующим образом:

struct todo_struct {

    struct list_head list;

    int priority; /* зависит от драйвера */

    /* ... добавить другие зависимые от драйвера поля */

};

Головой списка, как правило, является автономная структура list_head. Рисунок 11-1 показывает, как для поддержания списка данных структур используется простая структура list_head.

Рисунок 11-1. Структура данных list_head

Заголовки списков должны быть проинициализированы перед использованием с помощью макроса INIT_LIST_HEAD. Заголовок списка "что-нибудь сделать" может быть объявлен и проинициализирован так:

struct list_head todo_list;

INIT_LIST_HEAD(&todo_list);

Альтернативно, списки могут быть проинициализированы при компиляции:

LIST_HEAD(todo_list);

Некоторые функции для работы со списками определены в <linux/list.h>:

list_add(struct list_head *new, struct list_head *head);

добавляет новую запись сразу же после головы списка, как правило, в начало списка. Таким образом, она может быть использована для создания стеков. Однако, следует отметить, что голова не должна быть номинальной головой списка; если вы передадите структуру list_head, которая окажется где-то в середине списка, новая запись пойдёт сразу после неё. Так как списки Linux являются круговыми, голова списка обычно не отличается от любой другой записи.

list_add_tail(struct list_head *new, struct list_head *head);

Добавляет элемент new перед головой данного списка - в конец списка, другими словами. list_add_tail может, таким образом, быть использована для создания очередей первый вошёл - первый вышел.

list_del(struct list_head *entry);

list_del_init(struct list_head *entry);

Данная запись удаляется из списка. Если эта запись может быть когда-либо вставленной в другой список, вы должны использовать list_del_init, которая инициализирует заново указатели связного списка.

list_move(struct list_head *entry, struct list_head *head);

list_move_tail(struct list_head *entry, struct list_head *head);

Данная запись удаляется из своего текущего списка и добавляется в начало головы. Чтобы поместить запись в конце нового списка, используйте взамен неё list_move_tail.

list_empty(struct list_head *head);

Возвращает ненулевое значение, если данный список пуст.

list_splice(struct list_head *list, struct list_head *head);

Объединение двух списков вставкой списка сразу после головы.

Структуры list_head хороши для реализации списка, подобного структурам, но использующие его программы, как правило, больше заинтересованы в более крупных структурах, которые представляют список как целое. Предусмотрен макрос list_entry, который связывает указатель структуры list_head обратно с указателем на структуру, которая его содержит. Он вызывается следующим образом:

list_entry(struct list_head *ptr, type_of_struct, field_name);

где ptr является указателем на используемую структуру list_head, type_of_struct является типом структуры, содержащей этот ptr, и field_name является именем поля списка в этой структуре. В нашей предыдущей структуре todo_struct поле списка называется просто list. Таким образом, мы бы хотели превратить запись в списке в соответствующую структуру такими строчками:

struct todo_struct *todo_ptr = list_entry(listptr, struct todo_struct, list);

Макрос list_entry требует немного времени, чтобы привыкнуть, но его не так сложно использовать. Обход связных списков достаточно прост: надо только использовать указатели prev и next. В качестве примера предположим, что мы хотим сохранить список объектов todo_struct, отсортированный в порядке убывания. Функция добавления новой записи будет выглядеть примерно следующим образом:

void todo_add_entry(struct todo_struct *new)

{

    struct list_head *ptr;

    struct todo_struct *entry;

    for (ptr = todo_list.next; ptr != &todo_list; ptr = ptr->next) {

        entry = list_entry(ptr, struct todo_struct, list);

        if (entry->priority < new->priority) {

            list_add_tail(&new->list, ptr);

            return;

        }

    }

    list_add_tail(&new->list, &todo_list)

}

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

void todo_add_entry(struct todo_struct *new)

{

    struct list_head *ptr;

    struct todo_struct *entry;

    list_for_each(ptr, &todo_list) {

        entry = list_entry(ptr, struct todo_struct, list);

        if (entry->priority < new->priority) {

            list_add_tail(&new->list, ptr);

            return;

        }

    }

    list_add_tail(&new->list, &todo_list)

}

Использование предусмотренных макросов помогает избежать простых ошибок программирования; разработчики этих макросов также приложили некоторые усилия, чтобы они выполнялись хорошо. Существует несколько вариантов:

list_for_each(struct list_head *cursor, struct list_head *list)

Этот макрос создаёт цикл for, который выполняется один раз с cursor, указывающим на каждую последовательную позицию в списке. Будьте осторожны с изменением списка при итерациях через него.

list_for_each_prev(struct list_head *cursor, struct list_head *list)

Эта версия выполняет итерации назад по списку.

list_for_each_safe(struct list_head *cursor, struct list_head *next, struct list_head *list)

Если ваш цикл может удалить записи в списке, используйте эту версию. Он просто сохраняет следующую запись в списке в next для начала цикла, поэтому не запутается, если запись, на которую указывает cursor, удаляется.

list_for_each_entry(type *cursor, struct list_head *list, member)

list_for_each_entry_safe(type *cursor, type *next, struct list_head *list, member)

Эти макросы облегчают процесс просмотр списка, содержащего структуры данного type. Здесь, cursor является указателем на содержащий структуру тип, и member является именем структуры list_head внутри содержащей структуры. С этими макросами нет необходимости помещать внутри цикла вызов list_entry.

Если вы загляните внутрь <linux/list.h>, вы увидите некоторые дополнительные декларации. Тип hlist является двойным связным списком с отдельным, одно-указательным списком заголовка; он часто используется для создания хэш-таблиц и аналогичных структур. Есть также макросы для итерации через оба типа списков, которые предназначены для работы с механизмом прочитать-скопировать-обновить (описанным в разделе "Прочитать-скопировать-обновить" в Главе 5). Эти примитивы вряд ли будут полезны в драйверах устройств; смотрите заголовочный файл, если вам потребуется дополнительная информация о том, как они работают.