https://stackoverflow.com/questions/15962556
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianYour best bet would be to replace the raw pointers with std::unique_ptr< Elem >. That way you shouldn't need a destructor at all. Watch out that Elem::parent is likely a non-owning pointer so shouldn't be replaced.
Destructor for 2-3-4 leak
-
03-04-2022 - |
Question
If I am not mistaken, when it comes to destruction of a 2-3-4 tree it should be similar to a binary tree, just with 4 children (recursively). Below I have my Destructor-specific code, with a simple recursive delete.
The issue is I still get a leak. The file only contains my 2-3-4 tree.
I believe this to be the correct method to implement a destructor for 2-3-4 trees, but my implementation seems to be incorrect. Could anyone possibly point out a mistake in my logic? I've done diagrams and it seems sound.
//Destructor
template < typename KEY , typename T >
Map< KEY , T >::~Map(){
destructCode();
}
//Common code for deallocation
template < typename KEY , typename T >
void Map< KEY , T >::destructCode(){
destruct( _root );
}
//Recursive delete helper
template < typename KEY , typename T >
void Map< KEY , T >::destruct( Elem* node ){
if( node -> cOne )
destruct( node -> cOne );
if( node -> cTwo )
destruct( node -> cTwo );
if( node -> cThree )
destruct( node -> cThree );
if( node -> cFour )
destruct( node -> cFour );
delete node;
}
My node design:
Elem {
KEY k1, k2, k3;
T t1, t2, t3;
//Children
Elem *cOne, *cTwo, *cThree, *cFour;
Elem *parent;
//numChildren = #node type
//Contains numChildren - 1 data items
int _numChildren;
};
My insertion code. I have not implemented the delete function at this point in time.
//Sorts the keys of the node to include the new keyvalue pairing
template < typename KEY , typename T >
void Map< KEY , T >::keyAdding( KEY k , T t , Elem * node , Elem * smaller , Elem * bigger ){
if( node -> _numChildren == 4 )//3 keys already
cout << "Problem; adding a key to a 4-node" << endl;
else if( node -> _numChildren == 3 ){//2 keys
if( k < node -> k1 ){//Smallest of the three
node -> k3 = node -> k2;
node -> t3 = node -> t2;
node -> k2 = node -> k1;
node -> t2 = node -> t1;
node -> k1 = k;
node -> t1 = t;
node -> cFour = node -> cThree;
node -> cThree = node -> cTwo;
node -> cTwo = bigger;
node -> cOne = smaller;
}
else if( k < node -> k2 ){//Mid
node -> k3 = node -> k2;
node -> t3 = node -> t2;
node -> k2 = k;
node -> t2 = t;
node -> cFour = node -> cThree;
node -> cThree = bigger;
node -> cTwo = smaller;
}
else{//Largest
node -> k3 = k;
node -> t3 = t;
node -> cFour = bigger;
node -> cThree = smaller;
}
node -> _numChildren++;
}
else{//1 key
if( k < node -> k1 ){
node -> k2 = node -> k1;
node -> t2 = node -> t1;
node -> k1 = k;
node -> t1 = t;
node -> cThree = node -> cTwo;
node -> cTwo = bigger;
node -> cOne = smaller;
}
else{
node -> k2 = k;
node -> t2 = t;
node -> cThree = bigger;
node -> cTwo = smaller;
}
node -> _numChildren++;
}
}
//Sorts the keys of the node to include the new keyvalue pairing
template < typename KEY , typename T >
void Map< KEY , T >::keyAdding( KEY k , T t , Elem * node ){
if( node -> _numChildren == 4 )//3 keys already
cout << "Problem; adding a key to a 4-node" << endl;
else if( node -> _numChildren == 3 ){//2 keys
if( k < node -> k1 ){//Smallest of the three
node -> k3 = node -> k2;
node -> t3 = node -> t2;
node -> k2 = node -> k1;
node -> t2 = node -> t1;
node -> k1 = k;
node -> t1 = t;
}
else if( k < node -> k2 ){//Mid
node -> k3 = node -> k2;
node -> t3 = node -> t2;
node -> k2 = k;
node -> t2 = t;
}
else{//Largest
node -> k3 = k;
node -> t3 = t;
}
node -> _numChildren++;
}
else{//1 key
if( k < node -> k1 ){
node -> k2 = node -> k1;
node -> t2 = node -> t1;
node -> k1 = k;
node -> t1 = t;
}
else{
node -> k2 = k;
node -> t2 = t;
}
node -> _numChildren++;
}
}
//Insert, return true if successful.
template < typename KEY , typename T >
bool Map< KEY , T >::insert(KEY k , T t ){
if( _root == 0 ){//Empty
_root = new Elem;
_root -> _numChildren = 2;
_root -> cOne = NULL;
_root -> cTwo = NULL;
_root -> cThree = NULL;
_root -> cFour = NULL;
_root -> k1 = k;
_root -> t1 = t;
_size++;
return true;
}
else
return insert( k , t , _root );
}
//Recursive insert helper
template < typename KEY , typename T >
bool Map< KEY , T >::insert(KEY k , T t , Elem * rRoot ){
Elem * temp = rRoot;
if( temp -> _numChildren == 4 ){//4-node
//Save middle value.
KEY kTemp = temp -> k2;
T tTemp = temp -> t2;
//Remove middle value, making a 3-node.
temp -> k2 = temp -> k3;
temp -> t2 = temp -> t3;
//temp -> k3 = NULL;
//temp -> t3 = NULL;
temp -> _numChildren--;
//Split the (now) 3-node into a pair of 2-nodes
Elem * twoNode1 = new Elem;
twoNode1 -> _numChildren = 2;
twoNode1 -> parent = temp -> parent;
twoNode1 -> cOne = temp -> cOne;
twoNode1 -> cTwo = temp -> cTwo;
twoNode1 -> k1 = temp -> k1;
twoNode1 -> t1 = temp -> t1;
if( twoNode1 -> cOne )
twoNode1 -> cOne -> parent = twoNode1;
if( twoNode1 -> cTwo )
twoNode1 -> cTwo -> parent = twoNode1;
//2-nodes do not have values for these.
twoNode1 -> cThree = NULL;
twoNode1 -> cFour = NULL;
//twoNode1 -> k2 = NULL;
//twoNode1 -> t2 = NULL;
//twoNode1 -> k3 = NULL;
//twoNode1 -> t3 = NULL;
//Second 2-node...
Elem * twoNode2 = new Elem;
twoNode2 -> _numChildren = 2;
twoNode2 -> parent = temp -> parent;
twoNode2 -> cOne = temp -> cThree;
twoNode2 -> cTwo = temp -> cFour;
twoNode2 -> k1 = temp -> k3;
twoNode2 -> t1 = temp -> t3;
if( twoNode2 -> cOne )
twoNode2 -> cOne -> parent = twoNode1;
if( twoNode2 -> cTwo )
twoNode2 -> cTwo -> parent = twoNode1;
//2-Nodes do not have values for these.
twoNode2 -> cThree = NULL;
twoNode2 -> cFour = NULL;
//twoNode2 -> k2 = NULL;
//twoNode2 -> t2 = NULL;
//twoNode2 -> k3 = NULL;
//twoNode2 -> t3 = NULL;
//We're at the root node.
if( temp == _root ){
_root -> _numChildren = 2;
_root -> parent = NULL; //Root has no parent, silly.
_root -> cOne = twoNode1;
_root -> cTwo = twoNode2;
_root -> k1 = kTemp;
_root -> t1 = tTemp;
//2-Nodes do not have values for these.
_root -> cThree = NULL;
_root -> cFour = NULL;
//_root -> k2 = NULL;
//_root -> t2 = NULL;
//_root -> k3 = NULL;
//_root -> t3 = NULL;
//Update split node's parent
twoNode1 -> parent = _root;
twoNode2 -> parent = _root;
//Height has increased.
_height++;
//Ascend to root.
temp = _root;
}
//A generic 4-node somewhere in the tree.
else{
Elem * ntemp = temp;
temp = temp -> parent;
//Update split node's parent
twoNode1 -> parent = temp;
twoNode2 -> parent = temp;
keyAdding( kTemp , tTemp , temp , twoNode1 , twoNode2 );
}
}//4-node end
//Check if leaf
if( temp -> cOne == 0 && temp -> cTwo == 0 && temp -> cThree == 0 && temp -> cFour == 0 ){
keyAdding( k , t , temp );
_size++;
return true;
}
else{
if( temp -> _numChildren == 4 ){
cout << "Should not have a 4-node in leaf-checking.\n";
return -5;
}
else if( temp -> _numChildren == 3 ){
if( k < temp -> k1 )
insert( k , t , temp -> cOne );
else if( k < temp -> k2 )
insert( k , t , temp -> cTwo );
else
insert( k , t , temp -> cThree);
}
else{
if( k < temp -> k1 )
insert( k , t , temp -> cOne );
else
insert( k , t , temp -> cTwo );
}
}
}
Valgrind:
-bash-4.2$ valgrind -v ./a.out
==18357== Memcheck, a memory error detector
==18357== Copyright (C) 2002-2010, and GNU GPL'd, by Julian Seward et al.
==18357== Using Valgrind-3.6.1 and LibVEX; rerun with -h for copyright info
==18357== Command: ./a.out
==18357==
--18357-- Valgrind options:
--18357-- -v
--18357-- Contents of /proc/version:
--18357-- Linux version 3.6.11-1.fc16.i686.PAE (mockbuild@bkernel02) (gcc version 4.6.3 20120306 (Red Hat 4.6.3-2) (GCC) ) #1 SMP Mon Dec 17 21:31:29 UTC 2012
--18357-- Arch and hwcaps: X86, x86-sse1-sse2
--18357-- Page sizes: currently 4096, max supported 4096
--18357-- Valgrind library directory: /usr/lib/valgrind
--18357-- Reading syms from /home/csu/jan99/Documents/CS515/A8/a.out (0x8048000)
--18357-- Reading syms from /usr/lib/valgrind/memcheck-x86-linux (0x38000000)
--18357-- object doesn't have a dynamic symbol table
--18357-- Reading syms from /lib/ld-2.14.90.so (0x463f2000)
--18357-- Considering /usr/lib/debug/.build-id/6f/895b79f95b39ef92d24ff50a16ff774b34b527.debug ..
--18357-- .. build-id is valid
--18357-- Reading suppressions file: /usr/lib/valgrind/default.supp
--18357-- REDIR: 0x4640b610 (strlen) redirected to 0x38052c08 (vgPlain_x86_linux_REDIR_FOR_strlen)
--18357-- REDIR: 0x4640b390 (index) redirected to 0x38052be3 (vgPlain_x86_linux_REDIR_FOR_index)
--18357-- Reading syms from /usr/lib/valgrind/vgpreload_core-x86-linux.so (0x4001000)
--18357-- Reading syms from /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so (0x4004000)
==18357== WARNING: new redirection conflicts with existing -- ignoring it
--18357-- new: 0x4640b390 (index ) R-> 0x04008270 index
==18357== WARNING: new redirection conflicts with existing -- ignoring it
--18357-- new: 0x4640b610 (strlen ) R-> 0x040086d0 strlen
--18357-- Reading syms from /usr/lib/libstdc++.so.6.0.16 (0x46971000)
--18357-- Considering /usr/lib/debug/.build-id/19/bce624dda8659f770012166d85bc075fb23f1a.debug ..
--18357-- .. build-id is valid
--18357-- Reading syms from /lib/libm-2.14.90.so (0x465e7000)
--18357-- Considering /usr/lib/debug/.build-id/b8/362b3b5d82f212d77d69fff8e503ae6fdcfe9b.debug ..
--18357-- .. build-id is valid
--18357-- Reading syms from /lib/libgcc_s-4.6.3-20120306.so.1 (0x4663f000)
--18357-- Considering /usr/lib/debug/.build-id/4b/65b2ab36082e9552ad2014fac436421c4f65ad.debug ..
--18357-- .. build-id is valid
--18357-- Reading syms from /lib/libc-2.14.90.so (0x46417000)
--18357-- Considering /usr/lib/debug/.build-id/ea/4850e94d2deab52b8469f1e68a98f4d6229e48.debug ..
--18357-- .. build-id is valid
--18357-- REDIR: 0x46498a40 (__GI_strrchr) redirected to 0x40080d0 (__GI_strrchr)
--18357-- REDIR: 0x46498780 (__GI_strlen) redirected to 0x40086b0 (__GI_strlen)
--18357-- REDIR: 0x46497fb0 (strcmp) redirected to 0x40014c0 (_vgnU_ifunc_wrapper)
--18357-- REDIR: 0x46562db0 (__strcmp_ssse3) redirected to 0x4009250 (strcmp)
--18357-- REDIR: 0x46498730 (strlen) redirected to 0x40014c0 (_vgnU_ifunc_wrapper)
--18357-- REDIR: 0x4649f3e0 (__strlen_sse2_bsf) redirected to 0x4008690 (strlen)
--18357-- REDIR: 0x46a24350 (operator new(unsigned int)) redirected to 0x4007820 (operator new(unsigned int))
--18357-- REDIR: 0x46499fa0 (memcpy) redirected to 0x40014c0 (_vgnU_ifunc_wrapper)
--18357-- REDIR: 0x4655ab70 (__memcpy_ssse3) redirected to 0x4009420 (memcpy)
--18357-- REDIR: 0x464994c0 (bcmp) redirected to 0x40014c0 (_vgnU_ifunc_wrapper)
--18357-- REDIR: 0x46565c10 (__memcmp_ssse3) redirected to 0x4009fd0 (bcmp)
1
1
1
1
1
1
1
one
five
ten
twenty
twenty-five
thirty
One-hundred
Delete
--18357-- REDIR: 0x46a221d0 (operator delete(void*)) redirected to 0x4006b10 (operator delete(void*))
Delete
Delete
Delete
--18357-- REDIR: 0x464943e0 (free) redirected to 0x4006e80 (free)
==18357==
==18357== HEAP SUMMARY:
==18357== in use at exit: 86 bytes in 3 blocks
==18357== total heap usage: 12 allocs, 9 frees, 375 bytes allocated
==18357==
==18357== Searching for pointers to 3 not-freed blocks
==18357== Checked 97,132 bytes
==18357==
==18357== LEAK SUMMARY:
==18357== definitely lost: 48 bytes in 1 blocks
==18357== indirectly lost: 38 bytes in 2 blocks
==18357== possibly lost: 0 bytes in 0 blocks
==18357== still reachable: 0 bytes in 0 blocks
==18357== suppressed: 0 bytes in 0 blocks
==18357== Rerun with --leak-check=full to see details of leaked memory
==18357==
==18357== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
==18357== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
-bash-4.2$
Pas de solution correcte
Autres conseils
For your leak in your code, as Synxis has mentioned, valgrind is a wonderful thing here. You mentioned that it wasn't useful, but that's because you didn't read its output which suggested adding the --leak-check=full option.
The full valgrind --leak-check-full output (for me) includes this,
==4327== HEAP SUMMARY:
==4327== in use at exit: 376 bytes in 8 blocks
==4327== total heap usage: 42 allocs, 34 frees, 2,036 bytes allocated
==4327==
==4327== Searching for pointers to 8 not-freed blocks
==4327== Checked 186,824 bytes
==4327==
==4327== 156 (96 direct, 60 indirect) bytes in 1 blocks are definitely lost in loss record 7 of 8
==4327== at 0x4C2AF8E: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4327== by 0x401FB2: Map<std::string, std::string>::insert(std::string, std::string, Map<std::string, std::string>::Elem*) (code.cpp:272)
==4327== by 0x401B79: Map<std::string, std::string>::insert(std::string, std::string) (code.cpp:249)
==4327== by 0x401177: main (code.cpp:411)
==4327==
==4327== 220 (96 direct, 124 indirect) bytes in 1 blocks are definitely lost in loss record 8 of 8
==4327== at 0x4C2AF8E: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4327== by 0x4020C4: Map<std::string, std::string>::insert(std::string, std::string, Map<std::string, std::string>::Elem*) (code.cpp:296)
==4327== by 0x401B79: Map<std::string, std::string>::insert(std::string, std::string) (code.cpp:249)
==4327== by 0x401177: main (code.cpp:411)
==4327==
==4327== LEAK SUMMARY:
==4327== definitely lost: 192 bytes in 2 blocks
==4327== indirectly lost: 184 bytes in 6 blocks
==4327== possibly lost: 0 bytes in 0 blocks
==4327== still reachable: 0 bytes in 0 blocks
==4327== suppressed: 0 bytes in 0 blocks
==4327==
Much more helpful, since it tries to show from where the leaked memory originated.
You seem to have fundamental problems with your logic in regards to how you allocate new nodes.
Firstly, your 4 leaf validation code displays a warning, but doesn't do anything with the passed pointers, which means your passed pointers aren't processed and you lose the Elem that you pass in. You need to handle the error case properly.
Secondly, in most of your code, you shuffle around your cOne, cTwo, cThree and cFour pointers without any validation or regard for what may be there.
For example, here
node -> cFour = node -> cThree;
if cFour actually held a valid object, then you've just lost any link to it. Try putting in code that checks if these actually have NULL there or not, before you overwrite them.
You need to put some debug code around your new, delete and pointer assignment code and step carefully through your code.
Try this:
template<typename KEY, typename T> inline Map<Key, T>::~Map()
{
DestroyTree(_root);
}
template<typename KEY, typename T> void Map<Key, T>::DestroyTree(Elem *current)
{
if (current == nullptr) {
return;
}
switch (current->_numChildren) {
case 2: // two node
DestroyTree(current->cOne);
DestroyTree(current->cTwo);
delete current;
break;
case 3: // three node
DestroyTree(current->cOne);
DestroyTree(current->cTwo);
DestroyTree(current->cThree);
delete current;
break;
case 4: // four node
DestroyTree(current->cOne);
DestroyTree(current->cTwo);
DestroyTree(current->cThree);
DestroyTree(current->cFour);
delete current;
break;
}
}
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
