[PATCH][Hashtable 5/6] Remove H1/H2 template parameters

[Jonathan Wakely]

On 26/08/20 16:30 +0100, Jonathan Wakely wrote:
>On 25/08/20 15:30 +0100, Jonathan Wakely wrote:
>>On 17/08/20 19:13 +0200, François Dumont via Libstdc++ wrote:
>>>Hi
>>>
>>>Â Â Â  Here is the new proposal.
>>>
>>>Â Â Â  As we can't remove template parameters I simply restore those 
>>>that I tried to pass differently _H2 and _ExtractKey, so 
>>>eventually I only remove usage of _Hash which I renamed in 
>>>_Unused. Maybe I can keep the doc about it in hashtable.h and just 
>>>add a remark saying that it is now unused.
>>>
>>>Â Â Â  For _RangeHash, formerly _H2, and _ExtractKey I just stop 
>>>maintaining any storage. When we need those I always use a value 
>>>initialized instance. I kind of prefer the value initialization 
>>>syntax because you can't confuse it with a function call but let 
>>>me know if it is wrong and I should use _ExtractKey() or 
>>>_RangeHash(). I also add some static assertions about those types 
>>>regarding their noexcept qualifications.
>>>
>>>Â Â Â  I also included in this patch the few changes left from 
>>>[Hashtable 0/6] which are mostly _M_insert_unique_node and 
>>>_M_insert_multi_node signature cleanup as the key part can be 
>>>extracted from the inserted node.
>>>
>>>Â Â Â  Tested under Linux x86_64, ok to commit ?
>>>
>>>François
>>>
>>>On 06/08/20 11:27 am, Jonathan Wakely wrote:
>>>>On 06/08/20 08:35 +0200, François Dumont wrote:
>>>>>On 17/07/20 1:35 pm, Jonathan Wakely wrote:
>>>>>>I really like the general idea of getting rid of some of the
>>>>>>complexity and not supporting infinite customization. But we can do
>>>>>>that without changing mangled names of the _Hashtable specialiations.
>>>>>>
>>>>>>
>>>>>I didn't thought we need to keep abi compatibility for extensions.
>>>>
>>>>These aren't extensions though, they're part of std::unordered_map
>>>>etc.
>>>>
>>>>Just because something like _Vector_base is an internal type rather
>>>>than something defined in the standard doesn't mean we can just change
>>>>its ABI, because that would change the ABI of std::vector. It the same
>>>>here.
>>>>
>>>>Changing _Hashtable affects all users of std::unordered_map etc.
>>>>
>>>>
>>>
>>
>>>diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
>>>index 7b772a475e3..1ba32a3c7e2 100644
>>>--- a/libstdc++-v3/include/bits/hashtable.h
>>>+++ b/libstdc++-v3/include/bits/hashtable.h
>>>@@ -311,35 +303,37 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>>		    "Cache the hash code or qualify your functors involved"
>>>		    " in hash code and bucket index computation with noexcept");
>>>
>>>-      // When hash codes are cached local iterator inherits from H2 functor
>>>-      // which must then be default constructible.
>>>-      static_assert(__if_hash_cached<is_default_constructible<_H2>>::value,
>>>+      // To get bucket index we need _RangeHash not to throw.
>>>+      static_assert(is_nothrow_default_constructible<_RangeHash>::value,
>>>		    "Functor used to map hash code to bucket index"
>>>-		    " must be default constructible");
>>>+		    " is nothrow default constructible");
>>
>>Please phrase this as "must be nothrow default constructible".
>>
>>>+      static_assert(noexcept(
>>>+	std::declval<const _RangeHash&>()((std::size_t)0, (std::size_t)0)),
>>>+		"Functor used to map hash code to bucket index is noexcept");
>>
>>Same here, "must be noexcept".
>>
>>Otherwise this looks great, thanks. Please push.
>
>I'm seeing new FAILures with this:
>
>FAIL: 20_util/function_objects/searchers.cc (test for excess errors)
>UNRESOLVED: 20_util/function_objects/searchers.cc compilation failed to produce executable
>FAIL: experimental/functional/searchers.cc (test for excess errors)
>UNRESOLVED: experimental/functional/searchers.cc compilation failed to produce executable
>
>It looks like what you committed is not what you sent for review. The
>patch sent for review has:
>
>   /// Specialization: hash function and range-hashing function, no
>   /// caching of hash codes.
>   /// Provides typedef and accessor required by C++ 11.
>   template<typename _Key, typename _Value, typename _ExtractKey,
>-          typename _H1, typename _H2>
>-    struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
>-                          _Default_ranged_hash, false>
>+          typename _Hash, typename _RangeHash, typename _Unused>
>+    struct _Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash,
>+                          _Unused, false>
>     : private _Hashtable_ebo_helper<0, _ExtractKey>,
>-      private _Hashtable_ebo_helper<1, _H1>,
>-      private _Hashtable_ebo_helper<2, _H2>
>+      private _Hashtable_ebo_helper<1, _Hash>
>     {
>
>
>But what you committed has:
>
>   /// Specialization: hash function and range-hashing function, no
>   /// caching of hash codes.
>   /// Provides typedef and accessor required by C++ 11.
>   template<typename _Key, typename _Value, typename _ExtractKey,
>-          typename _H1, typename _H2>
>-    struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
>-                          _Default_ranged_hash, false>
>-    : private _Hashtable_ebo_helper<0, _ExtractKey>,
>-      private _Hashtable_ebo_helper<1, _H1>,
>-      private _Hashtable_ebo_helper<2, _H2>
>+          typename _Hash, typename _RangeHash, typename _Unused>
>+    struct _Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash,
>+                          _Unused, false>
>+    : private _Hashtable_ebo_helper<0, _Hash>
>     {
>
>
>Note that you've changed the type of the base class from:
>
>+      private _Hashtable_ebo_helper<1, _Hash>
>
>to
>
>+      private _Hashtable_ebo_helper<0, _Hash>
>
>This causes an ambiguity:
>
>/home/jwakely/src/gcc/build/x86_64-pc-linux-gnu/libstdc++-v3/include/bits/hashtable_policy.h:1706: error: 'std::__detail::_Hashtable_ebo_helper<0, test03()::<unnamed struct>, true>' is an ambiguous base of 'std::__detail::_Hashtable_base<char, std::pair<const char, long int>, std::__detail::_Select1st, test03()::<unnamed struct>, test03()::<unnamed struct>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, false, true> >'
>
>However, what I don't understand is why we are storing that _Hash type
>more than once as a base class. That seems wrong (but not something we
>can change without ABI impact).

Ah, we're not storing it more than once.

The problem is:

   template<typename _Key, typename _Value,
	   typename _ExtractKey, typename _Equal,
	   typename _H1, typename _H2, typename _Hash, typename _Traits>
   struct _Hashtable_base
   : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
			   _Traits::__hash_cached::value>,
     private _Hashtable_ebo_helper<0, _Equal>

This has a base of _Hashtable_ebo_helper<0, _Equal> so it used to
have these bases:

_Hashtable_ebo_helper<0, _ExtractKey>
_Hashtable_ebo_helper<1, _Hash>
_Hashtable_ebo_helper<2, _RangeHash>
_Hashtable_ebo_helper<0, _Equal>

but after your change it has these bases:

_Hashtable_ebo_helper<0, _Hash>
_Hashtable_ebo_helper<0, _Equal>

In the case
where _Equal and _Hash are the same type (which is what I was testing
in the test that fail, because I'm sneaky) that means:

_Hashtable_ebo_helper<0, T>
_Hashtable_ebo_helper<0, T>

which is obviously ambiguous.

I think the _hash_code_base should still use the index 1 for its base
class, i.e. _Hashtable_ebo_helper<1, _Hash>. That way we have these:

_Hashtable_ebo_helper<1, _Hash>
_Hashtable_ebo_helper<0, _Equal>

which works even if they're the same types.