On Wed, 13 Oct 2021 at 18:10, François Dumont via Libstdc++
<libstd...@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());
}
