[PATH,_GLIBCXX_DEBUG] Fix unordered container merge
Commit Message
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 ?
François
Comments
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());
}
Hi
Here is the new proposal. My only concern is that we are also using
hash or equal_to functors in the guard destructor.
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());
> }
>
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());
> > }
> >
>
>
I eventually would like to propose a different approach.
I am adding a hook in normal implementation to let the _GLIBCXX_DEBUG
code know when a node is being extracted. This way invalidation is only
done by comparing nodes, no need to compute hash code for this operation.
The only drawback is that for each extraction we have a linear research
on iterators to invalidate the correct one. I will implement next an
optimization when hasher/equal_to are noexcept.
This patch also remove the invalid noexcept qualification on the
_Hashtable merge methods and make use of const_iterator as it is what is
expected by the extract.
Tested under Linux x86_64.
Ok to commit ?
François
On 16/10/21 4:52 pm, Jonathan Wakely wrote:
>
>
> On Sat, 16 Oct 2021, 14:49 François Dumont via Libstdc++,
> <libstdc++@gcc.gnu.org <mailto:libstdc%2B%2B@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 <mailto:libstdc%2B%2B@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());
> > }
> >
>
On Thu, 21 Oct 2021 at 17:52, François Dumont <frs.dumont@gmail.com> wrote:
> I eventually would like to propose a different approach.
>
> I am adding a hook in normal implementation to let the _GLIBCXX_DEBUG code
> know when a node is being extracted. This way invalidation is only done by
> comparing nodes, no need to compute hash code for this operation.
>
Ugh, this is horrible, I don't like the normal mode depending on the debug
mode (even if it's just having to add hooks like this).
The previous patch seemed fine to me. Already an improvement on what is on
trunk now.
On 21/10/21 6:55 pm, Jonathan Wakely wrote:
>
>
> On Thu, 21 Oct 2021 at 17:52, François Dumont <frs.dumont@gmail.com
> <mailto:frs.dumont@gmail.com>> wrote:
>
> I eventually would like to propose a different approach.
>
> I am adding a hook in normal implementation to let the
> _GLIBCXX_DEBUG code know when a node is being extracted. This way
> invalidation is only done by comparing nodes, no need to compute
> hash code for this operation.
>
>
> Ugh, this is horrible, I don't like the normal mode depending on the
> debug mode (even if it's just having to add hooks like this).
Yes, I was relunctant to do so but in this case I was not able to find
another way to provide the same result as here.
Ok, I'll come back to the other patch and just invalidate all iterators
in case of exception.
>
> The previous patch seemed fine to me. Already an improvement on what
> is on trunk now.
>
New patch with the proposed workaround below.
I also slightly change the _M_merge_multi implementation so that if the
new hash code computation raise an exception the node is simply not
extracted rather than extracted and then released. This way, if it takes
place on the 1st moved node the _GLIBCXX_DEBUG mode won't try to
invalidate anything because the source size won't have changed.
Ok to commit ?
François
On 16/10/21 4:52 pm, Jonathan Wakely wrote:
>
>
> On Sat, 16 Oct 2021, 14:49 François Dumont via Libstdc++,
> <libstdc++@gcc.gnu.org <mailto:libstdc%2B%2B@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 <mailto:libstdc%2B%2B@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());
> > }
> >
>
You were right to delay your reply. Here is a new version with less code
duplication and a bug fix in the new _UContMergeGuard where we were
using it->second rather than it->first to get the key.
Note also that the change to _M_merge_multi implementation is also
important because otherwise we might be trying to extract a key from a
destructed node.
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/bits/hashtable_policy.h (__distance_fw): Replace
class keyword with
typename.
* include/bits/hashtable.h (_Hashtable<>::_M_merge_unique):
Remove noexcept
qualification. Use const_iterator for node extraction/reinsert.
(_Hashtable<>::_M_merge_multi): Likewise. Compute new hash
code before extract.
* include/debug/safe_container.h (_Safe_container<>): Make
all methods
protected.
* include/debug/safe_unordered_container.h
(_Safe_unordered_container<>::_UContMergeGuard<_ExtractKey, _Source>): New.
(_Safe_unordered_container<>::_S_uc_guard<_ExtractKey, _Source>): New.
(_Safe_unordered_container<>::_UMContMergeGuard<_ExtractKey, _Source>): New.
(_Safe_unordered_container<>::_S_umc_guard<_ExtractKey, _Source>): New.
(_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 ?
François
On 25/10/21 8:08 pm, François Dumont wrote:
> New patch with the proposed workaround below.
>
> I also slightly change the _M_merge_multi implementation so that if
> the new hash code computation raise an exception the node is simply
> not extracted rather than extracted and then released. This way, if it
> takes place on the 1st moved node the _GLIBCXX_DEBUG mode won't try to
> invalidate anything because the source size won't have changed.
>
> Ok to commit ?
>
> François
>
>
> On 16/10/21 4:52 pm, Jonathan Wakely wrote:
>>
>>
>> On Sat, 16 Oct 2021, 14:49 François Dumont via Libstdc++,
>> <libstdc++@gcc.gnu.org <mailto:libstdc%2B%2B@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 <mailto:libstdc%2B%2B@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());
>> > }
>> >
>>
>
Yet another version this time with only 1 guard implementation. The
predicate to invalidate the safe iterators has been externalized.
Ok to commit ?
On 06/11/21 2:51 pm, François Dumont wrote:
> You were right to delay your reply. Here is a new version with less
> code duplication and a bug fix in the new _UContMergeGuard where we
> were using it->second rather than it->first to get the key.
>
> Note also that the change to _M_merge_multi implementation is also
> important because otherwise we might be trying to extract a key from a
> destructed node.
>
> 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/bits/hashtable_policy.h (__distance_fw): Replace
> class keyword with
> typename.
> * include/bits/hashtable.h
> (_Hashtable<>::_M_merge_unique): Remove noexcept
> qualification. Use const_iterator for node
> extraction/reinsert.
> (_Hashtable<>::_M_merge_multi): Likewise. Compute new hash
> code before extract.
> * include/debug/safe_container.h (_Safe_container<>): Make
> all methods
> protected.
> * include/debug/safe_unordered_container.h
> (_Safe_unordered_container<>::_UContMergeGuard<_ExtractKey, _Source>):
> New.
> (_Safe_unordered_container<>::_S_uc_guard<_ExtractKey, _Source>): New.
> (_Safe_unordered_container<>::_UMContMergeGuard<_ExtractKey,
> _Source>): New.
> (_Safe_unordered_container<>::_S_umc_guard<_ExtractKey, _Source>): New.
> (_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 ?
>
> François
>
> On 25/10/21 8:08 pm, François Dumont wrote:
>> New patch with the proposed workaround below.
>>
>> I also slightly change the _M_merge_multi implementation so that if
>> the new hash code computation raise an exception the node is simply
>> not extracted rather than extracted and then released. This way, if
>> it takes place on the 1st moved node the _GLIBCXX_DEBUG mode won't
>> try to invalidate anything because the source size won't have changed.
>>
>> Ok to commit ?
>>
>> François
>>
>>
>> On 16/10/21 4:52 pm, Jonathan Wakely wrote:
>>>
>>>
>>> On Sat, 16 Oct 2021, 14:49 François Dumont via Libstdc++,
>>> <libstdc++@gcc.gnu.org <mailto:libstdc%2B%2B@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 <mailto:libstdc%2B%2B@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());
>>> > }
>>> >
>>>
>>
>
On Mon, 8 Nov 2021 at 21:36, François Dumont <frs.dumont@gmail.com> wrote:
> Yet another version this time with only 1 guard implementation. The
> predicate to invalidate the safe iterators has been externalized.
>
> Ok to commit ?
>
I like this version a lot - thanks for persisting with it.
OK to commit, thanks.
As an aside ...
--- a/libstdc++-v3/testsuite/util/testsuite_abi.h
+++ b/libstdc++-v3/testsuite/util/testsuite_abi.h
@@ -24,7 +24,11 @@
#include <locale>
#if __cplusplus >= 201103L
# include <unordered_map>
+# ifdef _GLIBCXX_DEBUG
+namespace unord = std::_GLIBCXX_STD_C;
+# else
namespace unord = std;
+# endif
#else
# include <tr1/unordered_map>
namespace unord = std::tr1;
Several times I've been annoyed by the fact that we don't have a way to
refer to std::_GLIBCXX_STD_C::vector etc. that is always valid, in normal
mode and debug mode.
Maybe we should add:
namespace std { namespace _GLIBCXX_STD_C = ::std; }
That way we can refer to std::_GLIBCXX_STD_C::foo in normal mode, and it
will mean the same thing as in debug mode. So we don't need to use #if
conditions like this.
On Mon, Nov 8, 2021 at 1:37 PM François Dumont via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> Yet another version this time with only 1 guard implementation. The
> predicate to invalidate the safe iterators has been externalized.
>
> Ok to commit ?
>
This may have broken GCC bootstrap on Linux/x86-64:
https://gcc.gnu.org/pipermail/gcc-regression/2021-November/075734.html
In file included from ../../src-master/gcc/sanopt.c:22:
In member function ‘hash_table<Descriptor, Lazy,
Allocator>::value_type* hash_table<Descriptor, Lazy,
Allocator>::alloc_entries(size_t) const [with Descriptor =
hash_map<tree_node*, auto_vec<gimple*> >::hash_entry; bool Lazy =
false; Allocator = xcallocator]’,
inlined from ‘void hash_table<Descriptor, Lazy,
Allocator>::expand() [with Descriptor = hash_map<tree_node*,
auto_vec<gimple*> >::hash_entry; bool Lazy = false; Allocator =
xcallocator]’ at ../../src-master/gcc/hash-table.h:802:40:
../../src-master/gcc/system.h:784:34: error: section type conflict
with ‘void hash_table<Descriptor, Lazy, Allocator>::expand() [with
Descriptor = hash_map<tree_node*, auto_vec<gimple*> >::hash_entry;
bool Lazy = false; Allocator = xcallocator]’
784 | ((void)(!(EXPR) ? fancy_abort (__FILE__, __LINE__,
__FUNCTION__), 0 : 0))
| ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
../../src-master/gcc/hash-table.h:715:3: note: in expansion of macro
‘gcc_assert’
715 | gcc_assert (nentries != NULL);
| ^~~~~~~~~~
In file included from ../../src-master/gcc/coretypes.h:482,
from ../../src-master/gcc/sanopt.c:23:
../../src-master/gcc/hash-table.h: In member function ‘void
hash_table<Descriptor, Lazy, Allocator>::expand() [with Descriptor =
hash_map<tree_node*, auto_vec<gimple*> >::hash_entry; bool Lazy =
false; Allocator = xcallocator]’:
../../src-master/gcc/hash-table.h:779:1: note: ‘void
hash_table<Descriptor, Lazy, Allocator>::expand() [with Descriptor =
hash_map<tree_node*, auto_vec<gimple*> >::hash_entry; bool Lazy =
false; Allocator = xcallocator]’ was declared here
779 | hash_table<Descriptor, Lazy, Allocator>::expand ()
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> On 06/11/21 2:51 pm, François Dumont wrote:
> > You were right to delay your reply. Here is a new version with less
> > code duplication and a bug fix in the new _UContMergeGuard where we
> > were using it->second rather than it->first to get the key.
> >
> > Note also that the change to _M_merge_multi implementation is also
> > important because otherwise we might be trying to extract a key from a
> > destructed node.
> >
> > 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/bits/hashtable_policy.h (__distance_fw): Replace
> > class keyword with
> > typename.
> > * include/bits/hashtable.h
> > (_Hashtable<>::_M_merge_unique): Remove noexcept
> > qualification. Use const_iterator for node
> > extraction/reinsert.
> > (_Hashtable<>::_M_merge_multi): Likewise. Compute new hash
> > code before extract.
> > * include/debug/safe_container.h (_Safe_container<>): Make
> > all methods
> > protected.
> > * include/debug/safe_unordered_container.h
> > (_Safe_unordered_container<>::_UContMergeGuard<_ExtractKey, _Source>):
> > New.
> > (_Safe_unordered_container<>::_S_uc_guard<_ExtractKey, _Source>): New.
> > (_Safe_unordered_container<>::_UMContMergeGuard<_ExtractKey,
> > _Source>): New.
> > (_Safe_unordered_container<>::_S_umc_guard<_ExtractKey, _Source>): New.
> > (_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 ?
> >
> > François
> >
> > On 25/10/21 8:08 pm, François Dumont wrote:
> >> New patch with the proposed workaround below.
> >>
> >> I also slightly change the _M_merge_multi implementation so that if
> >> the new hash code computation raise an exception the node is simply
> >> not extracted rather than extracted and then released. This way, if
> >> it takes place on the 1st moved node the _GLIBCXX_DEBUG mode won't
> >> try to invalidate anything because the source size won't have changed.
> >>
> >> Ok to commit ?
> >>
> >> François
> >>
> >>
> >> On 16/10/21 4:52 pm, Jonathan Wakely wrote:
> >>>
> >>>
> >>> On Sat, 16 Oct 2021, 14:49 François Dumont via Libstdc++,
> >>> <libstdc++@gcc.gnu.org <mailto:libstdc%2B%2B@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 <mailto:libstdc%2B%2B@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());
> >>> > }
> >>> >
> >>>
> >>
> >
>
I can't see any clue on how my commit can have had an impact on below code.
I don't think libstdc++ hash table has any relation with gcc hash table.
Still, I'm rebuilding gcc at my revision to confirm.
On 10/11/21 1:05 am, H.J. Lu wrote:
> On Mon, Nov 8, 2021 at 1:37 PM François Dumont via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
>> Yet another version this time with only 1 guard implementation. The
>> predicate to invalidate the safe iterators has been externalized.
>>
>> Ok to commit ?
>>
> This may have broken GCC bootstrap on Linux/x86-64:
>
> https://gcc.gnu.org/pipermail/gcc-regression/2021-November/075734.html
>
> In file included from ../../src-master/gcc/sanopt.c:22:
> In member function ‘hash_table<Descriptor, Lazy,
> Allocator>::value_type* hash_table<Descriptor, Lazy,
> Allocator>::alloc_entries(size_t) const [with Descriptor =
> hash_map<tree_node*, auto_vec<gimple*> >::hash_entry; bool Lazy =
> false; Allocator = xcallocator]’,
> inlined from ‘void hash_table<Descriptor, Lazy,
> Allocator>::expand() [with Descriptor = hash_map<tree_node*,
> auto_vec<gimple*> >::hash_entry; bool Lazy = false; Allocator =
> xcallocator]’ at ../../src-master/gcc/hash-table.h:802:40:
> ../../src-master/gcc/system.h:784:34: error: section type conflict
> with ‘void hash_table<Descriptor, Lazy, Allocator>::expand() [with
> Descriptor = hash_map<tree_node*, auto_vec<gimple*> >::hash_entry;
> bool Lazy = false; Allocator = xcallocator]’
> 784 | ((void)(!(EXPR) ? fancy_abort (__FILE__, __LINE__,
> __FUNCTION__), 0 : 0))
> | ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> ../../src-master/gcc/hash-table.h:715:3: note: in expansion of macro
> ‘gcc_assert’
> 715 | gcc_assert (nentries != NULL);
> | ^~~~~~~~~~
> In file included from ../../src-master/gcc/coretypes.h:482,
> from ../../src-master/gcc/sanopt.c:23:
> ../../src-master/gcc/hash-table.h: In member function ‘void
> hash_table<Descriptor, Lazy, Allocator>::expand() [with Descriptor =
> hash_map<tree_node*, auto_vec<gimple*> >::hash_entry; bool Lazy =
> false; Allocator = xcallocator]’:
> ../../src-master/gcc/hash-table.h:779:1: note: ‘void
> hash_table<Descriptor, Lazy, Allocator>::expand() [with Descriptor =
> hash_map<tree_node*, auto_vec<gimple*> >::hash_entry; bool Lazy =
> false; Allocator = xcallocator]’ was declared here
> 779 | hash_table<Descriptor, Lazy, Allocator>::expand ()
> | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>
>> On 06/11/21 2:51 pm, François Dumont wrote:
>>> You were right to delay your reply. Here is a new version with less
>>> code duplication and a bug fix in the new _UContMergeGuard where we
>>> were using it->second rather than it->first to get the key.
>>>
>>> Note also that the change to _M_merge_multi implementation is also
>>> important because otherwise we might be trying to extract a key from a
>>> destructed node.
>>>
>>> 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/bits/hashtable_policy.h (__distance_fw): Replace
>>> class keyword with
>>> typename.
>>> * include/bits/hashtable.h
>>> (_Hashtable<>::_M_merge_unique): Remove noexcept
>>> qualification. Use const_iterator for node
>>> extraction/reinsert.
>>> (_Hashtable<>::_M_merge_multi): Likewise. Compute new hash
>>> code before extract.
>>> * include/debug/safe_container.h (_Safe_container<>): Make
>>> all methods
>>> protected.
>>> * include/debug/safe_unordered_container.h
>>> (_Safe_unordered_container<>::_UContMergeGuard<_ExtractKey, _Source>):
>>> New.
>>> (_Safe_unordered_container<>::_S_uc_guard<_ExtractKey, _Source>): New.
>>> (_Safe_unordered_container<>::_UMContMergeGuard<_ExtractKey,
>>> _Source>): New.
>>> (_Safe_unordered_container<>::_S_umc_guard<_ExtractKey, _Source>): New.
>>> (_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 ?
>>>
>>> François
>>>
>>> On 25/10/21 8:08 pm, François Dumont wrote:
>>>> New patch with the proposed workaround below.
>>>>
>>>> I also slightly change the _M_merge_multi implementation so that if
>>>> the new hash code computation raise an exception the node is simply
>>>> not extracted rather than extracted and then released. This way, if
>>>> it takes place on the 1st moved node the _GLIBCXX_DEBUG mode won't
>>>> try to invalidate anything because the source size won't have changed.
>>>>
>>>> Ok to commit ?
>>>>
>>>> François
>>>>
>>>>
>>>> On 16/10/21 4:52 pm, Jonathan Wakely wrote:
>>>>>
>>>>> On Sat, 16 Oct 2021, 14:49 François Dumont via Libstdc++,
>>>>> <libstdc++@gcc.gnu.org <mailto:libstdc%2B%2B@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 <mailto:libstdc%2B%2B@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());
>>>>> > }
>>>>> >
>>>>>
>
On 09/11/21 5:25 pm, Jonathan Wakely wrote:
>
>
> On Mon, 8 Nov 2021 at 21:36, François Dumont <frs.dumont@gmail.com
> <mailto:frs.dumont@gmail.com>> wrote:
>
> Yet another version this time with only 1 guard implementation.
> The predicate to invalidate the safe iterators has been externalized.
>
> Ok to commit ?
>
>
> I like this version a lot - thanks for persisting with it.
>
> OK to commit, thanks.
>
>
> As an aside ...
>
> --- a/libstdc++-v3/testsuite/util/testsuite_abi.h
> +++ b/libstdc++-v3/testsuite/util/testsuite_abi.h
> @@ -24,7 +24,11 @@
> #include <locale>
> #if __cplusplus >= 201103L
> # include <unordered_map>
> +# ifdef _GLIBCXX_DEBUG
> +namespace unord = std::_GLIBCXX_STD_C;
> +# else
> namespace unord = std;
> +# endif
> #else
> # include <tr1/unordered_map>
> namespace unord = std::tr1;
>
>
> Several times I've been annoyed by the fact that we don't have a way
> to refer to std::_GLIBCXX_STD_C::vector etc. that is always valid, in
> normal mode and debug mode.
>
> Maybe we should add:
>
> namespace std { namespace _GLIBCXX_STD_C = ::std; }
>
> That way we can refer to std::_GLIBCXX_STD_C::foo in normal mode, and
> it will mean the same thing as in debug mode. So we don't need to use
> #if conditions like this.
>
>
Good idea, I'll prepare it.
François
On Wed, 10 Nov 2021, 05:45 François Dumont, <frs.dumont@gmail.com> wrote:
> I can't see any clue on how my commit can have had an impact on below code.
>
Agreed.
> I don't think libstdc++ hash table has any relation with gcc hash table.
>
Correct, it's totally unrelated. And "section type conflict" can't be
caused by the library anyway.
> Still, I'm rebuilding gcc at my revision to confirm.
>
> On 10/11/21 1:05 am, H.J. Lu wrote:
> > On Mon, Nov 8, 2021 at 1:37 PM François Dumont via Gcc-patches
> > <gcc-patches@gcc.gnu.org> wrote:
> >> Yet another version this time with only 1 guard implementation. The
> >> predicate to invalidate the safe iterators has been externalized.
> >>
> >> Ok to commit ?
> >>
> > This may have broken GCC bootstrap on Linux/x86-64:
> >
> > https://gcc.gnu.org/pipermail/gcc-regression/2021-November/075734.html
> >
> > In file included from ../../src-master/gcc/sanopt.c:22:
> > In member function ‘hash_table<Descriptor, Lazy,
> > Allocator>::value_type* hash_table<Descriptor, Lazy,
> > Allocator>::alloc_entries(size_t) const [with Descriptor =
> > hash_map<tree_node*, auto_vec<gimple*> >::hash_entry; bool Lazy =
> > false; Allocator = xcallocator]’,
> > inlined from ‘void hash_table<Descriptor, Lazy,
> > Allocator>::expand() [with Descriptor = hash_map<tree_node*,
> > auto_vec<gimple*> >::hash_entry; bool Lazy = false; Allocator =
> > xcallocator]’ at ../../src-master/gcc/hash-table.h:802:40:
> > ../../src-master/gcc/system.h:784:34: error: section type conflict
> > with ‘void hash_table<Descriptor, Lazy, Allocator>::expand() [with
> > Descriptor = hash_map<tree_node*, auto_vec<gimple*> >::hash_entry;
> > bool Lazy = false; Allocator = xcallocator]’
> > 784 | ((void)(!(EXPR) ? fancy_abort (__FILE__, __LINE__,
> > __FUNCTION__), 0 : 0))
> > |
> ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> > ../../src-master/gcc/hash-table.h:715:3: note: in expansion of macro
> > ‘gcc_assert’
> > 715 | gcc_assert (nentries != NULL);
> > | ^~~~~~~~~~
> > In file included from ../../src-master/gcc/coretypes.h:482,
> > from ../../src-master/gcc/sanopt.c:23:
> > ../../src-master/gcc/hash-table.h: In member function ‘void
> > hash_table<Descriptor, Lazy, Allocator>::expand() [with Descriptor =
> > hash_map<tree_node*, auto_vec<gimple*> >::hash_entry; bool Lazy =
> > false; Allocator = xcallocator]’:
> > ../../src-master/gcc/hash-table.h:779:1: note: ‘void
> > hash_table<Descriptor, Lazy, Allocator>::expand() [with Descriptor =
> > hash_map<tree_node*, auto_vec<gimple*> >::hash_entry; bool Lazy =
> > false; Allocator = xcallocator]’ was declared here
> > 779 | hash_table<Descriptor, Lazy, Allocator>::expand ()
> > | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>
>
On Wed, 10 Nov 2021 at 05:47, François Dumont <frs.dumont@gmail.com> wrote:
> On 09/11/21 5:25 pm, Jonathan Wakely wrote:
>
>
>
> On Mon, 8 Nov 2021 at 21:36, François Dumont <frs.dumont@gmail.com> wrote:
>
>> Yet another version this time with only 1 guard implementation. The
>> predicate to invalidate the safe iterators has been externalized.
>>
>> Ok to commit ?
>>
>
> I like this version a lot - thanks for persisting with it.
>
> OK to commit, thanks.
>
>
> As an aside ...
>
> --- a/libstdc++-v3/testsuite/util/testsuite_abi.h
> +++ b/libstdc++-v3/testsuite/util/testsuite_abi.h
> @@ -24,7 +24,11 @@
> #include <locale>
> #if __cplusplus >= 201103L
> # include <unordered_map>
> +# ifdef _GLIBCXX_DEBUG
> +namespace unord = std::_GLIBCXX_STD_C;
> +# else
> namespace unord = std;
> +# endif
> #else
> # include <tr1/unordered_map>
> namespace unord = std::tr1;
>
>
> Several times I've been annoyed by the fact that we don't have a way to
> refer to std::_GLIBCXX_STD_C::vector etc. that is always valid, in normal
> mode and debug mode.
>
> Maybe we should add:
>
> namespace std { namespace _GLIBCXX_STD_C = ::std; }
>
> That way we can refer to std::_GLIBCXX_STD_C::foo in normal mode, and it
> will mean the same thing as in debug mode. So we don't need to use #if
> conditions like this.
>
>
> Good idea, I'll prepare it.
>
Alternatively we could do this:
namespace std
{
namespace __cxx1998 { }
#ifdef _GLIBCXX_DEBUG
namespace __cont = __cxx1998;
#else
namespace __cont = ::std::
#endif
}
And then define this so it's always the same name:
#define _GLIBCXX_STD_C __cont
Then we can refer to std::_GLIBCXX_STD_C::vector in any context, and it
refers to the right thing. And we could also stop using the SHOUTING macro,
and just refer to std::__cont::vector instead.
We could also make this work as std::__cxx1998::vector, but maybe we should
move away from the "1998" name, because it doesn't make much sense for
forward_list and unordered_map which are not in C++98.
On Tue, 9 Nov 2021 at 16:25, Jonathan Wakely <jwakely@redhat.com> wrote:
>
>
> On Mon, 8 Nov 2021 at 21:36, François Dumont <frs.dumont@gmail.com> wrote:
>
>> Yet another version this time with only 1 guard implementation. The
>> predicate to invalidate the safe iterators has been externalized.
>>
>> Ok to commit ?
>>
>
> I like this version a lot - thanks for persisting with it.
>
>
I'm seeing new failures with this:
make check RUNTESTFLAGS="conformance.exp=23_containers/*/invalidation/*
--target_board=unix/-D_GLIBCXX_DEBUG/-std=gnu++98"
FAIL: 23_containers/deque/debug/invalidation/1.cc (test for excess errors)
FAIL: 23_containers/list/debug/invalidation/1.cc (test for excess errors)
FAIL: 23_containers/map/debug/invalidation/1.cc (test for excess errors)
FAIL: 23_containers/multimap/debug/invalidation/1.cc (test for excess
errors)
FAIL: 23_containers/multiset/debug/invalidation/1.cc (test for excess
errors)
FAIL: 23_containers/set/debug/invalidation/1.cc (test for excess errors)
FAIL: 23_containers/vector/debug/invalidation/1.cc (test for excess errors)
On Wed, 10 Nov 2021 at 11:55, Jonathan Wakely <jwakely@redhat.com> wrote:
>
>
> On Tue, 9 Nov 2021 at 16:25, Jonathan Wakely <jwakely@redhat.com> wrote:
>
>>
>>
>> On Mon, 8 Nov 2021 at 21:36, François Dumont <frs.dumont@gmail.com>
>> wrote:
>>
>>> Yet another version this time with only 1 guard implementation. The
>>> predicate to invalidate the safe iterators has been externalized.
>>>
>>> Ok to commit ?
>>>
>>
>> I like this version a lot - thanks for persisting with it.
>>
>>
>
> I'm seeing new failures with this:
>
> make check RUNTESTFLAGS="conformance.exp=23_containers/*/invalidation/*
> --target_board=unix/-D_GLIBCXX_DEBUG/-std=gnu++98"
>
> FAIL: 23_containers/deque/debug/invalidation/1.cc (test for excess errors)
> FAIL: 23_containers/list/debug/invalidation/1.cc (test for excess errors)
> FAIL: 23_containers/map/debug/invalidation/1.cc (test for excess errors)
> FAIL: 23_containers/multimap/debug/invalidation/1.cc (test for excess
> errors)
> FAIL: 23_containers/multiset/debug/invalidation/1.cc (test for excess
> errors)
> FAIL: 23_containers/set/debug/invalidation/1.cc (test for excess errors)
> FAIL: 23_containers/vector/debug/invalidation/1.cc (test for excess errors)
>
It's caused by:
--- a/libstdc++-v3/include/debug/safe_container.h
+++ b/libstdc++-v3/include/debug/safe_container.h
@@ -78,7 +78,6 @@ namespace __gnu_debug
{ }
#endif
- public:
// Copy assignment invalidate all iterators.
_Safe_container&
operator=(const _Safe_container&) _GLIBCXX_NOEXCEPT
For C++98 mode that gets called explicitly by the user-provided copy
assignment operators in the derived class.
I'm testing the attached fix.
commit 7075abd518364b8d9767079e044baba86145cc08
Author: Jonathan Wakely <jwakely@redhat.com>
Date: Thu Nov 11 20:23:48 2021
libstdc++: Fix debug containers for C++98 mode
Since r12-5072 made _Safe_container::operator=(const _Safe_container&)
protected, the debug containers no longer compile in C++98 mode. They
have user-provided copy assignment operators in C++98 mode, and they
assign each base class in turn. The 'this->_M_safe() = __x' expressions
fail, because calling a protected member function is only alowed via
`this`. They could be fixed by using this->_Safe::operator=(__x) but a
simpler solution is to just remove the user-provided assignment
operators and let the compiler defined them (as in C++11 and later).
The only change needed for that to work is to define the _Safe_vector
copy assignment operator in C++98 mode, so that the implicit
__gnu_debug::vector::operator= definition will call it, instead of
calling _M_update_guaranteed_capacity() manually.
libstdc++-v3/ChangeLog:
* include/debug/deque (deque::operator=(const deque&)): Remove
definition.
* include/debug/list (list::operator=(const list&)): Likewise.
* include/debug/map.h (map::operator=(const map&)): Likewise.
* include/debug/multimap.h (multimap::operator=(const multimap&)):
Likewise.
* include/debug/multiset.h (multiset::operator=(const multiset&)):
Likewise.
* include/debug/set.h (set::operator=(const set&)): Likewise.
* include/debug/string (basic_string::operator=(const basic_string&)):
Likewise.
* include/debug/vector (vector::operator=(const vector&)):
Likewise.
(_Safe_vector::operator=(const _Safe_vector&)): Define for
C++98 as well.
diff --git a/libstdc++-v3/include/debug/deque b/libstdc++-v3/include/debug/deque
index 8e4811149d2..52778ba1617 100644
--- a/libstdc++-v3/include/debug/deque
+++ b/libstdc++-v3/include/debug/deque
@@ -156,15 +156,7 @@ namespace __debug
deque(_Base_ref __x)
: _Base(__x._M_ref) { }
-#if __cplusplus < 201103L
- deque&
- operator=(const deque& __x)
- {
- this->_M_safe() = __x;
- _M_base() = __x;
- return *this;
- }
-#else
+#if __cplusplus >= 201103L
deque&
operator=(const deque&) = default;
diff --git a/libstdc++-v3/include/debug/list b/libstdc++-v3/include/debug/list
index de30edb19c2..f40ebc8521e 100644
--- a/libstdc++-v3/include/debug/list
+++ b/libstdc++-v3/include/debug/list
@@ -161,15 +161,7 @@ namespace __debug
list(_Base_ref __x)
: _Base(__x._M_ref) { }
-#if __cplusplus < 201103L
- list&
- operator=(const list& __x)
- {
- this->_M_safe() = __x;
- _M_base() = __x;
- return *this;
- }
-#else
+#if __cplusplus >= 201103L
list&
operator=(const list&) = default;
diff --git a/libstdc++-v3/include/debug/map.h b/libstdc++-v3/include/debug/map.h
index 9e142cf7023..3883c546871 100644
--- a/libstdc++-v3/include/debug/map.h
+++ b/libstdc++-v3/include/debug/map.h
@@ -152,15 +152,7 @@ namespace __debug
__gnu_debug::__base(__last),
__comp, __a) { }
-#if __cplusplus < 201103L
- map&
- operator=(const map& __x)
- {
- this->_M_safe() = __x;
- _M_base() = __x;
- return *this;
- }
-#else
+#if __cplusplus >= 201103L
map&
operator=(const map&) = default;
diff --git a/libstdc++-v3/include/debug/multimap.h b/libstdc++-v3/include/debug/multimap.h
index a05b8a8493e..073c1c39240 100644
--- a/libstdc++-v3/include/debug/multimap.h
+++ b/libstdc++-v3/include/debug/multimap.h
@@ -152,15 +152,7 @@ namespace __debug
multimap(_Base_ref __x)
: _Base(__x._M_ref) { }
-#if __cplusplus < 201103L
- multimap&
- operator=(const multimap& __x)
- {
- this->_M_safe() = __x;
- _M_base() = __x;
- return *this;
- }
-#else
+#if __cplusplus >= 201103L
multimap&
operator=(const multimap&) = default;
diff --git a/libstdc++-v3/include/debug/multiset.h b/libstdc++-v3/include/debug/multiset.h
index a312ccf6f50..479411d9d06 100644
--- a/libstdc++-v3/include/debug/multiset.h
+++ b/libstdc++-v3/include/debug/multiset.h
@@ -152,15 +152,7 @@ namespace __debug
multiset(_Base_ref __x)
: _Base(__x._M_ref) { }
-#if __cplusplus < 201103L
- multiset&
- operator=(const multiset& __x)
- {
- this->_M_safe() = __x;
- _M_base() = __x;
- return *this;
- }
-#else
+#if __cplusplus >= 201103L
multiset&
operator=(const multiset&) = default;
diff --git a/libstdc++-v3/include/debug/set.h b/libstdc++-v3/include/debug/set.h
index 01da942eb78..e35e5c1faae 100644
--- a/libstdc++-v3/include/debug/set.h
+++ b/libstdc++-v3/include/debug/set.h
@@ -150,15 +150,7 @@ namespace __debug
set(_Base_ref __x)
: _Base(__x._M_ref) { }
-#if __cplusplus < 201103L
- set&
- operator=(const set& __x)
- {
- this->_M_safe() = __x;
- _M_base() = __x;
- return *this;
- }
-#else
+#if __cplusplus >= 201103L
set&
operator=(const set&) = default;
diff --git a/libstdc++-v3/include/debug/string b/libstdc++-v3/include/debug/string
index a8389528001..2209f88fd54 100644
--- a/libstdc++-v3/include/debug/string
+++ b/libstdc++-v3/include/debug/string
@@ -201,15 +201,7 @@ namespace __gnu_debug
__glibcxx_check_valid_constructor_range(__begin, __end)),
__gnu_debug::__base(__end), __a) { }
-#if __cplusplus < 201103L
- basic_string&
- operator=(const basic_string& __str)
- {
- this->_M_safe() = __str;
- _M_base() = __str;
- return *this;
- }
-#else
+#if __cplusplus >= 201103L
basic_string&
operator=(const basic_string&) = default;
diff --git a/libstdc++-v3/include/debug/vector b/libstdc++-v3/include/debug/vector
index 03fd9405cc9..b532a168e0e 100644
--- a/libstdc++-v3/include/debug/vector
+++ b/libstdc++-v3/include/debug/vector
@@ -71,18 +71,18 @@ namespace __gnu_debug
: _M_guaranteed_capacity(__n)
{ }
-#if __cplusplus >= 201103L
- _Safe_vector(_Safe_vector&& __x) noexcept
- : _Safe_vector()
- { __x._M_guaranteed_capacity = 0; }
-
_Safe_vector&
- operator=(const _Safe_vector&) noexcept
+ operator=(const _Safe_vector&) _GLIBCXX_NOEXCEPT
{
_M_update_guaranteed_capacity();
return *this;
}
+#if __cplusplus >= 201103L
+ _Safe_vector(_Safe_vector&& __x) noexcept
+ : _Safe_vector()
+ { __x._M_guaranteed_capacity = 0; }
+
_Safe_vector&
operator=(_Safe_vector&& __x) noexcept
{
@@ -234,16 +234,7 @@ namespace __debug
vector(_Base_ref __x)
: _Base(__x._M_ref) { }
-#if __cplusplus < 201103L
- vector&
- operator=(const vector& __x)
- {
- this->_M_safe() = __x;
- _M_base() = __x;
- this->_M_update_guaranteed_capacity();
- return *this;
- }
-#else
+#if __cplusplus >= 201103L
vector&
operator=(const vector&) = default;
On 11/11/21 9:41 pm, Jonathan Wakely wrote:
>
>
> On Wed, 10 Nov 2021 at 11:55, Jonathan Wakely <jwakely@redhat.com
> <mailto:jwakely@redhat.com>> wrote:
>
>
>
> On Tue, 9 Nov 2021 at 16:25, Jonathan Wakely <jwakely@redhat.com
> <mailto:jwakely@redhat.com>> wrote:
>
>
>
> On Mon, 8 Nov 2021 at 21:36, François Dumont
> <frs.dumont@gmail.com <mailto:frs.dumont@gmail.com>> wrote:
>
> Yet another version this time with only 1 guard
> implementation. The predicate to invalidate the safe
> iterators has been externalized.
>
> Ok to commit ?
>
>
> I like this version a lot - thanks for persisting with it.
>
>
>
> I'm seeing new failures with this:
>
> make check
> RUNTESTFLAGS="conformance.exp=23_containers/*/invalidation/*
> --target_board=unix/-D_GLIBCXX_DEBUG/-std=gnu++98"
>
> FAIL: 23_containers/deque/debug/invalidation/1.cc (test for excess
> errors)
> FAIL: 23_containers/list/debug/invalidation/1.cc (test for excess
> errors)
> FAIL: 23_containers/map/debug/invalidation/1.cc (test for excess
> errors)
> FAIL: 23_containers/multimap/debug/invalidation/1.cc (test for
> excess errors)
> FAIL: 23_containers/multiset/debug/invalidation/1.cc (test for
> excess errors)
> FAIL: 23_containers/set/debug/invalidation/1.cc (test for excess
> errors)
> FAIL: 23_containers/vector/debug/invalidation/1.cc (test for
> excess errors)
>
>
> It's caused by:
>
> --- a/libstdc++-v3/include/debug/safe_container.h
> +++ b/libstdc++-v3/include/debug/safe_container.h
> @@ -78,7 +78,6 @@namespace __gnu_debug
> { }
> #endif
>
> - public:
> // Copy assignment invalidate all iterators.
> _Safe_container&
> operator=(const _Safe_container&) _GLIBCXX_NOEXCEPT
>
>
> For C++98 mode that gets called explicitly by the user-provided copy
> assignment operators in the derived class.
>
> I'm testing the attached fix.
>
I am also testing a patch but yours looks nicer so go ahead. I'll just
complete it with some additional cleanup I did to suppress
_Safe_container::_M_safe() and reduce usages of _M_base().
Thanks
On Thu, 11 Nov 2021 at 21:33, François Dumont wrote:
> On 11/11/21 9:41 pm, Jonathan Wakely wrote:
>
>
>
> On Wed, 10 Nov 2021 at 11:55, Jonathan Wakely <jwakely@redhat.com> wrote:
>
>>
>>
>> On Tue, 9 Nov 2021 at 16:25, Jonathan Wakely <jwakely@redhat.com> wrote:
>>
>>>
>>>
>>> On Mon, 8 Nov 2021 at 21:36, François Dumont <frs.dumont@gmail.com>
>>> wrote:
>>>
>>>> Yet another version this time with only 1 guard implementation. The
>>>> predicate to invalidate the safe iterators has been externalized.
>>>>
>>>> Ok to commit ?
>>>>
>>>
>>> I like this version a lot - thanks for persisting with it.
>>>
>>>
>>
>> I'm seeing new failures with this:
>>
>> make check RUNTESTFLAGS="conformance.exp=23_containers/*/invalidation/*
>> --target_board=unix/-D_GLIBCXX_DEBUG/-std=gnu++98"
>>
>> FAIL: 23_containers/deque/debug/invalidation/1.cc (test for excess
>> errors)
>> FAIL: 23_containers/list/debug/invalidation/1.cc (test for excess errors)
>> FAIL: 23_containers/map/debug/invalidation/1.cc (test for excess errors)
>> FAIL: 23_containers/multimap/debug/invalidation/1.cc (test for excess
>> errors)
>> FAIL: 23_containers/multiset/debug/invalidation/1.cc (test for excess
>> errors)
>> FAIL: 23_containers/set/debug/invalidation/1.cc (test for excess errors)
>> FAIL: 23_containers/vector/debug/invalidation/1.cc (test for excess
>> errors)
>>
>
> It's caused by:
>
> --- a/libstdc++-v3/include/debug/safe_container.h
> +++ b/libstdc++-v3/include/debug/safe_container.h
> @@ -78,7 +78,6 @@ namespace __gnu_debug
> { }
> #endif
>
> - public:
> // Copy assignment invalidate all iterators.
> _Safe_container&
> operator=(const _Safe_container&) _GLIBCXX_NOEXCEPT
>
>
> For C++98 mode that gets called explicitly by the user-provided copy
> assignment operators in the derived class.
>
> I'm testing the attached fix.
>
> I am also testing a patch but yours looks nicer so go ahead.
>
I've pushed it to trunk now.
> I'll just complete it with some additional cleanup I did to suppress
> _Safe_container::_M_safe() and reduce usages of _M_base().
>
Sounds good, thanks.
@@ -78,7 +78,6 @@ namespace __gnu_debug
{ }
#endif
- public:
// Copy assignment invalidate all iterators.
_Safe_container&
operator=(const _Safe_container&) _GLIBCXX_NOEXCEPT
@@ -72,6 +72,7 @@ namespace __gnu_debug
{ return __it != __local_end; });
}
+ public:
void
_M_invalidate_all()
{
@@ -97,7 +97,12 @@ namespace __debug
typedef typename _Base::key_type key_type;
typedef typename _Base::value_type value_type;
+ typedef typename _Base::mapped_type mapped_type;
+ typedef typename _Base::pointer pointer;
+ typedef typename _Base::const_pointer const_pointer;
+ typedef typename _Base::reference reference;
+ typedef typename _Base::const_reference const_reference;
typedef __gnu_debug::_Safe_iterator<
_Base_iterator, unordered_map> iterator;
typedef __gnu_debug::_Safe_iterator<
@@ -106,6 +111,7 @@ namespace __debug
_Base_local_iterator, unordered_map> local_iterator;
typedef __gnu_debug::_Safe_local_iterator<
_Base_const_local_iterator, unordered_map> const_local_iterator;
+ typedef typename _Base::difference_type difference_type;
unordered_map() = default;
@@ -209,6 +215,11 @@ namespace __debug
return *this;
}
+ using _Base::get_allocator;
+ using _Base::empty;
+ using _Base::size;
+ using _Base::max_size;
+
void
swap(unordered_map& __x)
noexcept( noexcept(declval<_Base&>().swap(__x)) )
@@ -291,6 +302,10 @@ namespace __debug
return { _Base::cend(__b), this };
}
+ using _Base::bucket_count;
+ using _Base::max_bucket_count;
+ using _Base::bucket;
+
size_type
bucket_size(size_type __b) const
{
@@ -298,6 +313,8 @@ namespace __debug
return _Base::bucket_size(__b);
}
+ using _Base::load_factor;
+
float
max_load_factor() const noexcept
{ return _Base::max_load_factor(); }
@@ -538,9 +555,72 @@ namespace __debug
return { _Base::insert(__hint.base(), std::move(__nh)), this };
}
- using _Base::merge;
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
+ {
+ auto __size = __source.size();
+ _Base::merge(__source._M_base());
+ if (__source.size() == __size)
+ return;
+
+ if (__source.empty())
+ __source._M_invalidate_all();
+ else
+ {
+ auto __pred = [&__source](auto __it)
+ { return __source.count(__it->first) == 0; };
+ __source._M_invalidate_if(__pred);
+ __source._M_invalidate_local_if(__pred);
+ }
+ }
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
+ { merge(__source); }
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
+ {
+ auto __size = __source.size();
+ _Base::merge(__source._M_base());
+ if (__source.size() == __size)
+ return;
+
+ if (__source.empty())
+ __source._M_invalidate_all();
+ else
+ {
+ _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&
+ __base_src = __source;
+ auto __pred = [&__base_src](auto __it)
+ {
+ auto __rng = __base_src.equal_range(__it->first);
+ for (auto __rit = __rng.first; __rit != __rng.second; ++__rit)
+ {
+ if (__it == __rit)
+ return false;
+ }
+
+ return true;
+ };
+ __source._M_invalidate_if(__pred);
+ __source._M_invalidate_local_if(__pred);
+ }
+ }
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
+ { merge(__source); }
#endif // C++17
+ using _Base::hash_function;
+ using _Base::key_eq;
+
iterator
find(const key_type& __key)
{ return { _Base::find(__key), this }; }
@@ -567,6 +647,11 @@ namespace __debug
{ return { _Base::find(__k), this }; }
#endif
+ using _Base::count;
+#if __cplusplus > 201703L
+ using _Base::contains;
+#endif
+
std::pair<iterator, iterator>
equal_range(const key_type& __key)
{
@@ -605,6 +690,9 @@ namespace __debug
}
#endif
+ using _Base::operator[];
+ using _Base::at;
+
size_type
erase(const key_type& __key)
{
@@ -651,6 +739,9 @@ namespace __debug
return { __next, this };
}
+ using _Base::rehash;
+ using _Base::reserve;
+
_Base&
_M_base() noexcept { return *this; }
@@ -843,7 +934,12 @@ namespace __debug
typedef typename _Base::key_type key_type;
typedef typename _Base::value_type value_type;
+ typedef typename _Base::mapped_type mapped_type;
+ typedef typename _Base::pointer pointer;
+ typedef typename _Base::const_pointer const_pointer;
+ typedef typename _Base::reference reference;
+ typedef typename _Base::const_reference const_reference;
typedef __gnu_debug::_Safe_iterator<
_Base_iterator, unordered_multimap> iterator;
typedef __gnu_debug::_Safe_iterator<
@@ -852,6 +948,7 @@ namespace __debug
_Base_local_iterator, unordered_multimap> local_iterator;
typedef __gnu_debug::_Safe_local_iterator<
_Base_const_local_iterator, unordered_multimap> const_local_iterator;
+ typedef typename _Base::difference_type difference_type;
unordered_multimap() = default;
@@ -952,6 +1049,11 @@ namespace __debug
return *this;
}
+ using _Base::get_allocator;
+ using _Base::empty;
+ using _Base::size;
+ using _Base::max_size;
+
void
swap(unordered_multimap& __x)
noexcept( noexcept(declval<_Base&>().swap(__x)) )
@@ -1034,6 +1136,10 @@ namespace __debug
return { _Base::cend(__b), this };
}
+ using _Base::bucket_count;
+ using _Base::max_bucket_count;
+ using _Base::bucket;
+
size_type
bucket_size(size_type __b) const
{
@@ -1192,9 +1298,37 @@ namespace __debug
return { _Base::insert(__hint.base(), std::move(__nh)), this };
}
- using _Base::merge;
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
+ {
+ _Base::merge(__source._M_base());
+ __source._M_invalidate_all();
+ }
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
+ { merge(__source); }
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
+ {
+ _Base::merge(__source._M_base());
+ __source._M_invalidate_all();
+ }
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
+ { merge(__source); }
#endif // C++17
+ using _Base::hash_function;
+ using _Base::key_eq;
+
iterator
find(const key_type& __key)
{ return { _Base::find(__key), this }; }
@@ -1221,6 +1355,11 @@ namespace __debug
{ return { _Base::find(__k), this }; }
#endif
+ using _Base::count;
+#if __cplusplus > 201703L
+ using _Base::contains;
+#endif
+
std::pair<iterator, iterator>
equal_range(const key_type& __key)
{
@@ -1309,6 +1448,9 @@ namespace __debug
return { __next, this };
}
+ using _Base::rehash;
+ using _Base::reserve;
+
_Base&
_M_base() noexcept { return *this; }
@@ -88,6 +88,7 @@ namespace __debug
public:
typedef typename _Base::size_type size_type;
+ typedef typename _Base::difference_type difference_type;
typedef typename _Base::hasher hasher;
typedef typename _Base::key_equal key_equal;
typedef typename _Base::allocator_type allocator_type;
@@ -95,6 +96,10 @@ namespace __debug
typedef typename _Base::key_type key_type;
typedef typename _Base::value_type value_type;
+ typedef typename _Base::pointer pointer;
+ typedef typename _Base::const_pointer const_pointer;
+ typedef typename _Base::reference reference;
+ typedef typename _Base::const_reference const_reference;
typedef __gnu_debug::_Safe_iterator<
_Base_iterator, unordered_set> iterator;
typedef __gnu_debug::_Safe_iterator<
@@ -203,6 +208,11 @@ namespace __debug
return *this;
}
+ using _Base::get_allocator;
+ using _Base::empty;
+ using _Base::size;
+ using _Base::max_size;
+
void
swap(unordered_set& __x)
noexcept( noexcept(declval<_Base&>().swap(__x)) )
@@ -285,6 +295,9 @@ namespace __debug
return { _Base::cend(__b), this };
}
+ using _Base::bucket_count;
+ using _Base::max_bucket_count;
+
size_type
bucket_size(size_type __b) const
{
@@ -292,6 +305,9 @@ namespace __debug
return _Base::bucket_size(__b);
}
+ using _Base::bucket;
+ using _Base::load_factor;
+
float
max_load_factor() const noexcept
{ return _Base::max_load_factor(); }
@@ -303,6 +319,9 @@ namespace __debug
_Base::max_load_factor(__f);
}
+ using _Base::rehash;
+ using _Base::reserve;
+
template<typename... _Args>
std::pair<iterator, bool>
emplace(_Args&&... __args)
@@ -423,9 +442,71 @@ namespace __debug
return { _Base::insert(__hint.base(), std::move(__nh)), this };
}
- using _Base::merge;
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
+ {
+ auto __size = __source.size();
+ _Base::merge(__source._M_base());
+ if (__source.size() == __size)
+ return;
+
+ if (__source.empty())
+ __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);
+ }
+ }
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
+ { merge(__source); }
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
+ {
+ auto __size = __source.size();
+ _Base::merge(__source._M_base());
+ if (__source.size() == __size)
+ return;
+
+ if (__source.empty())
+ __source._M_invalidate_all();
+ else
+ {
+ _GLIBCXX_STD_C::unordered_multiset<_Value, _H2, _P2, _Alloc>&
+ __base_src = __source;
+ auto __pred = [&__base_src](auto __it)
+ {
+ auto __rng = __base_src.equal_range(*__it);
+ for (auto __rit = __rng.first; __rit != __rng.second; ++__rit)
+ {
+ if (__it == __rit)
+ return false;
+ }
+
+ return true;
+ };
+ __source._M_invalidate_if(__pred);
+ __source._M_invalidate_local_if(__pred);
+ }
+ }
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
+ { merge(__source); }
#endif // C++17
+ using _Base::hash_function;
+ using _Base::key_eq;
+
iterator
find(const key_type& __key)
{ return { _Base::find(__key), this }; }
@@ -452,6 +533,12 @@ namespace __debug
{ return { _Base::find(__k), this }; }
#endif
+ using _Base::count;
+
+#if __cplusplus > 201703L
+ using _Base::contains;
+#endif
+
std::pair<iterator, iterator>
equal_range(const key_type& __key)
{
@@ -707,6 +794,7 @@ namespace __debug
public:
typedef typename _Base::size_type size_type;
+ typedef typename _Base::difference_type difference_type;
typedef typename _Base::hasher hasher;
typedef typename _Base::key_equal key_equal;
typedef typename _Base::allocator_type allocator_type;
@@ -714,6 +802,10 @@ namespace __debug
typedef typename _Base::key_type key_type;
typedef typename _Base::value_type value_type;
+ typedef typename _Base::pointer pointer;
+ typedef typename _Base::const_pointer const_pointer;
+ typedef typename _Base::reference reference;
+ typedef typename _Base::const_reference const_reference;
typedef __gnu_debug::_Safe_iterator<
_Base_iterator, unordered_multiset> iterator;
typedef __gnu_debug::_Safe_iterator<
@@ -822,6 +914,11 @@ namespace __debug
return *this;
}
+ using _Base::get_allocator;
+ using _Base::empty;
+ using _Base::size;
+ using _Base::max_size;
+
void
swap(unordered_multiset& __x)
noexcept( noexcept(declval<_Base&>().swap(__x)) )
@@ -904,6 +1001,9 @@ namespace __debug
return { _Base::cend(__b), this };
}
+ using _Base::bucket_count;
+ using _Base::max_bucket_count;
+
size_type
bucket_size(size_type __b) const
{
@@ -911,6 +1011,9 @@ namespace __debug
return _Base::bucket_size(__b);
}
+ using _Base::bucket;
+ using _Base::load_factor;
+
float
max_load_factor() const noexcept
{ return _Base::max_load_factor(); }
@@ -922,6 +1025,9 @@ namespace __debug
_Base::max_load_factor(__f);
}
+ using _Base::rehash;
+ using _Base::reserve;
+
template<typename... _Args>
iterator
emplace(_Args&&... __args)
@@ -1037,9 +1143,36 @@ namespace __debug
return { _Base::insert(__hint.base(), std::move(__nh)), this };
}
- using _Base::merge;
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
+ {
+ _Base::merge(__source._M_base());
+ __source._M_invalidate_all();
+ }
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
+ { merge(__source); }
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
+ {
+ _Base::merge(__source._M_base());
+ __source._M_invalidate_all();
+ }
+
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
+ { merge(__source); }
#endif // C++17
+ using _Base::hash_function;
+ using _Base::key_eq;
+
iterator
find(const key_type& __key)
{ return { _Base::find(__key), this }; }
@@ -1066,6 +1199,12 @@ namespace __debug
{ return { _Base::find(__k), this }; }
#endif
+ using _Base::count;
+
+#if __cplusplus > 201703L
+ using _Base::contains;
+#endif
+
std::pair<iterator, iterator>
equal_range(const key_type& __key)
{
new file mode 100644
@@ -0,0 +1,31 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_map>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_map<int, int>;
+
+void
+test01()
+{
+ test_type c0{ { 1, 1 }, { 2, 2 }, { 3, 3 }, { 5, 5 }, { 6, 6 } };
+ test_type c1{ { 1, 1 }, { 2, 2 }, { 3, 3 }, { 4, 4 } };
+
+ auto it2 = c1.find(2);
+ auto it4 = c1.find(4);
+ VERIFY( it2->second == 2 );
+ VERIFY( it4->second == 4 );
+
+ c0.merge(c1);
+
+ VERIFY( it2->second == 2 );
+ VERIFY( it4 != it2 ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
new file mode 100644
@@ -0,0 +1,32 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_map>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_map<int, int>;
+
+void
+test01()
+{
+ test_type c0{ { 1, 1 }, { 2, 2 }, { 3, 3 }, { 5, 5 }, { 6, 6 } };
+ test_type c1{ { 1, 1 }, { 2, 2 }, { 3, 3 }, { 4, 4 } };
+
+ auto it2 = c1.find(2);
+ auto it4 = c1.find(4);
+ VERIFY( it2->second == 2 );
+ VERIFY( it4->second == 4 );
+
+ c0.merge(std::move(c1));
+
+ VERIFY( it2->second == 2 );
+ VERIFY( it2 != it4 ); // Invalid iterator.
+}
+
+
+int
+main()
+{
+ test01();
+}
new file mode 100644
@@ -0,0 +1,42 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_map>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_map<int, int>;
+
+void
+test01()
+{
+ test_type c0
+ {
+ { 1, 1 }, { 2, 2 }, { 3, 3 },
+ { 5, 5 }, { 6, 6 }, { 7, 7 }
+ };
+ std::unordered_multimap<int, int> c1
+ {
+ { 1, 1 }, { 1, 1 }, { 2, 2 }, { 2, 2 },
+ { 3, 3 }, { 3, 3 }, { 4, 4 }, { 4, 4 },
+ { 5, 5 }
+ };
+
+ auto it1 = c1.find(1);
+ auto it41 = c1.find(4);
+ auto it42 = it41;
+ ++it42;
+ VERIFY( it42->second == 4 );
+
+ c0.merge(c1);
+
+ VERIFY( it1->second == 1 );
+ VERIFY( c1.count(4) == 1 );
+ VERIFY( it41 != it42 ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
new file mode 100644
@@ -0,0 +1,42 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_map>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_map<int, int>;
+
+void
+test01()
+{
+ test_type c0
+ {
+ { 1, 1 }, { 2, 2 }, { 3, 3 },
+ { 5, 5 }, { 6, 6 }, { 7, 7 }
+ };
+ std::unordered_multimap<int, int> c1
+ {
+ { 1, 1 }, { 1, 1 }, { 2, 2 }, { 2, 2 },
+ { 3, 3 }, { 3, 3 }, { 4, 4 }, { 4, 4 },
+ { 5, 5 }
+ };
+
+ auto it1 = c1.find(1);
+ auto it41 = c1.find(4);
+ auto it42 = it41;
+ ++it42;
+ VERIFY( it42->second == 4 );
+
+ c0.merge(std::move(c1));
+
+ VERIFY( it1->second == 1 );
+ VERIFY( c1.count(4) == 1 );
+ VERIFY( it41 != it42 ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
new file mode 100644
@@ -0,0 +1,32 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_map>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_multimap<int, int>;
+
+void
+test01()
+{
+ test_type c0
+ {
+ { 1, 1 }, { 1, 1 }, { 2, 2 },
+ { 2, 2 }, { 3, 3 }, { 3, 3 }
+ };
+ test_type c1 = c0;
+
+ auto it = c1.find(2);
+ VERIFY( it->second == 2 );
+
+ c0.merge(c1);
+
+ VERIFY( it != c1.end() ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
new file mode 100644
@@ -0,0 +1,32 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_map>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_multimap<int, int>;
+
+void
+test01()
+{
+ test_type c0
+ {
+ { 1, 1 }, { 1, 1 }, { 2, 2 },
+ { 2, 2 }, { 3, 3 }, { 3, 3 }
+ };
+ test_type c1 = c0;
+
+ auto it = c1.find(2);
+ VERIFY( it->second == 2 );
+
+ c0.merge(std::move(c1));
+
+ VERIFY( it != c1.end() ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
new file mode 100644
@@ -0,0 +1,32 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_map>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_multimap<int, int>;
+
+void
+test01()
+{
+ test_type c0
+ {
+ { 1, 1 }, { 1, 1 }, { 2, 2 },
+ { 2, 2 }, { 3, 3 }, { 3, 3 }
+ };
+ std::unordered_map<int, int> c1{ { 1, 1 }, { 2, 2 }, { 3, 3 } };
+
+ auto it = c1.find(2);
+ VERIFY( it->second == 2 );
+
+ c0.merge(c1);
+
+ VERIFY( it != c1.end() ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
new file mode 100644
@@ -0,0 +1,32 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_map>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_multimap<int, int>;
+
+void
+test01()
+{
+ test_type c0
+ {
+ { 1, 1 }, { 1, 1 }, { 2, 2 },
+ { 2, 2 }, { 3, 3 }, { 3, 3 }
+ };
+ std::unordered_map<int, int> c1{ { 1, 1 }, { 2, 2 }, { 3, 3 } };
+
+ auto it = c1.find(2);
+ VERIFY( it->second == 2 );
+
+ c0.merge(std::move(c1));
+
+ VERIFY( it != c1.end() ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
new file mode 100644
@@ -0,0 +1,28 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_set>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_multiset<int>;
+
+void
+test01()
+{
+ test_type c0{ 1, 1, 2, 2, 3, 3 };
+ test_type c1 = c0;
+
+ auto it = c1.find(2);
+ VERIFY( *it == 2 );
+
+ c0.merge(c1);
+
+ VERIFY( it != c1.end() ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
new file mode 100644
@@ -0,0 +1,28 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_set>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_multiset<int>;
+
+void
+test01()
+{
+ test_type c0{ 1, 1, 2, 2, 3, 3 };
+ test_type c1 = c0;
+
+ auto it = c1.find(2);
+ VERIFY( *it == 2 );
+
+ c0.merge(std::move(c1));
+
+ VERIFY( it != c1.end() ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
new file mode 100644
@@ -0,0 +1,28 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_set>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_multiset<int>;
+
+void
+test01()
+{
+ test_type c0{ 1, 1, 2, 2, 3, 3 };
+ std::unordered_set<int> c1{ 1, 2, 3 };
+
+ auto it = c1.find(2);
+ VERIFY( *it == 2 );
+
+ c0.merge(c1);
+
+ VERIFY( it != c1.end() ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
new file mode 100644
@@ -0,0 +1,28 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_set>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_multiset<int>;
+
+void
+test01()
+{
+ test_type c0{ 1, 1, 2, 2, 3, 3 };
+ std::unordered_set<int> c1{ 1, 2, 3 };
+
+ auto it = c1.find(2);
+ VERIFY( *it == 2 );
+
+ c0.merge(std::move(c1));
+
+ VERIFY( it != c1.end() ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
new file mode 100644
@@ -0,0 +1,31 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_set>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_set<int>;
+
+void
+test01()
+{
+ test_type c0{ 1, 2, 3, 5, 6 };
+ test_type c1{ 1, 2, 3, 4 };
+
+ auto it2 = c1.find(2);
+ auto it4 = c1.find(4);
+ VERIFY( *it2 == 2 );
+ VERIFY( *it4 == 4 );
+
+ c0.merge(c1);
+
+ VERIFY( *it2 == 2 );
+ VERIFY( it2 != it4 ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
new file mode 100644
@@ -0,0 +1,31 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_set>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_set<int>;
+
+void
+test01()
+{
+ test_type c0{ 1, 2, 3, 5, 6 };
+ test_type c1{ 1, 2, 3, 4 };
+
+ auto it2 = c1.find(2);
+ auto it4 = c1.find(4);
+ VERIFY( *it2 == 2 );
+ VERIFY( *it4 == 4 );
+
+ c0.merge(std::move(c1));
+
+ VERIFY( *it2 == 2 );
+ VERIFY( it2 != it4 ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
new file mode 100644
@@ -0,0 +1,33 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_set>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_set<int>;
+
+void
+test01()
+{
+ test_type c0{ 1, 2, 3, 5, 6, 7 };
+ std::unordered_multiset<int> c1{ 1, 1, 2, 2, 3, 3, 4, 4, 5 };
+
+ auto it1 = c1.find(1);
+ auto it41 = c1.find(4);
+ auto it42 = it41;
+ ++it42;
+ VERIFY( *it42 == 4 );
+
+ c0.merge(c1);
+
+ VERIFY( *it1 == 1 );
+ VERIFY( c1.count(4) == 1 );
+ VERIFY( it41 != it42 ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
new file mode 100644
@@ -0,0 +1,33 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_set>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_set<int>;
+
+void
+test01()
+{
+ test_type c0{ 1, 2, 3, 5, 6, 7 };
+ std::unordered_multiset<int> c1{ 1, 1, 2, 2, 3, 3, 4, 4, 5 };
+
+ auto it1 = c1.find(1);
+ auto it41 = c1.find(4);
+ auto it42 = it41;
+ ++it42;
+ VERIFY( *it42 == 4 );
+
+ c0.merge(std::move(c1));
+
+ VERIFY( *it1 == 1 );
+ VERIFY( c1.count(4) == 1 );
+ VERIFY( it41 != it42 ); // Invalid iterator.
+}
+
+int
+main()
+{
+ test01();
+}
@@ -24,7 +24,11 @@
#include <locale>
#if __cplusplus >= 201103L
# include <unordered_map>
+# ifdef _GLIBCXX_DEBUG
+namespace unord = std::_GLIBCXX_STD_C;
+# else
namespace unord = std;
+# endif
#else
# include <tr1/unordered_map>
namespace unord = std::tr1;