possible double free error

[juseniah]

I could use help determining whether an error is related to freeing memory or (somehow) to getting input by passing two files as arguments from the command line. I explain my beginner reasoning below.

My program is a C++ dynamic programming solution to the longest common subsequence problem. Code is at end of this message. It utilizes two 2d dynamic arrays and the only output is the actual LCS. It gets two strings from two input files at the command line, meaning I type this at the command line: ./Dynamic str1.txt str2.txt

When I compile and run it on Linux, I get the correct output followed by an error. I have omitted the backtrace.

GTCGTCGGAAGCCGGCCGAA
*** Error in `./Dynamic': double free or corruption (out): 0x00000000016ab200 ***

I can eliminate the error in two ways:
1) Alter the program so that I no longer read input from the command line. Instead, I simply define str1="ABCD" and str2="BD" (or whatever).
2) Stop deallocating the dynamic memory as I know I should (lines 68-75).

If I leave the program as is and run valgrind, the output is numerous repetitions of this:

==48471== Invalid write of size 8
==48471==    at 0x4012BD: lcs(std::string, std::string, unsigned long, unsigned long) (in /home/doherty/Dynamic)
==48471==    by 0x40190F: main (in /home/doherty/Dynamic)
==48471==  Address 0x5a29a18 is 0 bytes after a block of size 232 alloc'd
==48471==    at 0x4C2AC38: operator new[](unsigned long) (vg_replace_malloc.c:433)
==48471==    by 0x40122D: lcs(std::string, std::string, unsigned long, unsigned long) (in /home/doherty/Dynamic)
==48471==    by 0x40190F: main (in /home/doherty/Dynamic)

And finally, my code is all in one cpp file:

#include <iostream>
#include <fstream>
#include <string>

// recursively prints the actual subsequence
void printLCS(int** b, std::string x, size_t r, size_t c) {
    if (r==0 or c==0)
        return;
    int val = b[r][c];
    if (val==2){
        printLCS(b, x, r-1, c-1);
        std::cout << x[r];
    }
    else if (val==3)
        printLCS(b, x, r-1, c);
    else
        printLCS(b, x, r, c-1);
}

// lcs func calculates length of lcs
void lcs(const std::string x, const std::string y, const size_t m, const size_t n) {
    if(m==0 || n==0) {
        std::cerr << "Both strings must be at least one character in length." << std::endl;
        exit(1);
    }
    
    // dynamically create arrays of pointers of size m
    int **b = new int*[m];
    int **c = new int*[n];
    
    // dynamically allocate memory of size n for each row
    for (int i=0; i < m; i++) {
        b[i] = new int[n];
        c[i] = new int[n];
    }
    
    // assign values to allocated memory
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            c[i][j] = 0;
            b[i][j] = 0;
        }
    }
    
    // Main loop
    for(int i = 1; i < m; i++) {
        for(int j = 1; j < n; j++) {
            if (x[i] == y[j]) {
                c[i][j] = c[i-1][j-1] + 1;
                b[i][j] = 2;
            }
            else if (c[i-1][j] > c[i][j-1]) {
                c[i][j] = c[i-1][j];
                b[i][j] = 3;
            }
            else {
                c[i][j] = c[i][j-1];
                b[i][j] = 1;
            }
        }
    } // end of main loop
    
    // print LCS
    printLCS(b, x, m-1, n-1);
    std::cout << std::endl;
    
    // deallocating arrays
    for (int i = 0; i < m; i++) {
        delete[] b[i];
        delete[] c[i];
    }
    delete[] b;
    delete[] c;
    b = NULL;
    c = NULL;
    
} // end of lcs function

// Driver program
int main(int argc, const char * argv[]) {
    if (argc != 3) {
        std::cerr << "Provide 2 input file names for command line args." << std::endl;
        exit(1);
    }

    // Prepare file streams
    std::ifstream infile1(argv[1]);
    std::ifstream infile2(argv[2]);

    // If problem with either input file, exit
    if( !infile1.good() || !infile2.good() ) {
        std::cerr << "Invalid input file" << std::endl;
        exit(1);
    }

    // Gets first line of each file into str1 and str2
    std::string str1 = " ";
    std::string str2 = " ";
    std::string temp;
    getline(infile1, temp);
    str1.append(temp);
    getline(infile2, temp);
    str2.append(temp);

    // Cleaning up
    infile1.close();
    infile2.close();
    
    // Get length of both strings
    size_t m = str1.length();
    size_t n = str2.length();
    
    // Calculate LCS
    lcs(str1, str2, m, n);
    
    return 0;
}

[coder777]

Line 29: Replace n with m.

[keskiverto]

Is this homework, where you absolutely have to use new and delete?

If not, then lines 27-43 (and lines 67-75) could be replaced with:

std::vector<std::vector<int>> b( rows, std::vector( cols, 0 ) );
std::vector<std::vector<int>> c( rows, std::vector( cols, 0 ) );

Even if it is not, wouldn't rows and cols be easier to distinguish than m and n?

Obviously 'rows' is not intuitive name for "length of x", but neither is 'm'.

Why is the length passed to lcs() separately?
Will you sometimes call lcs( "Hello", "world!", 3, 4 );?

[seeplus]

Any reason why string x and string y are passed by value rather than by const ref - as their contents don't change?

[juseniah]

Thank you! It runs without error when I make the change suggested by coder777.

Now it's time to implement some of the other changes y'all suggested:
* change array to vector
* rename variables
* pass strings as const ref