Безопасные с точки зрения типов универсальные структуры данных в простом C?
Я сделал намного больше программирования на C++, чем "простой C" программирование. Одна вещь, которую я очень пропускаю, когда программирование в плоскости C является безопасными с точки зрения типов универсальными структурами данных, которые обеспечиваются в C++ через шаблоны.
Ради конкретности рассмотрите универсальный отдельно связанный список. В C++ это - простой вопрос, чтобы определить Ваш собственный шаблонный класс и затем инстанцировать его для типов, в которых Вы нуждаетесь.
В C я могу думать о нескольких способах реализовать универсальный отдельно связанный список:
- Запишите тип (типы) связанного списка и процедуры поддержки однажды, с помощью пустых указателей для обхождения системы типов.
- Запишите макросы препроцессора, берущие необходимые имена типов, и т.д., для генерации определенной для типа версии структуры данных и поддерживающий процедуры.
- Используйте более сложный, автономный инструмент, чтобы сгенерировать код для типов, в которых Вы нуждаетесь.
Мне не нравится опция 1, как это, ниспровергает систему типов и вероятно имел бы худшую производительность, чем специализированная определенная для типа реализация. Используя универсальное представление структуры данных для всех типов, и бросающий для освобождения указатели, насколько я вижу, требует косвенности, которой избежала бы реализация, специализированная для типа элемента.
Опция 2 не требует никаких дополнительных инструментов, но это чувствует себя несколько неуклюжим, и могло дать плохие ошибки компилятора при неподходящем использовании.
Опция 3 могла дать лучшие сообщения ошибки компилятора, чем опция 2, поскольку специализированный код структуры данных будет находиться в расширенной форме, которая могла быть открыта в редакторе и осмотрена программистом (в противоположность коду, сгенерированному макросами препроцессора). Однако эта опция является самой тяжелой, шаблоны своего рода "плохого человека". Я использовал этот подход прежде, с помощью простого sed сценария для специализации "шаблонной" версии некоторого кода C.
Я хотел бы программировать свои будущие проекты "низкого уровня" в C, а не C++, но был напуган мыслью о перезаписи структур общих данных для каждого определенного типа.
Какой опыт люди имеют с этой проблемой? Есть ли хорошие библиотеки универсальных структур данных и алгоритмов в C, которые не идут с Опцией 1 (т.е. бросающий к и от пустых указателей, который жертвует безопасностью типов и добавляет уровень абстракции)?
5 ответов
Вариант 1 - это подход, используемый большинством реализаций общих контейнеров на языке Си, которые я вижу. Набор драйверов Windows и ядро Linux используют макрос, позволяющий встраивать ссылки на контейнеры в любое место структуры, причем макрос используется для получения указателя структуры из указателя на поле ссылки:
Вариант 2 - это подход, используемый в BSD's tree. h и queue.h для реализации контейнеров:
Я не думаю, что посчитал бы любой из этих подходов безопасным для типов. Полезно, но не безопасно для типов.
Существует распространенная вариация варианта 1, которая является более эффективной, поскольку использует союзы для хранения значений в узлах списка, т.е. нет дополнительного перенаправления. Недостатком этого варианта является то, что список принимает значения только определенных типов и потенциально тратит некоторое количество памяти, если типы имеют разный размер.
Однако, можно избавиться от объединения, используя вместо него гибкий член массива, если вы готовы нарушить строгое уподобление. Код примера C99:
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct ll_node
{
struct ll_node *next;
long long data[]; // use `long long` for alignment
};
extern struct ll_node *ll_unshift(
struct ll_node *head, size_t size, void *value);
extern void *ll_get(struct ll_node *head, size_t index);
#define ll_unshift_value(LIST, TYPE, ...) \
ll_unshift((LIST), sizeof (TYPE), &(TYPE){ __VA_ARGS__ })
#define ll_get_value(LIST, INDEX, TYPE) \
(*(TYPE *)ll_get((LIST), (INDEX)))
struct ll_node *ll_unshift(struct ll_node *head, size_t size, void *value)
{
struct ll_node *node = malloc(sizeof *node + size);
if(!node) assert(!"PANIC");
memcpy(node->data, value, size);
node->next = head;
return node;
}
void *ll_get(struct ll_node *head, size_t index)
{
struct ll_node *current = head;
while(current && index--)
current = current->next;
return current ? current->data : NULL;
}
int main(void)
{
struct ll_node *head = NULL;
head = ll_unshift_value(head, int, 1);
head = ll_unshift_value(head, int, 2);
head = ll_unshift_value(head, int, 3);
printf("%i\n", ll_get_value(head, 0, int));
printf("%i\n", ll_get_value(head, 1, int));
printf("%i\n", ll_get_value(head, 2, int));
return 0;
}
Вариант 1 с использованием void * или какого-либо варианта на основе union - это то, что использует большинство программ на языке C, и он может дать вам ЛУЧШУЮ производительность, чем Стиль C ++ / макроса, предусматривающий наличие нескольких реализаций для разных типов, поскольку в нем меньше дублирования кода и, следовательно, меньше давления на icache и меньше промахов icache.
Ваш вариант 1 - это то, на что пошло бы большинство старых программистов на C, возможно, с добавлением небольшого числа 2, чтобы сократить повторяющийся набор текста, и просто , может быть, , используя несколько указателей на функции для некоторого вкуса. полиморфизм.
GLib содержит набор общих структур данных, http://www.gtk.org/
CCAN имеет набор полезных фрагментов и тому подобное http://ccan.ozlabs.org/