[Bug libstdc++/23244] New: __gnu_cxx::hash_map inconsistent iterator behavior

[jzampier at gmail dot com]

The iterators over hash_map behave in a manner inconsistent with the other
std::map, std::list, etc... data structures. This can cause segfaults which are
hard to root-cause. Sample Code Included with additional information:

Specifically, the iterators over hash_map require the 'first' datamember to
be valid until the iterator has advanced past that point. (see code for clarity)
The iterator operator++ should not depend on being able to call the
hash functor on that data member to advance. Because, as in the example, 
you can't call the functor when the pointer has been deleted.

This behavior happens on other hosts of g++ (tested on 3.4.3, linux). (I just
have cygwin on here...)

The offending code is placed in #if 0 and #endif directives.

While this isn't a bug per se, it is a problem with the behavior of 
hash_map that should at least be documented in LARGE letters 
in the hash_map, if not fixed to work like the rest of the stl.

// $Id$
// Program: hashbroke
// Purpose: To demonstrate how __gnu_cxx::hash_map is broken. (sorta)
// Author: Jeffrey Zampieron
// License: GPL.

#include <iostream>
#include <ext/hash_map>
#include <map>

using namespace std;
using namespace __gnu_cxx;

typedef struct {
  size_t operator()( const string* str ) const {
    return __gnu_cxx::__stl_hash_string( str->c_str() );
  }
} strptrhash;

typedef struct {
  bool operator()( const string* lhs, const string* rhs ) const {
    return *lhs == *rhs;
  }
} strptrequal;

typedef struct {
  bool operator()( const string* lhs, const string* rhs ) const {
    return *lhs < *rhs;
  }
} strptrless;

typedef hash_map< string*, string*, strptrhash, strptrequal > StringPtrHash;
typedef std::map< string*, string*, strptrless > StringPtrMap;

int main() {
  StringPtrHash testhash;
  // test keys
  string* k1 = new string( "key1" );
  string* k2 = new string( "key2" );
  string* k3 = new string( "key3" );
  string* k4 = new string( "key4" );
  string* k5 = new string( "key5" );
  string* k6 = new string( "key6" );

  // test vals
  string* v1 = new string( "val1" );
  string* v2 = new string( "val2" );
  string* v3 = new string( "val3" );
  string* v4 = new string( "val4" );
  string* v5 = new string( "val5" );
  string* v6 = new string( "val6" );

  testhash[ k1 ] = v1;
  testhash[ k2 ] = v2;
  testhash[ k3 ] = v3;
  testhash[ k4 ] = v4;
  testhash[ k5 ] = v5;
  testhash[ k6 ] = v6;
  
  cout << "Hash:\n";
  for( StringPtrHash::iterator iter = testhash.begin(); 
       iter != testhash.end();
       iter++ ) {
    cout << "Key: " << *( iter->first ) << endl;
    cout << "Val: " << *( iter->second ) << endl;
  }

  // this SHOULD be valid.
  // and is for std::map
  // but causes a segfault here.
#if 0
  for( StringPtrHash::iterator iter = testhash.begin(); 
       iter != testhash.end();
       iter++ ) {
    delete( iter->first );
    delete( iter->second );
  }
#endif 

  // Work around:
  string* prev = __null;
  for( StringPtrHash::iterator iter = testhash.begin(); 
       iter != testhash.end();
       iter++ ) {
    delete( prev );
    delete( iter->second );
    prev = iter->first;
  }
  delete( prev );

  // That this works with map:
  StringPtrMap testmap;
  k1 = new string( "key1" );
  k2 = new string( "key2" );
  k3 = new string( "key3" );
  k4 = new string( "key4" );
  k5 = new string( "key5" );
  k6 = new string( "key6" );
  
  // test vals
  v1 = new string( "val1" );
  v2 = new string( "val2" );
  v3 = new string( "val3" );
  v4 = new string( "val4" );
  v5 = new string( "val5" );
  v6 = new string( "val6" );
  

  testmap[ k1 ] = v1;
  testmap[ k2 ] = v2;
  testmap[ k3 ] = v3;
  testmap[ k4 ] = v4;
  testmap[ k5 ] = v5;
  testmap[ k6 ] = v6;

  cout << "\nMap:\n";
  for( StringPtrMap::iterator iter = testmap.begin(); 
       iter != testmap.end();
       iter++ ) {
    cout << "Key: " << *( iter->first ) << endl;
    cout << "Val: " << *( iter->second ) << endl;
  }

  // works like map should.
  for( StringPtrMap::iterator iter = testmap.begin(); 
       iter != testmap.end();
       iter++ ) {
    delete( iter->first );
    delete( iter->second );
  }
 
  // The problem seems to be that the 
  // operator++ in the hash_map iterator
  // needs to call the function provided 
  // by strptrhash in order to advance...
  // but in my example that pointer has been deleted...
  // hence the segfault.
  // This is apparent if you run valgrind on the exec.
  // (I don't have it on this machine, or I'd include the output)

  // Why is this the case? Iterating over a map
  // should not require computation of a hash key.
  // While not really a bug, this is a caveat that should
  // be documented somewhere, or ideally fixed
  // Notice that map does not call strptrcmp to advance the iterator

}

-- 
           Summary: __gnu_cxx::hash_map inconsistent iterator behavior
           Product: gcc
           Version: 3.4.4
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: libstdc++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: jzampier at gmail dot com
                CC: gcc-bugs at gcc dot gnu dot org
 GCC build triplet: i686-pc-cygwin
  GCC host triplet: i686-pc-cygwin
GCC target triplet: i686-pc-cygwin


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23244