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

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

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

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

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

Обратите внимание, что, в отличие от подпрограмм управления списками, операции перебора элементов списка из 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. Предыдущий пример раскрывается следующим образом.

for (p = mine->list->next; p != mine->list; p = p->next)