CODEWITHSUNDEEP
cstructmemory-leaks
JNevens
JNevens

Reputation: 11982

Why does this introduce a memory leak?

I am implementing an Ant Colony Optimization for the Set Covering Problem in C. In my code, I have found a function that causes a memory leak. I am pretty sure this function is the cause of the memory leak, since I have ruled out other functions by testing. Only, I don't understand why this function introduces a memory leak.

To understand this function, I'll describe the Ant struct first. The Ant struct looks like this:

struct Ant {
    int* x;
    int* y;
    int fx;
    int** col_cover;
    int* ncol_cover;
    int un_rows;
    double* pheromone;
}

typedef struct Ant ant_t;

The pointers in this struct (such as x, y, col_cover, etc.) are initialized using malloc and freed at the end of the program. Now, the function causing the memory leak is the following:

void localSearch(ant_t* ant) {
    int improvement = 1;
    ant_t* antcpy = (ant_t*) malloc(sizeof(ant_t));
    initAnt(antcpy);
    copyAnt(ant, antcpy);
    while (improvement) {
        improvement = 0;
        for (int i = 0; i < inst->n; i++) {
            if (antcpy->x[i]) {
                removeSet(inst, antcpy, i);
                while (!isSolution(antcpy)) {
                    constructSolution(antcpy);
                }
                if (antcpy->fx < ant->fx) {
                    copyAnt(antcpy, ant);
                    improvement = 1;
                    eliminate(ant);
                } else {
                    copyAnt(ant, antcpy);
                }
            }
        }
    }
    free((void*) antcpy);
}

First, I create another instance of the Ant struct (antcpy), using the initAnt function. The copyAnt function does a deep copy of one Ant struct to another Ant struct. My reason for doing a deep copy is the following; I am changing the antcpy and then comparing it to ant. If it turns out better (antcpy->fx < ant->fx), ant is replaced by antcpy. If it turns out worse, antcpy is restored to the values of ant.

These functions are given below:

void initAnt(ant_t* ant) {
    ant->x = (int*) malloc(inst->n * sizeof(int));
    ant->y = (int*) malloc(inst->m * sizeof(int));
    ant->col_cover = (int**) malloc(inst->m * sizeof(int*));
    ant->ncol_cover = (int*) malloc(inst->m * sizeof(int));
    ant->pheromone = (double*) malloc(inst->n * sizeof(double));
    for (int i = 0; i < inst->m; i++) {
        ant->col_cover[i] = (int*) malloc(inst->ncol[i] * sizeof(int));
    }
}

void copyAnt(ant_t* from, ant_t* to) {
    to->fx = from->fx;
    to->un_rows = from->un_rows;
    for (int i = 0; i < inst->n; i++) {
        to->x[i] = from->x[i];
        to->pheromone[i] = from->pheromone[i];
    }
    for (int i = 0; i < inst->m; i++) {
        to->y[i] = from->y[i];
        to->ncol_cover[i] = from->ncol_cover[i];
        for (int j = 0; j < inst->ncol[i]; j++) {
            to->col_cover[i][j] = from->col_cover[i][j];
        }
    }
}

I don't really see why this code causes a memory leak, since I free antcpy at the end of the localSearch function. So, why does this code introduce a memory leak and how can I fix it?

Upvotes: 0

Views: 89

Answers (1)

Adrian Roman
Adrian Roman

Reputation: 531

You will have to implement a function freeAnt that before free((void*) antcpy); will release all memory that was allocated in initAnt.

void freeAnt(ant_t* ant) {
    for (int i = 0; i < inst->m; i++) {
        free(ant->col_cover[i]);
    }
    free(ant->pheromone);
    free(ant->ncol_cover);
    free(ant->col_cover);
    free(ant->y);
    free(ant->x);
}

Upvotes: 2

Related Questions