]>
Commit | Line | Data |
---|---|---|
4d007574 PC |
1 | // std::__detail definitions -*- C++ -*- |
2 | ||
6e147946 | 3 | // Copyright (C) 2007-2013 Free Software Foundation, Inc. |
4d007574 PC |
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 | |
748086b7 | 8 | // Free Software Foundation; either version 3, or (at your option) |
4d007574 PC |
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 | ||
748086b7 JJ |
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. | |
4d007574 | 19 | |
748086b7 JJ |
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/>. | |
4d007574 | 24 | |
734f5023 | 25 | #if __cplusplus < 201103L |
a00e3769 BK |
26 | # error "hashtable_c++0x.cc must be compiled with -std=gnu++0x" |
27 | #endif | |
28 | ||
6e147946 FD |
29 | #include <initializer_list> |
30 | #include <tuple> | |
31 | #include <bits/hashtable_policy.h> | |
32 | ||
12ffa228 BK |
33 | namespace std _GLIBCXX_VISIBILITY(default) |
34 | { | |
8bae34da | 35 | #include "../shared/hashtable-aux.cc" |
6e147946 FD |
36 | |
37 | namespace __detail | |
38 | { | |
39 | _GLIBCXX_BEGIN_NAMESPACE_VERSION | |
40 | ||
41 | // Return a prime no smaller than n. | |
42 | std::size_t | |
43 | _Prime_rehash_policy::_M_next_bkt(std::size_t __n) const | |
44 | { | |
45 | // Optimize lookups involving the first elements of __prime_list. | |
46 | // (useful to speed-up, eg, constructors) | |
47 | static const unsigned char __fast_bkt[12] | |
48 | = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 }; | |
49 | ||
50 | if (__n <= 11) | |
51 | { | |
52 | _M_next_resize = | |
53 | __builtin_ceil(__fast_bkt[__n] * (long double)_M_max_load_factor); | |
54 | return __fast_bkt[__n]; | |
55 | } | |
56 | ||
57 | const unsigned long* __next_bkt = | |
58 | std::lower_bound(__prime_list + 5, __prime_list + _S_n_primes, __n); | |
59 | _M_next_resize = | |
60 | __builtin_ceil(*__next_bkt * (long double)_M_max_load_factor); | |
61 | return *__next_bkt; | |
62 | } | |
63 | ||
64 | // Finds the smallest prime p such that alpha p > __n_elt + __n_ins. | |
65 | // If p > __n_bkt, return make_pair(true, p); otherwise return | |
66 | // make_pair(false, 0). In principle this isn't very different from | |
67 | // _M_bkt_for_elements. | |
68 | ||
69 | // The only tricky part is that we're caching the element count at | |
70 | // which we need to rehash, so we don't have to do a floating-point | |
71 | // multiply for every insertion. | |
72 | ||
73 | std::pair<bool, std::size_t> | |
74 | _Prime_rehash_policy:: | |
75 | _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, | |
76 | std::size_t __n_ins) const | |
77 | { | |
78 | if (__n_elt + __n_ins >= _M_next_resize) | |
79 | { | |
80 | long double __min_bkts = (__n_elt + __n_ins) | |
81 | / (long double)_M_max_load_factor; | |
82 | if (__min_bkts >= __n_bkt) | |
83 | return std::make_pair(true, | |
84 | _M_next_bkt(std::max<std::size_t>(__builtin_floor(__min_bkts) + 1, | |
85 | __n_bkt * _S_growth_factor))); | |
86 | ||
87 | _M_next_resize | |
88 | = __builtin_floor(__n_bkt * (long double)_M_max_load_factor); | |
89 | return std::make_pair(false, 0); | |
90 | } | |
91 | else | |
92 | return std::make_pair(false, 0); | |
93 | } | |
94 | ||
95 | _GLIBCXX_END_NAMESPACE_VERSION | |
96 | } // namespace __detail | |
97 | } // namespace std |