[v3] fix libstdc++/52446

[Paolo Carlini]

Hi,
>
>     Here a patch proposition to fix PR 52446.
>
>     I have introduce 2 version of the _M_rehash method. One used when 
> keys are unique which is very close to the existing one. The second 
> that take care of keeping equivalent keys relative order on rehash. 
> The second one might seem complicated but I wanted to avoid to 
> recompute a bucket index each time we find an equivalent element. If 
> the hash code is cached it is ok but if it is not I prefer to limit 
> the number of time it is recalculated.
>
> 2012-03-13  François Dumont <fdumont@gcc.gnu.org>
>
>     PR libstdc++/52446
>     * include/bits/hashtable.h (_Hashtable<>::_M_rehash): Split into 2
>     methods, the first, copy of the existing one, is used when keys
>     are unique, the second purpose is to keep equivalent keys relative
>     orders.
The "purpose of the second", maybe? Can we use a new name for the new 
functions, instead of overloading? A descriptive name or suffix would 
add clarity to the code.

>     * testsuite/23_containers/unordered_multimap/insert/52446.cc: New.
>
> Tested under linux x86_64.
>
> If ok tell me if I must also apply it to 4.7 branch.
We are going to fix this in mainline and, then, if everything goes well, 
in 4.7.1.

Minor nits:
>
> François
>
>
> 52446.patch
>
>
> Index: include/bits/hashtable.h
> ===================================================================
> --- include/bits/hashtable.h	(revision 185352)
> +++ include/bits/hashtable.h	(working copy)
> @@ -596,6 +596,11 @@
>         // reserve, if present, comes from _Rehash_base.
>
>       private:
> +      // Rehash method when keys are unique
> +      void _M_rehash(size_type __n, std::true_type);
A blank line here.
> +      // Rehash method when there might be equivalent keys.
> +      void _M_rehash(size_type __n, std::false_type);
> +
>         // Unconditionally change size of bucket array to n, restore hash policy
>         // state to __state on exception.
>         void _M_rehash(size_type __n, const _RehashPolicyState&  __state);
> @@ -1592,41 +1597,141 @@
>       {
>         __try
>   	{
> -	  _Bucket* __new_buckets = _M_allocate_buckets(__n);
> -	  _Node* __p = _M_begin();
> -	  _M_before_begin._M_nxt = nullptr;
> -	  std::size_t __cur_bbegin_bkt;
> -	  while (__p)
> +	  _M_rehash(__n, integral_constant<bool, __uk>());
> +	}
> +      __catch(...)
> +	{
> +	  // A failure here means that buckets allocation failed.  We only
> +	  // have to restore hash policy previous state.
> +	  _M_rehash_policy._M_reset(__state);
> +	  __throw_exception_again;
> +	}
> +    }
> +
> +  template<typename _Key, typename _Value,
> +	   typename _Allocator, typename _ExtractKey, typename _Equal,
> +	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
> +	   bool __chc, bool __cit, bool __uk>
> +    void
> +    _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
> +	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
> +    _M_rehash(size_type __n, std::true_type)
> +    {
> +      // This version of rehash do not have to care about equivalent elements
> +      // relative order.
> +      _Bucket* __new_buckets = _M_allocate_buckets(__n);
> +      _Node* __p = _M_begin();
> +      _M_before_begin._M_nxt = nullptr;
> +      std::size_t __cur_bbegin_bkt;
> +      while (__p)
> +	{
> +	  _Node* __next = __p->_M_next();
> +	  std::size_t __new_index = _HCBase::_M_bucket_index(__p, __n);
> +	  if (!__new_buckets[__new_index])
>   	    {
> -	      _Node* __next = __p->_M_next();
> -	      std::size_t __new_index = _HCBase::_M_bucket_index(__p, __n);
> -	      if (!__new_buckets[__new_index])
> +	      __p->_M_nxt = _M_before_begin._M_nxt;
> +	      _M_before_begin._M_nxt = __p;
> +	      __new_buckets[__new_index] =&_M_before_begin;
> +	      if (__p->_M_nxt)
> +		__new_buckets[__cur_bbegin_bkt] = __p;
> +	      __cur_bbegin_bkt = __new_index;
> +	    }
> +	  else
> +	    {
> +	      __p->_M_nxt = __new_buckets[__new_index]->_M_nxt;
> +	      __new_buckets[__new_index]->_M_nxt = __p;
> +	    }
> +	  __p = __next;
> +	}
> +      _M_deallocate_buckets(_M_buckets, _M_bucket_count);
> +      _M_bucket_count = __n;
> +      _M_buckets = __new_buckets;
> +    }
> +
> +  template<typename _Key, typename _Value,
> +	   typename _Allocator, typename _ExtractKey, typename _Equal,
> +	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
> +	   bool __chc, bool __cit, bool __uk>
> +    void
> +    _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
> +	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
> +    _M_rehash(size_type __n, std::false_type)
> +    {
> +      // This version of rehash must guaranty that equivalent elements relative
> +      // order is preserve.
> +      _Bucket* __new_buckets = _M_allocate_buckets(__n);
> +      _Node* __p = _M_begin();
> +      _M_before_begin._M_nxt = nullptr;
> +      std::size_t __cur_bbegin_bkt;
> +      std::size_t __prev_index;
> +      _Node* __prev_p = nullptr;
> +      bool __check_next_bucket = false;
> +      while (__p)
> +	{
> +	  bool __check_now = true;
> +	  _Node* __next = __p->_M_next();
> +	  std::size_t __new_index = _HCBase::_M_bucket_index(__p, __n);
> +	  if (!__new_buckets[__new_index])
> +	    {
> +	      __p->_M_nxt = _M_before_begin._M_nxt;
> +	      _M_before_begin._M_nxt = __p;
> +	      __new_buckets[__new_index] =&_M_before_begin;
> +	      if (__p->_M_nxt)
> +		__new_buckets[__cur_bbegin_bkt] = __p;
> +	      __cur_bbegin_bkt = __new_index;
> +	    }
> +	  else
> +	    {
> +	      if (__prev_p&&  __prev_index == __new_index)
>   		{
> -		  __p->_M_nxt = _M_before_begin._M_nxt;
> -		  _M_before_begin._M_nxt = __p;
> -		  __new_buckets[__new_index] =&_M_before_begin;
> -		  if (__p->_M_nxt)
> -		    __new_buckets[__cur_bbegin_bkt] = __p;
> -		  __cur_bbegin_bkt = __new_index;
> +		  // Previous insert was already in this bucket, we insert after
> +		  // the previously inserted one to preserve equivalent elements
> +		  // relative order.
> +		  __p->_M_nxt = __prev_p->_M_nxt;
> +		  __prev_p->_M_nxt = __p;
And here. As a general style, I would say always when the comment itself 
is preceded by code != open curly bracket.
> +		  // Request a check as soon as we move out of the sequence of
> +		  // equivalent nodes.
> +		  __check_next_bucket = true;
> +		  __check_now = false;
In terms of testcases, I would also add something more straightforward, 
close to what we have in the PR, and duplicated for map and set. But I'm 
not going to insist ;)

Thanks!
Paolo.