I am new to c++ programming, and am having a lot of difficulty tracing down a memory leak, Can you help me find where this is happening? This is what valgrind says:
> ==9851== Memcheck, a memory error detector
==9851== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==9851== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==9851== Command: ./lab6 in81.txt out.txt
==9851==
==9851==
==9851== HEAP SUMMARY:
==9851== in use at exit: 72,760 bytes in 2 blocks
==9851== total heap usage: 198 allocs, 196 frees, 130,465 bytes allocated
==9851==
==9851== 56 bytes in 1 blocks are definitely lost in loss record 1 of 2
==9851== at 0x4C2E0EF: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==9851== by 0x4025EF: AVLTREE<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >::insert(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&, AVLTREE<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >::node*&) (AVLtree.h:228)
==9851== by 0x402666: AVLTREE<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >::insert(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&, AVLTREE<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >::node*&) (AVLtree.h:234)
==9851== by 0x4026AA: AVLTREE<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >::insert(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&, AVLTREE<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >::node*&) (AVLtree.h:239)
==9851== by 0x402666: AVLTREE<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >::insert(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&, AVLTREE<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >::node*&) (AVLtree.h:234)
==9851== by 0x401F74: AVLTREE<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >::insert(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&) (AVLtree.h:297)
==9851== by 0x4016FE: interpretLine(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, AVLTREE<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >&, std::__cxx11::basic_stringstream<char, std::char_traits<char>, std::allocator<char> >&) (Main.cpp:20)
==9851== by 0x401BF3: loadFile(char*, std::__cxx11::basic_stringstream<char, std::char_traits<char>, std::allocator<char> >&) (Main.cpp:68)
==9851== by 0x401E6A: main (Main.cpp:91)
==9851==
==9851== 72,704 bytes in 1 blocks are still reachable in loss record 2 of 2
==9851== at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==9851== by 0x4EC3EFF: ??? (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21)
==9851== by 0x40104E9: call_init.part.0 (dl-init.c:72)
==9851== by 0x40105FA: call_init (dl-init.c:30)
==9851== by 0x40105FA: _dl_init (dl-init.c:120)
==9851== by 0x4000CF9: ??? (in /lib/x86_64-linux-gnu/ld-2.23.so)
==9851== by 0x2: ???
==9851== by 0xFFF000626: ???
==9851== by 0xFFF00062D: ???
==9851== by 0xFFF000636: ???
==9851==
==9851== LEAK SUMMARY:
==9851== definitely lost: 56 bytes in 1 blocks
==9851== indirectly lost: 0 bytes in 0 blocks
==9851== possibly lost: 0 bytes in 0 blocks
==9851== still reachable: 72,704 bytes in 1 blocks
==9851== suppressed: 0 bytes in 0 blocks
==9851==
==9851== For counts of detected and suppressed errors, rerun with: -v
==9851== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
This is my Insert Function:
int insert(someType& someData, node*& currentSpot)
{
int i = 0; //i is nodes height.
bool isRight = false;
if (currentSpot == NULL)
{
currentSpot = new node(someData);
size++;
return 1;
}
if (someData < currentSpot->data)
{
i = insert(someData, currentSpot->kids[0]);
isRight = false;
}
else if (someData > currentSpot->data)
{
i = insert(someData, currentSpot->kids[1]);
isRight = true;
}
//rebalancing the tree;
rebalance(currentSpot, isRight);
//adjusting the height of the tree after rebalancing it.
currentSpot->adjustHeight();
return ++i;
}
This is what my remove function looks like:
bool remove(someType& d, node*& n)
{
//not passing by reference, in order to use recursion as a stack
if (n == nullptr) return false;
bool found;
if (d > n->data)
{
found = remove(d, n->kids[1]);
}
else if (d < n->data)
{
found = remove(d, n->kids[0]);
}
else if (d == n->data)
{
//use ctr
// take min value from
if (n->kids[1] != nullptr)
{
// case 1
// 2
// \
// 3
// ...
someType minimumValue;
minValue(n->kids[1], minimumValue);
n->data = minimumValue;
rebalance(n, n->tallerChild());
n->adjustHeight();
}
else if (n->kids[0] != nullptr)
{
//case 2
// 5
// /
// 4
// ......
node* temp = n;
n = n->kids[0];
n->adjustHeight();
size--;
delete temp;
}
else
{
if (n == root) root = nullptr;
node* temp = n;
n = nullptr;
size--;
delete temp;
}
//found and eliminated, tree integrity has been preserved.
return true;
}
//after recursively going down to n, going back up the stack adjusting the height
rebalance(n, n->tallerChild());
n->adjustHeight();
return found;
}
These are my destructor & clear function:
void clear()
{
if (root == nullptr) return;
root->clear();
delete root;
root = nullptr;
size = 0;
}
~AVLTREE()
{
clear();
}
This is my nodes clear function:
void clear()
{
if (kids[0] != nullptr)
{
kids[0]->clear();
delete kids[0];
}
if (kids[1] != nullptr)
{
kids[1]->clear();
delete kids[1];
}
}
