具有宏的类型安全的通用容器

Question

我正在尝试使用宏在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 */ 

Answer 1

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

您不能以一种完全局限于头文件的方式定义具有宏的真正通用的类型安全容器模板.标准预处理器无法"推送"和"弹出"您需要的宏分配,以便通过嵌套和连续的扩展上下文保持其完整性.一旦你尝试通过定义容器的T容器来吃自己的狗粮,你就会遇到嵌套的上下文.

事情可以做,因为我们将看到,但作为@immortal表明,它需要生成独特.h和.c文件,你需要的T每个值.例如,您可以list_type.inl在内联文件中定义一个完全通用的T列表,例如,然后包含list_type.inl在每对小型设置包装中 - list_float.h并且list_float.c- 将分别定义和实现列表 - 浮动容器.类似地,对于list-of-int,list-of-list-of-float,list-of-vector-of-list-of-double,等等.

一个示意图将清楚地表明.但首先要完全了解自己吃狗食的挑战.

将这样的二阶容器视为一个列表的列表.我们希望能够通过为我们的宏列表T解决方案设置T = list-of-thingummy来实例化这些.但绝不是list-of-thingummy将成为POD数据类型.无论list-of-thingummy是我们自己的dogfood还是别人的,它都将是一个生活在堆上的抽象数据类型,并通过一个typedef-ed指针类型表示给它的用户.或者至少,它将在堆上保留动态组件.无论如何,不​​是POD.

这意味着我们的T列表解决方案仅仅被告知T = list-of-thingummy是不够的.还必须告诉T是否需要非POD复制构造和破坏,如果是,则如何复制构造和销毁它.用C表示,这意味着:

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

• 毁灭:如何破坏给定地址的T.

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

接下来,假设除了list-of-T之外,我们还希望为T-set或T-map-to-T2提供模板.这些按键排序的数据类型添加了另一个参数,我们必须为T或T1的任何非POD值插入,即如何订购密钥类型的任何两个对象.实际上,对于任何memcmp()不能执行的关键数据类型,我们都需要该参数.

注意到,我们将坚持原理图示例中更简单的T列表问题; 为了进一步简化,我将忘记任何constAPI 的可取性.

对于这个和任何其他模板容器类型,我们需要一些令牌粘贴宏,它们可以方便地组合函数和类型的标识符,以及可能的其他实用程序宏.例如,这些都可以放在标题中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没有针对mutliple包含的宏保护.您希望每次看到它时至少包含其中的一部分 - 至少是模板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是唯一的选择,它可以通过这种方式完成.

Answer 2

你为什么不使用图书馆呢？我喜欢使用 GLib，但我讨厌代码中的 void 指针，为了获得 GLib 提供的数据类型的类型安全版本，我编写了一些非常简单的宏：

http://pastebin.com/Pc0KsadV

如果我想要一个 Symbol* 列表（假设它是我之前定义的类型），我只需要：

GLIST_INSTANCE(SymbolList, Symbol*, symbol_list);

如果您不想为简单的链表使用整个库（这有点大材小用），请实现一个处理 void* 的列表并创建一些函数来封装并进行正确的类型转换。