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 [216.205.24.124]) by sourceware.org (Postfix) with ESMTP id 507B93858C2C for ; Thu, 14 Oct 2021 08:24:03 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 507B93858C2C 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-547-loI1dZcGNj69iimCK9gD-A-1; Thu, 14 Oct 2021 04:24:01 -0400 X-MC-Unique: loI1dZcGNj69iimCK9gD-A-1 Received: by mail-vk1-f199.google.com with SMTP id r6-20020a1f8f06000000b002a3a5317c40so2086334vkd.0 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=qA6RV0Me4WvxSTRdi27JboEEyrWXt3tb2bgitq4VsXuj65djWqr+MJnzcBFKGW6YPn 5h0Mp4Y/qYZT8kvKYA4gxhOntLH9HUTdLEbKLoIdih9NF4GFNrNuzqmPdKqAsIzNmbtE 2Tdlt552T7W/QR34je7Z0PrmyCJf41fGiYjr9n0usju2QWbouI2cG5pbAS5UPwvQT2Go 9qv3lsZ0Qd2ct8u9QXknTXeaZaYEsySRGtfooYc9GcRzr/5HrUX88P01o/cGcC6E6Zvk kMcJ+aQxtU5jMjWAOW9iMNNSCULPs+0eWaWn8Qcy3KzIH+PEXGxXkOhTO6MVgOoEZbgX GF1g== X-Gm-Message-State: AOAM533Atm5ai0az4oJ5byrJqojjV/sfSEqUkOUUDh+LY3Z2kaWpDJYG h/AfHYHin02PO7AWot3iQXLQWcIQC6wG9d1R1axKZohINpoojxBeHRX6eqvoHMpNWtCCd1q0C8R m7XCiqeOk2gpnOM9+dXJ0KdLsAjGQ7Y4= X-Received: by 2002:a9f:3399:: with SMTP id p25mr4757829uab.24.1634199841274; 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=-4.0 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: 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: 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()); }