1 // std::__detail definitions -*- C++ -*-
3 // Copyright (C) 2007-2020 Free Software Foundation, Inc.
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)
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.
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.
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/>.
25 #if __cplusplus < 201103L
26 # error "hashtable_c++0x.cc must be compiled with -std=gnu++0x"
29 #include <initializer_list>
31 #include <ext/aligned_buffer.h>
32 #include <ext/alloc_traits.h>
33 #include <bits/hashtable_policy.h>
35 namespace std
_GLIBCXX_VISIBILITY(default)
37 _GLIBCXX_BEGIN_NAMESPACE_VERSION
39 #include "../shared/hashtable-aux.cc"
43 // Return a prime no smaller than n.
45 _Prime_rehash_policy::_M_next_bkt(std::size_t __n
) const
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 };
52 if (__n
< sizeof(__fast_bkt
))
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.
61 __builtin_floorl(__fast_bkt
[__n
] * (long double)_M_max_load_factor
);
62 return __fast_bkt
[__n
];
65 // Number of primes (without sentinel).
66 constexpr auto __n_primes
67 = sizeof(__prime_list
) / sizeof(unsigned long) - 1;
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;
74 const unsigned long* __next_bkt
=
75 std::lower_bound(__prime_list
+ 6, __last_prime
, __n
);
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
= size_t(-1);
84 __builtin_floorl(*__next_bkt
* (long double)_M_max_load_factor
);
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.
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.
98 std::pair
<bool, std::size_t>
99 _Prime_rehash_policy::
100 _M_need_rehash(std::size_t __n_bkt
, std::size_t __n_elt
,
101 std::size_t __n_ins
) const
103 if (__n_elt
+ __n_ins
> _M_next_resize
)
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
)
113 _M_next_bkt(std::max
<std::size_t>(__builtin_floorl(__min_bkts
) + 1,
114 __n_bkt
* _S_growth_factor
)) };
117 = __builtin_floorl(__n_bkt
* (long double)_M_max_load_factor
);
123 } // namespace __detail
125 _GLIBCXX_END_NAMESPACE_VERSION