diff options
| author | François Dumont <fdumont@gcc.gnu.org> | 2020-01-20 08:21:10 +0100 |
|---|---|---|
| committer | François Dumont <fdumont@gcc.gnu.org> | 2020-08-26 07:58:46 +0200 |
| commit | 4797a61cc5024fc9adf5918e9bb2b78988f9e4d4 (patch) | |
| tree | fa2619258ebc5abd290e97f6683aecfe5a58d2ac | |
| parent | 55290635d10ea3d18b0a45aa2e6f59405b8c1f54 (diff) | |
libstdc++: Rename _Hashtable _H1, _H2 and _Hash template parameters
Limit our _Hashtable implementation to ranged hash. _H1 is now rename
to _Hash matching the _Hash functor used for unordered containers. _H2
is now renamed to _RangeHash. Former _Hash simply becomes _Unused. Remove
_ExtractKey storage.
libstdc++-v3/ChangeLog:
* include/bits/hashtable_policy.h (_Hashtable<>): Rename _H1 into _Hash
_H2 into _RangeHash and _Hash into _Unused.
(_Hastable_base<>): Likewise.
(_Map_base<>): Likewise.
(_Insert_base<>): Likewise.
(_Insert<>): Likewise.
(_Rehash_base<>): Likewise.
(_Local_iterator_base<>): Likewise.
(_Hash_code_base<>): Likewise.
(_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false>):
Remove.
(_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>):
Remove.
(_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHas, _Unused,
bool>): Remove _Hashtable_ebo_helper<2, _RangeHash> base type..
(_Hash_code_base<>::_M_bucket_index(const _Key&, __hash_code, size_t)):
Replace by...
(_Hash_code_base<>::_M_bucket_index(__hash_code, size_t)): ...this.
(_Local_iterator<>): Remove _H1 and _H2 template parameters.
(_Local_const_iterator<>): Likewise.
(_Equality<>): Likewise.
(_Map_base<>::operator[](const key_type&): Adapt.
(_Map_base<>::operator[](key_type&&): Adapt.
(_Identity::operator()): Add noexcept.
(_Select1st::operator()): Likewise.
(_Hash_code_base<>): Remove _Hashtable_ebo_helper<0, _ExtractKey> base
type.
(_Hash_code_base::_M_extract): Remove.
* include/bits/hashtable.h (_Hashtable<>): Remove _H1 and _H2 template
parameters. Remove _ExtractKey from constructors.
(_Hashtable<>::_M_insert_unique_node(const key_type&, size_t,
__hash_code, __node_type*, size_t)): Replace by...
(_Hashtable<>::_M_insert_unique_node(size_t, __hash_code,
__node_type*, size_t)): ...this.
(_Hashtable<>::_M_insert_muti_node(__node_type*, const key_type&,
__hash_code, __node_type*)): Replace by...
(_Hashtable<>::_M_insert_multi_node(__node_type*, __hash_code,
__node_type*)): ...this.
(_Hashtable<>::__key_extract): Remove.
* include/bits/node_handle.h: Adapt.
| -rw-r--r-- | libstdc++-v3/include/bits/hashtable.h | 692 | ||||
| -rw-r--r-- | libstdc++-v3/include/bits/hashtable_policy.h | 468 | ||||
| -rw-r--r-- | libstdc++-v3/include/bits/node_handle.h | 4 |
3 files changed, 510 insertions, 654 deletions
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 7b772a475e3..07a4abe5c33 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -69,21 +69,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * and returns a bool-like value that is true if the two objects * are considered equal. * - * @tparam _H1 The hash function. A unary function object with + * @tparam _Hash The hash function. A unary function object with * argument type _Key and result type size_t. Return values should * be distributed over the entire range [0, numeric_limits<size_t>:::max()]. * - * @tparam _H2 The range-hashing function (in the terminology of + * @tparam _RangeHash The range-hashing function (in the terminology of * Tavori and Dreizin). A binary function object whose argument * types and result type are all size_t. Given arguments r and N, * the return value is in the range [0, N). * - * @tparam _Hash The ranged hash function (Tavori and Dreizin). A - * binary function whose argument types are _Key and size_t and - * whose result type is size_t. Given arguments k and N, the - * return value is in the range [0, N). Default: hash(k, N) = - * h2(h1(k), N). If _Hash is anything other than the default, _H1 - * and _H2 are ignored. + * @tparam _Unused Not used. * * @tparam _RehashPolicy Policy class with three members, all of * which govern the bucket count. _M_next_bkt(n) returns a bucket @@ -91,9 +86,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * bucket count appropriate for an element count of n. * _M_need_rehash(n_bkt, n_elt, n_ins) determines whether, if the * current bucket count is n_bkt and the current element count is - * n_elt, we need to increase the bucket count. If so, returns - * make_pair(true, n), where n is the new bucket count. If not, - * returns make_pair(false, <anything>) + * n_elt, we need to increase the bucket count for n_ins insertions. + * If so, returns make_pair(true, n), where n is the new bucket count. If + * not, returns make_pair(false, <anything>) * * @tparam _Traits Compile-time class with three boolean * std::integral_constant members: __cache_hash_code, __constant_iterators, @@ -168,19 +163,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION */ template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> class _Hashtable : public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, - _H1, _H2, _Hash, _Traits>, + _Hash, _RangeHash, _Unused, _Traits>, public __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>, + _Hash, _RangeHash, _Unused, + _RehashPolicy, _Traits>, public __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>, + _Hash, _RangeHash, _Unused, + _RehashPolicy, _Traits>, public __detail::_Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>, + _Hash, _RangeHash, _Unused, + _RehashPolicy, _Traits>, public __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>, + _Hash, _RangeHash, _Unused, + _RehashPolicy, _Traits>, private __detail::_Hashtable_alloc< __alloc_rebind<_Alloc, __detail::_Hash_node<_Value, @@ -227,30 +226,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION using __constant_iterators = typename __traits_type::__constant_iterators; using __unique_keys = typename __traits_type::__unique_keys; - using __key_extract = typename std::conditional< - __constant_iterators::value, - __detail::_Identity, - __detail::_Select1st>::type; - using __hashtable_base = __detail:: - _Hashtable_base<_Key, _Value, _ExtractKey, - _Equal, _H1, _H2, _Hash, _Traits>; + _Hashtable_base<_Key, _Value, _ExtractKey, + _Equal, _Hash, _RangeHash, _Unused, _Traits>; using __hash_code_base = typename __hashtable_base::__hash_code_base; using __hash_code = typename __hashtable_base::__hash_code; using __ireturn_type = typename __hashtable_base::__ireturn_type; using __map_base = __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, - _Equal, _H1, _H2, _Hash, + _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>; using __rehash_base = __detail::_Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>; using __eq_base = __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, - _Equal, _H1, _H2, _Hash, + _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>; using __reuse_or_alloc_node_gen_t = @@ -289,13 +283,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __fwd_value_for(value_type& __val) noexcept { return std::move(__val); } - // Metaprogramming for picking apart hash caching. - template<typename _Cond> - using __if_hash_cached = __or_<__not_<__hash_cached>, _Cond>; - - template<typename _Cond> - using __if_hash_not_cached = __or_<__hash_cached, _Cond>; - // Compile-time diagnostics. // _Hash_code_base has everything protected, so use this derived type to @@ -311,35 +298,45 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION "Cache the hash code or qualify your functors involved" " in hash code and bucket index computation with noexcept"); - // When hash codes are cached local iterator inherits from H2 functor - // which must then be default constructible. - static_assert(__if_hash_cached<is_default_constructible<_H2>>::value, + // To get bucket index we need _RangeHash not to throw. + static_assert(is_nothrow_default_constructible<_RangeHash>::value, "Functor used to map hash code to bucket index" - " must be default constructible"); + " must be nothrow default constructible"); + static_assert(noexcept( + std::declval<const _RangeHash&>()((std::size_t)0, (std::size_t)0)), + "Functor used to map hash code to bucket index must be" + " noexcept"); + + // To compute bucket index we also need _ExtratKey not to throw. + static_assert(is_nothrow_default_constructible<_ExtractKey>::value, + "_ExtractKey must be nothrow default constructible"); + static_assert(noexcept( + std::declval<const _ExtractKey&>()(std::declval<_Value>())), + "_ExtractKey functor must be noexcept invocable"); template<typename _Keya, typename _Valuea, typename _Alloca, typename _ExtractKeya, typename _Equala, - typename _H1a, typename _H2a, typename _Hasha, + typename _Hasha, typename _RangeHasha, typename _Unuseda, typename _RehashPolicya, typename _Traitsa, bool _Unique_keysa> friend struct __detail::_Map_base; template<typename _Keya, typename _Valuea, typename _Alloca, typename _ExtractKeya, typename _Equala, - typename _H1a, typename _H2a, typename _Hasha, + typename _Hasha, typename _RangeHasha, typename _Unuseda, typename _RehashPolicya, typename _Traitsa> friend struct __detail::_Insert_base; template<typename _Keya, typename _Valuea, typename _Alloca, typename _ExtractKeya, typename _Equala, - typename _H1a, typename _H2a, typename _Hasha, + typename _Hasha, typename _RangeHasha, typename _Unuseda, typename _RehashPolicya, typename _Traitsa, bool _Constant_iteratorsa> friend struct __detail::_Insert; template<typename _Keya, typename _Valuea, typename _Alloca, typename _ExtractKeya, typename _Equala, - typename _H1a, typename _H2a, typename _Hasha, + typename _Hasha, typename _RangeHasha, typename _Unuseda, typename _RehashPolicya, typename _Traitsa, bool _Unique_keysa> friend struct __detail::_Equality; @@ -453,16 +450,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION void _M_reset() noexcept; - _Hashtable(const _H1& __h1, const _H2& __h2, const _Hash& __h, - const _Equal& __eq, const _ExtractKey& __exk, + _Hashtable(const _Hash& __h, const _Equal& __eq, const allocator_type& __a) - : __hashtable_base(__exk, __h1, __h2, __h, __eq), + : __hashtable_base(__h, __eq), __hashtable_alloc(__node_alloc_type(__a)) { } _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a, true_type /* alloc always equal */) - noexcept(std::is_nothrow_copy_constructible<_H1>::value && + noexcept(std::is_nothrow_copy_constructible<_Hash>::value && std::is_nothrow_copy_constructible<_Equal>::value); _Hashtable(_Hashtable&&, __node_alloc_type&&, @@ -471,29 +467,30 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _InputIterator> _Hashtable(_InputIterator __first, _InputIterator __last, size_type __bkt_count_hint, - const _H1&, const _H2&, const _Hash&, - const _Equal&, const _ExtractKey&, - const allocator_type&, + const _Hash&, const _Equal&, const allocator_type&, true_type __uks); template<typename _InputIterator> _Hashtable(_InputIterator __first, _InputIterator __last, size_type __bkt_count_hint, - const _H1&, const _H2&, const _Hash&, - const _Equal&, const _ExtractKey&, - const allocator_type&, + const _Hash&, const _Equal&, const allocator_type&, false_type __uks); public: // Constructor, destructor, assignment, swap _Hashtable() = default; - _Hashtable(size_type __bkt_count_hint, - const _H1&, const _H2&, const _Hash&, - const _Equal&, const _ExtractKey&, - const allocator_type&); _Hashtable(const _Hashtable&); + _Hashtable(const _Hashtable&, const allocator_type&); + + explicit + _Hashtable(size_type __bkt_count_hint, + const _Hash& __hf = _Hash(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()); + + // Use delegating constructors. _Hashtable(_Hashtable&& __ht) noexcept( noexcept( _Hashtable(std::declval<_Hashtable>(), @@ -503,8 +500,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION true_type{}) { } - _Hashtable(const _Hashtable&, const allocator_type&); - _Hashtable(_Hashtable&& __ht, const allocator_type& __a) noexcept( noexcept( _Hashtable(std::declval<_Hashtable>(), @@ -514,49 +509,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename __node_alloc_traits::is_always_equal{}) { } - // Use delegating constructors. - template<typename _InputIterator> - _Hashtable(_InputIterator __first, _InputIterator __last, - size_type __bkt_count_hint, - const _H1& __h1, const _H2& __h2, const _Hash& __h, - const _Equal& __eq, const _ExtractKey& __exk, - const allocator_type& __a) - : _Hashtable(__first, __last, __bkt_count_hint, - __h1, __h2, __h, __eq, __exk, __a, __unique_keys{}) - { } - explicit _Hashtable(const allocator_type& __a) : __hashtable_alloc(__node_alloc_type(__a)) { } - explicit - _Hashtable(size_type __bkt_count_hint, - const _H1& __hf = _H1(), - const key_equal& __eql = key_equal(), - const allocator_type& __a = allocator_type()) - : _Hashtable(__bkt_count_hint, __hf, _H2(), _Hash(), __eql, - __key_extract(), __a) - { } - template<typename _InputIterator> _Hashtable(_InputIterator __f, _InputIterator __l, size_type __bkt_count_hint = 0, - const _H1& __hf = _H1(), + const _Hash& __hf = _Hash(), const key_equal& __eql = key_equal(), const allocator_type& __a = allocator_type()) - : _Hashtable(__f, __l, __bkt_count_hint, __hf, _H2(), _Hash(), __eql, - __key_extract(), __a) + : _Hashtable(__f, __l, __bkt_count_hint, __hf, __eql, __a, + __unique_keys{}) { } _Hashtable(initializer_list<value_type> __l, size_type __bkt_count_hint = 0, - const _H1& __hf = _H1(), + const _Hash& __hf = _Hash(), const key_equal& __eql = key_equal(), const allocator_type& __a = allocator_type()) : _Hashtable(__l.begin(), __l.end(), __bkt_count_hint, - __hf, _H2(), _Hash(), __eql, - __key_extract(), __a) + __hf, __eql, __a, __unique_keys{}) { } _Hashtable& @@ -565,10 +539,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Hashtable& operator=(_Hashtable&& __ht) noexcept(__node_alloc_traits::_S_nothrow_move() - && is_nothrow_move_assignable<_H1>::value + && is_nothrow_move_assignable<_Hash>::value && is_nothrow_move_assignable<_Equal>::value) { - constexpr bool __move_storage = + constexpr bool __move_storage = __node_alloc_traits::_S_propagate_on_move_assign() || __node_alloc_traits::_S_always_equal(); _M_move_assign(std::move(__ht), __bool_constant<__move_storage>()); @@ -597,8 +571,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION void swap(_Hashtable&) - noexcept(__and_<__is_nothrow_swappable<_H1>, - __is_nothrow_swappable<_Equal>>::value); + noexcept(__and_<__is_nothrow_swappable<_Hash>, + __is_nothrow_swappable<_Equal>>::value); // Basic container operations iterator @@ -663,7 +637,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION size_type bucket(const key_type& __k) const - { return _M_bucket_index(__k, this->_M_hash_code(__k)); } + { return _M_bucket_index(this->_M_hash_code(__k)); } local_iterator begin(size_type __bkt) @@ -741,8 +715,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); } size_type - _M_bucket_index(const key_type& __k, __hash_code __c) const - { return __hash_code_base::_M_bucket_index(__k, __c, _M_bucket_count); } + _M_bucket_index(__hash_code __c) const + { return __hash_code_base::_M_bucket_index(__c, _M_bucket_count); } // Find and insert helper functions and types // Find the node before the one matching the criteria. @@ -772,28 +746,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __node_base* _M_get_previous_node(size_type __bkt, __node_base* __n); - // Insert node __n with key __k and hash code __code, in bucket __bkt - // if no rehash (assumes no element with same key already present). + // Insert node __n with hash code __code, in bucket __bkt if no + // rehash (assumes no element with same key already present). // Takes ownership of __n if insertion succeeds, throws otherwise. iterator - _M_insert_unique_node(const key_type& __k, size_type __bkt, - __hash_code __code, __node_type* __n, - size_type __n_elt = 1); + _M_insert_unique_node(size_type __bkt, __hash_code, + __node_type* __n, size_type __n_elt = 1); // Insert node __n with key __k and hash code __code. // Takes ownership of __n if insertion succeeds, throws otherwise. iterator - _M_insert_multi_node(__node_type* __hint, const key_type& __k, + _M_insert_multi_node(__node_type* __hint, __hash_code __code, __node_type* __n); template<typename... _Args> std::pair<iterator, bool> - _M_emplace(true_type, _Args&&... __args); + _M_emplace(true_type __uks, _Args&&... __args); template<typename... _Args> iterator - _M_emplace(false_type __uk, _Args&&... __args) - { return _M_emplace(cend(), __uk, std::forward<_Args>(__args)...); } + _M_emplace(false_type __uks, _Args&&... __args) + { return _M_emplace(cend(), __uks, std::forward<_Args>(__args)...); } // Emplace with hint, useless when keys are unique. template<typename... _Args> @@ -835,10 +808,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION const _NodeGenerator&, false_type __uks); size_type - _M_erase(true_type, const key_type&); + _M_erase(true_type __uks, const key_type&); size_type - _M_erase(false_type, const key_type&); + _M_erase(false_type __uks, const key_type&); iterator _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n); @@ -848,13 +821,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename... _Args> __ireturn_type emplace(_Args&&... __args) - { return _M_emplace(__unique_keys(), std::forward<_Args>(__args)...); } + { return _M_emplace(__unique_keys{}, std::forward<_Args>(__args)...); } template<typename... _Args> iterator emplace_hint(const_iterator __hint, _Args&&... __args) { - return _M_emplace(__hint, __unique_keys(), + return _M_emplace(__hint, __unique_keys{}, std::forward<_Args>(__args)...); } @@ -871,7 +844,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION size_type erase(const key_type& __k) - { return _M_erase(__unique_keys(), __k); } + { return _M_erase(__unique_keys{}, __k); } iterator erase(const_iterator, const_iterator); @@ -900,7 +873,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION const key_type& __k = __nh._M_key(); __hash_code __code = this->_M_hash_code(__k); - size_type __bkt = _M_bucket_index(__k, __code); + size_type __bkt = _M_bucket_index(__code); if (__node_type* __n = _M_find_node(__bkt, __k, __code)) { __ret.node = std::move(__nh); @@ -910,7 +883,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION else { __ret.position - = _M_insert_unique_node(__k, __bkt, __code, __nh._M_ptr); + = _M_insert_unique_node(__bkt, __code, __nh._M_ptr); __nh._M_ptr = nullptr; __ret.inserted = true; } @@ -930,7 +903,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION const key_type& __k = __nh._M_key(); auto __code = this->_M_hash_code(__k); auto __ret - = _M_insert_multi_node(__hint._M_cur, __k, __code, __nh._M_ptr); + = _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr); __nh._M_ptr = nullptr; return __ret; } @@ -972,7 +945,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { node_type __nh; __hash_code __code = this->_M_hash_code(__k); - std::size_t __bkt = _M_bucket_index(__k, __code); + std::size_t __bkt = _M_bucket_index(__code); if (__node_base* __prev_node = _M_find_before_node(__bkt, __k, __code)) __nh = _M_extract_node(__bkt, __prev_node); return __nh; @@ -991,14 +964,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION for (auto __i = __src.begin(), __end = __src.end(); __i != __end;) { auto __pos = __i++; - const key_type& __k = this->_M_extract()(*__pos); + const key_type& __k = _ExtractKey{}(*__pos); __hash_code __code = this->_M_hash_code(__k); - size_type __bkt = _M_bucket_index(__k, __code); + size_type __bkt = _M_bucket_index(__code); if (_M_find_node(__bkt, __k, __code) == nullptr) { auto __nh = __src.extract(__pos); - _M_insert_unique_node(__k, __bkt, __code, __nh._M_ptr, - __n_elt); + _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt); __nh._M_ptr = nullptr; __n_elt = 1; } @@ -1024,10 +996,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION private: // Helper rehash method used when keys are unique. - void _M_rehash_aux(size_type __bkt_count, true_type); + void _M_rehash_aux(size_type __bkt_count, true_type __uks); // Helper rehash method used when keys can be non-unique. - void _M_rehash_aux(size_type __bkt_count, false_type); + void _M_rehash_aux(size_type __bkt_count, false_type __uks); // Unconditionally change size of bucket array to n, restore // hash policy state to __state on exception. @@ -1036,13 +1008,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Definitions of class template _Hashtable's out-of-line member functions. - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_bucket_begin(size_type __bkt) const -> __node_type* { @@ -1050,17 +1022,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return __n ? static_cast<__node_type*>(__n->_M_nxt) : nullptr; } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _Hashtable(size_type __bkt_count_hint, - const _H1& __h1, const _H2& __h2, const _Hash& __h, - const _Equal& __eq, const _ExtractKey& __exk, - const allocator_type& __a) - : _Hashtable(__h1, __h2, __h, __eq, __exk, __a) + const _Hash& __h, const _Equal& __eq, const allocator_type& __a) + : _Hashtable(__h, __eq, __a) { auto __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count_hint); if (__bkt_count > _M_bucket_count) @@ -1070,37 +1040,35 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> template<typename _InputIterator> _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _Hashtable(_InputIterator __f, _InputIterator __l, size_type __bkt_count_hint, - const _H1& __h1, const _H2& __h2, const _Hash& __h, - const _Equal& __eq, const _ExtractKey& __exk, + const _Hash& __h, const _Equal& __eq, const allocator_type& __a, true_type /* __uks */) - : _Hashtable(__bkt_count_hint, __h1, __h2, __h, __eq, __exk, __a) + : _Hashtable(__bkt_count_hint, __h, __eq, __a) { for (; __f != __l; ++__f) this->insert(*__f); } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> template<typename _InputIterator> _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _Hashtable(_InputIterator __f, _InputIterator __l, size_type __bkt_count_hint, - const _H1& __h1, const _H2& __h2, const _Hash& __h, - const _Equal& __eq, const _ExtractKey& __exk, + const _Hash& __h, const _Equal& __eq, const allocator_type& __a, false_type /* __uks */) - : _Hashtable(__h1, __h2, __h, __eq, __exk, __a) + : _Hashtable(__h, __eq, __a) { auto __nb_elems = __detail::__distance_fw(__f, __l); auto __bkt_count = @@ -1118,13 +1086,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION this->insert(*__f); } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: operator=(const _Hashtable& __ht) -> _Hashtable& { @@ -1170,14 +1138,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return *this; } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> template<typename _Ht> void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_assign_elements(_Ht&& __ht) { __bucket_type* __former_buckets = nullptr; @@ -1221,14 +1189,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> template<typename _Ht, typename _NodeGenerator> void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_assign(_Ht&& __ht, const _NodeGenerator& __node_gen) { __bucket_type* __buckets = nullptr; @@ -1270,13 +1238,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_reset() noexcept { _M_rehash_policy._M_reset(); @@ -1287,13 +1255,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_element_count = 0; } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_move_assign(_Hashtable&& __ht, true_type) { if (__builtin_expect(std::__addressof(__ht) == this, false)) @@ -1321,17 +1289,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __ht._M_reset(); } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_move_assign(_Hashtable&& __ht, false_type) { if (__ht._M_node_allocator() == this->_M_node_allocator()) - _M_move_assign(std::move(__ht), true_type()); + _M_move_assign(std::move(__ht), true_type{}); else { // Can't move memory, move elements then. @@ -1340,12 +1308,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _Hashtable(const _Hashtable& __ht) : __hashtable_base(__ht), __map_base(__ht), @@ -1361,15 +1329,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_assign(__ht, __alloc_node_gen); } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a, true_type /* alloc always equal */) - noexcept(std::is_nothrow_copy_constructible<_H1>::value && + noexcept(std::is_nothrow_copy_constructible<_Hash>::value && std::is_nothrow_copy_constructible<_Equal>::value) : __hashtable_base(__ht), __map_base(__ht), @@ -1394,12 +1362,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __ht._M_reset(); } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _Hashtable(const _Hashtable& __ht, const allocator_type& __a) : __hashtable_base(__ht), __map_base(__ht), @@ -1414,12 +1382,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_assign(__ht, __alloc_node_gen); } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a, false_type /* alloc always equal */) : __hashtable_base(__ht), @@ -1459,28 +1427,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: ~_Hashtable() noexcept { clear(); _M_deallocate_buckets(); } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: swap(_Hashtable& __x) - noexcept(__and_<__is_nothrow_swappable<_H1>, - __is_nothrow_swappable<_Equal>>::value) + noexcept(__and_<__is_nothrow_swappable<_Hash>, + __is_nothrow_swappable<_Equal>>::value) { // The only base class with member variables is hash_code_base. // We define _Hash_code_base::_M_swap because different @@ -1518,43 +1486,43 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __x._M_update_bbegin(); } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: find(const key_type& __k) -> iterator { __hash_code __code = this->_M_hash_code(__k); - std::size_t __bkt = _M_bucket_index(__k, __code); + std::size_t __bkt = _M_bucket_index(__code); return iterator(_M_find_node(__bkt, __k, __code)); } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: find(const key_type& __k) const -> const_iterator { __hash_code __code = this->_M_hash_code(__k); - std::size_t __bkt = _M_bucket_index(__k, __code); + std::size_t __bkt = _M_bucket_index(__code); return const_iterator(_M_find_node(__bkt, __k, __code)); } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: count(const key_type& __k) const -> size_type { @@ -1577,13 +1545,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return __result; } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: equal_range(const key_type& __k) -> pair<iterator, iterator> { @@ -1604,13 +1572,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return { __beg, __ite }; } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: equal_range(const key_type& __k) const -> pair<const_iterator, const_iterator> { @@ -1633,13 +1601,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Find the node before the one whose key compares equal to k in the bucket // bkt. Return nullptr if no node is found. - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_find_before_node(size_type __bkt, const key_type& __k, __hash_code __code) const -> __node_base* @@ -1662,13 +1630,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return nullptr; } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_insert_bucket_begin(size_type __bkt, __node_type* __node) { if (_M_buckets[__bkt]) @@ -1695,13 +1663,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_remove_bucket_begin(size_type __bkt, __node_type* __next, size_type __next_bkt) { @@ -1719,13 +1687,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_get_previous_node(size_type __bkt, __node_base* __n) -> __node_base* { @@ -1735,64 +1703,64 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return __prev_n; } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> template<typename... _Args> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: - _M_emplace(true_type, _Args&&... __args) + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_emplace(true_type /* __uks */, _Args&&... __args) -> pair<iterator, bool> { // First build the node to get access to the hash code _Scoped_node __node { this, std::forward<_Args>(__args)... }; - const key_type& __k = this->_M_extract()(__node._M_node->_M_v()); + const key_type& __k = _ExtractKey{}(__node._M_node->_M_v()); __hash_code __code = this->_M_hash_code(__k); - size_type __bkt = _M_bucket_index(__k, __code); + size_type __bkt = _M_bucket_index(__code); if (__node_type* __p = _M_find_node(__bkt, __k, __code)) // There is already an equivalent node, no insertion return std::make_pair(iterator(__p), false); // Insert the node - auto __pos = _M_insert_unique_node(__k, __bkt, __code, __node._M_node); + auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node); __node._M_node = nullptr; return { __pos, true }; } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> template<typename... _Args> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: - _M_emplace(const_iterator __hint, false_type, _Args&&... __args) + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_emplace(const_iterator __hint, false_type /* __uks */, + _Args&&... __args) -> iterator { // First build the node to get its hash code. _Scoped_node __node { this, std::forward<_Args>(__args)... }; - const key_type& __k = this->_M_extract()(__node._M_node->_M_v()); + const key_type& __k = _ExtractKey{}(__node._M_node->_M_v()); __hash_code __code = this->_M_hash_code(__k); auto __pos - = _M_insert_multi_node(__hint._M_cur, __k, __code, __node._M_node); + = _M_insert_multi_node(__hint._M_cur, __code, __node._M_node); __node._M_node = nullptr; return __pos; } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: - _M_insert_unique_node(const key_type& __k, size_type __bkt, - __hash_code __code, __node_type* __node, - size_type __n_elt) + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_insert_unique_node(size_type __bkt, __hash_code __code, + __node_type* __node, size_type __n_elt) -> iterator { const __rehash_state& __saved_state = _M_rehash_policy._M_state(); @@ -1803,7 +1771,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__do_rehash.first) { _M_rehash(__do_rehash.second, __saved_state); - __bkt = _M_bucket_index(__k, __code); + __bkt = _M_bucket_index(__code); } this->_M_store_code(__node, __code); @@ -1814,14 +1782,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return iterator(__node); } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: - _M_insert_multi_node(__node_type* __hint, const key_type& __k, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_insert_multi_node(__node_type* __hint, __hash_code __code, __node_type* __node) -> iterator { @@ -1833,7 +1801,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_rehash(__do_rehash.second, __saved_state); this->_M_store_code(__node, __code); - size_type __bkt = _M_bucket_index(__k, __code); + const key_type& __k = _ExtractKey{}(__node->_M_v()); + size_type __bkt = _M_bucket_index(__code); // Find the node before an equivalent one or use hint if it exists and // if it is equivalent. @@ -1868,41 +1837,41 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } // Insert v if no element with its key is already present. - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> template<typename _Arg, typename _NodeGenerator> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen, true_type /* __uks */) -> pair<iterator, bool> { - const key_type& __k = this->_M_extract()(__v); + const key_type& __k = _ExtractKey{}(__v); __hash_code __code = this->_M_hash_code(__k); - size_type __bkt = _M_bucket_index(__k, __code); + size_type __bkt = _M_bucket_index(__code); if (__node_type* __node = _M_find_node(__bkt, __k, __code)) return { iterator(__node), false }; _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this }; auto __pos - = _M_insert_unique_node(__k, __bkt, __code, __node._M_node); + = _M_insert_unique_node(__bkt, __code, __node._M_node); __node._M_node = nullptr; return { __pos, true }; } // Insert v unconditionally. - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> template<typename _Arg, typename _NodeGenerator> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_insert(const_iterator __hint, _Arg&& __v, const _NodeGenerator& __node_gen, false_type /* __uks */) @@ -1910,24 +1879,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { // First compute the hash code so that we don't do anything if it // throws. - __hash_code __code = this->_M_hash_code(this->_M_extract()(__v)); + __hash_code __code = this->_M_hash_code(_ExtractKey{}(__v)); // Second allocate new node so that we don't rehash if it throws. _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this }; - const key_type& __k = this->_M_extract()(__node._M_node->_M_v()); auto __pos - = _M_insert_multi_node(__hint._M_cur, __k, __code, __node._M_node); + = _M_insert_multi_node(__hint._M_cur, __code, __node._M_node); __node._M_node = nullptr; return __pos; } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: erase(const_iterator __it) -> iterator { @@ -1941,13 +1909,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return _M_erase(__bkt, __prev_n, __n); } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n) -> iterator { @@ -1969,18 +1937,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return __result; } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: - _M_erase(true_type, const key_type& __k) + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_erase(true_type /* __uks */, const key_type& __k) -> size_type { __hash_code __code = this->_M_hash_code(__k); - std::size_t __bkt = _M_bucket_index(__k, __code); + std::size_t __bkt = _M_bucket_index(__code); // Look for the node before the first matching node. __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code); @@ -1993,18 +1961,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return 1; } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: - _M_erase(false_type, const key_type& __k) + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_erase(false_type /* __uks */, const key_type& __k) -> size_type { __hash_code __code = this->_M_hash_code(__k); - std::size_t __bkt = _M_bucket_index(__k, __code); + std::size_t __bkt = _M_bucket_index(__code); // Look for the node before the first matching node. __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code); @@ -2044,13 +2012,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return __result; } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: erase(const_iterator __first, const_iterator __last) -> iterator { @@ -2091,13 +2059,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return iterator(__n); } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: clear() noexcept { this->_M_deallocate_nodes(_M_begin()); @@ -2106,13 +2074,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_before_begin._M_nxt = nullptr; } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: rehash(size_type __bkt_count) { const __rehash_state& __saved_state = _M_rehash_policy._M_state(); @@ -2129,18 +2097,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_rehash_policy._M_reset(__saved_state); } - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_rehash(size_type __bkt_count, const __rehash_state& __state) { __try { - _M_rehash_aux(__bkt_count, __unique_keys()); + _M_rehash_aux(__bkt_count, __unique_keys{}); } __catch(...) { @@ -2152,14 +2120,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } // Rehash when there is no equivalent elements. - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: - _M_rehash_aux(size_type __bkt_count, true_type) + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_rehash_aux(size_type __bkt_count, true_type /* __uks */) { __bucket_type* __new_buckets = _M_allocate_buckets(__bkt_count); __node_type* __p = _M_begin(); @@ -2195,14 +2163,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Rehash when there can be equivalent elements, preserve their relative // order. - template<typename _Key, typename _Value, - typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - typename _Traits> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: - _M_rehash_aux(size_type __bkt_count, false_type) + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_rehash_aux(size_type __bkt_count, false_type /* __uks */) { __bucket_type* __new_buckets = _M_allocate_buckets(__bkt_count); diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index 8031966f2f7..38bd5ae4e81 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -41,7 +41,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> class _Hashtable; @@ -52,9 +52,9 @@ namespace __detail * @ingroup unordered_associative_containers * @{ */ - template<typename _Key, typename _Value, - typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _Traits> + template<typename _Key, typename _Value, typename _ExtractKey, + typename _Equal, typename _Hash, typename _RangeHash, + typename _Unused, typename _Traits> struct _Hashtable_base; // Helper function: return distance(first, last) for forward @@ -81,7 +81,7 @@ namespace __detail { template<typename _Tp> _Tp&& - operator()(_Tp&& __x) const + operator()(_Tp&& __x) const noexcept { return std::forward<_Tp>(__x); } }; @@ -89,7 +89,7 @@ namespace __detail { template<typename _Tp> auto - operator()(_Tp&& __x) const + operator()(_Tp&& __x) const noexcept -> decltype(std::get<0>(std::forward<_Tp>(__x))) { return std::get<0>(std::forward<_Tp>(__x)); } }; @@ -638,37 +638,36 @@ namespace __detail */ template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits, bool _Unique_keys = _Traits::__unique_keys::value> struct _Map_base { }; /// Partial specialization, __unique_keys set to false. template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits, false> + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, false> { using mapped_type = typename std::tuple_element<1, _Pair>::type; }; /// Partial specialization, __unique_keys set to true. template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits, true> + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true> { private: - using __hashtable_base = __detail::_Hashtable_base<_Key, _Pair, - _Select1st, - _Equal, _H1, _H2, _Hash, - _Traits>; + using __hashtable_base = _Hashtable_base<_Key, _Pair, _Select1st, _Equal, + _Hash, _RangeHash, _Unused, + _Traits>; - using __hashtable = _Hashtable<_Key, _Pair, _Alloc, - _Select1st, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>; + using __hashtable = _Hashtable<_Key, _Pair, _Alloc, _Select1st, _Equal, + _Hash, _RangeHash, + _Unused, _RehashPolicy, _Traits>; using __hash_code = typename __hashtable_base::__hash_code; using __node_type = typename __hashtable_base::__node_type; @@ -694,17 +693,17 @@ namespace __detail }; template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> auto _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>:: operator[](const key_type& __k) -> mapped_type& { __hashtable* __h = static_cast<__hashtable*>(this); __hash_code __code = __h->_M_hash_code(__k); - std::size_t __bkt = __h->_M_bucket_index(__k, __code); + std::size_t __bkt = __h->_M_bucket_index(__code); if (__node_type* __node = __h->_M_find_node(__bkt, __k, __code)) return __node->_M_v().second; @@ -715,23 +714,23 @@ namespace __detail std::tuple<>() }; auto __pos - = __h->_M_insert_unique_node(__k, __bkt, __code, __node._M_node); + = __h->_M_insert_unique_node(__bkt, __code, __node._M_node); __node._M_node = nullptr; return __pos->second; } template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> auto _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>:: operator[](key_type&& __k) -> mapped_type& { __hashtable* __h = static_cast<__hashtable*>(this); __hash_code __code = __h->_M_hash_code(__k); - std::size_t __bkt = __h->_M_bucket_index(__k, __code); + std::size_t __bkt = __h->_M_bucket_index(__code); if (__node_type* __node = __h->_M_find_node(__bkt, __k, __code)) return __node->_M_v().second; @@ -742,17 +741,17 @@ namespace __detail std::tuple<>() }; auto __pos - = __h->_M_insert_unique_node(__k, __bkt, __code, __node._M_node); + = __h->_M_insert_unique_node(__bkt, __code, __node._M_node); __node._M_node = nullptr; return __pos->second; } template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> auto _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>:: at(const key_type& __k) -> mapped_type& { @@ -765,11 +764,11 @@ namespace __detail } template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> auto _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>:: at(const key_type& __k) const -> const mapped_type& { @@ -788,18 +787,18 @@ namespace __detail */ template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> struct _Insert_base { protected: - using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, - _Equal, _H1, _H2, _Hash, - _RehashPolicy, _Traits>; - using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey, - _Equal, _H1, _H2, _Hash, - _Traits>; + _Equal, _Hash, _RangeHash, + _Unused, _Traits>; + + using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, + _Unused, _RehashPolicy, _Traits>; using value_type = typename __hashtable_base::value_type; using iterator = typename __hashtable_base::iterator; @@ -849,7 +848,7 @@ namespace __detail { __hashtable& __h = _M_conjure_hashtable(); auto __code = __h._M_hash_code(__k); - std::size_t __bkt = __h._M_bucket_index(__k, __code); + std::size_t __bkt = __h._M_bucket_index(__code); if (__node_type* __node = __h._M_find_node(__bkt, __k, __code)) return { iterator(__node), false }; @@ -860,7 +859,7 @@ namespace __detail std::forward_as_tuple(std::forward<_Args>(__args)...) }; auto __it - = __h._M_insert_unique_node(__k, __bkt, __code, __node._M_node); + = __h._M_insert_unique_node(__bkt, __code, __node._M_node); __node._M_node = nullptr; return { __it, true }; } @@ -881,12 +880,13 @@ namespace __detail template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> template<typename _InputIterator, typename _NodeGetter> void - _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, - _RehashPolicy, _Traits>:: + _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, + _RehashPolicy, _Traits>:: _M_insert_range(_InputIterator __first, _InputIterator __last, const _NodeGetter& __node_gen, true_type __uks) { @@ -897,12 +897,13 @@ namespace __detail template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> template<typename _InputIterator, typename _NodeGetter> void - _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, - _RehashPolicy, _Traits>:: + _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, + _RehashPolicy, _Traits>:: _M_insert_range(_InputIterator __first, _InputIterator __last, const _NodeGetter& __node_gen, false_type __uks) { @@ -936,7 +937,7 @@ namespace __detail */ template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits, bool _Constant_iterators = _Traits::__constant_iterators::value> struct _Insert; @@ -944,20 +945,21 @@ namespace __detail /// Specialization. template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> - struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, + struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true> : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits> + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits> { using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey, - _Equal, _H1, _H2, _Hash, - _RehashPolicy, _Traits>; + _Equal, _Hash, _RangeHash, _Unused, + _RehashPolicy, _Traits>; using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey, - _Equal, _H1, _H2, _Hash, - _Traits>; + _Equal, _Hash, _RangeHash, + _Unused, _Traits>; using value_type = typename __base_type::value_type; using iterator = typename __base_type::iterator; @@ -991,15 +993,15 @@ namespace __detail /// Specialization. template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> - struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, - _RehashPolicy, _Traits, false> + struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, false> : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits> + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits> { using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey, - _Equal, _H1, _H2, _Hash, + _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>; using value_type = typename __base_type::value_type; using iterator = typename __base_type::iterator; @@ -1049,7 +1051,7 @@ namespace __detail */ template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits, typename = __detected_or_t<false_type, __has_load_factor, _RehashPolicy>> @@ -1058,25 +1060,25 @@ namespace __detail /// Specialization when rehash policy doesn't provide load factor management. template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits, - false_type> + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, + false_type /* Has load factor */> { }; /// Specialization when rehash policy provide load factor management. template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits, - true_type> + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, + true_type /* Has load factor */> { using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, - _Equal, _H1, _H2, _Hash, + _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>; float @@ -1152,7 +1154,7 @@ namespace __detail * but not between buckets. */ template<typename _Key, typename _Value, typename _ExtractKey, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, bool __cache_hash_code> struct _Local_iterator_base; @@ -1177,108 +1179,32 @@ namespace __detail * Primary template is unused except as a hook for specializations. */ template<typename _Key, typename _Value, typename _ExtractKey, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, bool __cache_hash_code> struct _Hash_code_base; - /// Specialization: ranged hash function, no caching hash codes. H1 - /// and H2 are provided but ignored. We define a dummy hash code type. - template<typename _Key, typename _Value, typename _ExtractKey, - typename _H1, typename _H2, typename _Hash> - struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false> - : private _Hashtable_ebo_helper<0, _ExtractKey>, - private _Hashtable_ebo_helper<1, _Hash> - { - private: - using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>; - using __ebo_hash = _Hashtable_ebo_helper<1, _Hash>; - - protected: - typedef void* __hash_code; - typedef _Hash_node<_Value, false> __node_type; - - // We need the default constructor for the local iterators and _Hashtable - // default constructor. - _Hash_code_base() = default; - - _Hash_code_base(const _ExtractKey& __ex, const _H1&, const _H2&, - const _Hash& __h) - : __ebo_extract_key(__ex), __ebo_hash(__h) { } - - __hash_code - _M_hash_code(const _Key& __key) const - { return 0; } - - std::size_t - _M_bucket_index(const _Key& __k, __hash_code, - std::size_t __bkt_count) const - { return _M_ranged_hash()(__k, __bkt_count); } - - std::size_t - _M_bucket_index(const __node_type* __p, std::size_t __bkt_count) const - noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>(), - (std::size_t)0)) ) - { return _M_ranged_hash()(_M_extract()(__p->_M_v()), __bkt_count); } - - void - _M_store_code(__node_type*, __hash_code) const - { } - - void - _M_copy_code(__node_type*, const __node_type*) const - { } - - void - _M_swap(_Hash_code_base& __x) - { - std::swap(__ebo_extract_key::_M_get(), - __x.__ebo_extract_key::_M_get()); - std::swap(__ebo_hash::_M_get(), __x.__ebo_hash::_M_get()); - } - - const _ExtractKey& - _M_extract() const { return __ebo_extract_key::_M_cget(); } - - const _Hash& - _M_ranged_hash() const { return __ebo_hash::_M_cget(); } - }; - - // No specialization for ranged hash function while caching hash codes. - // That combination is meaningless, and trying to do it is an error. - - /// Specialization: ranged hash function, cache hash codes. This - /// combination is meaningless, so we provide only a declaration - /// and no definition. - template<typename _Key, typename _Value, typename _ExtractKey, - typename _H1, typename _H2, typename _Hash> - struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>; - /// Specialization: hash function and range-hashing function, no /// caching of hash codes. /// Provides typedef and accessor required by C++ 11. template<typename _Key, typename _Value, typename _ExtractKey, - typename _H1, typename _H2> - struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, - _Default_ranged_hash, false> - : private _Hashtable_ebo_helper<0, _ExtractKey>, - private _Hashtable_ebo_helper<1, _H1>, - private _Hashtable_ebo_helper<2, _H2> + typename _Hash, typename _RangeHash, typename _Unused> + struct _Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, + _Unused, false> + : private _Hashtable_ebo_helper<0, _Hash> { private: - using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>; - using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>; - using __ebo_h2 = _Hashtable_ebo_helper<2, _H2>; + using __ebo_hash = _Hashtable_ebo_helper<0, _Hash>; // Gives the local iterator implementation access to _M_bucket_index(). - friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, - _Default_ranged_hash, false>; + friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, + _Hash, _RangeHash, _Unused, false>; public: - typedef _H1 hasher; + typedef _Hash hasher; hasher hash_function() const - { return _M_h1(); } + { return _M_hash(); } protected: typedef std::size_t __hash_code; @@ -1287,31 +1213,29 @@ namespace __detail // We need the default constructor for the local iterators and _Hashtable // default constructor. _Hash_code_base() = default; - - _Hash_code_base(const _ExtractKey& __ex, - const _H1& __h1, const _H2& __h2, - const _Default_ranged_hash&) - : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { } + _Hash_code_base(const _Hash& __hash) : __ebo_hash(__hash) { } __hash_code _M_hash_code(const _Key& __k) const { - static_assert(__is_invocable<const _H1&, const _Key&>{}, + static_assert(__is_invocable<const _Hash&, const _Key&>{}, "hash function must be invocable with an argument of key type"); - return _M_h1()(__k); + return _M_hash()(__k); } std::size_t - _M_bucket_index(const _Key&, __hash_code __c, - std::size_t __bkt_count) const - { return _M_h2()(__c, __bkt_count); } + _M_bucket_index(__hash_code __c, std::size_t __bkt_count) const + { return _RangeHash{}(__c, __bkt_count); } std::size_t _M_bucket_index(const __node_type* __p, std::size_t __bkt_count) const - noexcept( noexcept(declval<const _H1&>()(declval<const _Key&>())) - && noexcept(declval<const _H2&>()((__hash_code)0, - (std::size_t)0)) ) - { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v())), __bkt_count); } + noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>())) + && noexcept(declval<const _RangeHash&>()((__hash_code)0, + (std::size_t)0)) ) + { + return _RangeHash{}(_M_hash()(_ExtractKey{}(__p->_M_v())), + __bkt_count); + } void _M_store_code(__node_type*, __hash_code) const @@ -1323,49 +1247,30 @@ namespace __detail void _M_swap(_Hash_code_base& __x) - { - std::swap(__ebo_extract_key::_M_get(), - __x.__ebo_extract_key::_M_get()); - std::swap(__ebo_h1::_M_get(), __x.__ebo_h1::_M_get()); - std::swap(__ebo_h2::_M_get(), __x.__ebo_h2::_M_get()); - } - - const _ExtractKey& - _M_extract() const { return __ebo_extract_key::_M_cget(); } + { std::swap(__ebo_hash::_M_get(), __x.__ebo_hash::_M_get()); } - const _H1& - _M_h1() const { return __ebo_h1::_M_cget(); } - - const _H2& - _M_h2() const { return __ebo_h2::_M_cget(); } + const _Hash& + _M_hash() const { return __ebo_hash::_M_cget(); } }; /// Specialization: hash function and range-hashing function, /// caching hash codes. H is provided but ignored. Provides /// typedef and accessor required by C++ 11. template<typename _Key, typename _Value, typename _ExtractKey, - typename _H1, typename _H2> - struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, - _Default_ranged_hash, true> - : private _Hashtable_ebo_helper<0, _ExtractKey>, - private _Hashtable_ebo_helper<1, _H1>, - private _Hashtable_ebo_helper<2, _H2> + typename _Hash, typename _RangeHash, typename _Unused> + struct _Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, + _Unused, true> + : private _Hashtable_ebo_helper<0, _Hash> { private: - // Gives the local iterator implementation access to _M_h2(). - friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, - _Default_ranged_hash, true>; - - using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>; - using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>; - using __ebo_h2 = _Hashtable_ebo_helper<2, _H2>; + using __ebo_hash = _Hashtable_ebo_helper<0, _Hash>; public: - typedef _H1 hasher; + typedef _Hash hasher; hasher hash_function() const - { return _M_h1(); } + { return _M_hash(); } protected: typedef std::size_t __hash_code; @@ -1373,29 +1278,25 @@ namespace __detail // We need the default constructor for _Hashtable default constructor. _Hash_code_base() = default; - _Hash_code_base(const _ExtractKey& __ex, - const _H1& __h1, const _H2& __h2, - const _Default_ranged_hash&) - : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { } + _Hash_code_base(const _Hash& __hash) : __ebo_hash(__hash) { } __hash_code _M_hash_code(const _Key& __k) const { - static_assert(__is_invocable<const _H1&, const _Key&>{}, + static_assert(__is_invocable<const _Hash&, const _Key&>{}, "hash function must be invocable with an argument of key type"); - return _M_h1()(__k); + return _M_hash()(__k); } std::size_t - _M_bucket_index(const _Key&, __hash_code __c, - std::size_t __bkt_count) const - { return _M_h2()(__c, __bkt_count); } + _M_bucket_index(__hash_code __c, std::size_t __bkt_count) const + { return _RangeHash{}(__c, __bkt_count); } std::size_t _M_bucket_index(const __node_type* __p, std::size_t __bkt_count) const - noexcept( noexcept(declval<const _H2&>()((__hash_code)0, - (std::size_t)0)) ) - { return _M_h2()(__p->_M_hash_code, __bkt_count); } + noexcept( noexcept(declval<const _RangeHash&>()((__hash_code)0, + (std::size_t)0)) ) + { return _RangeHash{}(__p->_M_hash_code, __bkt_count); } void _M_store_code(__node_type* __n, __hash_code __c) const @@ -1407,43 +1308,30 @@ namespace __detail void _M_swap(_Hash_code_base& __x) - { - std::swap(__ebo_extract_key::_M_get(), - __x.__ebo_extract_key::_M_get()); - std::swap(__ebo_h1::_M_get(), __x.__ebo_h1::_M_get()); - std::swap(__ebo_h2::_M_get(), __x.__ebo_h2::_M_get()); - } - - const _ExtractKey& - _M_extract() const { return __ebo_extract_key::_M_cget(); } + { std::swap(__ebo_hash::_M_get(), __x.__ebo_hash::_M_get()); } - const _H1& - _M_h1() const { return __ebo_h1::_M_cget(); } - - const _H2& - _M_h2() const { return __ebo_h2::_M_cget(); } + const _Hash& + _M_hash() const { return __ebo_hash::_M_cget(); } }; /// Partial specialization used when nodes contain a cached hash code. template<typename _Key, typename _Value, typename _ExtractKey, - typename _H1, typename _H2, typename _Hash> + typename _Hash, typename _RangeHash, typename _Unused> struct _Local_iterator_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, true> - : private _Hashtable_ebo_helper<0, _H2> - , _Node_iterator_base<_Value, true> + _Hash, _RangeHash, _Unused, true> + : public _Node_iterator_base<_Value, true> { protected: - using __base_type = _Hashtable_ebo_helper<0, _H2>; using __base_node_iter = _Node_iterator_base<_Value, true>; using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, true>; + _Hash, _RangeHash, _Unused, true>; _Local_iterator_base() = default; - _Local_iterator_base(const __hash_code_base& __base, + _Local_iterator_base(const __hash_code_base&, _Hash_node<_Value, true>* __p, std::size_t __bkt, std::size_t __bkt_count) - : __base_type(__base._M_h2()), __base_node_iter(__p) - , _M_bucket(__bkt), _M_bucket_count(__bkt_count) { } + : __base_node_iter(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) + { } void _M_incr() @@ -1452,8 +1340,7 @@ namespace __detail if (this->_M_cur) { std::size_t __bkt - = __base_type::_M_get()(this->_M_cur->_M_hash_code, - _M_bucket_count); + = _RangeHash{}(this->_M_cur->_M_hash_code, _M_bucket_count); if (__bkt != _M_bucket) this->_M_cur = nullptr; } @@ -1499,22 +1386,23 @@ namespace __detail }; template<typename _Key, typename _Value, typename _ExtractKey, - typename _H1, typename _H2, typename _Hash> + typename _Hash, typename _RangeHash, typename _Unused> using __hash_code_for_local_iter = _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, false>>; + _Hash, _RangeHash, _Unused, false>>; // Partial specialization used when hash codes are not cached template<typename _Key, typename _Value, typename _ExtractKey, - typename _H1, typename _H2, typename _Hash> + typename _Hash, typename _RangeHash, typename _Unused> struct _Local_iterator_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, false> - : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _H1, _H2, _Hash> + _Hash, _RangeHash, _Unused, false> + : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _Hash, _RangeHash, + _Unused> , _Node_iterator_base<_Value, false> { protected: using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, false>; + _Hash, _RangeHash, _Unused, false>; using __node_iter_base = _Node_iterator_base<_Value, false>; _Local_iterator_base() : _M_bucket_count(-1) { } @@ -1582,25 +1470,25 @@ namespace __detail /// local iterators template<typename _Key, typename _Value, typename _ExtractKey, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, bool __constant_iterators, bool __cache> struct _Local_iterator : public _Local_iterator_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, __cache> + _Hash, _RangeHash, _Unused, __cache> { private: using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, __cache>; + _Hash, _RangeHash, _Unused, __cache>; using __hash_code_base = typename __base_type::__hash_code_base; public: typedef _Value value_type; typedef typename std::conditional<__constant_iterators, const _Value*, _Value*>::type - pointer; + pointer; typedef typename std::conditional<__constant_iterators, const _Value&, _Value&>::type - reference; + reference; typedef std::ptrdiff_t difference_type; typedef std::forward_iterator_tag iterator_category; @@ -1638,15 +1526,15 @@ namespace __detail /// local const_iterators template<typename _Key, typename _Value, typename _ExtractKey, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, bool __constant_iterators, bool __cache> struct _Local_const_iterator : public _Local_iterator_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, __cache> + _Hash, _RangeHash, _Unused, __cache> { private: using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, __cache>; + _Hash, _RangeHash, _Unused, __cache>; using __hash_code_base = typename __base_type::__hash_code_base; public: @@ -1665,7 +1553,7 @@ namespace __detail { } _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, + _Hash, _RangeHash, _Unused, __constant_iterators, __cache>& __x) : __base_type(__x) @@ -1705,12 +1593,12 @@ namespace __detail * - __detail::_Hash_code_base * - __detail::_Hashtable_ebo_helper */ - template<typename _Key, typename _Value, - typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _Traits> - struct _Hashtable_base - : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, - _Traits::__hash_cached::value>, + template<typename _Key, typename _Value, typename _ExtractKey, + typename _Equal, typename _Hash, typename _RangeHash, + typename _Unused, typename _Traits> + struct _Hashtable_base + : public _Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, + _Unused, _Traits::__hash_cached::value>, private _Hashtable_ebo_helper<0, _Equal> { public: @@ -1726,30 +1614,29 @@ namespace __detail using __unique_keys = typename __traits_type::__unique_keys; using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, + _Hash, _RangeHash, _Unused, __hash_cached::value>; using __hash_code = typename __hash_code_base::__hash_code; using __node_type = typename __hash_code_base::__node_type; - using iterator = __detail::_Node_iterator<value_type, - __constant_iterators::value, - __hash_cached::value>; + using iterator = _Node_iterator<value_type, + __constant_iterators::value, + __hash_cached::value>; - using const_iterator = __detail::_Node_const_iterator<value_type, - __constant_iterators::value, - __hash_cached::value>; + using const_iterator = _Node_const_iterator<value_type, + __constant_iterators::value, + __hash_cached::value>; - using local_iterator = __detail::_Local_iterator<key_type, value_type, - _ExtractKey, _H1, _H2, _Hash, - __constant_iterators::value, - __hash_cached::value>; + using local_iterator = _Local_iterator<key_type, value_type, + _ExtractKey, _Hash, _RangeHash, _Unused, + __constant_iterators::value, + __hash_cached::value>; - using const_local_iterator = __detail::_Local_const_iterator<key_type, - value_type, - _ExtractKey, _H1, _H2, _Hash, + using const_local_iterator = _Local_const_iterator<key_type, value_type, + _ExtractKey, _Hash, _RangeHash, _Unused, __constant_iterators::value, - __hash_cached::value>; + __hash_cached::value>; using __ireturn_type = typename std::conditional<__unique_keys::value, std::pair<iterator, bool>, @@ -1784,9 +1671,8 @@ namespace __detail protected: _Hashtable_base() = default; - _Hashtable_base(const _ExtractKey& __ex, const _H1& __h1, const _H2& __h2, - const _Hash& __hash, const _Equal& __eq) - : __hash_code_base(__ex, __h1, __h2, __hash), _EqualEBO(__eq) + _Hashtable_base(const _Hash& __hash, const _Equal& __eq) + : __hash_code_base(__hash), _EqualEBO(__eq) { } bool @@ -1796,15 +1682,15 @@ namespace __detail "key equality predicate must be invocable with two arguments of " "key type"); return _Equal_hash_code<__node_type>::_S_equals(__c, *__n) - && _M_eq()(__k, this->_M_extract()(__n->_M_v())); + && _M_eq()(__k, _ExtractKey{}(__n->_M_v())); } bool _M_node_equals(const __node_type* __lhn, const __node_type* __rhn) const { return _Equal_hash_code<__node_type>::_S_node_equals(*__lhn, *__rhn) - && _M_eq()(this->_M_extract()(__lhn->_M_v()), - this->_M_extract()(__rhn->_M_v())); + && _M_eq()(_ExtractKey{}(__lhn->_M_v()), + _ExtractKey{}(__rhn->_M_v())); } void @@ -1828,7 +1714,7 @@ namespace __detail */ template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits, bool _Unique_keys = _Traits::__unique_keys::value> struct _Equality; @@ -1836,13 +1722,14 @@ namespace __detail /// unordered_map and unordered_set specializations. template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits, true> + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true> { using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>; + _Hash, _RangeHash, _Unused, + _RehashPolicy, _Traits>; bool _M_equal(const __hashtable&) const; @@ -1850,11 +1737,11 @@ namespace __detail template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> bool _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>:: _M_equal(const __hashtable& __other) const { using __node_base = typename __hashtable::__node_base; @@ -1888,13 +1775,14 @@ namespace __detail /// unordered_multiset and unordered_multimap specializations. template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits, false> + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, false> { using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>; + _Hash, _RangeHash, _Unused, + _RehashPolicy, _Traits>; bool _M_equal(const __hashtable&) const; @@ -1902,11 +1790,11 @@ namespace __detail template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> bool _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits, false>:: + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, false>:: _M_equal(const __hashtable& __other) const { using __node_base = typename __hashtable::__node_base; @@ -1920,8 +1808,8 @@ namespace __detail std::size_t __x_count = 1; auto __itx_end = __itx; for (++__itx_end; __itx_end != __this->end() - && __this->key_eq()(_ExtractKey()(*__itx), - _ExtractKey()(*__itx_end)); + && __this->key_eq()(_ExtractKey{}(*__itx), + _ExtractKey{}(*__itx_end)); ++__itx_end) ++__x_count; @@ -1933,8 +1821,8 @@ namespace __detail __node_type* __y_n = static_cast<__node_type*>(__y_prev_n->_M_nxt); for (;;) { - if (__this->key_eq()(_ExtractKey()(__y_n->_M_v()), - _ExtractKey()(*__itx))) + if (__this->key_eq()(_ExtractKey{}(__y_n->_M_v()), + _ExtractKey{}(*__itx))) break; __node_type* __y_ref_n = __y_n; diff --git a/libstdc++-v3/include/bits/node_handle.h b/libstdc++-v3/include/bits/node_handle.h index cbf95f045a0..fc96937665a 100644 --- a/libstdc++-v3/include/bits/node_handle.h +++ b/libstdc++-v3/include/bits/node_handle.h @@ -226,7 +226,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _Key2, typename _Value2, typename _ValueAlloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> friend class _Hashtable; }; @@ -278,7 +278,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _Key2, typename _Value2, typename _ValueAlloc, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, + typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> friend class _Hashtable; }; |