Memory corruption when using IterableValueMap on Class derived from lemon Graph

[Alpar Juttner]

A post from Bernhard Kausler on lemon-devel@…:

The following code causes a memory access error.

• Tested for lemon 1.2.1 and the latest lemon-main sources
• Doesn't happen for other graph maps like IdMap?

---

#include <lemon/list_graph.h>
#include <lemon/maps.h>

using namespace lemon;

class MyGraph : public ListDigraph {
};

int main() {
  MyGraph derived;
  IterableValueMap<MyGraph, MyGraph::Node, int> derived_m2(derived);

  derived.addNode();

  return 0;
}

---

gdb backtrace:
#0  0x00000000004059a3 in lemon::IterableValueMap<MyGraph,
lemon::ListDigraphBase::Node, int>::unlace (this=0x7fffffffdcf0,
key=...) at lemon-main/lemon/maps.h:3098
#1  0x0000000000405050 in lemon::IterableValueMap<MyGraph,
lemon::ListDigraphBase::Node, int>::add (this=0x7fffffffdcf0, key=...)
at lemon-main/lemon/maps.h:3255
#2  0x00000000004026ab in
lemon::AlterationNotifier<lemon::DigraphExtender<lemon::ListDigraphBase>, lemon::ListDigraphBase::Node>::add
(this=0x7fffffffdcc0, item=...) at
/home/bkausler/loca/include/lemon/bits/alteration_notifier.h:356
#3  0x00000000004018a7 in
lemon::DigraphExtender<lemon::ListDigraphBase>::addNode
(this=0x7fffffffdc80) at
/home/bkausler/local/include/lemon/bits/graph_extender.h:269
#4  0x00000000004012c8 in lemon::ListDigraph::addNode
(this=0x7fffffffdc80) at lemon-main/lemon/list_graph.h:352
#5  0x0000000000400f54 in main () at inheritance-bug.cpp:15

[Alpar Juttner]

From: Bernhard Kausler

Dear all,

the bug was caused by uninitialized "next" and "prev" fields in struct IterableValueMapNode (resp. struct IterableIntMapNode) in maps.h. Please find attached a patch​ for the lemon-main branch, that fixes the problem. (The patch is valid for lemon-1.2.1, too).

Best, Bernhard Kausler