https://danielchasehooper.com/posts/typechecked-generic-c-data-structures/

比较可惜的是，在看到这篇博客之前，我已经写完了这学期数据结构的 oj 代码了

众所周知，用 C 写非侵入式泛型容器是很坐牢的事，要么全用 void* 一顿擦除，性能不高的同时还容易写错类型，要么写一个全是 define 的头文件，根据需要什么类型就 #define T int 然后 include 一下，产生很多重复代码，而且全 define 很难 debug 或代码提示。

这篇博客给出了一个令人耳目一新的方法

效果是这样的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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,
// although passing a int to Foo is acceptable according to Foo's structure!
// list_prepend(&foo_list, 7);

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

定义容器时只需要在括号里加上类型参数，然后就获得了编译期类型检查，完全不影响运行时性能。

容器算法用的是同一个函数，不需要 list_prepend_int 和 list_prepend_foo 等等。

原理：

首先用一个柔性数组成员存数据，这是容器节点类型

1
2
3
4
typedef struct ListNode {
    struct ListNode *next, *prev;
    char data[];
} ListNode;

但这样相当于把类型擦除了，无法在编译时检查类型。为了实现类型安全，我们需要在容器中存储类型信息。

定义一个 union，存下类型信息

1
2
3
4
5
#define List(type)      \
union {                 \
    ListNode* node;     \
    type* type_info;    \
};
Example

List(int) int_list;

好了，那怎么用上这个类型信息呢？

两种方案

  1. 用三目运算符约束类型，因为三目运算符两个结果必须是 is_convertible 的
1
2
3
4
#define list_prepend(list, item) \
    list_prepend_impl(&((list)->head), \
                  (1 ? (item) : (list)->type_info), \
                  sizeof(*(list)->type_info))
Error

1
2
3
4
5
6
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))
      |

这样如果插入了一个错误类型的元素，编译器就会报错。

  1. 用 __typeof__ 扩展 强制类型转换
1
2
3
#define list_prepend(list, data) \
    list_prepend_raw(            \
        &((list)->node), &(__typeof__(*((list)->typeinfo))){data}, sizeof(*((list)->typeinfo)))

这样在类型不兼容时也会报错

由于 2025年末 前的编译器不认为两处分别定义的结构相同的匿名 union/struct 是同一个类型，如果需要传递参数或者进行赋值时，需要 typedef 出一个类型

1
2
3
4
5
6
7
8
9
10
11
typedef List(int) IntList;
void traverse(IntList* list);
int main() {
    IntList int_list = {0};
    ...
    traverse(&int_list); // ok!

    List(int) int_list_2 = {0};
    ...
    traverse(&int_list_2); // error: incompatible pointer type
}