2016-06-20 François Dumont <fdumont@gcc.gnu.org>

	PR libstdc++/71181
	* include/tr1/hashtable_policy.h
	(_Prime_rehash_policy::_M_next_bkt): Make past-the-end iterator
	dereferenceable to avoid check on lower_bound result.
	(_Prime_rehash_policy::_M_bkt_for_elements): Call latter.
	(_Prime_rehash_policy::_M_need_rehash): Likewise.
	* src/c++11/hashtable_c++0x.cc (_Prime_rehash_policy::_M_next_bkt):
	Always return a value greater than input value. Set _M_next_resize to
	max value when reaching highest prime number.
	* src/shared/hashtable-aux.cc (__prime_list): Add comment about sentinel
	being now useless.
	* testsuite/23_containers/unordered_set/hash_policy/71181.cc: New.
	* testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc
	(test02): New.
	* testsuite/23_containers/unordered_set/hash_policy/prime_rehash.cc: New.
	* testsuite/23_containers/unordered_set/hash_policy/rehash.cc:
	Fix indentation.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@237617 138bc75d-0d04-0410-961f-82ee72b054a4

8 files changed, 216 insertions, 44 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index a9748517114..10ffc4169d1 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,23 @@
+2016-06-20  François Dumont  <fdumont@gcc.gnu.org>
+
+	PR libstdc++/71181
+	* include/tr1/hashtable_policy.h
+	(_Prime_rehash_policy::_M_next_bkt): Make past-the-end iterator
+	dereferenceable to avoid check on lower_bound result.
+	(_Prime_rehash_policy::_M_bkt_for_elements): Call latter.
+	(_Prime_rehash_policy::_M_need_rehash): Likewise.
+	* src/c++11/hashtable_c++0x.cc (_Prime_rehash_policy::_M_next_bkt):
+	Always return a value greater than input value. Set _M_next_resize to
+	max value when reaching highest prime number.
+	* src/shared/hashtable-aux.cc (__prime_list): Add comment about sentinel
+	being now useless.
+	* testsuite/23_containers/unordered_set/hash_policy/71181.cc: New.
+	* testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc
+	(test02): New.
+	* testsuite/23_containers/unordered_set/hash_policy/prime_rehash.cc: New.
+	* testsuite/23_containers/unordered_set/hash_policy/rehash.cc:
+	Fix indentation.
+
 2016-06-17  Jonathan Wakely  <jwakely@redhat.com>
 
 	PR libstdc++/71545
diff --git a/libstdc++-v3/include/tr1/hashtable_policy.h b/libstdc++-v3/include/tr1/hashtable_policy.h
index 4ee6d45044e..c5cf866b1fe 100644
--- a/libstdc++-v3/include/tr1/hashtable_policy.h
+++ b/libstdc++-v3/include/tr1/hashtable_policy.h
@@ -420,8 +420,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   _Prime_rehash_policy::
   _M_next_bkt(std::size_t __n) const
   {
-    const unsigned long* __p = std::lower_bound(__prime_list, __prime_list
-						+ _S_n_primes, __n);
+    // Don't include the last prime in the search, so that anything
+    // higher than the second-to-last prime returns a past-the-end
+    // iterator that can be dereferenced to get the last prime.
+    const unsigned long* __p
+      = std::lower_bound(__prime_list, __prime_list + _S_n_primes - 1, __n);
     _M_next_resize = 
       static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor));
     return *__p;
@@ -434,11 +437,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   _M_bkt_for_elements(std::size_t __n) const
   {
     const float __min_bkts = __n / _M_max_load_factor;
-    const unsigned long* __p = std::lower_bound(__prime_list, __prime_list
-						+ _S_n_primes, __min_bkts);
-    _M_next_resize =
-      static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor));
-    return *__p;
+    return _M_next_bkt(__builtin_ceil(__min_bkts));
   }
 
   // Finds the smallest prime p such that alpha p > __n_elt + __n_ins.
@@ -462,12 +461,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	if (__min_bkts > __n_bkt)
 	  {
 	    __min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt);
-	    const unsigned long* __p =
-	      std::lower_bound(__prime_list, __prime_list + _S_n_primes,
-			       __min_bkts);
-	    _M_next_resize = static_cast<std::size_t>
-	      (__builtin_ceil(*__p * _M_max_load_factor));
-	    return std::make_pair(true, *__p);
+	    return std::make_pair(true,
+				  _M_next_bkt(__builtin_ceil(__min_bkts)));
 	  }
 	else 
 	  {
diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc b/libstdc++-v3/src/c++11/hashtable_c++0x.cc
index a5e6520dcdb..ce4961fbd5e 100644
--- a/libstdc++-v3/src/c++11/hashtable_c++0x.cc
+++ b/libstdc++-v3/src/c++11/hashtable_c++0x.cc
@@ -46,22 +46,38 @@ namespace __detail
   {
     // Optimize lookups involving the first elements of __prime_list.
     // (useful to speed-up, eg, constructors)
-    static const unsigned char __fast_bkt[12]
-      = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 };
+    static const unsigned char __fast_bkt[13]
+      = { 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 };
 
-    if (__n <= 11)
+    if (__n <= 12)
       {
 	_M_next_resize =
 	  __builtin_ceil(__fast_bkt[__n] * (long double)_M_max_load_factor);
 	return __fast_bkt[__n];
       }
 
+    // Number of primes (without sentinel).
     constexpr auto __n_primes
       = sizeof(__prime_list) / sizeof(unsigned long) - 1;
+
+    // Don't include the last prime in the search, so that anything
+    // higher than the second-to-last prime returns a past-the-end
+    // iterator that can be dereferenced to get the last prime.
+    constexpr auto __last_prime = __prime_list + __n_primes - 1;
+
+    // Look for 'n + 1' to make sure returned value will be greater than n.
     const unsigned long* __next_bkt =
-      std::lower_bound(__prime_list + 5, __prime_list + __n_primes, __n);
-    _M_next_resize =
-      __builtin_ceil(*__next_bkt * (long double)_M_max_load_factor);
+      std::lower_bound(__prime_list + 6, __last_prime, __n + 1);
+
+    if (__next_bkt == __last_prime)
+      // Set next resize to the max value so that we never try to rehash again
+      // as we already reach the biggest possible bucket number.
+      // Note that it might result in max_load_factor not being respected.
+      _M_next_resize = std::size_t(-1);
+    else
+      _M_next_resize =
+	__builtin_ceil(*__next_bkt * (long double)_M_max_load_factor);
+
     return *__next_bkt;
   }
 
diff --git a/libstdc++-v3/src/shared/hashtable-aux.cc b/libstdc++-v3/src/shared/hashtable-aux.cc
index 081bb1236bc..ec9841e06a1 100644
--- a/libstdc++-v3/src/shared/hashtable-aux.cc
+++ b/libstdc++-v3/src/shared/hashtable-aux.cc
@@ -25,6 +25,7 @@
 namespace __detail
 {
 _GLIBCXX_BEGIN_NAMESPACE_VERSION
+  // The sentinel value is kept only for abi backward compatibility.
   extern const unsigned long __prime_list[] = // 256 + 1 or 256 + 48 + 1
   {
     2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul,
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc
new file mode 100644
index 00000000000..a8bbfc736d9
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc
@@ -0,0 +1,63 @@
+// Copyright (C) 2016 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/>.
+//
+// { dg-options "-std=gnu++11" }
+
+#include <unordered_set>
+
+#include <testsuite_hooks.h>
+
+template<typename _USet>
+  void test(int threshold)
+  {
+    bool test __attribute__((unused)) = true;
+    _USet us;
+    auto nb_reserved = us.bucket_count();
+    us.reserve(nb_reserved);
+    auto bkts = us.bucket_count();
+    for (int i = 0; i != threshold; ++i)
+      {
+	if (i == nb_reserved)
+	  {
+	    nb_reserved = bkts;
+	    us.reserve(nb_reserved);
+	    bkts = us.bucket_count();
+	  }
+
+	us.insert(i);
+
+	VERIFY( us.bucket_count() == bkts );
+      }
+  }
+
+template<typename _Value>
+  using unordered_set_power2_rehash =
+  std::_Hashtable<_Value, _Value, std::allocator<_Value>,
+		  std::__detail::_Identity,
+		  std::equal_to<_Value>,
+		  std::hash<_Value>,
+		  std::__detail::_Mask_range_hashing,
+		  std::__detail::_Default_ranged_hash,
+		  std::__detail::_Power2_rehash_policy,
+		  std::__detail::_Hashtable_traits<false, true, true>>;
+
+int main()
+{
+  test<std::unordered_set<int>>(150);
+  test<unordered_set_power2_rehash<int>>(150);
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc
index 1d01d0a19f5..5805f7aafc6 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc
@@ -17,6 +17,7 @@
 //
 // { dg-options "-std=gnu++11" }
 
+#include <limits>
 #include <unordered_set>
 
 #include <testsuite_hooks.h>
@@ -35,8 +36,32 @@ void test01()
 	  == (std::size_t(1) << (sizeof(std::size_t) * 8 - 1)) );
 }
 
+void test02()
+{
+  bool test __attribute__((unused)) = true;
+
+  std::__detail::_Power2_rehash_policy policy;
+
+  for (std::size_t i = 1;;)
+    {
+      auto nxt = policy._M_next_bkt(i);
+
+      if (nxt == i)
+	{
+	  // Equals only when reaching max.
+	  constexpr auto mx = std::numeric_limits<std::size_t>::max();
+	  VERIFY( nxt == policy._M_next_bkt(mx) );
+	  break;
+	}
+
+      VERIFY( nxt > i );
+      i = nxt;
+    }
+}
+
 int main()
 {
   test01();
+  test02();
   return 0;
 }
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/prime_rehash.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/prime_rehash.cc
new file mode 100644
index 00000000000..403382349fa
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/prime_rehash.cc
@@ -0,0 +1,52 @@
+// Copyright (C) 2016 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/>.
+//
+// { dg-options "-std=gnu++11" }
+
+#include <limits>
+#include <unordered_set>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+
+  std::__detail::_Prime_rehash_policy policy;
+
+  for (std::size_t i = 1;;)
+    {
+      auto nxt = policy._M_next_bkt(i);
+
+      if (nxt == i)
+	{
+	  // Equals only when reaching max.
+	  constexpr auto mx = std::numeric_limits<std::size_t>::max() - 1;
+	  VERIFY( nxt == policy._M_next_bkt(mx) );
+	  break;
+	}
+
+      VERIFY( nxt > i );
+      i = nxt;
+    }
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/rehash.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/rehash.cc
index 2dac583598d..96581317446 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/rehash.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/rehash.cc
@@ -22,40 +22,40 @@
 #include <testsuite_hooks.h>
 
 template<typename _USet>
-void test()
-{
-  bool test __attribute__((unused)) = true;
-  _USet us;
-  typedef typename _USet::size_type size_type;
-  bool rehashed = false;
-  for (int i = 0; i != 100000; ++i)
+  void test()
   {
-    size_type bkt_count = us.bucket_count();
-    us.insert(i);
-    if (bkt_count != us.bucket_count())
+    bool test __attribute__((unused)) = true;
+    _USet us;
+    typedef typename _USet::size_type size_type;
+    bool rehashed = false;
+    for (int i = 0; i != 100000; ++i)
       {
-	// Container has been rehashed, lets check that it won't be rehash again
-	// if we remove and restore the last 2 inserted elements:
-	rehashed = true;
-	bkt_count = us.bucket_count();
-	VERIFY( us.erase(i) == 1 );
-	VERIFY( bkt_count == us.bucket_count() );
-	if (i > 0)
+	size_type bkt_count = us.bucket_count();
+	us.insert(i);
+	if (bkt_count != us.bucket_count())
 	  {
-	    VERIFY( us.erase(i - 1) == 1 );
+	    // Container has been rehashed, lets check that it won't be rehash
+	    // again if we remove and restore the last 2 inserted elements:
+	    rehashed = true;
+	    bkt_count = us.bucket_count();
+	    VERIFY( us.erase(i) == 1 );
 	    VERIFY( bkt_count == us.bucket_count() );
+	    if (i > 0)
+	      {
+		VERIFY( us.erase(i - 1) == 1 );
+		VERIFY( bkt_count == us.bucket_count() );
 
-	    VERIFY( us.insert(i - 1).second );
+		VERIFY( us.insert(i - 1).second );
+		VERIFY( bkt_count == us.bucket_count() );
+	      }
+	    VERIFY( us.insert(i).second );
 	    VERIFY( bkt_count == us.bucket_count() );
 	  }
-	VERIFY( us.insert(i).second );
-	VERIFY( bkt_count == us.bucket_count() );
       }
-  }
 
-  // At lest we check a rehash once:
-  VERIFY( rehashed );
-}
+    // At lest we check a rehash once:
+    VERIFY( rehashed );
+  }
 
 template<typename _Value>
   using unordered_set_power2_rehash =