Автоматическая генерация типизированных структур данных для Си

Если Вы программируете на Си и Вам не хватает типизированных контейнеров, которые есть в языках высокого уровня, добро пожаловать под кат:

Всем привет!

Как известно, нетривиальная программа с большой долей вероятности предполагает работу с нетривиальными структурами данных. Современные ЯП высокого уровня имеют обширные библиотеки типизированных контейнеров, несравненно упрощающих работу с ними. Однако, при падении с небес на землю на чистый Си все эти блага цивилизации оказываются недоступными. Поэтому зачастую при необходимости написать что-то на Си, возникает потребность в некоем коде, обеспечивающем обработку сложно структурированных данных.

Необходимость каждый раз заново изобретать велосипед с квадратными колесами привела мою измученную нарзаном избалованную ЯП высокого уровня душу к мысли о создании универсального генератора типизируемых структур (являющегося частью более обширного пакета AutoC), способного решить эту проблему once and for all.

Существующие библиотеки контейнеров для Си, например из состава GLib, оперируют единственным типом — нетипизированными указателями gpointer, поскольку «честное» решение этой задачи на Си возможно только с привлечением препроцессора и будет представлять собой жуткую мешанину из макросов, трудную в понимании и отладке, что продемонстрировано существующими подобными проектами. То есть, ничего подобного по стройности и удобству контейнеров STL для Си++ и коллекций Явы и Шарпа штатными средствами Си построить не получится.

В данной статье представляется альтернативный путь — автоматическая генерация требуемых структур данных по задаваемой пользователем спецификации. Полученные таким путем структуры данных, помимо собственно обеспечения строгой типизации элементов, очень наглядны и имеют простой и понятный интерфейс, что облегчает их использование.

Генератор кода написан на Руби. Подготавливаемая пользователем спецификация структур данных представляет собой Руби-скрипт. Результатом работы генератора является исходный код на Си, оформленный в виде модуля (файл заголовка и файл реализации). Файл заголовка включается в пользовательский код, использующий эти структуры; файл реализации компилируется и связывается с остальными модулями, составляющими программу.

На момент написания статьи поддерживаются следующие структуры данных:

• Вектор Vector (Си++/Ява аналоги: std::vector и java.util.ArrayList).
• Односвязный список List (ближайшие Си++/Ява аналоги представляют собой двухсвязные списки: std::list и java.util.LinkedList).
• Набор на основе хешей HashSet (Си++/Ява аналоги: std::unordered_set и java.util.HashSet).
• Отображение на основе хешей HashMap (Си++/Ява аналоги: std::unordered_map и java.util.HashMap).

Для каждой специализации контейнера создается свой независимый исходный код; собственно, это именно то, что делает Си++ «за сценой» при генерации специализаций своих шаблонных типов (например, для

std::list и std::list генерируются два независимых набора машинного кода).



Генерируемые структуры могут оперировать как типами, передаваемыми по значению, так и ссылочными типами. Для последних может быть задействовано контролируемое пользователем управление памятью, например, с совмещением имен и счетчиком ссылок, copy-on-write и т.д. Обеспечивается множество операций, ожидаемых от подобных структур данных - вставка, удаление, поиск, перебор элементов и т.д.



В качестве примера приведу простой пример работы с AutoC для создания и применения структуры данных, соответствующей типу std::unordered_set для Си++.



Полный текст входного задания для генерации структуры данных типа набор (set), оперирующего целыми числами:


require "autoc"

CodeBuilder::CModule.generate!("containers") do |m|
	m << DataStructBuilder::HashSet.new("IntSet",  {:type=>"int"})
end

Вырезка из интерфейсной части модуля для IntSet:

...
typedef struct IntSet IntSet;
struct IntSet {...}
...
void IntSetCtor(IntSet*);
void IntSetDtor(IntSet*);
void IntSetPut(IntSet*, int);
...

Полный текст тестового примера для IntSet:

#include <stdio.h>

#include "containers_auto.h"

int main(int argc, char** argv) {
	IntSet set;
	IntSetCtor(&set);
	IntSetPut(&set, 0);
	IntSetPut(&set, 1);
	IntSetPut(&set, 0);
	printf("size(set)=%d\n", IntSetSize(&set));
	printf("contains(1)==%d\n", IntSetContains(&set, 1));
	IntSetDtor(&set);
	return 0;
}

Работа над пакетом еще не завершена; основные пробелы находятся, как водится, в части документации (краткое описание генерируемых API в наличии). Тем не менее, содержательная часть уже довольно стабильна, функциональна и готова к использованию.
Более полное представление о возможностях и способах применения можно получить из тестового примера, входящего в состав пакета.

P.S.
Идеи и конструктивная критика приветствуются.