Книга: Разработка ядра Linux

Структура элемента списка

Структура элемента списка

Раньше в ядре было несколько реализаций связанных списков. Тем не менее в таких случаях необходима единая реализация с целью убрать разный код, который выполняет одинаковые действия. Во время разработки серии ядер 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.

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

Оглавление книги