2012-07-29 François Dumont <fdumont@gcc.gnu.org>

[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / bits / hashtable_policy.h

diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index ab1be6d..631128a 100644 (file)
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -294,6 +294,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
     enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 };
 
+    static const std::size_t _S_growth_factor = 2;
+
     float                _M_max_load_factor;
     mutable std::size_t  _M_prev_resize;
     mutable std::size_t  _M_next_resize;
@@ -314,28 +316,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     static const unsigned char __fast_bkt[12]
       = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 };
 
-    if (__n <= 11)
+    const std::size_t __grown_n = __n * _S_growth_factor;
+    if (__grown_n <= 11)
       {
        _M_prev_resize = 0;
        _M_next_resize
-         = __builtin_ceil(__fast_bkt[__n] * (long double)_M_max_load_factor);
-       return __fast_bkt[__n];
+         = __builtin_ceil(__fast_bkt[__grown_n]
+                          * (long double)_M_max_load_factor);
+       return __fast_bkt[__grown_n];
       }
 
-    const unsigned long* __p
-      = std::lower_bound(__prime_list + 5, __prime_list + _S_n_primes, __n);
+    const unsigned long* __next_bkt
+      = std::lower_bound(__prime_list + 5, __prime_list + _S_n_primes,
+                        __grown_n);
+    const unsigned long* __prev_bkt
+      = std::lower_bound(__prime_list + 1, __next_bkt, __n / _S_growth_factor);
 
-    // Shrink will take place only if the number of elements is small enough
-    // so that the prime number 2 steps before __p is large enough to still
-    // conform to the max load factor:
     _M_prev_resize
-      = __builtin_floor(*(__p - 2) * (long double)_M_max_load_factor);
-
-    // Let's guaranty that a minimal grow step of 11 is used
-    if (*__p - __n < 11)
-      __p = std::lower_bound(__p, __prime_list + _S_n_primes, __n + 11);
-    _M_next_resize = __builtin_ceil(*__p * (long double)_M_max_load_factor);
-    return *__p;
+      = __builtin_floor(*(__prev_bkt - 1) * (long double)_M_max_load_factor);
+    _M_next_resize
+      = __builtin_ceil(*__next_bkt * (long double)_M_max_load_factor);
+    return *__next_bkt;
   }
 
   // Return the smallest prime p such that alpha p >= n, where alpha