文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >问答首页 >2-3-4泄漏的析构函数

问2-3-4泄漏的析构函数
EN

Stack Overflow用户
提问于 2013-04-12 03:29:54
回答 3查看 370关注 0票数 1

如果我没有弄错，当涉及到销毁一个2-3-4 tree时，它应该类似于一个二叉树，只有4个子树(递归)。下面我有我的析构函数特定的代码，带有一个简单的递归删除。

问题是我还在泄密。文件只包含我的2-3-4树。

我相信这是为2-3-4 tree实现析构函数的正确方法，但我的实现似乎不正确。有人能指出我逻辑上的错误吗？我做过图表，听起来很不错。

代码语言：javascript
复制
//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;
}

我的节点设计：

代码语言：javascript
复制
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;
};

我的插入码。我目前还没有实现删除功能。

代码语言：javascript
复制
//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 );
        }   
    }
}

瓦兰：

代码语言：javascript
复制
-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$
2-3-4-tree
c++
destructor
EN

回答 3

Stack Overflow用户

发布于 2013-04-12 03:35:36

最好的选择是用std::unique_ptr< Elem >替换原始指针。这样你就根本不需要一个破坏者了。注意，Elem::parent很可能是一个不拥有的指针，因此不应该被替换。

票数 1
EN

Stack Overflow用户

发布于 2013-04-20 14:53:55

对于代码中的漏洞，正如Synxis所提到的，valgrind在这里是一件很棒的事情。您提到它并不有用，但这是因为您没有读取它的输出，这意味着添加了--leak-check=full选项。

完整的valgrind --leak-check-full输出(对我而言)包括以下内容：

代码语言：javascript
复制
==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指针之间来回移动，而不考虑任何验证或可能存在的内容。

例如，这里

代码语言：javascript
复制
node -> cFour = node -> cThree;

如果cFour实际上持有一个有效的对象，那么您就失去了到它的任何链接。在覆盖它们之前，尝试放入代码，检查这些代码是否实际为NULL。

您需要在新、delete和指针赋值代码周围放置一些调试代码，并仔细地遍历代码。

票数 0
EN

Stack Overflow用户

发布于 2014-09-03 16:10:45

试试这个：

代码语言：javascript
复制
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
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：

https://stackoverflow.com/questions/15962556

复制
相关文章

相似问题

领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 粤公网安备44030502008569号

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档