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