[Bug libstdc++/18633] New: resource allocation problem with __gnu_cxx::hash_map

["work at paul dot dubuc dot org" <gcc-bugzilla at gcc dot gnu dot org>]

The operator[] method on hash_map will unnecessarily resize the container when
used to access an existing element when the container size is at any of the
values in the __stl_prime_list table (ext/hashtable.h).  This unnecessarily
causes the container capacity to double in size and the elements to be rehashed.

There is also a more serious consequence when using operator[] access in a
multithreaded environment which I think adds further justification for the
change.  This caused some controversy on the libstdc++ which I won't repeat
here.  See the following messages (and follow-ups) for details:

http://gcc.gnu.org/ml/libstdc++/2004-11/msg00132.html
http://gcc.gnu.org/ml/libstdc++/2004-11/msg00150.html
http://gcc.gnu.org/ml/libstdc++/2004-11/msg00156.html

The problem could be fixed in ext/hashtable.h by moving the call to resize() to
be after the first return statement:

template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::reference
hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::find_or_insert(const value_type& __obj)
{
  resize(_M_num_elements + 1);	// <- FROM HERE


  size_type __n = _M_bkt_num(__obj);
  _Node* __first = _M_buckets[__n];


  for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
    if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
      return __cur->_M_val;
				// <-- TO HERE
  _Node* __tmp = _M_new_node(__obj);
  __tmp->_M_next = __first;
  _M_buckets[__n] = __tmp;
  ++_M_num_elements;
  return __tmp->_M_val;
}

-- 
           Summary: resource allocation problem with __gnu_cxx::hash_map
           Product: gcc
           Version: 3.4.3
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: libstdc++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: work at paul dot dubuc dot org
                CC: gcc-bugs at gcc dot gnu dot org
  GCC host triplet: sparc-sun-solaris2.8


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