CODEWITHSUNDEEP
c++c++11
jonikvir
jonikvir

Reputation: 5

Getting a 'double free or corruption' error with calls to a function within a recursive function

I have a recursive function solveCountdownProblem which calls evaluateCountdown which takes an expression in reverse-polish notation format. evaluateCountdown is in a series of nested for loops (in solveCountdownProblem) so is called a lot of times.

double evaluateCountdown(string rpnIn) {
    vector<double> stack;
    double a = 0, b = 0;
    string token = "";
    char arithToken;
    
    for (int i = 0; i < rpnIn.size(); ++i) {
        if (rpnIn[i] == ' ') {
            if (token != "") {
                stack.push_back(stod(token)); // Push number to stack   
                token = "";
            }
        } else {
            if (find(arithOperators.begin(), arithOperators.end(), rpnIn[i]) != arithOperators.end()) { //if char is arithmetic operator
                // Pop two numbers of stack and perform operation
                // Push result back into stack
                arithToken = rpnIn[i];
                a = stack.back(); stack.pop_back(); // pops and removes elements
                b = stack.back(); stack.pop_back();
                if (arithToken == '+') {
                    stack.push_back(b+a);
                } else if (arithToken == '-'){
                    stack.push_back(b-a);
                } else if (arithToken == '/') {
                    stack.push_back(b/a);
                } else if (arithToken == '*') {
                    stack.push_back(b*a);
                }
            } else {
                token += rpnIn[i]; //add chars to string
            }
        }
    }

    return stack.back();
}

It works after some time producing the right calculations but eventually I end up with a memory error 'double free or corruption (out)'. I've used gdb to debug and it produces this backtrace.

Program received signal SIGABRT, Aborted.
__GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:50
50  ../sysdeps/unix/sysv/linux/raise.c: No such file or directory.
(gdb) backtrace
#0  __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:50
#1  0x00007ffff7bee859 in __GI_abort () at abort.c:79
#2  0x00007ffff7c593ee in __libc_message (action=action@entry=do_abort, fmt=fmt@entry=0x7ffff7d83285 "%s\n") at ../sysdeps/posix/libc_fatal.c:155
#3  0x00007ffff7c6147c in malloc_printerr (str=str@entry=0x7ffff7d85670 "double free or corruption (out)") at malloc.c:5347
#4  0x00007ffff7c63120 in _int_free (av=0x7ffff7db4b80 <main_arena>, p=0x5555555733d0, have_lock=<optimized out>) at malloc.c:4314
#5  0x000055555555a932 in __gnu_cxx::new_allocator<double>::deallocate (this=0x7fffffffd270, __p=0x5555555733e0) at /usr/include/c++/9/ext/new_allocator.h:128
#6  0x0000555555559dc0 in std::allocator_traits<std::allocator<double> >::deallocate (__a=..., __p=0x5555555733e0, __n=4) at /usr/include/c++/9/bits/alloc_traits.h:470
#7  0x000055555555932e in std::_Vector_base<double, std::allocator<double> >::_M_deallocate (this=0x7fffffffd270, __p=0x5555555733e0, __n=4) at /usr/include/c++/9/bits/stl_vector.h:351
#8  0x00005555555588fe in std::_Vector_base<double, std::allocator<double> >::~_Vector_base (this=0x7fffffffd270, __in_chrg=<optimized out>) at /usr/include/c++/9/bits/stl_vector.h:332
#9  0x0000555555558953 in std::vector<double, std::allocator<double> >::~vector (this=0x7fffffffd270, __in_chrg=<optimized out>) at /usr/include/c++/9/bits/stl_vector.h:680
#10 0x0000555555556a9a in evaluateCountdown (rpnIn="4 6 5 * + +") at Countdown.h:58
#11 0x0000555555557762 in solveCountdownProblem (operands=std::vector of length 3, capacity 4 = {...}, targetValue=21) at Countdown.h:172
#12 0x0000555555556d61 in solveCountdownProblem (operands=std::vector of length 4, capacity 5 = {...}, targetValue=21) at Countdown.h:113
#13 0x0000555555556d61 in solveCountdownProblem (operands=std::vector of length 5, capacity 6 = {...}, targetValue=21) at Countdown.h:113
#14 0x0000555555556d61 in solveCountdownProblem (operands=std::vector of length 6, capacity 6 = {...}, targetValue=21) at Countdown.h:113
#15 0x0000555555557e17 in main () at TestCountdown.cpp:19

It seems to be pointing to the line 'vector stack;' but I'm not sure why I'm getting a memory error. Doesn't the destructor automatically deallocate 'stack' once it falls out of scope?

Upvotes: 0

Views: 478

Answers (1)

Slava
Slava

Reputation: 44248

If you look into evaluated string "4 6 5 * + +" you can see that there are not enough operands for the last operation + and in your code you do not check if stack has enough elements before calling stack.pop_back() twice. You need to add that check and act accordingly. Probably cleanest way is to wrap popping in a function:

double pop( std::vector<double> &stack )
{
    if( stack.empty() ) { // throw exception, return NaN or whatever logic of your program requires
       ...
    }
    auto r = stack.back();
    stack.pop_back();
    return r;
}

then your code is shorter and cleaner:

            // Pop two numbers of stack and perform operation
            // Push result back into stack
            arithToken = rpnIn[i];
            double a = pop( stack ); // pops and removes elements
            double b = pop( stack );

(and it is better idea to declare and initialize variables when you need them, not in advance)

Upvotes: 5

Related Questions