Segmentation fault

[binbk]

I am a very new Linux but I like it a lot and don't want to go back to Windows. I use Block Code to do programming. Everything was good until now. My project now is using BTS to print out the words that have more than 2 letter ( it has 3 parts and this is the first one ). I already finished this part by using the computer at library that using window, therefor I wrote this part by using Visual Studio and it already worked. But when I created a new project in Block::Code and added the cpp file in, it has done the compile process but the xTerm give me the error "Segmentation fault". I already run the debug but I really don't know how to fix it.

void BinNode::Insert(BinNode *&root, string word)
{
    if(root==NULL)
    {
        root = new BinNode;
        root -> left = NULL;
        root -> right = NULL;
        root -> data = word;
        return ;
    }
    if(word > root -> data)
        Insert (root -> right, word);
    if(word < root -> data)
        Insert (root -> left, word);
}

I run the debug and it showed me there is something wrong with this function. It also lead me to the basic_string.h and the cursor is in the last line of the codes below

    template<typename _CharT, typename _Traits, typename _Alloc>
    inline bool
    operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
	      const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    { return __lhs.compare(__rhs) > 0; }

I asked Google the Segmentation fault and I knew that is something wrong with the pointer but I can't figure out. Do I have to create a overloading operator > ? I think <string> has it in its library. I really stuck. I will appreciate any help. Thank you for reading.

[ne555]

http://www.cplusplus.com/forum/general/112111/

> I knew that is something wrong with the pointer but I can't figure out
Dereferencing an invalid pointer.
Given that you check if `root' is NULL, then probably it was not initialized, or whatever it pointed to got deleted.
Hard to say with so little code.


> Do I have to create a overloading operator > ? I think <string> has it in its library.
If that were the problem your code wouldn't compile.

[binbk]

Thanks for replying. I really appreciate that. I already initialized the root as BinNode in the main(). Here is the rest of the code that include a class BinNode, the print function inorder and the main function

class BinNode
{
public:
    void Insert(BinNode *&root, string word);
    void inorder(BinNode *t);

    string data;
    BinNode *left;
    BinNode *right;
};

void BinNode::inorder(BinNode *t)
{
    if(t!=NULL)
    {
        inorder(t->left);
        cout<<t->data<<endl;
        inorder(t->right);
    }
}

int main()
{
    BinNode root;
    BinNode *ptr = & root;
    string word, myword;


    char namein[20];
    int length(0);

    ifstream stringin;
    ofstream stringout;

    cout<<"file in's name "<<endl;

    cin>>namein;

    stringin.open(namein);

    if(stringin.fail())
    {
        cout<<"Error opening"<<endl;
        return 0;
    }
    while(stringin>>word)
    {
        length = word.length();
        char p = word[length - 1];
        if(ispunct(p))
        {
            word.erase(length-1,1);
            length = word.length();
        }
        if(length<3)
            continue;
        else
        {
            root.Insert(ptr, word);
        }
    }
    root.inorder(ptr);
    stringin.close();
    return 0;
}

[ne555]

You have no initialized `root.right' and `root.left'
That should be done in the constructor

BinNode::BinNode(): 
   left(NULL),
   right(NULL)
{}

Also, you are leaking memory (all that's created with new must be destroyed with delete )


PS: when posting code try to make it simply to copy paste, so use just one snip and include the necessary headers

[binbk]

That's my bad. Thank you for reminding me. I don't have a constructor but I already combined a constructor in the insert function. That is when root == NULL.

void BinNode::Insert(BinNode *&root, string word)
{
    if(root==NULL)
    {
        root = new BinNode;
        root -> left = NULL;
        root -> right = NULL;
        root -> data = word;
        return ;
    }
    if(word > root -> data)
        Insert (root -> right, word);
    if(word < root -> data)
        Insert (root -> left, word);
}

And you are right about memory leakage, but even after I insert "delete root" before "return;" xterm still give me the segmentation fault. I want to repeat that it already worked when I used Visual Studio. I am wondering whether it has problem with different compiler.
This is what the Call Stack inform to me. I think it has problem with operator >.

#0 0xb7f753f9 std::string::compare(std::string const&) const() (/usr/lib/i386-linux-gnu/libstdc++.so.6:??)
#1 0x8049341 std::operator><char, std::char_traits<char>, std::allocator<char> >(__lhs=..., __rhs=...) (/usr/include/c++/4.6/bits/basic_string.h:2549)
#2 0x8048e89 BinNode::Insert(this=0xbffff5e8, root=@0xb7ec66e0: 0x804e1a8, word=...) (/home/Documents/p14/project14.cpp:30)
#3 0x8048ebd BinNode::Insert(this=0xbffff5e8, root=@0xbffff5f0: 0xb7ec66d8, word=...) (/home/Documents/p14/project14.cpp:31)
#4 0x8048ebd BinNode::Insert(this=0xbffff5e8, root=@0xbffff5f4: 0xbffff5e8, word=...) (/home/Documents/p14/project14.cpp:31)
#5 0x8049174 main() (/home/Documents/p14/project14.cpp:83)

Thank you for quick reply ne555. I really appreciate that.

[ne555]

> but I already combined a constructor in the insert function.
the problem is with the node created in main(). Inspect it

root = {data = "", left = garbage, right = garbage}

When you call the insert() function you are doing insert(&root, word);^*
Now see what happens inside the function

void BinNode::Insert(BinNode *&root, string word)
{
    if(root==NULL) //false
        //...
    if(word > root -> data) //data is empty, false
        Insert (root -> right, word);
    if(word < root -> data) //true
        Insert (root -> left, word); //gets called
}

So you called the function again, now passing `root->left'. But `root->left' has garbage, so when you try to do `root->left->data' you invoke undefined behaviour

> I want to repeat that it already worked when I used Visual Studio
undefined behaviour is undefined
you don't initialize your variables, they have garbage. `0' is as good value for garbage as any other.

> And you are right about memory leakage, but even after I insert "delete root" before "return;"
No, you must delete the object when you finish using it.
By instance

//the parent dies, so it takes its children with it
BinNode::~BinNode(){
   delete left;
   delete right;
}:

Another thing that you may do is to separate the tree from the nodes, the client doesn't need to know about the node class

class tree{
   BinNode root;
public:
   insert(std::string word);
};

^* The object is irrelevant, you don't use state in your function
You actually use `ptr' that holds the value of &root. And you never modify `ptr'

[binbk]

I got it. Thank you for you help. I am very appreciate that.

[dhayden]

Since BinNode owns the left and right pointers, you should create a copy constructor and assignment operator that do a deep copy, or define them both as private members so you'll get a compile time error if you try to copy them.