   [solved] c++ Memory corruption and unordered_set
  Can anyone see something wrong here ?  Running this program compiled with recent (4.3) g++ gives the following output,test 1.   Item not found in settest 2.   hash 1554188945   hash 1545800337struct A is a pod type having primitive fields so the copy constructor and assignment operator get compiler defaults (I experimented making these explicit.)We should be able to just iterate the memory of A in the hashing function object to yield a hash value. However the unordered_set does not find() an identical value of A that is previously inserted. Additionally, the second simple test of the hash function yields different hashes on the same value of A but *Only* when the first test using the unordered_set is also run prior to it. there is a strong sense of memory being stomped on somewhere.This is the simplest case I could make that produces the error - It works if any of the fields of A (eg x,y,dir,check) are removed  - It works if compiled with optimisation g++ -O2 or O3  - The separate hash test works (yields identical hash values) if we disable the first test (using unordered_set test).#include <iostream>#include <tr1/unordered_set>enum Direction {  UP };struct A{A( signed x, signed y, Direction dir, double check): x( x), y( y), dir( dir), check( check) { } signed x;signed y;Directiondir;doublecheck;};struct hashA{unsigned operator () ( const A &a) const{unsigned char *p = (unsigned char *)&a;unsigned hash = 0x12345;for( unsigned i = 0; i < sizeof( A); ++i){hash = ((hash<<5)^(hash>>27)) ^ p;} <span class="cpp-keyword">return</span> hash;}};<span class="cpp-keyword">struct</span> equalA{<span class="cpp-keyword">bool</span> <span class="cpp-keyword">operator</span> () ( <span class="cpp-keyword">const</span> A &amp;a, <span class="cpp-keyword">const</span> A &amp;b) <span class="cpp-keyword">const</span>{<span class="cpp-keyword">return</span> a.x == b.x&amp;&amp; a.y == b.y&amp;&amp; a.dir == b.dir&amp;&amp; a.check == b.check ; } };<span class="cpp-keyword">int</span> main(){#<span class="cpp-keyword">if</span> <span class="cpp-number">1</span> {<span class="cpp-comment">// unordered set test</span>std::cout &lt;&lt; <span class="cpp-literal">"test 1."</span> &lt;&lt; std::endl;<span class="cpp-keyword">typedef</span> std::tr1::unordered_set&lt; A, hashA, equalA&gt;set_type;set_types;Aa1( <span class="cpp-number">100</span>, <span class="cpp-number">100</span>, UP, <span class="cpp-number">123</span>);s.insert( a1);Aa2( <span class="cpp-number">100</span>, <span class="cpp-number">100</span>, UP, <span class="cpp-number">123</span>);set_type::iterator ip = s.find( a2);<span class="cpp-keyword">if</span>( ip == s.end()) std::cout &lt;&lt; <span class="cpp-literal">"\tItem not found in set"</span> &lt;&lt; std::endl;<span class="cpp-keyword">else</span>  std::cout &lt;&lt; <span class="cpp-literal">"\tOK"</span> &lt;&lt; std::endl; }<span class="cpp-directive">#endif</span>#<span class="cpp-keyword">if</span> <span class="cpp-number">1</span>{<span class="cpp-comment">// simple hash function test</span>std::cout &lt;&lt; <span class="cpp-literal">"test 2."</span> &lt;&lt; std::endl;Aa1( <span class="cpp-number">100</span>, <span class="cpp-number">100</span>, UP, <span class="cpp-number">123</span>);std::cout &lt;&lt; <span class="cpp-literal">"\thash "</span> &lt;&lt; hashA()( a1) &lt;&lt; std::endl;Aa2( <span class="cpp-number">100</span>, <span class="cpp-number">100</span>, UP, <span class="cpp-number">123</span>);std::cout &lt;&lt; <span class="cpp-literal">"\thash "</span> &lt;&lt; hashA()( a2) &lt;&lt; std::endl;}<span class="cpp-directive">#endif</span>}</pre></div><!–ENDSCRIPT–>Edit: source rather than code tags<!–EDIT–><span class=editedby><!–/EDIT–>[Edited by - chairthrower on May 7, 2009 2:02:54 PM]<!–EDIT–></span><!–/EDIT–>
Quote:Original post by chairthrowerWe should be able to just iterate the memory of A in the hashing function object to yield a hash value.That's only true if the structure doesn't have any padding, and if your floating point system doesn't have any logically identical values that have different binary representations. In particular, if your enum doesn't take up the same size as an int, you're probably going to have empty space.   ;  Thanks SiCrane,Your correct, I have managed to get away with this so far for pod types - But an additional test shows,sizeof( A)  gives 24 bytessizeof( signed) * 2 + sizeof( Direction) + sizeof( double)) gives 20 bytesThe enum in there is forcing an extra 4 bytes of padding which is getting filled randomly and corrupting the hash.Funny how after going through the process of clarifying things in a post and then 5 minutes later the problem reveals itself.;Quote:Original post by chairthrowerThe enum in there is forcing an extra 4 bytes of padding which is getting filled randomly and corrupting the hash.Actually, what looks like is happening is that the enum is 4 bytes, but the double is getting aligned to a multiple of 8. If you move the double to before one or more of the other member variables, it should reduce the size of the struct down to 20.   