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