二叉树的通用 C

Question

如何编写泛型 c？

我开始编写平衡树（scapegoat、splay、aa 等）的合集，发现了很多共同点。示例是下面找到的 destroy 函数。

这样的函数和类似的函数可以用空指针定义而不导致"dereferencing void* pointer error"吗？

销毁函数示例

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

实际上，编写处理给定算法的 "arbitrary"（通用）数据类型的 C 函数是完全可能的，而且相当容易。

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

一些示例：

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

这是一个有趣的 pre-processor 基于宏的库，其灵感来自于标准模板库：http://sglib.sourceforge.net/

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

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

另一种从通用数据结构构建 high-level 结构（如列表）的有趣方法可能被描述为 inside-out 技术（我也喜欢这个！）。我认为 inside-out 技术的规范实现可以在 4.4BSD queue(3) and tree(3) 宏中找到，这里有一些更易读的解释和示例：

这个答案描述了一种严重 pre-processor 依赖的技术，尽管它要求您事先知道所有 object 类型是什么，或者强制用户编写中间 header 对于它们的特定数据类型：https://whosebug.com/a/10430893/816536

另请参阅这些答案：

Answer 2

这里是一个通用树销毁的例子：

// GenericTree.h

void genericTreeDestroy(void *treeNode,  void (*fUserFree)(void *));

// GenericTree.c
typedef struct TREE_NODE {
    struct TREE_NODE *left;
    struct TREE_NODE *right;
};
void genericTreeDestroy(struct TREE_NODE *treeNode,  void (*fUserFree)(void *))
{
    if (treeNode->left)  genericTreeDestroy(treeNode->left,  fUserFree);
    if (treeNode->right) genericTreeDestroy(treeNode->right, fUserFree);
    if (fUserFree) fUserFree(treeNode);
    free(treeNode);
}

// UserStuff.c
#include "GenericTree.h"
typedef struct MY_TREE_NODE {
    struct MY_TREE_NODE *left;
    struct MY_TREE_NODE *right;
    int some_value;
    char *name;
};
void my_freedata(struct MY_TREE_NODE *node);

void main(void)
{
    struct MY_TREE_NODE *myTree= calloc(1,sizeof(struct MY_TREE_NODE));
    myTree->name= malloc(strlen("Hello world")+1);
    genericTreeDestroy(myTree, my_freedata);
}

void my_freedata(struct MY_TREE_NODE *node)
{
    free(node->name);
}

诀窍是所有树都必须从左右成员开始。 .h 文件将 genericTreeDestroy 定义为 void * 参数，.c 文件将其定义为 struct TREE_NODE *。通过这种方式，用户可以将任何树节点类型传递给它。

接下来用户可以定义任意树节点类型（只要是左右成员），调用泛型函数销毁即可。可以给通用函数一个函数来对用户定义的节点类型进行任何清理，如果不需要则为 null。

您可以用同样的方式定义其他函数。这是一个搜索功能：

// .h
void *generic_tree_search (void *tree, void *value, int (*fUserCmp)(void *value, void *node));

// .c
void *generic_tree_search (struct TREE_NODE *treeNode, void *value, int (*fUserCmp)(void *value, void *node))
{
    while (treeNode) {
        switch (fUserCmp(value,treeNode) {
        case -1: if (treeNode->left) treeNode= treeNode->left; else return(0); break;
        case  0: return(treeNode);
        case +1: if (treeNode->right) treeNode= treeNode->right; else return(0); break;
        }
    }
    return(0);
}

二叉树的通用 C

Generic C for binary trees

c

generics

search

binary-tree

binary-search-tree