From: Jonathan Wakely <jwakely.gcc@gmail.com>
To: "François Dumont" <frs.dumont@gmail.com>
Cc: Jonathan Wakely <jwakely@redhat.com>,
"libstdc++" <libstdc++@gcc.gnu.org>,
gcc-patches <gcc-patches@gcc.gnu.org>
Subject: Re: [PATH][_GLIBCXX_DEBUG] Fix unordered container merge
Date: Sat, 16 Oct 2021 15:52:36 +0100 [thread overview]
Message-ID: <CAH6eHdSt8wgsBjX7--vGz8ZFgo5sp8zBm52GJ5WFUvxHE3Q7zQ@mail.gmail.com> (raw)
In-Reply-To: <6c349652-8b6f-2027-08c3-6ce58a765aeb@gmail.com>
On Sat, 16 Oct 2021, 14:49 François 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çois
>
>
> On 14/10/21 10:23 am, Jonathan Wakely wrote:
> > On Wed, 13 Oct 2021 at 18:10, François Dumont via Libstdc++
> > <libstdc++@gcc.gnu.org> 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
> 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<typename _H2, typename _P2>
> > 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 = _M_source.size();
> > if (__size != _M_size)
> > {
> > if (__size == 0)
> > _M_source._M_invalidate_all();
> > else
> > {
> > auto __pred = [&__source](auto __it)
> > { return __source.count(*__it) == 0; };
> > __source._M_invalidate_if(__pred);
> > __source._M_invalidate_local_if(__pred);
> > }
> > }
> > }
> >
> > _Guard(const _Guard&) = delete;
> >
> > unordered_set& _M_source;
> > const size_type _M_size;
> > };
> > _Guard __guard(__source);
> > _Base::merge(__source._M_base());
> > }
> >
>
>
next prev parent reply other threads:[~2021-10-16 14:52 UTC|newest]
Thread overview: 21+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-10-13 17:10 François Dumont
2021-10-14 8:23 ` Jonathan Wakely
2021-10-16 13:47 ` François Dumont
2021-10-16 14:52 ` Jonathan Wakely [this message]
2021-10-21 16:51 ` François Dumont
2021-10-21 16:55 ` Jonathan Wakely
2021-10-22 5:22 ` François Dumont
2021-10-25 18:08 ` François Dumont
2021-11-06 13:51 ` François Dumont
2021-11-08 21:36 ` François Dumont
2021-11-09 16:25 ` Jonathan Wakely
2021-11-10 5:47 ` François Dumont
2021-11-10 9:38 ` Jonathan Wakely
2021-11-15 18:16 ` François Dumont
2021-11-10 11:55 ` Jonathan Wakely
2021-11-11 20:41 ` Jonathan Wakely
2021-11-11 21:33 ` François Dumont
2021-11-11 22:01 ` Jonathan Wakely
2021-11-10 0:05 ` H.J. Lu
2021-11-10 5:44 ` François Dumont
2021-11-10 7:26 ` Jonathan Wakely
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAH6eHdSt8wgsBjX7--vGz8ZFgo5sp8zBm52GJ5WFUvxHE3Q7zQ@mail.gmail.com \
--to=jwakely.gcc@gmail.com \
--cc=frs.dumont@gmail.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=jwakely@redhat.com \
--cc=libstdc++@gcc.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).