Opened 5 years ago

#13088 new Bugs

Boost::binomial_heap Merge memcheck error

Reported by: jun.kudo@… Owned by: timblechmann
Milestone: To Be Determined Component: heap
Version: Boost 1.64.0 Severity: Problem
Keywords: Cc:

Description

Binomial heap merge routine reads from uninitialized memory in the attached example.

#include "boost/heap/binomial_heap.hpp"
typedef boost::heap::binomial_heap<int> Heap;

int main(int /*argc*/, char* /*argv*/[]) {
  Heap heap0;
  size_t heap0_size = 3;
  size_t max_range = 100;
  for (size_t ix = 0; ix < heap0_size; ++ix) {
    heap0.push(rand() % max_range);
  }

  Heap heap1; 
  size_t heap1_size = 5;
  for (size_t ix = 0; ix < heap1_size; ++ix) {
    heap1.push(rand() % max_range);
  }
  heap0.merge(heap1);  
}

I believe the error stems from the case identified by line 699 in binomial_heap.hpp. If the last node of trees is erased in this line (as is the case in this example), this_iterator now points to trees.end(). However, for this case, it will follow the goto statement and start another iteration which will cause the function to again read from this_iterator.

Attachments (2)

main3.cpp (437 bytes ) - added by jun.kudo@… 5 years ago.
valgrind.txt (2.6 KB ) - added by anonymous 5 years ago.

Download all attachments as: .zip

Change History (2)

by jun.kudo@…, 5 years ago

Attachment: main3.cpp added

by anonymous, 5 years ago

Attachment: valgrind.txt added
Note: See TracTickets for help on using tickets.