Update copyright years.

[thirdparty/gcc.git] / libstdc++-v3 / src / c++11 / hashtable_c++0x.cc

diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc b/libstdc++-v3/src/c++11/hashtable_c++0x.cc
index 69f999f5cd5a39dd676409a2e2bd3d010a759d76..2fa35e7d16766293a69b7e9768782e41d4b866fa 100644 (file)
--- a/libstdc++-v3/src/c++11/hashtable_c++0x.cc
+++ b/libstdc++-v3/src/c++11/hashtable_c++0x.cc
@@ -1,6 +1,6 @@
 // std::__detail definitions -*- C++ -*-
 
-// Copyright (C) 2007-2015 Free Software Foundation, Inc.
+// Copyright (C) 2007-2024 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
@@ -30,38 +30,60 @@
 #include <tuple>
 #include <ext/aligned_buffer.h>
 #include <ext/alloc_traits.h>
+#include <bits/functional_hash.h>
 #include <bits/hashtable_policy.h>
 
 namespace std _GLIBCXX_VISIBILITY(default)
 {
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
 #include "../shared/hashtable-aux.cc"
 
 namespace __detail
 {
-  _GLIBCXX_BEGIN_NAMESPACE_VERSION
-
   // Return a prime no smaller than n.
   std::size_t
   _Prime_rehash_policy::_M_next_bkt(std::size_t __n) const
   {
     // 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[]
+      = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 };
 
-    if (__n <= 11)
+    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_ceil(__fast_bkt[__n] * (long double)_M_max_load_factor);
+         __builtin_floor(__fast_bkt[__n] * (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;
+
     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);
+
+    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 = size_t(-1);
+    else
+      _M_next_resize =
+       __builtin_floor(*__next_bkt * (double)_M_max_load_factor);
+
     return *__next_bkt;
   }
 
@@ -79,23 +101,27 @@ namespace __detail
   _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
                 std::size_t __n_ins) const
   {
-    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.
+       double __min_bkts
+         = std::max<std::size_t>(__n_elt + __n_ins, _M_next_resize ? 0 : 11)
+         / (double)_M_max_load_factor;
        if (__min_bkts >= __n_bkt)
-         return std::make_pair(true,
+         return { true,
            _M_next_bkt(std::max<std::size_t>(__builtin_floor(__min_bkts) + 1,
-                                             __n_bkt * _S_growth_factor)));
+                                             __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_floor(__n_bkt * (double)_M_max_load_factor);
+       return { false, 0 };
       }
     else
-      return std::make_pair(false, 0);
+      return { false, 0 };
   }
+} // namespace __detail
 
 _GLIBCXX_END_NAMESPACE_VERSION
-} // namespace __detail
 } // namespace std