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

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

Всем привет!

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

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

Существующие библиотеки контейнеров для Си, например из состава GLib ^[2], оперируют единственным типом — нетипизированными указателями gpointer, поскольку «честное» решение этой задачи на Си возможно только с привлечением препроцессора и будет представлять собой жуткую мешанину из макросов, трудную в понимании и отладке, что продемонстрировано существующими ^[3] подобными проектами. То есть, ничего подобного по стройности и удобству контейнеров 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<int> и std::list<box> генерируются два независимых набора машинного кода).

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

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

Полный текст входного задания для генерации структуры данных типа набор (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)=%dn", IntSetSize(&set));
             printf("contains(1)==%dn", IntSetContains(&set, 1));
	IntSetDtor(&set);
	return 0;
}

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

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

Автор: fougas

Источник ^[4]