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。

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

Answer 2

使用混合风格；例如不要让数据成为节点的一部分，而是让节点成为数据的一部分：

struct avl_node {
    struct avl_node *parent;
    struct avl_node *left;
    struct avl_node *right;
};

struct person {
    char const *name;
    struct avl_node node;
};

struct animal {
    struct avl_node node;
    int dangerousness;
};

animal 的构造函数类似于

struct animal *animal_create(double d)
{
    struct animal *animal = malloc(sizeof *animal);

    *animal = (struct animal) {
        .node = AVL_NODE_INIT(),
        .dangerousness = d,
    };

    return animal;
}

通用的 AVL 树操作看起来像

void avl_tree_insert(struct avl_node **root, struct avl_node *node, 
                     int (*cmp)(struct avl_node const *a, struct avl_node const *b))
{
    /* .... */
}

和一个 cmp 函数用于 animal like

int animal_cmp(struct avl_node const *a_, struct avl_node const *b_)
{
     struct animal const *a = container_of(a_, struct animal, node);
     struct animal const *b = container_of(b_, struct animal, node);

     return a->dangerousness - b->dangerousness;
}

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

Best practice for generic data structure implementation in C

c

data-structures

avl-tree