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函数一样

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;
}