c - 二叉树的通用 C

Question

如何编写通用的c？

我开始编写平衡树的集合(scapegoat、splay、aa 等)并发现许多共同点。示例是下面的销毁函数。

这样的函数和类似的函数可以用 void 指针定义而不会导致“取消引用 void* 指针错误”吗？

销毁函数示例

void splay_node_linked_destroy(SplayNode **this) {
 72   if(*this == NULL) {
 73     return;
 74   }
 75   SplayNode *root = (*this)->root, *previous, *next;
 76   while(root) {
 77     if(previous == root->parent) {
 78       // todo use funcs for comparisons for generic
 79       if(root->left) {
 80         next = root->left;
 81       } else if(root->right) {
 82         next = root->right;
 83       } else {
 84         next = root->parent;
 85       }
 86     } else if(previous == root->left) {
 87       if(root->right) {
 88         next = root->right;
 89       } else {
 90         next = root->parent;
 91       }
 92     } else {
 93       next = root->parent;
 94     }
 95     previous = root;
 96     if(next == root->parent) {
 97       splay_node_destroy(&root);
 98       // todo use callback here to make generic
 99     }
100     root = next;
101   }
102 }

Answer 1

实际上，编写处理给定算法的“任意”(通用)数据类型的 C 函数是完全可能的，而且相当容易。

一个技巧是使用 void 指针并以这样的方式设计 API，即使用包装函数将指针转换为其实际类型，从而受益于与 C 一样多的类型检查和安全性将允许。唯一困难的部分是编译器通常不会帮助您将类型信息传递给实现，尽管某些编译器确实支持 typeof() 扩展，这使得编写包装宏来执行以下操作成为可能:适合你的工作。

一些示例:

此示例似乎按照我建议的方式使用了 typeof():https://github.com/troydhanson/uthash/tree/master/src

这是一个有趣的基于预处理器宏的库，其灵感来自标准模板库:http://sglib.sourceforge.net/

这可能是 C 中泛型类型的泛型算法最完整的示例之一，尽管它有点丑陋且非常冗长，而且可能效率不高:http://home.gna.org/gdsl/

这个答案提供了很好的建议，尽管它使用嵌入式union而不是void指针。如果您提前知道所有可能的数据类型， union 是理想的选择:
https://stackoverflow.com/a/2891570/816536

从通用数据结构中构建高级结构(如列表)的另一种有趣的方法可能被描述为由内而外的技术(我也喜欢这个!)。我认为这种由内而外技术的规范实现可以在 4.4BSD queue(3) 中找到。和 tree(3)这里有一些更易读的解释和示例的宏:

• http://unixjunkie.blogspot.ca/2006/12/lists-and-queues.html
• http://blog.jasonish.org/2006/08/19/tailq-example/
• http://hackab.it/2014/01/generic-linked-list-in-c/

这个答案描述了一种严重依赖于预处理器的技术，尽管它要求您提前知道所有对象类型是什么，或者强制用户为其特定数据类型编写中间 header :https://stackoverflow.com/a/10430893/816536

另请参阅这些答案:

• https://stackoverflow.com/a/668567/816536
• https://stackoverflow.com/a/13225017/816536
• https://stackoverflow.com/a/28139957/816536
• https://stackoverflow.com/a/649673/816536