1 // std::__detail definitions -*- C++ -*-
2 
3 // Copyright (C) 2007-2018 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[13]
50       = { 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 };
51 
52     if (__n <= 12)
53       {
54 	_M_next_resize =
55 	  __builtin_ceil(__fast_bkt[__n] * (long double)_M_max_load_factor);
56 	return __fast_bkt[__n];
57       }
58 
59     // Number of primes (without sentinel).
60     constexpr auto __n_primes
61       = sizeof(__prime_list) / sizeof(unsigned long) - 1;
62 
63     // Don't include the last prime in the search, so that anything
64     // higher than the second-to-last prime returns a past-the-end
65     // iterator that can be dereferenced to get the last prime.
66     constexpr auto __last_prime = __prime_list + __n_primes - 1;
67 
68     // Look for 'n + 1' to make sure returned value will be greater than n.
69     const unsigned long* __next_bkt =
70       std::lower_bound(__prime_list + 6, __last_prime, __n + 1);
71 
72     if (__next_bkt == __last_prime)
73       // Set next resize to the max value so that we never try to rehash again
74       // as we already reach the biggest possible bucket number.
75       // Note that it might result in max_load_factor not being respected.
76       _M_next_resize = std::size_t(-1);
77     else
78       _M_next_resize =
79 	__builtin_ceil(*__next_bkt * (long double)_M_max_load_factor);
80 
81     return *__next_bkt;
82   }
83 
84   // Finds the smallest prime p such that alpha p > __n_elt + __n_ins.
85   // If p > __n_bkt, return make_pair(true, p); otherwise return
86   // make_pair(false, 0).  In principle this isn't very different from
87   // _M_bkt_for_elements.
88 
89   // The only tricky part is that we're caching the element count at
90   // which we need to rehash, so we don't have to do a floating-point
91   // multiply for every insertion.
92 
93   std::pair<bool, std::size_t>
94   _Prime_rehash_policy::
_M_need_rehash(std::size_t __n_bkt,std::size_t __n_elt,std::size_t __n_ins) const95   _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
96 		 std::size_t __n_ins) const
97   {
98     if (__n_elt + __n_ins >= _M_next_resize)
99       {
100 	long double __min_bkts = (__n_elt + __n_ins)
101 				   / (long double)_M_max_load_factor;
102 	if (__min_bkts >= __n_bkt)
103 	  return std::make_pair(true,
104 	    _M_next_bkt(std::max<std::size_t>(__builtin_floor(__min_bkts) + 1,
105 					      __n_bkt * _S_growth_factor)));
106 
107 	_M_next_resize
108 	  = __builtin_floor(__n_bkt * (long double)_M_max_load_factor);
109 	return std::make_pair(false, 0);
110       }
111     else
112       return std::make_pair(false, 0);
113   }
114 } // namespace __detail
115 
116 _GLIBCXX_END_NAMESPACE_VERSION
117 } // namespace std
118