Жилой массив людей. Нет, серьёзно.

Холивары между ценителями Си и приверженцами его "сына" в лице C++ начались ещё до моего рождения и прекратятся разве что после смерти обоих этих языков и меня заодно. Адепты великого творения Кернигана-Ритчи до последней секунды рабочего дня готовы доказывать аксиомы приспешникам Страуструпа про вечность Си и его невероятную гибкость. Те в ответ им по-свойски советуют лучше порадоваться рабочему дню, ведь он вот-вот окажется последним – двадцать первому веку кроссплатформенный ассемблер не нужен. Распаляясь, сторонники Си приводят давно прошедшие через голову навылет миллионы тезисов "почему Си лучше C++", при этом каждый раз подчёркивая, что второй все достоинства первого растерял ещё будучи в отцовской утробе, попутно утратив лик человеческий. Обвиняемая сторона в обиде не остаётся и… а хотя постойте, о чём это я.

Я люблю Си, уважаю C++ и не переношу холивары (честно). При этом я осознаю, что в Си действительно не хватает многого, и яркий тому пример – отсутствие удобной работы с данными. В C++ эту проблему во многом решает STL и свойства самого языка. На мой студенческий взгляд, здесь особо отличается всем знакомый std::vector. Если стало интересно, как я реализовал его аналог средствами C89 – прошу под кат.

Предыстория

Вообще, с вышеописанной проблемой сталкивается наверное каждый, кто переходит на Си с языка чуть более высокого уровня (в моём случае это были FreeBASIC и Free Pascal). Проблема отсутствия давно полюбившихся Redim и SetLength() поначалу решается "в лоб кувалдой" при помощи realloc(). Потом в обнимку с опытом приходит знание, и вместо этого используется простенький самописный динамический массив. Постепенно нарастает раздражение от необходимости дублировать его код для каждого отдельного типа данных или использовать указатели здесь и там. Затем человеку попадает в руки C++ (или его аналог), человек видит STL (или его аналог), ну а дальше можно прочитать в любом бульварном романе.

Однако влюбляются в тело, но любят душу. Если человек долгое время был в счастливых отношениях с Си, если в отношениях уже появились проекты, то человеку может вполне естественно захотеться сделать объект своей любви лучше – как для него самого, так и для себя. А человек в совершенствовании всегда на что-то ориентируется.

Короче говоря, это история о том, как любовь к Си заставила меня привнести в него (неё?) пресловутый std::vector – то, что мне нравилось в C++, которым (которой?) я в одно время увлёкся.

До нас хоть потоп

Как уже было отмечено, проблема отсутствия в Си встроенного динамического массива для произвольных типов не нова и по-разному решалась немало раз.
Вот те варианты реализации вектора, которые я нашёл буквально за пять минут в Google:

https://github.com/rxi/vec
https://github.com/eteran/c-vector
https://github.com/jibsen/scv
https://github.com/robertkety/dataStructures (Ctrl+F "dynamicArray")
https://github.com/troydhanson/uthash
https://github.com/dude719/Dynamic-Array-Kernel
https://developer.gnome.org/glib/stable/glib-Arrays.html
https://www.happybearsoftware.com/implementing-a-dynamic-array

Все эти решения имеют как минимум один из следующих недостатков:

1. Реализация макросами конкретных функций управления.
   Уж сколько раз твердили миру, что использовать макросы в качестве inline-функций – затея плохая. Что ж, тогда ещё раз.
   Во-первых, при использовании макросов-функций тяжелее отслеживать и отлаживать ошибки, возникающие из-за неправильных типов аргументов.
   Во-вторых, макросы-функции не умеют ничего возвращать, если не брать во внимание извращение с передачей отдельным аргументом имени переменной для хранения результата.
   В-третьих, из-за постоянных подстановок кода из макросов-функций, которые и на inline-то мало похожи, разбухает размер единицы трансляции. Отсюда следует увеличение размера выходного исполняемого файла и прочие радости жизни.

2. Дублирование общих для любых векторов функций.
   Например, разные функции освобождения для вектора int'ов и вектора char'ов. Под капотом они будут представлять собой всего-навсего вызов функции free(), глубоко безразличной к тому, что хранится в уничтожаемом буфере, равно как и к типу указателя на него.
   Это опять же провоцирует увеличение объёма единиц трансляции, дублирование кода, а заодно и замусоривание пространства имён.

3. Работа со значениями через нетипизированные указатели и предварительно известный размер типа значения.
   Это обязывает всегда брать указатель на значение для добавления его даже в простой вектор примитивных типов (например int'ов).

4. Обозначение типа вектора как структуры.
   Самый большой недостаток, при наличии одного которого даже полное отсутствие других уже не играет роли.
   Во-первых, обращение к элементам вектора происходит через поле структуры. Для одномерного вектора это уже неудобно – стоит ли говорить о многомерных.
   Во-вторых, все поля структуры, даже технические, свободно доступны пользователю.
   Во-третьих, практически полная несовместимость между векторами разных типов.
   В-четвёртых, для создания и удаления вектора требуется 2 вызова malloc() / free() соответственно – один на структуру и один на сам буфер вектора. Как нетрудно догадаться, в случае размерности вектора вызовов будет уже .

Таким образом, вырисовывается задача создания вектора, специализируемого для любых типов данных Си и обладающего следующими возможностями:

1. Доступ к элементам вектора как к элементам обычного массива, вне зависимости от его размерности: vec[k], vec[i][j] и т.д.
2. Управление вектором с помощью обычных функций, обладающих типизированными аргументами и возвращаемым значением в отличие от макросов.
3. Отсутствие дублирующегося кода благодаря специализации только тех функций, которые принимают и/или возвращают значения пользовательского типа.
4. Отсутствие у пользователя прямого доступа к технической информации вектора.
5. Совместимость между векторами разных типов на уровне присваивания одного другому.
6. Возможность пользователю при специализации вектора указать способ передачи и возврата значений: по значению или по ссылке (через указатель).
7. Максимальная схожесть интерфейса вектора с таковым у std::vector из C++11.

Dive into C89

Заранее отвечу на вопрос, почему C89, а не хотя бы C99. Я сам очень люблю C99, но в данном случае почувствовал, что поставленную задачу можно решить и в более жёстких условиях. Как-никак, публикацию в "ненормальном программировании" надо оправдывать.

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

Однако потом мне на глаза попалась библиотека динамических строк для Си под названием Simple Dynamic Strings, написанная в своё время для Redis. Она использует другой подход: техническая информация о векторе хранится не в структуре вместе с указателем на него, а в виде заголовка прямо перед самим буфером вектора в памяти. Это позволяет оперировать вектором напрямую через типизированный указатель, при этом размещение технической информации всегда достоверно известно.

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

Таким образом мы реализовали возможности (1) и (4). Идём дальше.

Так как теперь вектор – это просто типизированный указатель, то мы, казалось бы, уже можем обобщить для разных типов векторов такие функции как, например, функцию освобождения, просто обозначив аргумент "указатель на освобождаемый вектор" как void*. Общеизвестно, что в void* можно неявно преобразовать любой другой указатель, равно как и наоборот.

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

Пункты (2) и (3) реализованы. А так как в Си нет объектов и любое значение может быть переприсвоено другой переменной буквально копированием памяти, то реализован и пункт (5). Продолжаем в том же духе.

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

• присвоение указанным элементам вектора переданного значения;
• возврат значения указанного элемента.

Для примитивных типов предпочтительнее первый вариант, тогда как для сложных структур – второй.
Ссылок а-ля C++ в Си конечно же нет, но их заменят нам указатели.

Устали от текста? вопрос риторический.
Тогда приведу для наглядности определения вариантов одних и тех же функций, принимающих/возвращающих переменные по значению и по ссылке соответственно.

gvec_error_e gvec_NAME_push( gvec_NAME_t* phandle, const TYPE value )
gvec_error_e gvec_NAME_push( gvec_NAME_t* phandle, const TYPE* value )

TYPE gvec_NAME_front( gvec_NAME_t handle )
TYPE* gvec_NAME_front( gvec_NAME_t handle )

Видно, что в обоих случаях отличие лишь в одном символе.

Уже в C89 оператор присваивания доступен для всех типов, а не только для примитивных. Это позволяет передачу и возврат по ссылке или по значению в специализируемых функциях указывать аргументами макроса-специализатора. Правда возникает резонный вопрос: а почему не указывать это одним аргументом сразу для передачи и возврата одновременно? А очень просто: возврат по значению удобнее и быстрее в случае примитивных типов, но значение может быть не определено в случае отсутствия в векторе запрошенного элемента. При возврате по ссылке в таком случае мы можем просто вернуть NULL. Короче говоря, это оставлено на усмотрение самого программиста.

В итоге реализован пункт (6). Пункт (7) можно также считать реализованным по совокупности всех предыдущих.

Заключение

Итоговая реализация библиотеки вектора на C89, готовая к практическому применению, находится здесь:

https://github.com/cher-nov/genvector (MIT License)

Конечно, статья не освещает некоторые другие, менее сложные но не менее интересные аспекты реализации, на описание которых у меня не хватило лаконичности и красноречия. Также опущены разглагольствования по поводу решений, оказавшихся в итоге неудачными, и их переосмысления. Но я уверен, что ответы на первое можно получить из кода и ReadMe в репозитории, а на второе – из истории коммитов.

Это первая моя статья на Хабре, поэтому прошу судить как можно строже. За косноязычие – особенно.

Надеюсь, это всё окажется кому-то да полезным.

Автор: cher-nov

Источник