From patchwork Sun Nov 17 21:31:17 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: 1196457 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-513857-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="FMHL+gII"; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.b="Cp19yEE/"; 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 47GQJb39FNz9sP3 for ; Mon, 18 Nov 2019 08:31:41 +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=Aw2vMUrnCoLjQjgYJlfstFAKRINWfWlzteDCcHkQKnBM6XY0ZZ vd7SBcIrZqbH45M5QxrIed8vhFar6iKFRZpBd7B3V6ow2tXJS24VSZVDNrKu6xn+ WfHHXwAsU2OSw/oiV9cJQqHxQ0lLMznbzSKdI/T21A0BeixaCO3jMo3KQ= 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=Vvoy60xEX5MVqnX1Uask17QXD+Y=; b=FMHL+gII+rhlt3hC5/uc Il9fuwSFPNBgVrSV0rvBc02F5Dcsc10QJb39iEbLL+MJZ5FMCCu7X+gfLyeVDybn zgmOAFC7jfT/S4xrsWkxhynjv47CHzr9RIbEZi4+9WXNVNhbSi+M5vUoZCnFDGZc WaN52cPgnOr/Iq/+H22cvYI= Received: (qmail 118239 invoked by alias); 17 Nov 2019 21:31:25 -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 118221 invoked by uid 89); 17 Nov 2019 21:31:25 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00, 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= X-HELO: mail-wm1-f47.google.com Received: from mail-wm1-f47.google.com (HELO mail-wm1-f47.google.com) (209.85.128.47) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Sun, 17 Nov 2019 21:31:22 +0000 Received: by mail-wm1-f47.google.com with SMTP id q70so15295592wme.1; Sun, 17 Nov 2019 13:31:21 -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=eS6wfzPfly+puLUAmrM06CJF714qExCedAlUDIk0h+c=; b=Cp19yEE/TdbDIkQZSdLLrYOpm87oR05e44qkNgvmcIcrmd43yoMaJ1C2Y1Ksw2LlGw TcF7y74i1CzdOLnrDxM/K6vgU9dlNAUqvWs9/j4txXffEAOA+r1DwgDPHi0KHLOPXQBY Sk/PyQH4vaOeGmbjpH+UGXhUQOsoUPjlt8VKHsqu4OqzyfdJ8YDYuw8o664sOMg/N3hL kmK3myBVm6CdqtlHHq54JemVXdZ+c9rNiv9STLwZLRjLIwt6sJ85ywtgCRy7VlqMCjTQ utU7d9aJU3YHB7wob9oqaJfD9qXKE5z0mRjy889WLShZFLE1heIyQBoNfPOFZErXhTgo AqTA== 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 91sm21940713wrm.42.2019.11.17.13.31.17 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 17 Nov 2019 13:31:18 -0800 (PST) To: "libstdc++@gcc.gnu.org" , gcc-patches From: =?utf-8?q?Fran=C3=A7ois_Dumont?= Subject: [PATCH][Hashtable 6/6] PR 68303 small size optimization Message-ID: <88d3aa39-2146-3ea5-8bb2-a4d9b70accbd@gmail.com> Date: Sun, 17 Nov 2019 22:31:17 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.9.0 MIME-Version: 1.0 This is an implementation of PR 68303. I try to use this idea as much as possible to avoid computation of hash codes. Note that tests are not showing any gain. I guess hash computation must be quite bad to get a benefit from it. So I am only activating it when hash code is not cached and/or when computation is not fast.     PR libstdc++/68303     * include/bits/hashtable_policy.h     (_Small_size_threshold<_Hash>): New.     (_Hashtable_traits<>): Add _Small_size_threshold std::size_t template     parameter, default to 0.     (_Hashtable_traits<>::__small_size_threshold): New.     (_Hash_code_base<>::_M_hash_code(const __node_type*)): New.     (_Equal_helper<>::_S_node_equals): New.     * include/bits/hashtable.h:     (__small_size_threshold_default<>): New template alias.     (_Hashtable<>::find): Add linear lookup when size is lower or equal to     _Small_size_threshold.     (_Hashtable<>::_M_emplace<_Args>(true_type, _Args&&...)): Add linear     lookup when size is lower or equal to _Small_size_threshold.     (_Hashtable<>::_M_insert<>(_Arg&&, const _NodeGenerator&, true_type,     size_type)): Likewise.     (_Hashtable<>::_M_compute_hash_code(const_iterator, const key_type&)):     New.     (_Hashtable<>::_M_emplace<_Args>(false_type, _Args&&...)): Use latter.     (_Hashtable<>::_M_insert(const_iterator, _Arg&&, const _NodeGenerator&,     false_type)): Likewise.     (_Hashtable<>::_M_find_before_node(const key_type&)): New.     (_Hashtable<>::_M_erase(true_type, const key_type&)): Use latter if size     is lower or equal to _Small_size_threshold.     (_Hashtable<>::_M_erase(false_type, const key_type&)): Likewise.     * include/bits/unordered_map.h (__umaps_traits): Adapt using small size     threshold set to 20.     (__ummap_traits): Likewise.     * include/bits/unordered_set.h (__uset_traits, __ummset_traits): Likewise.     * src/c++11/hashtable_c++0x.cc: Add include. Tested under Linux x86_64. François diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 9dadc62e328..460f25affe4 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -48,6 +48,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Mandatory to have erase not throwing. __is_nothrow_invocable>>; + template + using __small_size_threshold_default + = typename conditional<__cache, + // No small size optimization if hash code is cached... + integral_constant, + _Small_size_threshold<_Hash>>::type; /** * Primary class template _Hashtable. * @@ -743,6 +749,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __node_base* _M_find_before_node(size_type, const key_type&, __hash_code) const; + __node_base* + _M_find_before_node(const key_type&); + __node_type* _M_find_node(size_type __bkt, const key_type& __key, __hash_code __c) const @@ -766,6 +775,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __node_base* _M_get_previous_node(size_type __bkt, __node_base* __n); + pair + _M_compute_hash_code(const_iterator __hint, const key_type& __k) const; + // Insert node __n with hash code __code, in bucket __bkt if no // rehash (assumes no element with same key already present). // Takes ownership of __n if insertion succeeds, throws otherwise. @@ -1490,6 +1502,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION find(const key_type& __k) -> iterator { + if (size() <= __traits_type::__small_size_threshold::value) + { + for (auto __it = begin(); __it != end(); ++__it) + if (this->_M_key_equals(__k, __it._M_cur)) + return __it; + return end(); + } + __hash_code __code = this->_M_hash_code(__k); std::size_t __bkt = _M_bucket_index(__code); return iterator(_M_find_node(__bkt, __k, __code)); @@ -1504,6 +1524,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION find(const key_type& __k) const -> const_iterator { + if (size() <= __traits_type::__small_size_threshold::value) + { + for (auto __it = begin(); __it != end(); ++__it) + if (this->_M_key_equals(__k, __it._M_cur)) + return __it; + return end(); + } + __hash_code __code = this->_M_hash_code(__k); std::size_t __bkt = _M_bucket_index(__code); return const_iterator(_M_find_node(__bkt, __k, __code)); @@ -1619,6 +1647,34 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return nullptr; } + // Find the node before the one whose key compares equal to k. + // Return nullptr if no node is found. + template + auto + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RehashPolicy, _Traits>:: + _M_find_before_node(const key_type& __k) + -> __node_base* + { + __node_base* __prev_p = &_M_before_begin; + if (!__prev_p->_M_nxt) + return nullptr; + + for (__node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt); + __p != nullptr; + __p = __p->_M_next()) + { + if (this->_M_key_equals(__k, __p)) + return __prev_p; + + __prev_p = __p; + } + + return nullptr; + } + template @@ -1702,11 +1758,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // First build the node to get access to the hash code _Scoped_node __node { this, std::forward<_Args>(__args)... }; const key_type& __k = this->_M_extract()(__node._M_node->_M_v()); + if (size() <= __traits_type::__small_size_threshold::value) + { + for (auto __it = begin(); __it != end(); ++__it) + if (this->_M_key_equals(__k, __it._M_cur)) + // There is already an equivalent node, no insertion + return { __it, false }; + } + __hash_code __code = this->_M_hash_code(__k); 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); + if (size() > __traits_type::__small_size_threshold::value) + if (__node_type* __p = _M_find_node(__bkt, __k, __code)) + // There is already an equivalent node, no insertion + return { iterator(__p), false }; // Insert the node auto __pos = _M_insert_node(__uks, __bkt, __code, __node._M_node); @@ -1728,13 +1793,40 @@ _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); + auto __res = this->_M_compute_hash_code(__hint, __k); auto __pos - = _M_insert_node(__mks, __hint._M_cur, __code, __node._M_node); + = _M_insert_node(__mks, __res.first._M_cur, __res.second, + __node._M_node); __node._M_node = nullptr; return __pos; } + template + auto + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RehashPolicy, _Traits>:: + _M_compute_hash_code(const_iterator __hint, const key_type& __k) const + -> pair + { + if (size() <= __traits_type::__small_size_threshold::value) + { + if (__hint != cend()) + { + for (auto __it = __hint; __it != cend(); ++__it) + if (this->_M_key_equals(__k, __it._M_cur)) + return { __it, this->_M_hash_code(__it._M_cur) }; + } + + for (auto __it = cbegin(); __it != __hint; ++__it) + if (this->_M_key_equals(__k, __it._M_cur)) + return { __it, this->_M_hash_code(__it._M_cur) }; + } + + return { __hint, this->_M_hash_code(__k) }; + } + template @@ -1830,11 +1922,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION -> pair { const key_type& __k = this->_M_extract()(__v); + + if (size() <= __traits_type::__small_size_threshold::value) + for (auto __it = begin(); __it != end(); ++__it) + if (this->_M_key_equals(__k, __it._M_cur)) + return { __it, false }; + __hash_code __code = this->_M_hash_code(__k); size_type __bkt = _M_bucket_index(__code); - if (__node_type* __node = _M_find_node(__bkt, __k, __code)) - return { iterator(__node), false }; + if (size() > __traits_type::__small_size_threshold::value) + if (__node_type* __node = _M_find_node(__bkt, __k, __code)) + return { iterator(__node), false }; _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this }; auto __pos = _M_insert_node(__uks, __bkt, __code, __node._M_node); @@ -1856,13 +1955,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { // First compute the hash code so that we don't do anything if it // throws. - __hash_code __code = this->_M_hash_code(this->_M_extract()(__v)); + auto __res + = this->_M_compute_hash_code(__hint, this->_M_extract()(__v)); // Second allocate new node so that we don't rehash if it throws. _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this }; - const key_type& __k = this->_M_extract()(__node._M_node->_M_v()); auto __pos - = _M_insert_node(__mks, __hint._M_cur, __code, __node._M_node); + = _M_insert_node(__mks, __res.first._M_cur, __res.second, + __node._M_node); __node._M_node = nullptr; return __pos; } @@ -1922,16 +2022,33 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _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(__code); + __node_base* __prev_n; + __node_type* __n; + std::size_t __bkt; + if (size() <= __traits_type::__small_size_threshold::value) + { + __prev_n = _M_find_before_node(__k); + if (!__prev_n) + return 0; - // Look for the node before the first matching node. - __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code); - if (!__prev_n) - return 0; + // We found a matching node, erase it. + __n = static_cast<__node_type*>(__prev_n->_M_nxt); + __bkt = _M_bucket_index(__n); + } + else + { + __hash_code __code = this->_M_hash_code(__k); + __bkt = _M_bucket_index(__code); + + // Look for the node before the first matching node. + __prev_n = _M_find_before_node(__bkt, __k, __code); + if (!__prev_n) + return 0; + + // We found a matching node, erase it. + __n = static_cast<__node_type*>(__prev_n->_M_nxt); + } - // We found a matching node, erase it. - __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt); _M_erase(__bkt, __prev_n, __n); return 1; } @@ -1945,13 +2062,31 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _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(__code); + std::size_t __bkt; + __node_base* __prev_n; + __node_type* __n; + if (size() <= __traits_type::__small_size_threshold::value) + { + __prev_n = _M_find_before_node(__k); + if (!__prev_n) + return 0; - // Look for the node before the first matching node. - __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code); - if (!__prev_n) - return 0; + // We found a matching node, erase it. + __n = static_cast<__node_type*>(__prev_n->_M_nxt); + __bkt = _M_bucket_index(__n); + } + else + { + __hash_code __code = this->_M_hash_code(__k); + __bkt = _M_bucket_index(__code); + + // Look for the node before the first matching node. + __prev_n = _M_find_before_node(__bkt, __k, __code); + if (!__prev_n) + return 0; + + __n = static_cast<__node_type*>(__prev_n->_M_nxt); + } // _GLIBCXX_RESOLVE_LIB_DEFECTS // 526. Is it undefined if a function in the standard changes @@ -1959,7 +2094,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // We use one loop to find all matching nodes and another to deallocate // them so that the key stays valid during the first loop. It might be // invalidated indirectly when destroying nodes. - __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt); __node_type* __n_last = __n->_M_next(); while (__n_last && this->_M_node_equals(__n, __n_last)) __n_last = __n_last->_M_next(); diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index 11ea47b322e..6f329c82335 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -45,6 +45,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename _Traits> class _Hashtable; + /** + * struct _Small_size_threshold + * + * Traits like type giving the threshold below which the hashtable will be + * considered as small. + * + * @tparam _Hash The hash functor. + */ + template + struct _Small_size_threshold + : public std::integral_constant::value ? 0 : 20> + { }; + namespace __detail { /** @@ -203,13 +216,22 @@ namespace __detail * be an arbitrary number. This is true for unordered_set and * unordered_map, false for unordered_multiset and * unordered_multimap. + * + * @tparam _Small_size_threshold Integer value. Threshold below which + * hashtable will be considered as small enough to perform linear + * lookup. */ - template + template struct _Hashtable_traits { using __hash_cached = __bool_constant<_Cache_hash_code>; using __constant_iterators = __bool_constant<_Constant_iterators>; using __unique_keys = __bool_constant<_Unique_keys>; + using __small_size_threshold + = integral_constant; }; /** @@ -1039,9 +1061,11 @@ namespace __detail struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RehashPolicy, _Traits, true_type> { + private: using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RehashPolicy, _Traits>; + public: float max_load_factor() const noexcept { @@ -1189,6 +1213,10 @@ namespace __detail return _M_hash()(__k); } + __hash_code + _M_hash_code(const __node_type* __n) const + { return _M_hash_code(_M_extract()(__n->_M_v())); } + std::size_t _M_bucket_index(__hash_code __c, std::size_t __bkt_count) const { return _RangedHash{}(__c, __bkt_count); } @@ -1198,9 +1226,7 @@ namespace __detail noexcept( noexcept(declval()(declval())) && noexcept(declval()((__hash_code)0, (std::size_t)0)) ) - { - return _RangedHash{}(_M_hash()(_M_extract()(__p->_M_v())), __bkt_count); - } + { return _RangedHash{}(_M_hash_code(__p), __bkt_count); } void _M_store_code(__node_type*, __hash_code) const @@ -1268,6 +1294,10 @@ namespace __detail return _M_hash()(__k); } + __hash_code + _M_hash_code(const __node_type* __n) const + { return __n->_M_hash_code; } + std::size_t _M_bucket_index(__hash_code __c, std::size_t __bkt_count) const { return _RangedHash{}(__c, __bkt_count); } @@ -1669,21 +1699,26 @@ namespace __detail { } bool - _M_equals(const _Key& __k, __hash_code __c, const __node_type* __n) const + _M_key_equals(const _Key& __k, const __node_type* __n) const { static_assert(__is_invocable{}, "key equality predicate must be invocable with two arguments of " "key type"); + return _M_eq()(__k, this->_M_extract()(__n->_M_v())); + } + + bool + _M_equals(const _Key& __k, __hash_code __c, const __node_type* __n) const + { return _Equal_hash_code<__node_type>::_S_equals(__c, *__n) - && _M_eq()(__k, this->_M_extract()(__n->_M_v())); + && _M_key_equals(__k, __n); } bool _M_node_equals(const __node_type* __lhn, const __node_type* __rhn) const { return _Equal_hash_code<__node_type>::_S_node_equals(*__lhn, *__rhn) - && _M_eq()(this->_M_extract()(__lhn->_M_v()), - this->_M_extract()(__rhn->_M_v())); + && _M_key_equals(this->_M_extract()(__lhn->_M_v()), __rhn); } void diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h index 310cfd39d79..5265020f608 100644 --- a/libstdc++-v3/include/bits/unordered_map.h +++ b/libstdc++-v3/include/bits/unordered_map.h @@ -36,30 +36,36 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _GLIBCXX_BEGIN_NAMESPACE_CONTAINER /// Base types for unordered_map. - template - using __umap_traits = __detail::_Hashtable_traits<_Cache, false, true>; + template + using __umap_traits + = __detail::_Hashtable_traits<_Cache, false, true, + __small_size_threshold_default<_Cache, _Hash>::value>; template, typename _Pred = std::equal_to<_Key>, typename _Alloc = std::allocator >, - typename _Tr = __umap_traits<__cache_default<_Key, _Hash>::value>> + typename _Tr = __umap_traits<__cache_default<_Key, _Hash>::value, + _Hash>> using __umap_hashtable = _Hashtable<_Key, std::pair, _Alloc, __detail::_Select1st, _Pred, _Hash, __detail::_Prime_rehash_policy, _Tr>; /// Base types for unordered_multimap. - template - using __ummap_traits = __detail::_Hashtable_traits<_Cache, false, false>; + template + using __ummap_traits + = __detail::_Hashtable_traits<_Cache, false, false, + __small_size_threshold_default<_Cache, _Hash>::value>; template, typename _Pred = std::equal_to<_Key>, typename _Alloc = std::allocator >, - typename _Tr = __ummap_traits<__cache_default<_Key, _Hash>::value>> + typename _Tr = __ummap_traits<__cache_default<_Key, _Hash>::value, + _Hash>> using __ummap_hashtable = _Hashtable<_Key, std::pair, _Alloc, __detail::_Select1st, _Pred, _Hash, diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h index 4319495f18b..9bfa8639faf 100644 --- a/libstdc++-v3/include/bits/unordered_set.h +++ b/libstdc++-v3/include/bits/unordered_set.h @@ -36,27 +36,33 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _GLIBCXX_BEGIN_NAMESPACE_CONTAINER /// Base types for unordered_set. - template - using __uset_traits = __detail::_Hashtable_traits<_Cache, true, true>; + template + using __uset_traits + = __detail::_Hashtable_traits<_Cache, true, true, + __small_size_threshold_default<_Cache, _Hash>::value>; template, typename _Pred = std::equal_to<_Value>, typename _Alloc = std::allocator<_Value>, - typename _Tr = __uset_traits<__cache_default<_Value, _Hash>::value>> + typename _Tr = __uset_traits<__cache_default<_Value, _Hash>::value, + _Hash>> using __uset_hashtable = _Hashtable<_Value, _Value, _Alloc, __detail::_Identity, _Pred, _Hash, __detail::_Prime_rehash_policy, _Tr>; /// Base types for unordered_multiset. - template - using __umset_traits = __detail::_Hashtable_traits<_Cache, true, false>; + template + using __umset_traits + = __detail::_Hashtable_traits<_Cache, true, false, + __small_size_threshold_default<_Cache, _Hash>::value>; template, typename _Pred = std::equal_to<_Value>, typename _Alloc = std::allocator<_Value>, - typename _Tr = __umset_traits<__cache_default<_Value, _Hash>::value>> + typename _Tr = __umset_traits<__cache_default<_Value, _Hash>::value, + _Hash>> using __umset_hashtable = _Hashtable<_Value, _Value, _Alloc, __detail::_Identity, _Pred, _Hash, diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc b/libstdc++-v3/src/c++11/hashtable_c++0x.cc index de437d00b56..dcf8a81fc5e 100644 --- a/libstdc++-v3/src/c++11/hashtable_c++0x.cc +++ b/libstdc++-v3/src/c++11/hashtable_c++0x.cc @@ -30,6 +30,7 @@ #include #include #include +#include #include namespace std _GLIBCXX_VISIBILITY(default)