带有宏的类型安全的通用容器 [英] Type-safe generic containers with macros

问题描述

我正在尝试使用宏在 C 中创建一个类型安全的通用链表.它的工作方式应该类似于模板在 C++ 中的工作方式.例如，

I'm trying to make a type-safe generic linked list in C using macros. It should work similarly to how templates work in C++. For example,

LIST(int) *list = LIST_CREATE(int);

我的第一次尝试是为 #define LIST(TYPE)(我上面使用的宏)定义一个 struct _List_##TYPE {...}.但是，这不起作用，因为每次我声明一个新列表时都会重新定义该结构.我通过这样做解决了这个问题:

My first attempt was for #define LIST(TYPE) (the macro I used above) to define a struct _List_##TYPE {...}. That, however, did not work because the struct would be redefined every time I declared a new list. I remedied the problem by doing this:

/* 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 检查结构是否已经定义?

But another problem is that when I have multiple files that use DEFINE_LIST(int), for example, and some of them include each other, then there will still be multiple definitions of the same struct. Is there any way to make DEFINE_LIST check if the struct has already been defined?

/* one.h */
DEFINE_LIST(int);

/* two.h */
#include "one.h"
DEFINE_LIST(int); /* Error: already defined in one.h */ 

推荐答案

我在 C++ 获得模板之前用 C 解决了这个问题，但我仍然有代码.

I tackled this problem in C before C++ acquired templates and I still have code.

您无法使用宏定义真正通用的类型安全容器 T 模板以一种完全局限于头文件的方式.标准预处理器不提供推送"和弹出"您将要执行的宏分配的方法要求通过嵌套和顺序保持其完整性扩张的背景.一旦你遇到嵌套的上下文尝试通过定义一个 container-of-containers-of-T 来吃自己的狗粮.

You can't define a truly generic typesafe container-of-T template with macros in a way that's confined entirely to header files. The standard preprocessor provides no means of "pushing" and "popping" the macro assignments you will require so as preserve their integrity through nested and sequential contexts of expansion. And you will encounter nested contexts as soon as you try to eat your own dog food by defining a container-of-containers-of-T.

正如我们将看到的那样，事情是可以完成的，但正如@immortal 所建议的那样，它需要为您需要的每个 T 值生成不同的 .h 和 .c 文件.例如，您可以定义一个完全通用的 T 列表，其中包含宏一个内联文件，例如 list_type.inl，然后将 list_type.inl 包含在每对小型设置包装器 - list_float.h 和 list_float.c -将分别定义和实现 list-of-float 容器.相似地对于整数列表、浮点列表列表、双精度列表向量列表、等等.

The thing can be done, as we'll see, but as @immortal suggests, it entails generating distinct .h and .c files for each value of T that you require. You can, for example, define a completely generic list-of-T with macros in an inline file, say, list_type.inl, and then include list_type.inl in a each of pair of small set-up wrappers - list_float.h and list_float.c - that will respectively define and implement the list-of-float container. Similarly for list-of-int, list-of-list-of-float, list-of-vector-of-list-of-double, and so so.

一个示意性的例子会让一切都清楚.但首先要全面了解吃你自己的狗粮挑战.

A schematic example will make all clear. But first just get the full measure of the eat-your-own-dogfood challenge.

将这样一个二阶容器视为一个 list-of-lists-of-thingummy.我们想可以通过为我们的宏设置 T = list-of-thingummy 来实例化这些T 列表解决方案.但绝不会成为 POD数据类型.无论是我们自己的狗粮清单还是其他人的，它都是将是一种抽象数据类型，存在于堆上并表示为它的用户通过 typedef-ed 指针类型.或者至少，它正在发生将动态组件保存在堆上.无论如何，不​​是 POD.

Consider such a second-order container as a list-of-lists-of-thingummy. We want to be able to instantiate these by setting T = list-of-thingummy for our macro list-of-T solution. But in no way is list-of-thingummy going to be a POD datatype. Whether list-of-thingummy is our own dogfood or somebody else's, it's going to be an abstract datatype that lives on the heap and is represented to its users through a typedef-ed pointer type. Or at the very least, it is going to have dynamic components held on the heap. In any case, not POD.

这意味着我们的 list-of-T 解决方案仅仅被告知是不够的T = 物品清单.还必须告知 T 是否需要非 POD复制构造和销毁，如果是，如何复制构造和销毁一.在 C 语言中，这意味着:

This means it's not enough for our list-of-T solution just to be told that T = list-of-thingummy. It must also be told whether a T requires non-POD copy-construction and destruction, and if so how to copy-construct and destroy one. In C terms, that means:

• 复制构造:如何以 T 大小创建给定 T 的副本未提交的内存区域，给定这样一个区域的地址.

• Copy-construction: How to create a copy of a given T in a T-sized region of uncommitted memory, given the address of such a region.

销毁:如何销毁给定地址的T.

Destruction: How to destroy the T at a given address.

我们可以在不知道默认构造或构造从非 T 参数，因为我们可以合理地将 T 列表解决方案限制为包含从用户提供的原件复制的对象.但我们做必须复制它们，我们必须处理掉我们的副本.

We can do without knowing about default construction or construction from non-T parameters, as we can reasonably restrict our list-of-T solution to the containment of objects copied from user-supplied originals. But we do have to copy them, and we have to dispose of our copies.

接下来，假设我们希望为 T 集或 T1 到 T2 的映射提供一个模板，除了 T 列表.这些键序数据类型添加了另一个参数我们将不得不插入 T 或 T1 的任何非 POD 值，即如何订购键类型的任意两个对象.事实上，我们将需要该参数memcmp() 不会执行的任何键数据类型.

Next, suppose that we aspire to offer a template for set-of-T, or map-of-T1-to-T2, in addition to list-of-T. These key-ordered datatypes add another parameter we will have to plug in for any non-POD value of T or T1, namely how to order any two objects of the key type. Indeed we will need that parameter for any key datatype for which memcmp() won't do.

注意到这一点后，我们将坚持使用更简单的 list-of-T 问题来解决示意图示例；为了更简单，我会忘记可取性任何 const API.

Having noted that, we'll stick with the simpler list-of-T problem for the schematic example; and for further simplicity I'll forget the desirability of any const API.

对于这个和任何其他模板容器类型，我们需要一些标记粘贴让我们方便地组装函数和类型标识符的宏，加上可能的其他实用程序宏.这些都可以放在标题中，比如 macro_kit.h，如:

For this and any other template container type we'll want some token-pasting macros that let us conveniently assemble identifiers of functions and types, plus probably other utility macros. These can all go in a header, say macro_kit.h, such as:

#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——每次都被包含在内见过.

Note that list_type.inl has no macro-guard against mutliple inclusion. You want at least some of it - at least the template API - to be included every time it is seen.

如果您阅读文件顶部的注释，您可以猜出您将如何编码用于导入 list-of-int 容器类型的包装标头.

If you read the comments at the top of the file you can guess how you would code a wrapping header to import a list-of-int container type.

#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容器类型:

and likewise how you would code the wrapping header to import a list-of-list-of-int container type:

#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 

您的应用程序可以安全地包含此类包装器，例如

Your applications can safely include such wrappers, e.g.

#include "list_int.h"
#include "list_list_int.h"

尽管他们以相互冲突的方式定义 LIST_ELEMENT_TYPE，因为list_type.inl 总是 #undefs 所有参数化列表类型的宏完成后:查看文件的最后几行.

despite the fact the they define LIST_ELEMENT_TYPE in conflicting ways because list_type.inl always #undefs all the macros that parameterize the list-type when it's done with them: see the last few lines of the file.

还要注意宏 LIST_IMPLEMENT 的使用.如果 list_type.inl 时未定义被解析然后只暴露模板API；模板实现是跳过.如果定义了 LIST_IMPLEMENT，则编译整个文件.因此我们的包装标题，通过不定义 LIST_IMPLEMENT，只导入列表类型API.

Note too the use of the macro LIST_IMPLEMENT. If its undefined when list_type.inl is parsed then only the template API is exposed; the template implementation is skipped. If LIST_IMPLEMENT is defined then the whole file is compiled. Thus our wrapping headers, by not defining LIST_IMPLEMENT, import only the list-type API.

相反，对于我们的包装源文件 list_int.c、list_list_int.c，我们将定义 LIST_IMPLEMENT.在那之后，除了包括对应标题:

Conversely for our wrapping source files list_int.c, list_list_int.c, we will define LIST_IMPLEMENT. After that, there's nothing to do but include the corresponding header:

/* 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"

现在在您的应用程序中，不会出现列表模板宏.你的包装标头解析为真实代码":

Now in your application, no list-template macros appear. Your wrapping headers parse out to "real code":

#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 包装器其他类型按需提供.

To equip yourself with a "C template library" this way the only (!) hard work is to write the .inl file for each container type you want and to test it very, very thoroughly. You would then probably generate an object file and header for each combination of native datatype and container type for off-the-shelf linkage, and knock out the .h and .c wrappers in a jiffy for other types on demand.

不用说，C++ 模板一出，我就热血沸腾了他们就这样蒸发了.但完全可以通过这种方式完成一般来说，如果出于某种原因 C 是唯一的选择.

Needless to say, as soon as C++ sprouted templates my enthusiam for sweating them out this way evaporated. But it can be done this way, completely generically, if for some reason C is the only option.

这篇关于带有宏的类型安全的通用容器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！