From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wr1-x441.google.com (mail-wr1-x441.google.com [IPv6:2a00:1450:4864:20::441]) by sourceware.org (Postfix) with ESMTPS id 9865F3857C49; Sat, 24 Oct 2020 14:25:38 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 9865F3857C49 Received: by mail-wr1-x441.google.com with SMTP id s9so6119554wro.8; Sat, 24 Oct 2020 07:25:38 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:from:to:references:message-id:date :user-agent:mime-version:in-reply-to:content-language; bh=3OVCqOxmTkVmeRjJKq0gez0zzRXS+cq3f+hLPai7Icc=; b=GKC33Ur24J7Nal9/yRBGNwiV11j6aJPRpq094kDRB1tPiiOiJC6nuGc7ysYuEekZyW iqCSfJgnTgrQkrt2aMNC2WjzqVOscD7qcUic1n3snHwd4BzUYhOaP69omHu6MxtGLV5z vvQWMKdpiy2M8iLHlnnqXKiOknMoM+aMOYFFC7wODk05/myqz2ukbnBFN+md/2YK7/io bbmGkIbOjbRFVMUWaHQGgwju2GD/JOcnrUKCItxnDrsXZkRK1Dmeqj6xSMEnCOvvWSyX o6018mVRWi/q0wZ7S9kTzyemPCEosrpG8s+M/giOFr+thbswyW2/l+7eoU+jl3dQ8kfQ kaYg== X-Gm-Message-State: AOAM533fsMsyMuS/lapFhRU3VfTEdlEehTfwUHwnsOzMfTQDmuk0qsEz wq5Jl3pV+F4q9ZRMbz2gSkwm5eZZ1v4= X-Google-Smtp-Source: ABdhPJxPXroSp9rVDqDl/J8Ph7wCUbSo++BxyyjYo2YrGfRSCvmV/cBgihYznZGijwhrXkudlo3vhA== X-Received: by 2002:adf:f4ca:: with SMTP id h10mr7699034wrp.89.1603549537141; Sat, 24 Oct 2020 07:25:37 -0700 (PDT) Received: from ?IPv6:2a01:e0a:1dc:b1c0:91d2:d31:eb0:5479? ([2a01:e0a:1dc:b1c0:91d2:d31:eb0:5479]) by smtp.googlemail.com with ESMTPSA id 205sm10981659wme.38.2020.10.24.07.25.32 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Sat, 24 Oct 2020 07:25:33 -0700 (PDT) Subject: Re: [PATCH] Hashtable PR96088 From: =?UTF-8?Q?Fran=c3=a7ois_Dumont?= To: "libstdc++@gcc.gnu.org" , gcc-patches References: <5b198dd5-cb89-91a0-9070-13927ac263a4@gmail.com> <524e2eee-a4ee-a05e-087f-6000c8274eff@gmail.com> Message-ID: <21854fd0-ad6b-1eaa-adaa-2074421fc107@gmail.com> Date: Sat, 24 Oct 2020 16:25:32 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.10.0 MIME-Version: 1.0 In-Reply-To: <524e2eee-a4ee-a05e-087f-6000c8274eff@gmail.com> Content-Type: multipart/mixed; boundary="------------61FDB39B77BECB162C93005A" Content-Language: fr X-Spam-Status: No, score=-9.9 required=5.0 tests=BAYES_00, BODY_8BITS, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, KAM_NUMSUBJECT, KAM_SHORT, NICE_REPLY_A, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: libstdc++@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++ mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 24 Oct 2020 14:25:42 -0000 This is a multi-part message in MIME format. --------------61FDB39B77BECB162C93005A Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Hi     Just a rebase of this patch. François On 17/10/20 6:21 pm, François Dumont wrote: > I eventually would like to propose the following resolution. > > For multi-key containers I kept the same resolution build the node > first and compute has code from the node key. > > For unique-key ones I change behavior when I can't find out hash > functor argument type. I am rather using the iterator key type and > just hope that the user's functors are prepared for it. > > For now I am using functor argument_type which is deprecated. I just > hope that the day we remove it we will have a compiler built-in to get > any functor argument type given an input type. > >     libstdc++: Limit allocation on iterator insertion in Hashtable [PR > 96088] > >     Detect Hash functor argument type to find out if it is different > to the >     container key_type and if a temporary instance needs to be > generated to invoke >     the functor from the iterator value_type key part. If this > temporary generation >     can throw a key_type instance is generated at Hashtable level and > use to call >     the functors and, if needed, move it to the storage. > >     libstdc++-v3/ChangeLog: > >             PR libstdc++/96088 >             * include/bits/hashtable_policy.h (_Select2nd): New. >             (_NodeBuilder<>): New. >             (_ReuseOrAllocNode<>::operator()): Use varriadic template > args. >             (_AllocNode<>::operator()): Likewise. >             (_Hash_code_base<>::_M_hash_code): Add _KType template > parameter. >             (_Hashtable_base<>::_M_equals): Add _KType template > parameter. >             * include/bits/hashtable.h >             (_Hashtable<>::__node_builder_t): New. >             (_Hashtable<>::_M_find_before_node): Add _KType template > parameter. >             (_Hashtable<>::_M_find_node): Likewise. >             (_Hashtable<>::_Hash_arg_t): New. >             (_Hashtable<>::_S_forward_key): New. > (_Hashtable<>::_M_insert_unique<>(_KType&&, _Arg&&, const > _NodeGenerator&)): >              New. >             (_Hashtable<>::_M_insert): Use latter. >             * testsuite/23_containers/unordered_map/96088.cc: New test. >             * testsuite/23_containers/unordered_multimap/96088.cc: New > test. >             * testsuite/23_containers/unordered_multiset/96088.cc: New > test. >             * testsuite/23_containers/unordered_set/96088.cc: New test. >             * testsuite/util/replacement_memory_operators.h >             (counter::_M_increment): New. >             (counter::_M_decrement): New. >             (counter::reset()): New. > > Tested under Linux x86_64. > > Ok to commit ? > > François > > On 01/09/20 2:36 pm, François Dumont wrote: >> Hi >> >>     I started working on PR96088 problem in Hashtable implementation. >> >>     In the case of multi-key containers the problem is easy to >> manage. Now that we have _Scoped_node we can easily allocate the node >> first and then extract the key from it to compute hash code. It is >> quite safe as computating a hash code is rarely going to throw >> especially if there is no allocation anymore to invoke the hasher. >> >>     In the unique-key case it is more tricky. First I only consider >> the hasher invocation, the equal_to shall be consistent with it. My >> approach is to consider that if the operation needed transform the >> inserted element key part into the hasher argument can throw then I >> better generate a key_type instance myself and move it to the node if >> it is eventually to be inserted. Note that any allocation needed to >> call the hasher from the key_type is user fault. >> >>     Of course the tricky part here is to find out what is the hasher >> argument_type. For the moment I support hasher with a nested >> argument_type typedef and function pointer. But, as pointed out by >> the tests which are failing for the moment I am missing the support >> for a classic functor. I am pretty sure that if I support it I will >> still be missing some use cases (like std::function). So I am looking >> for help on how to determine it. Or maybe the whole approach it wrong ? >> >> For now I am still working on it, thanks, >> >> François >> > --------------61FDB39B77BECB162C93005A Content-Type: text/x-patch; charset=UTF-8; name="pr96088.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="pr96088.patch" diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 6c6c5edde0b..234b40c13b7 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -274,6 +274,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __detail::_ReuseOrAllocNode<__node_alloc_type>; using __alloc_node_gen_t = __detail::_AllocNode<__node_alloc_type>; + using __node_builder_t = + __detail::_NodeBuilder<_ExtractKey>; // Simple RAII type for managing a node containing an element struct _Scoped_node @@ -736,18 +738,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Find and insert helper functions and types // Find the node before the one matching the criteria. - __node_base_ptr - _M_find_before_node(size_type, const key_type&, __hash_code) const; - - __node_ptr - _M_find_node(size_type __bkt, const key_type& __key, - __hash_code __c) const - { - __node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c); - if (__before_n) - return static_cast<__node_ptr>(__before_n->_M_nxt); - return nullptr; - } + template + __node_base_ptr + _M_find_before_node(size_type, const _KType&, __hash_code) const; + + template + __node_ptr + _M_find_node(size_type __bkt, const _KType& __key, + __hash_code __c) const + { + __node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c); + if (__before_n) + return static_cast<__node_ptr>(__before_n->_M_nxt); + return nullptr; + } // Insert a node at the beginning of a bucket. void @@ -794,9 +798,53 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION iterator _M_emplace(const_iterator, false_type __uks, _Args&&... __args); + template + std::pair + _M_insert_unique(_KType&&, _Arg&&, const _NodeGenerator&); + + // Detect nested argument_type. + template> + struct _Hash_arg_t + { typedef _KType argument_type; }; + + // Nested argument_type. + template + struct _Hash_arg_t<_KType, _Tp, + __void_t> + { typedef typename _Tp::argument_type argument_type; }; + + // Function pointer. + template + struct _Hash_arg_t<_KType, std::size_t(*)(const _Arg&)> + { typedef _Arg argument_type; }; + + template::argument_type> + static typename conditional< + __is_nothrow_convertible<_KType, _ArgType>::value, + _KType&&, + key_type>::type + _S_forward_key(_KType&& __k) + { return std::forward<_KType>(__k); } + + static const key_type& + _S_forward_key(const key_type& __k) + { return __k; } + + static key_type&& + _S_forward_key(key_type&& __k) + { return std::move(__k); } + template std::pair - _M_insert(_Arg&&, const _NodeGenerator&, true_type __uks); + _M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen, + true_type /* __uks */) + { + return _M_insert_unique( + _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))), + std::forward<_Arg>(__arg), __node_gen); + } template iterator @@ -1621,30 +1669,31 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename _ExtractKey, typename _Equal, typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> - auto - _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_find_before_node(size_type __bkt, const key_type& __k, - __hash_code __code) const - -> __node_base_ptr - { - __node_base_ptr __prev_p = _M_buckets[__bkt]; - if (!__prev_p) - return nullptr; + template + auto + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_find_before_node(size_type __bkt, const _KType& __k, + __hash_code __code) const + -> __node_base_ptr + { + __node_base_ptr __prev_p = _M_buckets[__bkt]; + if (!__prev_p) + return nullptr; - for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);; - __p = __p->_M_next()) - { - if (this->_M_equals(__k, __code, *__p)) - return __prev_p; + for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);; + __p = __p->_M_next()) + { + if (this->_M_equals(__k, __code, *__p)) + return __prev_p; - if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt) - break; - __prev_p = __p; - } + if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt) + break; + __prev_p = __p; + } - return nullptr; - } + return nullptr; + } template - template + template auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen, - true_type /* __uks */) + _M_insert_unique(_KType&& __k, _Arg&& __v, + const _NodeGenerator& __node_gen) -> pair { - const key_type& __k = _ExtractKey{}(__v); __hash_code __code = this->_M_hash_code(__k); size_type __bkt = _M_bucket_index(__code); if (__node_ptr __node = _M_find_node(__bkt, __k, __code)) return { iterator(__node), false }; - _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this }; + _Scoped_node __node { + __node_builder_t::_S_build(std::forward<_KType>(__k), + std::forward<_Arg>(__v), + __node_gen), + this + }; auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node); __node._M_node = nullptr; @@ -1894,12 +1947,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION false_type /* __uks */) -> iterator { - // First compute the hash code so that we don't do anything if it - // throws. - __hash_code __code = this->_M_hash_code(_ExtractKey{}(__v)); - - // Second allocate new node so that we don't rehash if it throws. + // First allocate new node so that we don't do anything if it throws. _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this }; + + // Second compute the hash code so that we don't rehash if it throws. + __hash_code __code + = this->_M_hash_code(_ExtractKey{}(__node._M_node->_M_v())); + auto __pos = _M_insert_multi_node(__hint._M_cur, __code, __node._M_node); __node._M_node = nullptr; diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index f5ce7209957..378f800ab9e 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -94,6 +94,48 @@ namespace __detail { return std::get<0>(std::forward<_Tp>(__x)); } }; + struct _Select2nd + { + template + auto + operator()(_Tp&& __x) const noexcept + -> decltype(std::get<1>(std::forward<_Tp>(__x))) + { return std::get<1>(std::forward<_Tp>(__x)); } + }; + + template + struct _NodeBuilder; + + template<> + struct _NodeBuilder<_Select1st> + { + template + static auto + _S_build(_KType&& __k, _Arg&& __arg, + const _NodeGenerator& __node_gen) + -> decltype(__node_gen(std::piecewise_construct, + std::forward_as_tuple(std::forward<_KType>(__k)), + std::forward_as_tuple(_Select2nd{}( + std::forward<_Arg>(__arg))))) + { + return __node_gen(std::piecewise_construct, + std::forward_as_tuple(std::forward<_KType>(__k)), + std::forward_as_tuple(_Select2nd{}( + std::forward<_Arg>(__arg)))); + } + }; + + template<> + struct _NodeBuilder<_Identity> + { + template + static auto + _S_build(_KType&& __k, _Arg&&, + const _NodeGenerator& __node_gen) + -> decltype(__node_gen(std::forward<_KType>(__k))) + { return __node_gen(std::forward<_KType>(__k)); } + }; + template struct _Hashtable_alloc; @@ -117,9 +159,9 @@ namespace __detail ~_ReuseOrAllocNode() { _M_h._M_deallocate_nodes(_M_nodes); } - template + template __node_type* - operator()(_Arg&& __arg) const + operator()(_Args&&... __args) const { if (_M_nodes) { @@ -131,7 +173,7 @@ namespace __detail __try { __node_alloc_traits::construct(__a, __node->_M_valptr(), - std::forward<_Arg>(__arg)); + std::forward<_Args>(__args)...); } __catch(...) { @@ -140,7 +182,7 @@ namespace __detail } return __node; } - return _M_h._M_allocate_node(std::forward<_Arg>(__arg)); + return _M_h._M_allocate_node(std::forward<_Args>(__args)...); } private: @@ -161,10 +203,10 @@ namespace __detail _AllocNode(__hashtable_alloc& __h) : _M_h(__h) { } - template + template __node_type* - operator()(_Arg&& __arg) const - { return _M_h._M_allocate_node(std::forward<_Arg>(__arg)); } + operator()(_Args&&... __args) const + { return _M_h._M_allocate_node(std::forward<_Args>(__args)...); } private: __hashtable_alloc& _M_h; @@ -1211,13 +1253,14 @@ namespace __detail _Hash_code_base() = default; _Hash_code_base(const _Hash& __hash) : __ebo_hash(__hash) { } - __hash_code - _M_hash_code(const _Key& __k) const - { - static_assert(__is_invocable{}, + template + __hash_code + _M_hash_code(const _KType& __k) const + { + static_assert(__is_invocable{}, "hash function must be invocable with an argument of key type"); - return _M_hash()(__k); - } + return _M_hash()(__k); + } std::size_t _M_bucket_index(__hash_code __c, std::size_t __bkt_count) const @@ -1597,15 +1640,18 @@ namespace __detail : __hash_code_base(__hash), _EqualEBO(__eq) { } - bool - _M_equals(const _Key& __k, __hash_code __c, - const _Hash_node_value<_Value, __hash_cached::value>& __n) const - { - static_assert(__is_invocable{}, - "key equality predicate must be invocable with two arguments of " - "key type"); - return _S_equals(__c, __n) && _M_eq()(__k, _ExtractKey{}(__n._M_v())); - } + template + bool + _M_equals(const _KType& __k, __hash_code __c, + const _Hash_node_value<_Value, + __hash_cached::value>& __n) const + { + static_assert( + __is_invocable{}, + "key equality predicate must be invocable with two arguments of " + "key type"); + return _S_equals(__c, __n) && _M_eq()(__k, _ExtractKey{}(__n._M_v())); + } bool _M_node_equals( diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/96088.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/96088.cc new file mode 100644 index 00000000000..4d399353120 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/96088.cc @@ -0,0 +1,240 @@ +// { dg-do run { target c++11 } } + +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// libstdc++/96088 + +#include +#include +#include +#include + +#include +#include + +static constexpr std::initializer_list> lst = { + {"long_str_for_dynamic_allocating", 1} +}; + +void +test01() +{ + __gnu_test::counter::reset(); + std::unordered_map um; + um.insert(lst.begin(), lst.end()); + VERIFY( um.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); + + um.insert(lst.begin(), lst.end()); + VERIFY( um.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 4 ); +} + +void +test02() +{ + __gnu_test::counter::reset(); + std::unordered_map, + std::equal_to> um; + um.insert(lst.begin(), lst.end()); + VERIFY( um.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); + + um.insert(lst.begin(), lst.end()); + VERIFY( um.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); +} + +std::size_t +hash_string_f(const std::string& str) +{ + std::hash h; + return h(str); +} + +void +test11() +{ + typedef std::size_t (*hash_string_t)(const std::string&); + __gnu_test::counter::reset(); + hash_string_t hasher = &hash_string_f; + std::unordered_map> um(0, hasher); + um.insert(lst.begin(), lst.end()); + VERIFY( um.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); + + um.insert(lst.begin(), lst.end()); + VERIFY( um.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 4 ); +} + +std::size_t +hash_string_view_f(const std::string_view& str) +{ + std::hash h; + return h(str); +} + +void +test12() +{ + typedef std::size_t (*hash_stringview_t)(const std::string_view&); + __gnu_test::counter::reset(); + hash_stringview_t hasher = &hash_string_view_f; + std::unordered_map> um(0, hasher); + um.insert(lst.begin(), lst.end()); + VERIFY( um.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); + + um.insert(lst.begin(), lst.end()); + VERIFY( um.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); +} + +struct hash_string_functor +{ + std::size_t + operator()(const std::string& str) const noexcept + { + std::hash h; + return h(str); + } +}; + +void +test21() +{ + __gnu_test::counter::reset(); + std::unordered_map> um; + um.insert(lst.begin(), lst.end()); + VERIFY( um.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 4 ); + + um.insert(lst.begin(), lst.end()); + VERIFY( um.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 6 ); +} + +struct hash_string_view_functor +{ + std::size_t + operator()(const std::string_view& str) const noexcept + { + std::hash h; + return h(str); + } +}; + +void +test22() +{ + __gnu_test::counter::reset(); + std::unordered_map> um; + um.insert(lst.begin(), lst.end()); + VERIFY( um.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); + + um.insert(lst.begin(), lst.end()); + VERIFY( um.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); +} + +void +test03() +{ + std::vector> v; + v.insert(v.end(), lst.begin(), lst.end()); + + auto __offset = __gnu_test::counter::count(); + { + __gnu_test::counter::reset(); + std::unordered_map, + std::equal_to> um; + um.insert(v.begin(), v.end()); + VERIFY( um.size() == 1 ); + + VERIFY( __gnu_test::counter::count() - __offset == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); + + um.insert(v.begin(), v.end()); + VERIFY( um.size() == 1 ); + + VERIFY( __gnu_test::counter::count() - __offset == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); + } + + { + __gnu_test::counter::reset(); + std::unordered_map, + std::equal_to> um; + um.insert(std::make_move_iterator(v.begin()), + std::make_move_iterator(v.end())); + VERIFY( um.size() == 1 ); + + VERIFY( __gnu_test::counter::count() - __offset == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 2 ); + } +} + +int +main() +{ + test01(); + test02(); + test11(); + test12(); + test21(); + test22(); + test03(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/96088.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/96088.cc new file mode 100644 index 00000000000..ffc98e25540 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/96088.cc @@ -0,0 +1,65 @@ +// { dg-do run { target c++17 } } + +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// libstdc++/96088 + +#include +#include +#include + +#include +#include + +static constexpr std::initializer_list> lst = { + {"long_str_for_dynamic_allocating", 1} +}; + +void +test01() +{ + __gnu_test::counter::reset(); + std::unordered_multimap, + std::equal_to> foo; + foo.insert(lst.begin(), lst.end()); + VERIFY( foo.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); +} + +void +test02() +{ + __gnu_test::counter::reset(); + std::unordered_multimap foo; + foo.insert(lst.begin(), lst.end()); + VERIFY( foo.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); +} + +int +main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/96088.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/96088.cc new file mode 100644 index 00000000000..4951b100a54 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/96088.cc @@ -0,0 +1,65 @@ +// { dg-do run { target c++17 } } + +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// libstdc++/96088 + +#include +#include +#include + +#include +#include + +static constexpr std::initializer_list lst = { + "long_str_for_dynamic_allocating" +}; + +void +test01() +{ + __gnu_test::counter::reset(); + std::unordered_multiset, + std::equal_to> foo; + foo.insert(lst.begin(), lst.end()); + VERIFY( foo.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); +} + +void +test02() +{ + __gnu_test::counter::reset(); + std::unordered_multiset foo; + foo.insert(lst.begin(), lst.end()); + VERIFY( foo.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); +} + +int +main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc new file mode 100644 index 00000000000..da4794cfb22 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc @@ -0,0 +1,240 @@ +// { dg-do run { target c++11 } } + +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// libstdc++/96088 + +#include +#include +#include +#include + +#include +#include + +static constexpr std::initializer_list lst = { + "long_str_for_dynamic_allocating" +}; + +void +test01() +{ + __gnu_test::counter::reset(); + std::unordered_set us; + us.insert(lst.begin(), lst.end()); + VERIFY( us.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); + + us.insert(lst.begin(), lst.end()); + VERIFY( us.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 4 ); +} + +void +test02() +{ + __gnu_test::counter::reset(); + std::unordered_set, + std::equal_to> us; + us.insert(lst.begin(), lst.end()); + VERIFY( us.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); + + us.insert(lst.begin(), lst.end()); + VERIFY( us.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); +} + +std::size_t +hash_string_f(const std::string& str) +{ + std::hash h; + return h(str); +} + +void +test11() +{ + typedef std::size_t (*hash_string_t)(const std::string&); + __gnu_test::counter::reset(); + hash_string_t hasher = &hash_string_f; + std::unordered_set> us(0, hasher); + us.insert(lst.begin(), lst.end()); + VERIFY( us.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); + + us.insert(lst.begin(), lst.end()); + VERIFY( us.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 4 ); +} + +std::size_t +hash_string_view_f(const std::string_view& str) +{ + std::hash h; + return h(str); +} + +void +test12() +{ + typedef std::size_t (*hash_stringview_t)(const std::string_view&); + __gnu_test::counter::reset(); + hash_stringview_t hasher = &hash_string_view_f; + std::unordered_set> us(0, hasher); + us.insert(lst.begin(), lst.end()); + VERIFY( us.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); + + us.insert(lst.begin(), lst.end()); + VERIFY( us.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); +} + +struct hash_string_functor +{ + std::size_t + operator()(const std::string& str) const noexcept + { + std::hash h; + return h(str); + } +}; + +void +test21() +{ + __gnu_test::counter::reset(); + std::unordered_set> us; + us.insert(lst.begin(), lst.end()); + VERIFY( us.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 4 ); + + us.insert(lst.begin(), lst.end()); + VERIFY( us.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 6 ); +} + +struct hash_string_view_functor +{ + std::size_t + operator()(const std::string_view& str) const noexcept + { + std::hash h; + return h(str); + } +}; + +void +test22() +{ + __gnu_test::counter::reset(); + std::unordered_set> us; + us.insert(lst.begin(), lst.end()); + VERIFY( us.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); + + us.insert(lst.begin(), lst.end()); + VERIFY( us.size() == 1 ); + + VERIFY( __gnu_test::counter::count() == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); +} + +void +test03() +{ + std::vector v; + v.insert(v.end(), lst.begin(), lst.end()); + + auto __offset = __gnu_test::counter::count(); + { + __gnu_test::counter::reset(); + std::unordered_set, + std::equal_to> us; + us.insert(v.begin(), v.end()); + VERIFY( us.size() == 1 ); + + VERIFY( __gnu_test::counter::count() - __offset == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); + + us.insert(v.begin(), v.end()); + VERIFY( us.size() == 1 ); + + VERIFY( __gnu_test::counter::count() - __offset == 3 ); + VERIFY( __gnu_test::counter::get()._M_increments == 3 ); + } + + { + __gnu_test::counter::reset(); + std::unordered_set, + std::equal_to> us; + us.insert(std::make_move_iterator(v.begin()), + std::make_move_iterator(v.end())); + VERIFY( us.size() == 1 ); + + VERIFY( __gnu_test::counter::count() - __offset == 2 ); + VERIFY( __gnu_test::counter::get()._M_increments == 2 ); + } +} + +int +main() +{ + test01(); + test02(); + test11(); + test12(); + test21(); + test22(); + test03(); + return 0; +} diff --git a/libstdc++-v3/testsuite/util/replacement_memory_operators.h b/libstdc++-v3/testsuite/util/replacement_memory_operators.h index a90ffd47524..a76962ebedd 100644 --- a/libstdc++-v3/testsuite/util/replacement_memory_operators.h +++ b/libstdc++-v3/testsuite/util/replacement_memory_operators.h @@ -29,6 +29,7 @@ namespace __gnu_test struct counter { std::size_t _M_count; + std::size_t _M_increments, _M_decrements; bool _M_throw; counter() : _M_count(0), _M_throw(true) { } @@ -40,10 +41,20 @@ namespace __gnu_test } static void - increment() { get()._M_count++; } + increment() + { + counter& cntr = get(); + cntr._M_count++; + cntr._M_increments++; + } static void - decrement() { get()._M_count--; } + decrement() + { + counter& cntr = get(); + cntr._M_count--; + cntr._M_decrements++; + } static counter& get() @@ -57,6 +68,13 @@ namespace __gnu_test static void exceptions(bool __b) { get()._M_throw = __b; } + + static void + reset() + { + counter& cntr = get(); + cntr._M_increments = cntr._M_decrements = 0; + } }; template --------------61FDB39B77BECB162C93005A--