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