CODEWITHSUNDEEP
c++c++11
Kodnot
Kodnot

Reputation: 113

Code exhibiting different behaviour on different platforms, requesting explanation

When trying to answer a question on stackexchange, I tried to review this piece of code:

#include <iostream>


using namespace std;

struct Node {
    int key;
    Node *leftnode;
    Node *rightnode;
    string value;
    Node(int tkey, const std::string& tvalue) : leftnode(nullptr), rightnode(nullptr), key(tkey), value(tvalue) {}
};

Node root_node(1, "Node #1"); // Binary search tree
string inline query_bst(const int key) {
    Node *cur_node = &root_node;
    while (cur_node != NULL) {
        if (key == cur_node->key) {
            return cur_node->value;
        }
        if (key < cur_node->key) { /* value already returned, no need for else */
            cur_node = cur_node->leftnode;
        } else {
            cur_node = cur_node->rightnode;
        }
    }
    return ""; // Return empty string if not found
}

void inline insert_bst(int key, string value) {
    Node *cur_node;
    Node *next_node = &root_node;
    // Search through bst for key
    while (next_node != NULL) {
        cur_node = next_node;
        if (key < cur_node->key) {
            next_node = cur_node->leftnode;
        } else {
            next_node = cur_node->rightnode;
        }
    }
    Node new_node(key, value);
    next_node = &new_node;
    if (key < cur_node->key) {
        cur_node->leftnode = next_node;
    } else {
        cur_node->rightnode = next_node;
    }
}

int main() {
    root_node.key = 1;
    insert_bst(2, "Node #3");
    insert_bst(3, "Node #4");

    cout << query_bst(3) << '\n' << query_bst(4);
}

For me, this program compiles, but crashes. I searched for the cause of this, and deduced (hopefully correctly) that in function "insert_bst()" a variable named "new_node" is created, and later a pointer is assigned this variable's address. However, the new_node var has an automatic duration, thus it is destroyed at the end of the function's execution. Therefore, during the second call of insert_bst(), when the program tries to access the key/value of the inserted node, trash values are retrived (this I confirmed using a debugger), which ruins the program. Then why would this piece of code work properly on some other platform?

My tests were done on Windows 7 x64, on Code::Blocks 16.01 and CLion, using g++.

The platform on which the code works: Mac OS X Yosemite Clion, also g++

Upvotes: 1

Views: 72

Answers (1)

NathanOliver
NathanOliver

Reputation: 180414

As you deduced correctly the function is creating a local object and adding that to the BST. When the local object is destroyed when the function returns we now have a dangling pointer and using it is undefined behavior.

Since it is undefined behavior that means that the behavior of the program is undefined. It may run, crash, become self aware and name itself Skynet or anything in between.

As MikeCAT pointed out we can get rid of this undefined behavior by using new to make the node persistent and that gets rid of the dangling pointer issue.

Upvotes: 2

Related Questions