C++ binary search tree creates segmentation fault

Question

I'm trying to make a program that identifies AVR assembly instructions by opcode, since those are just a list of 1's and 0's I thought it would be a good project to make a binary search tree for.

Sadly I keep getting segmentation faults when trying to search through the tree. As I understand it a seg fault is usually the result of trying to do stuff with a pointer that doesn't point to anything, but since I have a Boolean that I check first that should never happen.

I'm pretty sure it has something to do with the way I use pointers, as I'm not very experienced with those. But I can't seem to figure out what's going wrong.

Below is the code involved (SearchTree is only a global variable in this minimal example, not in the real program.):

The code:

#include <iostream>

void ADD(short &code) {std::cout << code << "\n";}
void LDI(short &code) {std::cout << code << "\n";}
void SBRC(short &code){std::cout << code << "\n";}

struct node
{
    void(* instruct)(short &code);
    bool hasInst = false;

    struct node *zero;
    bool hasZero = false;

    struct node *one;
    bool hasOne = false;
};

node SearchTree;

auto parseOpcode(short code, node *currentRoot)
{
    std::cout << "Looking for a:  " << ((code >> 15) & 0b01 == 1) << std::endl;
    std::cout << "Current node 1: " << (*currentRoot).hasOne << std::endl;
    std::cout << "Current node 0: " << (*currentRoot).hasZero << std::endl;

    // Return instruction if we've found it.
    if ((*currentRoot).hasInst) return (*currentRoot).instruct;

    // Case current bit == 1.
    else if ((code >> 15) & 0b01 == 1)
    {
        if ((*currentRoot).hasOne) return parseOpcode((code << 1), (*currentRoot).one);
        else throw "this instruction does not exist";
    }
    // Case current bit == 0.
    else {
        if ((*currentRoot).hasZero) return parseOpcode((code << 1), (*currentRoot).zero);
        else throw "this instruction does not exist";
    }
}

void addopcode(void(& instruct)(short &code), int opcode, int codeLength)
{
    node *latest;
    latest = &SearchTree;
    for (int i = 0; i <= codeLength; i++)
    {
        // Add function pointer to struct if we hit the bottom.
        if (i == codeLength)
        {
            if ((*latest).hasInst == false)
            {
                (*latest).instruct = &instruct;
                (*latest).hasInst = true;
            }
        }
        // Case 1
        else if (opcode >> (codeLength - 1 - i) & 0b01)
        {
            if ((*latest).hasOne)
            {
                latest = (*latest).one;
            }
            else{
                node newNode;
                (*latest).one = &newNode;
                (*latest).hasOne = true;
                latest = &newNode;
            }
        }
        // Case 0
        else {
            if ((*latest).hasZero)
            {
                latest = (*latest).zero;
            }
            else{
                node newNode;
                (*latest).zero = &newNode;
                (*latest).hasZero = true;
                latest = &newNode;
            }
        }
    }
}


int main()
{
    addopcode(ADD, 0b000011, 6);
    addopcode(LDI, 0b1110, 4);
    addopcode(SBRC, 0b1111110, 7);

    short firstOpcode = 0b1110000000010011;

    void(* instruction)(short &code) = parseOpcode(firstOpcode, &SearchTree);
    instruction(firstOpcode);
    return 0;
}

EDIT: I still had some #includes at the top of my file that linked to code I didn't put on StackOverflow.

Answer 1

The error happened because I forgot to use the new keyword and was therefor populating my search tree with local variables (which were obviously now longer around by the time I started searching through the tree).

Fixed by using:

node *newNode = new node();
(*latest).one = newNode;
(*latest).hasOne = true;
latest = newNode;

Instead of:

node newNode;
(*latest).one = &newNode;
(*latest).hasOne = true;
latest = &newNode;