1 // std::__detail definitions -*- C++ -*- 2 3 // Copyright (C) 2007-2020 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 #if __cplusplus < 201103L 26 # error "hashtable_c++0x.cc must be compiled with -std=gnu++0x" 27 #endif 28 29 #include <initializer_list> 30 #include <tuple> 31 #include <ext/aligned_buffer.h> 32 #include <ext/alloc_traits.h> 33 #include <bits/hashtable_policy.h> 34 35 namespace std _GLIBCXX_VISIBILITY(default) 36 { 37 _GLIBCXX_BEGIN_NAMESPACE_VERSION 38 39 #include "../shared/hashtable-aux.cc" 40 41 namespace __detail 42 { 43 // Return a prime no smaller than n. 44 std::size_t _M_next_bkt(std::size_t __n) const45 _Prime_rehash_policy::_M_next_bkt(std::size_t __n) const 46 { 47 // Optimize lookups involving the first elements of __prime_list. 48 // (useful to speed-up, eg, constructors) 49 static const unsigned char __fast_bkt[] 50 = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 }; 51 52 if (__n < sizeof(__fast_bkt)) 53 { 54 if (__n == 0) 55 // Special case on container 1st initialization with 0 bucket count 56 // hint. We keep _M_next_resize to 0 to make sure that next time we 57 // want to add an element allocation will take place. 58 return 1; 59 60 _M_next_resize = 61 __builtin_floorl(__fast_bkt[__n] * (long double)_M_max_load_factor); 62 return __fast_bkt[__n]; 63 } 64 65 // Number of primes (without sentinel). 66 constexpr auto __n_primes 67 = sizeof(__prime_list) / sizeof(unsigned long) - 1; 68 69 // Don't include the last prime in the search, so that anything 70 // higher than the second-to-last prime returns a past-the-end 71 // iterator that can be dereferenced to get the last prime. 72 constexpr auto __last_prime = __prime_list + __n_primes - 1; 73 74 const unsigned long* __next_bkt = 75 std::lower_bound(__prime_list + 6, __last_prime, __n); 76 77 if (__next_bkt == __last_prime) 78 // Set next resize to the max value so that we never try to rehash again 79 // as we already reach the biggest possible bucket number. 80 // Note that it might result in max_load_factor not being respected. 81 _M_next_resize = numeric_limits<size_t>::max(); 82 else 83 _M_next_resize = 84 __builtin_floorl(*__next_bkt * (long double)_M_max_load_factor); 85 86 return *__next_bkt; 87 } 88 89 // Finds the smallest prime p such that alpha p > __n_elt + __n_ins. 90 // If p > __n_bkt, return make_pair(true, p); otherwise return 91 // make_pair(false, 0). In principle this isn't very different from 92 // _M_bkt_for_elements. 93 94 // The only tricky part is that we're caching the element count at 95 // which we need to rehash, so we don't have to do a floating-point 96 // multiply for every insertion. 97 98 std::pair<bool, std::size_t> 99 _Prime_rehash_policy:: _M_need_rehash(std::size_t __n_bkt,std::size_t __n_elt,std::size_t __n_ins) const100 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, 101 std::size_t __n_ins) const 102 { 103 if (__n_elt + __n_ins > _M_next_resize) 104 { 105 // If _M_next_resize is 0 it means that we have nothing allocated so 106 // far and that we start inserting elements. In this case we start 107 // with an initial bucket size of 11. 108 long double __min_bkts 109 = std::max<std::size_t>(__n_elt + __n_ins, _M_next_resize ? 0 : 11) 110 / (long double)_M_max_load_factor; 111 if (__min_bkts >= __n_bkt) 112 return { true, 113 _M_next_bkt(std::max<std::size_t>(__builtin_floorl(__min_bkts) + 1, 114 __n_bkt * _S_growth_factor)) }; 115 116 _M_next_resize 117 = __builtin_floorl(__n_bkt * (long double)_M_max_load_factor); 118 return { false, 0 }; 119 } 120 else 121 return { false, 0 }; 122 } 123 } // namespace __detail 124 125 _GLIBCXX_END_NAMESPACE_VERSION 126 } // namespace std 127