Access Violation exception thrown on delete Keyword

Question

For some reason, after AddToBinarySearchTree is called, an exception is thrown from the ~BinarySearchTreeNode<T> destructor. I think this could be happening because the Node itself is deleted before the tree is deleted - but I don't think this is the case.

Why would calling delete m_left; throw the following exception?

Access violation reading location 0xFEEEFEF2

int _tmain(int argc, _TCHAR* argv[])
{
    void AddToBinarySearchTree(BinarySearchTree<T> bst, T value) {
        bst.Add(value);
    }

    void MyMethod() {
        BinarySearchTree<int> bstStack;
        bstStack.Add(5)
        // the exception is thrown after this line of code executes
        AddToBinarySearchTree(bstStack, 1000);
    }
}

// BinarySearchTreeNode<T>
template <typename>
BinarySearchTreeNode {
public:
    BinarySearchTreeNode<T>::~BinarySearchTreeNode() {
        // executing the following line of code throws the exception
        delete this->m_left;
        this->m_left = NULL;
        delete this->m_right;
        this->m_right = NULL;
    }
};

// BinarySearchTree<T>
template <typename T>
class BinarySearchTree {
    BinarySearchTree<T>::~BinarySearchTree() {
        delete m_head;
        m_head = NULL;
    }

    void BinarySearchTree<T>::Add(T value) {
        Add(new BinarySearchTreeNode<T>(value));
    }

    AddRecursive(BinarySearchTreeNode<T>* node, BinarySearchTreeNode<T>* parentNode) {
        if (node->GetValue() < parentNode->GetValue()) {
            if (!parentNode->GetLeft()) {
                parentNode->SetLeft(node);
            }
            else {
                this->AddRecursive(node, parentNode->GetLeft());
            }
        }
        else if (node->GetValue() > parentNode->GetValue()) {
            if (!parentNode->GetRight()){
                parentNode->SetRight(node);
            }
            else {
                this->AddRecursive(node, parentNode->GetRight());
            }
        }
    }
};

Note: some class details have been omitted

Still too many details omitted, but based on the pointer value it looks like you're deleting something twice. — nobody, May 23 '14 at 19:51
Just saying, I almost always do a `if (x) {delete x; x=NULL;}` to prevent errors from double deallocations (which usually only comes up with move-style stuff if you do your code properly). In the case of things like your tree, it'll stop double-deletes from causing you problems. In this case, you are getting the error because you're not following the rule of three. — IdeaHat, May 23 '14 at 19:54
@MadScienceDreams: (A) that `if (x)` is completely unnecessary, and (B) it wouldn't have helped in this situation at all, because of the rule of three violation you mentioned. — Mooing Duck, May 23 '14 at 19:57
@MooingDuck Wow...complete correct, never knew. The problem is completely he didn't follow the rule of 3 though. — IdeaHat, May 23 '14 at 19:59

score 3 · Accepted Answer · edited May 23 '17 at 11:54

"Access violation" in a destructor means the pointer is invalid. Usually that the destructor has already been called.

"reading location 0xFEEEFEF2" tells us a little more. Namely, when the debugging runtime frees memory, it fills it with the pattern 0xFEEEFEEE (That look familiar?), which affirms our believe that the object containing the pointer has already been freed. (more info: https://stackoverflow.com/a/127404/845092)

The object with the pointer is a BinarySearchTreeNode, which means that node has already been freed, and you are freeing it a second time. As to how that is coming about, you'll have to examine the code that you didn't paste here. The first things I would check are the copy constructor and copy assignment operator.

Curg noted the missing reference in AddToBinarySearchTree. This tells me it's your copy constructor, probably that you didn't make one. When you call AddToBinarySearchTree, the function is making a brand new BinarySearchTree on the stack that probably refers to the same nodes, and then you're adding to the copy. Then when the function ends, the copy is being destroyed, freeing the nodes. Then MyMethod ends, and it attempts to destroy the original, which tries to free those same nodes a second time.

You're right about it missing the copy constructor. The Node itself is a pointer so I think that is how the same Node is being deleted twice. — Ian R. O'Brien, May 23 '14 at 20:00
That was exactly it. Added a copy constructor to do the following: `m_head = new BinarySearchTreeNode(); *m_head = *other.m_head;` — Ian R. O'Brien, May 23 '14 at 20:08
@IanO'Brien: Well, you have to copy all of the nodes, not just the head... — Mooing Duck, May 23 '14 at 20:11
Just noticed this in the debugger. I am working on the method now to walk the tree and copy all of the nodes. — Ian R. O'Brien, May 23 '14 at 20:14

score 1 · Answer 2 · answered May 23 '14 at 20:02

I decided to put this into an answer. As Curg said, the problem arises when you pass by value instead of reference into "AddToBinarySearchTree".

HOWEVER THIS IS NOT YOUR BUG. This is just when your bug appears.

It appears because when you call the function, you make a shallow copy of the class, including all pointer values. Then when the function is over, that instance goes out of scope. It cleans up itself (correctly) leaving dangling pointers in the instance it was copied from. When you try to clean that up, you get the error. The compiler puts FEEEEFEEE in memory it has freed.

The bug is that you aren't following the RULE OF THREE, which is (Wikipedia):

A class defines one of the following it should probably explicitly define all three:

destructor
copy constructor
copy assignment operator

So you're missing a copy constuctor and copy assignment operator (which should do a deep copy).

Access Violation exception thrown on delete Keyword

2 Answers2