[PATCH] Hashtable PR96088

[Jonathan Wakely]

On 22/05/21 18:35 +0200, François Dumont wrote:
>This was indeed the right approach.
>
>    The only minor drawback is that __is_noexcept_invocable<> combines 
>noexcept qualification of the conversion and of the hash functor. So 
>if the hash functor is not noexcept we could end up creating 
>temporaries for nothing.
>
>    So I've eventually used this condition:
>
>__and_<__is_nothrow_invocable<_Hash&, const key_type&>,
>         __not_<__is_nothrow_invocable<_Hash&, _Kt>>>::value,
>
>    so that we do not create a temporary key_type if invoking _Hash 
>with it can still throw.
>
>    libstdc++: Limit allocation on iterator insertion in Hashtable [PR 
>96088]
>
>    When inserting into unordered_multiset or unordered_multimap first 
>instantiate
>    the node to store and compute the hash code from it to avoid a 
>potential
>    intermediate key_type instantiation.
>
>    When inserting into unordered_set or unordered_map check if 
>invoking the hash
>    functor with container key_type is noexcept and invoking the same 
>hash functor
>    with key part of the iterator value_type can throw. In this case 
>create a
>    temporary key_type instance at Hashtable level and use it to 
>compute the hash
>    code. This temporary instance is moved to the final storage 
>location if needed.
>
>    libstdc++-v3/ChangeLog:
>
>            PR libstdc++/96088
>            * include/bits/hashtable_policy.h (_Select2nd): New.
>            (_NodeBuilder<>): New.
>            (_ReuseOrAllocNode<>::operator()): Use variadic template args.
>            (_AllocNode<>::operator()): Likewise.
>            * include/bits/hashtable.h
>            (_Hashtable<>::__node_builder_t): New.
>(_Hashtable<>::_M_insert_unique<>(_Kt&&, _Arg&&, const _NodeGenerator&)):
>             New.
>            (_Hashtable<>::_S_forward_key): New.
>            (_Hashtable<>::_M_insert): Use latter.
>            (_Hashtable<>::_M_insert(const_iterator, _Arg&&, const 
>_NodeGenerator&, false_type)):
>            Instantiate node first, compute hash code second.
>            * testsuite/23_containers/unordered_map/96088.cc: New test.
>            * testsuite/23_containers/unordered_multimap/96088.cc: New 
>test.
>            * testsuite/23_containers/unordered_multiset/96088.cc: New 
>test.
>            * testsuite/23_containers/unordered_set/96088.cc: New test.
>            * testsuite/util/replacement_memory_operators.h
>            (counter::_M_increment): New.
>            (counter::_M_decrement): New.
>            (counter::reset()): New.
>
>Tested under Linux x64.
>
>Ok to commit ?

OK for trunk, thanks.