Введение:
ядро linux написано преимущественно на языке С. В отличие от многих других языков программирования С не имеет хороших встроенных средств для работы с коллекциями структурированных данных. Такие средства отсутствуют и в стандартной библиотеке С. Т.о., Вы, вероятно будете рады узнать, что можно позаимствовать хорошую реализацию циклического двусвязного списка, написанную на языке С из кода ядра linux.
Ясная, лёгкая в использовании реализация циклического двусвязного списка на С находится в файле include/linux/list.h. Код этой реализации эффективен и переносим - в противном случае он не был бы в ядре. Если при программировании ядра необходим список для работы с множеством данных любой структуры, то используют двусвязные списки ядра linux. Путём минимальной правки (удаление аппаратно-зависимого ускорения предвыборки записей списка) списки могут быть адаптированы к использованию в приложениях пользовательского режима. Здесь находится версия файла, пригодная для такого использования.
Преимущества использования таких списков следующие:
- Независимость от типа:
Вы можете использовать любую структуру данных, какую заблагорассудится. - Переносимость:
Хотя я не пробовал использовать списки на всех платформах, но можно предположить, что данная реализация весьма переносима. В противногм случае она бы не попала в дерево исходного кода ядра. - Простота использования:
В силу независимости списков от типа данных записей для инициализации, доступа к элементам списка, прохождения по списку используются одни и те же функции. - Простота восприятия:
Макросы и подставляемые (inline) функции делают код очень элегантным и простым для понимания. - Экономия времени:
Вам не нужно изобретать колесо. Использование списков позволяет существенно сэкономить время на отладку и повторное создание списков для каждой структуры данных, которая используется в программе.
struct my_list {
void *myitem;
struct my_list *next;
struct my_list *prev;
};
Реализации списков в ядре создаёт иллюзию, что это данные содержат в себе список! Например, если у Вас есть список данных со структурой struct my_cool_list, то список будет выглядеть следующим образом:struct my_cool_list {
struct list_head list; /* kernel's list structure */
int my_cool_data;
void* my_cool_void;
};
Следует отметить следующее:
- Список содержится в структурах, которые необходимо связать.
- Структуру struct list_head можно поместить везде в объявлении Вашей структуры.
- struct list_head может иметь любое имя.
- У вас в Вашей структуре может быть несколько полей типа struct list_head!
struct todo_tasks{
char *task_name;
unsigned int name_len;
short int status;
int sub_tasks;
int subtasks_completed;
struct list_head completed_subtasks; /* структура списка */
int subtasks_waiting;
struct list_head waiting_subtasks; /* ещё один список таких же или других элементов! */
struct list_head todo_list; /* список дел - todo_tasks */
};
Вот несколько примеров использования списокв в самом ядре:
Раз уж мы вплотную подошли к спискам, то посмотрим на объявление типа struct list_head в include/linux/list.h:struct list_head{
struct list_head *next;
struct list_head *prev;
};
Пожалуй, самое время перейти к деталям. Для начала, давайте посмотрим, как можно использовать этот тип в нашей программе, а затем рассмотрим, как эта структура работает.
Использование списка:
Думаю, лучший способ ближе познакомиться с функциями для работы со списками, это посмотреть на содержимое файла исходного кода. Код хорошо откомментирован и его понимание не должно вызвать трудностей.
Ниже приведён пример создания, добавления, удаления и прохождения списка.
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
struct kool_list{
int to;
struct list_head list;
int from;
};
int main(int argc, char **argv)
{
struct kool_list *tmp;
struct list_head *pos, *q;
unsigned int i;
struct kool_list mylist;
INIT_LIST_HEAD(&mylist.list);
/* вместо строки выше можно было бы использовать макрос
* LIST_HEAD(mylist) при объявлении списка; данный макрос объявляет
* переменную типа struct list_head с указанным именем и инициализирует её.
*/
/* добавление элементов в mylist */
for (i = 5; i != 0; --i) {
tmp = (struct kool_list *)malloc (sizeof (struct kool_list));
/* INIT_LIST_HEAD(&tmp->list);
*
* здесь производится инициализация поля list динамически созданной структуры типа struct
* kool_list. Эту инициализацию можно пропустить, если следуим будет вызов add_list() или
* любая другая функция подобного рода, которая выполняет инициализацию полей next, prev
*/
printf ("enter to and from:");
scanf ("%d %d", &tmp->to, &tmp->from);
/* добавить новый элемент 'tmp' в список элементов mylist */
list_add(&(tmp->list), &(mylist.list));
/* можно также использовать list_add_tail(), которая добавляет новые элементы
* в хвост списка
*/
}
printf ("\n");
/* теперь у нас есть циклически связанный список элементов типа struct kool_list.
* теперь распечатаем весь список
*/
/* list_for_each() - это макрос, реализующий цикл прохождения по элементам списка.
* первый аргумент макроса используется как счётчик, или иными словами в цикле он
* используется для указания на поле типа list_head текущего элемента списка.
* второй аргумент - указатель на список. Макрос не манипулирует этим указателем.
*/
printf ("traversing the list using list_for_each()\n");
list_for_each(pos, &mylist.list) {
/* в этой строке: pos->next указывает на поле 'list' следующего элемента списка, а
* pos->prev - на поле 'list' предыдущего элемента. Здесь элемент - это запись типа
* struct kool_list. Но нам нужен сам элемент, а не его поле 'list'! list_entry() позволяет
* получить указатель на сам элемент. Как это делается, см. ниже в части "Как
* это работает?".
*/
tmp = list_entry (pos, struct kool_list, list);
/* в качестве аргументов макрос принимает указатель на struct list_head, в котором
* хранится текущая позиция списка, второй аргумент - тип пользовательской структуры,
* членом которой является поле, на которое указывает, первый аргумент и третий
* аргумент - имя этого поля (член типа struct list_head в пользовательской структуре).
* Макрос возвращает указатель на структуру, членом которой является первый аргумент.
* Или точнее говоря, на который указывает первый аргумент - pos.
* Например, выше list_entry() возвратит указатель на элемент типа struct kool_list,
* частью которого является pos
*/
printf("to = %d from= %d\n", tmp->to, tmp->from);
}
printf ("\n");
/* т.к. наш список цикличен, то его можно обойти и в обратном порядке.
* всё, что для этого надо - заменить макрос 'list_for_each' на 'list_for_each_prev',
* а всё остальное останется без изменений.
*
* Также можно использовать list_for_each_entry(), чтобы пройти по элементам списка
* данного типа. Например:
*/
printf ("traversing the list using list_for_each_entry()\n");
list_for_each_entry(tmp, &mylist.list, list)
printf ("to = %d from = %d\n", tmp->to, tmp->from);
/* Как видно, здесь мы не используем макрос list_entry(), чтобы получить указатель
* на элемент списка типа struct kool_list. Этот указатель помещается в переменную tmp
* на "полуавтомате" самим макросом list_for_each_entry() :)
*/
printf ("\n");
/* теперь будем вежливыми и освободим память, захваченную под записи kool_list items.
* т.к. мы будем удалять записи из списка с помощью list_del(), нам нужна защищённая
* версия макроса list_for_each().
* такая версия названа list_for_each_safe(). Этот макрос НЕОБХОДИМО использовать
* для организации цикла, который предусматривает удаление или перемещение записей
* из одного списка в другой.
*/
printf ("deleting the list using list_for_each_safe()\n");
list_for_each_safe(pos, q, &mylist.list){
tmp = list_entry(pos, struct kool_list, list);
printf ("freeing item to = %d from = %d\n", tmp->to, tmp->from);
list_del(pos);
free (tmp);
}
return 0;
}
Как это работает?
В общем, большая часть реализации довольна тривиальна, но тонко она выполнена. Тонкость заключается в том, чтобы получить адрес целой структуры по адресу члена, являющегося частью этой структуры (т.е., получить указатель на структуру, содержащую в себе элемент типа struct list_head). Этот трюк проделывает макрос list_entry(), как мы увидели ранее. Теперь попытаемся понять, как он это делает.
#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
Если опираться на ранее приведённый пример, то макрос будет развёрнут следующим образом:((struct kool_list *)((char *)(pos) - (unsigned long)(&((struct kool_list *)0)->list)))Это смущает многих, однако приём достаточно прост и является широко известным (см. вопрос 2.14 - англ.). Используя указатель на поле типа struct list_head в структуре данных, макрос list_entry() просто высчитывает адрес самой структуры. Чтобы выполнить такой расчёт, необходимо выяснить, где в структуре данных находится член типа list_head (смещение list_head). Затем просто вычисляется смещение члена типа list_head по отношению к указателю, который был передан макросу в качестве первого аргумента.
Следующий вопрос, как нам вычислить смещение элемента внутри структуры данных? Допустим, у нас есть структура struct foo_bar и нам надо найти смещение элемента boo, который является членом структуры. Сделаем это следующим образом:
(unsigned long)(&((struct foo_bar *)0)->boo)Возьмём нулевой адрес памяти и приведём его к указателю на нашу структуру - в данной случае, к указателю на struct foo_bar. Затем возьмём адрес поля, которое нас интересует. Это и будет смещение данного поля внутри структуры. Так как мы узнали абсолютное положение данного элемента в памяти, мы теперь можем с помощью этого элемента получить указатель на конкретный экземпляр целой структуры, опираясь на некоторые данные (например, аргумент pos в случае с макросом list_entry). Вот и всё. Чтобы лучше понять, что происходит, советую вам погонять этот код.
#include <stdio.h>
#include <stdlib.h>
struct foobar {
unsigned int foo;
char bar;
char boo;
};
int main (int argc, char** argv)
{
struct foobar tmp;
printf ("address of &tmp is= %p\n\n", &tmp);
printf ("address of tmp->foo= %p \t offset of tmp->foo= %lu\n", &tmp.foo,
(unsigned long) &((struct foobar *)0)->foo);
printf ("address of tmp->bar= %p \t offset of tmp->bar= %lu\n", &tmp.bar,
(unsigned long) &((struct foobar *)0)->bar);
printf ("address of tmp->boo= %p \t offset of tmp->boo= %lu\n\n", &tmp.boo,
(unsigned long) &((struct foobar *)0)->boo);
printf ("computed address of &tmp using:\n");
printf ("\taddress and offset of tmp->foo= %p\n",
(struct foobar *) (((char *) &tmp.foo) - ((unsigned long) &((struct foobar *)0)->foo)));
printf ("\taddress and offset of tmp->bar= %p\n",
(struct foobar *) (((char *) &tmp.bar) - ((unsigned long) &((struct foobar *)0)->bar)));
printf ("\taddress and offset of tmp->boo= %p\n",
(struct foobar *) (((char *) &tmp.boo) - ((unsigned long) &((struct foobar *)0)->boo)));
return 0;
}
Вывод приведённого куска кода:address of &tmp is = 0xbfffed00 address of tmp->foo = 0xbfffed00 offset of tmp->foo= 0 address of tmp->bar = 0xbfffed04 offset of tmp->bar= 4 address of tmp->boo = 0xbfffed05 offset of tmp->boo= 5 computed address of &tmp using: address and offset of tmp->foo = 0xbfffed00 address and offset of tmp->bar = 0xbfffed00 address and offset of tmp->boo = 0xbfffed00
См. также:
- Код хэш-таблиц, организованных в виде списков.
- Ещё код /sutff/src/
Оригинал статьи на английском лежит здесь.
No comments:
Post a Comment