Mercurial > hg > CbC > CbC_gcc

comparison libstdc++-v3/include/bits/hashtable_policy.h @ 145:1830386684a0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
gcc-9.2.0
author anatofuz
date Thu, 13 Feb 2020 11:34:05 +0900
parents 84e7813d76e9
children da32f4b04d38
comparison
equal deleted inserted replaced
131:84e7813d76e9 145:1830386684a0
1 // Internal policy header for unordered_set and unordered_map -*- C++ -*- 1 // Internal policy header for unordered_set and unordered_map -*- C++ -*-
2 2
3 // Copyright (C) 2010-2018 Free Software Foundation, Inc. 3 // Copyright (C) 2010-2020 Free Software Foundation, Inc.
4 // 4 //
5 // This file is part of the GNU ISO C++ Library. This library is free 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 6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the 7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option) 8 // Free Software Foundation; either version 3, or (at your option)
32 #define _HASHTABLE_POLICY_H 1 32 #define _HASHTABLE_POLICY_H 1
33 33
34 #include <tuple> // for std::tuple, std::forward_as_tuple 34 #include <tuple> // for std::tuple, std::forward_as_tuple
35 #include <limits> // for std::numeric_limits 35 #include <limits> // for std::numeric_limits
36 #include <bits/stl_algobase.h> // for std::min. 36 #include <bits/stl_algobase.h> // for std::min.
37 #include <bits/stl_algo.h> // for std::is_permutation.
37 38
38 namespace std _GLIBCXX_VISIBILITY(default) 39 namespace std _GLIBCXX_VISIBILITY(default)
39 { 40 {
40 _GLIBCXX_BEGIN_NAMESPACE_VERSION 41 _GLIBCXX_BEGIN_NAMESPACE_VERSION
41 42
109 typename __hashtable_alloc::__node_alloc_traits; 110 typename __hashtable_alloc::__node_alloc_traits;
110 using __node_type = typename __hashtable_alloc::__node_type; 111 using __node_type = typename __hashtable_alloc::__node_type;
111 112
112 public: 113 public:
113 _ReuseOrAllocNode(__node_type* __nodes, __hashtable_alloc& __h) 114 _ReuseOrAllocNode(__node_type* __nodes, __hashtable_alloc& __h)
114 : _M_nodes(__nodes), _M_h(__h) { } 115 : _M_nodes(__nodes), _M_h(__h) { }
115 _ReuseOrAllocNode(const _ReuseOrAllocNode&) = delete; 116 _ReuseOrAllocNode(const _ReuseOrAllocNode&) = delete;
116 117
117 ~_ReuseOrAllocNode() 118 ~_ReuseOrAllocNode()
118 { _M_h._M_deallocate_nodes(_M_nodes); } 119 { _M_h._M_deallocate_nodes(_M_nodes); }
119 120
133 __node_alloc_traits::construct(__a, __node->_M_valptr(), 134 __node_alloc_traits::construct(__a, __node->_M_valptr(),
134 std::forward<_Arg>(__arg)); 135 std::forward<_Arg>(__arg));
135 } 136 }
136 __catch(...) 137 __catch(...)
137 { 138 {
138 __node->~__node_type(); 139 _M_h._M_deallocate_node_ptr(__node);
139 __node_alloc_traits::deallocate(__a, __node, 1);
140 __throw_exception_again; 140 __throw_exception_again;
141 } 141 }
142 return __node; 142 return __node;
143 } 143 }
144 return _M_h._M_allocate_node(std::forward<_Arg>(__arg)); 144 return _M_h._M_allocate_node(std::forward<_Arg>(__arg));
158 using __hashtable_alloc = _Hashtable_alloc<_NodeAlloc>; 158 using __hashtable_alloc = _Hashtable_alloc<_NodeAlloc>;
159 using __node_type = typename __hashtable_alloc::__node_type; 159 using __node_type = typename __hashtable_alloc::__node_type;
160 160
161 public: 161 public:
162 _AllocNode(__hashtable_alloc& __h) 162 _AllocNode(__hashtable_alloc& __h)
163 : _M_h(__h) { } 163 : _M_h(__h) { }
164 164
165 template<typename _Arg> 165 template<typename _Arg>
166 __node_type* 166 __node_type*
167 operator()(_Arg&& __arg) const 167 operator()(_Arg&& __arg) const
168 { return _M_h._M_allocate_node(std::forward<_Arg>(__arg)); } 168 { return _M_h._M_allocate_node(std::forward<_Arg>(__arg)); }
180 * Important traits for hash tables. 180 * Important traits for hash tables.
181 * 181 *
182 * @tparam _Cache_hash_code Boolean value. True if the value of 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 183 * the hash function is stored along with the value. This is a
184 * time-space tradeoff. Storing it may improve lookup speed by 184 * time-space tradeoff. Storing it may improve lookup speed by
185 * reducing the number of times we need to call the _Equal 185 * reducing the number of times we need to call the _Hash or _Equal
186 * function. 186 * functors.
187 * 187 *
188 * @tparam _Constant_iterators Boolean value. True if iterator and 188 * @tparam _Constant_iterators Boolean value. True if iterator and
189 * const_iterator are both constant iterator types. This is true 189 * const_iterator are both constant iterator types. This is true
190 * for unordered_set and unordered_multiset, false for 190 * for unordered_set and unordered_multiset, false for
191 * unordered_map and unordered_multimap. 191 * unordered_map and unordered_multimap.
443 443
444 /// Default value for rehash policy. Bucket size is (usually) the 444 /// Default value for rehash policy. Bucket size is (usually) the
445 /// smallest prime that keeps the load factor small enough. 445 /// smallest prime that keeps the load factor small enough.
446 struct _Prime_rehash_policy 446 struct _Prime_rehash_policy
447 { 447 {
448 using __has_load_factor = std::true_type; 448 using __has_load_factor = true_type;
449 449
450 _Prime_rehash_policy(float __z = 1.0) noexcept 450 _Prime_rehash_policy(float __z = 1.0) noexcept
451 : _M_max_load_factor(__z), _M_next_resize(0) { } 451 : _M_max_load_factor(__z), _M_next_resize(0) { }
452 452
453 float 453 float
459 _M_next_bkt(std::size_t __n) const; 459 _M_next_bkt(std::size_t __n) const;
460 460
461 // Return a bucket count appropriate for n elements 461 // Return a bucket count appropriate for n elements
462 std::size_t 462 std::size_t
463 _M_bkt_for_elements(std::size_t __n) const 463 _M_bkt_for_elements(std::size_t __n) const
464 { return __builtin_ceil(__n / (long double)_M_max_load_factor); } 464 { return __builtin_ceill(__n / (long double)_M_max_load_factor); }
465 465
466 // __n_bkt is current bucket count, __n_elt is current element count, 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 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 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). 469 // is the new bucket count. If not, return make_pair(false, 0).
520 520
521 /// Rehash policy providing power of 2 bucket numbers. Avoids modulo 521 /// Rehash policy providing power of 2 bucket numbers. Avoids modulo
522 /// operations. 522 /// operations.
523 struct _Power2_rehash_policy 523 struct _Power2_rehash_policy
524 { 524 {
525 using __has_load_factor = std::true_type; 525 using __has_load_factor = true_type;
526 526
527 _Power2_rehash_policy(float __z = 1.0) noexcept 527 _Power2_rehash_policy(float __z = 1.0) noexcept
528 : _M_max_load_factor(__z), _M_next_resize(0) { } 528 : _M_max_load_factor(__z), _M_next_resize(0) { }
529 529
530 float 530 float
534 // Return a bucket size no smaller than n (as long as n is not above the 534 // Return a bucket size no smaller than n (as long as n is not above the
535 // highest power of 2). 535 // highest power of 2).
536 std::size_t 536 std::size_t
537 _M_next_bkt(std::size_t __n) noexcept 537 _M_next_bkt(std::size_t __n) noexcept
538 { 538 {
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
539 const auto __max_width = std::min<size_t>(sizeof(size_t), 8); 545 const auto __max_width = std::min<size_t>(sizeof(size_t), 8);
540 const auto __max_bkt = size_t(1) << (__max_width * __CHAR_BIT__ - 1); 546 const auto __max_bkt = size_t(1) << (__max_width * __CHAR_BIT__ - 1);
541 std::size_t __res = __clp2(__n); 547 std::size_t __res = __clp2(__n);
542 548
543 if (__res == __n)
544 __res <<= 1;
545
546 if (__res == 0) 549 if (__res == 0)
547 __res = __max_bkt; 550 __res = __max_bkt;
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;
548 556
549 if (__res == __max_bkt) 557 if (__res == __max_bkt)
550 // Set next resize to the max value so that we never try to rehash again 558 // Set next resize to the max value so that we never try to rehash again
551 // as we already reach the biggest possible bucket number. 559 // as we already reach the biggest possible bucket number.
552 // Note that it might result in max_load_factor not being respected. 560 // Note that it might result in max_load_factor not being respected.
553 _M_next_resize = std::size_t(-1); 561 _M_next_resize = numeric_limits<size_t>::max();
554 else 562 else
555 _M_next_resize 563 _M_next_resize
556 = __builtin_ceil(__res * (long double)_M_max_load_factor); 564 = __builtin_floorl(__res * (long double)_M_max_load_factor);
557 565
558 return __res; 566 return __res;
559 } 567 }
560 568
561 // Return a bucket count appropriate for n elements 569 // Return a bucket count appropriate for n elements
562 std::size_t 570 std::size_t
563 _M_bkt_for_elements(std::size_t __n) const noexcept 571 _M_bkt_for_elements(std::size_t __n) const noexcept
564 { return __builtin_ceil(__n / (long double)_M_max_load_factor); } 572 { return __builtin_ceill(__n / (long double)_M_max_load_factor); }
565 573
566 // __n_bkt is current bucket count, __n_elt is current element count, 574 // __n_bkt is current bucket count, __n_elt is current element count,
567 // and __n_ins is number of elements to be inserted. Do we need to 575 // and __n_ins is number of elements to be inserted. Do we need to
568 // increase bucket count? If so, return make_pair(true, n), where n 576 // increase bucket count? If so, return make_pair(true, n), where n
569 // is the new bucket count. If not, return make_pair(false, 0). 577 // is the new bucket count. If not, return make_pair(false, 0).
570 std::pair<bool, std::size_t> 578 std::pair<bool, std::size_t>
571 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, 579 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
572 std::size_t __n_ins) noexcept 580 std::size_t __n_ins) noexcept
573 { 581 {
574 if (__n_elt + __n_ins >= _M_next_resize) 582 if (__n_elt + __n_ins > _M_next_resize)
575 { 583 {
576 long double __min_bkts = (__n_elt + __n_ins) 584 // If _M_next_resize is 0 it means that we have nothing allocated so
577 / (long double)_M_max_load_factor; 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;
578 if (__min_bkts >= __n_bkt) 590 if (__min_bkts >= __n_bkt)
579 return std::make_pair(true, 591 return { true,
580 _M_next_bkt(std::max<std::size_t>(__builtin_floor(__min_bkts) + 1, 592 _M_next_bkt(std::max<std::size_t>(__builtin_floorl(__min_bkts) + 1,
581 __n_bkt * _S_growth_factor))); 593 __n_bkt * _S_growth_factor)) };
582 594
583 _M_next_resize 595 _M_next_resize
584 = __builtin_floor(__n_bkt * (long double)_M_max_load_factor); 596 = __builtin_floorl(__n_bkt * (long double)_M_max_load_factor);
585 return std::make_pair(false, 0); 597 return { false, 0 };
586 } 598 }
587 else 599 else
588 return std::make_pair(false, 0); 600 return { false, 0 };
589 } 601 }
590 602
591 typedef std::size_t _State; 603 typedef std::size_t _State;
592 604
593 _State 605 _State
692 operator[](const key_type& __k) 704 operator[](const key_type& __k)
693 -> mapped_type& 705 -> mapped_type&
694 { 706 {
695 __hashtable* __h = static_cast<__hashtable*>(this); 707 __hashtable* __h = static_cast<__hashtable*>(this);
696 __hash_code __code = __h->_M_hash_code(__k); 708 __hash_code __code = __h->_M_hash_code(__k);
697 std::size_t __n = __h->_M_bucket_index(__k, __code); 709 std::size_t __bkt = __h->_M_bucket_index(__k, __code);
698 __node_type* __p = __h->_M_find_node(__n, __k, __code); 710 if (__node_type* __node = __h->_M_find_node(__bkt, __k, __code))
699 711 return __node->_M_v().second;
700 if (!__p) 712
701 { 713 typename __hashtable::_Scoped_node __node {
702 __p = __h->_M_allocate_node(std::piecewise_construct, 714 __h,
703 std::tuple<const key_type&>(__k), 715 std::piecewise_construct,
704 std::tuple<>()); 716 std::tuple<const key_type&>(__k),
705 return __h->_M_insert_unique_node(__n, __code, __p)->second; 717 std::tuple<>()
706 } 718 };
707 719 auto __pos
708 return __p->_M_v().second; 720 = __h->_M_insert_unique_node(__k, __bkt, __code, __node._M_node);
721 __node._M_node = nullptr;
722 return __pos->second;
709 } 723 }
710 724
711 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, 725 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
712 typename _H1, typename _H2, typename _Hash, 726 typename _H1, typename _H2, typename _Hash,
713 typename _RehashPolicy, typename _Traits> 727 typename _RehashPolicy, typename _Traits>
717 operator[](key_type&& __k) 731 operator[](key_type&& __k)
718 -> mapped_type& 732 -> mapped_type&
719 { 733 {
720 __hashtable* __h = static_cast<__hashtable*>(this); 734 __hashtable* __h = static_cast<__hashtable*>(this);
721 __hash_code __code = __h->_M_hash_code(__k); 735 __hash_code __code = __h->_M_hash_code(__k);
722 std::size_t __n = __h->_M_bucket_index(__k, __code); 736 std::size_t __bkt = __h->_M_bucket_index(__k, __code);
723 __node_type* __p = __h->_M_find_node(__n, __k, __code); 737 if (__node_type* __node = __h->_M_find_node(__bkt, __k, __code))
724 738 return __node->_M_v().second;
725 if (!__p) 739
726 { 740 typename __hashtable::_Scoped_node __node {
727 __p = __h->_M_allocate_node(std::piecewise_construct, 741 __h,
728 std::forward_as_tuple(std::move(__k)), 742 std::piecewise_construct,
729 std::tuple<>()); 743 std::forward_as_tuple(std::move(__k)),
730 return __h->_M_insert_unique_node(__n, __code, __p)->second; 744 std::tuple<>()
731 } 745 };
732 746 auto __pos
733 return __p->_M_v().second; 747 = __h->_M_insert_unique_node(__k, __bkt, __code, __node._M_node);
748 __node._M_node = nullptr;
749 return __pos->second;
734 } 750 }
735 751
736 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, 752 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
737 typename _H1, typename _H2, typename _Hash, 753 typename _H1, typename _H2, typename _Hash,
738 typename _RehashPolicy, typename _Traits> 754 typename _RehashPolicy, typename _Traits>
742 at(const key_type& __k) 758 at(const key_type& __k)
743 -> mapped_type& 759 -> mapped_type&
744 { 760 {
745 __hashtable* __h = static_cast<__hashtable*>(this); 761 __hashtable* __h = static_cast<__hashtable*>(this);
746 __hash_code __code = __h->_M_hash_code(__k); 762 __hash_code __code = __h->_M_hash_code(__k);
747 std::size_t __n = __h->_M_bucket_index(__k, __code); 763 std::size_t __bkt = __h->_M_bucket_index(__k, __code);
748 __node_type* __p = __h->_M_find_node(__n, __k, __code); 764 __node_type* __p = __h->_M_find_node(__bkt, __k, __code);
749 765
750 if (!__p) 766 if (!__p)
751 __throw_out_of_range(__N("_Map_base::at")); 767 __throw_out_of_range(__N("_Map_base::at"));
752 return __p->_M_v().second; 768 return __p->_M_v().second;
753 } 769 }
761 at(const key_type& __k) const 777 at(const key_type& __k) const
762 -> const mapped_type& 778 -> const mapped_type&
763 { 779 {
764 const __hashtable* __h = static_cast<const __hashtable*>(this); 780 const __hashtable* __h = static_cast<const __hashtable*>(this);
765 __hash_code __code = __h->_M_hash_code(__k); 781 __hash_code __code = __h->_M_hash_code(__k);
766 std::size_t __n = __h->_M_bucket_index(__k, __code); 782 std::size_t __bkt = __h->_M_bucket_index(__k, __code);
767 __node_type* __p = __h->_M_find_node(__n, __k, __code); 783 __node_type* __p = __h->_M_find_node(__bkt, __k, __code);
768 784
769 if (!__p) 785 if (!__p)
770 __throw_out_of_range(__N("_Map_base::at")); 786 __throw_out_of_range(__N("_Map_base::at"));
771 return __p->_M_v().second; 787 return __p->_M_v().second;
772 } 788 }
1028 template<typename _Key, typename _Value, typename _Alloc, 1044 template<typename _Key, typename _Value, typename _Alloc,
1029 typename _ExtractKey, typename _Equal, 1045 typename _ExtractKey, typename _Equal,
1030 typename _H1, typename _H2, typename _Hash, 1046 typename _H1, typename _H2, typename _Hash,
1031 typename _RehashPolicy, typename _Traits, 1047 typename _RehashPolicy, typename _Traits,
1032 typename = 1048 typename =
1033 __detected_or_t<std::false_type, __has_load_factor, _RehashPolicy>> 1049 __detected_or_t<false_type, __has_load_factor, _RehashPolicy>>
1034 struct _Rehash_base; 1050 struct _Rehash_base;
1035 1051
1036 /// Specialization when rehash policy doesn't provide load factor management. 1052 /// Specialization when rehash policy doesn't provide load factor management.
1037 template<typename _Key, typename _Value, typename _Alloc, 1053 template<typename _Key, typename _Value, typename _Alloc,
1038 typename _ExtractKey, typename _Equal, 1054 typename _ExtractKey, typename _Equal,
1039 typename _H1, typename _H2, typename _Hash, 1055 typename _H1, typename _H2, typename _Hash,
1040 typename _RehashPolicy, typename _Traits> 1056 typename _RehashPolicy, typename _Traits>
1041 struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1057 struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1042 _H1, _H2, _Hash, _RehashPolicy, _Traits, 1058 _H1, _H2, _Hash, _RehashPolicy, _Traits,
1043 std::false_type> 1059 false_type>
1044 { 1060 {
1045 }; 1061 };
1046 1062
1047 /// Specialization when rehash policy provide load factor management. 1063 /// Specialization when rehash policy provide load factor management.
1048 template<typename _Key, typename _Value, typename _Alloc, 1064 template<typename _Key, typename _Value, typename _Alloc,
1049 typename _ExtractKey, typename _Equal, 1065 typename _ExtractKey, typename _Equal,
1050 typename _H1, typename _H2, typename _Hash, 1066 typename _H1, typename _H2, typename _Hash,
1051 typename _RehashPolicy, typename _Traits> 1067 typename _RehashPolicy, typename _Traits>
1052 struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1068 struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1053 _H1, _H2, _Hash, _RehashPolicy, _Traits, 1069 _H1, _H2, _Hash, _RehashPolicy, _Traits,
1054 std::true_type> 1070 true_type>
1055 { 1071 {
1056 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, 1072 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
1057 _Equal, _H1, _H2, _Hash, 1073 _Equal, _H1, _H2, _Hash,
1058 _RehashPolicy, _Traits>; 1074 _RehashPolicy, _Traits>;
1059 1075
1073 1089
1074 void 1090 void
1075 reserve(std::size_t __n) 1091 reserve(std::size_t __n)
1076 { 1092 {
1077 __hashtable* __this = static_cast<__hashtable*>(this); 1093 __hashtable* __this = static_cast<__hashtable*>(this);
1078 __this->rehash(__builtin_ceil(__n / max_load_factor())); 1094 __this->rehash(__this->__rehash_policy()._M_bkt_for_elements(__n));
1079 } 1095 }
1080 }; 1096 };
1081 1097
1082 /** 1098 /**
1083 * Primary class template _Hashtable_ebo_helper. 1099 * Primary class template _Hashtable_ebo_helper.
1096 { 1112 {
1097 _Hashtable_ebo_helper() = default; 1113 _Hashtable_ebo_helper() = default;
1098 1114
1099 template<typename _OtherTp> 1115 template<typename _OtherTp>
1100 _Hashtable_ebo_helper(_OtherTp&& __tp) 1116 _Hashtable_ebo_helper(_OtherTp&& __tp)
1101 : _Tp(std::forward<_OtherTp>(__tp)) 1117 : _Tp(std::forward<_OtherTp>(__tp))
1102 { } 1118 { }
1103 1119
1104 static const _Tp& 1120 const _Tp& _M_cget() const { return static_cast<const _Tp&>(*this); }
1105 _S_cget(const _Hashtable_ebo_helper& __eboh) 1121 _Tp& _M_get() { return static_cast<_Tp&>(*this); }
1106 { return static_cast<const _Tp&>(__eboh); }
1107
1108 static _Tp&
1109 _S_get(_Hashtable_ebo_helper& __eboh)
1110 { return static_cast<_Tp&>(__eboh); }
1111 }; 1122 };
1112 1123
1113 /// Specialization not using EBO. 1124 /// Specialization not using EBO.
1114 template<int _Nm, typename _Tp> 1125 template<int _Nm, typename _Tp>
1115 struct _Hashtable_ebo_helper<_Nm, _Tp, false> 1126 struct _Hashtable_ebo_helper<_Nm, _Tp, false>
1116 { 1127 {
1117 _Hashtable_ebo_helper() = default; 1128 _Hashtable_ebo_helper() = default;
1118 1129
1119 template<typename _OtherTp> 1130 template<typename _OtherTp>
1120 _Hashtable_ebo_helper(_OtherTp&& __tp) 1131 _Hashtable_ebo_helper(_OtherTp&& __tp)
1121 : _M_tp(std::forward<_OtherTp>(__tp)) 1132 : _M_tp(std::forward<_OtherTp>(__tp))
1122 { } 1133 { }
1123 1134
1124 static const _Tp& 1135 const _Tp& _M_cget() const { return _M_tp; }
1125 _S_cget(const _Hashtable_ebo_helper& __eboh) 1136 _Tp& _M_get() { return _M_tp; }
1126 { return __eboh._M_tp; }
1127
1128 static _Tp&
1129 _S_get(_Hashtable_ebo_helper& __eboh)
1130 { return __eboh._M_tp; }
1131 1137
1132 private: 1138 private:
1133 _Tp _M_tp; 1139 _Tp _M_tp;
1134 }; 1140 };
1135 1141
1196 __hash_code 1202 __hash_code
1197 _M_hash_code(const _Key& __key) const 1203 _M_hash_code(const _Key& __key) const
1198 { return 0; } 1204 { return 0; }
1199 1205
1200 std::size_t 1206 std::size_t
1201 _M_bucket_index(const _Key& __k, __hash_code, std::size_t __n) const 1207 _M_bucket_index(const _Key& __k, __hash_code,
1202 { return _M_ranged_hash()(__k, __n); } 1208 std::size_t __bkt_count) const
1209 { return _M_ranged_hash()(__k, __bkt_count); }
1203 1210
1204 std::size_t 1211 std::size_t
1205 _M_bucket_index(const __node_type* __p, std::size_t __n) const 1212 _M_bucket_index(const __node_type* __p, std::size_t __bkt_count) const
1206 noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>(), 1213 noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>(),
1207 (std::size_t)0)) ) 1214 (std::size_t)0)) )
1208 { return _M_ranged_hash()(_M_extract()(__p->_M_v()), __n); } 1215 { return _M_ranged_hash()(_M_extract()(__p->_M_v()), __bkt_count); }
1209 1216
1210 void 1217 void
1211 _M_store_code(__node_type*, __hash_code) const 1218 _M_store_code(__node_type*, __hash_code) const
1212 { } 1219 { }
1213 1220
1216 { } 1223 { }
1217 1224
1218 void 1225 void
1219 _M_swap(_Hash_code_base& __x) 1226 _M_swap(_Hash_code_base& __x)
1220 { 1227 {
1221 std::swap(_M_extract(), __x._M_extract()); 1228 std::swap(__ebo_extract_key::_M_get(),
1222 std::swap(_M_ranged_hash(), __x._M_ranged_hash()); 1229 __x.__ebo_extract_key::_M_get());
1230 std::swap(__ebo_hash::_M_get(), __x.__ebo_hash::_M_get());
1223 } 1231 }
1224 1232
1225 const _ExtractKey& 1233 const _ExtractKey&
1226 _M_extract() const { return __ebo_extract_key::_S_cget(*this); } 1234 _M_extract() const { return __ebo_extract_key::_M_cget(); }
1227
1228 _ExtractKey&
1229 _M_extract() { return __ebo_extract_key::_S_get(*this); }
1230 1235
1231 const _Hash& 1236 const _Hash&
1232 _M_ranged_hash() const { return __ebo_hash::_S_cget(*this); } 1237 _M_ranged_hash() const { return __ebo_hash::_M_cget(); }
1233
1234 _Hash&
1235 _M_ranged_hash() { return __ebo_hash::_S_get(*this); }
1236 }; 1238 };
1237 1239
1238 // No specialization for ranged hash function while caching hash codes. 1240 // No specialization for ranged hash function while caching hash codes.
1239 // That combination is meaningless, and trying to do it is an error. 1241 // That combination is meaningless, and trying to do it is an error.
1240 1242
1285 const _Default_ranged_hash&) 1287 const _Default_ranged_hash&)
1286 : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { } 1288 : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { }
1287 1289
1288 __hash_code 1290 __hash_code
1289 _M_hash_code(const _Key& __k) const 1291 _M_hash_code(const _Key& __k) const
1290 { return _M_h1()(__k); } 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 }
1291 1297
1292 std::size_t 1298 std::size_t
1293 _M_bucket_index(const _Key&, __hash_code __c, std::size_t __n) const 1299 _M_bucket_index(const _Key&, __hash_code __c,
1294 { return _M_h2()(__c, __n); } 1300 std::size_t __bkt_count) const
1301 { return _M_h2()(__c, __bkt_count); }
1295 1302
1296 std::size_t 1303 std::size_t
1297 _M_bucket_index(const __node_type* __p, std::size_t __n) const 1304 _M_bucket_index(const __node_type* __p, std::size_t __bkt_count) const
1298 noexcept( noexcept(declval<const _H1&>()(declval<const _Key&>())) 1305 noexcept( noexcept(declval<const _H1&>()(declval<const _Key&>()))
1299 && noexcept(declval<const _H2&>()((__hash_code)0, 1306 && noexcept(declval<const _H2&>()((__hash_code)0,
1300 (std::size_t)0)) ) 1307 (std::size_t)0)) )
1301 { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v())), __n); } 1308 { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v())), __bkt_count); }
1302 1309
1303 void 1310 void
1304 _M_store_code(__node_type*, __hash_code) const 1311 _M_store_code(__node_type*, __hash_code) const
1305 { } 1312 { }
1306 1313
1309 { } 1316 { }
1310 1317
1311 void 1318 void
1312 _M_swap(_Hash_code_base& __x) 1319 _M_swap(_Hash_code_base& __x)
1313 { 1320 {
1314 std::swap(_M_extract(), __x._M_extract()); 1321 std::swap(__ebo_extract_key::_M_get(),
1315 std::swap(_M_h1(), __x._M_h1()); 1322 __x.__ebo_extract_key::_M_get());
1316 std::swap(_M_h2(), __x._M_h2()); 1323 std::swap(__ebo_h1::_M_get(), __x.__ebo_h1::_M_get());
1324 std::swap(__ebo_h2::_M_get(), __x.__ebo_h2::_M_get());
1317 } 1325 }
1318 1326
1319 const _ExtractKey& 1327 const _ExtractKey&
1320 _M_extract() const { return __ebo_extract_key::_S_cget(*this); } 1328 _M_extract() const { return __ebo_extract_key::_M_cget(); }
1321
1322 _ExtractKey&
1323 _M_extract() { return __ebo_extract_key::_S_get(*this); }
1324 1329
1325 const _H1& 1330 const _H1&
1326 _M_h1() const { return __ebo_h1::_S_cget(*this); } 1331 _M_h1() const { return __ebo_h1::_M_cget(); }
1327
1328 _H1&
1329 _M_h1() { return __ebo_h1::_S_get(*this); }
1330 1332
1331 const _H2& 1333 const _H2&
1332 _M_h2() const { return __ebo_h2::_S_cget(*this); } 1334 _M_h2() const { return __ebo_h2::_M_cget(); }
1333
1334 _H2&
1335 _M_h2() { return __ebo_h2::_S_get(*this); }
1336 }; 1335 };
1337 1336
1338 /// Specialization: hash function and range-hashing function, 1337 /// Specialization: hash function and range-hashing function,
1339 /// caching hash codes. H is provided but ignored. Provides 1338 /// caching hash codes. H is provided but ignored. Provides
1340 /// typedef and accessor required by C++ 11. 1339 /// typedef and accessor required by C++ 11.
1373 const _Default_ranged_hash&) 1372 const _Default_ranged_hash&)
1374 : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { } 1373 : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { }
1375 1374
1376 __hash_code 1375 __hash_code
1377 _M_hash_code(const _Key& __k) const 1376 _M_hash_code(const _Key& __k) const
1378 { return _M_h1()(__k); } 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 }
1379 1382
1380 std::size_t 1383 std::size_t
1381 _M_bucket_index(const _Key&, __hash_code __c, 1384 _M_bucket_index(const _Key&, __hash_code __c,
1382 std::size_t __n) const 1385 std::size_t __bkt_count) const
1383 { return _M_h2()(__c, __n); } 1386 { return _M_h2()(__c, __bkt_count); }
1384 1387
1385 std::size_t 1388 std::size_t
1386 _M_bucket_index(const __node_type* __p, std::size_t __n) const 1389 _M_bucket_index(const __node_type* __p, std::size_t __bkt_count) const
1387 noexcept( noexcept(declval<const _H2&>()((__hash_code)0, 1390 noexcept( noexcept(declval<const _H2&>()((__hash_code)0,
1388 (std::size_t)0)) ) 1391 (std::size_t)0)) )
1389 { return _M_h2()(__p->_M_hash_code, __n); } 1392 { return _M_h2()(__p->_M_hash_code, __bkt_count); }
1390 1393
1391 void 1394 void
1392 _M_store_code(__node_type* __n, __hash_code __c) const 1395 _M_store_code(__node_type* __n, __hash_code __c) const
1393 { __n->_M_hash_code = __c; } 1396 { __n->_M_hash_code = __c; }
1394 1397
1397 { __to->_M_hash_code = __from->_M_hash_code; } 1400 { __to->_M_hash_code = __from->_M_hash_code; }
1398 1401
1399 void 1402 void
1400 _M_swap(_Hash_code_base& __x) 1403 _M_swap(_Hash_code_base& __x)
1401 { 1404 {
1402 std::swap(_M_extract(), __x._M_extract()); 1405 std::swap(__ebo_extract_key::_M_get(),
1403 std::swap(_M_h1(), __x._M_h1()); 1406 __x.__ebo_extract_key::_M_get());
1404 std::swap(_M_h2(), __x._M_h2()); 1407 std::swap(__ebo_h1::_M_get(), __x.__ebo_h1::_M_get());
1408 std::swap(__ebo_h2::_M_get(), __x.__ebo_h2::_M_get());
1405 } 1409 }
1406 1410
1407 const _ExtractKey& 1411 const _ExtractKey&
1408 _M_extract() const { return __ebo_extract_key::_S_cget(*this); } 1412 _M_extract() const { return __ebo_extract_key::_M_cget(); }
1409
1410 _ExtractKey&
1411 _M_extract() { return __ebo_extract_key::_S_get(*this); }
1412 1413
1413 const _H1& 1414 const _H1&
1414 _M_h1() const { return __ebo_h1::_S_cget(*this); } 1415 _M_h1() const { return __ebo_h1::_M_cget(); }
1415
1416 _H1&
1417 _M_h1() { return __ebo_h1::_S_get(*this); }
1418 1416
1419 const _H2& 1417 const _H2&
1420 _M_h2() const { return __ebo_h2::_S_cget(*this); } 1418 _M_h2() const { return __ebo_h2::_M_cget(); }
1421 1419 };
1422 _H2&
1423 _M_h2() { return __ebo_h2::_S_get(*this); }
1424 };
1425
1426 /**
1427 * Primary class template _Equal_helper.
1428 *
1429 */
1430 template <typename _Key, typename _Value, typename _ExtractKey,
1431 typename _Equal, typename _HashCodeType,
1432 bool __cache_hash_code>
1433 struct _Equal_helper;
1434
1435 /// Specialization.
1436 template<typename _Key, typename _Value, typename _ExtractKey,
1437 typename _Equal, typename _HashCodeType>
1438 struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, true>
1439 {
1440 static bool
1441 _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
1442 const _Key& __k, _HashCodeType __c, _Hash_node<_Value, true>* __n)
1443 { return __c == __n->_M_hash_code && __eq(__k, __extract(__n->_M_v())); }
1444 };
1445
1446 /// Specialization.
1447 template<typename _Key, typename _Value, typename _ExtractKey,
1448 typename _Equal, typename _HashCodeType>
1449 struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, false>
1450 {
1451 static bool
1452 _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
1453 const _Key& __k, _HashCodeType, _Hash_node<_Value, false>* __n)
1454 { return __eq(__k, __extract(__n->_M_v())); }
1455 };
1456
1457 1420
1458 /// Partial specialization used when nodes contain a cached hash code. 1421 /// Partial specialization used when nodes contain a cached hash code.
1459 template<typename _Key, typename _Value, typename _ExtractKey, 1422 template<typename _Key, typename _Value, typename _ExtractKey,
1460 typename _H1, typename _H2, typename _Hash> 1423 typename _H1, typename _H2, typename _Hash>
1461 struct _Local_iterator_base<_Key, _Value, _ExtractKey, 1424 struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1479 { 1442 {
1480 _M_cur = _M_cur->_M_next(); 1443 _M_cur = _M_cur->_M_next();
1481 if (_M_cur) 1444 if (_M_cur)
1482 { 1445 {
1483 std::size_t __bkt 1446 std::size_t __bkt
1484 = __base_type::_S_get(*this)(_M_cur->_M_hash_code, 1447 = __base_type::_M_get()(_M_cur->_M_hash_code,
1485 _M_bucket_count); 1448 _M_bucket_count);
1486 if (__bkt != _M_bucket) 1449 if (__bkt != _M_bucket)
1487 _M_cur = nullptr; 1450 _M_cur = nullptr;
1488 } 1451 }
1489 } 1452 }
1657 typedef std::forward_iterator_tag iterator_category; 1620 typedef std::forward_iterator_tag iterator_category;
1658 1621
1659 _Local_iterator() = default; 1622 _Local_iterator() = default;
1660 1623
1661 _Local_iterator(const __hash_code_base& __base, 1624 _Local_iterator(const __hash_code_base& __base,
1662 _Hash_node<_Value, __cache>* __p, 1625 _Hash_node<_Value, __cache>* __n,
1663 std::size_t __bkt, std::size_t __bkt_count) 1626 std::size_t __bkt, std::size_t __bkt_count)
1664 : __base_type(__base, __p, __bkt, __bkt_count) 1627 : __base_type(__base, __n, __bkt, __bkt_count)
1665 { } 1628 { }
1666 1629
1667 reference 1630 reference
1668 operator*() const 1631 operator*() const
1669 { return this->_M_cur->_M_v(); } 1632 { return this->_M_cur->_M_v(); }
1709 typedef std::forward_iterator_tag iterator_category; 1672 typedef std::forward_iterator_tag iterator_category;
1710 1673
1711 _Local_const_iterator() = default; 1674 _Local_const_iterator() = default;
1712 1675
1713 _Local_const_iterator(const __hash_code_base& __base, 1676 _Local_const_iterator(const __hash_code_base& __base,
1714 _Hash_node<_Value, __cache>* __p, 1677 _Hash_node<_Value, __cache>* __n,
1715 std::size_t __bkt, std::size_t __bkt_count) 1678 std::size_t __bkt, std::size_t __bkt_count)
1716 : __base_type(__base, __p, __bkt, __bkt_count) 1679 : __base_type(__base, __n, __bkt, __bkt_count)
1717 { } 1680 { }
1718 1681
1719 _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey, 1682 _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey,
1720 _H1, _H2, _Hash, 1683 _H1, _H2, _Hash,
1721 __constant_iterators, 1684 __constant_iterators,
1722 __cache>& __x) 1685 __cache>& __x)
1723 : __base_type(__x) 1686 : __base_type(__x)
1724 { } 1687 { }
1725 1688
1726 reference 1689 reference
1727 operator*() const 1690 operator*() const
1728 { return this->_M_cur->_M_v(); } 1691 { return this->_M_cur->_M_v(); }
1806 using __ireturn_type = typename std::conditional<__unique_keys::value, 1769 using __ireturn_type = typename std::conditional<__unique_keys::value,
1807 std::pair<iterator, bool>, 1770 std::pair<iterator, bool>,
1808 iterator>::type; 1771 iterator>::type;
1809 private: 1772 private:
1810 using _EqualEBO = _Hashtable_ebo_helper<0, _Equal>; 1773 using _EqualEBO = _Hashtable_ebo_helper<0, _Equal>;
1811 using _EqualHelper = _Equal_helper<_Key, _Value, _ExtractKey, _Equal, 1774
1812 __hash_code, __hash_cached::value>; 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 };
1813 1790
1814 protected: 1791 protected:
1815 _Hashtable_base() = default; 1792 _Hashtable_base() = default;
1816 _Hashtable_base(const _ExtractKey& __ex, const _H1& __h1, const _H2& __h2, 1793 _Hashtable_base(const _ExtractKey& __ex, const _H1& __h1, const _H2& __h2,
1817 const _Hash& __hash, const _Equal& __eq) 1794 const _Hash& __hash, const _Equal& __eq)
1819 { } 1796 { }
1820 1797
1821 bool 1798 bool
1822 _M_equals(const _Key& __k, __hash_code __c, __node_type* __n) const 1799 _M_equals(const _Key& __k, __hash_code __c, __node_type* __n) const
1823 { 1800 {
1824 return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(), 1801 static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{},
1825 __k, __c, __n); 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()));
1826 } 1806 }
1827 1807
1828 void 1808 void
1829 _M_swap(_Hashtable_base& __x) 1809 _M_swap(_Hashtable_base& __x)
1830 { 1810 {
1831 __hash_code_base::_M_swap(__x); 1811 __hash_code_base::_M_swap(__x);
1832 std::swap(_M_eq(), __x._M_eq()); 1812 std::swap(_EqualEBO::_M_get(), __x._EqualEBO::_M_get());
1833 } 1813 }
1834 1814
1835 const _Equal& 1815 const _Equal&
1836 _M_eq() const { return _EqualEBO::_S_cget(*this); } 1816 _M_eq() const { return _EqualEBO::_M_cget(); }
1837
1838 _Equal&
1839 _M_eq() { return _EqualEBO::_S_get(*this); }
1840 }; 1817 };
1841
1842 /**
1843 * struct _Equality_base.
1844 *
1845 * Common types and functions for class _Equality.
1846 */
1847 struct _Equality_base
1848 {
1849 protected:
1850 template<typename _Uiterator>
1851 static bool
1852 _S_is_permutation(_Uiterator, _Uiterator, _Uiterator);
1853 };
1854
1855 // See std::is_permutation in N3068.
1856 template<typename _Uiterator>
1857 bool
1858 _Equality_base::
1859 _S_is_permutation(_Uiterator __first1, _Uiterator __last1,
1860 _Uiterator __first2)
1861 {
1862 for (; __first1 != __last1; ++__first1, ++__first2)
1863 if (!(*__first1 == *__first2))
1864 break;
1865
1866 if (__first1 == __last1)
1867 return true;
1868
1869 _Uiterator __last2 = __first2;
1870 std::advance(__last2, std::distance(__first1, __last1));
1871
1872 for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1)
1873 {
1874 _Uiterator __tmp = __first1;
1875 while (__tmp != __it1 && !bool(*__tmp == *__it1))
1876 ++__tmp;
1877
1878 // We've seen this one before.
1879 if (__tmp != __it1)
1880 continue;
1881
1882 std::ptrdiff_t __n2 = 0;
1883 for (__tmp = __first2; __tmp != __last2; ++__tmp)
1884 if (*__tmp == *__it1)
1885 ++__n2;
1886
1887 if (!__n2)
1888 return false;
1889
1890 std::ptrdiff_t __n1 = 0;
1891 for (__tmp = __it1; __tmp != __last1; ++__tmp)
1892 if (*__tmp == *__it1)
1893 ++__n1;
1894
1895 if (__n1 != __n2)
1896 return false;
1897 }
1898 return true;
1899 }
1900 1818
1901 /** 1819 /**
1902 * Primary class template _Equality. 1820 * Primary class template _Equality.
1903 * 1821 *
1904 * This is for implementing equality comparison for unordered 1822 * This is for implementing equality comparison for unordered
1911 typename _H1, typename _H2, typename _Hash, 1829 typename _H1, typename _H2, typename _Hash,
1912 typename _RehashPolicy, typename _Traits, 1830 typename _RehashPolicy, typename _Traits,
1913 bool _Unique_keys = _Traits::__unique_keys::value> 1831 bool _Unique_keys = _Traits::__unique_keys::value>
1914 struct _Equality; 1832 struct _Equality;
1915 1833
1916 /// Specialization. 1834 /// unordered_map and unordered_set specializations.
1917 template<typename _Key, typename _Value, typename _Alloc, 1835 template<typename _Key, typename _Value, typename _Alloc,
1918 typename _ExtractKey, typename _Equal, 1836 typename _ExtractKey, typename _Equal,
1919 typename _H1, typename _H2, typename _Hash, 1837 typename _H1, typename _H2, typename _Hash,
1920 typename _RehashPolicy, typename _Traits> 1838 typename _RehashPolicy, typename _Traits>
1921 struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1839 struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1935 bool 1853 bool
1936 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1854 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1937 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: 1855 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
1938 _M_equal(const __hashtable& __other) const 1856 _M_equal(const __hashtable& __other) const
1939 { 1857 {
1858 using __node_base = typename __hashtable::__node_base;
1859 using __node_type = typename __hashtable::__node_type;
1940 const __hashtable* __this = static_cast<const __hashtable*>(this); 1860 const __hashtable* __this = static_cast<const __hashtable*>(this);
1941
1942 if (__this->size() != __other.size()) 1861 if (__this->size() != __other.size())
1943 return false; 1862 return false;
1944 1863
1945 for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx) 1864 for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
1946 { 1865 {
1947 const auto __ity = __other.find(_ExtractKey()(*__itx)); 1866 std::size_t __ybkt = __other._M_bucket_index(__itx._M_cur);
1948 if (__ity == __other.end() || !bool(*__ity == *__itx)) 1867 __node_base* __prev_n = __other._M_buckets[__ybkt];
1868 if (!__prev_n)
1949 return false; 1869 return false;
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 }
1950 } 1881 }
1882
1951 return true; 1883 return true;
1952 } 1884 }
1953 1885
1954 /// Specialization. 1886 /// unordered_multiset and unordered_multimap specializations.
1955 template<typename _Key, typename _Value, typename _Alloc, 1887 template<typename _Key, typename _Value, typename _Alloc,
1956 typename _ExtractKey, typename _Equal, 1888 typename _ExtractKey, typename _Equal,
1957 typename _H1, typename _H2, typename _Hash, 1889 typename _H1, typename _H2, typename _Hash,
1958 typename _RehashPolicy, typename _Traits> 1890 typename _RehashPolicy, typename _Traits>
1959 struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1891 struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1960 _H1, _H2, _Hash, _RehashPolicy, _Traits, false> 1892 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
1961 : public _Equality_base
1962 { 1893 {
1963 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1894 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1964 _H1, _H2, _Hash, _RehashPolicy, _Traits>; 1895 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1965 1896
1966 bool 1897 bool
1974 bool 1905 bool
1975 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1906 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1976 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>:: 1907 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>::
1977 _M_equal(const __hashtable& __other) const 1908 _M_equal(const __hashtable& __other) const
1978 { 1909 {
1910 using __node_base = typename __hashtable::__node_base;
1911 using __node_type = typename __hashtable::__node_type;
1979 const __hashtable* __this = static_cast<const __hashtable*>(this); 1912 const __hashtable* __this = static_cast<const __hashtable*>(this);
1980
1981 if (__this->size() != __other.size()) 1913 if (__this->size() != __other.size())
1982 return false; 1914 return false;
1983 1915
1984 for (auto __itx = __this->begin(); __itx != __this->end();) 1916 for (auto __itx = __this->begin(); __itx != __this->end();)
1985 { 1917 {
1986 const auto __xrange = __this->equal_range(_ExtractKey()(*__itx)); 1918 std::size_t __x_count = 1;
1987 const auto __yrange = __other.equal_range(_ExtractKey()(*__itx)); 1919 auto __itx_end = __itx;
1988 1920 for (++__itx_end; __itx_end != __this->end()
1989 if (std::distance(__xrange.first, __xrange.second) 1921 && __this->key_eq()(_ExtractKey()(*__itx),
1990 != std::distance(__yrange.first, __yrange.second)) 1922 _ExtractKey()(*__itx_end));
1923 ++__itx_end)
1924 ++__x_count;
1925
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)
1991 return false; 1929 return false;
1992 1930
1993 if (!_S_is_permutation(__xrange.first, __xrange.second, 1931 __node_type* __y_n = static_cast<__node_type*>(__y_prev_n->_M_nxt);
1994 __yrange.first)) 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)
1995 return false; 1949 return false;
1996 1950
1997 __itx = __xrange.second; 1951 if (!std::is_permutation(__itx, __itx_end, __ity))
1952 return false;
1953
1954 __itx = __itx_end;
1998 } 1955 }
1999 return true; 1956 return true;
2000 } 1957 }
2001 1958
2002 /** 1959 /**
2003 * This type deals with all allocation and keeps an allocator instance through 1960 * This type deals with all allocation and keeps an allocator instance
2004 * inheritance to benefit from EBO when possible. 1961 * through inheritance to benefit from EBO when possible.
2005 */ 1962 */
2006 template<typename _NodeAlloc> 1963 template<typename _NodeAlloc>
2007 struct _Hashtable_alloc : private _Hashtable_ebo_helper<0, _NodeAlloc> 1964 struct _Hashtable_alloc : private _Hashtable_ebo_helper<0, _NodeAlloc>
2008 { 1965 {
2009 private: 1966 private:
2027 _Hashtable_alloc(const _Hashtable_alloc&) = default; 1984 _Hashtable_alloc(const _Hashtable_alloc&) = default;
2028 _Hashtable_alloc(_Hashtable_alloc&&) = default; 1985 _Hashtable_alloc(_Hashtable_alloc&&) = default;
2029 1986
2030 template<typename _Alloc> 1987 template<typename _Alloc>
2031 _Hashtable_alloc(_Alloc&& __a) 1988 _Hashtable_alloc(_Alloc&& __a)
2032 : __ebo_node_alloc(std::forward<_Alloc>(__a)) 1989 : __ebo_node_alloc(std::forward<_Alloc>(__a))
2033 { } 1990 { }
2034 1991
2035 __node_alloc_type& 1992 __node_alloc_type&
2036 _M_node_allocator() 1993 _M_node_allocator()
2037 { return __ebo_node_alloc::_S_get(*this); } 1994 { return __ebo_node_alloc::_M_get(); }
2038 1995
2039 const __node_alloc_type& 1996 const __node_alloc_type&
2040 _M_node_allocator() const 1997 _M_node_allocator() const
2041 { return __ebo_node_alloc::_S_cget(*this); } 1998 { return __ebo_node_alloc::_M_cget(); }
2042 1999
2000 // Allocate a node and construct an element within it.
2043 template<typename... _Args> 2001 template<typename... _Args>
2044 __node_type* 2002 __node_type*
2045 _M_allocate_node(_Args&&... __args); 2003 _M_allocate_node(_Args&&... __args);
2046 2004
2005 // Destroy the element within a node and deallocate the node.
2047 void 2006 void
2048 _M_deallocate_node(__node_type* __n); 2007 _M_deallocate_node(__node_type* __n);
2049 2008
2050 // Deallocate the linked list of nodes pointed to by __n 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.
2051 void 2015 void
2052 _M_deallocate_nodes(__node_type* __n); 2016 _M_deallocate_nodes(__node_type* __n);
2053 2017
2054 __bucket_type* 2018 __bucket_type*
2055 _M_allocate_buckets(std::size_t __n); 2019 _M_allocate_buckets(std::size_t __bkt_count);
2056 2020
2057 void 2021 void
2058 _M_deallocate_buckets(__bucket_type*, std::size_t __n); 2022 _M_deallocate_buckets(__bucket_type*, std::size_t __bkt_count);
2059 }; 2023 };
2060 2024
2061 // Definitions of class template _Hashtable_alloc's out-of-line member 2025 // Definitions of class template _Hashtable_alloc's out-of-line member
2062 // functions. 2026 // functions.
2063 template<typename _NodeAlloc> 2027 template<typename _NodeAlloc>
2064 template<typename... _Args> 2028 template<typename... _Args>
2065 typename _Hashtable_alloc<_NodeAlloc>::__node_type* 2029 auto
2066 _Hashtable_alloc<_NodeAlloc>::_M_allocate_node(_Args&&... __args) 2030 _Hashtable_alloc<_NodeAlloc>::_M_allocate_node(_Args&&... __args)
2031 -> __node_type*
2067 { 2032 {
2068 auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1); 2033 auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1);
2069 __node_type* __n = std::__to_address(__nptr); 2034 __node_type* __n = std::__to_address(__nptr);
2070 __try 2035 __try
2071 { 2036 {
2084 2049
2085 template<typename _NodeAlloc> 2050 template<typename _NodeAlloc>
2086 void 2051 void
2087 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node(__node_type* __n) 2052 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node(__node_type* __n)
2088 { 2053 {
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 {
2089 typedef typename __node_alloc_traits::pointer _Ptr; 2062 typedef typename __node_alloc_traits::pointer _Ptr;
2090 auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__n); 2063 auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__n);
2091 __node_alloc_traits::destroy(_M_node_allocator(), __n->_M_valptr());
2092 __n->~__node_type(); 2064 __n->~__node_type();
2093 __node_alloc_traits::deallocate(_M_node_allocator(), __ptr, 1); 2065 __node_alloc_traits::deallocate(_M_node_allocator(), __ptr, 1);
2094 } 2066 }
2095 2067
2096 template<typename _NodeAlloc> 2068 template<typename _NodeAlloc>
2105 } 2077 }
2106 } 2078 }
2107 2079
2108 template<typename _NodeAlloc> 2080 template<typename _NodeAlloc>
2109 typename _Hashtable_alloc<_NodeAlloc>::__bucket_type* 2081 typename _Hashtable_alloc<_NodeAlloc>::__bucket_type*
2110 _Hashtable_alloc<_NodeAlloc>::_M_allocate_buckets(std::size_t __n) 2082 _Hashtable_alloc<_NodeAlloc>::_M_allocate_buckets(std::size_t __bkt_count)
2111 { 2083 {
2112 __bucket_alloc_type __alloc(_M_node_allocator()); 2084 __bucket_alloc_type __alloc(_M_node_allocator());
2113 2085
2114 auto __ptr = __bucket_alloc_traits::allocate(__alloc, __n); 2086 auto __ptr = __bucket_alloc_traits::allocate(__alloc, __bkt_count);
2115 __bucket_type* __p = std::__to_address(__ptr); 2087 __bucket_type* __p = std::__to_address(__ptr);
2116 __builtin_memset(__p, 0, __n * sizeof(__bucket_type)); 2088 __builtin_memset(__p, 0, __bkt_count * sizeof(__bucket_type));
2117 return __p; 2089 return __p;
2118 } 2090 }
2119 2091
2120 template<typename _NodeAlloc> 2092 template<typename _NodeAlloc>
2121 void 2093 void
2122 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_buckets(__bucket_type* __bkts, 2094 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_buckets(__bucket_type* __bkts,
2123 std::size_t __n) 2095 std::size_t __bkt_count)
2124 { 2096 {
2125 typedef typename __bucket_alloc_traits::pointer _Ptr; 2097 typedef typename __bucket_alloc_traits::pointer _Ptr;
2126 auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__bkts); 2098 auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__bkts);
2127 __bucket_alloc_type __alloc(_M_node_allocator()); 2099 __bucket_alloc_type __alloc(_M_node_allocator());
2128 __bucket_alloc_traits::deallocate(__alloc, __ptr, __n); 2100 __bucket_alloc_traits::deallocate(__alloc, __ptr, __bkt_count);
2129 } 2101 }
2130 2102
2131 //@} hashtable-detail 2103 //@} hashtable-detail
2132 } // namespace __detail 2104 } // namespace __detail
2133 _GLIBCXX_END_NAMESPACE_VERSION 2105 _GLIBCXX_END_NAMESPACE_VERSION