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