hashtable.h (_Hashtable<>::rehash): Review comment.

2019-05-04  François Dumont  <fdumont@gcc.gnu.org>

	* include/bits/hashtable.h (_Hashtable<>::rehash): Review comment.
	* include/bits/hashtable_policy.h
	(_Prime_rehash_policy::_M_bkt_for_elements): Use __builtin_ceill.
	(_Power2_rehash_policy::_M_bkt_for_elements): Likewise.
	(_Power2_rehash_policy::_M_next_bkt): Enforce returning a result not
	smaller than input value rather than always greater. Preserve
	_M_next_resize if called with 0 input. Use __builtin_floorl.
	(_Power2_rehash_policy::_M_need_rehash): Rehash only if number of
	elements + number of insertions is greater than _M_next_resize. Start
	with 11 buckets if not told otherwise. Use __builtin_floorl.
	(_Rehash_base<>::reserve): Use rehash policy _M_bkt_for_elements.
	* src/c++11/hashtable_c++0x.cc (_Prime_rehash_policy::_M_next_bkt):
	Preserve _M_next_resize if called with 0 input. Use __builtin_floorl.
	(_Prime_rehash_policy::_M_need_rehash): Start with 11 buckets if not
	told otherwise. Use __builtin_floorl.
	* testsuite/23_containers/unordered_set/hash_policy/71181.cc: Adapt test
	to also validate _Power2_rehash_policy.
	* testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc:
	Adapt.

From-SVN: r270868

6 files changed, 101 insertions, 42 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 40396312a0c..995ae0f6bb0 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,25 @@
+2019-05-04  François Dumont  <fdumont@gcc.gnu.org>
+
+	* include/bits/hashtable.h (_Hashtable<>::rehash): Review comment.
+	* include/bits/hashtable_policy.h
+	(_Prime_rehash_policy::_M_bkt_for_elements): Use __builtin_ceill.
+	(_Power2_rehash_policy::_M_bkt_for_elements): Likewise.
+	(_Power2_rehash_policy::_M_next_bkt): Enforce returning a result not
+	smaller than input value rather than always greater. Preserve
+	_M_next_resize if called with 0 input. Use __builtin_floorl.
+	(_Power2_rehash_policy::_M_need_rehash): Rehash only if number of
+	elements + number of insertions is greater than _M_next_resize. Start
+	with 11 buckets if not told otherwise. Use __builtin_floorl.
+	(_Rehash_base<>::reserve): Use rehash policy _M_bkt_for_elements.
+	* src/c++11/hashtable_c++0x.cc (_Prime_rehash_policy::_M_next_bkt):
+	Preserve _M_next_resize if called with 0 input. Use __builtin_floorl.
+	(_Prime_rehash_policy::_M_need_rehash): Start with 11 buckets if not
+	told otherwise. Use __builtin_floorl.
+	* testsuite/23_containers/unordered_set/hash_policy/71181.cc: Adapt test
+	to also validate _Power2_rehash_policy.
+	* testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc:
+	Adapt.
+
 2019-05-03  Jonathan Wakely  <jwakely@redhat.com>
 
 	PR libstdc++/61761
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index da78c68434f..2e8aeb7e4d4 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -2055,7 +2055,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       if (__buckets != _M_bucket_count)
 	_M_rehash(__buckets, __saved_state);
       else
-	// No rehash, restore previous state to keep a consistent state.
+	// No rehash, restore previous state to keep it consistent with
+	// container state.
 	_M_rehash_policy._M_reset(__saved_state);
     }
 
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index b38e8e0ecef..c7f466cd686 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -460,7 +460,7 @@ namespace __detail
     // Return a bucket count appropriate for n elements
     std::size_t
     _M_bkt_for_elements(std::size_t __n) const
-    { return __builtin_ceil(__n / (long double)_M_max_load_factor); }
+    { return __builtin_ceill(__n / (long double)_M_max_load_factor); }
 
     // __n_bkt is current bucket count, __n_elt is current element count,
     // and __n_ins is number of elements to be inserted.  Do we need to
@@ -535,24 +535,32 @@ namespace __detail
     std::size_t
     _M_next_bkt(std::size_t __n) noexcept
     {
+      if (__n == 0)
+	// Special case on container 1st initialization with 0 bucket count
+	// hint. We keep _M_next_resize to 0 to make sure that next time we
+	// want to add an element allocation will take place.
+	return 1;
+
       const auto __max_width = std::min<size_t>(sizeof(size_t), 8);
       const auto __max_bkt = size_t(1) << (__max_width * __CHAR_BIT__ - 1);
       std::size_t __res = __clp2(__n);
 
-      if (__res == __n)
-	__res <<= 1;
-
       if (__res == 0)
 	__res = __max_bkt;
+      else if (__res == 1)
+	// If __res is 1 we force it to 2 to make sure there will be an
+	// allocation so that nothing need to be stored in the initial
+	// single bucket
+	__res = 2;
 
       if (__res == __max_bkt)
 	// 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);
+	_M_next_resize = numeric_limits<size_t>::max();
       else
 	_M_next_resize
-	  = __builtin_ceil(__res * (long double)_M_max_load_factor);
+	  = __builtin_floorl(__res * (long double)_M_max_load_factor);
 
       return __res;
     }
@@ -560,7 +568,7 @@ namespace __detail
     // Return a bucket count appropriate for n elements
     std::size_t
     _M_bkt_for_elements(std::size_t __n) const noexcept
-    { return __builtin_ceil(__n / (long double)_M_max_load_factor); }
+    { return __builtin_ceill(__n / (long double)_M_max_load_factor); }
 
     // __n_bkt is current bucket count, __n_elt is current element count,
     // and __n_ins is number of elements to be inserted.  Do we need to
@@ -570,21 +578,25 @@ namespace __detail
     _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
 		   std::size_t __n_ins) noexcept
     {
-      if (__n_elt + __n_ins >= _M_next_resize)
+      if (__n_elt + __n_ins > _M_next_resize)
 	{
-	  long double __min_bkts = (__n_elt + __n_ins)
-					/ (long double)_M_max_load_factor;
+	  // If _M_next_resize is 0 it means that we have nothing allocated so
+	  // far and that we start inserting elements. In this case we start
+	  // with an initial bucket size of 11.
+	  long double __min_bkts
+	    = std::max<std::size_t>(__n_elt + __n_ins, _M_next_resize ? 0 : 11)
+	      / (long double)_M_max_load_factor;
 	  if (__min_bkts >= __n_bkt)
-	    return std::make_pair(true,
-	      _M_next_bkt(std::max<std::size_t>(__builtin_floor(__min_bkts) + 1,
-						__n_bkt * _S_growth_factor)));
+	    return { true,
+	      _M_next_bkt(std::max<std::size_t>(__builtin_floorl(__min_bkts) + 1,
+						__n_bkt * _S_growth_factor)) };
 
 	  _M_next_resize
-	    = __builtin_floor(__n_bkt * (long double)_M_max_load_factor);
-	  return std::make_pair(false, 0);
+	    = __builtin_floorl(__n_bkt * (long double)_M_max_load_factor);
+	  return { false, 0 };
 	}
       else
-	return std::make_pair(false, 0);
+	return { false, 0 };
     }
 
     typedef std::size_t _State;
@@ -1074,7 +1086,7 @@ namespace __detail
       reserve(std::size_t __n)
       {
 	__hashtable* __this = static_cast<__hashtable*>(this);
-	__this->rehash(__builtin_ceil(__n / max_load_factor()));
+	__this->rehash(__this->__rehash_policy()._M_bkt_for_elements(__n));
       }
     };
 
diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc b/libstdc++-v3/src/c++11/hashtable_c++0x.cc
index 47c609d1800..de437d00b56 100644
--- a/libstdc++-v3/src/c++11/hashtable_c++0x.cc
+++ b/libstdc++-v3/src/c++11/hashtable_c++0x.cc
@@ -51,8 +51,14 @@ namespace __detail
 
     if (__n < sizeof(__fast_bkt))
       {
+	if (__n == 0)
+	  // Special case on container 1st initialization with 0 bucket count
+	  // hint. We keep _M_next_resize to 0 to make sure that next time we
+	  // want to add an element allocation will take place.
+	  return 1;
+
 	_M_next_resize =
-	  __builtin_floor(__fast_bkt[__n] * (long double)_M_max_load_factor);
+	  __builtin_floorl(__fast_bkt[__n] * (long double)_M_max_load_factor);
 	return __fast_bkt[__n];
       }
 
@@ -72,10 +78,10 @@ namespace __detail
       // 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);
+      _M_next_resize = numeric_limits<size_t>::max();
     else
       _M_next_resize =
-	__builtin_floor(*__next_bkt * (long double)_M_max_load_factor);
+	__builtin_floorl(*__next_bkt * (long double)_M_max_load_factor);
 
     return *__next_bkt;
   }
@@ -96,19 +102,23 @@ namespace __detail
   {
     if (__n_elt + __n_ins > _M_next_resize)
       {
-	long double __min_bkts = (__n_elt + __n_ins)
-				   / (long double)_M_max_load_factor;
+	// If _M_next_resize is 0 it means that we have nothing allocated so
+	// far and that we start inserting elements. In this case we start
+	// with an initial bucket size of 11.
+	long double __min_bkts
+	  = std::max<std::size_t>(__n_elt + __n_ins, _M_next_resize ? 0 : 11)
+	  / (long double)_M_max_load_factor;
 	if (__min_bkts >= __n_bkt)
-	  return std::make_pair(true,
-	    _M_next_bkt(std::max<std::size_t>(__builtin_floor(__min_bkts) + 1,
-					      __n_bkt * _S_growth_factor)));
+	  return { true,
+	    _M_next_bkt(std::max<std::size_t>(__builtin_floorl(__min_bkts) + 1,
+					      __n_bkt * _S_growth_factor)) };
 
 	_M_next_resize
-	  = __builtin_floor(__n_bkt * (long double)_M_max_load_factor);
-	return std::make_pair(false, 0);
+	  = __builtin_floorl(__n_bkt * (long double)_M_max_load_factor);
+	return { false, 0 };
       }
     else
-      return std::make_pair(false, 0);
+      return { false, 0 };
   }
 } // namespace __detail
 
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
index 6e38eba2c2c..7bbf4fd73db 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc
@@ -22,22 +22,22 @@
 #include <testsuite_hooks.h>
 
 template<typename _USet>
-  void test(int threshold)
+  void
+  test(_USet& us, int threshold)
   {
-    _USet us;
     auto nb_reserved = us.bucket_count();
     us.reserve(nb_reserved);
     auto bkts = us.bucket_count();
-    for (int i = 0; i != threshold; ++i)
+    for (int nb_insert = 1; nb_insert <= threshold; ++nb_insert)
       {
-	if (i >= nb_reserved)
+	if (nb_insert > nb_reserved)
 	  {
 	    nb_reserved = bkts;
 	    us.reserve(nb_reserved);
 	    bkts = us.bucket_count();
 	  }
 
-	us.insert(i);
+	us.insert(nb_insert);
 
 	VERIFY( us.bucket_count() == bkts );
       }
@@ -54,9 +54,22 @@ template<typename _Value>
 		  std::__detail::_Power2_rehash_policy,
 		  std::__detail::_Hashtable_traits<false, true, true>>;
 
+template<typename _USet>
+  void
+  test_cont()
+  {
+    _USet us;
+    test(us, 150);
+
+    us.clear();
+    us.rehash(0);
+
+    test(us, 150);
+  }
+
 int main()
 {
-  test<std::unordered_set<int>>(150);
-  test<unordered_set_power2_rehash<int>>(150);
+  test_cont<std::unordered_set<int>>();
+  test_cont<unordered_set_power2_rehash<int>>();
   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 58ed268ee4c..5e42485b977 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
@@ -26,9 +26,10 @@ void test01()
 {
   std::__detail::_Power2_rehash_policy policy;
   VERIFY( policy._M_next_bkt(1) == 2 );
-  VERIFY( policy._M_next_bkt(2) == 4 );
+  VERIFY( policy._M_next_bkt(2) == 2 );
   VERIFY( policy._M_next_bkt(3) == 4 );
   VERIFY( policy._M_next_bkt(5) == 8 );
+  VERIFY( policy._M_next_bkt(16) == 16 );
   VERIFY( policy._M_next_bkt(33) == 64 );
   VERIFY( policy._M_next_bkt((std::size_t(1) << (sizeof(std::size_t) * 8 - 2)) + 1)
 	  == (std::size_t(1) << (sizeof(std::size_t) * 8 - 1)) );
@@ -38,20 +39,20 @@ void test02()
 {
   std::__detail::_Power2_rehash_policy policy;
 
-  for (std::size_t i = 1;;)
+  for (std::size_t i = 3;;)
     {
       auto nxt = policy._M_next_bkt(i);
 
-      if (nxt == i)
+      if (nxt <= i)
 	{
-	  // Equals only when reaching max.
+	  // Lower or equal 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;
+      VERIFY( nxt >= i );
+      i = nxt + 1;
     }
 }