Типовые безопасные универсальные контейнеры с макросами
Я пытаюсь сделать типобезопасный общий связанный список в C, используя макросы. Это должно работать аналогично тому, как шаблоны работают в C++. Например,
LIST(int) *list = LIST_CREATE(int);
Моя первая попытка была для #define LIST(TYPE) (макрос, который я использовал выше), чтобы определить struct _List_##TYPE {...}, Это, однако, не сработало, потому что структура будет переопределяться каждый раз, когда я объявляю новый список. Я исправил проблему, выполнив это:
/* You would first have to use this macro, which will define
the `struct _List_##TYPE`... */
DEFINE_LIST(int);
int main(void)
{
/* ... And this macro would just be an alias for the struct, it
wouldn't actually define it. */
LIST(int) *list = LIST_CREATE(int);
return 0;
}
/* This is how the macros look like */
#define DEFINE_LIST(TYPE) \
struct _List_##TYPE \
{ \
... \
}
#define LIST(TYPE) \
struct _List_##TYPE
Но другая проблема заключается в том, что, когда у меня есть несколько файлов, которые используют DEFINE_LIST(int)Например, и некоторые из них включают друг друга, тогда все равно будет несколько определений одной и той же структуры. Есть ли способ сделать DEFINE_LIST проверить, была ли структура уже определена?
/* one.h */
DEFINE_LIST(int);
/* two.h */
#include "one.h"
DEFINE_LIST(int); /* Error: already defined in one.h */
6 ответов
Я решил эту проблему в C до того, как C++ приобрел шаблоны, и у меня все еще есть код.
Вы не можете определить действительно универсальный типобезопасный шаблон контейнера T с макросами так, чтобы он полностью ограничивался заголовочными файлами. Стандартный препроцессор не предоставляет средств для "проталкивания" и "выталкивания" макрокоманд, которые вам потребуются, чтобы сохранить их целостность через вложенные и последовательные контексты расширения. И вы столкнетесь с вложенным контекстом, как только вы попытаетесь съесть свою собачью еду, определив контейнер из контейнеров.
Это можно сделать, как мы увидим, но, как подсказывает @immortal, это влечет за собой .h а также .c файлы для каждого значения T, которое вам требуется. Вы можете, например, определить полностью общий список T с макросами во встроенном файле, скажем, list_type.inl, а затем включить list_type.inl в каждой паре небольших упаковочных комплектов - list_float.h а также list_float.c - соответственно будет определять и реализовывать контейнер list-of-float. Аналогично для list-of-int, list-of-list-of-float, list-of-vector-of-list-of-double и так далее.
Схематичный пример прояснит все. Но сначала просто получите полное представление о том, как съесть собаку.
Рассмотрим такой контейнер второго порядка как list-lists-of-thingummy. Мы хотим иметь возможность создавать их экземпляры, устанавливая T = list-of-thingummy для нашего макроса решения list-of-T. Но ни в коем случае список вещей не будет типом данных POD. Независимо от того, является ли list-thingummy нашим собственным собачьим кормом или чьим-либо еще, это будет абстрактный тип данных, который живет в куче и представляется его пользователям через тип указателя typedef-ed. Или, по крайней мере, динамические компоненты будут храниться в куче. В любом случае, не POD.
Это означает, что для нашего решения list-of-T недостаточно просто сказать, что T = list-of-thingummy. Также необходимо указать, требуется ли для T создание и уничтожение без POD, и если да, то как его создать и уничтожить. В терминах C это означает:
Конструкция копирования: Как создать копию данного T в области T-размера незафиксированной памяти, учитывая адрес такого региона.
Уничтожение: Как уничтожить Т по заданному адресу.
Мы можем обойтись без знания конструкции или конструкции по умолчанию из не-T-параметров, поскольку мы можем разумно ограничить наше решение list-of-T ограничением объектов, скопированных из предоставленных пользователем оригиналов. Но мы должны их скопировать, и мы должны избавиться от наших копий.
Далее, предположим, что мы стремимся предложить шаблон для набора-T или map-of-T1-to-T2, в дополнение к list-of-T. Эти упорядоченные по ключу типы данных добавляют еще один параметр, который мы должны будем подключить для любого не POD-значения T или T1, а именно, как упорядочить любые два объекта типа ключа. Действительно, нам понадобится этот параметр для любого ключевого типа данных, для которого memcmp() не буду делать
Отметив это, мы остановимся на более простой задаче list-of-T для схематического примера; и для дальнейшей простоты я забуду желательность любого const API.
Для этого и любого другого типа контейнера шаблона нам понадобятся несколько макросов для вставки токенов, которые позволят нам удобно собирать идентификаторы функций и типов, а также, возможно, другие служебные макросы. Все это может идти в заголовке, скажем macro_kit.h, такие как:
#ifndef MACRO_KIT_H
#define MACRO_KIT_H
/* macro_kit.h */
#define _CAT2(x,y) x##y
// Concatenate 2 tokens x and y
#define CAT2(x,y) _CAT2(x,y)
// Concatenate 3 tokens x, y and z
#define CAT3(x,y,z) CAT2(x,CAT2(y,z))
// Join 2 tokens x and y with '_' = x_y
#define JOIN2(x,y) CAT3(x,_,y)
// Join 3 tokens x, y and z with '_' = x_y_z
#define JOIN3(x,y,z) JOIN2(x,JOIN2(y,z))
// Compute the memory footprint of n T's
#define SPAN(n,T) ((n) * sizeof(T))
#endif
Теперь к схематической структуре list_type.inl:
//! There is intentionally no idempotence guard on this file
#include "macro_kit.h"
#include <stddef.h>
#ifndef INCLUDE_LIST_TYPE_INL
#error This file should only be included from headers \
that define INCLUDE_LIST_TYPE_INL
#endif
#ifndef LIST_ELEMENT_TYPE
#error Need a definition for LIST_ELEMENT_TYPE
#endif
/* list_type.inl
Defines and implements a generic list-of-T container
for T the current values of the macros:
- LIST_ELEMENT_TYPE:
- must have a definition = the datatype (or typedef alias) for \
which a list container is required.
- LIST_ELEMENT_COPY_INITOR:
- If undefined, then LIST_ELEMENT_TYPE is assumed to be copy-
initializable by the assignment operator. Otherwise must be defined
as the name of a copy initialization function having a prototype of
the form:
LIST_ELEMENT_TYPE * copy_initor_name(LIST_ELEMENT_TYPE *pdest,
LIST_ELEMENT_TYPE *psrc);
that will attempt to copy the LIST_ELEMENT_TYPE at `psrc` into the
uncommitted memory at `pdest`, returning `pdest` on success and NULL
on failure.
N.B. This file itself defines the copy initializor for the list-type
that it generates.
- LIST_ELEMENT_DISPOSE
If undefined, then LIST_ELEMENT_TYPE is assumed to need no
destruction. Otherwise the name of a destructor function having a
protoype of the form:
void dtor_name(LIST_ELEMENT_TYPE pt*);
that appropriately destroys the LIST_ELEMENT_TYPE at `pt`.
N.B. This file itself defines the destructor for the list-type that
it generates.
*/
/* Define the names of the list-type to generate,
e.g. list_int, list_float
*/
#define LIST_TYPE JOIN2(list,LIST_ELEMENT_TYPE)
/* Define the function-names of the LIST_TYPE API.
Each of the API macros LIST_XXXX generates a function name in
which LIST becomes the value of LIST_TYPE and XXXX becomes lowercase,
e.g list_int_new
*/
#define LIST_NEW JOIN2(LIST_TYPE,new)
#define LIST_NODE JOIN2(LIST_TYPE,node)
#define LIST_DISPOSE JOIN2(LIST_TYPE,dispose)
#define LIST_COPY_INIT JOIN2(LIST_TYPE,copy_init)
#define LIST_COPY JOIN2(LIST_TYPE,copy)
#define LIST_BEGIN JOIN2(LIST_TYPE,begin)
#define LIST_END JOIN2(LIST_TYPE,end)
#define LIST_SIZE JOIN2(LIST_TYPE,size)
#define LIST_INSERT_BEFORE JOIN3(LIST_TYPE,insert,before)
#define LIST_DELETE_BEFORE JOIN3(LIST_TYPE,delete,before)
#define LIST_PUSH_BACK JOIN3(LIST_TYPE,push,back)
#define LIST_PUSH_FRONT JOIN3(LIST_TYPE,push,front)
#define LIST_POP_BACK JOIN3(LIST_TYPE,pop,back)
#define LIST_POP_FRONT JOIN3(LIST_TYPE,pop,front)
#define LIST_NODE_GET JOIN2(LIST_NODE,get)
#define LIST_NODE_NEXT JOIN2(LIST_NODE,next)
#define LIST_NODE_PREV JOIN2(LIST_NODE,prev)
/* Define the name of the structure used to implement a LIST_TYPE.
This structure is not exposed to user code.
*/
#define LIST_STRUCT JOIN2(LIST_TYPE,struct)
/* Define the name of the structure used to implement a node of a LIST_TYPE.
This structure is not exposed to user code.
*/
#define LIST_NODE_STRUCT JOIN2(LIST_NODE,struct)
/* The LIST_TYPE API... */
// Define the abstract list type
typedef struct LIST_STRUCT * LIST_TYPE;
// Define the abstract list node type
typedef struct LIST_NODE_STRUCT * LIST_NODE;
/* Return a pointer to the LIST_ELEMENT_TYPE in a LIST_NODE `node`,
or NULL if `node` is null
*/
extern LIST_ELEMENT_TYPE * LIST_NODE_GET(LIST_NODE node);
/* Return the LIST_NODE successor of a LIST_NODE `node`,
or NULL if `node` is null.
*/
extern LIST_NODE LIST_NODE_NEXT(LIST_NODE node);
/* Return the LIST_NODE predecessor of a LIST_NODE `node`,
or NULL if `node` is null.
*/
extern LIST_NODE LIST_NODE_PREV(LIST_NODE node);
/* Create a new LIST_TYPE optionally initialized with elements copied from
`start` and until `end`.
If `end` is null it is assumed == `start` + 1.
If `start` is not NULL then elements will be appended to the
LIST_TYPE until `end` or until an element cannot be successfully copied.
The size of the LIST_TYPE will be the number of successfully copied
elements.
*/
extern LIST_TYPE LIST_NEW(LIST_ELEMENT_TYPE *start, LIST_ELEMENT_TYPE *end);
/* Dispose of a LIST_TYPE
If the pointer to LIST_TYPE `plist` is not null and addresses
a non-null LIST_TYPE then the LIST_TYPE it addresses is
destroyed and set NULL.
*/
extern void LIST_DISPOSE(LIST_TYPE * plist);
/* Copy the LIST_TYPE at `psrc` into the LIST_TYPE-sized region at `pdest`,
returning `pdest` on success, else NULL.
If copying is unsuccessful the LIST_TYPE-sized region at `pdest is
unchanged.
*/
extern LIST_TYPE * LIST_COPY_INIT(LIST_TYPE *pdest, LIST_TYPE *psrc);
/* Return a copy of the LIST_TYPE `src`, or NULL if `src` cannot be
successfully copied.
*/
extern LIST_TYPE LIST_COPY(LIST_TYPE src);
/* Return a LIST_NODE referring to the start of the
LIST_TYPE `list`, or NULL if `list` is null.
*/
extern LIST_NODE LIST_BEGIN(LIST_TYPE list);
/* Return a LIST_NODE referring to the end of the
LIST_TYPE `list`, or NULL if `list` is null.
*/
extern LIST_NODE LIST_END(LIST_TYPE list);
/* Return the number of LIST_ELEMENT_TYPEs in the LIST_TYPE `list`
or 0 if `list` is null.
*/
extern size_t LIST_SIZE(LIST_TYPE list);
/* Etc. etc. - extern prototypes for all API functions.
...
...
*/
/* If LIST_IMPLEMENT is defined then the implementation of LIST_TYPE is
compiled, otherwise skipped. #define LIST_IMPLEMENT to include this
file in the .c file that implements LIST_TYPE. Leave it undefined
to include this file in the .h file that defines the LIST_TYPE API.
*/
#ifdef LIST_IMPLEMENT
// Implementation code now included.
// Standard library #includes...?
// The heap structure of a list node
struct LIST_NODE_STRUCT {
struct LIST_NODE_STRUCT * _next;
struct LIST_NODE_STRUCT * _prev;
LIST_ELEMENT_TYPE _data[1];
};
// The heap structure of a LIST_TYPE
struct LIST_STRUCT {
size_t _size;
struct LIST_NODE_STRUCT * _anchor;
};
/* Etc. etc. - implementations for all API functions
...
...
*/
/* Undefine LIST_IMPLEMENT whenever it was defined.
Should never fall through.
*/
#undef LIST_IMPLEMENT
#endif // LIST_IMPLEMENT
/* Always undefine all the LIST_TYPE parameters.
Should never fall through.
*/
#undef LIST_ELEMENT_TYPE
#undef LIST_ELEMENT_COPY_INITOR
#undef LIST_ELEMENT_DISPOSE
/* Also undefine the "I really meant to include this" flag. */
#undef INCLUDE_LIST_TYPE_INL
Обратите внимание, что list_type.inl не имеет макро-защиты от включения мутлипа. Вы хотите, чтобы по крайней мере некоторые из них - по крайней мере, API -интерфейс шаблона - включались каждый раз, когда они видны.
Если вы прочтете комментарии вверху файла, вы сможете догадаться, как бы вы закодировали упаковочный заголовок для импорта типа контейнера list-of-int.
#ifndef LIST_INT_H
#define LIST_INT_H
/* list_int.h*/
#define LIST_ELEMENT_TYPE int
#define INCLUDE_LIST_TYPE_INL
#include "list_type.inl"
#endif
а также как вы будете кодировать заголовок переноса для импорта типа контейнера list-of-list-of-int:
#ifndef LIST_LIST_INT_H
#define LIST_LIST_INT_H
/* list_list_int.h*/
#define LIST_ELEMENT_TYPE list_int
#define LIST_ELEMENT_COPY_INIT list_int_copy_init
#define LIST_ELEMENT_DISPOSE list_int_dispose
#define INCLUDE_LIST_TYPE_INL
#include "list_type.inl"
#endif
Ваши приложения могут безопасно включать такие оболочки, например,
#include "list_int.h"
#include "list_list_int.h"
несмотря на то, что они определяют LIST_ELEMENT_TYPE противоречивыми способами, потому чтоlist_type.inl всегда #undefs все макросы, которые параметризуют тип списка, когда это делается с ними: посмотрите последние несколько строк файла.
Обратите внимание также на использование макроса LIST_IMPLEMENT, Если его не определено, когда list_type.inlанализируется, тогда выставляется только шаблон API; реализация шаблона пропускается. Если LIST_IMPLEMENT определяется, то весь файл компилируется. Таким образом, наши заголовки упаковки, не определяя LIST_IMPLEMENTИмпортируйте только API типа списка.
И наоборот для нашей упаковки исходных файлов list_int.c, list_list_int.cмы определим LIST_IMPLEMENT, После этого ничего не нужно делать, кроме как включить соответствующий заголовок:
/* list_int.c */
#define LIST_IMPLEMENT
#include "list_int.h"
а также:
/* list_list_int.c*/
#include "list_int.h"
#define LIST_IMPLEMENT
#include "list_list_int.h"
Теперь в вашем приложении макросы шаблонов списков не отображаются. Ваши заголовки переноса разбираются на "реальный код":
#include "list_int.h"
#include "list_list_int.h"
// etc.
int main(void)
{
int idata[10] = {1,2,3,4,5,6,7,8,9,10};
//...
list_int lint = list_int_new(idata,idata + 10);
//...
list_list_int llint = list_list_int_new(&lint,0);
//...
list_int_dispose(&lint);
//...
list_list_int_dispose(&llint);
//...
exit(0);
}
Чтобы оснастить себя "библиотекой шаблонов C" таким образом, единственной (!) Тяжелой работой является написание .inl файл для каждого типа контейнера, который вы хотите, и проверить его очень, очень тщательно. Затем вы, вероятно, сгенерируете объектный файл и заголовок для каждой комбинации собственного типа данных и типа контейнера для готовой связи, и выбьете .h а также .c упаковщики в один миг для других типов по запросу.
Само собой разумеется, как только C++ вырастил шаблоны, мой энтузиазм потеть их таким образом испарился. Но это может быть сделано таким образом, совершенно обобщенно, если по какой-то причине C является единственным вариантом.
Вы всегда можете добавить второй аргумент DEFINE_LIST макрос, который позволит вам "назвать" список. Например:
#define DEFINE_LIST(TYPE, NAME) \
struct _List_##TYPE_##NAME \
{ \
TYPE member_1; \
struct _List_##TYPE_##NAME* next; \
}
Тогда вы можете просто сделать:
DEFINE_LIST(int, my_list);
//... more code that uses the "my_list" type
Вы просто должны ограничить себя, чтобы не использовать повторно одно и то же "имя" списка, когда два разных заголовочных файла включают друг друга, и оба используют DEFINE_LIST макро. Вы также должны ссылаться на список по имени при использовании LIST_CREATE, так далее.
При передаче списков функциям, которые вы написали, вы всегда можете создавать "универсальные" типы, в которые преобразуются пользовательские "именованные" версии. Это ни на что не должно влиять, так как фактическая информация в struct остается прежним, а тег "name" просто отличает типы от объявления, а не от двоичной точки зрения. Например, вот функция, которая принимает список объектов, которые хранят int типы:
#define GENERIC_LIST_PTR(TYPE) struct _generic_list_type_##TYPE*
#define LIST_CAST_PTR(OBJ, TYPE) (GENERIC_LIST_PTR(TYPE))(OBJ)
void function(GENERIC_LIST_PTR(INT) list)
{
//...use list as normal (i.e., access it's int data-member, etc.)
}
DEFINE_LIST(int, my_list);
int main()
{
LIST(int, my_list)* list = LIST_CREATE(int, my_list);
function(LIST_CAST_PTR(list, int));
//...more code
return 0;
}
Я знаю, что это не обязательно самая удобная вещь, но это решает проблемы с именами, и вы можете контролировать, какие версии struct _generic_list_type_XXX создаются в каком-то частном заголовочном файле, к которому другие пользователи не будут добавлять (если они не хотят делать это для своих собственных типов) ... но это будет механизм для разделения объявления и определения общего списка. тип из фактического пользовательского списка-типа.
Можно создавать универсальные и типобезопасные контейнеры с макросами. С точки зрения теории вычислений, язык (код), сгенерированный из макроразложений, может быть распознан недетерминированным автоматом с понижением, что означает, что он является не более контекстно-свободной грамматикой. Вышеупомянутое утверждение делает невозможным достижение нашей цели, так как контейнер и связанные с ним итераторы должны помнить тип, который они содержат, но это может быть сделано только с помощью контекстно-зависимой грамматики. Тем не менее, мы можем сделать некоторые трюки!
Ключ к успеху лежит в процессе компиляции, построения таблиц символов. Если тип переменной может быть распознан, когда компилятор запрашивает таблицу, и небезопасное приведение типов не происходит, то это считается безопасным для типа. Поэтому мы должны дать каждому struct специальное имя, потому что имя структуры может конфликтовать, если две или более структур объявлены на одном уровне области видимости. Самый простой способ - добавить текущий номер строки к имени структуры. Стандарт C поддерживает предопределенный макрос __LINE__ и макроконкатирование / строковое преобразование начиная с ANSI C (C89/C90).
Затем мы должны скрыть некоторые атрибуты в структуре, которую мы определили, как указано выше. Если вы хотите создать еще одну запись списка во время выполнения, поместите указатель на себя в структуре, что на самом деле решит проблему. Однако этого недостаточно. Нам может понадобиться дополнительная переменная для хранения количества записей списка, которые мы выделяем во время выполнения. Это помогает нам понять, как освободить память, когда список явно уничтожается программистами. Кроме того, мы можем воспользоваться __typeof__() расширение, которое широко используется в макропрограммировании.
Я являюсь автором OpenGC3, целью которого является создание типовых безопасных универсальных контейнеров с макросами, и вот краткий и краткий пример того, как работает эта библиотека:
ccxll(int) list; // declare a list of type int
ccxll_init(list); // initialize the list record
for (int cnt = 8; cnt-- > 0; ) //
ccxll_push_back(list, rand()); // insert "rand()" to the end
ccxll_sort(list); // sort with comparator: XLEQ
CCXLL_INCR_AUTO(pnum, list) // traverse the list forward:
printf("num = %d\n", *pnum); // access elems through iters
ccxll_free(list); // destroy the list after use
Это очень похоже на синтаксис STL. Тип списка определяется, когда list объявлен Нам не нужно беспокоиться о безопасности типов, потому что нет небезопасного приведения типов при выполнении операций со списком.
Я действительно сомневаюсь, что вы можете проверять существование и определять (структуру) в одном макросе. Поставить другой #ifndef проверить перед DEFINE_LIST(int), Это не элегантно, но делает то, что вы хотите.
Как насчет создания list_template.h файл, а затем создание list_TYPE.h файл и list_TYPE.c файл для каждого экземпляра шаблона. Конечно, они могут поставляться с надлежащими защитными устройствами. После этого вы можете включить только заголовок шаблона, но не забудьте добавить все .c файлы для процесса компиляции и компоновки, и это должно работать.
Это в основном то, что C++ делает автоматически для вас... Дублирование экземпляров...
Почему вы не используете библиотеку? Мне нравится использовать GLib, но я ненавижу указатели void в своем коде, чтобы получить безопасную от типов версию типов данных, предоставляемую GLib, я написал несколько очень простых макросов:
Если мне нужен список Symbol* (при условии, что это тип, который я определил ранее), мне просто нужно:
GLIST_INSTANCE(SymbolList, Symbol*, symbol_list);
Если вы не хотите использовать целую библиотеку (что было бы своего рода избыточным) для простого связанного списка, реализуйте список, который обрабатывает void*, и создайте некоторые функции для инкапсуляции и создания правильного приведения типов.