c - C语言中通用数据结构实现的最佳实践

Question

在我用 C 语言实现通用数据结构的冒险经历中，我遇到了一个进退两难的问题。例如，在下面的代码中:

void add_something(avl_tree_t * my_tree) {
        int new_element = 123;

        avl_insert(my_tree, (void*)&new_element);
}

int main() {
        avl_tree_t * my_tree = avl_create();

        add_something(my_tree);

        // do stuff

        avl_print(my_tree, function_that_prints_ints);

        exit(0);
}

其中avl_insert定义为

void avl_insert(avl_tree_t * tree, void * data) {
        avl_node_t * new_node = malloc(sizeof(struct avl_node));

        new_node->data = data;
        // do tree balancing stuff
}

为了让我的通用插入函数起作用，我必须向它传递一个 void * 项目来存储。但是，为了让它工作，在这种情况下，我需要传入我要添加的新 int 项目的地址，这样我就可以将它取消引用到 void *。如果我没记错的话，当我们返回 main 函数时，我存储新元素的内存地址将被泄露。

我研究解决这个问题的一种方法是将我存储在树中的东西的大小作为参数传递给 avl_create，然后为每个元素的副本分配内存我插入。这是可行的，因为您不需要原始地址或添加的任何值。

另一件可行的事情是只在单个函数的范围内使用数据结构，这显然是不可行的。

我的问题是:将静态分配的数据存储在通用数据结构中的最佳方式是什么，无论是基本的 C 类型还是用户创建的结构？

提前谢谢你。

Answer 1

要存储指向具有自动存储持续时间的数据的指针，是的，您必须知道容器中元素的大小并分配和复制指向的数据。

最简单的方法是在所有情况下都只进行分配和复制，可选地使用用户指定的 clone() 或 create() 函数进行深度复制，如果必要的。这还需要使用用户指定的 destroy() 函数来正确处理副本(如有必要，同样如此)。

为了能够避免分配，你必须有某种状态变量，让你知道容器是否应该分配，或者只是复制指针值本身。

请注意，这应该适用于容器 对象，而不适用于单个节点或元素。如果容器以一种或另一种方式存储数据，它应该以这种方式存储所有数据。参见 Principle of Least Astonishment .

这是更复杂的方法，因为您必须确保使用正确的过程来根据状态变量添加和删除元素。通常只需确保您永远不会传递指向具有自动存储持续时间的值的指针，这通常要简单得多。