[Boost-bugs] [Boost C++ Libraries] #7903: boost::heap::fibonacci_heap::erase() does not reset top_element after the last element is erased

Subject: [Boost-bugs] [Boost C++ Libraries] #7903: boost::heap::fibonacci_heap::erase() does not reset top_element after the last element is erased
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2013-01-18 14:53:57

#7903: boost::heap::fibonacci_heap::erase() does not reset top_element after the
last element is erased
-----------------------------------------+----------------------------------
 Reporter:  Yin Qiu <qiuyi.n@…>          |       Owner:  timblechmann
     Type:  Bugs                         |      Status:  new         
Milestone:  To Be Determined             |   Component:  heap        
  Version:  Boost Development Trunk      |    Severity:  Problem     
 Keywords:                               |  
-----------------------------------------+----------------------------------
 When a fibonacci heap contains only one element, calling
 `fibonacci_heap::erase()` deallocates that element's memory, changes the
 heap size to 0, but does not reset the `top_element` member, leaving it a
 dangling pointer.

 This member is however used in the `push()` function:

 {{{#!cpp
   if (!top_element || super_t::operator()(top_element->value, n->value))
       top_element = n;
 }}}

 Calling the comparison operator would result in an invalid read.

 Code to reproduce (confirmed by valgrind memcheck):

 {{{#!cpp
 using namespace boost::heap;

 fibonacci_heap<int> fh;
 fh.erase(fh.push(1));
 fh.push(2); // invalid memory access here
 }}}

 I don't know if the heap is supposed to be used like this, but I've
 attached a patch anyway, which simply resets `top_element` in the
 `consolidate()` function.

 Thanks.

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/7903>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.