https://svn.boost.org/trac10/ticket/7903 <p> When a fibonacci heap contains only one element, calling <code>fibonacci_heap::erase()</code> deallocates that element's memory, changes the heap size to 0, but does not reset the <code>top_element</code> member, leaving it a dangling pointer. </p> <p> This member is however used in the <code>push()</code> function: </p> <div class="wiki-code"><div class="code"><pre> <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">top_element</span> <span class="o">||</span> <span class="n">super_t</span><span class="o">::</span><span class="k">operator</span><span class="p">()(</span><span class="n">top_element</span><span class="o">-&gt;</span><span class="n">value</span><span class="p">,</span> <span class="n">n</span><span class="o">-&gt;</span><span class="n">value</span><span class="p">))</span> <span class="n">top_element</span> <span class="o">=</span> <span class="n">n</span><span class="p">;</span> </pre></div></div><p> Calling the comparison operator would result in an invalid read. </p> <p> Code to reproduce (confirmed by valgrind memcheck): </p> <div class="wiki-code"><div class="code"><pre><span class="k">using</span> <span class="k">namespace</span> <span class="n">boost</span><span class="o">::</span><span class="n">heap</span><span class="p">;</span> <span class="n">fibonacci_heap</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">fh</span><span class="p">;</span> <span class="n">fh</span><span class="p">.</span><span class="n">erase</span><span class="p">(</span><span class="n">fh</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="mi">1</span><span class="p">));</span> <span class="n">fh</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="mi">2</span><span class="p">);</span> <span class="c1">// invalid memory access here</span> </pre></div></div><p> I don't know if the heap is supposed to be used like this, but I've attached a patch anyway, which simply resets <code>top_element</code> in the <code>consolidate()</code> function. </p> <p> Thanks. </p> en-us /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/7903 Trac 1.4.3 Yin Qiu <qiuyi.n@…> Fri, 18 Jan 2013 14:54:14 GMT https://svn.boost.org/trac10/ticket/7903 https://svn.boost.org/trac10/ticket/7903 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">erase-last-one.diff</span> </li> </ul> Ticket timblechmann Fri, 18 Jan 2013 15:17:44 GMT https://svn.boost.org/trac10/ticket/7903#comment:1 https://svn.boost.org/trac10/ticket/7903#comment:1 <ul> <li><strong>status</strong> <span class="trac-field-old">new</span> → <span class="trac-field-new">closed</span> </li> <li><strong>resolution</strong> → <span class="trac-field-new">fixed</span> </li> </ul> <p> (In <a class="changeset" href="https://svn.boost.org/trac10/changeset/82534" title="heap: fix fibonacci_heap::erase fixes #7903">[82534]</a>) heap: fix fibonacci_heap::erase </p> <p> fixes <a class="closed ticket" href="https://svn.boost.org/trac10/ticket/7903" title="#7903: Bugs: boost::heap::fibonacci_heap::erase() does not reset top_element after ... (closed: fixed)">#7903</a> </p> Ticket