From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 23729 invoked by alias); 19 Dec 2019 19:22:44 -0000 Mailing-List: contact libstdc++-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libstdc++-owner@gcc.gnu.org Received: (qmail 23716 invoked by uid 89); 19 Dec 2019 19:22:44 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-21.2 required=5.0 tests=AWL,BAYES_00,FILL_THIS_FORM_LOAN,FREEMAIL_FROM,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,RCVD_IN_DNSWL_NONE,SPF_PASS autolearn=ham version=3.3.1 spammy=sk:__has_l X-HELO: mail-wr1-f54.google.com Received: from mail-wr1-f54.google.com (HELO mail-wr1-f54.google.com) (209.85.221.54) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 19 Dec 2019 19:22:35 +0000 Received: by mail-wr1-f54.google.com with SMTP id b6so7175922wrq.0; Thu, 19 Dec 2019 11:22:34 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=subject:from:to:references:message-id:date:user-agent:mime-version :in-reply-to:content-language; bh=EpLdt++foFJecXcTfDzdH7YXi34xaW46lOkWOZFENZc=; b=AbjpFRS1lREKXj5SRAX/6oZmxxvb8DNY8JLQewH5CKFUsNeEstXHWlKVxeym90V4IQ 04HgFD1T5M/huL4votKzUM2pzdIQ6kv6zltoeO1G9I9CuaK9EZ0R0H/bX5OioKc4KfDR UCoD6Z+VoNeTmKsjGB5a8vtbo1giDhMnez8pbWicG2LGHhiHABI3xS2PXRkUl2M4AfXI zqt42fj8qhv3JtPojjX/wi6+FmxP6+R3udhb2MDhh4S8zB6KijeaXnigRsj2grCgkLDe p4qWZLElc5rgoZDGaQfzSgfQBOj/f6SRn17sHi42NkAz+v7e8Pf1Mhro5KWlsZmijDOv IRAw== Return-Path: Received: from [10.21.6.247] ([109.190.253.11]) by smtp.googlemail.com with ESMTPSA id e8sm7181384wrt.7.2019.12.19.11.22.30 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 19 Dec 2019 11:22:30 -0800 (PST) Subject: Re: [PATCH][Hashtable 5/6] Remove H1/H2 template parameters From: =?UTF-8?Q?Fran=c3=a7ois_Dumont?= To: "libstdc++@gcc.gnu.org" , gcc-patches References: <93d1a4b7-bbea-2766-9a71-6ba1a789d0da@gmail.com> Message-ID: Date: Thu, 19 Dec 2019 19:22:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.2.1 MIME-Version: 1.0 In-Reply-To: <93d1a4b7-bbea-2766-9a71-6ba1a789d0da@gmail.com> Content-Type: multipart/mixed; boundary="------------03D68154453308403F879338" X-IsSubscribed: yes X-SW-Source: 2019-12/txt/msg00069.txt.bz2 This is a multi-part message in MIME format. --------------03D68154453308403F879338 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Content-length: 2569 Because of this change printers.py has to be updated too. François On 11/17/19 10:15 PM, François Dumont wrote: > H1 used to be a reference to the user Hash, now _Hashtable and > unordered types agree on the same Hash type which is more intuitive. > > I also chose to not support anymore a stateful ranged hash functor. We > only use _Mod_range_hashing and _Mask_range_hashing. > > Thanks to this simplification _M_bucket_index can also be simplified. > >     * include/bits/hashtable_policy.h (_Hashtable<>): Remove _H1 and _H2 >     template parameters. >     (_Hastable_base<>): Likewise. >     (_Default_ranged_hash): Remove. >     (_Prime_rehash_policy::__ranged_hash): New. >     (_Power2_rehash_policy::__ranged_hash): New. >     (_Map_base<>): Remove _H1 and _H2 template parameters. >     (_Insert_base<>): Likewise. >     (_Insert<>): Likewise. >     (_Rehash_base<>): Likewise. >     (_Local_iterator_base<>): Remove _H1 and _H2 template parameters > and add >     _RangedHash. >     (_Hash_code_base<>): Likewise. >     (_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, >     __hash_not_cached_t>): Remove. >     (_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. >     * include/bits/hashtable.h (_Hashtable<>): Remove _H1 and _H2 > template >     parameters. >     * include/bits/node_handle.h: Adapt. >     * include/bits/unordered_map.h: Adapt. >     * include/bits/unordered_set.h: Adapt. >     * testsuite/23_containers/unordered_set/hash_policy/26132.cc: Adapt. >     * testsuite/23_containers/unordered_set/hash_policy/71181.cc: Adapt. >     * testsuite/23_containers/unordered_set/hash_policy/load_factor.cc: >     Adapt. >     * testsuite/23_containers/unordered_set/hash_policy/rehash.cc: Adapt. >     * testsuite/23_containers/unordered_set/insert/hash_policy.cc: Adapt. >     * > testsuite/23_containers/unordered_set/max_load_factor/robustness.cc: >     Adapt. >     * testsuite/performance/23_containers/insert/54075.cc: Adapt. >     * testsuite/performance/23_containers/insert_erase/41975.cc: Adapt. >     * testsuite/performance/23_containers/insert_erase/ >     unordered_small_size.cc: Adapt. > > Tested under Linux x86_64. > > François > > --------------03D68154453308403F879338 Content-Type: text/x-patch; charset=UTF-8; name="hashtable#6.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="hashtable#6.patch" Content-length: 89167 diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 41be821782d..9dadc62e328 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -69,31 +69,18 @@ _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:::max()]. * - * @tparam _H2 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 _RehashPolicy Policy class with three members, all of - * which govern the bucket count. _M_next_bkt(n) returns a bucket - * count no smaller than n. _M_bkt_for_elements(n) returns a - * 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, ) + * @tparam _RehashPolicy Policy class with three members, all of which + * govern the bucket count. _M_next_bkt(n) returns a bucket count no smaller + * than n. _M_bkt_for_elements(n) returns a 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 for n_ins insertions. + * If so, returns make_pair(true, n), where n is the new bucket count. If + * not, returns make_pair(false, ) * * @tparam _Traits Compile-time class with three boolean * std::integral_constant members: __cache_hash_code, __constant_iterators, @@ -168,19 +155,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION */ template + typename _Hash, typename _RehashPolicy, typename _Traits> class _Hashtable - : public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, - _H1, _H2, _Hash, _Traits>, + : public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, _Hash, + typename _RehashPolicy::__ranged_hash, + _Traits>, public __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>, + _Hash, _RehashPolicy, _Traits>, public __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>, + _Hash, _RehashPolicy, _Traits>, public __detail::_Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>, + _Hash, _RehashPolicy, _Traits>, public __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>, + _Hash, _RehashPolicy, _Traits>, private __detail::_Hashtable_alloc< __alloc_rebind<_Alloc, __detail::_Hash_node<_Value, @@ -235,26 +222,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __detail::_Identity, __detail::_Select1st>::type; - using __hashtable_base = __detail:: - _Hashtable_base<_Key, _Value, _ExtractKey, - _Equal, _H1, _H2, _Hash, _Traits>; + using __hashtable_base = + __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, + _Hash, typename _RehashPolicy::__ranged_hash, + _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, - _RehashPolicy, _Traits>; + using __map_base = + __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RehashPolicy, _Traits>; - using __rehash_base = __detail::_Rehash_base<_Key, _Value, _Alloc, - _ExtractKey, _Equal, - _H1, _H2, _Hash, - _RehashPolicy, _Traits>; + using __rehash_base = + __detail::_Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RehashPolicy, _Traits>; - using __eq_base = __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, - _Equal, _H1, _H2, _Hash, - _RehashPolicy, _Traits>; + using __eq_base = + __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RehashPolicy, _Traits>; using __reuse_or_alloc_node_gen_t = __detail::_ReuseOrAllocNode<__node_alloc_type>; @@ -321,29 +308,20 @@ _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>::value, - "Functor used to map hash code to bucket index" - " must be default constructible"); - template friend struct __detail::_Map_base; template + typename _Hasha, typename _RehashPolicya, typename _Traitsa> friend struct __detail::_Insert_base; template friend struct __detail::_Insert; @@ -456,15 +434,14 @@ _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 _ExtractKey& __exk, const allocator_type& __a) - : __hashtable_base(__exk, __h1, __h2, __h, __eq), + : __hashtable_base(__exk, __h, __eq), __hashtable_alloc(__node_alloc_type(__a)) { } _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a, true_type) - 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), @@ -495,16 +472,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template _Hashtable(_InputIterator __first, _InputIterator __last, size_type __bkt_count_hint, - const _H1&, const _H2&, const _Hash&, - const _Equal&, const _ExtractKey&, + const _Hash&, const _Equal&, const _ExtractKey&, const allocator_type&, __unique_keys_t); template _Hashtable(_InputIterator __first, _InputIterator __last, size_type __bkt_count_hint, - const _H1&, const _H2&, const _Hash&, - const _Equal&, const _ExtractKey&, + const _Hash&, const _Equal&, const _ExtractKey&, const allocator_type&, __multi_keys_t); @@ -512,8 +487,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Constructor, destructor, assignment, swap _Hashtable() = default; _Hashtable(size_type __bkt_count_hint, - const _H1&, const _H2&, const _Hash&, - const _Equal&, const _ExtractKey&, + const _Hash&, const _Equal&, const _ExtractKey&, const allocator_type&); _Hashtable(const _Hashtable&); @@ -541,11 +515,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template _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) + 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{}) + __h, __eq, __exk, __a, __unique_keys{}) { } explicit @@ -555,31 +528,29 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION explicit _Hashtable(size_type __bkt_count_hint, - const _H1& __hf = _H1(), + const _Hash& __hf = _Hash(), const key_equal& __eql = key_equal(), const allocator_type& __a = allocator_type()) - : _Hashtable(__bkt_count_hint, __hf, _H2(), _Hash(), __eql, - __key_extract(), __a) + : _Hashtable(__bkt_count_hint, __hf, __eql, __key_extract(), __a) { } template _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, __key_extract(), + __a) { } _Hashtable(initializer_list __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, __key_extract(), __a) { } _Hashtable& @@ -588,7 +559,7 @@ _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 = @@ -620,8 +591,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 @@ -686,7 +657,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) @@ -764,8 +735,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. @@ -925,7 +896,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); @@ -1006,7 +977,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; @@ -1048,7 +1019,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION auto __pos = __i++; const key_type& __k = this->_M_extract()(*__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); @@ -1086,13 +1057,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Definitions of class template _Hashtable's out-of-line member functions. - template + template auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: _M_bucket_begin(size_type __bkt) const -> __node_type* { @@ -1100,17 +1070,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return __n ? static_cast<__node_type*>(__n->_M_nxt) : nullptr; } - template + template _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: _Hashtable(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 _ExtractKey& __exk, const allocator_type& __a) - : _Hashtable(__h1, __h2, __h, __eq, __exk, __a) + : _Hashtable(__h, __eq, __exk, __a) { auto __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count_hint); if (__bkt_count > _M_bucket_count) @@ -1120,37 +1088,33 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } } - template + template template _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _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 _ExtractKey& __exk, const allocator_type& __a, __unique_keys_t) - : _Hashtable(__bkt_count_hint, __h1, __h2, __h, __eq, __exk, __a) + : _Hashtable(__bkt_count_hint, __h, __eq, __exk, __a) { for (; __f != __l; ++__f) this->insert(*__f); } - template + template template _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _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 _ExtractKey& __exk, const allocator_type& __a, __multi_keys_t) - : _Hashtable(__h1, __h2, __h, __eq, __exk, __a) + : _Hashtable(__h, __eq, __exk, __a) { auto __nb_elems = __detail::__distance_fw(__f, __l); auto __bkt_count = @@ -1168,13 +1132,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION this->insert(*__f); } - template + template auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: operator=(const _Hashtable& __ht) -> _Hashtable& { @@ -1220,14 +1183,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return *this; } - template + template template void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: _M_assign_elements(_Ht&& __ht) { __bucket_type* __former_buckets = nullptr; @@ -1271,14 +1233,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } } - template + template template void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: _M_assign(_Ht&& __ht, const _NodeGenerator& __node_gen) { __bucket_type* __buckets = nullptr; @@ -1324,11 +1285,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: _M_reset() noexcept { _M_rehash_policy._M_reset(); @@ -1341,11 +1301,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: _M_move_assign(_Hashtable&& __ht, true_type) { this->_M_deallocate_nodes(_M_begin()); @@ -1372,11 +1331,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: _M_move_assign(_Hashtable&& __ht, false_type) { if (__ht._M_node_allocator() == this->_M_node_allocator()) @@ -1391,10 +1349,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: _Hashtable(const _Hashtable& __ht) : __hashtable_base(__ht), __map_base(__ht), @@ -1412,10 +1369,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: _Hashtable(const _Hashtable& __ht, const allocator_type& __a) : __hashtable_base(__ht), __map_base(__ht), @@ -1432,10 +1388,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a, false_type) : __hashtable_base(__ht), __map_base(__ht), @@ -1472,10 +1427,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: ~_Hashtable() noexcept { clear(); @@ -1484,13 +1438,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: swap(_Hashtable& __x) - noexcept(__and_<__is_nothrow_swappable<_H1>, + noexcept(__and_<__is_nothrow_swappable<_Hash>, __is_nothrow_swappable<_Equal>>::value) { // The only base class with member variables is hash_code_base. @@ -1530,41 +1483,38 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _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 _Hash, typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _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 _Hash, typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: count(const key_type& __k) const -> size_type { @@ -1589,11 +1539,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: equal_range(const key_type& __k) -> pair { @@ -1616,11 +1565,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: equal_range(const key_type& __k) const -> pair { @@ -1645,11 +1593,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // bkt. Return nullptr if no node is found. template + typename _Hash, typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: _M_find_before_node(size_type __bkt, const key_type& __k, __hash_code __code) const -> __node_base* @@ -1674,11 +1621,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: _M_insert_bucket_begin(size_type __bkt, __node_type* __node) { if (_M_buckets[__bkt]) @@ -1707,11 +1653,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: _M_remove_bucket_begin(size_type __bkt, __node_type* __next, size_type __next_bkt) { @@ -1731,11 +1676,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: _M_get_previous_node(size_type __bkt, __node_base* __n) -> __node_base* { @@ -1747,12 +1691,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> template auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: _M_emplace(__unique_keys_t __uks, _Args&&... __args) -> pair { @@ -1760,7 +1703,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Scoped_node __node { this, std::forward<_Args>(__args)... }; const key_type& __k = this->_M_extract()(__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); @@ -1773,12 +1716,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> template auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: _M_emplace(const_iterator __hint, __multi_keys_t __mks, _Args&&... __args) -> iterator { @@ -1795,11 +1737,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: _M_insert_node(__unique_keys_t, size_type __bkt, __hash_code __code, __node_type* __node, size_type __n_elt) -> iterator @@ -1812,7 +1753,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__do_rehash.first) { _M_rehash(__do_rehash.second, __saved_state); - __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v()), __code); + __bkt = _M_bucket_index(__code); } this->_M_store_code(__node, __code); @@ -1825,11 +1766,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: _M_insert_node(__multi_keys_t, __node_type* __hint, __hash_code __code, __node_type* __node) -> iterator @@ -1843,7 +1783,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION this->_M_store_code(__node, __code); const key_type& __k = this->_M_extract()(__node->_M_v()); - size_type __bkt = _M_bucket_index(__k, __code); + 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. @@ -1880,19 +1820,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Insert v if no element with its key is already present. template + typename _Hash, typename _RehashPolicy, typename _Traits> template auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen, __unique_keys_t __uks) -> pair { const key_type& __k = this->_M_extract()(__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 }; @@ -1906,12 +1845,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Insert v unconditionally. template + typename _Hash, typename _RehashPolicy, typename _Traits> template auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: _M_insert(const_iterator __hint, _Arg&& __v, const _NodeGenerator& __node_gen, __multi_keys_t __mks) -> iterator @@ -1931,11 +1869,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: erase(const_iterator __it) -> iterator { @@ -1951,11 +1888,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n) -> iterator { @@ -1979,16 +1915,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: _M_erase(__unique_keys_t, 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); @@ -2003,16 +1938,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: _M_erase(__multi_keys_t, 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); @@ -2054,11 +1988,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: erase(const_iterator __first, const_iterator __last) -> iterator { @@ -2101,11 +2034,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: clear() noexcept { this->_M_deallocate_nodes(_M_begin()); @@ -2116,11 +2048,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: rehash(size_type __bkt_count) { const __rehash_state& __saved_state = _M_rehash_policy._M_state(); @@ -2139,11 +2070,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: _M_rehash(size_type __bkt_count, const __rehash_state& __state) { __try @@ -2162,11 +2092,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Rehash when there is no equivalent elements. template + typename _Hash, typename _RehashPolicy, typename _Traits> void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: _M_rehash_aux(size_type __bkt_count, __unique_keys_t) { __bucket_type* __new_buckets = _M_allocate_buckets(__bkt_count); @@ -2205,11 +2134,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // order. template + typename _Hash, typename _RehashPolicy, typename _Traits> void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _Hash, _RehashPolicy, _Traits>:: _M_rehash_aux(size_type __bkt_count, __multi_keys_t) { __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 5cc943b3d22..11ea47b322e 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -41,8 +41,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, + typename _Traits> class _Hashtable; namespace __detail @@ -54,7 +54,8 @@ namespace __detail */ template + typename _Hash, typename _RangedHash, + typename _Traits> struct _Hashtable_base; // Helper function: return distance(first, last) for forward @@ -442,18 +443,12 @@ namespace __detail { return __num % __den; } }; - /// Default ranged hash function H. In principle it should be a - /// function object composed from objects of type H1 and H2 such that - /// h(k, N) = h2(h1(k), N), but that would mean making extra copies of - /// h1 and h2. So instead we'll just use a tag to tell class template - /// hashtable to do that composition. - struct _Default_ranged_hash { }; - /// Default value for rehash policy. Bucket size is (usually) the /// smallest prime that keeps the load factor small enough. struct _Prime_rehash_policy { using __has_load_factor = true_type; + using __ranged_hash = _Mod_range_hashing; _Prime_rehash_policy(float __z = 1.0) noexcept : _M_max_load_factor(__z), _M_next_resize(0) { } @@ -531,6 +526,7 @@ namespace __detail struct _Power2_rehash_policy { using __has_load_factor = true_type; + using __ranged_hash = _Mask_range_hashing; _Power2_rehash_policy(float __z = 1.0) noexcept : _M_max_load_factor(__z), _M_next_resize(0) { } @@ -648,37 +644,33 @@ namespace __detail */ template struct _Map_base { }; /// Partial specialization, keys are not unique. template + typename _Hash, typename _RehashPolicy, typename _Traits> struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits, __multi_keys_t> + _Hash, _RehashPolicy, _Traits, __multi_keys_t> { using mapped_type = typename std::tuple_element<1, _Pair>::type; }; /// Partial specialization, keys are unique. template + typename _Hash, typename _RehashPolicy, typename _Traits> struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t> + _Hash, _RehashPolicy, _Traits, __unique_keys_t> { private: - using __hashtable_base = __detail::_Hashtable_base<_Key, _Pair, - _Select1st, - _Equal, _H1, _H2, _Hash, - _Traits>; + using __hashtable_base = + __detail::_Hashtable_base<_Key, _Pair, _Select1st, _Equal, + _Hash, typename _RehashPolicy::__ranged_hash, + _Traits>; - using __hashtable = _Hashtable<_Key, _Pair, _Alloc, - _Select1st, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>; + using __hashtable = _Hashtable<_Key, _Pair, _Alloc, _Select1st, _Equal, + _Hash, _RehashPolicy, _Traits>; using __hash_code = typename __hashtable_base::__hash_code; using __node_type = typename __hashtable_base::__node_type; @@ -704,17 +696,16 @@ namespace __detail }; template + typename _Hash, typename _RehashPolicy, typename _Traits> auto _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t>:: + _Hash, _RehashPolicy, _Traits, __unique_keys_t>:: 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; @@ -731,17 +722,16 @@ namespace __detail } template + typename _Hash, typename _RehashPolicy, typename _Traits> auto _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t>:: + _Hash, _RehashPolicy, _Traits, __unique_keys_t>:: 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; @@ -758,11 +748,10 @@ namespace __detail } template + typename _Hash, typename _RehashPolicy, typename _Traits> auto _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t>:: + _Hash, _RehashPolicy, _Traits, __unique_keys_t>:: at(const key_type& __k) -> mapped_type& { @@ -775,11 +764,10 @@ namespace __detail } template + typename _Hash, typename _RehashPolicy, typename _Traits> auto _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t>:: + _Hash, _RehashPolicy, _Traits, __unique_keys_t>:: at(const key_type& __k) const -> const mapped_type& { @@ -798,18 +786,16 @@ namespace __detail */ template + typename _Hash, typename _RehashPolicy, typename _Traits> struct _Insert_base { protected: using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, - _Equal, _H1, _H2, _Hash, - _RehashPolicy, _Traits>; + _Equal, _Hash, _RehashPolicy, _Traits>; - using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey, - _Equal, _H1, _H2, _Hash, - _Traits>; + using __hashtable_base = + _Hashtable_base<_Key, _Value, _ExtractKey, _Equal, + _Hash, typename _RehashPolicy::__ranged_hash, _Traits>; using value_type = typename __hashtable_base::value_type; using iterator = typename __hashtable_base::iterator; @@ -871,12 +857,11 @@ namespace __detail template + typename _Hash, typename _RehashPolicy, typename _Traits> template void - _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, - _RehashPolicy, _Traits>:: + _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RehashPolicy, _Traits>:: _M_insert_range(_InputIterator __first, _InputIterator __last, const _NodeGetter& __node_gen, __unique_keys_t __uks) { @@ -887,12 +872,11 @@ namespace __detail template + typename _Hash, typename _RehashPolicy, typename _Traits> template void - _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, - _RehashPolicy, _Traits>:: + _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RehashPolicy, _Traits>:: _M_insert_range(_InputIterator __first, _InputIterator __last, const _NodeGetter& __node_gen, __multi_keys_t __mks) { @@ -926,28 +910,25 @@ namespace __detail */ template struct _Insert; /// Specialization. template - struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, + typename _Hash, typename _RehashPolicy, typename _Traits> + struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RehashPolicy, _Traits, __constant_iterators_t> : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits> + _Hash, _RehashPolicy, _Traits> { using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey, - _Equal, _H1, _H2, _Hash, - _RehashPolicy, _Traits>; + _Equal, _Hash, _RehashPolicy, _Traits>; - using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey, - _Equal, _H1, _H2, _Hash, - _Traits>; + using __hashtable_base = + _Hashtable_base<_Key, _Value, _ExtractKey, _Equal, _Hash, + typename _RehashPolicy::__ranged_hash, _Traits>; using value_type = typename __base_type::value_type; using iterator = typename __base_type::iterator; @@ -981,16 +962,14 @@ namespace __detail /// Specialization. template - struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, - _RehashPolicy, _Traits, __mutable_iterators_t> + typename _Hash, typename _RehashPolicy, typename _Traits> + struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RehashPolicy, _Traits, __mutable_iterators_t> : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits> + _Hash, _RehashPolicy, _Traits> { using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey, - _Equal, _H1, _H2, _Hash, - _RehashPolicy, _Traits>; + _Equal, _Hash, _RehashPolicy, _Traits>; using value_type = typename __base_type::value_type; using iterator = typename __base_type::iterator; using const_iterator = typename __base_type::const_iterator; @@ -1039,8 +1018,7 @@ namespace __detail */ template> struct _Rehash_base; @@ -1048,26 +1026,21 @@ namespace __detail /// Specialization when rehash policy doesn't provide load factor management. template + typename _Hash, typename _RehashPolicy, typename _Traits> struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits, - false_type> + _Hash, _RehashPolicy, _Traits, false_type> { }; /// Specialization when rehash policy provide load factor management. template + typename _Hash, typename _RehashPolicy, typename _Traits> struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits, - true_type> + _Hash, _RehashPolicy, _Traits, true_type> { using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, - _Equal, _H1, _H2, _Hash, - _RehashPolicy, _Traits>; + _Equal, _Hash, _RehashPolicy, _Traits>; float max_load_factor() const noexcept @@ -1142,7 +1115,7 @@ namespace __detail * but not between buckets. */ template struct _Local_iterator_base; @@ -1167,111 +1140,35 @@ namespace __detail * Primary template is unused except as a hook for specializations. */ template 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 - struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, - __hash_not_cached_t> - : 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, __hash_not_cached_t> __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()(declval(), - (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 - struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, - __hash_cached_t>; - /// Specialization: hash function and range-hashing function, no /// caching of hash codes. /// Provides typedef and accessor required by C++ 11. template - struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, - _Default_ranged_hash, __hash_not_cached_t> + typename _Hash, typename _RangedHash> + struct _Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangedHash, + __hash_not_cached_t> : private _Hashtable_ebo_helper<0, _ExtractKey>, - private _Hashtable_ebo_helper<1, _H1>, - private _Hashtable_ebo_helper<2, _H2> + private _Hashtable_ebo_helper<1, _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<1, _Hash>; // Gives the local iterator implementation access to _M_bucket_index(). - friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, - _Default_ranged_hash, + friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, + _Hash, _RangedHash, __hash_not_cached_t>; public: - typedef _H1 hasher; + typedef _Hash hasher; hasher hash_function() const - { return _M_h1(); } + { return _M_hash(); } protected: typedef std::size_t __hash_code; @@ -1281,30 +1178,29 @@ namespace __detail // 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 _ExtractKey& __ex, const _Hash& __hash) + : __ebo_extract_key(__ex), __ebo_hash(__hash) { } __hash_code _M_hash_code(const _Key& __k) const { - static_assert(__is_invocable{}, + static_assert(__is_invocable{}, "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 _RangedHash{}(__c, __bkt_count); } std::size_t _M_bucket_index(const __node_type* __p, std::size_t __bkt_count) const - noexcept( noexcept(declval()(declval())) - && noexcept(declval()((__hash_code)0, - (std::size_t)0)) ) - { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v())), __bkt_count); } + noexcept( noexcept(declval()(declval())) + && noexcept(declval()((__hash_code)0, + (std::size_t)0)) ) + { + return _RangedHash{}(_M_hash()(_M_extract()(__p->_M_v())), __bkt_count); + } void _M_store_code(__node_type*, __hash_code) const @@ -1319,46 +1215,41 @@ namespace __detail { 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()); + std::swap(__ebo_hash::_M_get(), __x.__ebo_hash::_M_get()); } const _ExtractKey& _M_extract() const { return __ebo_extract_key::_M_cget(); } - 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 - struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, - _Default_ranged_hash, __hash_cached_t> + typename _Hash, typename _RangedHash> + struct _Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangedHash, + __hash_cached_t> : private _Hashtable_ebo_helper<0, _ExtractKey>, - private _Hashtable_ebo_helper<1, _H1>, - private _Hashtable_ebo_helper<2, _H2> + private _Hashtable_ebo_helper<1, _Hash> { private: // Gives the local iterator implementation access to _M_h2(). - friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, - _Default_ranged_hash, __hash_cached_t>; + friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, + _Hash, _RangedHash, + __hash_cached_t>; 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<1, _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; @@ -1366,29 +1257,26 @@ 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 _ExtractKey& __ex, const _Hash& __hash) + : __ebo_extract_key(__ex), __ebo_hash(__hash) { } __hash_code _M_hash_code(const _Key& __k) const { - static_assert(__is_invocable{}, + static_assert(__is_invocable{}, "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 _RangedHash{}(__c, __bkt_count); } std::size_t _M_bucket_index(const __node_type* __p, std::size_t __bkt_count) const - noexcept( noexcept(declval()((__hash_code)0, - (std::size_t)0)) ) - { return _M_h2()(__p->_M_hash_code, __bkt_count); } + noexcept( noexcept(declval()((__hash_code)0, + (std::size_t)0)) ) + { return _RangedHash{}(__p->_M_hash_code, __bkt_count); } void _M_store_code(__node_type* __n, __hash_code __c) const @@ -1403,41 +1291,36 @@ namespace __detail { 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()); + std::swap(__ebo_hash::_M_get(), __x.__ebo_hash::_M_get()); } const _ExtractKey& _M_extract() const { return __ebo_extract_key::_M_cget(); } - 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 _Hash, typename _RangedHash> struct _Local_iterator_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, __hash_cached_t> - : private _Hashtable_ebo_helper<0, _H2> - , _Node_iterator_base<_Value, __hash_cached_t> + _Hash, _RangedHash, __hash_cached_t> + : public _Node_iterator_base<_Value, __hash_cached_t> { protected: - using __base_type = _Hashtable_ebo_helper<0, _H2>; - using __base_node_iter = _Node_iterator_base<_Value, __hash_cached_t>; - using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, - __hash_cached_t>; + using __hash_code_base = + _Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangedHash, + __hash_cached_t>; + using __base_node_iter = + _Node_iterator_base<_Value, __hash_cached_t>; _Local_iterator_base() = default; - _Local_iterator_base(const __hash_code_base& __base, + _Local_iterator_base(const __hash_code_base&, _Hash_node<_Value, __hash_cached_t>* __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() @@ -1446,8 +1329,7 @@ namespace __detail if (this->_M_cur) { std::size_t __bkt - = __base_type::_M_get()(this->_M_cur->_M_hash_code, - _M_bucket_count); + = _RangedHash{}(this->_M_cur->_M_hash_code, _M_bucket_count); if (__bkt != _M_bucket) this->_M_cur = nullptr; } @@ -1493,23 +1375,23 @@ namespace __detail }; template + typename _Hash, typename _RangedHash> using __hash_code_for_local_iter = _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, + _Hash, _RangedHash, __hash_not_cached_t>>; // Partial specialization used when hash codes are not cached template + typename _Hash, typename _RangedHash> struct _Local_iterator_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, __hash_not_cached_t> - : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _H1, _H2, _Hash> + _Hash, _RangedHash, __hash_not_cached_t> + : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _Hash, _RangedHash> , _Node_iterator_base<_Value, __hash_not_cached_t> { protected: using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, + _Hash, _RangedHash, __hash_not_cached_t>; using __node_iter_base = _Node_iterator_base<_Value, __hash_not_cached_t>; @@ -1578,15 +1460,16 @@ namespace __detail /// local iterators template struct _Local_iterator : public _Local_iterator_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, _Cache_hash_code> + _Hash, _RangedHash, _Cache_hash_code> { private: - using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, _Cache_hash_code>; + using __base_type = + _Local_iterator_base<_Key, _Value, _ExtractKey, _Hash, _RangedHash, + _Cache_hash_code>; using __hash_code_base = typename __base_type::__hash_code_base; public: @@ -1634,15 +1517,15 @@ namespace __detail /// local const_iterators template struct _Local_const_iterator : public _Local_iterator_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, _Cache_hash_code> + _Hash, _RangedHash, _Cache_hash_code> { private: using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, + _Hash, _RangedHash, _Cache_hash_code>; using __hash_code_base = typename __base_type::__hash_code_base; @@ -1662,7 +1545,7 @@ namespace __detail { } _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, + _Hash, _RangedHash, _Constant_iterators, _Cache_hash_code>& __x) : __base_type(__x) @@ -1704,9 +1587,9 @@ namespace __detail */ template + typename _Hash, typename _RangedHash, typename _Traits> struct _Hashtable_base - : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, + : public _Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangedHash, typename _Traits::__hash_cached>, private _Hashtable_ebo_helper<0, _Equal> { @@ -1723,30 +1606,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, _RangedHash, __hash_cached>; using __hash_code = typename __hash_code_base::__hash_code; using __node_type = typename __hash_code_base::__node_type; - using iterator = __detail::_Node_iterator; + using iterator = + __detail::_Node_iterator; - using const_iterator = __detail::_Node_const_iterator; + using const_iterator = + __detail::_Node_const_iterator; - using local_iterator = __detail::_Local_iterator; + using local_iterator = + __detail::_Local_iterator; - using const_local_iterator = __detail::_Local_const_iterator; + using const_local_iterator = + __detail::_Local_const_iterator; using __ireturn_type = typename std::conditional<__unique_keys::value, std::pair, @@ -1781,9 +1663,9 @@ namespace __detail protected: _Hashtable_base() = default; - _Hashtable_base(const _ExtractKey& __ex, const _H1& __h1, const _H2& __h2, + _Hashtable_base(const _ExtractKey& __ex, const _Hash& __hash, const _Equal& __eq) - : __hash_code_base(__ex, __h1, __h2, __hash), _EqualEBO(__eq) + : __hash_code_base(__ex, __hash), _EqualEBO(__eq) { } bool @@ -1884,21 +1766,20 @@ namespace __detail */ template struct _Equality; /// Specialization. template + typename _Hash, typename _RehashPolicy, typename _Traits> struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t> + _Hash, _RehashPolicy, _Traits, __unique_keys_t> { using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>; + _Hash, _RehashPolicy, _Traits>; bool _M_equal(const __hashtable&) const; @@ -1906,11 +1787,10 @@ namespace __detail template + typename _Hash, typename _RehashPolicy, typename _Traits> bool _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t>:: + _Hash, _RehashPolicy, _Traits, __unique_keys_t>:: _M_equal(const __hashtable& __other) const { const __hashtable* __this = static_cast(this); @@ -1930,14 +1810,13 @@ namespace __detail /// Specialization. template + typename _Hash, typename _RehashPolicy, typename _Traits> struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits, __multi_keys_t> + _Hash, _RehashPolicy, _Traits, __multi_keys_t> : public _Equality_base { using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>; + _Hash, _RehashPolicy, _Traits>; bool _M_equal(const __hashtable&) const; @@ -1945,11 +1824,10 @@ namespace __detail template + typename _Hash, typename _RehashPolicy, typename _Traits> bool _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits, __multi_keys_t>:: + _Hash, _RehashPolicy, _Traits, __multi_keys_t>:: _M_equal(const __hashtable& __other) const { const __hashtable* __this = static_cast(this); diff --git a/libstdc++-v3/include/bits/node_handle.h b/libstdc++-v3/include/bits/node_handle.h index 2d134c1ba2c..013d9d7dbbf 100644 --- a/libstdc++-v3/include/bits/node_handle.h +++ b/libstdc++-v3/include/bits/node_handle.h @@ -226,8 +226,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> friend class _Hashtable; }; @@ -278,8 +277,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template + typename _Hash, typename _RehashPolicy, typename _Traits> friend class _Hashtable; }; diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h index 5131e02e8aa..310cfd39d79 100644 --- a/libstdc++-v3/include/bits/unordered_map.h +++ b/libstdc++-v3/include/bits/unordered_map.h @@ -48,8 +48,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER using __umap_hashtable = _Hashtable<_Key, std::pair, _Alloc, __detail::_Select1st, _Pred, _Hash, - __detail::_Mod_range_hashing, - __detail::_Default_ranged_hash, __detail::_Prime_rehash_policy, _Tr>; /// Base types for unordered_multimap. @@ -65,8 +63,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER using __ummap_hashtable = _Hashtable<_Key, std::pair, _Alloc, __detail::_Select1st, _Pred, _Hash, - __detail::_Mod_range_hashing, - __detail::_Default_ranged_hash, __detail::_Prime_rehash_policy, _Tr>; template diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h index d3aec2b961d..590bda8f060 100644 --- a/libstdc++-v3/include/bits/unordered_set.h +++ b/libstdc++-v3/include/bits/unordered_set.h @@ -46,8 +46,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER typename _Tr = __uset_traits<__cache_default<_Value, _Hash>::value>> using __uset_hashtable = _Hashtable<_Value, _Value, _Alloc, __detail::_Identity, _Pred, _Hash, - __detail::_Mod_range_hashing, - __detail::_Default_ranged_hash, __detail::_Prime_rehash_policy, _Tr>; /// Base types for unordered_multiset. @@ -62,8 +60,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER using __umset_hashtable = _Hashtable<_Value, _Value, _Alloc, __detail::_Identity, _Pred, _Hash, - __detail::_Mod_range_hashing, - __detail::_Default_ranged_hash, __detail::_Prime_rehash_policy, _Tr>; template diff --git a/libstdc++-v3/python/libstdcxx/v6/printers.py b/libstdc++-v3/python/libstdcxx/v6/printers.py index 66560701fb9..746652b448b 100644 --- a/libstdc++-v3/python/libstdcxx/v6/printers.py +++ b/libstdc++-v3/python/libstdcxx/v6/printers.py @@ -945,7 +945,7 @@ class StdHashtableIterator(Iterator): def __init__(self, hashtable): self.node = hashtable['_M_before_begin']['_M_nxt'] valtype = hashtable.type.template_argument(1) - cached = hashtable.type.template_argument(9).template_argument(0) + cached = hashtable.type.template_argument(7).template_argument(0) node_type = lookup_templ_spec('std::__detail::_Hash_node', str(valtype), 'std::integral_constant'.format('true' if cached else 'false')) self.node_type = node_type.pointer() diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/26132.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/26132.cc index dd3a4fd9b76..1fd87693bed 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/26132.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/26132.cc @@ -55,8 +55,6 @@ template std::__detail::_Identity, std::equal_to<_Value>, std::hash<_Value>, - std::__detail::_Mask_range_hashing, - std::__detail::_Default_ranged_hash, std::__detail::_Power2_rehash_policy, std::__detail::_Hashtable_traits>; diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc index 7bbf4fd73db..1f6caa36700 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/71181.cc @@ -49,8 +49,6 @@ template std::__detail::_Identity, std::equal_to<_Value>, std::hash<_Value>, - std::__detail::_Mask_range_hashing, - std::__detail::_Default_ranged_hash, std::__detail::_Power2_rehash_policy, std::__detail::_Hashtable_traits>; diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/load_factor.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/load_factor.cc index 2a9dd745bcc..d68fac7697e 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/load_factor.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/load_factor.cc @@ -58,8 +58,6 @@ template std::__detail::_Identity, std::equal_to<_Value>, std::hash<_Value>, - std::__detail::_Mask_range_hashing, - std::__detail::_Default_ranged_hash, std::__detail::_Power2_rehash_policy, std::__detail::_Hashtable_traits>; diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/rehash.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/rehash.cc index d717b0c7def..a134b353889 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/rehash.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/rehash.cc @@ -62,8 +62,6 @@ template std::__detail::_Identity, std::equal_to<_Value>, std::hash<_Value>, - std::__detail::_Mask_range_hashing, - std::__detail::_Default_ranged_hash, std::__detail::_Power2_rehash_policy, std::__detail::_Hashtable_traits>; diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/insert/hash_policy.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/insert/hash_policy.cc index 89cda8daa8d..54e5635684f 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/insert/hash_policy.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/insert/hash_policy.cc @@ -122,8 +122,6 @@ template>; diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/max_load_factor/robustness.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/max_load_factor/robustness.cc index 47cbadeb746..c36c9f6f977 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/max_load_factor/robustness.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/max_load_factor/robustness.cc @@ -84,8 +84,6 @@ template>; diff --git a/libstdc++-v3/testsuite/performance/23_containers/insert/54075.cc b/libstdc++-v3/testsuite/performance/23_containers/insert/54075.cc index 4e9b6e01a87..a632f659a1f 100644 --- a/libstdc++-v3/testsuite/performance/23_containers/insert/54075.cc +++ b/libstdc++-v3/testsuite/performance/23_containers/insert/54075.cc @@ -134,8 +134,6 @@ template std::_Hashtable, std::__detail::_Identity, std::equal_to, HashFunction, - std::__detail::_Mask_range_hashing, - std::__detail::_Default_ranged_hash, std::__detail::_Power2_rehash_policy, std::__uset_traits>; @@ -144,8 +142,6 @@ template std::_Hashtable, std::__detail::_Identity, std::equal_to, HashFunction, - std::__detail::_Mask_range_hashing, - std::__detail::_Default_ranged_hash, std::__detail::_Power2_rehash_policy, std::__umset_traits>; diff --git a/libstdc++-v3/testsuite/performance/23_containers/insert_erase/41975.cc b/libstdc++-v3/testsuite/performance/23_containers/insert_erase/41975.cc index b6b303d853c..5bf05ee9587 100644 --- a/libstdc++-v3/testsuite/performance/23_containers/insert_erase/41975.cc +++ b/libstdc++-v3/testsuite/performance/23_containers/insert_erase/41975.cc @@ -181,8 +181,6 @@ template std::_Hashtable, std::__detail::_Identity, std::equal_to, std::hash, - std::__detail::_Mask_range_hashing, - std::__detail::_Default_ranged_hash, std::__detail::_Power2_rehash_policy, std::__uset_traits>; @@ -205,8 +203,6 @@ template std::_Hashtable, std::__detail::_Identity, std::equal_to, std::hash, - std::__detail::_Mask_range_hashing, - std::__detail::_Default_ranged_hash, std::__detail::_Power2_rehash_policy, std::__uset_traits>; diff --git a/libstdc++-v3/testsuite/performance/23_containers/insert_erase/unordered_small_size.cc b/libstdc++-v3/testsuite/performance/23_containers/insert_erase/unordered_small_size.cc index ca589ad85b7..3514343e7df 100644 --- a/libstdc++-v3/testsuite/performance/23_containers/insert_erase/unordered_small_size.cc +++ b/libstdc++-v3/testsuite/performance/23_containers/insert_erase/unordered_small_size.cc @@ -206,8 +206,6 @@ template std::_Hashtable, std::__detail::_Identity, std::equal_to, std::hash, - std::__detail::_Mask_range_hashing, - std::__detail::_Default_ranged_hash, std::__detail::_Power2_rehash_policy, std::__uset_traits>; @@ -230,8 +228,6 @@ template std::_Hashtable, std::__detail::_Identity, std::equal_to, std::hash, - std::__detail::_Mask_range_hashing, - std::__detail::_Default_ranged_hash, std::__detail::_Power2_rehash_policy, std::__uset_traits>; --------------03D68154453308403F879338--