CODEWITHSUNDEEP
c++treec-strings
user1861248
user1861248

Reputation: 79

Why does passing a C-style string to a function result in not being able to access the string?

I have this code here below, which describes a structure called Node which contains a pointer to an Entry type and two pointers to other Nodes. It is a tree.

struct Node {
public:
    Entry* value;
    Node* left;
    Node* right;

    Node() {
        this->value = new Entry();
        this->left = nullptr;
        this->right = nullptr;
    }
    Node(Entry* init_value) {
        this->value = init_value;
        this->left = nullptr;
        this->right = nullptr;
    }

    int insert(Entry* e)
    {
        if(this->value->key == nullptr) {
            this->value = e;
            this->left = new Node();
            this->right = new Node();
            return 0;
        }
        else {
            if(this->value->compare(e) > 0) {
                return this->left->insert(e);
            }
            else if(this->value->compare(e) < 0) {
                return this->right->insert(e);
            }
            else {
                return -1; // error code
            }
        }
    }

    int research(char* key)
    {
        if(key == nullptr) { return -1; }

        if(this->value->key == nullptr) { return -1; }

        if(strcmp(this->value->key, key) > 0) {
            return this->right->research(key);
        }
        else if(strcmp(this->value->key, key) < 0) {
            return this->left->research(key);
        }
        else {
            return this->value->id;
        }
    }
};

Then I have a function in which, after ensuring that the variable key (which is a char*, ie a C-style string) is not a nullptr, I call reasearch on a Node like this:

int result = root->reasearch(key);

Why cannot I access the string inside the function, having a segmentation fault?

Upvotes: 1

Views: 105

Answers (1)

Christophe
Christophe

Reputation: 73386

In your tree search research() you will go down in the tree until either you find a matching node, or you reach a leaf.

Unfortunately, you assume that the right and left node are always non null, hence you'll end up trying to dereference a null pointer.

More details:

Suppose in the tree there is ony one node, with the key "ABC++". The node will look like: 

this->value->key points to "ABC++"
this->left is nullptr
this->right is nullptr

when you then call research("AAA") the step by step execution will be: 

    if(key == nullptr)              // condition is false 
        { ... }                     // skipped

    if(this->value->key == nullptr) // condition is false
       { ... }                      // skipped

    if(strcmp(this->value->key, key) > 0) {  // condition is true 
        return this->right->research(key);  // OUCH!!! SEGFAULT 
    ...

The problem is that in this example this->right is nullptr and dereferencing it with ->research is UB.

How to solve it:

int research(char* key)
{
    if(key == nullptr) { return -1; }

    if(this->value==nullptr || this->value->key == nullptr)  // better verify that non null.
       { return -1; }  

    if(strcmp(this->value->key, key) > 0) {
        return this->right ? this->right->research(key) : -1 ;  // check for nullptr
    }
    else if(strcmp(this->value->key, key) < 0) {
        return this->left ? this->left->research(key) : -1;   // check for nullptr
    }
    else {
        return this->value->id;
    }
}

Upvotes: 4

Related Questions