Возвращаясь к теме хранения данных, затронутой ранее, хотелось бы поделиться ещё одной полезностью, которую я часто использую в своих программах, написанных на С.

Сразу оговорюсь, это не моё изобретение, мне подсказал идею мой друг, а он, в свою очередь, добыл эти знания где-то в недрах сетевого ядра FreeBSD.

Итак, имеем проект, написанный на С. Задача – хранить некоторое количество структур данных таким образом, чтобы имелась возможность вставки и удаления произвольной структуры при сохранении адресов всех прочих.

Одним их подходящих решений для данной задачи является кольцевой двусвязный список (я надеюсь, мне не нужно объяснять вам, что это такое). Но в С нет такого встроенного типа, нельзя решить задачу и через шаблоны, как это сделано, например, в STL. На помощь нам приходит близость языка к «железу» и такое мощное (в умелых руках) средство, как приведение типов.

Почему я упомянул здесь про умелые руки? Бездумное приведение типов есть отличный источник трудноуловимых ошибок. Хрестоматийным случаем является приведение беззнакового целого к знаковому и наоборот. Не зря в С++ это действие сопровождается ритуальными плясками с static_cast и прочими cast-ами. Поэтому пользоваться им необходимо осмотрительно, точно зная, что делаешь.

Сначала нам необходимо провести подготовительные работы. Знакомьтесь – базовая структура для кольцевого двусвязного списка: 


struct dl_node {
  struct dl_node  *next; // Указатель на следующий
                         // элемент
  struct dl_node  *prev; // Указатель на предыдущий
                         // элемент
};

У пустого списка, представленного своим головным элементом, оба указателя содержат адрес самой структуры «головы».

Пустой двусвязный список

При добавлении элемента его элементы next и prev будут указывать на «голову» списка, а те же элементы «головы» – на добавленный элемент.

Двусвязный список с одним элементом

Далее можно добавлять элементы в конец и начало списка, то есть до и после головного элемента. Получаем такую структуру:

Двусвязный список

Для того, чтобы удалить элемент из списка, достаточно правильно перелинковать его предыдущего и последующего соседей.

Все эти операции осуществляют функции, находящиеся в файлах list.h и list.c. Архив с ними лежит здесь.

Теперь пришла ваша очередь задать вопрос: «Конечно, всё вышеизложенное весьма интересно, но где же сами данные, которые мы будем хранить при помощи двунаправленного списка?».

Замечание справедливо, поэтому переходим к практическому применению полученного кода.

Пример: необходим список целых знаковых значений.

Для реализации сначала опишем следующую структуру:


struct int_list {
  struct dl_node  node;  // Служебная структура для
                         // реализации кольцевого
                         // двусвязного списка
  int             value; // Собственно, данные
};

Далее определяем переменные.


struct dl_node	our_list; // «голова» списка. Её тип
                          // одинаков для любых типов
                          // хранимых значений - это
                          // очень удобно
struct int_list	*element; // Это указатель на текущий
                          // элемент списка

Инициализируем список 


list_init (&our_list);

Аллокируем и добавляем первый элемент


element = (struct int_list *)malloc (sizeof (int_list));
element->value = 45;
list_append (&our_list, (struct dl_node*)element);

Здесь как раз используется приведение типов. Почему такое возможно? Потому, что структура dl_node есть первый элемент структуры int_list, а значит, их адреса совпадают. Поэтому мы можем свободно приводить их адреса друг к другу, не опасаясь за последствия.

Мы можем добавлять сколько угодно членов любых типов в структуру int_list, и она будет оставаться двусвязным списком, при условии первенства элемента node.

А теперь пробежимся по списку и распечатаем его значения. Сделать это можно многими способами. Мне больше всего нравится такой:


for (element = (struct int_list *)our_list.node.next;
    element != (struct int_list *)&dev->protocols;
    element = (struct int_list *) element ->node.next) {
  printf ("Element is %d\\n", element->value);
}

Пришло время собирать камни. Функции list_remove, служащей для удаления элемента из списка, требуется только один параметр – адрес этого элемента. А бремя освобождения памяти, занятой элементами списка ложится целиком на ваши плечи.

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

Надеюсь, этот набор сегодня пополнился.

P.S. Спасибо Ивану Сагалаеву за его highlight.js