Bra*_*sen 52 c generics code-generation data-structures
我做了比"普通的旧C"编程更多的C++编程.在普通C编程时,我非常想念的一件事是类型安全的通用数据结构,它是通过模板在C++中提供的.
为了具体起见,请考虑一般的单链表.在C++中,定义自己的模板类,然后根据需要对其进行实例化是一件简单的事情.
在C中,我可以想到一些实现通用单链表的方法:
我不喜欢选项1,因为它颠覆了类型系统,并且可能比特定类型的特定实现具有更差的性能.对于所有类型使用数据结构的统一表示,并向/从void指针进行转换,据我所知,需要一个间接性,这可以通过专用于元素类型的实现来避免.
选项2不需要任何额外的工具,但感觉有些笨拙,并且在使用不当时可能会导致错误的编译器错误.
选项3可以提供比选项2更好的编译器错误消息,因为专用数据结构代码将以扩展形式存在,可以在编辑器中打开并由程序员检查(而不是由预处理器宏生成的代码).但是,这个选项是最重量级的,一种"穷人的模板".之前我使用过这种方法,使用一个简单的sed脚本来专门化一些C代码的"模板化"版本.
我想用C而不是C++来编写我未来的"低级"项目,但是为每种特定类型重写通用数据结构的想法让我感到害怕.
人们对这个问题有什么经验？C中是否存在通用数据结构和算法的良好库,这些库不与选项1一起使用(即与void指针进行转换,这会牺牲类型安全性并增加间接级别)？
Mic*_*urr 23
选项1是我看到的大多数通用容器的C实现所采用的方法.Windows驱动程序工具包和Linux内核使用宏来允许容器的链接嵌入到结构中的任何位置,宏用于从指向链接字段的指针获取结构指针:
选项2是BSD的tree.h和queue.h容器实现所采用的方法:
我不认为我认为这些方法中的任何一种都是安全的.有用,但不安全.
Dra*_*rgy 19
C与C++有着不同的美感,并且类型安全,能够在查看代码而不涉及调试器中的强制转换时始终能够看到所有内容,通常不是其中之一.
C的美丽来自于它缺乏类型安全性,在类型系统中工作以及原始的位和字节级别.正因为如此,它有一些事情可以更容易地做,而不是像语言一样,例如,可变长度的结构,使用堆栈,甚至对于大小在运行时确定的数组,等等.它也往往更简单.当你在这个较低的水平工作时,保留ABI.
所以这里有一种不同的审美形式以及不同的挑战,当你在C工作时,我建议改变思维模式.为了真正体会到这一点,我建议做很多人认为理所当然的事情,比如实现自己的内存分配器或设备驱动程序.当你在如此低的水平上工作时,你会情不自禁地将所有内容视为位和字节的内存布局,而不是附加行为的"对象".此外,在这种低级别的位/字节操作代码中可能会出现一个问题,其中C变得比C++代码更容易理解reinterpret_casts,例如,
至于你的链表示例,我建议一个链接节点的非侵入式版本(一个不需要将列表指针存储到元素类型中T,本身,允许链表逻辑和表示与T自身分离),像这样:
struct ListNode
{
struct ListNode* prev;
struct ListNode* next;
MAX_ALIGN char element[1]; // Watch out for alignment here.
// see your compiler's specific info on
// aligning data members.
};
现在我们可以像这样创建一个列表节点:
struct ListNode* list_new_node(int element_size)
{
// Watch out for alignment here.
return malloc_max_aligned(sizeof(struct ListNode) + element_size - 1);
}
// create a list node for 'struct Foo'
void foo_init(struct Foo*);
struct ListNode* foo_node = list_new_node(sizeof(struct Foo));
foo_init(foo_node->element);
要从列表中检索元素为T*:
T* element = list_node->element;
因为它是C,所以在以这种方式转换指针时没有任何类型检查,如果你来自C++背景,这可能也会给你一种不安的感觉.
这里棘手的部分是确保该成员element正确对齐您想要存储的任何类型.当您可以根据需要轻松解决问题时,您将拥有一个强大的解决方案来创建高效的内存布局和分配器.通常,这将使您只使用max alignment来处理可能看起来很浪费的所有内容,但通常情况下,如果您使用的是适当的数据结构和分配器,而这些数据结构和分配器不会为单个基础上的众多小元素支付此开销.
现在这个解决方案仍然涉及类型转换.关于这个列表节点的单独版本代码和相应的逻辑,你可以做很少的事情来处理你想要支持的每种类型的T(缺乏动态多态性).但是,它不需要您可能认为需要的额外级别的间接,并且仍然在单个分配中分配整个列表节点和元素.
在很多情况下,我会建议这种简单的方法在C中实现通用性.只需T使用长度匹配sizeof(T)并正确对齐的缓冲区替换即可.如果你有一个合理的可移植和安全的方法,你可以推广以确保正确对齐,你将有一个非常强大的方式来处理内存,通常可以提高缓存命中率,减少堆分配/解除分配的频率,需要间接,构建时间等
如果你需要更多的自动化,比如list_new_node自动初始化struct Foo,我建议创建一个你可以传递的通用类型表结构,其中包含大T是多少的信息,一个指向函数的函数指针来创建一个默认的T实例,另一个是复制T,克隆T,销毁T,比较器等.在C++中,您可以使用模板和内置语言概念(如复制构造函数和析构函数)自动生成此表.C需要更多的手动操作,但您仍然可以使用宏来减少它的样板.
如果你采用更加面向宏的代码生成路线,那么另一个有用的技巧是兑现基于前缀或后缀的标识符命名约定.例如,CLONE(Type,ptr)可以定义为返回Type##Clone(ptr),因此CLONE(Foo, foo)可以调用FooClone(foo).这是一种欺骗,可以在C中获得类似于函数重载的东西,并且在批量生成代码时很有用(当CLONE用于实现另一个宏时)或者至少复制和粘贴样板类型代码至少提高样板的均匀性.