Деструктор на 2-3-4 утечки

Если я не ошибаюсь, когда дело доходит до уничтожения 2-3-4 tree оно должно быть похоже на двоичное дерево, только с 4 дочерними элементами (рекурсивно). Ниже у меня есть мой специфичный для Destructor код с простым рекурсивным удалением.

Проблема в том, что у меня все еще течь. Файл содержит только мое 2-3-4 дерева.

Я считаю, что это правильный метод для реализации деструктора для 2-3-4 treeс, но моя реализация кажется неправильной. Может ли кто-нибудь указать на ошибку в моей логике? Я сделал диаграммы, и кажется, звук.

//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;
}

Мой дизайн узла:

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;
};

Мой код вставки. Я не реализовал функцию удаления на данный момент.

//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$

1

Решение

Лучше всего заменить сырые указатели на std::unique_ptr< Elem >, Таким образом, вам вообще не нужен деструктор. Берегись этого Elem::parent скорее всего, это не принадлежащий указатель, поэтому его не следует заменять.

1

Другие решения

Для вашей утечки в вашем коде, как упомянул Synxis, valgrind — замечательная вещь здесь.
Вы упомянули, что это бесполезно, но это потому, что вы не читали вывод, который предлагал добавить —утечка проверка = полная вариант.

Полный valgrind --leak-check-full вывод (для меня) включает это,

==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==

Гораздо полезнее, поскольку он пытается показать, откуда произошла утечка памяти.

Похоже, у вас есть фундаментальные проблемы с вашей логикой в ​​отношении того, как вы распределяете новые узлы.

Во-первых, ваш код проверки с 4 листами отображает предупреждение, но ничего не делает с переданными указателями, что означает, что ваши переданные указатели не обрабатываются, и вы теряете переданный элемент Elem. Вам необходимо правильно обработать ошибку.

Во-вторых, в большей части кода вы перетасовываете указатели cOne, cTwo, cThree и cFour без какой-либо проверки или рассмотрения того, что там может быть.

Например, здесь

node -> cFour = node -> cThree;

если cFour действительно содержал действительный объект, то вы просто потеряли любую ссылку на него. Попробуйте вставить код, который проверяет, действительно ли они имеют значение NULL, прежде чем перезаписывать их.

Вы должны поместить некоторый код отладки вокруг вашего новый, удалять а также назначение указателя код и шаг за шагом тщательно через ваш код.

0

Попробуй это:

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;
}

}
0
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector