C++

Forum

 
 
Help with segmentation fault

rubito (28)
I'm writing a binary search tree program and I got it to compile but as soon as I input something it returns a "segmentation fault error"

I suspect the issue with the code is withing my `add` function. 
1
2
3
4
5
6
7
8
9
10
11
12
 
template<typename T>
void BinarySearchTree<T>::add(T value)
{
    if (m_root == nullptr)
    {
        Node<T>* node = new Node<T>;
        node->setValue(value);
        m_root = node;
    }
    else
        add(value, m_root);
}



and it's private member class 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
template<typename T>
void BinarySearchTree<T>::add(T value, Node<T>* subtree)
{
    if (value < subtree->getValue())
    {
        if(subtree->getLeft() == nullptr)
        {

            Node<T>* node = new Node<T>();
            node->setValue(value);
            subtree->setLeft(node);
        }
        else
        {
            add(value, subtree->getLeft());
        }
    }
        else if (value >= subtree->getValue())
        {
            if(subtree->getRight() == nullptr)
            {

            Node<T>* node = new Node<T>();
            node->setValue(value);
            subtree->setRight(node);
            }
        }
        else
        {
            add(value, subtree->getRight());
        }
}


This class it's called from my main.cpp 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
int main()
{
	BinarySearchTree<int> numTree;
	int userNum=0;
	char quit='n';

	while(quit != 'y')
	{
		std::cout << "Input a number to put in the tree: ";
		std::cin >> userNum;
		numTree.add(userNum);
		std::cout << "Done adding numbers? (y/n): ";
		std::cin >> quit;
	}


I'm not too familiar with segmentation errors. I checked for memory leaks and it didn't return any.
This is my valgrind log file

==17213== Memcheck, a memory error detector
==17213== Copyright © 2002-2012, and GNU GPL'd, by Julian Seward et al.
==17213== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==17213== Command: ./Lab
==17213==
Input a number to put in the tree: 10
==17213== Conditional jump or move depends on uninitialised value(s)
==17213== at 0x400DE0: BinarySearchTree<int>::add(int) (BinarySearchTree.hpp:22)
==17213== by 0x400B8F: main (main.cpp:15)
==17213==
==17213== Use of uninitialised value of size 8
==17213== at 0x401330: Node<int>::getValue() (Node.hpp:17)
==17213== by 0x400F49: BinarySearchTree<int>::add(int, Node<int>*) (BinarySearchTree.hpp:69)
==17213== by 0x400E30: BinarySearchTree<int>::add(int) (BinarySearchTree.hpp:29)
==17213== by 0x400B8F: main (main.cpp:15)
==17213==
==17213== Use of uninitialised value of size 8
==17213== at 0x401342: Node<int>::getLeft() (Node.hpp:23)
==17213== by 0x400F5F: BinarySearchTree<int>::add(int, Node<int>*) (BinarySearchTree.hpp:71)
==17213== by 0x400E30: BinarySearchTree<int>::add(int) (BinarySearchTree.hpp:29)
==17213== by 0x400B8F: main (main.cpp:15)
==17213==
==17213== Use of uninitialised value of size 8
==17213== at 0x401342: Node<int>::getLeft() (Node.hpp:23)
==17213== by 0x400FB7: BinarySearchTree<int>::add(int, Node<int>*) (BinarySearchTree.hpp:80)
==17213== by 0x400E30: BinarySearchTree<int>::add(int) (BinarySearchTree.hpp:29)
==17213== by 0x400B8F: main (main.cpp:15)
==17213==
==17213== Invalid read of size 4
==17213== at 0x401330: Node<int>::getValue() (Node.hpp:17)
==17213== by 0x400F49: BinarySearchTree<int>::add(int, Node<int>*) (BinarySearchTree.hpp:69)
==17213== by 0x400FCB: BinarySearchTree<int>::add(int, Node<int>*) (BinarySearchTree.hpp:80)
==17213== by 0x400E30: BinarySearchTree<int>::add(int) (BinarySearchTree.hpp:29)
==17213== by 0x400B8F: main (main.cpp:15)
==17213== Address 0x64894cd8246c8958 is not stack'd, malloc'd or (recently) free'd
==17213==
==17213==
==17213== Process terminating with default action of signal 11 (SIGSEGV)
==17213== General Protection Fault
==17213== at 0x401330: Node<int>::getValue() (Node.hpp:17)
==17213== by 0x400F49: BinarySearchTree<int>::add(int, Node<int>*) (BinarySearchTree.hpp:69)
==17213== by 0x400FCB: BinarySearchTree<int>::add(int, Node<int>*) (BinarySearchTree.hpp:80)
==17213== by 0x400E30: BinarySearchTree<int>::add(int) (BinarySearchTree.hpp:29)
==17213== by 0x400B8F: main (main.cpp:15)
==17213==
==17213== HEAP SUMMARY:
==17213== in use at exit: 0 bytes in 0 blocks
==17213== total heap usage: 0 allocs, 0 frees, 0 bytes allocated
==17213==
==17213== All heap blocks were freed -- no leaks are possible
==17213==
==17213== For counts of detected and suppressed errors, rerun with: -v
==17213== Use --track-origins=yes to see where uninitialised values come from
==17213== ERROR SUMMARY: 5 errors from 5 contexts (suppressed: 2 from 2)
Segmentation fault (core dumped)



My program makes use of templated classes but I didn't include any of the .h code in order to keep this post as small as possible. Any help would be great.
Smac89 (1727)
Your first error is that you are not passing the pointers by reference. Pointers are variable types. If you want to modify the value of a pointer, you need the actual reference to the pointer.

void BinarySearchTree<T>::add(T, Node<T> *&);

Your second error comes from the fact that you are not checking if the subtree is null before attempting to dereference the pointer (line 4 of private add function) Nvm, it looks like you are checking for null, I failed to see that
Last edited on
MiiNiPaa (8886)
Show default Node constructor. I suppose it does not set left and right pointers to nullptr so you will have garbage in it and so your ==nullptr condition will fil and you will try to access uninitialized pointer.
rubito (28)
So line 2 of private add function should be?:
void BinarySearchTree<T>::add(T value, Node<T>* & subtree)
rubito (28)
This is my default Node constructor

1
2
3
4
5
6
7
8
 
#define nullptr NULL
template<typename T>
Node<T>::Node()
{
    this->m_left = nullptr;
    this->m_right = nullptr;
    this->m_value = nullptr;
}
Smac89 (1727)
@rubito, yes that is what it should look like. Also what do your setLeft, setRight functions look like?
rubito (28)
When I change line 2 to that I get the errors

BinarySearchTree.hpp|67|error: prototype for ‘void BinarySearchTree<T>::add(T, Node<T>*&)’ does not match any in class ‘BinarySearchTree<T>’|
BinarySearchTree.hpp|20|error: candidates are: void BinarySearchTree<T>::add(T)|
BinarySearchTree.h|19|error:void BinarySearchTree<T>::add(T, Node<T>*)|


These are my setLeft & setRight functions

1
2
3
4
5
6
7
8
9
10
11
 
template<typename T>
void Node<T>::setRight(Node<T>* right)
{
    m_right = right;
}//end setRight

template<typename T>
void Node<T>::setLeft(Node<T>* left)
{
    m_left=left;
}
MiiNiPaa (8886)
What about BinarySearchTree default constructor? Your stack trace shows that getLeft called twice on first run which should not happens. My next suspect is uninitialized m_root
Smac89 (1727)
The error is because you have not corrected the function header in your header file. You need to change

void BinarySearchTree<T>::add(T, Node<T>*)
To
void BinarySearchTree<T>::add(T, Node<T> *&)

in BinarySearchTree.h
Last edited on
rubito (28)
Smac89 you were right on point with that one.

My BinarySearchTree 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
#include "BinarySearchTree.h"

template<typename T>
BinarySearchTree<T>::BinarySearchTree()
{
    Node<T>* m_root = nullptr;
}

template<typename T>
BinarySearchTree<T>::~BinarySearchTree()
{
    delete m_root;
    m_root = nullptr;
}
MiiNiPaa (8886)
Line 6 in your constructor: you are declaring local variable which shadows member of class and assigning it value while leaving class member uninitializated. Remove Node<T>* from that line.

Also you shouldn't pass pointers by reference here: you do not change them, only dereference, so extra layer of indirection isn't needed (and no breaking CPU prediction here)
Last edited on
rubito (28)
I changed line 6 to 

1
2
 
  m_root = new Node<T>;
    m_root->setValue(nullptr);


and now I'm getting an error on the
add(value, subtree->getLeft());

it has to do with the & operand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
template<typename T>
void BinarySearchTree<T>::add(T value, Node<T>* & subtree)
{
    if (value < subtree->getValue())
    {
        if(subtree->getLeft() == nullptr)
        {

            Node<T>* node = new Node<T>();
            node->setValue(value);
            subtree->setLeft(node);
        }
        else
        {
            add(value, subtree->getLeft());
        }
    }
Smac89 (1727)
1
2
3
4
5
6
7
8
9
 
Node<T> *&Node<T>::getRight()
{
    return m_right;
}

Node<T> *&Node<T>::getLeft()
{
    return m_left;
}
rubito (28)
Could you please elaborate? I'm having a hard time following where your correction should go.
Smac89 (1727)
I mean replace your get functions with those ones I posted above
rubito (28)
You guys are awesome! With your help I'm now free of errors! Thanks a lot!
Topic archived. No new replies allowed.