Разработка ядра Linux

Для добавления элемента в связанный список можно использовать следующую функцию.

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>.

Перемещение по связанным спискам

Теперь мы уже знаем, как объявлять, инициализировать и работать со связанными списками в ядре. Это все хорошо, но не имеет никакого смысла, если нет возможности работать С данными, которые хранятся в списках! Связанный список — это просто контейнер, в котором хранятся важные данные. Необходимо иметь способ перемещения по списку и доступа к данным. К счастью, ядро предоставляет набор полезных интерфейсов для перемещения по связанным спискам и обращения к структурам данных, которые хранятся в этих списках.

Обратите внимание, что, в отличие от подпрограмм управления списками, операции перебора элементов списка из n узлов масштабируются как O(n).

Наиболее простой способ выполнять итерации по элементам связанного списка — это использовать макрос list_for_each. Этот макрос принимает два параметра — указатели на структуры list_head. Первый параметр указывает на текущий элемент списка, а второй — на любой элемент списка, для которого необходимо обойти все узлы. На каждой итерации цикла первый параметр макроса указывает на текущий элемент списка, пока не будут пройдены все элементы, как в следующем примере.

struct list_head *p;
list_for_each(p, list) {
 /* p указывает на каждый элемент списка list */
}

Это пока все еще бесполезно! Указатель на структуру узла списка — это не то, что нам нужно. Нам нужен указатель на структуру данных, в которой содержится структура узла. В показанном ранее примере структуры данных my_struct необходимо получить указатель на каждый экземпляр структуры my_struct, а не на их поля list. Макрос list_entry возвращает структуру данных, которая содержит соответствующий элемент list_head. Этот макрос принимает три параметра: указатель на текущий узел, тип структуры данных, в которую включен узел списка, и имя поля структуры данных, в которой хранится этот узел.

struct list_head *p;
struct my_struct *my;

list_for_each(p, mine->list) {
 my = list_entry(p, struct my_struct, list);
 /*
 * указатель my указывает на все структуры данных,
 * в которые включено поле list
 */
}

Макрос list_for_each раскрывается в обычный цикл for. Предыдущий пример раскрывается следующим образом.