c - 普通 C 中类型安全的通用数据结构？

Question

与“普通的老式 C”编程相比，我进行的 C++ 编程要多得多。在纯 C 中编程时，我非常想念的一件事是类型安全的通用数据结构，它在 C++ 中通过模板提供。

为了具体起见，考虑一个通用的单向链表。在 C++ 中，定义您自己的模板类，然后为您需要的类型实例化它是一件简单的事情。

在 C 中，我可以想到几种实现通用单链表的方法:

1. 一次编写链表类型和支持过程，使用 void 指针遍历类型系统。
2. 使用必要的类型名称等编写预处理器宏，以生成数据结构和支持过程的特定类型版本。
3. 使用更复杂的独立工具为您需要的类型生成代码。

我不喜欢选项 1，因为它颠覆了类型系统，并且可能比专门的特定于类型的实现具有更差的性能。据我所知，对所有类型使用数据结构的统一表示，并转换为 void 指针/从 void 指针转换，需要一个间接的方法，而专门用于元素类型的实现可以避免这种方法。

选项 2 不需要任何额外的工具，但感觉有些笨拙，如果使用不当可能会产生严重的编译器错误。

选项 3 可以提供比选项 2 更好的编译器错误消息，因为专用数据结构代码将以扩展形式存在，可以在编辑器中打开并由程序员检查(与预处理器宏生成的代码相反)。然而，这个选项是最重量级的，是一种“穷人的模板”。我以前使用过这种方法，使用一个简单的 sed 脚本来专门化一些 C 代码的“模板化”版本。

我想用 C 而不是 C++ 来编写我 future 的“低级”项目，但一想到要为每种特定类型重写通用数据结构，我就害怕了。

人们对这个问题有什么经验？ C 中是否有不符合选项 1 的良好通用数据结构和算法库(即转换为 void 指针或从 void 指针转换，这牺牲了类型安全并增加了间接级别)？

Answer 1

选项 1 是我所见的大多数通用容器的 C 实现所采用的方法。 Windows 驱动程序包和 Linux 内核使用宏允许将容器的链接嵌入结构中的任何位置，宏用于从指向链接字段的指针获取结构指针:

• list_entry() macro in Linux
• CONTAINING_RECORD() macro in Windows

选项 2 是 BSD 的 tree.h 和 queue.h 容器实现所采取的方法:

• http://openbsd.su/src/sys/sys/queue.h
• http://openbsd.su/src/sys/sys/tree.h

我认为这些方法中的任何一种都不是类型安全的。有用，但类型不安全。