From patchwork Sun Nov 17 21:15:05 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Fran=C3=A7ois_Dumont?= X-Patchwork-Id: 1196453 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-513856-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=gmail.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="tunOc7Xc"; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.b="c1HBt6qk"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 47GPyb02Pvz9s3Z for ; Mon, 18 Nov 2019 08:16:04 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:to :from:subject:message-id:date:mime-version:content-type; q=dns; s=default; b=s9G+M2dMdiZdkVe68rvdQumOvolQoEocNwmW8S5abmY6pHfGMC DU6IilBKncBJClaL8UBHzfBXYNPb0QTiAFWvme1B7hV330+Trny30sVg3akMQ1VH 6Kz1+UZnS+AiJEG1fpZ5RAog7+Lc5xJrSslwcrFeN8fx8r1U1YdMrdO+M= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:to :from:subject:message-id:date:mime-version:content-type; s= default; bh=LvzEh10dH1VrFjzOvK2OBW+1NUg=; b=tunOc7XcJoQUDSI6YjHo +jnlmDn6K8Rlg+pt8+X+roIkkIc7Pe03qTtExJ6jufhFCJ2yJe0PEHlY0L4un0Fc 6JFb/DwdPhkvJfGoa2AvHN1WNa7sQOH0xEuit5jMv8HzL0vK4L1FXvurSUAjgSbr UpckQS7WfvhY6dXKooaxoGU= Received: (qmail 91974 invoked by alias); 17 Nov 2019 21:15:37 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 91582 invoked by uid 89); 17 Nov 2019 21:15:31 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00, FILL_THIS_FORM, FREEMAIL_FROM, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, SPF_PASS, T_FILL_THIS_FORM_FRAUD_PHISH, T_FILL_THIS_FORM_LOAN autolearn=ham version=3.3.1 spammy=prime X-HELO: mail-wm1-f43.google.com Received: from mail-wm1-f43.google.com (HELO mail-wm1-f43.google.com) (209.85.128.43) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Sun, 17 Nov 2019 21:15:21 +0000 Received: by mail-wm1-f43.google.com with SMTP id t26so16583944wmi.4; Sun, 17 Nov 2019 13:15:10 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=to:from:subject:message-id:date:user-agent:mime-version :content-language; bh=VQ67lsm4mIKQ7WAPZLPsny/4IPyd+Fbd52JwSV7zkP8=; b=c1HBt6qkMtMRtYh5QS868xclZjC45LCaxvPy+zsntg7J43g2nJDbwJd30F2iII7di4 fZcY72pCmCjNJ0DU1HOZGWj4LWtSpKI49EQdYWhurDb6PMuzU+QBWDEliToWhmgrXIgZ d7JYjshJHen0WDb8GZnQGfgS/pJuNqgXHmmVt6FYUXFNNomMhG+LGZCFHxEnyjiFNzyd TyQ/PU5kFMZKQ4vV454ccH8f7vXGidogEtvXC3jrc6AexQNa7TtjXPvBPuEFflh560E/ Syg0FUkEiFsz4QxzAOwx/a09WilXpi5lqpegLzciw8K4/Il+2seU68CTGfB2w3APJEga EmVA== Received: from ?IPv6:2a01:e0a:1dc:b1c0:2de3:6b55:97a4:2396? ([2a01:e0a:1dc:b1c0:2de3:6b55:97a4:2396]) by smtp.googlemail.com with ESMTPSA id g4sm19575121wru.75.2019.11.17.13.15.06 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 17 Nov 2019 13:15:07 -0800 (PST) To: "libstdc++@gcc.gnu.org" , gcc-patches From: =?utf-8?q?Fran=C3=A7ois_Dumont?= Subject: [PATCH][Hashtable 5/6] Remove H1/H2 template parameters Message-ID: <93d1a4b7-bbea-2766-9a71-6ba1a789d0da@gmail.com> Date: Sun, 17 Nov 2019 22:15:05 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.9.0 MIME-Version: 1.0 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 diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index ad07a36eb83..d09c851e8a4 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 // 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 7154ec843db..4319495f18b 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/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>;