CODEWITHSUNDEEP
c++recursionmemory-leaks
gabyk00
gabyk00

Reputation: 151

C++ memory leak in recursion

I am trying to implement a fast way of applying power operation on a matrix in C++ ( O(logn) ). Therefore I had the define the multiplication and the power operation as you can see below

int ** matrixmul(int ** A, int ** B, int n) {
    int ** result = (int **) calloc(sizeof(int *), n);
    for (int i = 0; i < n; ++i)
    result[i] = (int *) calloc(sizeof(int), n);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            int sum = 0;
            for (int k = 0; k < n; ++k) {
                sum += A[i][k] * B[k][j];
            }
            result[i][j] = sum;
        }
    }
    return result;
}

int ** matrixpow(int ** m, int n, int p) {
    if (p == 1) {
        return m;
    } else if (p % 2 == 0) {
        return matrixmul(matrixpow(m, n, p / 2), matrixpow(m, n, p / 2), n);
    } else {
        return matrixmul(matrixmul(matrixpow(m, n, (p - 1) / 2), matrixpow(m, n, (p - 1) / 2), n), m, n);
    }
}

The matrixmul function is not a generic multiplication for matrices, it's only for squared ones.

My question is if there is a way of modifying these functions so I will not have any memory leaks, because the program loses memory on each recursive call

Upvotes: 0

Views: 844

Answers (2)

Rubix Rechvin
Rubix Rechvin

Reputation: 581

If you wanted to continue to use the int** for some reason, you could also make your program handle the free properly by freeing A and B before returning result in matrixmult. These are most likely the variables that are getting leaked as once matrixmult is done, you lose the ability to reference them ever again. You can free this memory pretty easily since everything is of size n throughout you code:

for( int i = 0 ; i < n ; i++ ) {
    for( int j = 0 ; j < n ; j++ ) {
        free(A[i][j]);
        free(B[i][j]);
    }
    free(A[i]);
    free(B[i]);
}

Also this line of code seems strange: 

int ** result = (int **) calloc(sizeof(int *), n);

The first parameter to calloc should be the number of elements you want and the second one should be size. I believe it should be 

int ** result = (int **) calloc(n, sizeof(int *));

Upvotes: 1

Luka Rahne
Luka Rahne

Reputation: 10447

Replace ** with vectors and avoid using calloc, malloc, new and delete.

std::vector< std::vector<int> > result = ....

This will remove problems with memory management and you can return vectors by value in C++11.

typedef std::vector< std::vector<int> >  Matrix;

Matrix  matrixmul(const Matrix& A, const Matrix& B, int n) {
  Matrix result(n);
  for (int i = 0; i < n; ++i)
    result[i] = std::vector<int>(n);

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      int sum = 0;
      for (int k = 0; k < n; ++k) {
        sum += A[i][k] * B[k][j];
      }
     result[i][j] = sum;
    }
  }
  return result;
}

Upvotes: 4

Related Questions