Unknown Segmentation Fault?

Question

I am having a problem in my code. I have run and debugged it several times. It seems to work fine if I do not throw an exception in my getEntry function. But when I do throw an exception, my program has a segmentation fault after that. When I debug through the program, it seems that the nextNodePtr in the getEntryHelper is not 0x0. So it somehow gets changed after it throws the exception and I have no idea why.

My main:

#include <iostream>
#include "BinarySearchTree.h"

int main {
BinarySearchTree<std::string,std::string> myTree;
    myTree.add("book");
        myTree.add("encyclopedia");
    myTree.add("automobile");
    myTree.add("zebra");
        myTree.getEntry(zebra);
        myTree.getEntry(xylophone);
        myTree.getEntry(tree); // Does not get to here

}

Here are my add an and getEntry methods (although it appears that my getEntry is the problem:

template<typename KeyType, typename ItemType>
void BinarySearchTree<KeyType,ItemType>::add(const ItemType& newEntry) {
    if(rootPtr == NULL)
        rootPtr = new BinaryNode<ItemType>(newEntry);
    else {
        addHelper(rootPtr,rootPtr,newEntry);
    }
}

template<typename KeyType, typename ItemType>
ItemType BinarySearchTree<KeyType,ItemType>::getEntry(const KeyType& aKey) const
        throw(NotFoundException) {
    try {
        BinaryNode<ItemType>* temp = getEntryHelper(rootPtr,aKey);
        std::cout << temp->getItem() << "\n";
        return temp->getItem();
    }
    catch(NotFoundException& nf) {
        std::cout << nf.what();
    }
}

template<typename KeyType, typename ItemType>
void BinarySearchTree<KeyType,ItemType>::addHelper(BinaryNode<ItemType>* prevNodePtr,
                                                    BinaryNode<ItemType>* nextNodePtr,
                                                    const ItemType& newEntry) {

    if(nextNodePtr == NULL) { // Base Case
        nextNodePtr = new BinaryNode<ItemType>(newEntry,NULL,NULL);
        if(newEntry < prevNodePtr->getItem())
            prevNodePtr->setLeftChildPtr(nextNodePtr);
        else
            prevNodePtr->setRightChildPtr(nextNodePtr);
        return;
    }
    if(newEntry < nextNodePtr->getItem()) {
        prevNodePtr = nextNodePtr;
        nextNodePtr = nextNodePtr->getLeftChildPtr();
        addHelper(prevNodePtr,nextNodePtr,newEntry);
    }
    else {
        prevNodePtr = nextNodePtr;
        nextNodePtr = nextNodePtr->getRightChildPtr();
        addHelper(prevNodePtr,nextNodePtr,newEntry);
    }
}

template<typename KeyType, typename ItemType>
BinaryNode<ItemType>* BinarySearchTree<KeyType,ItemType>::getEntryHelper(BinaryNode<ItemType>* nextNodePtr,const KeyType& aKey) const {
    if(nextNodePtr == NULL) {
        throw NotFoundException("does not exist in tree.\n");
    }
    else if(nextNodePtr->getItem() == aKey)
        return nextNodePtr;
    else if(aKey < nextNodePtr->getItem()) {
        getEntryHelper(nextNodePtr->getLeftChildPtr(),aKey);
    }
    else {
        getEntryHelper(nextNodePtr->getRightChildPtr(),aKey);
    }
}

Output: automobile book encyclopedia zebra zebra Precondition Violated Exception: xylophone does not exist in tree. Segmentation fault (core dumped)

I think you'll need to rethrow in getEntry after logging - otherwise the return value from there is undefined, no? — 500 - Internal Server Error, Apr 29 '13 at 16:58
I didn't realize that could change the pointer value. It works now, thanks! — user2041391, Apr 29 '13 at 18:13
If NotFoundException is thrown from getEntryHelper() function then you should not be having any issues, as it is caught in getEntry() function. I feel its a dangling pointer issue, where nextnodePtr is not allocated and that triggered the exception which is not caught anywhere leading to segmentation fault. And I guess you haven't set the left and right ptr's to null in constructor for BinaryNode(newEntry). — Rahul Sundar, Apr 29 '13 at 18:52
don't use `throw(something)`: http://stackoverflow.com/a/1055407/453271 — Andriy Tylychko, Apr 29 '13 at 20:13

Rahul Sundar · Answer 1 · 2013-04-29T20:06:07.487

On a quick look, I could see there are few issues where exceptions are not handled proper.

Function getEntry() signals that it can thow NotFoundException, but in main() I couldn't see any exception handler for it. So put a basic try catch in main() function which can handle any exceptions.
```
int main()
{
 try
 {
  //some code
 }
 catch(..)
 {
  cout << "Unkown Exception";
 }
 return 0;
}
```
Function getEntry() signals that it can thow NotFoundException but you have a try catch block where you process the exception but never re-throwed nor thowing any new\modified NotFoundException. If you don't wish to throw it, then comment the throw(NotFoundException) in the function declaration.
```
    ItemType BinarySearchTree<KeyType,ItemType>::getEntry(const KeyType& aKey) //const throw (NotFoundException) -> Comment this
```

If not after processing the NotFoundException, rethrow it.

catch(NotFoundException& nf) {
    std::cout << nf.what();
    rethrow;
}

But still I am not sure if your Binary code insertion logic works fine. Post the entire header and cpp file, if you come across any logic issues.

Unknown Segmentation Fault?

1 Answers1