Реализация связанных списков в ядре Linux
В ядре Linux для прохождения по связанным спискам используется унифицированный подход. При прохождении связанного списка, если не важен порядок прохода, эту операцию не обязательно начинать с головного элемента, на самом деле вообще не важно, с какого элемента списка начинать прохождение! Важно только, чтобы при таком прохождении были пройдены все узлы. В большинстве случаев нет необходимости вводить концепции первого и последнего элементов. Если в кольцевом связанном списке содержится коллекция несортированных данных, то любой элемент можно назвать головным. Для прохождения всего связанного списка необходимо взять любой элемент и следовать за указателями, пока снова не вернемся к тому элементу, с которого начали обход списка. Это избавляет от необходимости вводить специальный головной элемент. Кроме того, упрощаются процедуры работы со связанными списками. Каждая подпрограмма должна просто принимать указатель на один элемент — любой элемент списка. Разработчики ядра даже немножко гордятся такой остроумной реализацией.
Связанные списки в ядре, так же как и в любой сложной программе, встречаются часто. Например, в ядре связанный список используется для хранения списка задач (структура task_struct каждого процесса является элементом связанного списка).
Структура элемента списка
Раньше в ядре было несколько реализаций связанных списков. Тем не менее в таких случаях необходима единая реализация с целью убрать разный код, который выполняет одинаковые действия. Во время разработки серии ядер 2.1 была предложена единая реализация связанных списков в ядре. Сегодня во всех подсистемах ядра используется официальная реализация. Для новых разработок необходимо использовать только существующий интерфейс и не нужно изобретать велосипед.
Код работы со связанными списками определен в файле <linux/list.h>, a основная структура данных имеет очень простой вид.
struct list_head {
struct list_head *next, *prev;
};
Обратите внимание на характерное имя структуры list_head. Такое название выбрано, чтобы подчеркнуть, что списку не нужно головного элемента. Наоборот, обход списка можно начинать с любого элемента, и каждый элемент может быть головным. В связи с этим все элементы списка называются головными (list head). Указатель next указывает на следующий элемент списка, а указатель prev — на предыдущий элемент списка. Если текущий элемент списка является последним, то его указатель next указывает на первый узел. Если же текущим элементом является первый, то его указатель prev указывает на последний узел списка. Благодаря элегантной реализации связанных списков без концепции головного элемента, можно вообще не вводить понятия первого и последнего элементов.
Структура list_head сама по себе бесполезна. Ее необходимо включать в другие структуры данных.
struct my_struct {
struct list_head list;
unsigned long dog;
void *cat;
};
Перед использованием элементы связанных списков должны быть инициализированы. Так как элементы связанных списков обычно создаются динамически (иначе, вероятно, не нужно использовать связанный список), то эти элементы, как правило, инициализируются во время выполнения.
struct my_struct *p;
/* выделить память для структуры my_struct ... */
p->dog = 0;
p->cat = NULL;
INIT_LIST_HEAD(&p->list);
Если структура данных создается статически во время компиляции и на нее есть непосредственная ссылка, то инициализацию можно выполнить следующим образом.
struct my_struct mine = {
.list = LIST_HEAD_INIT(mine.list),
.dog = 0,
.cat = NULL
};
Для того чтобы создать и инициализировать связанный список, можно использовать следующее объявление.
static LIST_HEAD(fox);
Эта команда позволяет статически создать связанный список с именем fox.
Нет необходимости явно выполнять какие-либо операции со служебными полями элементов связанного списка. Вместо этого необходимо просто включить структуру узла связанного списка в вашу структуру данных, чтобы можно было легко манипулировать данными и выполнять прохождение по связанному списку.
Работа со связанными списками
Для работы со связанными списками ядро предоставляет семейство функций. Все они принимают указатели на одну или более структур list_head. Все функции выполнены как функции с подстановкой тела (inline) на языке С, и их все можно найти в файле <linux/list.h>.
Интересно, что время выполнения всех этих функций масштабируется как O(1)[97]. Это значит, что они выполняются в течение постоянного интервала времени независимо от количества элементов списка, для которого они вызываются. Например, время добавления элемента в связанный список из 3 и 3000 элементов будет одинаковым. Это, возможно, и не вызывает удивления, но тем не менее, приятно.
Для добавления элемента в связанный список можно использовать следующую функцию.
list_add(struct list_head *new, struct list head *head);
Эта функция добавляет узел new в заданный связанный список сразу после элемента head. Поскольку связанный список является кольцевым и для него не существует понятий первого и последнего узлов, в качестве параметра head можно использовать указатель на любой элемент списка. Если в качестве рассмотренного параметра всегда передавать указатель на последний элемент, то эту функцию можно использовать для организации стека.
Для добавления элемента в конец связанного списка служит следующая функция.
list_add_tail(struct list_head *new,
struct list_head *head);
Эта функция добавляет новый элемент new в связанный список сразу перед элементом, на который указывает параметр head. Поскольку связанный список является кольцевым, то, как и в случае функции list_add(), в качестве параметра head можно передавать указатель на любой элемент списка. Эту функцию можно использовать для реализации очереди, если передавать указатель на первый элемент.
Для удаления узла списка служит следующая функция.
list_del(struct list_head *entry);
Эта функция позволяет удалить из списка элемент, на который указывает параметр entry. Обратите внимание, что эта функция не освобождает память, выделенную под структуру данных, содержащую узел списка, на который указывает параметр entry. Данная функция просто удаляет узел из списка. После вызова этой функции обычно необходимо удалить структуру данных, в которой находится узел list_head.
Для удаления узла из списка и повторной инициализации этого узла служит следующая функция.
list_del_init(struct list head *entry);
Эта. функция аналогична функции list_del(), за исключением того, что она дополнительно инициализирует указанную структуру list_head из тех соображений, что эта структура данных больше не нужна в качестве элемента текущего списка и ее повторно можно использовать.
Для перемещения узла из одного списка в другой предназначена следующая функция.
list_move(struct list_head *list, struct list_head *head);
Эта функция удаляет элемент list из одного связанного списка и добавляет его в другой связанный список после элемента head.
Для перемещения элемента из одного связанного списка в конец другого служит следующая функция.
list_move_tail(struct list_head *list,
struct list_head *head);
Эта функция выполняет то же самое, что и функция list_move(), но вставляет элемент перед элементом head.
Для проверки того, пуст ли список, служит функция.
list_empty(struct list_head *head);
Эта функция возвращает ненулевое значение, если связанный список пуст, и нулевое значение в противном случае.
Для объединения двух не перекрывающихся связанных списков служит следующая функция.
list_splice(struct list_head *list,
struct list_head *head);
Эта функция вставляет список, на который указывает параметр list, в другой список после параметра head.
Для объединения двух не перекрывающихся списков и повторной инициализации старого головного элемента служит следующая функция.
list splice_init(struct list head *list, struct list head *head);
Эта функция аналогична функции list_splice(), за исключением того, что параметр list, представляющий список, из которого удаляются элементы, повторно инициализируется.
Как избежать двух лишних разыменований
Если вам уже доступны указатели next и prev, то можно сэкономить пару процессорных тактов (в частности, время выполнения операций разыменования указателей) путем вызова внутренних функций работы со связанными списками. Все ранее рассмотренные функции в сущности не делают ничего, кроме получения указателей next и prev и вызовов внутренних функций. Внутренние функции имеют те же имена, что и их оболочки, но перед именем используется два символа подчеркивания. Вместо того чтобы вызвать функцию list_del(list), можно вызвать функцию __list_del(prev, next). Это имеет смысл, только когда указанные указатели уже известны. В противном случае просто получится некрасивый код. Для подробной информации об этих интерфейсах можно обратиться к файлу <linux/list.h>.
