]>
Commit | Line | Data |
---|---|---|
3b2524b1 PC |
1 | // Internal policy header for unordered_set and unordered_map -*- C++ -*- |
2 | ||
7adcbafe | 3 | // Copyright (C) 2010-2022 Free Software Foundation, Inc. |
3b2524b1 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 | |
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 | /** @file bits/hashtable_policy.h | |
26 | * This is an internal header file, included by other library headers. | |
7c3e9502 | 27 | * Do not attempt to use it directly. |
f910786b | 28 | * @headername{unordered_map,unordered_set} |
3b2524b1 PC |
29 | */ |
30 | ||
31 | #ifndef _HASHTABLE_POLICY_H | |
32 | #define _HASHTABLE_POLICY_H 1 | |
33 | ||
02a2c630 | 34 | #include <tuple> // for std::tuple, std::forward_as_tuple |
44c85722 | 35 | #include <bits/stl_algobase.h> // for std::min, std::is_permutation. |
9af65c2b | 36 | #include <ext/numeric_traits.h> // for __gnu_cxx::__int_traits |
732eb076 | 37 | |
12ffa228 BK |
38 | namespace std _GLIBCXX_VISIBILITY(default) |
39 | { | |
63dc7fbe | 40 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
6667d5fe | 41 | /// @cond undocumented |
63dc7fbe | 42 | |
4dad8b49 BK |
43 | template<typename _Key, typename _Value, typename _Alloc, |
44 | typename _ExtractKey, typename _Equal, | |
4797a61c | 45 | typename _Hash, typename _RangeHash, typename _Unused, |
4dad8b49 BK |
46 | typename _RehashPolicy, typename _Traits> |
47 | class _Hashtable; | |
48 | ||
3b2524b1 PC |
49 | namespace __detail |
50 | { | |
4dad8b49 BK |
51 | /** |
52 | * @defgroup hashtable-detail Base and Implementation Classes | |
53 | * @ingroup unordered_associative_containers | |
54 | * @{ | |
55 | */ | |
4797a61c FD |
56 | template<typename _Key, typename _Value, typename _ExtractKey, |
57 | typename _Equal, typename _Hash, typename _RangeHash, | |
58 | typename _Unused, typename _Traits> | |
4dad8b49 BK |
59 | struct _Hashtable_base; |
60 | ||
3b2524b1 | 61 | // Helper function: return distance(first, last) for forward |
0f146257 | 62 | // iterators, or 0/1 for input iterators. |
f4b4ce15 | 63 | template<typename _Iterator> |
3b2524b1 PC |
64 | inline typename std::iterator_traits<_Iterator>::difference_type |
65 | __distance_fw(_Iterator __first, _Iterator __last, | |
66 | std::input_iterator_tag) | |
0f146257 | 67 | { return __first != __last ? 1 : 0; } |
3b2524b1 | 68 | |
f4b4ce15 | 69 | template<typename _Iterator> |
3b2524b1 PC |
70 | inline typename std::iterator_traits<_Iterator>::difference_type |
71 | __distance_fw(_Iterator __first, _Iterator __last, | |
72 | std::forward_iterator_tag) | |
73 | { return std::distance(__first, __last); } | |
74 | ||
f4b4ce15 | 75 | template<typename _Iterator> |
3b2524b1 PC |
76 | inline typename std::iterator_traits<_Iterator>::difference_type |
77 | __distance_fw(_Iterator __first, _Iterator __last) | |
0f146257 FD |
78 | { return __distance_fw(__first, __last, |
79 | std::__iterator_category(__first)); } | |
3b2524b1 | 80 | |
5ac4e73a PC |
81 | struct _Identity |
82 | { | |
83 | template<typename _Tp> | |
84 | _Tp&& | |
4797a61c | 85 | operator()(_Tp&& __x) const noexcept |
5ac4e73a PC |
86 | { return std::forward<_Tp>(__x); } |
87 | }; | |
88 | ||
89 | struct _Select1st | |
90 | { | |
d87105d6 JW |
91 | template<typename _Pair> |
92 | struct __1st_type; | |
93 | ||
94 | template<typename _Tp, typename _Up> | |
95 | struct __1st_type<pair<_Tp, _Up>> | |
96 | { using type = _Tp; }; | |
97 | ||
98 | template<typename _Tp, typename _Up> | |
99 | struct __1st_type<const pair<_Tp, _Up>> | |
100 | { using type = const _Tp; }; | |
101 | ||
102 | template<typename _Pair> | |
103 | struct __1st_type<_Pair&> | |
104 | { using type = typename __1st_type<_Pair>::type&; }; | |
5ac4e73a | 105 | |
2c43f5ec | 106 | template<typename _Tp> |
d87105d6 | 107 | typename __1st_type<_Tp>::type&& |
2c43f5ec | 108 | operator()(_Tp&& __x) const noexcept |
d87105d6 | 109 | { return std::forward<_Tp>(__x).first; } |
2c43f5ec FD |
110 | }; |
111 | ||
112 | template<typename _ExKey> | |
113 | struct _NodeBuilder; | |
114 | ||
115 | template<> | |
116 | struct _NodeBuilder<_Select1st> | |
117 | { | |
118 | template<typename _Kt, typename _Arg, typename _NodeGenerator> | |
119 | static auto | |
120 | _S_build(_Kt&& __k, _Arg&& __arg, const _NodeGenerator& __node_gen) | |
d87105d6 | 121 | -> typename _NodeGenerator::__node_type* |
2c43f5ec | 122 | { |
d87105d6 JW |
123 | return __node_gen(std::forward<_Kt>(__k), |
124 | std::forward<_Arg>(__arg).second); | |
2c43f5ec FD |
125 | } |
126 | }; | |
127 | ||
128 | template<> | |
129 | struct _NodeBuilder<_Identity> | |
130 | { | |
131 | template<typename _Kt, typename _Arg, typename _NodeGenerator> | |
132 | static auto | |
133 | _S_build(_Kt&& __k, _Arg&&, const _NodeGenerator& __node_gen) | |
d87105d6 | 134 | -> typename _NodeGenerator::__node_type* |
2c43f5ec FD |
135 | { return __node_gen(std::forward<_Kt>(__k)); } |
136 | }; | |
137 | ||
b09bcf83 FD |
138 | template<typename _NodeAlloc> |
139 | struct _Hashtable_alloc; | |
140 | ||
b3abc9d8 FD |
141 | // Functor recycling a pool of nodes and using allocation once the pool is |
142 | // empty. | |
b09bcf83 | 143 | template<typename _NodeAlloc> |
b3abc9d8 FD |
144 | struct _ReuseOrAllocNode |
145 | { | |
146 | private: | |
b09bcf83 FD |
147 | using __node_alloc_type = _NodeAlloc; |
148 | using __hashtable_alloc = _Hashtable_alloc<__node_alloc_type>; | |
b09bcf83 FD |
149 | using __node_alloc_traits = |
150 | typename __hashtable_alloc::__node_alloc_traits; | |
b3abc9d8 FD |
151 | |
152 | public: | |
d87105d6 JW |
153 | using __node_type = typename __hashtable_alloc::__node_type; |
154 | ||
b09bcf83 | 155 | _ReuseOrAllocNode(__node_type* __nodes, __hashtable_alloc& __h) |
7cfe71d1 | 156 | : _M_nodes(__nodes), _M_h(__h) { } |
b3abc9d8 FD |
157 | _ReuseOrAllocNode(const _ReuseOrAllocNode&) = delete; |
158 | ||
159 | ~_ReuseOrAllocNode() | |
160 | { _M_h._M_deallocate_nodes(_M_nodes); } | |
161 | ||
2c43f5ec | 162 | template<typename... _Args> |
b3abc9d8 | 163 | __node_type* |
2c43f5ec | 164 | operator()(_Args&&... __args) const |
b3abc9d8 FD |
165 | { |
166 | if (_M_nodes) | |
167 | { | |
168 | __node_type* __node = _M_nodes; | |
169 | _M_nodes = _M_nodes->_M_next(); | |
170 | __node->_M_nxt = nullptr; | |
b74f0db1 JW |
171 | auto& __a = _M_h._M_node_allocator(); |
172 | __node_alloc_traits::destroy(__a, __node->_M_valptr()); | |
b3abc9d8 FD |
173 | __try |
174 | { | |
b74f0db1 | 175 | __node_alloc_traits::construct(__a, __node->_M_valptr(), |
2c43f5ec | 176 | std::forward<_Args>(__args)...); |
b3abc9d8 FD |
177 | } |
178 | __catch(...) | |
179 | { | |
23d5fd6c | 180 | _M_h._M_deallocate_node_ptr(__node); |
b3abc9d8 FD |
181 | __throw_exception_again; |
182 | } | |
183 | return __node; | |
184 | } | |
2c43f5ec | 185 | return _M_h._M_allocate_node(std::forward<_Args>(__args)...); |
b3abc9d8 FD |
186 | } |
187 | ||
188 | private: | |
189 | mutable __node_type* _M_nodes; | |
b09bcf83 | 190 | __hashtable_alloc& _M_h; |
b3abc9d8 FD |
191 | }; |
192 | ||
1bb59e05 FD |
193 | // Functor similar to the previous one but without any pool of nodes to |
194 | // recycle. | |
b09bcf83 | 195 | template<typename _NodeAlloc> |
b3abc9d8 FD |
196 | struct _AllocNode |
197 | { | |
198 | private: | |
b09bcf83 | 199 | using __hashtable_alloc = _Hashtable_alloc<_NodeAlloc>; |
b3abc9d8 FD |
200 | |
201 | public: | |
d87105d6 JW |
202 | using __node_type = typename __hashtable_alloc::__node_type; |
203 | ||
b09bcf83 | 204 | _AllocNode(__hashtable_alloc& __h) |
7cfe71d1 | 205 | : _M_h(__h) { } |
b3abc9d8 | 206 | |
2c43f5ec | 207 | template<typename... _Args> |
b3abc9d8 | 208 | __node_type* |
2c43f5ec FD |
209 | operator()(_Args&&... __args) const |
210 | { return _M_h._M_allocate_node(std::forward<_Args>(__args)...); } | |
b3abc9d8 FD |
211 | |
212 | private: | |
b09bcf83 | 213 | __hashtable_alloc& _M_h; |
b3abc9d8 FD |
214 | }; |
215 | ||
4dad8b49 | 216 | // Auxiliary types used for all instantiations of _Hashtable nodes |
3b2524b1 | 217 | // and iterators. |
7c3e9502 | 218 | |
4dad8b49 BK |
219 | /** |
220 | * struct _Hashtable_traits | |
221 | * | |
222 | * Important traits for hash tables. | |
223 | * | |
207585a6 | 224 | * @tparam _Cache_hash_code Boolean value. True if the value of |
4dad8b49 BK |
225 | * the hash function is stored along with the value. This is a |
226 | * time-space tradeoff. Storing it may improve lookup speed by | |
7cfe71d1 FD |
227 | * reducing the number of times we need to call the _Hash or _Equal |
228 | * functors. | |
4dad8b49 | 229 | * |
207585a6 | 230 | * @tparam _Constant_iterators Boolean value. True if iterator and |
4dad8b49 BK |
231 | * const_iterator are both constant iterator types. This is true |
232 | * for unordered_set and unordered_multiset, false for | |
233 | * unordered_map and unordered_multimap. | |
234 | * | |
207585a6 | 235 | * @tparam _Unique_keys Boolean value. True if the return value |
4dad8b49 | 236 | * of _Hashtable::count(k) is always at most one, false if it may |
207585a6 | 237 | * be an arbitrary number. This is true for unordered_set and |
4dad8b49 BK |
238 | * unordered_map, false for unordered_multiset and |
239 | * unordered_multimap. | |
240 | */ | |
241 | template<bool _Cache_hash_code, bool _Constant_iterators, bool _Unique_keys> | |
242 | struct _Hashtable_traits | |
243 | { | |
4dad8b49 BK |
244 | using __hash_cached = __bool_constant<_Cache_hash_code>; |
245 | using __constant_iterators = __bool_constant<_Constant_iterators>; | |
246 | using __unique_keys = __bool_constant<_Unique_keys>; | |
247 | }; | |
248 | ||
249 | /** | |
250 | * struct _Hash_node_base | |
251 | * | |
af6204cc BK |
252 | * Nodes, used to wrap elements stored in the hash table. A policy |
253 | * template parameter of class template _Hashtable controls whether | |
254 | * nodes also store a hash code. In some cases (e.g. strings) this | |
255 | * may be a performance win. | |
4dad8b49 | 256 | */ |
f86b266c FD |
257 | struct _Hash_node_base |
258 | { | |
259 | _Hash_node_base* _M_nxt; | |
260 | ||
34e6625a | 261 | _Hash_node_base() noexcept : _M_nxt() { } |
4dad8b49 | 262 | |
34e6625a | 263 | _Hash_node_base(_Hash_node_base* __next) noexcept : _M_nxt(__next) { } |
f86b266c FD |
264 | }; |
265 | ||
0462b6aa FD |
266 | /** |
267 | * struct _Hash_node_value_base | |
268 | * | |
269 | * Node type with the value to store. | |
270 | */ | |
271 | template<typename _Value> | |
1b6f0476 | 272 | struct _Hash_node_value_base |
0462b6aa | 273 | { |
b09bcf83 FD |
274 | typedef _Value value_type; |
275 | ||
0462b6aa FD |
276 | __gnu_cxx::__aligned_buffer<_Value> _M_storage; |
277 | ||
278 | _Value* | |
279 | _M_valptr() noexcept | |
280 | { return _M_storage._M_ptr(); } | |
281 | ||
282 | const _Value* | |
283 | _M_valptr() const noexcept | |
284 | { return _M_storage._M_ptr(); } | |
285 | ||
286 | _Value& | |
287 | _M_v() noexcept | |
288 | { return *_M_valptr(); } | |
289 | ||
290 | const _Value& | |
291 | _M_v() const noexcept | |
292 | { return *_M_valptr(); } | |
293 | }; | |
294 | ||
4dad8b49 | 295 | /** |
1b6f0476 | 296 | * Primary template struct _Hash_node_code_cache. |
4dad8b49 | 297 | */ |
1b6f0476 FD |
298 | template<bool _Cache_hash_code> |
299 | struct _Hash_node_code_cache | |
300 | { }; | |
3b2524b1 | 301 | |
af6204cc | 302 | /** |
1b6f0476 | 303 | * Specialization for node with cache, struct _Hash_node_code_cache. |
af6204cc | 304 | */ |
1b6f0476 FD |
305 | template<> |
306 | struct _Hash_node_code_cache<true> | |
307 | { std::size_t _M_hash_code; }; | |
3b2524b1 | 308 | |
1b6f0476 FD |
309 | template<typename _Value, bool _Cache_hash_code> |
310 | struct _Hash_node_value | |
311 | : _Hash_node_value_base<_Value> | |
312 | , _Hash_node_code_cache<_Cache_hash_code> | |
313 | { }; | |
3b2524b1 | 314 | |
af6204cc | 315 | /** |
1b6f0476 | 316 | * Primary template struct _Hash_node. |
af6204cc | 317 | */ |
1b6f0476 FD |
318 | template<typename _Value, bool _Cache_hash_code> |
319 | struct _Hash_node | |
320 | : _Hash_node_base | |
321 | , _Hash_node_value<_Value, _Cache_hash_code> | |
3b2524b1 | 322 | { |
4dad8b49 | 323 | _Hash_node* |
34e6625a MG |
324 | _M_next() const noexcept |
325 | { return static_cast<_Hash_node*>(this->_M_nxt); } | |
3b2524b1 PC |
326 | }; |
327 | ||
4dad8b49 BK |
328 | /// Base class for node iterators. |
329 | template<typename _Value, bool _Cache_hash_code> | |
3b2524b1 PC |
330 | struct _Node_iterator_base |
331 | { | |
5b3be7cf | 332 | using __node_type = _Hash_node<_Value, _Cache_hash_code>; |
4dad8b49 | 333 | |
1b6f0476 | 334 | __node_type* _M_cur; |
4dad8b49 | 335 | |
05a30af3 | 336 | _Node_iterator_base() : _M_cur(nullptr) { } |
34e6625a | 337 | _Node_iterator_base(__node_type* __p) noexcept |
3b2524b1 | 338 | : _M_cur(__p) { } |
7c3e9502 | 339 | |
3b2524b1 | 340 | void |
34e6625a | 341 | _M_incr() noexcept |
f86b266c | 342 | { _M_cur = _M_cur->_M_next(); } |
3b2524b1 | 343 | |
acc1d1a9 FD |
344 | friend bool |
345 | operator==(const _Node_iterator_base& __x, const _Node_iterator_base& __y) | |
346 | noexcept | |
347 | { return __x._M_cur == __y._M_cur; } | |
348 | ||
349 | #if __cpp_impl_three_way_comparison < 201907L | |
350 | friend bool | |
351 | operator!=(const _Node_iterator_base& __x, const _Node_iterator_base& __y) | |
352 | noexcept | |
353 | { return __x._M_cur != __y._M_cur; } | |
354 | #endif | |
355 | }; | |
3b2524b1 | 356 | |
4dad8b49 | 357 | /// Node iterators, used to iterate through all the hashtable. |
3b2524b1 PC |
358 | template<typename _Value, bool __constant_iterators, bool __cache> |
359 | struct _Node_iterator | |
360 | : public _Node_iterator_base<_Value, __cache> | |
361 | { | |
4dad8b49 BK |
362 | private: |
363 | using __base_type = _Node_iterator_base<_Value, __cache>; | |
364 | using __node_type = typename __base_type::__node_type; | |
365 | ||
366 | public: | |
a09bb4a8 JW |
367 | using value_type = _Value; |
368 | using difference_type = std::ptrdiff_t; | |
369 | using iterator_category = std::forward_iterator_tag; | |
3b2524b1 | 370 | |
a09bb4a8 JW |
371 | using pointer = __conditional_t<__constant_iterators, |
372 | const value_type*, value_type*>; | |
4dad8b49 | 373 | |
a09bb4a8 JW |
374 | using reference = __conditional_t<__constant_iterators, |
375 | const value_type&, value_type&>; | |
4dad8b49 | 376 | |
05a30af3 | 377 | _Node_iterator() = default; |
3b2524b1 PC |
378 | |
379 | explicit | |
34e6625a | 380 | _Node_iterator(__node_type* __p) noexcept |
4dad8b49 | 381 | : __base_type(__p) { } |
3b2524b1 PC |
382 | |
383 | reference | |
34e6625a | 384 | operator*() const noexcept |
0462b6aa | 385 | { return this->_M_cur->_M_v(); } |
7c3e9502 | 386 | |
3b2524b1 | 387 | pointer |
34e6625a | 388 | operator->() const noexcept |
0462b6aa | 389 | { return this->_M_cur->_M_valptr(); } |
3b2524b1 PC |
390 | |
391 | _Node_iterator& | |
34e6625a | 392 | operator++() noexcept |
7c3e9502 | 393 | { |
3b2524b1 | 394 | this->_M_incr(); |
7c3e9502 | 395 | return *this; |
3b2524b1 | 396 | } |
7c3e9502 | 397 | |
3b2524b1 | 398 | _Node_iterator |
34e6625a | 399 | operator++(int) noexcept |
7c3e9502 | 400 | { |
3b2524b1 PC |
401 | _Node_iterator __tmp(*this); |
402 | this->_M_incr(); | |
403 | return __tmp; | |
404 | } | |
405 | }; | |
406 | ||
4dad8b49 | 407 | /// Node const_iterators, used to iterate through all the hashtable. |
3b2524b1 PC |
408 | template<typename _Value, bool __constant_iterators, bool __cache> |
409 | struct _Node_const_iterator | |
410 | : public _Node_iterator_base<_Value, __cache> | |
411 | { | |
5b3be7cf | 412 | private: |
4dad8b49 BK |
413 | using __base_type = _Node_iterator_base<_Value, __cache>; |
414 | using __node_type = typename __base_type::__node_type; | |
415 | ||
416 | public: | |
b09bcf83 FD |
417 | typedef _Value value_type; |
418 | typedef std::ptrdiff_t difference_type; | |
419 | typedef std::forward_iterator_tag iterator_category; | |
3b2524b1 | 420 | |
1b6f0476 FD |
421 | typedef const value_type* pointer; |
422 | typedef const value_type& reference; | |
4dad8b49 | 423 | |
05a30af3 | 424 | _Node_const_iterator() = default; |
3b2524b1 PC |
425 | |
426 | explicit | |
34e6625a | 427 | _Node_const_iterator(__node_type* __p) noexcept |
4dad8b49 | 428 | : __base_type(__p) { } |
3b2524b1 PC |
429 | |
430 | _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators, | |
34e6625a | 431 | __cache>& __x) noexcept |
4dad8b49 | 432 | : __base_type(__x._M_cur) { } |
3b2524b1 PC |
433 | |
434 | reference | |
34e6625a | 435 | operator*() const noexcept |
0462b6aa | 436 | { return this->_M_cur->_M_v(); } |
7c3e9502 | 437 | |
3b2524b1 | 438 | pointer |
34e6625a | 439 | operator->() const noexcept |
0462b6aa | 440 | { return this->_M_cur->_M_valptr(); } |
3b2524b1 PC |
441 | |
442 | _Node_const_iterator& | |
34e6625a | 443 | operator++() noexcept |
7c3e9502 | 444 | { |
3b2524b1 | 445 | this->_M_incr(); |
7c3e9502 | 446 | return *this; |
3b2524b1 | 447 | } |
7c3e9502 | 448 | |
3b2524b1 | 449 | _Node_const_iterator |
34e6625a | 450 | operator++(int) noexcept |
7c3e9502 | 451 | { |
3b2524b1 PC |
452 | _Node_const_iterator __tmp(*this); |
453 | this->_M_incr(); | |
454 | return __tmp; | |
455 | } | |
456 | }; | |
457 | ||
3b2524b1 PC |
458 | // Many of class template _Hashtable's template parameters are policy |
459 | // classes. These are defaults for the policies. | |
460 | ||
4dad8b49 BK |
461 | /// Default range hashing function: use division to fold a large number |
462 | /// into the range [0, N). | |
3b2524b1 PC |
463 | struct _Mod_range_hashing |
464 | { | |
465 | typedef std::size_t first_argument_type; | |
466 | typedef std::size_t second_argument_type; | |
467 | typedef std::size_t result_type; | |
468 | ||
469 | result_type | |
0462b6aa FD |
470 | operator()(first_argument_type __num, |
471 | second_argument_type __den) const noexcept | |
3b2524b1 PC |
472 | { return __num % __den; } |
473 | }; | |
474 | ||
4dad8b49 BK |
475 | /// Default ranged hash function H. In principle it should be a |
476 | /// function object composed from objects of type H1 and H2 such that | |
477 | /// h(k, N) = h2(h1(k), N), but that would mean making extra copies of | |
478 | /// h1 and h2. So instead we'll just use a tag to tell class template | |
479 | /// hashtable to do that composition. | |
3b2524b1 PC |
480 | struct _Default_ranged_hash { }; |
481 | ||
4dad8b49 BK |
482 | /// Default value for rehash policy. Bucket size is (usually) the |
483 | /// smallest prime that keeps the load factor small enough. | |
3b2524b1 PC |
484 | struct _Prime_rehash_policy |
485 | { | |
7cfe71d1 | 486 | using __has_load_factor = true_type; |
732eb076 | 487 | |
da27f556 | 488 | _Prime_rehash_policy(float __z = 1.0) noexcept |
d4a7f7a1 | 489 | : _M_max_load_factor(__z), _M_next_resize(0) { } |
3b2524b1 PC |
490 | |
491 | float | |
d3677132 | 492 | max_load_factor() const noexcept |
7c3e9502 | 493 | { return _M_max_load_factor; } |
3b2524b1 PC |
494 | |
495 | // Return a bucket size no smaller than n. | |
496 | std::size_t | |
497 | _M_next_bkt(std::size_t __n) const; | |
7c3e9502 | 498 | |
3b2524b1 PC |
499 | // Return a bucket count appropriate for n elements |
500 | std::size_t | |
6e147946 | 501 | _M_bkt_for_elements(std::size_t __n) const |
943cc2a1 | 502 | { return __builtin_ceil(__n / (double)_M_max_load_factor); } |
7c3e9502 | 503 | |
3b2524b1 PC |
504 | // __n_bkt is current bucket count, __n_elt is current element count, |
505 | // and __n_ins is number of elements to be inserted. Do we need to | |
506 | // increase bucket count? If so, return make_pair(true, n), where n | |
507 | // is the new bucket count. If not, return make_pair(false, 0). | |
508 | std::pair<bool, std::size_t> | |
509 | _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, | |
510 | std::size_t __n_ins) const; | |
511 | ||
d4a7f7a1 | 512 | typedef std::size_t _State; |
da29608a FD |
513 | |
514 | _State | |
515 | _M_state() const | |
d4a7f7a1 | 516 | { return _M_next_resize; } |
da29608a | 517 | |
0462b6aa FD |
518 | void |
519 | _M_reset() noexcept | |
520 | { _M_next_resize = 0; } | |
521 | ||
da29608a | 522 | void |
d4a7f7a1 FD |
523 | _M_reset(_State __state) |
524 | { _M_next_resize = __state; } | |
da29608a | 525 | |
78aa145d FD |
526 | static const std::size_t _S_growth_factor = 2; |
527 | ||
b09bcf83 FD |
528 | float _M_max_load_factor; |
529 | mutable std::size_t _M_next_resize; | |
3b2524b1 PC |
530 | }; |
531 | ||
732eb076 FD |
532 | /// Range hashing function assuming that second arg is a power of 2. |
533 | struct _Mask_range_hashing | |
534 | { | |
535 | typedef std::size_t first_argument_type; | |
536 | typedef std::size_t second_argument_type; | |
537 | typedef std::size_t result_type; | |
538 | ||
539 | result_type | |
540 | operator()(first_argument_type __num, | |
541 | second_argument_type __den) const noexcept | |
542 | { return __num & (__den - 1); } | |
543 | }; | |
544 | ||
4957b284 | 545 | /// Compute closest power of 2 not less than __n |
732eb076 | 546 | inline std::size_t |
d34d36ef | 547 | __clp2(std::size_t __n) noexcept |
732eb076 | 548 | { |
9af65c2b | 549 | using __gnu_cxx::__int_traits; |
9866abe3 | 550 | // Equivalent to return __n ? std::bit_ceil(__n) : 0; |
4957b284 JW |
551 | if (__n < 2) |
552 | return __n; | |
2fb17d2d JW |
553 | const unsigned __lz = sizeof(size_t) > sizeof(long) |
554 | ? __builtin_clzll(__n - 1ull) | |
555 | : __builtin_clzl(__n - 1ul); | |
556 | // Doing two shifts avoids undefined behaviour when __lz == 0. | |
9af65c2b | 557 | return (size_t(1) << (__int_traits<size_t>::__digits - __lz - 1)) << 1; |
732eb076 FD |
558 | } |
559 | ||
560 | /// Rehash policy providing power of 2 bucket numbers. Avoids modulo | |
561 | /// operations. | |
562 | struct _Power2_rehash_policy | |
563 | { | |
7cfe71d1 | 564 | using __has_load_factor = true_type; |
732eb076 FD |
565 | |
566 | _Power2_rehash_policy(float __z = 1.0) noexcept | |
567 | : _M_max_load_factor(__z), _M_next_resize(0) { } | |
568 | ||
569 | float | |
570 | max_load_factor() const noexcept | |
571 | { return _M_max_load_factor; } | |
572 | ||
573 | // Return a bucket size no smaller than n (as long as n is not above the | |
574 | // highest power of 2). | |
575 | std::size_t | |
834f4c43 | 576 | _M_next_bkt(std::size_t __n) noexcept |
732eb076 | 577 | { |
de6f5f57 FD |
578 | if (__n == 0) |
579 | // Special case on container 1st initialization with 0 bucket count | |
580 | // hint. We keep _M_next_resize to 0 to make sure that next time we | |
581 | // want to add an element allocation will take place. | |
582 | return 1; | |
583 | ||
834f4c43 JW |
584 | const auto __max_width = std::min<size_t>(sizeof(size_t), 8); |
585 | const auto __max_bkt = size_t(1) << (__max_width * __CHAR_BIT__ - 1); | |
732eb076 FD |
586 | std::size_t __res = __clp2(__n); |
587 | ||
732eb076 FD |
588 | if (__res == 0) |
589 | __res = __max_bkt; | |
de6f5f57 FD |
590 | else if (__res == 1) |
591 | // If __res is 1 we force it to 2 to make sure there will be an | |
592 | // allocation so that nothing need to be stored in the initial | |
593 | // single bucket | |
594 | __res = 2; | |
732eb076 FD |
595 | |
596 | if (__res == __max_bkt) | |
597 | // Set next resize to the max value so that we never try to rehash again | |
598 | // as we already reach the biggest possible bucket number. | |
599 | // Note that it might result in max_load_factor not being respected. | |
9af65c2b | 600 | _M_next_resize = size_t(-1); |
732eb076 FD |
601 | else |
602 | _M_next_resize | |
943cc2a1 | 603 | = __builtin_floor(__res * (double)_M_max_load_factor); |
732eb076 FD |
604 | |
605 | return __res; | |
606 | } | |
607 | ||
608 | // Return a bucket count appropriate for n elements | |
609 | std::size_t | |
610 | _M_bkt_for_elements(std::size_t __n) const noexcept | |
943cc2a1 | 611 | { return __builtin_ceil(__n / (double)_M_max_load_factor); } |
732eb076 FD |
612 | |
613 | // __n_bkt is current bucket count, __n_elt is current element count, | |
614 | // and __n_ins is number of elements to be inserted. Do we need to | |
615 | // increase bucket count? If so, return make_pair(true, n), where n | |
616 | // is the new bucket count. If not, return make_pair(false, 0). | |
617 | std::pair<bool, std::size_t> | |
618 | _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, | |
834f4c43 | 619 | std::size_t __n_ins) noexcept |
732eb076 | 620 | { |
de6f5f57 | 621 | if (__n_elt + __n_ins > _M_next_resize) |
732eb076 | 622 | { |
de6f5f57 FD |
623 | // If _M_next_resize is 0 it means that we have nothing allocated so |
624 | // far and that we start inserting elements. In this case we start | |
625 | // with an initial bucket size of 11. | |
a1343e5c | 626 | double __min_bkts |
de6f5f57 | 627 | = std::max<std::size_t>(__n_elt + __n_ins, _M_next_resize ? 0 : 11) |
a1343e5c | 628 | / (double)_M_max_load_factor; |
732eb076 | 629 | if (__min_bkts >= __n_bkt) |
de6f5f57 | 630 | return { true, |
943cc2a1 | 631 | _M_next_bkt(std::max<std::size_t>(__builtin_floor(__min_bkts) + 1, |
de6f5f57 | 632 | __n_bkt * _S_growth_factor)) }; |
732eb076 FD |
633 | |
634 | _M_next_resize | |
943cc2a1 | 635 | = __builtin_floor(__n_bkt * (double)_M_max_load_factor); |
de6f5f57 | 636 | return { false, 0 }; |
732eb076 FD |
637 | } |
638 | else | |
de6f5f57 | 639 | return { false, 0 }; |
732eb076 FD |
640 | } |
641 | ||
642 | typedef std::size_t _State; | |
643 | ||
644 | _State | |
645 | _M_state() const noexcept | |
646 | { return _M_next_resize; } | |
647 | ||
648 | void | |
649 | _M_reset() noexcept | |
650 | { _M_next_resize = 0; } | |
651 | ||
652 | void | |
653 | _M_reset(_State __state) noexcept | |
654 | { _M_next_resize = __state; } | |
655 | ||
656 | static const std::size_t _S_growth_factor = 2; | |
657 | ||
834f4c43 JW |
658 | float _M_max_load_factor; |
659 | std::size_t _M_next_resize; | |
732eb076 FD |
660 | }; |
661 | ||
5dc22714 | 662 | // Base classes for std::_Hashtable. We define these base classes |
4dad8b49 BK |
663 | // because in some cases we want to do different things depending on |
664 | // the value of a policy class. In some cases the policy class | |
5dc22714 PC |
665 | // affects which member functions and nested typedefs are defined; |
666 | // we handle that by specializing base class templates. Several of | |
667 | // the base class templates need to access other members of class | |
4dad8b49 BK |
668 | // template _Hashtable, so we use a variant of the "Curiously |
669 | // Recurring Template Pattern" (CRTP) technique. | |
670 | ||
671 | /** | |
672 | * Primary class template _Map_base. | |
673 | * | |
d87105d6 JW |
674 | * If the hashtable has a value type of the form pair<const T1, T2> and |
675 | * a key extraction policy (_ExtractKey) that returns the first part | |
4dad8b49 BK |
676 | * of the pair, the hashtable gets a mapped_type typedef. If it |
677 | * satisfies those criteria and also has unique keys, then it also | |
678 | * gets an operator[]. | |
679 | */ | |
680 | template<typename _Key, typename _Value, typename _Alloc, | |
681 | typename _ExtractKey, typename _Equal, | |
4797a61c | 682 | typename _Hash, typename _RangeHash, typename _Unused, |
4dad8b49 BK |
683 | typename _RehashPolicy, typename _Traits, |
684 | bool _Unique_keys = _Traits::__unique_keys::value> | |
3b2524b1 | 685 | struct _Map_base { }; |
5dc22714 | 686 | |
d87105d6 JW |
687 | /// Partial specialization, __unique_keys set to false, std::pair value type. |
688 | template<typename _Key, typename _Val, typename _Alloc, typename _Equal, | |
4797a61c | 689 | typename _Hash, typename _RangeHash, typename _Unused, |
4dad8b49 | 690 | typename _RehashPolicy, typename _Traits> |
d87105d6 | 691 | struct _Map_base<_Key, pair<const _Key, _Val>, _Alloc, _Select1st, _Equal, |
4797a61c | 692 | _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, false> |
3b2524b1 | 693 | { |
d87105d6 | 694 | using mapped_type = _Val; |
3b2524b1 PC |
695 | }; |
696 | ||
4dad8b49 | 697 | /// Partial specialization, __unique_keys set to true. |
d87105d6 | 698 | template<typename _Key, typename _Val, typename _Alloc, typename _Equal, |
4797a61c | 699 | typename _Hash, typename _RangeHash, typename _Unused, |
4dad8b49 | 700 | typename _RehashPolicy, typename _Traits> |
d87105d6 | 701 | struct _Map_base<_Key, pair<const _Key, _Val>, _Alloc, _Select1st, _Equal, |
4797a61c | 702 | _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true> |
3b2524b1 | 703 | { |
4dad8b49 | 704 | private: |
d87105d6 JW |
705 | using __hashtable_base = _Hashtable_base<_Key, pair<const _Key, _Val>, |
706 | _Select1st, _Equal, _Hash, | |
707 | _RangeHash, _Unused, | |
4797a61c | 708 | _Traits>; |
4dad8b49 | 709 | |
d87105d6 JW |
710 | using __hashtable = _Hashtable<_Key, pair<const _Key, _Val>, _Alloc, |
711 | _Select1st, _Equal, _Hash, _RangeHash, | |
4797a61c | 712 | _Unused, _RehashPolicy, _Traits>; |
4dad8b49 BK |
713 | |
714 | using __hash_code = typename __hashtable_base::__hash_code; | |
4dad8b49 BK |
715 | |
716 | public: | |
717 | using key_type = typename __hashtable_base::key_type; | |
d87105d6 | 718 | using mapped_type = _Val; |
5dc22714 | 719 | |
3b2524b1 | 720 | mapped_type& |
4dad8b49 | 721 | operator[](const key_type& __k); |
3b2524b1 | 722 | |
fb7342fd | 723 | mapped_type& |
4dad8b49 | 724 | operator[](key_type&& __k); |
fb7342fd | 725 | |
3b2524b1 PC |
726 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
727 | // DR 761. unordered_map needs an at() member function. | |
728 | mapped_type& | |
d87105d6 JW |
729 | at(const key_type& __k) |
730 | { | |
731 | auto __ite = static_cast<__hashtable*>(this)->find(__k); | |
732 | if (!__ite._M_cur) | |
733 | __throw_out_of_range(__N("unordered_map::at")); | |
734 | return __ite->second; | |
735 | } | |
3b2524b1 PC |
736 | |
737 | const mapped_type& | |
d87105d6 JW |
738 | at(const key_type& __k) const |
739 | { | |
740 | auto __ite = static_cast<const __hashtable*>(this)->find(__k); | |
741 | if (!__ite._M_cur) | |
742 | __throw_out_of_range(__N("unordered_map::at")); | |
743 | return __ite->second; | |
744 | } | |
3b2524b1 PC |
745 | }; |
746 | ||
d87105d6 | 747 | template<typename _Key, typename _Val, typename _Alloc, typename _Equal, |
4797a61c | 748 | typename _Hash, typename _RangeHash, typename _Unused, |
4dad8b49 | 749 | typename _RehashPolicy, typename _Traits> |
612b4711 | 750 | auto |
d87105d6 | 751 | _Map_base<_Key, pair<const _Key, _Val>, _Alloc, _Select1st, _Equal, |
4797a61c | 752 | _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>:: |
4dad8b49 | 753 | operator[](const key_type& __k) |
612b4711 | 754 | -> mapped_type& |
3b2524b1 | 755 | { |
4dad8b49 BK |
756 | __hashtable* __h = static_cast<__hashtable*>(this); |
757 | __hash_code __code = __h->_M_hash_code(__k); | |
4797a61c | 758 | std::size_t __bkt = __h->_M_bucket_index(__code); |
1b6f0476 | 759 | if (auto __node = __h->_M_find_node(__bkt, __k, __code)) |
b0c849fa FD |
760 | return __node->_M_v().second; |
761 | ||
762 | typename __hashtable::_Scoped_node __node { | |
763 | __h, | |
764 | std::piecewise_construct, | |
765 | std::tuple<const key_type&>(__k), | |
766 | std::tuple<>() | |
767 | }; | |
768 | auto __pos | |
4797a61c | 769 | = __h->_M_insert_unique_node(__bkt, __code, __node._M_node); |
b0c849fa FD |
770 | __node._M_node = nullptr; |
771 | return __pos->second; | |
3b2524b1 PC |
772 | } |
773 | ||
d87105d6 | 774 | template<typename _Key, typename _Val, typename _Alloc, typename _Equal, |
4797a61c | 775 | typename _Hash, typename _RangeHash, typename _Unused, |
4dad8b49 | 776 | typename _RehashPolicy, typename _Traits> |
612b4711 | 777 | auto |
d87105d6 | 778 | _Map_base<_Key, pair<const _Key, _Val>, _Alloc, _Select1st, _Equal, |
4797a61c | 779 | _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>:: |
4dad8b49 | 780 | operator[](key_type&& __k) |
612b4711 | 781 | -> mapped_type& |
fb7342fd | 782 | { |
4dad8b49 BK |
783 | __hashtable* __h = static_cast<__hashtable*>(this); |
784 | __hash_code __code = __h->_M_hash_code(__k); | |
4797a61c | 785 | std::size_t __bkt = __h->_M_bucket_index(__code); |
1b6f0476 | 786 | if (auto __node = __h->_M_find_node(__bkt, __k, __code)) |
b0c849fa FD |
787 | return __node->_M_v().second; |
788 | ||
789 | typename __hashtable::_Scoped_node __node { | |
790 | __h, | |
791 | std::piecewise_construct, | |
792 | std::forward_as_tuple(std::move(__k)), | |
793 | std::tuple<>() | |
794 | }; | |
795 | auto __pos | |
4797a61c | 796 | = __h->_M_insert_unique_node(__bkt, __code, __node._M_node); |
b0c849fa FD |
797 | __node._M_node = nullptr; |
798 | return __pos->second; | |
fb7342fd PC |
799 | } |
800 | ||
4dad8b49 BK |
801 | /** |
802 | * Primary class template _Insert_base. | |
803 | * | |
272b2ce4 | 804 | * Defines @c insert member functions appropriate to all _Hashtables. |
4dad8b49 BK |
805 | */ |
806 | template<typename _Key, typename _Value, typename _Alloc, | |
807 | typename _ExtractKey, typename _Equal, | |
4797a61c | 808 | typename _Hash, typename _RangeHash, typename _Unused, |
4dad8b49 BK |
809 | typename _RehashPolicy, typename _Traits> |
810 | struct _Insert_base | |
811 | { | |
b3abc9d8 | 812 | protected: |
4dad8b49 | 813 | using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey, |
4797a61c FD |
814 | _Equal, _Hash, _RangeHash, |
815 | _Unused, _Traits>; | |
816 | ||
817 | using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, | |
818 | _Hash, _RangeHash, | |
819 | _Unused, _RehashPolicy, _Traits>; | |
4dad8b49 | 820 | |
1b6f0476 FD |
821 | using __hash_cached = typename _Traits::__hash_cached; |
822 | using __constant_iterators = typename _Traits::__constant_iterators; | |
823 | ||
824 | using __hashtable_alloc = _Hashtable_alloc< | |
825 | __alloc_rebind<_Alloc, _Hash_node<_Value, | |
826 | __hash_cached::value>>>; | |
827 | ||
4dad8b49 | 828 | using value_type = typename __hashtable_base::value_type; |
4dad8b49 BK |
829 | using size_type = typename __hashtable_base::size_type; |
830 | ||
1b6f0476 FD |
831 | using __unique_keys = typename _Traits::__unique_keys; |
832 | using __node_alloc_type = typename __hashtable_alloc::__node_alloc_type; | |
b09bcf83 | 833 | using __node_gen_type = _AllocNode<__node_alloc_type>; |
4dad8b49 BK |
834 | |
835 | __hashtable& | |
836 | _M_conjure_hashtable() | |
837 | { return *(static_cast<__hashtable*>(this)); } | |
838 | ||
b3abc9d8 FD |
839 | template<typename _InputIterator, typename _NodeGetter> |
840 | void | |
841 | _M_insert_range(_InputIterator __first, _InputIterator __last, | |
6dcf0423 | 842 | const _NodeGetter&, true_type __uks); |
0f146257 FD |
843 | |
844 | template<typename _InputIterator, typename _NodeGetter> | |
845 | void | |
846 | _M_insert_range(_InputIterator __first, _InputIterator __last, | |
6dcf0423 | 847 | const _NodeGetter&, false_type __uks); |
b3abc9d8 FD |
848 | |
849 | public: | |
1b6f0476 FD |
850 | using iterator = _Node_iterator<_Value, __constant_iterators::value, |
851 | __hash_cached::value>; | |
852 | ||
a09bb4a8 JW |
853 | using const_iterator = _Node_const_iterator<_Value, |
854 | __constant_iterators::value, | |
1b6f0476 FD |
855 | __hash_cached::value>; |
856 | ||
a09bb4a8 JW |
857 | using __ireturn_type = __conditional_t<__unique_keys::value, |
858 | std::pair<iterator, bool>, | |
859 | iterator>; | |
1b6f0476 | 860 | |
4dad8b49 BK |
861 | __ireturn_type |
862 | insert(const value_type& __v) | |
863 | { | |
864 | __hashtable& __h = _M_conjure_hashtable(); | |
b3abc9d8 | 865 | __node_gen_type __node_gen(__h); |
6dcf0423 | 866 | return __h._M_insert(__v, __node_gen, __unique_keys{}); |
4dad8b49 BK |
867 | } |
868 | ||
869 | iterator | |
41349aec FD |
870 | insert(const_iterator __hint, const value_type& __v) |
871 | { | |
872 | __hashtable& __h = _M_conjure_hashtable(); | |
b3abc9d8 | 873 | __node_gen_type __node_gen(__h); |
6dcf0423 | 874 | return __h._M_insert(__hint, __v, __node_gen, __unique_keys{}); |
41349aec | 875 | } |
3b2524b1 | 876 | |
7688e5e8 FD |
877 | template<typename _KType, typename... _Args> |
878 | std::pair<iterator, bool> | |
879 | try_emplace(const_iterator, _KType&& __k, _Args&&... __args) | |
880 | { | |
881 | __hashtable& __h = _M_conjure_hashtable(); | |
882 | auto __code = __h._M_hash_code(__k); | |
4797a61c | 883 | std::size_t __bkt = __h._M_bucket_index(__code); |
1b6f0476 | 884 | if (auto __node = __h._M_find_node(__bkt, __k, __code)) |
7688e5e8 FD |
885 | return { iterator(__node), false }; |
886 | ||
887 | typename __hashtable::_Scoped_node __node { | |
888 | &__h, | |
889 | std::piecewise_construct, | |
890 | std::forward_as_tuple(std::forward<_KType>(__k)), | |
891 | std::forward_as_tuple(std::forward<_Args>(__args)...) | |
892 | }; | |
893 | auto __it | |
4797a61c | 894 | = __h._M_insert_unique_node(__bkt, __code, __node._M_node); |
7688e5e8 FD |
895 | __node._M_node = nullptr; |
896 | return { __it, true }; | |
897 | } | |
898 | ||
4dad8b49 BK |
899 | void |
900 | insert(initializer_list<value_type> __l) | |
901 | { this->insert(__l.begin(), __l.end()); } | |
902 | ||
903 | template<typename _InputIterator> | |
904 | void | |
b3abc9d8 FD |
905 | insert(_InputIterator __first, _InputIterator __last) |
906 | { | |
907 | __hashtable& __h = _M_conjure_hashtable(); | |
908 | __node_gen_type __node_gen(__h); | |
6dcf0423 | 909 | return _M_insert_range(__first, __last, __node_gen, __unique_keys{}); |
b3abc9d8 | 910 | } |
4dad8b49 BK |
911 | }; |
912 | ||
913 | template<typename _Key, typename _Value, typename _Alloc, | |
914 | typename _ExtractKey, typename _Equal, | |
4797a61c | 915 | typename _Hash, typename _RangeHash, typename _Unused, |
4dad8b49 | 916 | typename _RehashPolicy, typename _Traits> |
b3abc9d8 | 917 | template<typename _InputIterator, typename _NodeGetter> |
4dad8b49 | 918 | void |
4797a61c FD |
919 | _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, |
920 | _Hash, _RangeHash, _Unused, | |
921 | _RehashPolicy, _Traits>:: | |
b3abc9d8 | 922 | _M_insert_range(_InputIterator __first, _InputIterator __last, |
6dcf0423 | 923 | const _NodeGetter& __node_gen, true_type __uks) |
0f146257 | 924 | { |
0f146257 FD |
925 | __hashtable& __h = _M_conjure_hashtable(); |
926 | for (; __first != __last; ++__first) | |
6dcf0423 | 927 | __h._M_insert(*__first, __node_gen, __uks); |
0f146257 FD |
928 | } |
929 | ||
930 | template<typename _Key, typename _Value, typename _Alloc, | |
931 | typename _ExtractKey, typename _Equal, | |
4797a61c | 932 | typename _Hash, typename _RangeHash, typename _Unused, |
0f146257 FD |
933 | typename _RehashPolicy, typename _Traits> |
934 | template<typename _InputIterator, typename _NodeGetter> | |
935 | void | |
4797a61c FD |
936 | _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, |
937 | _Hash, _RangeHash, _Unused, | |
938 | _RehashPolicy, _Traits>:: | |
0f146257 | 939 | _M_insert_range(_InputIterator __first, _InputIterator __last, |
6dcf0423 | 940 | const _NodeGetter& __node_gen, false_type __uks) |
4dad8b49 BK |
941 | { |
942 | using __rehash_type = typename __hashtable::__rehash_type; | |
943 | using __rehash_state = typename __hashtable::__rehash_state; | |
944 | using pair_type = std::pair<bool, std::size_t>; | |
945 | ||
946 | size_type __n_elt = __detail::__distance_fw(__first, __last); | |
0f146257 FD |
947 | if (__n_elt == 0) |
948 | return; | |
4dad8b49 BK |
949 | |
950 | __hashtable& __h = _M_conjure_hashtable(); | |
951 | __rehash_type& __rehash = __h._M_rehash_policy; | |
952 | const __rehash_state& __saved_state = __rehash._M_state(); | |
953 | pair_type __do_rehash = __rehash._M_need_rehash(__h._M_bucket_count, | |
954 | __h._M_element_count, | |
955 | __n_elt); | |
956 | ||
957 | if (__do_rehash.first) | |
958 | __h._M_rehash(__do_rehash.second, __saved_state); | |
959 | ||
960 | for (; __first != __last; ++__first) | |
6dcf0423 | 961 | __h._M_insert(*__first, __node_gen, __uks); |
4dad8b49 BK |
962 | } |
963 | ||
964 | /** | |
965 | * Primary class template _Insert. | |
966 | * | |
272b2ce4 JW |
967 | * Defines @c insert member functions that depend on _Hashtable policies, |
968 | * via partial specializations. | |
4dad8b49 BK |
969 | */ |
970 | template<typename _Key, typename _Value, typename _Alloc, | |
971 | typename _ExtractKey, typename _Equal, | |
4797a61c | 972 | typename _Hash, typename _RangeHash, typename _Unused, |
4dad8b49 | 973 | typename _RehashPolicy, typename _Traits, |
732eb076 | 974 | bool _Constant_iterators = _Traits::__constant_iterators::value> |
4dad8b49 BK |
975 | struct _Insert; |
976 | ||
977 | /// Specialization. | |
978 | template<typename _Key, typename _Value, typename _Alloc, | |
979 | typename _ExtractKey, typename _Equal, | |
4797a61c | 980 | typename _Hash, typename _RangeHash, typename _Unused, |
4dad8b49 | 981 | typename _RehashPolicy, typename _Traits> |
4797a61c FD |
982 | struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, |
983 | _Hash, _RangeHash, _Unused, | |
732eb076 | 984 | _RehashPolicy, _Traits, true> |
4dad8b49 | 985 | : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, |
4797a61c | 986 | _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits> |
4dad8b49 BK |
987 | { |
988 | using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey, | |
4797a61c FD |
989 | _Equal, _Hash, _RangeHash, _Unused, |
990 | _RehashPolicy, _Traits>; | |
4dad8b49 | 991 | |
4dad8b49 BK |
992 | using value_type = typename __base_type::value_type; |
993 | using iterator = typename __base_type::iterator; | |
994 | using const_iterator = typename __base_type::const_iterator; | |
1b6f0476 | 995 | using __ireturn_type = typename __base_type::__ireturn_type; |
4dad8b49 BK |
996 | |
997 | using __unique_keys = typename __base_type::__unique_keys; | |
998 | using __hashtable = typename __base_type::__hashtable; | |
b3abc9d8 | 999 | using __node_gen_type = typename __base_type::__node_gen_type; |
4dad8b49 BK |
1000 | |
1001 | using __base_type::insert; | |
1002 | ||
732eb076 | 1003 | __ireturn_type |
4dad8b49 BK |
1004 | insert(value_type&& __v) |
1005 | { | |
1006 | __hashtable& __h = this->_M_conjure_hashtable(); | |
b3abc9d8 | 1007 | __node_gen_type __node_gen(__h); |
6dcf0423 | 1008 | return __h._M_insert(std::move(__v), __node_gen, __unique_keys{}); |
4dad8b49 BK |
1009 | } |
1010 | ||
1011 | iterator | |
41349aec FD |
1012 | insert(const_iterator __hint, value_type&& __v) |
1013 | { | |
1014 | __hashtable& __h = this->_M_conjure_hashtable(); | |
b3abc9d8 FD |
1015 | __node_gen_type __node_gen(__h); |
1016 | return __h._M_insert(__hint, std::move(__v), __node_gen, | |
6dcf0423 | 1017 | __unique_keys{}); |
41349aec FD |
1018 | } |
1019 | }; | |
4dad8b49 BK |
1020 | |
1021 | /// Specialization. | |
1022 | template<typename _Key, typename _Value, typename _Alloc, | |
1023 | typename _ExtractKey, typename _Equal, | |
4797a61c | 1024 | typename _Hash, typename _RangeHash, typename _Unused, |
732eb076 | 1025 | typename _RehashPolicy, typename _Traits> |
4797a61c FD |
1026 | struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, |
1027 | _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, false> | |
4dad8b49 | 1028 | : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, |
4797a61c | 1029 | _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits> |
3b2524b1 | 1030 | { |
4dad8b49 | 1031 | using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey, |
4797a61c | 1032 | _Equal, _Hash, _RangeHash, _Unused, |
4dad8b49 BK |
1033 | _RehashPolicy, _Traits>; |
1034 | using value_type = typename __base_type::value_type; | |
1035 | using iterator = typename __base_type::iterator; | |
1036 | using const_iterator = typename __base_type::const_iterator; | |
1037 | ||
1038 | using __unique_keys = typename __base_type::__unique_keys; | |
1039 | using __hashtable = typename __base_type::__hashtable; | |
1040 | using __ireturn_type = typename __base_type::__ireturn_type; | |
4dad8b49 BK |
1041 | |
1042 | using __base_type::insert; | |
1043 | ||
1044 | template<typename _Pair> | |
57cee56a | 1045 | using __is_cons = std::is_constructible<value_type, _Pair&&>; |
4dad8b49 BK |
1046 | |
1047 | template<typename _Pair> | |
57cee56a | 1048 | using _IFcons = std::enable_if<__is_cons<_Pair>::value>; |
4dad8b49 BK |
1049 | |
1050 | template<typename _Pair> | |
57cee56a | 1051 | using _IFconsp = typename _IFcons<_Pair>::type; |
4dad8b49 | 1052 | |
57cee56a | 1053 | template<typename _Pair, typename = _IFconsp<_Pair>> |
4dad8b49 BK |
1054 | __ireturn_type |
1055 | insert(_Pair&& __v) | |
1056 | { | |
1057 | __hashtable& __h = this->_M_conjure_hashtable(); | |
6dcf0423 | 1058 | return __h._M_emplace(__unique_keys{}, std::forward<_Pair>(__v)); |
4dad8b49 BK |
1059 | } |
1060 | ||
57cee56a | 1061 | template<typename _Pair, typename = _IFconsp<_Pair>> |
4dad8b49 | 1062 | iterator |
41349aec FD |
1063 | insert(const_iterator __hint, _Pair&& __v) |
1064 | { | |
1065 | __hashtable& __h = this->_M_conjure_hashtable(); | |
6dcf0423 | 1066 | return __h._M_emplace(__hint, __unique_keys{}, |
9f285ccb | 1067 | std::forward<_Pair>(__v)); |
41349aec | 1068 | } |
4dad8b49 BK |
1069 | }; |
1070 | ||
732eb076 FD |
1071 | template<typename _Policy> |
1072 | using __has_load_factor = typename _Policy::__has_load_factor; | |
1073 | ||
4dad8b49 BK |
1074 | /** |
1075 | * Primary class template _Rehash_base. | |
1076 | * | |
1077 | * Give hashtable the max_load_factor functions and reserve iff the | |
732eb076 | 1078 | * rehash policy supports it. |
4dad8b49 BK |
1079 | */ |
1080 | template<typename _Key, typename _Value, typename _Alloc, | |
1081 | typename _ExtractKey, typename _Equal, | |
4797a61c | 1082 | typename _Hash, typename _RangeHash, typename _Unused, |
732eb076 FD |
1083 | typename _RehashPolicy, typename _Traits, |
1084 | typename = | |
7cfe71d1 | 1085 | __detected_or_t<false_type, __has_load_factor, _RehashPolicy>> |
4dad8b49 BK |
1086 | struct _Rehash_base; |
1087 | ||
732eb076 | 1088 | /// Specialization when rehash policy doesn't provide load factor management. |
4dad8b49 BK |
1089 | template<typename _Key, typename _Value, typename _Alloc, |
1090 | typename _ExtractKey, typename _Equal, | |
4797a61c | 1091 | typename _Hash, typename _RangeHash, typename _Unused, |
732eb076 | 1092 | typename _RehashPolicy, typename _Traits> |
4dad8b49 | 1093 | struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, |
4797a61c FD |
1094 | _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, |
1095 | false_type /* Has load factor */> | |
732eb076 FD |
1096 | { |
1097 | }; | |
1098 | ||
1099 | /// Specialization when rehash policy provide load factor management. | |
1100 | template<typename _Key, typename _Value, typename _Alloc, | |
1101 | typename _ExtractKey, typename _Equal, | |
4797a61c | 1102 | typename _Hash, typename _RangeHash, typename _Unused, |
732eb076 FD |
1103 | typename _RehashPolicy, typename _Traits> |
1104 | struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, | |
4797a61c FD |
1105 | _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, |
1106 | true_type /* Has load factor */> | |
4dad8b49 BK |
1107 | { |
1108 | using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, | |
4797a61c | 1109 | _Equal, _Hash, _RangeHash, _Unused, |
732eb076 | 1110 | _RehashPolicy, _Traits>; |
4dad8b49 | 1111 | |
3b2524b1 | 1112 | float |
d3677132 | 1113 | max_load_factor() const noexcept |
3b2524b1 | 1114 | { |
4dad8b49 | 1115 | const __hashtable* __this = static_cast<const __hashtable*>(this); |
3b2524b1 PC |
1116 | return __this->__rehash_policy().max_load_factor(); |
1117 | } | |
1118 | ||
1119 | void | |
1120 | max_load_factor(float __z) | |
1121 | { | |
4dad8b49 | 1122 | __hashtable* __this = static_cast<__hashtable*>(this); |
732eb076 | 1123 | __this->__rehash_policy(_RehashPolicy(__z)); |
3b2524b1 | 1124 | } |
9155c0e3 PC |
1125 | |
1126 | void | |
1127 | reserve(std::size_t __n) | |
1128 | { | |
4dad8b49 | 1129 | __hashtable* __this = static_cast<__hashtable*>(this); |
de6f5f57 | 1130 | __this->rehash(__this->__rehash_policy()._M_bkt_for_elements(__n)); |
9155c0e3 | 1131 | } |
3b2524b1 PC |
1132 | }; |
1133 | ||
4dad8b49 BK |
1134 | /** |
1135 | * Primary class template _Hashtable_ebo_helper. | |
1136 | * | |
d872e4aa JW |
1137 | * Helper class using EBO when it is not forbidden (the type is not |
1138 | * final) and when it is worth it (the type is empty.) | |
4dad8b49 | 1139 | */ |
cc74ac5d | 1140 | template<int _Nm, typename _Tp, |
a188284c | 1141 | bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)> |
346afd84 | 1142 | struct _Hashtable_ebo_helper; |
a188284c | 1143 | |
4dad8b49 | 1144 | /// Specialization using EBO. |
cc74ac5d | 1145 | template<int _Nm, typename _Tp> |
970aa0b9 | 1146 | struct _Hashtable_ebo_helper<_Nm, _Tp, true> |
a13ab2bc | 1147 | : private _Tp |
a188284c | 1148 | { |
f8f0193b | 1149 | _Hashtable_ebo_helper() noexcept(noexcept(_Tp())) : _Tp() { } |
4dad8b49 | 1150 | |
b09bcf83 FD |
1151 | template<typename _OtherTp> |
1152 | _Hashtable_ebo_helper(_OtherTp&& __tp) | |
7cfe71d1 | 1153 | : _Tp(std::forward<_OtherTp>(__tp)) |
b09bcf83 | 1154 | { } |
a188284c | 1155 | |
1f6ea968 JW |
1156 | const _Tp& _M_cget() const { return static_cast<const _Tp&>(*this); } |
1157 | _Tp& _M_get() { return static_cast<_Tp&>(*this); } | |
a188284c FD |
1158 | }; |
1159 | ||
4dad8b49 | 1160 | /// Specialization not using EBO. |
cc74ac5d | 1161 | template<int _Nm, typename _Tp> |
346afd84 | 1162 | struct _Hashtable_ebo_helper<_Nm, _Tp, false> |
a188284c | 1163 | { |
346afd84 | 1164 | _Hashtable_ebo_helper() = default; |
4dad8b49 | 1165 | |
b09bcf83 FD |
1166 | template<typename _OtherTp> |
1167 | _Hashtable_ebo_helper(_OtherTp&& __tp) | |
7cfe71d1 | 1168 | : _M_tp(std::forward<_OtherTp>(__tp)) |
b09bcf83 | 1169 | { } |
a188284c | 1170 | |
1f6ea968 JW |
1171 | const _Tp& _M_cget() const { return _M_tp; } |
1172 | _Tp& _M_get() { return _M_tp; } | |
a188284c FD |
1173 | |
1174 | private: | |
f8f0193b | 1175 | _Tp _M_tp{}; |
a188284c FD |
1176 | }; |
1177 | ||
5b3be7cf FD |
1178 | /** |
1179 | * Primary class template _Local_iterator_base. | |
1180 | * | |
1181 | * Base class for local iterators, used to iterate within a bucket | |
1182 | * but not between buckets. | |
1183 | */ | |
1184 | template<typename _Key, typename _Value, typename _ExtractKey, | |
4797a61c | 1185 | typename _Hash, typename _RangeHash, typename _Unused, |
5b3be7cf FD |
1186 | bool __cache_hash_code> |
1187 | struct _Local_iterator_base; | |
1188 | ||
4dad8b49 BK |
1189 | /** |
1190 | * Primary class template _Hash_code_base. | |
1191 | * | |
1192 | * Encapsulates two policy issues that aren't quite orthogonal. | |
1193 | * (1) the difference between using a ranged hash function and using | |
1194 | * the combination of a hash function and a range-hashing function. | |
1195 | * In the former case we don't have such things as hash codes, so | |
1196 | * we have a dummy type as placeholder. | |
1197 | * (2) Whether or not we cache hash codes. Caching hash codes is | |
1198 | * meaningless if we have a ranged hash function. | |
1199 | * | |
1200 | * We also put the key extraction objects here, for convenience. | |
1201 | * Each specialization derives from one or more of the template | |
1202 | * parameters to benefit from Ebo. This is important as this type | |
1203 | * is inherited in some cases by the _Local_iterator_base type used | |
1204 | * to implement local_iterator and const_local_iterator. As with | |
1205 | * any iterator type we prefer to make it as small as possible. | |
4dad8b49 | 1206 | */ |
a188284c | 1207 | template<typename _Key, typename _Value, typename _ExtractKey, |
4797a61c | 1208 | typename _Hash, typename _RangeHash, typename _Unused, |
3b2524b1 | 1209 | bool __cache_hash_code> |
1b6f0476 | 1210 | struct _Hash_code_base |
9f9c0549 | 1211 | : private _Hashtable_ebo_helper<1, _Hash> |
3b2524b1 | 1212 | { |
a188284c | 1213 | private: |
9f9c0549 | 1214 | using __ebo_hash = _Hashtable_ebo_helper<1, _Hash>; |
a188284c | 1215 | |
92e16228 | 1216 | // Gives the local iterator implementation access to _M_bucket_index(). |
4797a61c FD |
1217 | friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, |
1218 | _Hash, _RangeHash, _Unused, false>; | |
92e16228 | 1219 | |
a188284c | 1220 | public: |
4797a61c | 1221 | typedef _Hash hasher; |
3b2524b1 PC |
1222 | |
1223 | hasher | |
1224 | hash_function() const | |
4797a61c | 1225 | { return _M_hash(); } |
3b2524b1 | 1226 | |
5b3be7cf | 1227 | protected: |
4dad8b49 | 1228 | typedef std::size_t __hash_code; |
4dad8b49 | 1229 | |
da27f556 FD |
1230 | // We need the default constructor for the local iterators and _Hashtable |
1231 | // default constructor. | |
d9a3647a | 1232 | _Hash_code_base() = default; |
f8f0193b | 1233 | |
4797a61c | 1234 | _Hash_code_base(const _Hash& __hash) : __ebo_hash(__hash) { } |
3b2524b1 | 1235 | |
4dad8b49 | 1236 | __hash_code |
3b2524b1 | 1237 | _M_hash_code(const _Key& __k) const |
e625ccc2 | 1238 | { |
4797a61c | 1239 | static_assert(__is_invocable<const _Hash&, const _Key&>{}, |
e625ccc2 | 1240 | "hash function must be invocable with an argument of key type"); |
4797a61c | 1241 | return _M_hash()(__k); |
e625ccc2 | 1242 | } |
7c3e9502 | 1243 | |
d2b1a684 FD |
1244 | template<typename _Kt> |
1245 | __hash_code | |
1246 | _M_hash_code_tr(const _Kt& __k) const | |
1247 | { | |
1248 | static_assert(__is_invocable<const _Hash&, const _Kt&>{}, | |
1249 | "hash function must be invocable with an argument of key type"); | |
1250 | return _M_hash()(__k); | |
1251 | } | |
1252 | ||
d10b863f FD |
1253 | __hash_code |
1254 | _M_hash_code(const _Hash&, | |
1255 | const _Hash_node_value<_Value, true>& __n) const | |
1256 | { return __n._M_hash_code; } | |
1257 | ||
1258 | // Compute hash code using _Hash as __n _M_hash_code, if present, was | |
1259 | // computed using _H2. | |
1260 | template<typename _H2> | |
1261 | __hash_code | |
1262 | _M_hash_code(const _H2&, | |
1263 | const _Hash_node_value<_Value, __cache_hash_code>& __n) const | |
1264 | { return _M_hash_code(_ExtractKey{}(__n._M_v())); } | |
1265 | ||
3b2524b1 | 1266 | std::size_t |
4797a61c FD |
1267 | _M_bucket_index(__hash_code __c, std::size_t __bkt_count) const |
1268 | { return _RangeHash{}(__c, __bkt_count); } | |
3b2524b1 PC |
1269 | |
1270 | std::size_t | |
1b6f0476 FD |
1271 | _M_bucket_index(const _Hash_node_value<_Value, false>& __n, |
1272 | std::size_t __bkt_count) const | |
4797a61c FD |
1273 | noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>())) |
1274 | && noexcept(declval<const _RangeHash&>()((__hash_code)0, | |
1275 | (std::size_t)0)) ) | |
1276 | { | |
1b6f0476 | 1277 | return _RangeHash{}(_M_hash_code(_ExtractKey{}(__n._M_v())), |
4797a61c FD |
1278 | __bkt_count); |
1279 | } | |
3b2524b1 | 1280 | |
1b6f0476 FD |
1281 | std::size_t |
1282 | _M_bucket_index(const _Hash_node_value<_Value, true>& __n, | |
1283 | std::size_t __bkt_count) const | |
1284 | noexcept( noexcept(declval<const _RangeHash&>()((__hash_code)0, | |
1285 | (std::size_t)0)) ) | |
1286 | { return _RangeHash{}(__n._M_hash_code, __bkt_count); } | |
3b2524b1 PC |
1287 | |
1288 | void | |
1b6f0476 | 1289 | _M_store_code(_Hash_node_code_cache<false>&, __hash_code) const |
3b2524b1 PC |
1290 | { } |
1291 | ||
1292 | void | |
1b6f0476 FD |
1293 | _M_copy_code(_Hash_node_code_cache<false>&, |
1294 | const _Hash_node_code_cache<false>&) const | |
1295 | { } | |
3b2524b1 PC |
1296 | |
1297 | void | |
1b6f0476 FD |
1298 | _M_store_code(_Hash_node_code_cache<true>& __n, __hash_code __c) const |
1299 | { __n._M_hash_code = __c; } | |
3b2524b1 PC |
1300 | |
1301 | void | |
1b6f0476 FD |
1302 | _M_copy_code(_Hash_node_code_cache<true>& __to, |
1303 | const _Hash_node_code_cache<true>& __from) const | |
1304 | { __to._M_hash_code = __from._M_hash_code; } | |
3b2524b1 PC |
1305 | |
1306 | void | |
1307 | _M_swap(_Hash_code_base& __x) | |
4797a61c | 1308 | { std::swap(__ebo_hash::_M_get(), __x.__ebo_hash::_M_get()); } |
4dad8b49 | 1309 | |
4797a61c FD |
1310 | const _Hash& |
1311 | _M_hash() const { return __ebo_hash::_M_cget(); } | |
a188284c FD |
1312 | }; |
1313 | ||
92e16228 | 1314 | /// Partial specialization used when nodes contain a cached hash code. |
a188284c | 1315 | template<typename _Key, typename _Value, typename _ExtractKey, |
4797a61c | 1316 | typename _Hash, typename _RangeHash, typename _Unused> |
a188284c | 1317 | struct _Local_iterator_base<_Key, _Value, _ExtractKey, |
4797a61c FD |
1318 | _Hash, _RangeHash, _Unused, true> |
1319 | : public _Node_iterator_base<_Value, true> | |
a188284c | 1320 | { |
5b3be7cf | 1321 | protected: |
acc1d1a9 | 1322 | using __base_node_iter = _Node_iterator_base<_Value, true>; |
5b3be7cf | 1323 | using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, |
4797a61c | 1324 | _Hash, _RangeHash, _Unused, true>; |
5b3be7cf | 1325 | |
a188284c | 1326 | _Local_iterator_base() = default; |
4797a61c | 1327 | _Local_iterator_base(const __hash_code_base&, |
5b3be7cf | 1328 | _Hash_node<_Value, true>* __p, |
a188284c | 1329 | std::size_t __bkt, std::size_t __bkt_count) |
4797a61c FD |
1330 | : __base_node_iter(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) |
1331 | { } | |
a188284c FD |
1332 | |
1333 | void | |
1334 | _M_incr() | |
1335 | { | |
acc1d1a9 FD |
1336 | __base_node_iter::_M_incr(); |
1337 | if (this->_M_cur) | |
a188284c | 1338 | { |
5b3be7cf | 1339 | std::size_t __bkt |
4797a61c | 1340 | = _RangeHash{}(this->_M_cur->_M_hash_code, _M_bucket_count); |
a188284c | 1341 | if (__bkt != _M_bucket) |
acc1d1a9 | 1342 | this->_M_cur = nullptr; |
a188284c FD |
1343 | } |
1344 | } | |
1345 | ||
a188284c FD |
1346 | std::size_t _M_bucket; |
1347 | std::size_t _M_bucket_count; | |
92e16228 JW |
1348 | |
1349 | public: | |
92e16228 JW |
1350 | std::size_t |
1351 | _M_get_bucket() const { return _M_bucket; } // for debug mode | |
1352 | }; | |
1353 | ||
1354 | // Uninitialized storage for a _Hash_code_base. | |
1355 | // This type is DefaultConstructible and Assignable even if the | |
1356 | // _Hash_code_base type isn't, so that _Local_iterator_base<..., false> | |
1357 | // can be DefaultConstructible and Assignable. | |
1358 | template<typename _Tp, bool _IsEmpty = std::is_empty<_Tp>::value> | |
1359 | struct _Hash_code_storage | |
1360 | { | |
1361 | __gnu_cxx::__aligned_buffer<_Tp> _M_storage; | |
1362 | ||
1363 | _Tp* | |
1364 | _M_h() { return _M_storage._M_ptr(); } | |
1365 | ||
1366 | const _Tp* | |
1367 | _M_h() const { return _M_storage._M_ptr(); } | |
1368 | }; | |
1369 | ||
1370 | // Empty partial specialization for empty _Hash_code_base types. | |
1371 | template<typename _Tp> | |
1372 | struct _Hash_code_storage<_Tp, true> | |
1373 | { | |
1374 | static_assert( std::is_empty<_Tp>::value, "Type must be empty" ); | |
1375 | ||
1376 | // As _Tp is an empty type there will be no bytes written/read through | |
1377 | // the cast pointer, so no strict-aliasing violation. | |
1378 | _Tp* | |
1379 | _M_h() { return reinterpret_cast<_Tp*>(this); } | |
1380 | ||
1381 | const _Tp* | |
1382 | _M_h() const { return reinterpret_cast<const _Tp*>(this); } | |
a188284c FD |
1383 | }; |
1384 | ||
92e16228 | 1385 | template<typename _Key, typename _Value, typename _ExtractKey, |
4797a61c | 1386 | typename _Hash, typename _RangeHash, typename _Unused> |
92e16228 JW |
1387 | using __hash_code_for_local_iter |
1388 | = _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey, | |
4797a61c | 1389 | _Hash, _RangeHash, _Unused, false>>; |
92e16228 JW |
1390 | |
1391 | // Partial specialization used when hash codes are not cached | |
a188284c | 1392 | template<typename _Key, typename _Value, typename _ExtractKey, |
4797a61c | 1393 | typename _Hash, typename _RangeHash, typename _Unused> |
a188284c | 1394 | struct _Local_iterator_base<_Key, _Value, _ExtractKey, |
4797a61c FD |
1395 | _Hash, _RangeHash, _Unused, false> |
1396 | : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _Hash, _RangeHash, | |
1397 | _Unused> | |
acc1d1a9 | 1398 | , _Node_iterator_base<_Value, false> |
a188284c | 1399 | { |
5b3be7cf FD |
1400 | protected: |
1401 | using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, | |
4797a61c | 1402 | _Hash, _RangeHash, _Unused, false>; |
acc1d1a9 | 1403 | using __node_iter_base = _Node_iterator_base<_Value, false>; |
5b3be7cf | 1404 | |
92e16228 JW |
1405 | _Local_iterator_base() : _M_bucket_count(-1) { } |
1406 | ||
5b3be7cf FD |
1407 | _Local_iterator_base(const __hash_code_base& __base, |
1408 | _Hash_node<_Value, false>* __p, | |
a188284c | 1409 | std::size_t __bkt, std::size_t __bkt_count) |
acc1d1a9 | 1410 | : __node_iter_base(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) |
92e16228 JW |
1411 | { _M_init(__base); } |
1412 | ||
1413 | ~_Local_iterator_base() | |
1414 | { | |
eb6b71b8 | 1415 | if (_M_bucket_count != size_t(-1)) |
92e16228 JW |
1416 | _M_destroy(); |
1417 | } | |
1418 | ||
1419 | _Local_iterator_base(const _Local_iterator_base& __iter) | |
1b6f0476 | 1420 | : __node_iter_base(__iter._M_cur), _M_bucket(__iter._M_bucket) |
acc1d1a9 | 1421 | , _M_bucket_count(__iter._M_bucket_count) |
92e16228 | 1422 | { |
eb6b71b8 | 1423 | if (_M_bucket_count != size_t(-1)) |
92e16228 JW |
1424 | _M_init(*__iter._M_h()); |
1425 | } | |
1426 | ||
1427 | _Local_iterator_base& | |
1428 | operator=(const _Local_iterator_base& __iter) | |
1429 | { | |
1430 | if (_M_bucket_count != -1) | |
1431 | _M_destroy(); | |
acc1d1a9 | 1432 | this->_M_cur = __iter._M_cur; |
92e16228 JW |
1433 | _M_bucket = __iter._M_bucket; |
1434 | _M_bucket_count = __iter._M_bucket_count; | |
1435 | if (_M_bucket_count != -1) | |
1436 | _M_init(*__iter._M_h()); | |
1437 | return *this; | |
1438 | } | |
a188284c FD |
1439 | |
1440 | void | |
1441 | _M_incr() | |
1442 | { | |
acc1d1a9 FD |
1443 | __node_iter_base::_M_incr(); |
1444 | if (this->_M_cur) | |
a188284c | 1445 | { |
1b6f0476 | 1446 | std::size_t __bkt = this->_M_h()->_M_bucket_index(*this->_M_cur, |
92e16228 | 1447 | _M_bucket_count); |
a188284c | 1448 | if (__bkt != _M_bucket) |
acc1d1a9 | 1449 | this->_M_cur = nullptr; |
a188284c FD |
1450 | } |
1451 | } | |
1452 | ||
a188284c FD |
1453 | std::size_t _M_bucket; |
1454 | std::size_t _M_bucket_count; | |
92e16228 JW |
1455 | |
1456 | void | |
1457 | _M_init(const __hash_code_base& __base) | |
1458 | { ::new(this->_M_h()) __hash_code_base(__base); } | |
1459 | ||
1460 | void | |
1461 | _M_destroy() { this->_M_h()->~__hash_code_base(); } | |
1462 | ||
1463 | public: | |
92e16228 JW |
1464 | std::size_t |
1465 | _M_get_bucket() const { return _M_bucket; } // for debug mode | |
a188284c FD |
1466 | }; |
1467 | ||
4dad8b49 | 1468 | /// local iterators |
a188284c | 1469 | template<typename _Key, typename _Value, typename _ExtractKey, |
4797a61c | 1470 | typename _Hash, typename _RangeHash, typename _Unused, |
a188284c FD |
1471 | bool __constant_iterators, bool __cache> |
1472 | struct _Local_iterator | |
1473 | : public _Local_iterator_base<_Key, _Value, _ExtractKey, | |
4797a61c | 1474 | _Hash, _RangeHash, _Unused, __cache> |
a188284c | 1475 | { |
5b3be7cf FD |
1476 | private: |
1477 | using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey, | |
4797a61c | 1478 | _Hash, _RangeHash, _Unused, __cache>; |
5b3be7cf | 1479 | using __hash_code_base = typename __base_type::__hash_code_base; |
acc1d1a9 | 1480 | |
5b3be7cf | 1481 | public: |
a09bb4a8 JW |
1482 | using value_type = _Value; |
1483 | using pointer = __conditional_t<__constant_iterators, | |
1484 | const value_type*, value_type*>; | |
1485 | using reference = __conditional_t<__constant_iterators, | |
1486 | const value_type&, value_type&>; | |
1487 | using difference_type = ptrdiff_t; | |
1488 | using iterator_category = forward_iterator_tag; | |
a188284c FD |
1489 | |
1490 | _Local_iterator() = default; | |
1491 | ||
5b3be7cf | 1492 | _Local_iterator(const __hash_code_base& __base, |
7cfe71d1 | 1493 | _Hash_node<_Value, __cache>* __n, |
a188284c | 1494 | std::size_t __bkt, std::size_t __bkt_count) |
7cfe71d1 | 1495 | : __base_type(__base, __n, __bkt, __bkt_count) |
a188284c FD |
1496 | { } |
1497 | ||
1498 | reference | |
1499 | operator*() const | |
0462b6aa | 1500 | { return this->_M_cur->_M_v(); } |
a188284c FD |
1501 | |
1502 | pointer | |
1503 | operator->() const | |
0462b6aa | 1504 | { return this->_M_cur->_M_valptr(); } |
a188284c FD |
1505 | |
1506 | _Local_iterator& | |
1507 | operator++() | |
1508 | { | |
1509 | this->_M_incr(); | |
1510 | return *this; | |
1511 | } | |
1512 | ||
1513 | _Local_iterator | |
1514 | operator++(int) | |
1515 | { | |
1516 | _Local_iterator __tmp(*this); | |
1517 | this->_M_incr(); | |
1518 | return __tmp; | |
1519 | } | |
1520 | }; | |
1521 | ||
4dad8b49 | 1522 | /// local const_iterators |
a188284c | 1523 | template<typename _Key, typename _Value, typename _ExtractKey, |
4797a61c | 1524 | typename _Hash, typename _RangeHash, typename _Unused, |
a188284c FD |
1525 | bool __constant_iterators, bool __cache> |
1526 | struct _Local_const_iterator | |
1527 | : public _Local_iterator_base<_Key, _Value, _ExtractKey, | |
4797a61c | 1528 | _Hash, _RangeHash, _Unused, __cache> |
a188284c | 1529 | { |
5b3be7cf FD |
1530 | private: |
1531 | using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey, | |
4797a61c | 1532 | _Hash, _RangeHash, _Unused, __cache>; |
5b3be7cf FD |
1533 | using __hash_code_base = typename __base_type::__hash_code_base; |
1534 | ||
1535 | public: | |
b09bcf83 | 1536 | typedef _Value value_type; |
1b6f0476 FD |
1537 | typedef const value_type* pointer; |
1538 | typedef const value_type& reference; | |
b09bcf83 FD |
1539 | typedef std::ptrdiff_t difference_type; |
1540 | typedef std::forward_iterator_tag iterator_category; | |
a188284c FD |
1541 | |
1542 | _Local_const_iterator() = default; | |
1543 | ||
5b3be7cf | 1544 | _Local_const_iterator(const __hash_code_base& __base, |
7cfe71d1 | 1545 | _Hash_node<_Value, __cache>* __n, |
a188284c | 1546 | std::size_t __bkt, std::size_t __bkt_count) |
7cfe71d1 | 1547 | : __base_type(__base, __n, __bkt, __bkt_count) |
a188284c FD |
1548 | { } |
1549 | ||
1550 | _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey, | |
4797a61c | 1551 | _Hash, _RangeHash, _Unused, |
a188284c FD |
1552 | __constant_iterators, |
1553 | __cache>& __x) | |
7cfe71d1 | 1554 | : __base_type(__x) |
a188284c FD |
1555 | { } |
1556 | ||
1557 | reference | |
1558 | operator*() const | |
0462b6aa | 1559 | { return this->_M_cur->_M_v(); } |
a188284c FD |
1560 | |
1561 | pointer | |
1562 | operator->() const | |
0462b6aa | 1563 | { return this->_M_cur->_M_valptr(); } |
a188284c FD |
1564 | |
1565 | _Local_const_iterator& | |
1566 | operator++() | |
1567 | { | |
1568 | this->_M_incr(); | |
1569 | return *this; | |
1570 | } | |
1571 | ||
1572 | _Local_const_iterator | |
1573 | operator++(int) | |
1574 | { | |
1575 | _Local_const_iterator __tmp(*this); | |
1576 | this->_M_incr(); | |
1577 | return __tmp; | |
1578 | } | |
3b2524b1 | 1579 | }; |
5dc22714 | 1580 | |
4dad8b49 BK |
1581 | /** |
1582 | * Primary class template _Hashtable_base. | |
1583 | * | |
af6204cc BK |
1584 | * Helper class adding management of _Equal functor to |
1585 | * _Hash_code_base type. | |
1586 | * | |
1587 | * Base class templates are: | |
1588 | * - __detail::_Hash_code_base | |
1589 | * - __detail::_Hashtable_ebo_helper | |
4dad8b49 | 1590 | */ |
4797a61c FD |
1591 | template<typename _Key, typename _Value, typename _ExtractKey, |
1592 | typename _Equal, typename _Hash, typename _RangeHash, | |
1593 | typename _Unused, typename _Traits> | |
1594 | struct _Hashtable_base | |
1595 | : public _Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, | |
1596 | _Unused, _Traits::__hash_cached::value>, | |
1b6f0476 FD |
1597 | private _Hashtable_ebo_helper<0, _Equal> |
1598 | { | |
1599 | public: | |
1600 | typedef _Key key_type; | |
1601 | typedef _Value value_type; | |
1602 | typedef _Equal key_equal; | |
1603 | typedef std::size_t size_type; | |
1604 | typedef std::ptrdiff_t difference_type; | |
eba20412 | 1605 | |
1b6f0476 FD |
1606 | using __traits_type = _Traits; |
1607 | using __hash_cached = typename __traits_type::__hash_cached; | |
f9d98fa7 | 1608 | |
1b6f0476 FD |
1609 | using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, |
1610 | _Hash, _RangeHash, _Unused, | |
1611 | __hash_cached::value>; | |
eba20412 | 1612 | |
1b6f0476 | 1613 | using __hash_code = typename __hash_code_base::__hash_code; |
4dad8b49 | 1614 | |
1b6f0476 FD |
1615 | private: |
1616 | using _EqualEBO = _Hashtable_ebo_helper<0, _Equal>; | |
4dad8b49 | 1617 | |
1b6f0476 FD |
1618 | static bool |
1619 | _S_equals(__hash_code, const _Hash_node_code_cache<false>&) | |
1620 | { return true; } | |
1621 | ||
1622 | static bool | |
1623 | _S_node_equals(const _Hash_node_code_cache<false>&, | |
1624 | const _Hash_node_code_cache<false>&) | |
1625 | { return true; } | |
1626 | ||
1627 | static bool | |
1628 | _S_equals(__hash_code __c, const _Hash_node_code_cache<true>& __n) | |
1629 | { return __c == __n._M_hash_code; } | |
1630 | ||
1631 | static bool | |
1632 | _S_node_equals(const _Hash_node_code_cache<true>& __lhn, | |
1633 | const _Hash_node_code_cache<true>& __rhn) | |
1634 | { return __lhn._M_hash_code == __rhn._M_hash_code; } | |
1635 | ||
1636 | protected: | |
1637 | _Hashtable_base() = default; | |
f8f0193b | 1638 | |
1b6f0476 FD |
1639 | _Hashtable_base(const _Hash& __hash, const _Equal& __eq) |
1640 | : __hash_code_base(__hash), _EqualEBO(__eq) | |
1641 | { } | |
1642 | ||
1643 | bool | |
1644 | _M_equals(const _Key& __k, __hash_code __c, | |
1645 | const _Hash_node_value<_Value, __hash_cached::value>& __n) const | |
1646 | { | |
1647 | static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{}, | |
e625ccc2 JW |
1648 | "key equality predicate must be invocable with two arguments of " |
1649 | "key type"); | |
1b6f0476 FD |
1650 | return _S_equals(__c, __n) && _M_eq()(__k, _ExtractKey{}(__n._M_v())); |
1651 | } | |
4dad8b49 | 1652 | |
d2b1a684 FD |
1653 | template<typename _Kt> |
1654 | bool | |
1655 | _M_equals_tr(const _Kt& __k, __hash_code __c, | |
1656 | const _Hash_node_value<_Value, | |
1657 | __hash_cached::value>& __n) const | |
1658 | { | |
1659 | static_assert( | |
1660 | __is_invocable<const _Equal&, const _Kt&, const _Key&>{}, | |
1661 | "key equality predicate must be invocable with two arguments of " | |
1662 | "key type"); | |
1663 | return _S_equals(__c, __n) && _M_eq()(__k, _ExtractKey{}(__n._M_v())); | |
1664 | } | |
1665 | ||
1b6f0476 FD |
1666 | bool |
1667 | _M_node_equals( | |
1668 | const _Hash_node_value<_Value, __hash_cached::value>& __lhn, | |
1669 | const _Hash_node_value<_Value, __hash_cached::value>& __rhn) const | |
1670 | { | |
1671 | return _S_node_equals(__lhn, __rhn) | |
1672 | && _M_eq()(_ExtractKey{}(__lhn._M_v()), _ExtractKey{}(__rhn._M_v())); | |
1673 | } | |
f9d98fa7 | 1674 | |
1b6f0476 FD |
1675 | void |
1676 | _M_swap(_Hashtable_base& __x) | |
1677 | { | |
1678 | __hash_code_base::_M_swap(__x); | |
1679 | std::swap(_EqualEBO::_M_get(), __x._EqualEBO::_M_get()); | |
1680 | } | |
4dad8b49 | 1681 | |
1b6f0476 FD |
1682 | const _Equal& |
1683 | _M_eq() const { return _EqualEBO::_M_cget(); } | |
1684 | }; | |
5dc22714 | 1685 | |
4dad8b49 BK |
1686 | /** |
1687 | * Primary class template _Equality. | |
1688 | * | |
1689 | * This is for implementing equality comparison for unordered | |
1690 | * containers, per N3068, by John Lakos and Pablo Halpern. | |
1691 | * Algorithmically, we follow closely the reference implementations | |
1692 | * therein. | |
1693 | */ | |
1694 | template<typename _Key, typename _Value, typename _Alloc, | |
1695 | typename _ExtractKey, typename _Equal, | |
4797a61c | 1696 | typename _Hash, typename _RangeHash, typename _Unused, |
4dad8b49 BK |
1697 | typename _RehashPolicy, typename _Traits, |
1698 | bool _Unique_keys = _Traits::__unique_keys::value> | |
1699 | struct _Equality; | |
1700 | ||
d9165389 | 1701 | /// unordered_map and unordered_set specializations. |
4dad8b49 BK |
1702 | template<typename _Key, typename _Value, typename _Alloc, |
1703 | typename _ExtractKey, typename _Equal, | |
4797a61c | 1704 | typename _Hash, typename _RangeHash, typename _Unused, |
4dad8b49 BK |
1705 | typename _RehashPolicy, typename _Traits> |
1706 | struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, | |
4797a61c | 1707 | _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true> |
4dad8b49 BK |
1708 | { |
1709 | using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, | |
4797a61c FD |
1710 | _Hash, _RangeHash, _Unused, |
1711 | _RehashPolicy, _Traits>; | |
4dad8b49 BK |
1712 | |
1713 | bool | |
1714 | _M_equal(const __hashtable&) const; | |
5dc22714 PC |
1715 | }; |
1716 | ||
4dad8b49 BK |
1717 | template<typename _Key, typename _Value, typename _Alloc, |
1718 | typename _ExtractKey, typename _Equal, | |
4797a61c | 1719 | typename _Hash, typename _RangeHash, typename _Unused, |
4dad8b49 | 1720 | typename _RehashPolicy, typename _Traits> |
5dc22714 | 1721 | bool |
4dad8b49 | 1722 | _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, |
4797a61c | 1723 | _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>:: |
4dad8b49 | 1724 | _M_equal(const __hashtable& __other) const |
5dc22714 | 1725 | { |
d9165389 | 1726 | using __node_type = typename __hashtable::__node_type; |
4dad8b49 | 1727 | const __hashtable* __this = static_cast<const __hashtable*>(this); |
5dc22714 PC |
1728 | if (__this->size() != __other.size()) |
1729 | return false; | |
1730 | ||
1731 | for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx) | |
1732 | { | |
1b6f0476 FD |
1733 | std::size_t __ybkt = __other._M_bucket_index(*__itx._M_cur); |
1734 | auto __prev_n = __other._M_buckets[__ybkt]; | |
d9165389 | 1735 | if (!__prev_n) |
5dc22714 | 1736 | return false; |
d9165389 FD |
1737 | |
1738 | for (__node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);; | |
1739 | __n = __n->_M_next()) | |
1740 | { | |
1741 | if (__n->_M_v() == *__itx) | |
1742 | break; | |
1743 | ||
1744 | if (!__n->_M_nxt | |
1b6f0476 | 1745 | || __other._M_bucket_index(*__n->_M_next()) != __ybkt) |
d9165389 FD |
1746 | return false; |
1747 | } | |
5dc22714 | 1748 | } |
d9165389 | 1749 | |
5dc22714 PC |
1750 | return true; |
1751 | } | |
1752 | ||
d9165389 | 1753 | /// unordered_multiset and unordered_multimap specializations. |
4dad8b49 BK |
1754 | template<typename _Key, typename _Value, typename _Alloc, |
1755 | typename _ExtractKey, typename _Equal, | |
4797a61c | 1756 | typename _Hash, typename _RangeHash, typename _Unused, |
4dad8b49 BK |
1757 | typename _RehashPolicy, typename _Traits> |
1758 | struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, | |
4797a61c | 1759 | _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, false> |
5dc22714 | 1760 | { |
4dad8b49 | 1761 | using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, |
4797a61c FD |
1762 | _Hash, _RangeHash, _Unused, |
1763 | _RehashPolicy, _Traits>; | |
5dc22714 | 1764 | |
5dc22714 | 1765 | bool |
4dad8b49 BK |
1766 | _M_equal(const __hashtable&) const; |
1767 | }; | |
5dc22714 | 1768 | |
4dad8b49 BK |
1769 | template<typename _Key, typename _Value, typename _Alloc, |
1770 | typename _ExtractKey, typename _Equal, | |
4797a61c | 1771 | typename _Hash, typename _RangeHash, typename _Unused, |
4dad8b49 | 1772 | typename _RehashPolicy, typename _Traits> |
5dc22714 | 1773 | bool |
4dad8b49 | 1774 | _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, |
4797a61c | 1775 | _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, false>:: |
4dad8b49 | 1776 | _M_equal(const __hashtable& __other) const |
5dc22714 | 1777 | { |
d9165389 | 1778 | using __node_type = typename __hashtable::__node_type; |
4dad8b49 | 1779 | const __hashtable* __this = static_cast<const __hashtable*>(this); |
5dc22714 PC |
1780 | if (__this->size() != __other.size()) |
1781 | return false; | |
1782 | ||
1783 | for (auto __itx = __this->begin(); __itx != __this->end();) | |
1784 | { | |
d9165389 FD |
1785 | std::size_t __x_count = 1; |
1786 | auto __itx_end = __itx; | |
1787 | for (++__itx_end; __itx_end != __this->end() | |
4797a61c FD |
1788 | && __this->key_eq()(_ExtractKey{}(*__itx), |
1789 | _ExtractKey{}(*__itx_end)); | |
d9165389 FD |
1790 | ++__itx_end) |
1791 | ++__x_count; | |
1792 | ||
1b6f0476 FD |
1793 | std::size_t __ybkt = __other._M_bucket_index(*__itx._M_cur); |
1794 | auto __y_prev_n = __other._M_buckets[__ybkt]; | |
d9165389 FD |
1795 | if (!__y_prev_n) |
1796 | return false; | |
1797 | ||
1798 | __node_type* __y_n = static_cast<__node_type*>(__y_prev_n->_M_nxt); | |
f9d98fa7 | 1799 | for (;;) |
d9165389 | 1800 | { |
4797a61c FD |
1801 | if (__this->key_eq()(_ExtractKey{}(__y_n->_M_v()), |
1802 | _ExtractKey{}(*__itx))) | |
d9165389 FD |
1803 | break; |
1804 | ||
1b6f0476 | 1805 | auto __y_ref_n = __y_n; |
f9d98fa7 | 1806 | for (__y_n = __y_n->_M_next(); __y_n; __y_n = __y_n->_M_next()) |
1b6f0476 | 1807 | if (!__other._M_node_equals(*__y_ref_n, *__y_n)) |
f9d98fa7 FD |
1808 | break; |
1809 | ||
1b6f0476 | 1810 | if (!__y_n || __other._M_bucket_index(*__y_n) != __ybkt) |
d9165389 FD |
1811 | return false; |
1812 | } | |
1813 | ||
1814 | typename __hashtable::const_iterator __ity(__y_n); | |
1815 | for (auto __ity_end = __ity; __ity_end != __other.end(); ++__ity_end) | |
1816 | if (--__x_count == 0) | |
1817 | break; | |
5dc22714 | 1818 | |
d9165389 | 1819 | if (__x_count != 0) |
5dc22714 PC |
1820 | return false; |
1821 | ||
d9165389 | 1822 | if (!std::is_permutation(__itx, __itx_end, __ity)) |
5dc22714 PC |
1823 | return false; |
1824 | ||
d9165389 | 1825 | __itx = __itx_end; |
5dc22714 PC |
1826 | } |
1827 | return true; | |
1828 | } | |
7c3e9502 | 1829 | |
0dd49691 | 1830 | /** |
b0c849fa FD |
1831 | * This type deals with all allocation and keeps an allocator instance |
1832 | * through inheritance to benefit from EBO when possible. | |
0dd49691 FD |
1833 | */ |
1834 | template<typename _NodeAlloc> | |
b09bcf83 | 1835 | struct _Hashtable_alloc : private _Hashtable_ebo_helper<0, _NodeAlloc> |
0dd49691 | 1836 | { |
b09bcf83 FD |
1837 | private: |
1838 | using __ebo_node_alloc = _Hashtable_ebo_helper<0, _NodeAlloc>; | |
64acc43d JW |
1839 | |
1840 | template<typename> | |
1841 | struct __get_value_type; | |
1842 | template<typename _Val, bool _Cache_hash_code> | |
1843 | struct __get_value_type<_Hash_node<_Val, _Cache_hash_code>> | |
1844 | { using type = _Val; }; | |
1845 | ||
b09bcf83 FD |
1846 | public: |
1847 | using __node_type = typename _NodeAlloc::value_type; | |
1848 | using __node_alloc_type = _NodeAlloc; | |
1849 | // Use __gnu_cxx to benefit from _S_always_equal and al. | |
1850 | using __node_alloc_traits = __gnu_cxx::__alloc_traits<__node_alloc_type>; | |
1851 | ||
b74f0db1 | 1852 | using __value_alloc_traits = typename __node_alloc_traits::template |
64acc43d | 1853 | rebind_traits<typename __get_value_type<__node_type>::type>; |
0dd49691 | 1854 | |
1b6f0476 FD |
1855 | using __node_ptr = __node_type*; |
1856 | using __node_base = _Hash_node_base; | |
1857 | using __node_base_ptr = __node_base*; | |
1858 | using __buckets_alloc_type = | |
1859 | __alloc_rebind<__node_alloc_type, __node_base_ptr>; | |
1860 | using __buckets_alloc_traits = std::allocator_traits<__buckets_alloc_type>; | |
1861 | using __buckets_ptr = __node_base_ptr*; | |
b09bcf83 | 1862 | |
da27f556 | 1863 | _Hashtable_alloc() = default; |
b09bcf83 FD |
1864 | _Hashtable_alloc(const _Hashtable_alloc&) = default; |
1865 | _Hashtable_alloc(_Hashtable_alloc&&) = default; | |
0dd49691 FD |
1866 | |
1867 | template<typename _Alloc> | |
b09bcf83 | 1868 | _Hashtable_alloc(_Alloc&& __a) |
7cfe71d1 | 1869 | : __ebo_node_alloc(std::forward<_Alloc>(__a)) |
0dd49691 | 1870 | { } |
b09bcf83 FD |
1871 | |
1872 | __node_alloc_type& | |
1873 | _M_node_allocator() | |
1f6ea968 | 1874 | { return __ebo_node_alloc::_M_get(); } |
b09bcf83 FD |
1875 | |
1876 | const __node_alloc_type& | |
1877 | _M_node_allocator() const | |
1f6ea968 | 1878 | { return __ebo_node_alloc::_M_cget(); } |
b09bcf83 | 1879 | |
b0c849fa | 1880 | // Allocate a node and construct an element within it. |
b09bcf83 | 1881 | template<typename... _Args> |
1b6f0476 | 1882 | __node_ptr |
b09bcf83 FD |
1883 | _M_allocate_node(_Args&&... __args); |
1884 | ||
b0c849fa | 1885 | // Destroy the element within a node and deallocate the node. |
b09bcf83 | 1886 | void |
1b6f0476 | 1887 | _M_deallocate_node(__node_ptr __n); |
b09bcf83 | 1888 | |
b0c849fa | 1889 | // Deallocate a node. |
23d5fd6c | 1890 | void |
1b6f0476 | 1891 | _M_deallocate_node_ptr(__node_ptr __n); |
23d5fd6c | 1892 | |
b0c849fa FD |
1893 | // Deallocate the linked list of nodes pointed to by __n. |
1894 | // The elements within the nodes are destroyed. | |
b09bcf83 | 1895 | void |
1b6f0476 | 1896 | _M_deallocate_nodes(__node_ptr __n); |
b09bcf83 | 1897 | |
1b6f0476 | 1898 | __buckets_ptr |
7cfe71d1 | 1899 | _M_allocate_buckets(std::size_t __bkt_count); |
b09bcf83 FD |
1900 | |
1901 | void | |
1b6f0476 | 1902 | _M_deallocate_buckets(__buckets_ptr, std::size_t __bkt_count); |
0dd49691 FD |
1903 | }; |
1904 | ||
b09bcf83 FD |
1905 | // Definitions of class template _Hashtable_alloc's out-of-line member |
1906 | // functions. | |
1907 | template<typename _NodeAlloc> | |
1908 | template<typename... _Args> | |
7cfe71d1 | 1909 | auto |
b09bcf83 | 1910 | _Hashtable_alloc<_NodeAlloc>::_M_allocate_node(_Args&&... __args) |
1b6f0476 | 1911 | -> __node_ptr |
b09bcf83 FD |
1912 | { |
1913 | auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1); | |
1b6f0476 | 1914 | __node_ptr __n = std::__to_address(__nptr); |
b09bcf83 FD |
1915 | __try |
1916 | { | |
ff90a89e | 1917 | ::new ((void*)__n) __node_type; |
b74f0db1 JW |
1918 | __node_alloc_traits::construct(_M_node_allocator(), |
1919 | __n->_M_valptr(), | |
1920 | std::forward<_Args>(__args)...); | |
b09bcf83 FD |
1921 | return __n; |
1922 | } | |
1923 | __catch(...) | |
1924 | { | |
1925 | __node_alloc_traits::deallocate(_M_node_allocator(), __nptr, 1); | |
1926 | __throw_exception_again; | |
1927 | } | |
1928 | } | |
1929 | ||
1930 | template<typename _NodeAlloc> | |
1931 | void | |
1b6f0476 | 1932 | _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node(__node_ptr __n) |
23d5fd6c FD |
1933 | { |
1934 | __node_alloc_traits::destroy(_M_node_allocator(), __n->_M_valptr()); | |
1935 | _M_deallocate_node_ptr(__n); | |
1936 | } | |
1937 | ||
1938 | template<typename _NodeAlloc> | |
1939 | void | |
1b6f0476 | 1940 | _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node_ptr(__node_ptr __n) |
b09bcf83 FD |
1941 | { |
1942 | typedef typename __node_alloc_traits::pointer _Ptr; | |
1943 | auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__n); | |
b09bcf83 FD |
1944 | __n->~__node_type(); |
1945 | __node_alloc_traits::deallocate(_M_node_allocator(), __ptr, 1); | |
1946 | } | |
1947 | ||
1948 | template<typename _NodeAlloc> | |
1949 | void | |
1b6f0476 | 1950 | _Hashtable_alloc<_NodeAlloc>::_M_deallocate_nodes(__node_ptr __n) |
b09bcf83 FD |
1951 | { |
1952 | while (__n) | |
1953 | { | |
1b6f0476 | 1954 | __node_ptr __tmp = __n; |
b09bcf83 FD |
1955 | __n = __n->_M_next(); |
1956 | _M_deallocate_node(__tmp); | |
1957 | } | |
1958 | } | |
1959 | ||
1960 | template<typename _NodeAlloc> | |
1b6f0476 | 1961 | auto |
7cfe71d1 | 1962 | _Hashtable_alloc<_NodeAlloc>::_M_allocate_buckets(std::size_t __bkt_count) |
1b6f0476 | 1963 | -> __buckets_ptr |
b09bcf83 | 1964 | { |
1b6f0476 | 1965 | __buckets_alloc_type __alloc(_M_node_allocator()); |
b09bcf83 | 1966 | |
1b6f0476 FD |
1967 | auto __ptr = __buckets_alloc_traits::allocate(__alloc, __bkt_count); |
1968 | __buckets_ptr __p = std::__to_address(__ptr); | |
1969 | __builtin_memset(__p, 0, __bkt_count * sizeof(__node_base_ptr)); | |
b09bcf83 FD |
1970 | return __p; |
1971 | } | |
1972 | ||
1973 | template<typename _NodeAlloc> | |
1974 | void | |
1b6f0476 FD |
1975 | _Hashtable_alloc<_NodeAlloc>:: |
1976 | _M_deallocate_buckets(__buckets_ptr __bkts, | |
1977 | std::size_t __bkt_count) | |
b09bcf83 | 1978 | { |
1b6f0476 | 1979 | typedef typename __buckets_alloc_traits::pointer _Ptr; |
b09bcf83 | 1980 | auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__bkts); |
1b6f0476 FD |
1981 | __buckets_alloc_type __alloc(_M_node_allocator()); |
1982 | __buckets_alloc_traits::deallocate(__alloc, __ptr, __bkt_count); | |
b09bcf83 FD |
1983 | } |
1984 | ||
f0b88346 | 1985 | ///@} hashtable-detail |
12ffa228 | 1986 | } // namespace __detail |
6667d5fe | 1987 | /// @endcond |
4a15d842 | 1988 | _GLIBCXX_END_NAMESPACE_VERSION |
12ffa228 | 1989 | } // namespace std |
3b2524b1 PC |
1990 | |
1991 | #endif // _HASHTABLE_POLICY_H |