From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTP id 3755B3858D3C for ; Thu, 14 Oct 2021 08:24:03 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 3755B3858D3C Received: from mail-vk1-f199.google.com (mail-vk1-f199.google.com [209.85.221.199]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-466-6qRDccLyNeS_5ns4TKJqMQ-1; Thu, 14 Oct 2021 04:24:01 -0400 X-MC-Unique: 6qRDccLyNeS_5ns4TKJqMQ-1 Received: by mail-vk1-f199.google.com with SMTP id e136-20020a1f1e8e000000b0029be9174364so2063978vke.12 for ; Thu, 14 Oct 2021 01:24:01 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=5AA1R7TaBPk9CQJmn+3D82s9bSc59aGHzB+7/85zRAM=; b=eNVDppuGf1ChK9eGz9j/mTf9zz+K3t8NAMozQosMqnAEi2AIUKFyPRfJ7sCz0isKOr /cB5Q4C2J9Y5543TRkWSnGAnHvQROzhEi5yr7Gj+HfRPxMvocDHpbxYtFz1N1NFQYyig vDcCVqVTCnkEPMAQSV+IvQOw2+Sl/XvoIDTv6Ccw7x+nTcdqy1WzIgJJSX3P3qV8hCbz Y0+Ps0f243hfNfOnPxysvJ/yccEBMFnBC42hrL0++60itSJjz1K8SzSeO5haZ/GH8z3s +49M1crB8XAZFYcbd+kYCiwPdmb/oK4nC5hRxSTL5R3F9pfb+VLJy1u+pTtryVOyw5ol V0Tw== X-Gm-Message-State: AOAM532io82hfEulmYfiYy1sgRau5jstKDxBis9TqMdKmBvoM8dC95nW Jdi6FoAFYrb3yoGxeX1EWLXl3rDwCCMJ9vfOFECPRfYxmpKHW6Uo0frafeV4xi85vPRfvJRjJ5R qClZEswXM50Niod7KcQ/em9t49AprPvnPSg== X-Received: by 2002:a9f:3399:: with SMTP id p25mr4757828uab.24.1634199841272; Thu, 14 Oct 2021 01:24:01 -0700 (PDT) X-Google-Smtp-Source: ABdhPJxEui3FGoOdCVHeUdZK7KLxschNgEKV3Ue5fDo9VrakIMnTraX8xZ19YS2QjEdKVJcyTHWlm1X2nQasET3I0l8= X-Received: by 2002:a9f:3399:: with SMTP id p25mr4757815uab.24.1634199841075; Thu, 14 Oct 2021 01:24:01 -0700 (PDT) MIME-Version: 1.0 References: <4eec3fb9-851e-3e4e-f9f4-1110db3af747@gmail.com> In-Reply-To: <4eec3fb9-851e-3e4e-f9f4-1110db3af747@gmail.com> From: Jonathan Wakely Date: Thu, 14 Oct 2021 09:23:50 +0100 Message-ID: Subject: Re: [PATH][_GLIBCXX_DEBUG] Fix unordered container merge To: =?UTF-8?Q?Fran=C3=A7ois_Dumont?= Cc: "libstdc++@gcc.gnu.org" , gcc-patches X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-6.4 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP 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-List-Received-Date: Thu, 14 Oct 2021 08:24:04 -0000 On Wed, 13 Oct 2021 at 18:10, Fran=C3=A7ois Dumont via Libstdc++ wrote: > > Hi > > libstdc++: [_GLIBCXX_DEBUG] Implement unordered container merge > > The _GLIBCXX_DEBUG unordered containers need a dedicated merge > implementation > so that any existing iterator on the transfered nodes is properly > invalidated. > > Add typedef/using declaration for everything used as-is from normal > implementation. > > libstdc++-v3/ChangeLog: > > * include/debug/safe_container.h (_Safe_container<>): Make > all methods > protected. > * include/debug/safe_unordered_container.h > (_Safe_unordered_container<>::_M_invalide_all): Make public. > (_Safe_unordered_container<>::_M_invalide_if): Likewise. > (_Safe_unordered_container<>::_M_invalide_local_if): Likewise. > * include/debug/unordered_map > (unordered_map<>::mapped_type, pointer, const_pointer): New > typedef. > (unordered_map<>::reference, const_reference, > difference_type): New typedef. > (unordered_map<>::get_allocator, empty, size, max_size): > Add usings. > (unordered_map<>::bucket_count, max_bucket_count, bucket): > Add usings. > (unordered_map<>::hash_function, key_equal, count, > contains): Add usings. > (unordered_map<>::operator[], at, rehash, reserve): Add usin= gs. > (unordered_map<>::merge): New. > (unordered_multimap<>::mapped_type, pointer, > const_pointer): New typedef. > (unordered_multimap<>::reference, const_reference, > difference_type): New typedef. > (unordered_multimap<>::get_allocator, empty, size, > max_size): Add usings. > (unordered_multimap<>::bucket_count, max_bucket_count, > bucket): Add usings. > (unordered_multimap<>::hash_function, key_equal, count, > contains): Add usings. > (unordered_multimap<>::rehash, reserve): Add usings. > (unordered_multimap<>::merge): New. > * include/debug/unordered_set > (unordered_set<>::mapped_type, pointer, const_pointer): New > typedef. > (unordered_set<>::reference, const_reference, > difference_type): New typedef. > (unordered_set<>::get_allocator, empty, size, max_size): > Add usings. > (unordered_set<>::bucket_count, max_bucket_count, bucket): > Add usings. > (unordered_set<>::hash_function, key_equal, count, > contains): Add usings. > (unordered_set<>::rehash, reserve): Add usings. > (unordered_set<>::merge): New. > (unordered_multiset<>::mapped_type, pointer, > const_pointer): New typedef. > (unordered_multiset<>::reference, const_reference, > difference_type): New typedef. > (unordered_multiset<>::get_allocator, empty, size, > max_size): Add usings. > (unordered_multiset<>::bucket_count, max_bucket_count, > bucket): Add usings. > (unordered_multiset<>::hash_function, key_equal, count, > contains): Add usings. > (unordered_multiset<>::rehash, reserve): Add usings. > (unordered_multiset<>::merge): New. > * > testsuite/23_containers/unordered_map/debug/merge1_neg.cc: New test. > * > testsuite/23_containers/unordered_map/debug/merge2_neg.cc: New test. > * > testsuite/23_containers/unordered_map/debug/merge3_neg.cc: New test. > * > testsuite/23_containers/unordered_map/debug/merge4_neg.cc: New test. > * > testsuite/23_containers/unordered_multimap/debug/merge1_neg.cc: New test. > * > testsuite/23_containers/unordered_multimap/debug/merge2_neg.cc: New test. > * > testsuite/23_containers/unordered_multimap/debug/merge3_neg.cc: New test. > * > testsuite/23_containers/unordered_multimap/debug/merge4_neg.cc: New test. > * > testsuite/23_containers/unordered_multiset/debug/merge1_neg.cc: New test. > * > testsuite/23_containers/unordered_multiset/debug/merge2_neg.cc: New test. > * > testsuite/23_containers/unordered_multiset/debug/merge3_neg.cc: New test. > * > testsuite/23_containers/unordered_multiset/debug/merge4_neg.cc: New test. > * > testsuite/23_containers/unordered_set/debug/merge1_neg.cc: New test. > * > testsuite/23_containers/unordered_set/debug/merge2_neg.cc: New test. > * > testsuite/23_containers/unordered_set/debug/merge3_neg.cc: New test. > * > testsuite/23_containers/unordered_set/debug/merge4_neg.cc: New test. > * testsuite/util/testsuite_abi.h: [_GLIBCXX_DEBUG] Use > normal unordered container implementation. > > Tested under Linux x86_64. > > Ok to commit ? Yes, thanks. But ... This looks like an improvement over what we have now, but not 100% correct. The merge functions can exit via exception (if any hash function or equality predicate throws), and if that happens the safe iterators will not get invalidated. I think we need to call _Base::merge in a try-block, and do the iterator invalidation whether we return normally or via an exception. Something like: template void merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source) { struct _Guard { _Guard(unordered_set& __source) noexcept : _M_source(__source), _M_size(__source.size()) { } ~_Guard() { const size_type __size =3D _M_source.size(); if (__size !=3D _M_size) { if (__size =3D=3D 0) _M_source._M_invalidate_all(); else { auto __pred =3D [&__source](auto __it) { return __source.count(*__it) =3D=3D 0; }; __source._M_invalidate_if(__pred); __source._M_invalidate_local_if(__pred); } } } _Guard(const _Guard&) =3D delete; unordered_set& _M_source; const size_type _M_size; }; _Guard __guard(__source); _Base::merge(__source._M_base()); }