Связные списки в ядре ОС GNU/Linux
Обычно определение двунаправленнго связного списка выглядит следующим образом:
struct list
{
void *data;
struct list *next;
struct list *prev;
};
К моменту инициализации списка он является пустым (если только мы заранее не определили его элементы статически) и представляется всего лишь одним элементом, а именно «головой» списка:
Рис.1. "Голова" пустого списка
Как видно из рисунка, указатели на следующий next и предыдущий prev элементы указывают на элемент («голову»), к которому они принадлежат (в не кольцевых списках им было бы присвоено значение NULL).
На рисунке 2 можно проследить изменение указателей при добавлении новых элементов (синим цветом выделена «голова» списка).
Рис.2. Добавление элементов в связный список
Для того, чтобы удалить элемент из списка необходимо изменить связи между соседними элементами (переопределить указатели). Таким образом, если мы удалим второй элемент на рисунке 2 справа, то получим список, представленный слева. В коде это можно было записать так (node элемент некоторого списка типа struct list, который представлен выше):
node->next->next->prev = node->prev->prev;
node->prev->prev->next = node->next->next;
...
Такой подход к реализации связных списков используется уже давно и стал в некотором роде стандартом de facto. Давайте сравним его с реализацией списков в ядре операционной системы GNU/Linux (реализацию списка можно найти в файле include/linux/list.h).
Определение списка, которое используется в ядре ОС GNU/Linux, выглядит следующим образом (include/linux/types.h):
struct list_head
{
struct list_head *next, *prev;
};
Обычно структура хранит указатель на поле с данными (поле data в нашем примере), но в реализации списков, используемых в ядре Linux, такого поля нет. Возникает вопрос "А где же храняться данные?". Реализация списков в ядре ОС GNU/Linux является интрузивной (Intrusive list). Узлы интрузивных списков не хранят в себе данные, а лишь указатели на следующий и предыдущий элементы списка, сам же узел является частью структуры, хранящей данные. Такой подход делает структуру общей, то есть не зависящей от данных.
Ниже приведен пример использования структуры list_head для простой реализации стека:
struct stack_t
{
char data;
struct list_head node;
};
LIST_HEAD(top_stack);
Теперь список list_head является частью структуры stack_t, а не представляется самой структурой. Таким образом, вся работа со списком сводится к манипуляциям над list_head, будь то добавление или удаление элемента из списка (мысленно уберите элемент data из рисунков 1 и 2).
Инициализация головы списка производится с помощью макроса LIST_HEAD(), который опеределен следующим образом:
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
#define LIST_HEAD_INIT(name) { &(name), &(name) }
Если взять на себя работу препроцессора, то получим следущее определение головы списка:
struct list_head top_stack = { &(top_stack), &(top_stack) };
Рисунок
Теперь проследим как происходит добавление двух новых элемнетов:
struct stack_t a, b;
a.data = 'A';
b.data = 'B';
INIT_LIST_HEAD(&A.node);
list_add(&A.node, &top_stack);
INIT_LIST_HEAD(&B.node);
list_add(&B.node, &top_stack);
Каждый узел предварительно инициализируется с помощью функции INIT_LIST_HEAD(), который просто присваивает элементам next и prev адрес самого узла:
static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}
Добавление элемента производится с помощью функции list_add:
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
Функция list_add в свою очередь вызывает внутренную функцию __list_add и передает ей три параметра:
new- новый узел;head- голова списка;head->next- узел следующий за головой списка.
static inline void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next)
{
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
Рисунок
Обращение к соответствующей структуре stack_t, и, как следствие, к пользовательским данным (для нашего примера это поле data) производится с помощью специального макроса list_entry:
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
Этот макрос принимает три параметра:
ptr- адрес узла;type- тип пользовательской структуры;member- имя структурыlist_headвнутри пользовательской структуры.
Например:
stack_t tmp = list_entry(top_stack.next, struct stack, node);
В свою очередь list_entry использует макрос container_of(), который и делает всю реальную работу по извлечению элемента:
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
Для того, чтобы использовать ядерную реализацию связных списков в своих программах достаточно взять библиотеку ядра для работы со связными списками и убрать оттуда код связанный с отладкой и некоторыми специфичными функциями (например prefetch(), которая связана с кешированием данных). Готовую к работе библиотеку вы можете найти по адресу ???.
Далее представленна полная реализация стека, на примере которого мы рассмотрим некоторые из доступных функций:
#include <stdlib.h>
#include <stdio.h>
#include "list.h"
typedef char stack_element_t;
struct stack_t
{
stack_element_t data;
struct list_head node;
};
LIST_HEAD(top_stack);
void stack_push(stack_element_t data)
{
struct stack_t *element;
if ((element = malloc(sizeof(struct stack_t))) == NULL) {
fprintf(stderr, "Can't allocate memory\n");
exit(1);
}
element->data = data;
INIT_LIST_HEAD(&element->node);
list_add(&element->node, &top_stack);
}
void stack_pop(void)
{
struct stack_t *tmp;
if (list_empty(&top_stack))
{
fprintf(stderr, "Stack is empty\n");
exit(1);
} else {
tmp = list_entry(top_stack.next, struct stack_t, node);
list_del(top_stack.next);
free(tmp);
}
}
void stack_popall(void)
{
struct stack_t *element, *next;
if (!list_empty(&top_stack))
{
list_for_each_entry_safe(element, next, &top_stack, node) {
list_del(&element->node);
free(element);
}
}
}
void print_stack(void)
{
struct stack_е *element;
if (list_empty(&top_stack))
{
fprintf(stderr, "Stack is empty\n");
exit(1);
} else {
list_for_each_entry(element, &top_stack, node)
printf("data: %c\n", element->data);
}
}
Программа довольно проста для понимания (проверку ошибок мы опустили), поэтому пройдемся только по функциям, связанными со списками, за исключением тех, которые были рассмотренны ранее.
Функция push() принимает один аргумент, а именно, значение, которое мы хотим положить в стек. Выделяется память под структуру struct stack_t, инициализируются необходимые элементы структуры и добавляется новый узел в список при помощи функции list_add().
Если мы положили в стек пять элементов со значениями от 1 до 5, то вывод будет выглядеть следующим образом:
data: 5
data: 4
data: 3
data: 2
data: 1
Если необходимо распологать элементы в обратном порядке, то можно воспользоваться функцией list_add_tail(). Она работает аналогично list_add(), но новый узел вставляет не после head, а до него.
Если в нашей программе заменить list_add() на list_add_tail(), то вывод будет следующим (и вместо реализации стека, мы получаем очередь, которая работает по принципу FIFO):
data: 1
data: 2
data: 3
data: 4
data: 5
Функция pop() должна удалять узел из списка и освобождать память, занимаемую структурой, если список не является пустым.
Проверить является ли список пустым можно при помощи функции list_empty():
static inline int list_empty(const struct list_head *head)
Прежде чем удалить узел из списка, необходимо сохранить адрес структуры, связанной с данным узлом, чтобы освободить занимаемую ей память. Как упоминалось ранее, получить этот адрес можно при помощи макроса list_entry(). В нашей реализации стека можно было бы использовать другой макрос — list_first_entry() для получения первого элемента списка, тогда:
tmp = list_entry(top_stack.next, struct stack, node);
можно было бы заменить на:
tmp = list_first_entry(top_stack, struct stack, node);
Прежде чем освободить память из под элемента типа struct stack_t, необходимо удалить узел из списка. Сделать это можно с помощью функции list_del():
static inline void list_del(struct list_head *entry)
Функция list_del() принимает адрес узла, который необходимо удлать из списка (удалить не означает освободить память, она только «отвязывет» узел от списка, освобождать память необходимо самостоятельно).
Теперь рассмотрим функцию печати содержимого стека print_stack(). Для этого нам необходимо пройти все элементы списка и вывести содержимое каждого из них. Сделать это можно следующим образом:
struct stack *element;
struct list_head *pos;
list_for_each(pos, &top->stack)
{
element = list_entry(pos, struct stack_t, node);
printf("data: %d\n", element->data);
}
Макрос list_for_each() проходит по всем узлам списка, начиная с top_stack, и сохраняет текующую позицию в pos. Получить адрес структуры для pos мы можем с помощью ранее описанного макроса list_entry(). Но есть более простой способ выполнить описанную выше опирацию — использовать макрос list_for_each_entry(). Тогда код будет выглядить следующим образом:
struct stack_t *element;
list_for_each_entry(element, &top->stack, node)
printf("data: %d\n", element->data);
Если необходимо осуществить вывод в обратном порядке, то можно воспользоваться макросом list_for_each_entry_reverse().
Функция popall() необходима в том случае, когда мы завершаем работу программы не освободив память из под всех элементов (т.е., если список не является пустым). Фактически, нам надо пройти по каждому узлу и удалить его из списка, а затем освободить память, занимаемую структурой. Это можно было бы сделать при помощи макроса list_for_each_entry() и функции list_del(), но пришлось бы хранить указатели next и prev (на следующий и предыдущий элементы, соответственно) во временных переменных. Поэтому для этих целей есть специально предназначенный макрос list_for_each_entry_safe(), который аналогичен list_for_each_entry(), но принимает еще один дополнительный аргумент next для временного хранения элемента:
struct stack_t *element, *next;
list_for_each_entry_safe(element, next, &top_stack, node) {
list_del(&element->node);
free(element);
}