如何在释放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 datan");
    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 NODEn");
    free(t);
}

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

Answer 1

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

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

更改这些行：

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

至

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

尽管我不确定你会提供什么作为ngram。可能会传入原件。

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