如何释放 DAG-like 数据结构

Question

我有以下 DAG（有向无环图）数据结构：

struct dag {
    struct dag **children;  // Array of pointers to DAGs
    int n_children;         // Number of children
};

我希望这是一个 DAG 而不仅仅是一棵树，这意味着给定 DAG 的某些 children 可能是相同的。这就在删除函数中引发了一个问题：

void del(struct dag *d)
{
    if (d != NULL) {
        for(int i = 0; i < d->n_children; i++) {
            del(d->children[i]);
        }
        free(d->children);
        free(d);
    }
}

事实上，我最终释放了已经释放的东西，如下例所示（这会引发分段错误）。此代码创建两个 DAG a 和 b； a 没有 children，b 有两个 children，它们都是 a.

void main()
{
    struct dag *a, *b, **b_children;

    a = malloc(sizeof(*a));
    a->children = NULL;
    a->n_children = 0;

    b_children = malloc(sizeof(a) * 2);
    b_children[0] = a;
    b_children[1] = a;

    b = malloc(sizeof(*b));
    b->children = b_children;
    b->n_children = 2;

    del(b);
}

这种方法有什么缺陷？我可以编写一个 del 函数来实现我想要的功能吗？

Answer 1

对于有向无环图，节点可能被多个父节点引用，这需要额外的簿记来处理生命周期。

对此有多种方法：

您可以在每个节点中添加一个引用计数，为引用该节点的每个额外指针递增它，并在指针不再引用该节点时递减它，特别是当父节点要引用该节点时被释放。引用计数很难正确可靠地实现，并且如果您的图形变得更加复杂，即：如果存在实际循环，则它不是一个完整的解决方案。
您可以维护已分配节点的链表，并在释放树时释放完整列表。这种方法允许任意节点交叉引用，但不允许释放单个节点。您一次只能释放整棵树。您仍然可以从树中删除单个节点，但它们将保持分配在列表中，直到您释放整个树。另请注意，开销是等效的：一个额外的指针而不是：每个节点需要一个整数。

根据您要用这棵树解决的问题的具体情况，一种方法可能比另一种更合适。

在这两种情况下，您都应该使用函数来分配、更新和删除节点。

这是一个带有引用计数的版本：

#include <stdio.h>
#include <stdlib.h>

static int total_dag_nodes = 0;  // for debugging

struct dag {
    int refs;
    int n_children;         // Number of children
    struct dag **children;  // Array of pointers to DAGs
};

struct dag *new_dag(int n) {
    struct dag *s = malloc(sizeof *s);
    if (s == NULL)
        return NULL;
    total_dag_nodes++;
    s->refs = 1;
    s->n_children = 0;
    s->children = NULL;
    if (n > 0) {
        s->n_children = n;
        s->children = calloc(sizeof(*s->children), n);
    }
    return s;
}

void free_dag(struct dag *s) {
    if (s && --s->refs <= 0) {
        for (int i = 0; i < s->n_children; i++)
            free_dag(s->children[i]);
        free(s);
        total_dag_nodes--;
    }
}

int set_dag_child(struct dag *s, int n, struct dag *child) {
    if (s == NULL || n < 0 || n >= s->n_children) {
        /* invalid argument */
        return -1;
    }
    struct dag *prev = s->children[n];
    s->children[n] = child;
    if (child != NULL)
        child->refs++;
    /* delay freeing the previous node to avoid freeing it
       if it is identical to new one. */
    free_dag(prev);
    return 0;
}

void print_dag(const char *name, struct dag *s) {
    printf("%s: %p", name, (void*)s);
    if (s) {
        printf(" [refs:%d] {", s->refs);
        for (int i = 0; i < s->n_children; i++)
            printf(" %p", (void*)s->children[i]);
        printf(" }");
    }
    printf(";\n");
}

int main() {
    struct dag *a = new_dag(0);
    struct dag *b = new_dag(2);

    printf("\ntotal_dag_nodes=%d\n", total_dag_nodes);
    print_dag("a", a);
    print_dag("b", b);

    set_dag_child(b, 0, a);
    set_dag_child(b, 1, a);

    printf("\ntotal_dag_nodes=%d\n", total_dag_nodes);
    print_dag("a", a);
    print_dag("b", b);

    free_dag(a);    // removes the reference from a to the first dag

    printf("\ntotal_dag_nodes=%d\n", total_dag_nodes);
    print_dag("b[0]", b->children[0]);
    print_dag("b", b);

    free_dag(b);    // should remove all references to both dags

    printf("\ntotal_dag_nodes=%d\n", total_dag_nodes);

    return 0;
}

输出：

total_dag_nodes=2                                                                                           a: 0x7f885f600000 [refs:1] { };
b: 0x7f885f600010 [refs:1] { 0x0 0x0 };

total_dag_nodes=2                                                                                           a: 0x7f885f600000 [refs:3] { };
b: 0x7f885f600010 [refs:1] { 0x7f885f600000 0x7f885f600000 };

total_dag_nodes=2                                                                                           b[0]: 0x7f885f600000 [refs:2] { };
b: 0x7f885f600010 [refs:1] { 0x7f885f600000 0x7f885f600000 };

total_dag_nodes=0

这是使用全局列表的替代方法：

#include <stdio.h>
#include <stdlib.h>

static int total_dag_nodes = 0;  // for debugging
static struct dag *dag_list;

struct dag {
    struct dag *next;       // linked list for maintenance
    int n_children;         // Number of children
    struct dag **children;  // Array of pointers to DAGs
};

struct dag *new_dag(int n) {
    struct dag *s = malloc(sizeof *s);
    if (s == NULL)
        return NULL;
    total_dag_nodes++;
    s->next = dag_list;
    dag_list = s;
    s->n_children = 0;
    s->children = NULL;
    if (n > 0) {
        s->n_children = n;
        s->children = calloc(sizeof(*s->children), n);
    }
    return s;
}

void free_dag(struct dag *s) {
    /* nothing to do because tag could be referenced elsewhere */
}

void free_all_dags(void) {
    struct dag *p;
    while ((p = dag_list) != NULL) {
        dag_list = p->next;
        free(p->children);
        free(p);
        total_dag_nodes--;
    }
}

void print_dag(const char *name, struct dag *s) {
    printf("%s: %p", name, (void*)s);
    if (s) {
        printf(" {");
        for (int i = 0; i < s->n_children; i++)
            printf(" %p", (void*)s->children[i]);
        printf(" }");
    }
    printf(";\n");
}

int main() {
    struct dag *a = new_dag(0);
    struct dag *b = new_dag(2);

    printf("\ntotal_dag_nodes=%d\n", total_dag_nodes);
    print_dag("a", a);
    print_dag("b", b);

    b->children[0] = a;
    b->children[1] = a;

    printf("\ntotal_dag_nodes=%d\n", total_dag_nodes);
    print_dag("a", a);
    print_dag("b", b);

    free_dag(a);  // individual frees do nothing

    printf("\ntotal_dag_nodes=%d\n", total_dag_nodes);
    print_dag("b[0]", b->children[0]);
    print_dag("b", b);

    free_all_dags();

    printf("\ntotal_dag_nodes=%d\n", total_dag_nodes);

    return 0;
}

输出：

total_dag_nodes=2                                                                                           a: 0x7f8d7b402650 { };
b: 0x7f8d7b402670 { 0x0 0x0 };

total_dag_nodes=2                                                                                           a: 0x7f8d7b402650 { };
b: 0x7f8d7b402670 { 0x7f8d7b402650 0x7f8d7b402650 };

total_dag_nodes=2                                                                                           b[0]: 0x7f8d7b402650 { };
b: 0x7f8d7b402670 { 0x7f8d7b402650 0x7f8d7b402650 };

total_dag_nodes=0

Answer 2

基本上，您需要实现垃圾回收算法。这有两个基本选择

引用计数

基本上，只需向每个节点添加一个引用计数，并在每次 add/remove 引用时 increment/decrement 它。当引用计数降为 0 时，释放节点。只要你没有循环（DAG 没有），这就很好用
mark/sweep

您需要一种在访问节点时标记节点的方法（如果您可以可靠地取消标记所有节点，可能只需要一个位，或者一个 'id of last traversal' 值）。然后，为了释放您的 DAG，您访问所有标记它们的节点，如果它们之前没有标记（标记阶段），则将它们添加到 'to be freed' 列表中。然后，通过 'to be freed' 列表释放它们（扫描阶段）

如何释放 DAG-like 数据结构

How to free DAG-like data structure

c

free

directed-acyclic-graphs