CODEWITHSUNDEEP
c++11memory-leaksbinary-search-tree
granite chimp
granite chimp

Reputation: 21

C++ binary search tree template class memory leak

Newbie question. I am trying to program a binary search tree, but even a simple insert has a memory leak.

File Node.h

template<typename X> struct Node {
   X value;
   Node* left;
   Node* right;

   Node(X x) {
      this->value = x;
      this->left = nullptr;
      this->right = nullptr;
   }
};

File BST.h

template <typename X> class BST {
   public:
      BST() { root = nullptr; }

      bool Insert(const X& x) { return InsertAt(root, x); }

   private:

      bool InsertAt(Node<X>*& node, const X& x)
      {
         if (node == nullptr) {
            node = new Node<X>(x);
            return true;
         }

         if (node->value == x)
            return false;

         if (*(node->value) > *x)
            return InsertAt(node->left, x);

         return InsertAt(node->right, x);
      }

//----

      Node<X>* root;
};

The main program

#include "Node.h"
#include "BST.h"

int main(int argc, char **argv)
{
   BST<int*> bst;
   bst.Insert(new int(8));
}

The output of g++ -g -fsanitize=address -fno-omit-frame-pointer -std=c++11 B.cpp ==10646==ERROR: LeakSanitizer: detected memory leaks

Direct leak of 24 byte(s) in 1 object(s) allocated from:
    #0 0x7fb5e7f45532 in operator new(unsigned long) (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x99532)
    #1 0x400eb7 in BST<int*>::InsertAt(Node<int*>*&, int* const&) /home/gc/BST.h:12
    #2 0x400e68 in BST<int*>::Insert(int* const&) /home/gc/BST.h:5
    #3 0x400d09 in main /home/gc/B.cpp:22
    #4 0x7fb5e778082f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)

Indirect leak of 4 byte(s) in 1 object(s) allocated from:
    #0 0x7fb5e7f45532 in operator new(unsigned long) (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x99532)
    #1 0x400caf in main /home/gc/B.cpp:22
    #2 0x7fb5e778082f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)

SUMMARY: AddressSanitizer: 28 byte(s) leaked in 2 allocation(s).

First, why am I getting a memory leak? Second, why am I getting a message about new(unsigned long) when there is nothing unsigned long about my program? Thanks.

You may tell me to use smart pointers, but for right now I'm just trying to educate myself about pointers and trying to figure out why this doesn't work.

Upvotes: 2

Views: 994

Answers (1)

hegel5000
hegel5000

Reputation: 884

If you're not going to use smart pointers, then you have to pair every new with a delete. Since your calls to new happen in each class's constructor, you can delete in the destructor.

Anyways, in BST the destructor should be

~BST() { delete root; }

And in Node, it's

~Node() { delete left; delete right; }

This will recursively work it's way down the tree. Your recursive case is when a pointer to a node is not null. Unlike with free which crashes on a null, delete simply does nothing, making nullptr your base case.

Check out http://en.cppreference.com/w/cpp/language/destructor

Upvotes: 1

Related Questions