From patchwork Thu May 5 17:37:03 2022 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: 53528 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 3F728385780F for ; Thu, 5 May 2022 17:37:41 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 3F728385780F DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1651772261; bh=95goaUmg4jTZxZgHPcThwh0Q/0K77LA5drPh/WfDDAU=; h=Date:Subject:To:References:In-Reply-To:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=aKmHze9j9oa+9sN6HjllDE75dG0hng9Y4gpw4xDW1Ce6lSmdhGan4kTX99UesNqYX Qdn2mPi+NISNY2Ye7dem2WMtUWBUOx8LPx/jUnVLB9Ps2oGLBezcG/jsnE/672DE+B YgJSlbWHfaaufpRAzROqsA/ZK3mZPsIMwZZJr24E= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-ej1-x62f.google.com (mail-ej1-x62f.google.com [IPv6:2a00:1450:4864:20::62f]) by sourceware.org (Postfix) with ESMTPS id 5F39A3858D3C; Thu, 5 May 2022 17:37:10 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 5F39A3858D3C Received: by mail-ej1-x62f.google.com with SMTP id l18so10067026ejc.7; Thu, 05 May 2022 10:37:10 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:date:mime-version:user-agent:from :subject:to:cc:references:content-language:in-reply-to; bh=95goaUmg4jTZxZgHPcThwh0Q/0K77LA5drPh/WfDDAU=; b=zmp8NhxL/i9LhgejoKXfQX3wNfffGOGIjswayJmOYnjAmsXYF8yqW8O55tIZFFGB4i NjmODHX88j5D6QY79HVoucL+shorrjCcMto3ADzOlcvTzNHBzRDgmMK4VA0Vwd0cqH/l dtbZbEGDKIb2OeS1LXcyg+EAq6U9zAdheVoJewXO2ZEVFnqK1Wdyc3Xb53q5RhdBsSyR fIylaLeKGtTFDnfSDGfLXK+U00OeLym2tHKHAzBCTaVHwi9PEPDaMtKFF/dcFHHStTZA ySsn1CF77CDDB/kCLngPZkyEGqm/1yvfN+Ri+nkVC99zv27V1kQc+mPPUCpNDm0DzmU3 I9Bw== X-Gm-Message-State: AOAM532BIC5/rZOF8Vey+ngiYrPURyTzxe6uDMH9fuSuale3Lj0DM8Hs +DuqyN0KSEAKv85hOhtdY+0DiKdI6Hk= X-Google-Smtp-Source: ABdhPJzW/XcM9/0/lOTjKsQX8yiaAQMp1z950vzeqskhBLj38C+lXT5IIeNbD4jkVOX7Fyv64fCeHg== X-Received: by 2002:a17:906:4fd5:b0:6f4:2704:1edf with SMTP id i21-20020a1709064fd500b006f427041edfmr25552633ejw.136.1651772228436; Thu, 05 May 2022 10:37:08 -0700 (PDT) Received: from [10.24.4.57] ([109.190.253.11]) by smtp.googlemail.com with ESMTPSA id w1-20020a1709064a0100b006f3ef214db4sm987691eju.26.2022.05.05.10.37.04 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 05 May 2022 10:37:07 -0700 (PDT) Message-ID: Date: Thu, 5 May 2022 19:37:03 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.8.1 Subject: [PATCH][_Hashtable] Fix insertion of range of type convertible to value_type PR 56112 To: "libstdc++@gcc.gnu.org" References: <2fe3937d-1b9a-a547-bb41-225d3d5426a2@gmail.com> Content-Language: en-US In-Reply-To: <2fe3937d-1b9a-a547-bb41-225d3d5426a2@gmail.com> X-Spam-Status: No, score=-8.4 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, RCVD_IN_BARRACUDACENTRAL, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: =?utf-8?q?Fran=C3=A7ois_Dumont_via_Gcc-patches?= From: =?utf-8?q?Fran=C3=A7ois_Dumont?= Reply-To: =?utf-8?q?Fran=C3=A7ois_Dumont?= Cc: gcc-patches Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" Hi Renewing my patch to fix PR 56112 but for the insert methods, I totally change it, now works also with move-only key types. I let you Jonathan find a better name than _ValueTypeEnforcer as usual :-) libstdc++: [_Hashtable] Insert range of types convertible to value_type PR 56112 Fix insertion of range of types convertible to value_type. Fix also when this value_type has a move-only key_type which also allow converted values to be moved. libstdc++-v3/ChangeLog:         PR libstdc++/56112         * include/bits/hashtable_policy.h (_ValueTypeEnforcer): New.         * include/bits/hashtable.h (_Hashtable<>::_M_insert_unique_aux): New.         (_Hashtable<>::_M_insert(_Arg&&, const _NodeGenerator&, true_type)): Use latters.         (_Hashtable<>::_M_insert(_Arg&&, const _NodeGenerator&, false_type)): Likewise.         (_Hashtable(_InputIterator, _InputIterator, size_type, const _Hash&, const _Equal&,         const allocator_type&, true_type)): Use this.insert range.         (_Hashtable(_InputIterator, _InputIterator, size_type, const _Hash&, const _Equal&,         const allocator_type&, false_type)): Use _M_insert.         * testsuite/23_containers/unordered_map/cons/56112.cc: Check how many times conversion         is done.         (test02): New test case.         * testsuite/23_containers/unordered_set/cons/56112.cc: New test. Tested under Linux x86_64. Ok to commit ? François diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 5e1a417f7cd..cd42d3c9ba0 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -898,21 +898,33 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template std::pair - _M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen, - true_type /* __uks */) + _M_insert_unique_aux(_Arg&& __arg, const _NodeGenerator& __node_gen) { return _M_insert_unique( _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))), std::forward<_Arg>(__arg), __node_gen); } + template + std::pair + _M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen, + true_type /* __uks */) + { + using __to_value + = __detail::_ValueTypeEnforcer<_ExtractKey, value_type>; + return _M_insert_unique_aux( + __to_value{}(std::forward<_Arg>(__arg)), __node_gen); + } + template iterator _M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen, false_type __uks) { - return _M_insert(cend(), std::forward<_Arg>(__arg), __node_gen, - __uks); + using __to_value + = __detail::_ValueTypeEnforcer<_ExtractKey, value_type>; + return _M_insert(cend(), + __to_value{}(std::forward<_Arg>(__arg)), __node_gen, __uks); } // Insert with hint, not used when keys are unique. @@ -1184,10 +1196,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION const _Hash& __h, const _Equal& __eq, const allocator_type& __a, true_type /* __uks */) : _Hashtable(__bkt_count_hint, __h, __eq, __a) - { - for (; __f != __l; ++__f) - this->insert(*__f); - } + { this->insert(__f, __l); } templateinsert(*__f); + _M_insert(*__f, __node_gen, __uks); } template(__x).first; } }; + template + struct _ValueTypeEnforcer; + + template + struct _ValueTypeEnforcer<_Identity, _Value> + { + template + constexpr _Kt&& + operator()(_Kt&& __k) noexcept + { return std::forward<_Kt>(__k); } + }; + + template + struct _ValueTypeEnforcer<_Select1st, _Value> + { + constexpr _Value&& + operator()(_Value&& __x) noexcept + { return std::move(__x); } + + constexpr const _Value& + operator()(const _Value& __x) noexcept + { return __x; } + + using __fst_type = typename _Value::first_type; + + template + using __mutable_value_t = + std::pair< + typename std::remove_const::type, + typename _Pair::second_type>; + + constexpr __enable_if_t::value, + __mutable_value_t<_Value>&&> + operator()(__mutable_value_t<_Value>&& __x) noexcept + { return std::move(__x); } + + constexpr __enable_if_t::value, + const __mutable_value_t<_Value>&> + operator()(const __mutable_value_t<_Value>& __x) noexcept + { return __x; } + + template + constexpr std::pair<_Kt, _Val>&& + operator()(std::pair<_Kt, _Val>&& __x) noexcept + { return std::move(__x); } + + template + constexpr const std::pair<_Kt, _Val>& + operator()(const std::pair<_Kt, _Val>& __x) noexcept + { return __x; } + }; + template struct _NodeBuilder; diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/cons/56112.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/cons/56112.cc index c4cdeee234c..4476103c986 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_map/cons/56112.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/cons/56112.cc @@ -20,30 +20,108 @@ #include #include +#include + struct Key { explicit Key(const int* p) : value(p) { } ~Key() { value = nullptr; } - bool operator==(const Key& k) const { return *value == *k.value; } + bool operator==(const Key& k) const + { return *value == *k.value; } const int* value; }; struct hash { - std::size_t operator()(const Key& k) const noexcept { return *k.value; } + std::size_t operator()(const Key& k) const noexcept + { return *k.value; } }; struct S { + static int _count; + int value; - operator std::pair() const { return {Key(&value), value}; } + operator std::pair() const + { + ++_count; + return { Key(&value), value }; + } }; -int main() +int S::_count = 0; + +void test01() { S s[1] = { {2} }; - std::unordered_map m(s, s+1); - std::unordered_multimap mm(s, s+1); + std::unordered_map m(s, s + 1); + VERIFY( S::_count == 1 ); + + std::unordered_multimap mm(s, s + 1); + VERIFY( S::_count == 2 ); + + m.insert(s, s + 1); + VERIFY( S::_count == 3 ); + + mm.insert(s, s + 1); + VERIFY( S::_count == 4 ); +} + +struct MoveOnlyKey +{ + explicit MoveOnlyKey(const int* p) : value(p) { } + MoveOnlyKey(const MoveOnlyKey&) = delete; + MoveOnlyKey(MoveOnlyKey&& k) : value(k.value) + { k.value = nullptr; } + ~MoveOnlyKey() { value = nullptr; } + + bool operator==(const MoveOnlyKey& k) const + { return *value == *k.value; } + + const int* value; +}; + +struct MoveOnlyKeyHash +{ + std::size_t operator()(const MoveOnlyKey& k) const noexcept + { return *k.value; } +}; + +struct S2 +{ + static int _count; + + int value; + operator std::pair() const + { + ++_count; + return { MoveOnlyKey(&value), value }; + } +}; + +int S2::_count = 0; + +void test02() +{ + S2 s[1] = { {2} }; + std::unordered_map m(s, s + 1); + VERIFY( S2::_count == 1 ); + + std::unordered_multimap mm(s, s + 1); + VERIFY( S2::_count == 2 ); + + m.insert(s, s + 1); + VERIFY( S2::_count == 3 ); + + mm.insert(s, s + 1); + VERIFY( S2::_count == 4 ); +} + +int main() +{ + test01(); + test02(); + return 0; } diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/cons/56112.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/cons/56112.cc new file mode 100644 index 00000000000..c55965a2caa --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/cons/56112.cc @@ -0,0 +1,70 @@ +// { dg-do run { target c++11 } } + +// Copyright (C) 2022 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 +// . + +#include +#include + +#include + +struct Key +{ + explicit Key(const int* p) : value(p) { } + ~Key() { value = nullptr; } + + bool operator==(const Key& k) const + { return *value == *k.value; } + + const int* value; +}; + +struct hash +{ + std::size_t operator()(const Key& k) const noexcept + { return *k.value; } +}; + +struct S +{ + static int _count; + + int value; + operator Key() const + { + ++_count; + return Key(&value); + } +}; + +int S::_count = 0; + +int main() +{ + S s[1] = { {2} }; + std::unordered_set m(s, s + 1); + VERIFY( S::_count == 1 ); + + std::unordered_multiset mm(s, s + 1); + VERIFY( S::_count == 2 ); + + m.insert(s, s + 1); + VERIFY( S::_count == 3 ); + + mm.insert(s, s + 1); + VERIFY( S::_count == 4 ); +}