[v3] fix libstdc++/52446

[François Dumont <frs dot dumont at gmail dot com>]

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.
    * 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.

François

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);
+      // 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;
+		  // Request a check as soon as we move out of the sequence of
+		  // equivalent nodes.
+		  __check_next_bucket = true;
+		  __check_now = false;
 		}
 	      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;
+	  
+	  if (__check_now && __check_next_bucket)
+	    {
+	      // Check if we shall update the buckets because of a previous
+	      // insertion after __prev_p. We do so only here to do a check on
+	      // the bucket index only once for all the sequence of equivalent
+	      // nodes we just pass through.
+	      if (__prev_p->_M_nxt)
+		{
+		  std::size_t __next_index
+		    = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n);
+		  if (__next_index != __prev_index)
+		    __new_buckets[__next_index] = __prev_p;
+		}
+	      __check_next_bucket = false;
+	    }
+	  __prev_p = __p;
+	  __prev_index = __new_index;
+	  __p = __next;
 	}
-      __catch(...)
+
+      if (__check_next_bucket && __prev_p->_M_nxt)
 	{
-	  // 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;
+	  std::size_t __next_index
+	    = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n);
+	  if (__next_index != __prev_index)
+	    __new_buckets[__next_index] = __prev_p;
 	}
+
+      _M_deallocate_buckets(_M_buckets, _M_bucket_count);
+      _M_bucket_count = __n;
+      _M_buckets = __new_buckets;
     }
 
 _GLIBCXX_END_NAMESPACE_VERSION
Index: testsuite/23_containers/unordered_multimap/insert/52476.cc
===================================================================
--- testsuite/23_containers/unordered_multimap/insert/52476.cc	(revision 0)
+++ testsuite/23_containers/unordered_multimap/insert/52476.cc	(revision 0)
@@ -0,0 +1,59 @@
+// { dg-options "-std=gnu++0x" }
+//
+// Copyright (C) 2012 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <unordered_map>
+#include <vector>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+void test01()
+{
+  using namespace std;
+  bool test __attribute__((unused)) = true;
+  
+  unordered_multimap<int, int> mmap;
+  vector<int> values;
+
+  size_t nb_bkts = mmap.bucket_count();
+  int i = 0;
+  for (;; ++i)
+    {
+      mmap.insert(make_pair(0, i));
+      if (mmap.bucket_count() != nb_bkts)
+	// Container got rehash
+	break;
+      values.clear();
+      transform(mmap.begin(), mmap.end(), back_inserter(values),
+		[](const pair<int, int>& p) { return p.second; });
+    }
+
+  vector<int> rehash_values;
+  transform(mmap.begin(), mmap.end(), back_inserter(rehash_values),
+	    [](const pair<int, int>& p) { return p.second; });
+  // Remove the value that result in a rehash
+  rehash_values.erase(remove(rehash_values.begin(), rehash_values.end(), i));
+
+  VERIFY( rehash_values == values );
+}
+  
+int main()
+{
+  test01();
+  return 0;
+}