C++ memory leak, where?

Question

I'm having a problem with the code attached below. Essentially it generates a huge memory leak but I can't see where it happens.

What the code does is receiving an array of strings, called prints, containing numbers (nodes) separated by ',' (ordered by desc number of nodes), finding other compatible prints (compatible means that the other string has no overlapping nodes 0 excluded because every print contains it) and when all nodes are covered it calculates a risk function on the basis of a weighted graph. In the end it retains the solution having the lowest risk.

The problem is that leak you see in the picture. I really can't get where it comes from.

Here's the code:

#include "Analyzer.h"

#define INFINITY 999999999

// functions prototypes
bool areFullyCompatible(int *, int, string);
bool contains(int *, int, int);
bool selectionComplete(int , int);
void extractNodes(string , int *, int &, int);
void addNodes(int *, int &, string);

Analyzer::Analyzer(Graph *graph, string *prints, int printsLen) {
    this->graph = graph;
    this->prints = prints;
    this->printsLen = printsLen;
    this->actualResult = new string[graph->nodesNum];
    this->bestResult = new string[graph->nodesNum];
    this->bestReSize = INFINITY;
    this->bestRisk = INFINITY;
    this-> actualSize = -1;
}

void Analyzer::getBestResult(int &size) {

    for (int i = 0; i < bestReSize; i++)
        cout << bestResult[i] << endl;
}

void Analyzer::analyze() {

    // the number of selected paths is at most equal to the number of nodes
    int maxSize = this->graph->nodesNum;
    float totRisk;
    int *actualNodes = new int[maxSize];
    int nodesNum;
    bool newCycle = true;

    for (int i = 0; i < printsLen - 1; i++) {
        for (int j = i + 1; j < printsLen; j++) {

            // initializing the current selection
            if (newCycle) {
                newCycle = false;
                nodesNum = 0;

                extractNodes(prints[i], actualNodes, nodesNum, maxSize);
                this->actualResult[0] = prints[i];
                this->actualSize = 1;
            }

            // adding just fully compatible prints
            if (areFullyCompatible(actualNodes, nodesNum, prints[j])) {
                this->actualResult[actualSize] = prints[j];
                actualSize++;

                addNodes(actualNodes, nodesNum, prints[j]);
            }

            if (selectionComplete(nodesNum, maxSize)) {

                // it means it's no more a possible best solution with the minimum number of paths
                if (actualSize > bestReSize) {
                    break;
                }

                // calculating the risk associated to the current selection of prints
                totRisk = calculateRisk();

                // saving the best result
                if (actualSize <= bestReSize && totRisk < bestRisk) {
                    bestReSize = actualSize;
                    bestRisk = totRisk;
                    for(int k=0;k<actualSize; k++)
                        bestResult[k] = actualResult[k];
                }
            }
        }

        newCycle = true;
    }
}

float Analyzer::calculateRisk() {

    float totRisk = 0;
    int maxSize = graph->nodesNum;
    int *nodes = new int[maxSize];
    int nodesNum = 0;


    for (int i = 0; i < actualSize; i++) {
        extractNodes(this->actualResult[i], nodes, nodesNum, maxSize);

        // now nodes containt all the nodes from the print but 0, so I add it (it's already counted but misses)
        nodes[nodesNum-1] = 0;

        // at this point I use the graph to calculate the risk
        for (int i = 0; i < nodesNum - 1; i++) {
            float add = this->graph->nodes[nodes[i]].edges[nodes[i+1]]->risk;
            totRisk += this->graph->nodes[nodes[i]].edges[nodes[i+1]]->risk;
            //cout << "connecting " << nodes[i] << " to " << nodes[i + 1] << " with risk " << add << endl;
        }
    }

    delete nodes;
    return totRisk;
}

// -------------- HELP FUNCTIONS--------------

bool areFullyCompatible(int *nodes, int nodesNum, string print) {

    char *node;
    char *dup;
    int tmp;
    bool flag = false;

    dup = strdup(print.c_str());
    node = strtok(dup, ",");


    while (node != NULL && !flag)
    {
        tmp = atoi(node);

        if (contains(nodes, nodesNum, tmp))
            flag = true;

        node = strtok(NULL, ",");
    }

    // flag signals whether an element in the print is already contained. If it is, there's no full compatibility

    if (flag)
        return false;

    delete dup;
    delete node;

    return true;
}

// adds the new nodes to the list
void addNodes(int *nodes, int &nodesNum, string print) {

    char *node;
    char *dup;
    int tmp;

    // in this case I must add the new nodes to the list
    dup = strdup(print.c_str());
    node = strtok(dup, ",");

    while (node != NULL)
    {
        tmp = atoi(node);

        if (tmp != 0) {
            nodes[nodesNum] = tmp;
            nodesNum++;
        }

        node = strtok(NULL, ",");
    }

    delete dup;
    delete node;
}

// verifies whether a node is already contained in the nodes list
bool contains(int *nodes, int nodesNum, int node) {
    for (int i = 0; i < nodesNum; i++)
        if (nodes[i] == node)
            return true;
    return false;
}

// verifies if there are no more nodes to be added to the list (0 excluded)
bool selectionComplete(int nodesNum, int maxSize) {
    return nodesNum == (maxSize-1);
}

// extracts nodes from a print add adds them to the nodes list
void extractNodes(string print, int *nodes, int &nodesNum, int maxSize) {

    char *node;
    char *dup;
    int idx = 0;
    int tmp;

    dup = strdup(print.c_str());
    node = strtok(dup, ",");


    while (node != NULL)
    {
        tmp = atoi(node);

        // not adding 0 because every prints contains it
        if (tmp != 0) {
            nodes[idx] = tmp;
            idx++;
        }
        node = strtok(NULL, ",");
    }

    delete dup;
    delete node;

    nodesNum = idx;
}

Answer 1

You have forgotten to delete several things and used the wrong form of delete for arrays where you have remembered, e.g.

float Analyzer::calculateRisk() {

    float totRisk = 0;
    int maxSize = graph->nodesNum;
    int *nodes = new int[maxSize];
    //...
    delete [] nodes; //<------- DO THIS not delete nodes

The simplest solution is to avoid using raw pointers and use smart ones instead. Or a std::vector if you just want to store stuff somewhere to index into.

Answer 2

You allocate actualNodes in analyze() but you don't release the memory anywhere:

int *actualNodes = new int[maxSize];

In Addition, Analyzer::bestResult and Analyzer::actualResult are allocated in the constructor of Analyzer but not deallocated anywhere.

this->actualResult = new string[graph->nodesNum];
this->bestResult = new string[graph->nodesNum];

If you must use pointers, I really suggest to use smart pointers, e.g. std::unique_ptr and/or std::shared_ptr when using C++11 or later, or a Boost equivalent when using C++03 or earlier. Otherwise, using containers, e.g. std::vector is preferred.

PS: You're code also has a lot of mismatches in terms of allocation and deallocation. If memory is allocated using alloc/calloc/strdup... it must be freed using free. If memory is allocated using operator new it must be allocated with operator delete. If memory is allocated using operator new[] it must be allocated with operator delete[]. And I guess you certainly should not delete the return value of strtok.

Answer 3

You have new without corresponding delete

this->actualResult = new string[graph->nodesNum];
this->bestResult = new string[graph->nodesNum];

These should be deleted somewhere using delete [] ...