CODEWITHSUNDEEP
cmemory-leakstreemallocfree
stz
stz

Reputation: 67

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

I'm trying to find out which part of my code causes memory leaks. To be more specific I already presume where it all begins but have no idea what to do to fix it. These are my structures:

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;

And functions where I use 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 prompts that something is wrong with function create_data and insert . Please help

Upvotes: 0

Views: 73

Answers (1)

kdopen
kdopen

Reputation: 8215

Valgrind is pointing to the place where the memory was allocated, not where you failed to release it.

The cuplrit is almost certainly free_tree. A tree is a recursive data-structure, which means you need to free it recursively. You are only freeing the root node.

Change these lines:

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

to 

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

though I'm not sure what you'd provide as ngram. Probably pass in the original.

The point is that you have to navigate down each branch, freeing from the bottom up before releasing the node itself.

Upvotes: 1

Related Questions