AVL Tree Memory issues with destructor

Question

I'm trying to implement AVL Tree in C++, but I'm stuck with the insertion, I have changed some things but nothing seemed to effectively solve the problem. I used Xcode's Address Sanitizer and I'm getting that error after inserting a second element into the tree:

Thread 1: Use of deallocated memory detected. ==3822==ERROR: AddressSanitizer: heap-use-after-free on address.....

This is the implementation of the tree so far:

RoadTree.hpp

#ifndef RoadTree_hpp
#define RoadTree_hpp

#include "Road.hpp"

class RoadTree {

private:
    struct TreeNode {
        Road *key;
        TreeNode *rightChild;
        TreeNode *leftChild;
        int height;

        TreeNode() : key(NULL), rightChild(NULL), leftChild(NULL), height(0) { }
        TreeNode(Road *r) : key(r), rightChild(NULL), leftChild(NULL), height(0) { }
    };

    TreeNode *root;
    int numberOfRoads;

    int GetHeight(TreeNode *n) const;
    void SimpleRightRotation(TreeNode *&n);
    void DoubleRightRotation(TreeNode *&n);
    void SimpleLeftRotation(TreeNode *&n);
    void DoubleLeftRotation(TreeNode *&n);
    void Insert(TreeNode *&n, Road *r);
    void ClearTree(TreeNode *&n);
    void PreOrder(TreeNode *n) const;

public:
    RoadTree();
    ~RoadTree();
    void Insert(Road *r);
    Road *FindRoad(string destination);
    void ListRoads();
    void ClearTree();
    void PreOrder();

    inline int RoadCount() {
        return numberOfRoads;
    }
};

#endif /* RoadTree_hpp */

RoadTree.cpp

#include "RoadTree.hpp"

RoadTree::RoadTree() : root(NULL), numberOfRoads(0) { }

RoadTree::~RoadTree() {
    ClearTree(root);
}

void RoadTree::Insert(Road *r) {
    Insert(root, r);
}

int RoadTree::GetHeight(TreeNode *n) const {
    if (n == NULL)
        return -1;
    else
        return n->height;
}

void RoadTree::SimpleRightRotation(TreeNode *&n) {
    TreeNode *tempNode = n->rightChild;
    n->rightChild = tempNode->leftChild;
    tempNode->leftChild = n;

    n->height = 1 + max(GetHeight(n->leftChild), GetHeight(n->rightChild));
    n = tempNode;
    tempNode->height = 1 + max(n->height, GetHeight(tempNode->rightChild));
}

void RoadTree::DoubleRightRotation(TreeNode *&n) {
    SimpleLeftRotation(n->rightChild);
    SimpleRightRotation(n);
}

void RoadTree::SimpleLeftRotation(TreeNode *&n) {
    TreeNode *tempNode = n->leftChild;
    n->leftChild = tempNode->rightChild;
    tempNode->rightChild = n;

    n->height = 1 + max(GetHeight(n->leftChild), GetHeight(n->rightChild));
    n = tempNode;
    tempNode->height = 1 + max(n->height, GetHeight(n->leftChild));
}

void RoadTree::DoubleLeftRotation(TreeNode *&n) {
    SimpleRightRotation(n->leftChild);
    SimpleLeftRotation(n);
}

void RoadTree::ClearTree(TreeNode *&n) {
    if (n != NULL) {
        ClearTree(n->rightChild);
        ClearTree(n->leftChild);
        delete n;
    }

    n = NULL;
}

void RoadTree::Insert(TreeNode *&n, Road *r) {
    if (n == NULL) {
        n = new TreeNode(r);
        numberOfRoads++;
    } else {
        if (r->GetDestination() < n->key->GetDestination()) {
            Insert(n->leftChild, r);
            if ((GetHeight(n->leftChild) - GetHeight(n->rightChild)) == 2) {
                if (r->GetDestination() < n->leftChild->key->GetDestination())
                    SimpleLeftRotation(n);
                else
                    DoubleLeftRotation(n);
            }
        } else if (r->GetDestination() > n->key->GetDestination()) {
            Insert(n->rightChild, r);
            if ((GetHeight(n->rightChild) - GetHeight(n->leftChild)) == 2) {
                if (r->GetDestination() > n->rightChild->key->GetDestination())
                    SimpleRightRotation(n);
                else
                    DoubleRightRotation(n);
            }
        } else if (r->GetDestination() == n->key->GetDestination())
            n->key->SetRoad(r->GetDestination(), r->GetCost(), r->GetInfo());
    }

    n->height = 1 + max(GetHeight(n->leftChild), GetHeight(n->rightChild));
}

Road *RoadTree::FindRoad(string destination) {
    TreeNode *n = root;
    while (n != NULL) {
        string current = n->key->GetDestination();
        if (destination < current)
            n = n->leftChild;
        else if (destination > current)
            n = n->rightChild;
        else if (destination == current)
            return n->key;
    }

    return NULL;
}

void RoadTree::PreOrder(TreeNode *n) const {
    if (n != NULL) {
        cout << " " << n->key->GetDestination() << " ";
        PreOrder(n->leftChild);
        PreOrder(n->rightChild);
    }
}

void RoadTree::PreOrder() {
    PreOrder(root);
}

void RoadTree::ListRoads() {

}

void RoadTree::ClearTree() {
    ClearTree(root);
}

And this is the implementation of Road:

Road.hpp

#ifndef Road_hpp
#define Road_hpp

#include <iostream>

using namespace std;

class Road {

private:
    string destination;
    int cost;
    string info;

public:
    Road();
    Road(string destination, int cost, string info);

    inline string GetDestination() {
        return destination;
    }

    inline int GetCost() {
        return cost;
    }

    inline string GetInfo() {
        return info;
    }
};

#endif /* Road_hpp */

Road.cpp

#include "Road.hpp"

Road::Road() {
    destination = "";
    cost = 0;
    info = "";
}

Road::Road(string destination, int cost, string info) {
    this->destination = destination;
    this->cost = cost;
    this->info = info;
}

The only way I can insert more than 1 element is leaving the destructor blank, then no error shows, so I don't know what's causing it to fail. The error is showing up at the Insertion method, in the line that compares the elements in order to advance in the tree.

Update: Since this is part of a bigger project, I'm almost 100% sure that the problem isn't from the tree's implementation (I put the tree and Road class in a separate project and everything worked as intended). The full project has a class called Place, it has a name and info, as well as an AVL Tree for each place (where I store the place's roads). Those places are stored in a Hash Table (that I have implemented myself).

This is the implementation of the Place class:

Place.hpp

#ifndef Place_hpp
#define Place_hpp

#include <iostream>
#include "Road.hpp"
#include "RoadTree.hpp"

using namespace std;

class Place {

private:
    string name;
    string info;
    RoadTree adjacentRoads;

public:
    Place();
    Place(string name, string info);
    void InsertRoad(Road *r);
    Road *FindRoad(string destination);
    void ListRoads();

    inline string GetName() {
        return name;
    }

    inline string GetInfo() {
        return info;
    }

    inline void SetPlace(string newName, string newInfo) {
        name = newName;
        info = newInfo;
    }

    inline void Write() {
        cout << name << endl;
        cout << "Info: " << info << endl;
    }
};

Place.cpp

#include "Place.hpp"

Place::Place() {
    name = "";
    info = "";
}

Place::Place(string name, string info) {
    this->name = name;
    this->info = info;
}

void Place::InsertRoad(Road *r) {
    adjacentRoads.Insert(r);
}

Road *Place::FindRoad(string destination) {
    return adjacentRoads.FindRoad(destination);
}

void Place::ListRoads() {
    adjacentRoads.ListRoads();
}

This is how I get a pointer from the Hash Table (if the full code is needed tell me):

Place *HashTable::Find(string key) {
    unsigned long hashedKey = HashFunction(key);

    list<Place>::iterator current;

    for (current = table[hashedKey].begin(); current != table[hashedKey].end(); current++) {
        Place currentPlace = *current;
        if (currentPlace.GetName() == key)
            return &*current;
    }

    return NULL;
}

And this is an example of a main that gives me the Thread 1: Use of deallocated memory detected. error

int main(int argc, const char * argv[]) {
    //Declare a HashTable to store Places
    HashTable map;

    //Declare some places
    Place p1("Murcia", "10");
    Place p2("Lorca", "11");
    Place p3("Cartagena", "12");
    Place p4("Zaragoza", "13");
    Place p5("Madrid", "14");
    Place p6("Galicia", "15");

    //Insert those places into the HashTable
    map.Insert(p1);
    map.Insert(p2);
    map.Insert(p3);
    map.Insert(p4);
    map.Insert(p5);
    map.Insert(p6);

    //Declare some roads
    Road *r1 = new Road(p2.GetName(), 20, "asdgasdg");
    Road *r2 = new Road(p3.GetName(), 61, "asdgsw2");

    //Get a pointer of a place from the HashTable to insert roads in it
    Place *p1f = map.Find(p1.GetName());

    //Check if it's not null, if it's not then insert the first road, 
    //get a pointer of it and print the name        
    if (p1f != NULL) {
        p1f->InsertRoad(r1);
        Road *r1f = p1f->FindRoad(p2.GetName());
        cout << r1f->GetDestination() << endl;
    }

    //Get pointer of a place again (each time you want to insert a road
    //in a place you must get it's pointer from the HashTable
    Place *p2f = map.Find(p1.GetName());

    //Checks again and insert second road, then throws error after that
    if (p2f != NULL) {
        p2f->InsertRoad(r2);
        Road *r2f = p1f->FindRoad(p3.GetName());
        cout << r2f->GetDestination() << endl;
    }

    return 0;

Update 2: Added HashTable implementation

HashTable.hpp

#ifndef HashTable_hpp
#define HashTable_hpp

#include "Place.hpp"
#include <list>

class HashTable {

private:
    list<Place> *table;
    int numberOfEntries;
    int currentTableSize;
    float maxLoadFactor;

    unsigned int HashFunction(string key);
    bool LoadFactorExceeded();
    void ResizeTable();
    bool IsPrime(int number);
    int NextPrime(int number);

public:
    HashTable();
    ~HashTable();
    void Insert(Place p);
    Place *Find(string key);
    void EmptyTable();
    void ListPlaces();

    inline int Count() {
        return numberOfEntries;
    }
};

#endif /* HashTable_hpp */

HashTable.cpp

#include "HashTable.hpp"
#include <algorithm>

const int START_SIZE = 101;

HashTable::HashTable() {
    table = new list<Place>[START_SIZE];
    numberOfEntries = 0;
    maxLoadFactor = 2.0f;
    currentTableSize = START_SIZE;

    for (int i = 0; i < START_SIZE; i++) {
        table[i].clear();
    }
}

HashTable::~HashTable() {
    delete [] table;
}

unsigned int HashTable::HashFunction(string key) {
    unsigned long hashValue = 0;

    for (int i = 0; i < key.length(); i++)
        hashValue = 47 * hashValue + key[i];

    return (hashValue % currentTableSize);
}

bool HashTable::LoadFactorExceeded() {
    float currentLoadFactor = numberOfEntries / currentTableSize;

    if (currentLoadFactor > maxLoadFactor)
        return true;
    else
        return false;
}

void HashTable::ResizeTable() {
    list<Place> *oldTable = table;
    int oldTableSize = currentTableSize;

    currentTableSize *= 2;
    currentTableSize = NextPrime(currentTableSize);
    table = new list<Place>[currentTableSize];
    for (int i = 0; i < currentTableSize; i++)
        table[i].clear();

    numberOfEntries = 0;

    for (int i = 0; i < oldTableSize; i++) {
        list<Place>::iterator current;
        for (current = oldTable[i].begin(); current != oldTable[i].end(); current++)
            Insert(*current);
    }

    delete [] oldTable;
}

bool HashTable::IsPrime(int number) {
    if (number % 2 == 0 || number % 3 == 0)
        return false;

    int divisor = 6;
    while (divisor * divisor - 2 * divisor + 1 <= number) {
        if (number % (divisor - 1) == 0)
            return false;

        if (number % (divisor + 1) == 0)
            return false;

        divisor += 6;
    }

    return true;
}

int HashTable::NextPrime(int number) {
    while (!IsPrime(++number)) {}
    return number;
}

void HashTable::Insert(Place p) {

    unsigned long hashedKey = HashFunction(p.GetName());

    list<Place>::iterator current = table[hashedKey].begin();

    if (!table[hashedKey].empty()) {
        for (current = table[hashedKey].begin(); current != table[hashedKey].end(); current++) {
            Place &currentPlace = *current;

            if (currentPlace.GetName() == p.GetName()) {
                currentPlace.SetPlace(p.GetName(), p.GetInfo());
                break;
            } else if (current == --table[hashedKey].end()) {
                table[hashedKey].push_back(p);
                numberOfEntries++;
            }
        }
    } else {
        table[hashedKey].push_back(p);
        numberOfEntries++;
    }

    if (LoadFactorExceeded())
        ResizeTable();
}

Place *HashTable::Find(string key) {
    unsigned long hashedKey = HashFunction(key);

    list<Place>::iterator current;

    for (current = table[hashedKey].begin(); current != table[hashedKey].end(); current++) {
        Place currentPlace = *current;
        if (currentPlace.GetName() == key)
            return &*current;
    }

    return NULL;
}

void HashTable::EmptyTable() {
    for (int i = 0; i < currentTableSize; i++) {
        table[i].clear();
    }

    table = new list<Place>[START_SIZE];
    numberOfEntries = 0;
    currentTableSize = START_SIZE;
}

void HashTable::ListPlaces() {
    list<string> places;

    for (int i = 0; i < currentTableSize; i++) {
        list<Place>::iterator current;
        for (current = table[i].begin(); current != table[i].end(); current++)
            places.push_back(current->GetName());
    }

    places.sort();

    for (list<string>::iterator current = places.begin(); current != places.end(); current++)
        cout << *current << endl;

    cout << "Total: " << numberOfEntries << " lugares" << endl;
}

What could be causing the problem?

Answer 1

I'm not sure if this is it, but I noticed something: it looks like a linked list, and your recursive ClearTree function will attempt to free items repeatedly:

void RoadTree::ClearTree(TreeNode *&n) {
    if (n != NULL) {
        ClearTree(n->rightChild);
        ClearTree(n->leftChild);
        delete n;
    }
    n = NULL;
}

Assuming there are 2 elements in the list, and we call it with the first element:

   ClearTree( firstElement );

It will then first

        ClearTree(n->rightChild);   // 2nd element

which in turn will first call

       ClearTree(n->rightChild);    // non-existing 3rd element: NOP

and proceed with

       ClearTree(n->leftChild);     // first element again

Maybe if you didn't get the error, this would recurse until you get a stack overflow?

You could simply remove the call to ClearTree(n->leftChild) to fix it; the function will recurse across the rightChild until it reaches the end, then delete the nodes from last to first when it backtracks.

Perhaps it's better to just iterate over the list: (untested, hope this works)

TreeNode * cur = n;
while ( cur != NULL )
    TreeNode * next = n->rightChild;
    delete cur;
    cur = next;
}
n = NULL;

UPDATE

I've found the problem. Here's my debug output:

> g++ -O0 -g *cpp && gdb ./a.out
(gdb) r
Starting program: /home/kenney/roadtree/a.out
= INITIALIZING PLACES =
--> RoadTree[0x7fffffffe1a0] CONSTRUCTOR root: 0
--> RoadTree[0x7fffffffe1c0] CONSTRUCTOR root: 0
--> RoadTree[0x7fffffffe1e0] CONSTRUCTOR root: 0
--> RoadTree[0x7fffffffe200] CONSTRUCTOR root: 0
--> RoadTree[0x7fffffffe220] CONSTRUCTOR root: 0
--> RoadTree[0x7fffffffe240] CONSTRUCTOR root: 0
= INSERTING PLACES =
<-- RoadTree[0x7fffffffe340] DESTRUCTOR! root: 0
<-- RoadTree[0x7fffffffe360] DESTRUCTOR! root: 0
<-- RoadTree[0x7fffffffe380] DESTRUCTOR! root: 0
<-- RoadTree[0x7fffffffe3a0] DESTRUCTOR! root: 0
<-- RoadTree[0x7fffffffe3c0] DESTRUCTOR! root: 0
<-- RoadTree[0x7fffffffe3e0] DESTRUCTOR! root: 0
= CREATING ROADS =

These are the p1..p6 and the map.Insert(p1..p6). There's already a hint that something is wrong. Next this code is run:

cout << "= p1 =\n";
Place *p1f = map.Find(p1.GetName());
cout << "found " << p1f << " for " << p1.GetName() << "\n";

Producing this debug output:

= p1 =
<-- RoadTree[0x7fffffffe110] DESTRUCTOR! root: 0
found 0x6098f0 for Murcia

Then,

if (p1f != NULL) {
    p1f->InsertRoad(r1);
    Road *r1f = p1f->FindRoad(p2.GetName());
    cout << r1f->GetDestination() << endl;
}

outputting this debug from RoadTree::Insert, indicating that the first if statement's 'then' is executed, assigning a new TreeNode to n:

  n null, allocating.                                         
--> TreeNode[0x609ad0] CONSTRUCTOR
  allocated TreeNode 0x609ad0 key: 0x609a60 dest: Lorca
Lorca

So far so good, now the same again for p2. First the output of map.Find:

= p2 =       
FINDING Murcia
<-- RoadTree[0x7fffffffe110] DESTRUCTOR! root: 0x609ad0
!!! RoadTree::ClearTree:: delete 0x609a60
<-- TreeNode[0x609ad0] DESTRUCTOR
found 0x6098f0 for Murcia

Next we continue to p2f->InsertRoad(r2); which is basically Place.adjacentroads.Insert aka RoadTree.insert:

  n not null: 0x609ad0 key: 0x609af0

Note the address of n: this is the deleted TreeNode. Here, the 'else' of the 'if' in RoadTree::Insert is taken since n != NULL:

    if (r->GetDestination() < n->key->GetDestination()) {

is executed, causing:

Program received signal SIGSEGV, Segmentation fault.
0x00007ffff7b9126b in std::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string(std::string const&) ()
   from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
(gdb) bt
#0  0x00007ffff7b9126b in std::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string(std::string const&) ()
   from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#1  0x00000000004046b3 in Road::GetDestination (this=0x609af0) at Road.hpp:20
#2  0x0000000000405121 in RoadTree::Insert (this=0x609900, n=@0x609900: 0x609ad0, r=0x609ab0) at RoadTree.cpp:75
#3  0x0000000000404c0d in RoadTree::Insert (this=0x609900, r=0x609ab0) at RoadTree.cpp:15
#4  0x0000000000404845 in Place::InsertRoad (this=0x6098f0, r=0x609ab0) at Place.cpp:14
#5  0x000000000040401d in main (argc=1, argv=0x7fffffffe5f8) at main.cpp:63
(gdb)

The fault is apparent in the n->key->GetDestination() which attempts to return a copy of a string that is already deleted, causing a segfault because some pointers are already overwritten.

The problem is in HashTable::Find, which does this:

      Place currentPlace = *current;
      if (currentPlace.GetName() == key)
          return &*current;

which constructs a Place copy on the stack that gets destroyed when the method returns. The private fields of Place also get destroyed, including the string name, which was attempted to be returned by Road::GetDestination().

Replacing it with this with this solves it:

      if (current->GetName() == key)
          return &*current;

I'm not sure this is the only fix needed, but it's a step.