Связанные списки

Связанные списки в ядре Linux.

Связанные списки используется в очень многих местах в коде ядра. Действительно, если взять какую-нибудь из подсистем, то обязательно увидим обьявление struct list_head в одной из структур. list_head и есть реализацией двухсвязных списков в Linux.

Что такое двухсвязный список хорошо написано в книге Р. Лава "Разработка ядра Linux". Если быть кратким, то это есть не что инное, как набор связанных элементом. Причем каждый элемент указывает как на следующий, так и на предыдущий. Это все реализованно в include/linux/list.h.

+++++++++++++++++++++++++++++++++++++++++++++
struct list_head {
struct list_head *next, *prev;
};

+++++++++++++++++++++++++++++++++++++++++++++
Набор функций-примитивов по работе со списком реализован тут же. Функции добавления в список:
list_add(struct list_head *new, struct list_head *head);
list_add_tail(struct list_head *new, struct list_head *head)

Добавить элемент new после элемента head. Пример использования из /drivers/pci/bus.c
+++++++++++++++++++++++++++++++++++++++++++++

void __devinit pci_bus_add_device(struct pci_dev *dev)
{
device_add(&dev->dev);

down_write(&pci_bus_sem);
list_add_tail(&dev->global_list, &pci_devices);
up_write(&pci_bus_sem);

pci_proc_attach_device(dev);
pci_create_sysfs_dev_files(dev);
}

+++++++++++++++++++++++++++++++++++++++++++++
Вот функции которые добавляют/удаляют задачу в/из массива приоритетов:
+++++++++++++++++++++++++++++++++++++++++++++

static void dequeue_task(struct task_struct *p, struct prio_array *array)
{
array->nr_active--;
list_del(&p->run_list);
if (list_empty(array->queue + p->prio))
__clear_bit(p->prio, array->bitmap);
}

static void enqueue_task(struct task_struct *p, struct prio_array *array)
{
sched_info_queued(p);
list_add_tail(&p->run_list, array->queue + p->prio); /* добавить задачу в массив в зависимости от ее приоритета
__set_bit(p->prio, array->bitmap);
array->nr_active++;
p->array = array;
}

+++++++++++++++++++++++++++++++++++++++++++++

Соответственно существуют функции удаления элемента из очереди:
extern void list_del(struct list_head *entry);
Сама структура list_head как видно не особо полезна, т.к. содержит всего 2 указателя. Поэтому эту структуру вставляют как элемент в другую структуру. Например, структура дескриптора процесса содержит элемент struct list_head run_list, через который дескрипторы процесса связаны в двухсвязный список.

Когда элементы связанны в двухсвязный список, очень полезно получить стркутуру, в которую этот связанный список интегрирован. Т.е., напрмер, есть некоторая структура house:

struct house {
unsigned int number;
const char *street;
....
struct list_head list;
};

Мы хотим иметь глобальный список всех домов global_house, поэтому добавляем дома в этот список.
+++++++++++++++++++++++++++++++++++++++++++++

LIST_HEAD(global_house);

struct list_head *tmp;
struct house {
unsigned int number;
const char* street;
struct list_head list;
};
struct house first_house, second_house, *tmp_house;
first_house.number = 1;
first_house.street = "aaa";
second_house.number = 2;
second_house.street = "bbb";
list_add(&first_house.list, &global_house);
list_add(&second_house.list, &global_house);
list_for_each(tmp, &global_house) {
tmp_house = list_entry(tmp, struct house, list);
printk("number: %d, street: %s\n", tmp_house->number, tmp_house->street);

+++++++++++++++++++++++++++++++++++++++++++++
Результат будет следующим:
number: 2, street: bbb
number: 1, street: aaa