[Lemon-user] bug in ListDigraph::erase(Node &) ?

[Alpár Jüttner]

Hi Duraid,

> > For example, when you double delete an item, Valgind (http://valgrind.org/
> > , the most useful debugging tool for C/C++) will point out the array
> > underindexing with the current code, but not with your modification.
> 
> Not always! In fact, most of the time Valgrind won't say anything,
> because so long as array[-2] is still inside valid memory (which it
> might tend to be, statistically speaking), Valgrind doesn't report
> anything. (I've just observed exactly this behaviour in my code.)

I think you are not right. Valgrind uses a much more sophisticated
technique to localize wrong memory usage. For example I have just tried
this simple code:

#include<lemon/list_graph.h>
using namespace lemon;
int main()
{
  ListDigraph g;
  ListDigraph::Node n = g.addNode();
  g.erase(n);
  g.erase(n);  
}

On my laptop it compiles and runs with no error (exactly because
nodes[-2] point to a valid memory block), but valgrind immediately
reports about the wrong memory usage:

$ ./test/double_erase_test 
$ valgrind test/double_erase_test 
==10533== Memcheck, a memory error detector
==10533== Copyright (C) 2002-2010, and GNU GPL'd, by Julian Seward et
al.
==10533== Using Valgrind-3.6.1 and LibVEX; rerun with -h for copyright
info
==10533== Command: test/double_erase_test
==10533== 
==10533== Invalid write of size 4
==10533==    at 0x80510DA:
lemon::ListDigraphBase::erase(lemon::ListDigraphBase::Node const&)
(list_graph.h:231)
==10533==    by 0x8051896:
lemon::DigraphExtender<lemon::ListDigraphBase>::erase(lemon::ListDigraphBase::Node const&) (graph_extender.h:307)
==10533==    by 0x8051419:
lemon::ListDigraph::erase(lemon::ListDigraphBase::Node)
(list_graph.h:370)
==10533==    by 0x8050D69: main (double_erase_test.cc:11)
==10533==  Address 0x4309014 is not stack'd, malloc'd or (recently)
free'd
==10533== 
==10533== 
==10533== HEAP SUMMARY:
==10533==     in use at exit: 0 bytes in 0 blocks
==10533==   total heap usage: 1 allocs, 1 frees, 16 bytes allocated
==10533== 
==10533== All heap blocks were freed -- no leaks are possible
==10533== 
==10533== For counts of detected and suppressed errors, rerun with: -v
==10533== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 3 from 3)

Regards,
Alpar