如何在 C 中释放树时找出导致内存泄漏的原因

Question

我正在尝试找出我的代码的哪一部分导致了内存泄漏。更具体地说，我已经假设一切从哪里开始，但不知道如何修复它。这些是我的结构：

typedef struct {
    char *suffix;
    int occurr;
} suff_t;

typedef struct {
    char **prefix;
    suff_t **suffix;
    int n_suff;
    int cap_suff;
} data_t;

typedef struct node {

    data_t *d;
    struct node *left, *right;

} node_t, *tree_t;

以及我使用 malloc / realloc 的函数：

tree_t insert( tree_t t, char **buf, int ngram ) {
    if( t == NULL ) {
            node_t *n = malloc( sizeof *n);
            n->d = create_data(buf, ngram);
            n->left = n->right = NULL;
            return n;
    } else if( cmp_data( t->d, buf, ngram ) > 0  ) {
            t->left = insert( t->left, buf, ngram);
            return t;
    } else if( cmp_data( t->d, buf, ngram ) < 0 ) {
            t->right = insert( t->right, buf, ngram);
            return t;
    } else { // add suffix
            insert_suffix(t->d, buf, ngram);
            return t;
    }

}


void insert_suffix(data_t *data, char **buf, int ngram) {

    int i;
    int cap;

    for(i = 0; i < data->n_suff; i++) {
            if( ! (strcmp(buf[ngram-1], data->suffix[i]->suffix)) ) {
                    data->suffix[i]->occurr++;
                    return;
            }
    }


    if(data->n_suff == data->cap_suff){ // extend table of suffixes
            cap = data->cap_suff;
            data->suffix = realloc(data->suffix, 2*cap*sizeof*data->suffix); // 
            for(i = cap; i < 2*cap; i++)
                    data->suffix[i] = malloc(sizeof(suff_t));
            data->cap_suff *= 2;
    }
            data->suffix[data->n_suff]->suffix = strdup(buf[ngram-1]);
            data->suffix[data->n_suff]->occurr = 1;
            data->n_suff++;
}

data_t * create_data(char **buf, int ngram) {

    int i;

    data_t *newdata = malloc(sizeof*newdata); // 
    newdata->prefix = malloc((ngram-1)*sizeof*newdata->prefix);

    for(i = 0; i < ngram-1; i++) // copy prefix
            newdata->prefix[i] = strdup(buf[i]);

    newdata->suffix = malloc(8*sizeof*newdata->suffix);
    for(i = 0; i < 8; i++)
            //newdata->suffix[i] = malloc(sizeof*newdata->suffix[i]);
            newdata->suffix[i] = calloc(sizeof*newdata->suffix[i], 1);

    newdata->suffix[0]->suffix = strdup(buf[ngram-1]);
    newdata->suffix[0]->occurr = 1;
    newdata->n_suff = 1;
    newdata->cap_suff = 8;

    return newdata;

}

void free_data(data_t *d, int ngram) {

    int i;
    if(d == NULL) return;
    printf("deleting data\n");

    for(i = 0; i < ngram-1; i++)
            free(d->prefix[i]);
    free(d->prefix);

    for(i = 0; i < d->cap_suff; i++) {
            free(d->suffix[i]->suffix);
            free(d->suffix[i]);
    }

    free(d->suffix);
    free(d);
}


void free_tree(tree_t t, int ngram) {

    if( t == NULL) return;
    free_data(t->d, ngram);

    free(t->left);
    free(t->right);
    printf("DELETING NODE\n");
    free(t);

}

Valgrind 提示函数 create_data 和 insert 有问题。请帮助

Answer 1

Valgrind 指向分配内存的地方，而不是你未能释放它的地方。

cuplrit 几乎可以肯定是 free_tree。树是一种递归数据结构，这意味着您需要递归释放它。您只是在释放根节点。

更改这些行：

free(t->left);
free(t->right);

到

free_tree(t->left);
free_tree(t->right);

尽管我不确定您会提供什么作为 ngram。大概传原件吧。

关键是你必须向下导航每个分支，在释放节点本身之前从下往上释放。

如何在 C 中释放树时找出导致内存泄漏的原因

How to find out what causes memory leak while freeing tree in C

c

memory-leaks

tree

malloc

free