# tsgds **Repository Path**: bds123/tsgds ## Basic Information - **Project Name**: tsgds - **Description**: C中如何编写类型安全的泛型？作者：Daniel Hooper，原文：https://danielchasehooper.com/posts/typechecked-generic-c-data-structures/ - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2025-07-03 - **Last Updated**: 2025-07-03 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README ## 我用 C 语言编写类型安全的泛型数据结构

2025年6月25日・8分钟阅读

我使用一种鲜为人知的技术 1，在 C 语言中编写类型安全的通用数据结构。该技术通过联合体(union)将类型信息与通用数据结构关联，具体细节稍后会展开说明。这种方法适用于任何类型的数据结构：映射、数组、二叉树...但本文将通过实现基础链表来阐述核心思想。考虑到许多人甚至不知道 C 语言完全可以实现泛型编程，我决定从简单概念开始逐步深入：

typedef struct {
    int value;
} Foo;
    
List(int) int_list = {0};
list_prepend(&int_list, 3);

List(Foo) foo_list = {0};
list_prepend(&foo_list, (Foo){ 5 });
list_prepend(&foo_list, (Foo){ 3 });

// this won't compile, which is good!
// list_prepend(&foo_list, 7); 

list_for(item, &foo_list) {
    // `item` is of type `Foo *`
    printf("%i\n", item->value);
}

泛型编程第0级：通用头文件

虽然我对此方法颇有微词 2，但仍有必要与文末介绍的技术进行对比。其实现原理是：在头文件中用宏定义类型来编写数据结构，然后通过 #include 指令多次引入该头文件——每个使用该数据结构的类型各引入一次。

点击查看代码

list.h

#ifndef T
#error "T must be defined before including this header"
#endif

#define _CONCAT(a, b) a##b
#define CONCAT(a, b) _CONCAT(a, b)

#define NODE_TYPE CONCAT(T, ListNode)
#define PREPEND_FUNC CONCAT(T, _list_prepend)

typedef struct NODE_TYPE NODE_TYPE;
struct NODE_TYPE {
    NODE_TYPE *next;
    T data;
};

void PREPEND_FUNC(NODE_TYPE **head, T data) {
    NODE_TYPE *node = malloc(sizeof(*node));
    node->data = data;
    node->next = *head;
    *head = node;
}

#undef T
#undef _CONCAT
#undef CONCAT
#undef NODE_TYPE
#undef PREPEND_FUNC

main.c

typedef struct {
    int a;
} Foo;

typedef struct {
    char *str;
    double num;
} Bar;

#define T Foo
#include "list.h"

#define T Bar
#include "list.h"

FooListNode *foo_head = NULL;
Foo_list_prepend(&foo_head, (Foo){1})

BarListNode *bar_head = NULL;
Bar_list_prepend(&bar_head, (Bar){"hello", 5.4})

尽管这种方法确实具备泛型和类型安全的特性，但存在明显缺陷：

泛型第一层：void *

另一种实现数据结构泛型化的方式是使用 void *。虽然这种方式不具备类型安全性，但这个问题我们稍后会解决。

typedef struct ListNode ListNode;
struct ListNode {
    ListNode *next;
    void *data;
};

void list_prepend(ListNode **head, void *data) {
    ListNode *node = malloc(sizeof(*node));
    node->data = data;
    node->next = *head;
    *head = node;
}

注：为便于理解此处使用 malloc，但我强烈推荐改用内存池（Arenas）。相关视频讲解和文章可供参考。

从内存和性能角度看，将 ListNode 与其 data 分开分配并不理想。这导致每个节点需要两次分配（本可一次完成），data 指针不必要地占用内存，且在遍历链表时每个节点可能引发两次缓存失效：一次获取下一节点，一次获取其数据。我们可以通过以下方式解决这些问题...

泛型方案第二阶：内联存储

我们不再存储指向节点数据的指针，而是使用柔性数组成员将数据直接存储在节点内部。为此，我们进行单次分配，其大小足以容纳节点及其存储的类型 3：

typedef struct ListNode ListNode;
struct ListNode {
    ListNode *next;
    char data[]; // glossing over some padding/alignment details here
};

void list_prepend(ListNode **head, 
                 void *data, 
                 size_t data_size) 
{
    ListNode *node = malloc(sizeof(*node) + data_size);
    memcpy(node->data, data, data_size);
    node->next = *head;
    *head = node;
}

void main() {
    ListNode *foo_list = NULL;
    Foo foo = {5};
    list_prepend(&foo_list, &foo, sizeof(foo));
}

现在 next 指针和 data 的实际内容在内存中相邻存放，解决了 void * 方案的问题。遗憾的是现在必须传递尺寸参数，但我们将在下一节解决这个问题

若想避免使用 memcpy 并直接初始化节点内存，可通过 list_alloc_front 函数实现：

void *list_alloc_front(ListNode **head, size_t data_size)  {
    ListNode *node = malloc(sizeof(*node) + data_size);
    node->next = *head;
    *head = node;
    return node->data;
}

Foo *new_foo = list_alloc_front(&foo_list, sizeof(*new_foo));
new_foo->value = 5;

泛型第三级：类型检查

大家最期待的部分来了：如何在尝试向链表添加错误类型时让编译器报错。我找到的方法是使用带有参数化类型 payload 成员的联合体：

#define List(type) union { \
    ListNode *head; \
    type *payload; \
}

List(Foo) foo_list = {0};
List(int) int_list = {0};

这如何帮助我们？我们可以使用三元运算符强制 item 参数与链表的 payload 类型相同：

// Note: leading underscore add to the 
// function name since only the macro should call it
void _list_prepend(ListNode **head, 
                 void *data, 
                 size_t data_size);

#define list_prepend(list, item) \
    _list_prepend(&((list)->head), \
                  (1 ? (item) : (list)->payload), \
                  sizeof(*(list)->payload)) 
               
List(Foo) *foo_list = NULL;
Bar bar = {5, 6};
list_prepend(&foo_list, &bar); // error!

该宏还会自动处理传递项目大小的操作！这是 Clang 编译器在添加错误类型时产生的错误提示：

error: pointer type mismatch ('Foo *' and 'Bar *') [-Werror,-Wpointer-type-mismatch]
   38 |     list_prepend(&foo_list, &bar);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
note: expanded from macro 'list_prepend'
   15 |     _list_prepend(&((list)->head), (1 ? (item) : (list)->payload), sizeof(*(list)->payload))
      |

宏的名声不太好，但我认为这相当可以理解。需要注意几点：payload 在运行时永远不会被使用，它仅存在于编译时的类型信息中。使用联合体能让 payload 不占用任何内存。

如果你正在编写需要返回指向包含数据的指针的泛型函数，可以使用 __typeof__() 将返回类型从 void * 转换为数据结构的 payload 类型。__typeof__() 在三大 C 编译器（clang、gcc 以及 19.39 版本后的 msvc）中都得到支持。


#define list_alloc_front(list) \
    (__typeof__((list)->payload))_list_alloc_front(&(list)->head, sizeof(*(list)->payload))
    
void *_list_alloc_front(ListNode **head) {...}

如果出于某些原因你不喜欢使用三元运算符来确保两种类型相同，本文的旧版本曾采用过另一种技术：

阅读旧技术方案

我们可以使用 __typeof__(foo_list.payload) 来获取链表包含的类型。我们将编写一个 list_prepend 宏，它会调用带有类型转换函数签名的 _list_prepend，这样 void * 参数就能对应链表的 payload 类型

// Note: I added a leading underscore to the 
// function name since only the macro should call it
void _list_prepend(ListNode **head, 
                 void *data, 
                 size_t data_size);

#define list_prepend(list, item) \
    /* cast function type */ \
    ((void (*)(ListNode **, \
               __typeof__((list)->payload), \
               size_t))_list_prepend)  \
               /* call function */ \
               (&((list)->head), item, sizeof(*(list)->payload)) 
               
List(Foo) *foo_list = NULL;
Bar bar = {5};
list_prepend(&foo_list, &bar); // error!

从技术上讲，调用类型转换函数指针属于未定义行为，但在现代编译器针对现代平台编译时，实践中没有问题

旧版编译器上的 typeof

__typeof__() 在 C23 之前是可选扩展，直到 C23 才成为 C 标准的一部分。虽然 Clang 和 gcc 早已支持该特性，但某些编译器（如 19.39 版本前的 msvc）并不支持。要让这项技术在这些编译器上生效，可以使用三元运算符替代 typeof

#define List(type) struct { \
    ListNode *head; \
    type *payload; \
}

#define list_prepend(list, item) \
    _list_prepend(&((list)->head), (1 ? (item) : (list)->payload), sizeof(*(list)->payload))

通过 payload 赋值也可以实现类型安全的返回操作，但具体细节留给读者作为练习。#


传递参数

2025 年末之前发布的 C 编译器有个恼人的问题 4：它们不认为这两个变量属于相同类型：

List(Foo) a;
List(Foo) b = a; // error

void my_function(List(Foo) list);
my_function(a); // error: incompatible type

尽管变量具有完全相同的类型定义，但由于是两个独立的定义 ，编译器仍会报错。使用 typedef 可以避免该问题：

typedef List(Foo) ListFoo; // this makes it all work

ListFoo a;
ListFoo b = a; // ok

void my_function(ListFoo list);
my_function(a); // ok

List(Foo) local_foo_list; // still works

结论

这适用于任何类型的数据结构，即使是像哈希表这样具有多个关联类型的数据结构：

typedef struct {
    ...
} MapInternal;

#define Map(key_type, value_type) union { \
    MapInternal map; \
    key_type *key; \
    value_type *value; \
}

关于 list_for 宏的具体实现等更多细节，请参阅此处代码

感谢 Martin Fouilleul 鼓励我完成这篇搁置数月的文章，并对初稿提供了宝贵意见。

  1. stb_ds.h 虽然实现了类型安全的通用数据结构，但其采用的技术不如本文介绍的方法通用——它仅适用于通过 C 数组实现的数组和映射表。编译器仅在赋值给该 C 数组时捕获部分类型错误，而非在将值作为参数传递给泛型函数时捕获。例如 struct {int a; int b;} baz; STBDS_ADDRESSOF(baz, 5) 能通过编译，但实际上你期望这里应该报类型错误。 ↩︎

  2. 若需编写需要类型特定代码生成的泛型函数（如从同一源码生成 add_int 和 add_double），此方案更具优势。你还可以通过其他方式巧妙运用 C 语言特性实现类型特定行为，例如针对哈希函数的设计。 ↩︎

  3. 关于 data 成员涉及的字节对齐、填充和大小计算等细节在此不做赘述，若您对此不熟悉，建议另行查阅相关资料。 ↩︎

  4. 由于规则变更 ，GCC 15 和 2025 年后续发布的 Clang 编译器将把结构相同的类型视为同一类型 ↩︎

❖
获取我的下一篇文章通知：
更多 Daniel 的文章