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 3ddc10c72f7e7aa48f4de8f705b124ef8ca77f0b..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-2017 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,6 +30,7 @@
 #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)
@@ -46,13 +47,19 @@ namespace __detail
   {
     // Optimize lookups involving the first elements of __prime_list.
     // (useful to speed-up, eg, constructors)
-    static const unsigned char __fast_bkt[13]
-      = { 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 };
+    static const unsigned char __fast_bkt[]
+      = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 };
 
-    if (__n <= 12)
+    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];
       }
 
@@ -65,18 +72,17 @@ namespace __detail
     // 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 + 6, __last_prime, __n + 1);
+      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 = std::size_t(-1);
+      _M_next_resize = size_t(-1);
     else
       _M_next_resize =
-       __builtin_ceil(*__next_bkt * (long double)_M_max_load_factor);
+       __builtin_floor(*__next_bkt * (double)_M_max_load_factor);
 
     return *__next_bkt;
   }
@@ -95,21 +101,25 @@ 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