diff options
| author | fdumont <fdumont@138bc75d-0d04-0410-961f-82ee72b054a4> | 2011-12-07 19:47:03 +0000 |
|---|---|---|
| committer | fdumont <fdumont@138bc75d-0d04-0410-961f-82ee72b054a4> | 2011-12-07 19:47:03 +0000 |
| commit | d0914bfdd37704e9ecd85b28cb7e420b01645426 (patch) | |
| tree | c55917c60479c8571ba34ecd6313ba38a6d70232 /libstdc++-v3 | |
| parent | a53286c0084b73466d07a3f73137ff487cfc1cea (diff) | |
| download | gcc-d0914bfdd37704e9ecd85b28cb7e420b01645426.tar.gz | |
2011-12-07 François Dumont <fdumont@gcc.gnu.org>
PR libstdc++/51386
* include/bits/hashtable_policy.h (_Prime_rehash_policy::_M_next_bkt):
Fix computation of _M_prev_resize so that hashtable do not keep on
being rehashed when _M_max_load_factor is lower than 1.
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@182085 138bc75d-0d04-0410-961f-82ee72b054a4
Diffstat (limited to 'libstdc++-v3')
| -rw-r--r-- | libstdc++-v3/ChangeLog | 7 | ||||
| -rw-r--r-- | libstdc++-v3/include/bits/hashtable_policy.h | 33 |
2 files changed, 27 insertions, 13 deletions
diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 065b6357e96..d8707d8d371 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,10 @@ +2011-12-07 François Dumont <fdumont@gcc.gnu.org> + + PR libstdc++/51386 + * include/bits/hashtable_policy.h (_Prime_rehash_policy::_M_next_bkt): + Fix computation of _M_prev_resize so that hashtable do not keep on + being rehashed when _M_max_load_factor is lower than 1. + 2011-12-06 Paolo Carlini <paolo.carlini@oracle.com> PR libstdc++/51438 diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index 44c749af515..e97685c6ae7 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -300,23 +300,30 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { // Optimize lookups involving the first elements of __prime_list. // (useful to speed-up, eg, constructors) - static const unsigned long __fast_bkt[12] + static const unsigned char __fast_bkt[12] = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 }; + if (__n <= 11) + { + _M_prev_resize = 0; + _M_next_resize + = __builtin_ceil(__fast_bkt[__n] * (long double)_M_max_load_factor); + return __fast_bkt[__n]; + } + const unsigned long* __p - = __n <= 11 ? __fast_bkt + __n - : std::lower_bound(__prime_list + 5, - __prime_list + _S_n_primes, __n); - - _M_prev_resize = __builtin_floor(*__p * (long double)_M_max_load_factor); - if (__p != __fast_bkt) - _M_prev_resize = std::min(_M_prev_resize, - static_cast<std::size_t>(*(__p - 1))); - // Lets guaranty a minimal grow step of 11: + = std::lower_bound(__prime_list + 5, __prime_list + _S_n_primes, __n); + + // 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(__prime_list + 5, - __prime_list + _S_n_primes, __n + 11); - _M_next_resize = __builtin_floor(*__p * (long double)_M_max_load_factor); + __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; } |