From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wr1-x430.google.com (mail-wr1-x430.google.com [IPv6:2a00:1450:4864:20::430]) by sourceware.org (Postfix) with ESMTPS id 1BA7F3858418; Sat, 16 Oct 2021 14:52:49 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 1BA7F3858418 Received: by mail-wr1-x430.google.com with SMTP id r10so31644113wra.12; Sat, 16 Oct 2021 07:52:49 -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; bh=/Qx9Ks7xhhiVqjft7e3YvsnkbAj/SWJZZXx2r/U3f4c=; b=IgA3OdC9NgvQq82+NHZxWNzE2EKWtoBNVZGuwqYgHneAJZ+xftkefj4jk5eQsWleJ9 P8mLgZ2g4L4ynzP0YHG45+VL+zholCbIrdHBHDo1oirNI+k1EYYHe+rkdvQmseSO2iQU yhSQdEtDOPkivTlPMvPwpNEiF4Am87sPmSFG/GGpGj1uaXMnue4joa9eYBPvmsLLQocS DbhmypoFbPbb+H3uZHb9lYrYR/hzNeM2G6AS168K2QiMTptGi1ip4KiyPQKRbGw6X6Tx mrfFIB/HEnOSeaRJiRxZlmDrq5fBhBQwtYZAc7JQb/rSZuZMCwNJZ91ZV7CQ0cAKBPgp wYqA== X-Gm-Message-State: AOAM533tWnKuyTtAaB5COWwxx4llMGrI96JYYMw2ZozLLn0vTcRCzl51 KuViXnarp+lBhZSpIcxL1UCQApoHPzWBGqvHIRc= X-Google-Smtp-Source: ABdhPJyrM0iGoNHQ9U7HEPh3Mt0lzjrQ0grXAeu0oqyx4F+X3E9cGVQigcnYaooLb1kOPwOdq0ORuG9/OUl4YaC/1Qw= X-Received: by 2002:a5d:4481:: with SMTP id j1mr23411221wrq.6.1634395967949; Sat, 16 Oct 2021 07:52:47 -0700 (PDT) MIME-Version: 1.0 References: <4eec3fb9-851e-3e4e-f9f4-1110db3af747@gmail.com> <6c349652-8b6f-2027-08c3-6ce58a765aeb@gmail.com> In-Reply-To: <6c349652-8b6f-2027-08c3-6ce58a765aeb@gmail.com> From: Jonathan Wakely Date: Sat, 16 Oct 2021 15:52:36 +0100 Message-ID: Subject: Re: [PATH][_GLIBCXX_DEBUG] Fix unordered container merge To: =?UTF-8?Q?Fran=C3=A7ois_Dumont?= Cc: Jonathan Wakely , "libstdc++" , gcc-patches X-Spam-Status: No, score=-1.0 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, HTML_MESSAGE, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, 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 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Content-Filtered-By: Mailman/MimeDel 2.1.29 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, 16 Oct 2021 14:52:52 -0000 On Sat, 16 Oct 2021, 14:49 Fran=C3=A7ois Dumont via Libstdc++, < libstdc++@gcc.gnu.org> wrote: > Hi > > Here is the new proposal. My only concern is that we are also using > hash or equal_to functors in the guard destructor. > Can we catch any exception there, invalidate all iterators, and not rethrow the exception? > I am going to enhance merge normal implementation to make use of > the cached hash code when hash functors are the same between the source > and destination of nodes. Maybe I'll be able to make use of it in Debug > implementation too. > > Fran=C3=A7ois > > > On 14/10/21 10:23 am, Jonathan Wakely wrote: > > 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 properl= y > >> invalidated. > >> > >> Add typedef/using declaration for everything used as-is from > normal > >> implementation. > >> > >> libstdc++-v3/ChangeLog: > >> > >> * include/debug/safe_container.h (_Safe_container<>): Ma= ke > >> 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 > usings. > >> (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()); > > } > > > >