segmentation fault while loading data from a file in C++

Question

The title of my question might have been the title for many other questions on the site, however, what I am experiencing is probably the strangest thing I've ever had to deal with in my whole academic life.

I was assigned to design a binary search tree for a database that contains a long list of a company's employee records. I have successfully implemented the project and everything worked fine, until I received an email from my professor asking everyone in class to log into a Linux-powered server via SSH and verify that the project compiles and behaves as expected on there.

The source code compiled just fine, however, when I run the application and tell it to load a list of 3000 records of a file, I run into a segmentation fault at the 543th record (line in the file).

My question is: What could be causing this problem, considering the code worked fine on my own machine?

Does it matter, for the size of the project, how much memory is assigned to me? is it possible that I am running out of memory while loading the data?

Even though I am 100% sure the problem is not in my code, I still think it would be convenient for you to look at a piece of code and try to spot the problem.

Here's my employee class:

class employee
{
public:

    employee(){}

    employee(std::string first_name, std::string last_name, unsigned int ID)
    {
        this->first_name = first_name;
        this->last_name = last_name;
        this->ID = ID;
    }

    std::string first_name;
    std::string last_name;
    unsigned int ID;
    employee * left, * right;
};//*root;

This is the function I am using to load the file into the database:

void createBST(bstree & tree)
{
    string file_name;

    cout << "Enter database file path: ";
    cin >> file_name;

    ifstream file_reader (file_name.c_str());

  //  if (file_reader == NULL)
  //  {
   //     error("\nError: Invalid file path provided!\n\n");
   ///     return;
   // }

    string line;
    for (;;)
    {
        if (!getline(file_reader, line))
            break;

        string tokens[3];
        split(line, tokens);

        string first_name, last_name;
        unsigned int ID;

        last_name = tokens[0];
        first_name = tokens[1];
        ID = std::atoi(tokens[2].c_str());

    //    cout << "INSERTING: " << tokens[2] << "\t" << tokens[0] << "\t" << tokens[1] << endl;

        // insert a new employee object into bstree
        tree.Insert(new employee(first_name, last_name, ID));
    }

    cout << endl << endl << "All employee records have been inserted to database successfully." << endl << endl;

    // close file
    file_reader.close();
}

And here is my binary search tree (bstree):

#include <iomanip>
#include <iostream>
#include "bstree.h"

//--------------------------------------------
// Function: bstree()
// Purpose: Class constructor.
//--------------------------------------------
bstree::bstree()
{
    count = 0;
    root = NULL;
}

//--------------------------------------------
// Function: ~bstree()
// Purpose: Class destructor.
//--------------------------------------------
bstree::~bstree()
{
    ClearTree(root);
    return;
}

//--------------------------------------------
// Function: ClearTree()
// Purpose: Perform a recursive traversal of
//        a tree destroying all nodes.
//--------------------------------------------
void bstree::ClearTree(employee *T)
{
    if(T==NULL) return;  // Nothing to clear
    if(T->left != NULL) ClearTree(T->left); // Clear left sub-tree
    if(T->right != NULL) ClearTree(T->right); // Clear right sub-tree
    delete T;    // Destroy this node
    return;
}

//--------------------------------------------
// Function: isEmpty()
// Purpose: Return TRUE if tree is empty.
//--------------------------------------------
bool bstree::isEmpty()
{
    return(root == NULL);
}


//--------------------------------------------
// Function: DupNode()
// Purpose: Duplicate a node in the tree.  This
//        is used to allow returning a complete
//        structure from the tree without giving
//        access into the tree through the pointers.
// Preconditions: None
// Returns: Pointer to a duplicate of the node arg
//--------------------------------------------
employee *bstree::DupNode(employee * T)
{
    employee *dupNode;

    dupNode = new employee();
    *dupNode = *T;    // Copy the data structure
    dupNode->left = NULL;    // Set the pointers to NULL
    dupNode->right = NULL;
    return dupNode;
}


//--------------------------------------------
// Function: SearchTree()
// Purpose: Perform an iterative search of the tree and
//        return a pointer to a treenode containing the
//        search key or NULL if not found.
// Preconditions: None
// Returns: Pointer to a duplicate of the node found
//--------------------------------------------
employee *bstree::SearchTree(unsigned int Key)
{
    employee *temp;

    temp = root;
    while((temp != NULL) && (temp->ID != Key))
    {
        if(Key < temp->ID)
            temp = temp->left;  // Search key comes before this node.
        else
            temp = temp->right; // Search key comes after this node
    }

    if(temp == NULL)
        return temp;    // Search key not found
    else
        return(DupNode(temp));    // Found it so return a duplicate
}



//--------------------------------------------
// Function: Insert()
// Insert a new node into the tree.
// Preconditions: None
// Returns: int (TRUE if successful, FALSE otherwise)
//--------------------------------------------
bool bstree::Insert(employee *newNode)
{
    employee *temp;
    employee *back;

    temp = root;
    back = NULL;

    while(temp != NULL) // Loop till temp falls out of the tree
    {
        back = temp;
        if(newNode->ID < temp->ID)
            temp = temp->left;
        else if (newNode->ID > temp->ID)
            temp = temp->right;
        else
            return false;
    }

    // Now attach the new node to the node that back points to
    if(back == NULL) // Attach as root node in a new tree
        root = newNode;

    else
    {
        if(newNode->ID < back->ID)
            back->left = newNode;
        else if (newNode->ID > back->ID)
            back->right = newNode;
        else
            return false;
    }

   return true;
}


//--------------------------------------------
// Function: Insert()
// Insert a new node into the tree.
// Preconditions: None
// Returns: int (TRUE if successful, FALSE otherwise)
//--------------------------------------------
bool bstree::Insert(unsigned int Key, string first_name, string last_name)
{
     employee *newNode;

    // Create the new node and copy data into it
    newNode = new employee();
    newNode->ID = Key;
    newNode->first_name = first_name;
    newNode->last_name = last_name;
    newNode->left = newNode->right = NULL;

    // Call other Insert() to do the actual insertion
    return(Insert(newNode));
}

//--------------------------------------------
// Function: Delete()
// Purpose: Delete a node from the tree.
// Preconditions: Tree contains the node to delete
// Returns: int (TRUE if successful, FALSE otherwise)
//--------------------------------------------
bool bstree::Delete(unsigned int Key)
{
    employee *back;
    employee *temp;
    employee *delParent;    // Parent of node to delete
    employee *delNode;      // Node to delete

    temp = root;
    back = NULL;

    // Find the node to delete
    while((temp != NULL) && (Key != temp->ID))
    {
        back = temp;
        if(Key < temp->ID)
            temp = temp->left;
        else
            temp = temp->right;
    }

    if(temp == NULL) // Didn't find the one to delete
        return false;

    else
    {
        if(temp == root) // Deleting the root
        {
            delNode = root;
            delParent = NULL;
        }
        else
        {
            delNode = temp;
            delParent = back;
        }
    }

    // Case 1: Deleting node with no children or one child
    if(delNode->right == NULL)
    {
        if(delParent == NULL)    // If deleting the root
        {
            root = delNode->left;
            delete delNode;
            return true;
        }
        else
        {
            if(delParent->left == delNode)
                delParent->left = delNode->left;
            else
                delParent->right = delNode->left;
                delete delNode;
            return true;
        }
    }
    else // There is at least one child
    {
        if(delNode->left == NULL)    // Only 1 child and it is on the right
        {
            if(delParent == NULL)    // If deleting the root
            {
                root = delNode->right;
                delete delNode;
                return true;
            }
            else
            {
                if(delParent->left == delNode)
                    delParent->left = delNode->right;
                else
                    delParent->right = delNode->right;
                delete delNode;
                return true;
            }
        }
        else // Case 2: Deleting node with two children
        {
            // Find the replacement value.  Locate the node
            // containing the largest value smaller than the
            // key of the node being deleted.
            temp = delNode->left;
            back = delNode;
            while(temp->right != NULL)
            {
                back = temp;
                temp = temp->right;
            }
            // Copy the replacement values into the node to be deleted
            delNode->ID = temp->ID;
            delNode->first_name = temp->first_name;
            delNode->last_name = temp->last_name;

            // Remove the replacement node from the tree
            if(back == delNode)
                back->left = temp->left;
            else
                back->right = temp->left;
            delete temp;
            return true;
        }
    }
}


//--------------------------------------------
// Function: PrintOne()
// Purpose: Print data in one node of a tree.
// Preconditions: None
// Returns: void
//--------------------------------------------
void bstree::PrintOne(employee *T)
{
    cout << T->ID << "\t\t" << T->first_name << "\t\t" << T->last_name << endl;
}



//--------------------------------------------
// Function: PrintAll()
// Purpose: Print the tree using a recursive
//        traversal
// Preconditions: None
// Returns: void
//--------------------------------------------
void bstree::PrintAll(employee *T)
{
    if(T != NULL)
    {
        PrintAll(T->left);
        PrintOne(T);
        PrintAll(T->right);
    }
}


//--------------------------------------------
// Function: PrintTree()
// Purpose: Print the tree using a recursive
//        traversal.  This gives the user access
//        to PrintAll() without giving access to
//        the root of the tree.
// Preconditions: None
// Returns: void
//--------------------------------------------
void bstree::PrintTree()
{
    PrintAll(root);
}


void bstree::saveToFile(const char * fileName)
{
    ofstream file_writer;
    file_writer.open(fileName);
    saveToFile(file_writer, root);
    file_writer.close();
}

void bstree::saveToFile(ofstream & file_writer, employee * T)
{
    if (T != NULL)
    {
        saveToFile(file_writer, T->left);
        file_writer << T->last_name;
        file_writer << "\t";
        file_writer << T->first_name;
        file_writer << "\t";
        file_writer << T->ID;
        file_writer << "\n";
        saveToFile(file_writer, T->right);
    }

}

Answer 1

Neither of the employee constructors initialize either the left or right pointers to NULL. this is particularly worrisome for the copy-constructor, but the parameterized constructor is where the pain will really show through:

When loading from a file you do this:

tree.Insert(new employee(first_name, last_name, ID));

which fires this constructor:

employee(std::string first_name, std::string last_name, unsigned int ID)
{
    this->first_name = first_name;
    this->last_name = last_name;
    this->ID = ID;
}

Nowhere in the above are the left and right member pointers assigned to anything. Thus they are indeterminate and therefore garbage. so when you do this:

bool bstree::Insert(employee *newNode)
{
    employee *temp;
    employee *back;

    temp = root;
    back = NULL;

    while(temp != NULL) // Loop till temp falls out of the tree
    {
        back = temp;
        if(newNode->ID < temp->ID)
            temp = temp->left;
        else if (newNode->ID > temp->ID)
            temp = temp->right;
        else
            return false;
    }

    // Now attach the new node to the node that back points to
    if(back == NULL) // Attach as root node in a new tree
        root = newNode;

    else
    {
        if(newNode->ID < back->ID)
            back->left = newNode;
        else if (newNode->ID > back->ID)
            back->right = newNode;
        else
            return false;
    }

   return true;
}

you're chasing pointers that are not valid, and indeed cannot even be evaluated much less dereferenced without invoking undefined behavior.

This is not going to turn into an online debugging session. You need to properly initialize all members of your object class, ideally in the initializer list:

class employee
{
public:

    // note: this shouldn't even be *needed*
    employee() : ID(), left(), right() {}

    // parameterized constructor
    employee(const std::string& first, const std::string& last, unsigned int id)
        : first_name(first)
        , last_name(last)
        , ID(id)
        , left(), right()
    {
    }

     // copy-ctor. retains values; child pointers set as null
    employee(const employee& obj)
        : first_name(obj.first_name)
        , last_name(obj.last_name)
        , ID(obj.id)
        , left(), right()
    {
    }

    // assignment operator. does NOT copy child pointers
    employee& operator =(const employee& obj)
    {
        first_name = obj.first_name;
        last_name = obj.last_name;
        ID = obj.ID;
    }

    std::string first_name;
    std::string last_name;
    unsigned int ID;
    employee * left, * right;
};

Normally I would code the assignment operator to use the copy-constructor by implementing the copy/swap idiom. but in this case it would be overkill, since your object has no actual dynamic-managed members ( i.e. members the object itself is actually responsible for creating/destroying).

Anyway, the above is a big issue, and I did NOT take the time to dissect the actual tree management code beyond the insertion logic. I wouldn't be surprised if there were a defect lurking in the Delete operation, which is always tedious for binary trees. But this should be enough to get you further down the road.

Answer 2

My question is: What could be causing this problem, considering the code worked fine on my own machine?

There are several possibilities. Your program could be running into some resource constraint (e.g. memory). It is also possible that it exhibits undefined behaviour.

The first thing I would do is obtain the stack trace from the crash.

Additionally, I would run the program under valgrind, to see if it spots any problems.

Answer 3

You're doing a shallow copy of Employee as if it was a trivially copyable type, which it is not.

You should be using a copy constructor. This code is wrong, and will result in undefined behaviour.

Since I can't see the rest of the program I can't tell whether this would cause the problem, but it's a place to start.