Preprocessor: Fix unpredicatable result of BinaryHeap::WasInserted()

[GoogleCodeExporter]

Hi,

we had an uninitialized memory issue in the BinaryHeap.

From the patch:
------------------------------------------------------
The problem was that the BinaryHeap::nodeIndex
was not initialized at all. This will give
(very slightly) unpredictable contraction results.

We can't initialize with zero as it's a valid node id.

valgrind reported:
==11698== Conditional jump or move depends on uninitialised value(s)
==11698==    at 0x44D61D: BinaryHeap<unsigned int, unsigned int, unsigned int, 
Contractor::_HeapData, ArrayStorage<unsigned int, unsigned int> 
>::WasInserted(unsigned int) (binaryheap.h:138)
==11698==    by 0x44DA60: bool 
Contractor::_Contract<true>(Contractor::_ThreadData*, unsigned int, 
Contractor::_ContractionInformation*) (contractor.h:508)
==11698==    by 0x447029: Contractor::_Evaluate(Contractor::_ThreadData*, 
Contractor::_PriorityData*, unsigned int) (contractor.h:464)
==11698==    by 0x43EB57: Contractor::Run() [clone ._omp_fn.1] 
(contractor.h:262)
==11698==    by 0x446383: Contractor::Run() (contractor.h:257)
==11698==    by 0x43D1EF: ContractionHierarchies::Preprocess(IImporter*, 
QString) (contractionhierarchies.cpp:88)
==11698==    by 0x417FBB: runRouting(QString, IImporter*, IPreprocessor*, 
IPreprocessor*, PackerInfo) (pluginmanager.cpp:424)
==11698==    by 0x4193F8: PluginManager::processRoutingModule(QString, QString, 
QString, QString, bool) (pluginmanager.cpp:550)
==11698==    by 0x422AB3: main (console-main.cpp:295)
==11698== 
==11698== Use of uninitialised value of size 8
==11698==    at 0x44D638: BinaryHeap<unsigned int, unsigned int, unsigned int, 
Contractor::_HeapData, ArrayStorage<unsigned int, unsigned int> 
>::WasInserted(unsigned int) (binaryheap.h:140)
==11698==    by 0x44DA60: bool 
Contractor::_Contract<true>(Contractor::_ThreadData*, unsigned int, 
Contractor::_ContractionInformation*) (contractor.h:508)
==11698==    by 0x447029: Contractor::_Evaluate(Contractor::_ThreadData*, 
Contractor::_PriorityData*, unsigned int) (contractor.h:464)
==11698==    by 0x43EB57: Contractor::Run() [clone ._omp_fn.1] 
(contractor.h:262)
==11698==    by 0x446383: Contractor::Run() (contractor.h:257)
==11698==    by 0x43D1EF: ContractionHierarchies::Preprocess(IImporter*, 
QString) (contractionhierarchies.cpp:88)
==11698==    by 0x417FBB: runRouting(QString, IImporter*, IPreprocessor*, 
IPreprocessor*, PackerInfo) (pluginmanager.cpp:424)
==11698==    by 0x4193F8: PluginManager::processRoutingModule(QString, QString, 
QString, QString, bool) (pluginmanager.cpp:550)
==11698==    by 0x422AB3: main (console-main.cpp:295

Original issue reported on code.google.com by t...@simonv.com on 2 Jun 2013 at 12:10

Attachments:

• 0001-Fix-use-of-uninitialized-memory-in-binary-heap.patch