главная->Статьи->Списки в С
    

Работа со списками в С

Сравнение с С++

C++ программисты очень гордятся, по-видимому, тем, что у них есть такой инструмент, как STL. Они могут в пять секунд построить и отсортировать вам любой список, создать хэш-таблицу, и т.д. Но есть одно "НО". Лично я глубоко убеждён, что всё, что позволяет сделать С++ можно сделать и на С, ровно таким счетом, как всё, что позволяет сделать С можно сделать на ассемблере. Разница только в том, что делать что-то на ассемблере может оказаться достаточно затруднительным, а на С - уже можно.

Для затравки скажу, что в С есть практически всё, что есть в С++. Но на эту тему (как в С реализовать обработку исключений, как разрабатывать приложения в объектно-ориентированном стиле, где в С аналог шаблонов) будет отдельная статья. Сейчас речь пойдет о работе со списками. Я, конечно, не разделяю полностью позицию Линуса Торвальдса об ущербности С++, но просто чистый С мне очень симпатичен, поэтому буду его защищать всеми силами!

Стандартный подход

Стандартный подход заключается в создании некоей структуры такого типа:

typedef struct list_entry_tag { struct list_entry_tag *next; struct list_entry_tag *prev; void *object; }list_entry_t;

При этом в памяти формируется что-то типа:

list_entry1 ^ +--prev = NULL | +--object -------> object1 | +--next---+ +---нечто | | +---нечто | +-----------+ +---..... | | +---|-----------+ | | V | list_entry2 | ^ +--prev---+ | +--object -------> object2 | +--next---+ +---нечто | | +---нечто | +-----------+ +---..... | | +---|-----------+ | | V | list_entry3 | ^ +--prev---+ | +--object -------> object3 | +--next---+ +---нечто | | +---нечто | +-----------+ +---..... | | +---|-----------+ | | V | list_entry4 | +--prev---+ +--object -------> object4 +--next = NULL +---нечто +---нечто +---.....

Его [этого стандартного подхода] недостаток очевиден: список требует отдельного управления памятью. Т.е. если обычно нам может быть достаточно не сложно работать с динамической памятью (когда у всех объектов мы стараемся четко выделить время жизни, обеспечить упорядоченность выделения памяти под них и их удаление), то в случае со списком не всё так просто: Для каждого объекта у нас должен быть list_entry, этот list_entry надо вовремя создать и вовремя уничтожить. И не дай бог, обратиться к нему после уничтожения - можно получить плавающую ошибку, которую исправить будет очень сложно. Именно из-за этого Java-программисты считают себя существами высшего сорта - у них-то таких проблем почти никогда не бывает - у них же нет указателей!

Подход, основанный на использовании макроса offsetof

Итак, нам нужны списки. Более того, нам желательно, чтоб одни и те же объекты могли быть в нескольких списках (например: алфавитный список, список по возрастанию рейтинга, список по возрастанию номеров телефонов, и т.д.)

В Linux kernel для этого есть замечательный файл: list.h. Основная идея в том, что наш list_entry_t не содержит указателя на объект, а сам содержится в качестве одного из полей объекта. При этом достигается отсутствие необходимости выделять память под элемент списка - память выделяется автоматически вместе с объектом. Отрицательным моментом этого является то, что при уничтожении объекта до удаления его из списка - рушится и весь список тоже, но это не страшно, т.к. потерявши голову по волосам не плачут! Чем быстрее такая ошибка обнаружится - тем лучше.

struct list_head { struct list_head *next, *prev; }; #define LIST_HEAD_INIT(name) { &(name), &(name) } #define LIST_HEAD(name) \ struct list_head name = LIST_HEAD_INIT(name) static inline void INIT_LIST_HEAD(struct list_head *list) { list->next = list; list->prev = list; }

Итак, видим четыре связанных между собой выражения. Очевидно что,
первое из них определяет как раз структуру для поддержания двухсвязного списка
второе служит для примерно такой вот инициализации этой структуры:

struct list_head my_list = LIST_HEAD_INIT(my_list);

третье служит для объявления вместе с инициализацией:

LIST_HEAD(my_list);

ну и четвертое служит для инициализации имеющейся структуры через вызов функции:

struct list_head my_list; INIT_LIST_HEAD(&my_list)

Любой из способов инициализации, указанных на последних трёх листингах, подходит. Главное, что у вновь созданной структуры и next и prev должны указыать на неё саму.

При работе, происходит следующее: допустим, у нас есть такой объект, к которому мы хотим иметь доступ через список:

typedef struct my_object_tag { //здесь какие-то поля (не важно какие) //...... struct list_head alpha_list; //здесь могут снова идти какие-то поля //..... }my_object_t; my_object_t *my_object_create(void) { my_object_t *rslt = NULL; rslt = malloc(sizeof(*rslt)); INIT_LIST_HEAD(rslt->alpha_list); //какая-то другая инициализация //..... return rslt; }

таким образом, после такой инициализации поля alpha_list->next и alpha_list->prev указывают на alpha_list, т.е. считаем, что линки next и prev указывают на сам объект, в котором они есть.

также нам нужно завести отдельную (вне объекта) структуру типа list_head, которая у нас собственно и будет отождествляться со списком:

struct list_head alpha_list = LIST_HEAD_INIT(alpha_list);

Эта структура при такой инициализации фактически также указывает сама на себя, показывая таким образом, что список пуст.

дальше мы будем добавлять объекты к alpha_list следующим образом: в list.h есть такой код:

/* * Insert a new entry between two known consecutive entries. * * This is only for internal list manipulation where we know * the prev/next entries already! */ 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; } /** * list_add - add a new entry * @new: new entry to be added * @head: list head to add it after * * Insert a new entry after the specified head. * This is good for implementing stacks. */ static inline void list_add(struct list_head *new, struct list_head *head) { __list_add(new, head, head->next); } /** * list_add_tail - add a new entry * @new: new entry to be added * @head: list head to add it before * * Insert a new entry before the specified head. * This is useful for implementing queues. */ static inline void list_add_tail(struct list_head *new, struct list_head *head) { __list_add(new, head->prev, head); }

Используя из него list_add либо list_add_tail добавляем наш объект в начало либо в конец списка:

list_add(object->alpha_list, alpha_list);

После добавления нескольких объектов получается такая картина:

object1 object2 object3 +---нечто +---нечто +---нечто +---нечто +---нечто +---нечто alpha_list +alpha_list +alpha_list +alpha_list +--next | +--next | +--next | +--next +--prev | +--prev | +--prev | +--prev +---нечто +---нечто +---нечто +---нечто +---нечто +---нечто

Вот как ссылаются друг на друга ответственные за создание списка поля:

Это очень хорошо, но как получить доступ к самим объектам? Элементы списка ведь ссылаются только на себя, но не на объект. Вот тут и начинают работать некоторые Си-шные трюки. В list.h определён такой макрос:

/** * list_entry - get the struct for this entry * @ptr: the &struct list_head pointer. * @type: the type of the struct this is embedded in. * @member: the name of the list_struct within the struct. */ #define list_entry(ptr, type, member) \ container_of(ptr, type, member)

container_of определён в kernel.h вот так вот:

/** * container_of - cast a member of a structure out to the containing structure * @ptr: the pointer to the member. * @type: the type of the container struct this is embedded in. * @member: the name of the member within the struct. * */ #define container_of(ptr, type, member) ({ \ const typeof( ((type *)0)->member ) *__mptr = (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) );})

а offsetof определён в stddef.h вот так вот:

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

Таким образом, в нашем случае

list_entry(alpha_list.next->next->next, my_object_t, alpha_list);

возвращает указатель на object3. Недостаток только в том, что IDE-шки этого могут не понимать, и, соответственно, не будут помогать вам, высвечивая автоматически список полей my_object_t, после того как вы поставите "->" за закрывающейся скобкой list_entry.

Собственно, соль вся не в том, как это устроено, а в том, что работать с такими списками очень удобно. Например, есть в файле list.h специальные макросы, которые обеспечивают перебор всех объектов списка, имея только указатель на list_head, например:

/** * list_for_each - iterate over a list * @pos: the &struct list_head to use as a loop counter. * @head: the head for your list. * итерирует по list_head объектам */ #define list_for_each(pos, head) \ for (pos = (head)->next; prefetch(pos->next), pos != (head); \ pos = pos->next) /** * list_for_each_entry - iterate over list of given type * @pos: the type * to use as a loop counter. * @head: the head for your list. * @member: the name of the list_struct within the struct. * итерирует по объектам-контейнерам. */ #define list_for_each_entry(pos, head, member) \ for (pos = list_entry((head)->next, typeof(*pos), member); \ prefetch(pos->member.next), &pos->member != (head); \ pos = list_entry(pos->member.next, typeof(*pos), member))

Есть там аналогичные макросы и для перебора в обратную сторону, и вообще много всего, чтобы не загромождать - не буду здесь указывать. Приведу только пример программы, которая используя эту технологию парсит текст, считает количество вхождений каждого слова, выводит таблицу либо по частоте вхождений, либо в алфавитном порядке. Вот ссылка на архив с программой. Для справки надо запустить ./concordance --help

Вот ссылка на соответствующий man. Для тех, кто под Linux, можно просто набрать man queue или man 3 queue. Про man queue мне сказал LJ-user afonia.