Re: [PATCH][Hashtable 5/6] Remove H1/H2 template parameters
Deeply sorry, I indeed didn't sent the patch I wanted to commit. It was
in 3 commits on my side and it looks like I had miss the last one
regarding the changes for _ExtractKey.
But moreover I had change the ebo helper index wrongly, I missed the abi
change here, thanks for fixing it.
On 26/08/20 6:45 pm, Jonathan Wakely wrote:
On 26/08/20 16:58 +0100, Jonathan Wakely wrote:
On 26/08/20 16:55 +0100, Jonathan Wakely wrote:
On 26/08/20 16:30 +0100, Jonathan Wakely wrote:
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
- 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
- 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()::struct>, true>' is an ambiguous base of
'std::__detail::_Hashtable_baseint>, std::__detail::_Select1st, test03()::,
test03()::, std::__detail::_Mod_range_hashing,
std::__detail::_Default_ranged_hash,
std::__detail::_Hashtable_traits >'
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
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.
Here's a minimal test:
#include
struct Evil : std::hash, std::equal_to
{
};
int main()
{
std::unordered_map h;
h.key_eq();
}
This fails on current trunk.
Fixed by the attached patch.
Tested powerpc64le-linux, committed to trunk.
Re: [PATCH][Hashtable 5/6] Remove H1/H2 template parameters
On 26/08/20 16:58 +0100, Jonathan Wakely wrote:
On 26/08/20 16:55 +0100, Jonathan Wakely wrote:
On 26/08/20 16:30 +0100, Jonathan Wakely wrote:
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
-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
-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()::, true>' is an ambiguous base of
'std::__detail::_Hashtable_base, std::__detail::_Select1st,
test03()::, test03()::, std::__detail::_Mod_range_hashing,
std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits >'
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
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.
Here's a minimal test:
#include
struct Evil : std::hash, std::equal_to
{
};
int main()
{
std::unordered_map h;
h.key_eq();
}
This fails on current trunk.
Fixed by the attached patch.
Tested powerpc64le-linux, committed to trunk.
commit 9f9c0549dd42e85e2500ca67cef89dddb142c0c7
Author: Jonathan Wakely
Date: Wed Aug 26 17:30:31 2020
libstdc++: Fix regression in hash containers
A recent change altered the layout of EBO-helper base classes, resulting
in an ambiguity when the hash function and equality predicate are the
same type.
This modifies the type of one of the base classes, so that we don't get
two base classes of the same type.
libstdc++-v3/ChangeLog:
* include/bits/hashtable_policy.h (_Hash_code_base): Change
index of _Hashtable_ebo_helper base class.
* testsuite/23_containers/unordered_map/dup_types.cc: New test.
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 38bd5ae4e81..0109ef86a7b 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -1190,10 +1190,10 @@ namespace __detail
Re: [PATCH][Hashtable 5/6] Remove H1/H2 template parameters
On 26/08/20 16:55 +0100, Jonathan Wakely wrote:
On 26/08/20 16:30 +0100, Jonathan Wakely wrote:
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
-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
-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()::, true>' is an ambiguous base of
'std::__detail::_Hashtable_base, std::__detail::_Select1st,
test03()::, test03()::, std::__detail::_Mod_range_hashing,
std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits >'
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
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.
Here's a minimal test:
#include
struct Evil : std::hash, std::equal_to
{
};
int main()
{
std::unordered_map h;
h.key_eq();
}
This fails on current trunk.
Re: [PATCH][Hashtable 5/6] Remove H1/H2 template parameters
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>::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()((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
-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
-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>
Re: [PATCH][Hashtable 5/6] Remove H1/H2 template parameters
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>::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()((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
-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
-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,
Re: [PATCH][Hashtable 5/6] Remove H1/H2 template parameters
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>::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()((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.
Re: [PATCH][Hashtable 5/6] Remove H1/H2 template parameters
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 @@ -69,21 +69,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * and returns a bool-like value that is true if the two objects * are considered equal. * - * @tparam _H1 The hash function. A unary function object with + * @tparam _Hash The hash function. A unary function object with * argument type _Key and result type size_t. Return values should * be distributed over the entire range [0, numeric_limits:::max()]. * - * @tparam _H2 The range-hashing function (in the terminology of + * @tparam _RangeHash The range-hashing function (in the terminology of * Tavori and Dreizin). A binary function object whose argument * types and result type are all size_t. Given arguments r and N, * the return value is in the range [0, N). * - * @tparam _Hash The ranged hash function (Tavori and Dreizin). A - * binary function whose argument types are _Key and size_t and - * whose result type is size_t. Given arguments k and N, the - * return value is in the range [0, N). Default: hash(k, N) = - * h2(h1(k), N). If _Hash is anything other than the default, _H1 - * and _H2 are ignored. + * @tparam _Unused Not used. * * @tparam _RehashPolicy Policy class with three members, all of * which govern the bucket count. _M_next_bkt(n) returns a bucket @@ -91,9 +86,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * bucket count appropriate for an element count of n. * _M_need_rehash(n_bkt, n_elt, n_ins) determines whether, if the * current bucket count is n_bkt and the current element count is - * n_elt, we need to increase the bucket count. If so, returns - * make_pair(true, n), where n is the new bucket count. If not, - * returns make_pair(false, ) + * n_elt, we need to increase the bucket count for n_ins insertions. + * If so, returns make_pair(true, n), where n is the new bucket count. If + * not, returns make_pair(false, ) * * @tparam _Traits Compile-time class with three boolean * std::integral_constant members: __cache_hash_code, __constant_iterators, @@ -168,19 +163,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION */ template class _Hashtable : public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, - _H1, _H2, _Hash, _Traits>, + _Hash, _RangeHash, _Unused, _Traits>, public __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>, + _Hash, _RangeHash, _Unused, + _RehashPolicy, _Traits>, public __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, _Traits>, + _Hash, _RangeHash, _Unused, + _RehashPolicy, _Traits>, public __detail::_Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, -_H1, _H2, _Hash, _RehashPolicy, _Traits>, +_Hash, _RangeHash, _Unused, +_RehashPolicy, _Traits>, public
Re: [PATCH][Hashtable 5/6] Remove H1/H2 template parameters
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.
Re: [PATCH][Hashtable 5/6] Remove H1/H2 template parameters
On 17/07/20 1:35 pm, Jonathan Wakely wrote: On 19/12/19 20:22 +0100, François Dumont wrote: Because of this change printers.py has to be updated too. François On 11/17/19 10:15 PM, François Dumont wrote: H1 used to be a reference to the user Hash, now _Hashtable and unordered types agree on the same Hash type which is more intuitive. I also chose to not support anymore a stateful ranged hash functor. We only use _Mod_range_hashing and _Mask_range_hashing. Thanks to this simplification _M_bucket_index can also be simplified.    * include/bits/hashtable_policy.h (_Hashtable<>): Remove _H1 and _H2    template parameters.    (_Hastable_base<>): Likewise.    (_Default_ranged_hash): Remove.    (_Prime_rehash_policy::__ranged_hash): New.    (_Power2_rehash_policy::__ranged_hash): New.    (_Map_base<>): Remove _H1 and _H2 template parameters.    (_Insert_base<>): Likewise.    (_Insert<>): Likewise.    (_Rehash_base<>): Likewise.    (_Local_iterator_base<>): Remove _H1 and _H2 template parameters and add    _RangedHash.    (_Hash_code_base<>): Likewise.    (_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,    __hash_not_cached_t>): Remove.    (_Hash_code_base<>::_M_bucket_index(const _Key&, __hash_code, size_t)):    Replace by...    (_Hash_code_base<>::_M_bucket_index(__hash_code, size_t)): ...this.    (_Local_iterator<>): Remove _H1 and _H2 template parameters.    (_Local_const_iterator<>): Likewise.    (_Equality<>): Likewise.    * include/bits/hashtable.h (_Hashtable<>): Remove _H1 and _H2 template    parameters.    * include/bits/node_handle.h: Adapt.    * include/bits/unordered_map.h: Adapt.    * include/bits/unordered_set.h: Adapt.    * testsuite/23_containers/unordered_set/hash_policy/26132.cc: Adapt.    * testsuite/23_containers/unordered_set/hash_policy/71181.cc: Adapt.    * testsuite/23_containers/unordered_set/hash_policy/load_factor.cc:    Adapt.    * testsuite/23_containers/unordered_set/hash_policy/rehash.cc: Adapt.    * testsuite/23_containers/unordered_set/insert/hash_policy.cc: Adapt.    * testsuite/23_containers/unordered_set/max_load_factor/robustness.cc:    Adapt.    * testsuite/performance/23_containers/insert/54075.cc: Adapt.    * testsuite/performance/23_containers/insert_erase/41975.cc: Adapt.    * testsuite/performance/23_containers/insert_erase/    unordered_small_size.cc: Adapt. Tested under Linux x86_64. François diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 41be821782d..9dadc62e328 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -69,31 +69,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * and returns a bool-like value that is true if the two objects * are considered equal. * - * @tparam _H1 The hash function. A unary function object with + * @tparam _Hash The hash function. A unary function object with Renaming this to _Hash is great, that makes the code much easier to understand for a casual reader (like me every time I have to remember how our hash tables work). It makes much more sense for the _Hash parameter of unordered_set and the _Hash parameter of _Hashtable to be the same thing! * argument type _Key and result type size_t. Return values should * be distributed over the entire range [0, numeric_limits:::max()]. * - * @tparam _H2 The range-hashing function (in the terminology of - * Tavori and Dreizin). A binary function object whose argument - * types and result type are all size_t. Given arguments r and N, - * the return value is in the range [0, N). - * - * @tparam _Hash The ranged hash function (Tavori and Dreizin). A - * binary function whose argument types are _Key and size_t and - * whose result type is size_t. Given arguments k and N, the - * return value is in the range [0, N). Default: hash(k, N) = - * h2(h1(k), N). If _Hash is anything other than the default, _H1 - * and _H2 are ignored. But I would prefer to keep these parameters, and just rename them to _Unused1 and _Unused2 or something like that. Maybe _U1 and _U2. You can still get rid of them as constructor parameters and get rid of the base classes using those types. Just keep them in the template argument lists, so that we keep generating the same mangled names for specializations of _Hashtable. That way you don't need to change printers.py (which is good, because that change to printers.py is not OK anyway - it would make it impossible to debug code built with older versions of GCC, because the printers would only support the new layout - we need to support debugging programs that were not all built by the same version of GCC). @@ -168,19 +155,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION */ template + typename _Hash, typename
Re: [PATCH][Hashtable 5/6] Remove H1/H2 template parameters
On 19/12/19 20:22 +0100, François Dumont wrote: Because of this change printers.py has to be updated too. François On 11/17/19 10:15 PM, François Dumont wrote: H1 used to be a reference to the user Hash, now _Hashtable and unordered types agree on the same Hash type which is more intuitive. I also chose to not support anymore a stateful ranged hash functor. We only use _Mod_range_hashing and _Mask_range_hashing. Thanks to this simplification _M_bucket_index can also be simplified.    * include/bits/hashtable_policy.h (_Hashtable<>): Remove _H1 and _H2    template parameters.    (_Hastable_base<>): Likewise.    (_Default_ranged_hash): Remove.    (_Prime_rehash_policy::__ranged_hash): New.    (_Power2_rehash_policy::__ranged_hash): New.    (_Map_base<>): Remove _H1 and _H2 template parameters.    (_Insert_base<>): Likewise.    (_Insert<>): Likewise.    (_Rehash_base<>): Likewise.    (_Local_iterator_base<>): Remove _H1 and _H2 template parameters and add    _RangedHash.    (_Hash_code_base<>): Likewise.    (_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,    __hash_not_cached_t>): Remove.    (_Hash_code_base<>::_M_bucket_index(const _Key&, __hash_code, size_t)):    Replace by...    (_Hash_code_base<>::_M_bucket_index(__hash_code, size_t)): ...this.    (_Local_iterator<>): Remove _H1 and _H2 template parameters.    (_Local_const_iterator<>): Likewise.    (_Equality<>): Likewise.    * include/bits/hashtable.h (_Hashtable<>): Remove _H1 and _H2 template    parameters.    * include/bits/node_handle.h: Adapt.    * include/bits/unordered_map.h: Adapt.    * include/bits/unordered_set.h: Adapt.    * testsuite/23_containers/unordered_set/hash_policy/26132.cc: Adapt.    * testsuite/23_containers/unordered_set/hash_policy/71181.cc: Adapt.    * testsuite/23_containers/unordered_set/hash_policy/load_factor.cc:    Adapt.    * testsuite/23_containers/unordered_set/hash_policy/rehash.cc: Adapt.    * testsuite/23_containers/unordered_set/insert/hash_policy.cc: Adapt.    * testsuite/23_containers/unordered_set/max_load_factor/robustness.cc:    Adapt.    * testsuite/performance/23_containers/insert/54075.cc: Adapt.    * testsuite/performance/23_containers/insert_erase/41975.cc: Adapt.    * testsuite/performance/23_containers/insert_erase/    unordered_small_size.cc: Adapt. Tested under Linux x86_64. François diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 41be821782d..9dadc62e328 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -69,31 +69,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * and returns a bool-like value that is true if the two objects * are considered equal. * - * @tparam _H1 The hash function. A unary function object with + * @tparam _Hash The hash function. A unary function object with Renaming this to _Hash is great, that makes the code much easier to understand for a casual reader (like me every time I have to remember how our hash tables work). It makes much more sense for the _Hash parameter of unordered_set and the _Hash parameter of _Hashtable to be the same thing! * argument type _Key and result type size_t. Return values should * be distributed over the entire range [0, numeric_limits:::max()]. * - * @tparam _H2 The range-hashing function (in the terminology of - * Tavori and Dreizin). A binary function object whose argument - * types and result type are all size_t. Given arguments r and N, - * the return value is in the range [0, N). - * - * @tparam _Hash The ranged hash function (Tavori and Dreizin). A - * binary function whose argument types are _Key and size_t and - * whose result type is size_t. Given arguments k and N, the - * return value is in the range [0, N). Default: hash(k, N) = - * h2(h1(k), N). If _Hash is anything other than the default, _H1 - * and _H2 are ignored. But I would prefer to keep these parameters, and just rename them to _Unused1 and _Unused2 or something like that. Maybe _U1 and _U2. You can still get rid of them as constructor parameters and get rid of the base classes using those types. Just keep them in the template argument lists, so that we keep generating the same mangled names for specializations of _Hashtable. That way you don't need to change printers.py (which is good, because that change to printers.py is not OK anyway - it would make it impossible to debug code built with older versions of GCC, because the printers would only support the new layout - we need to support debugging programs that were not all built by the same version of GCC). @@ -168,19 +155,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION */ template + typename _Hash, typename _RehashPolicy, typename _Traits> So to be clear, what
Re: [PATCH][Hashtable 5/6] Remove H1/H2 template parameters
On 19/11/19 00:10 +0200, Ville Voutilainen wrote: On Mon, 18 Nov 2019 at 23:41, François Dumont wrote: > Also, is > this ABI-compatible > for our unordered containers? > IMHO, yes it is. In hashtable_policy.h _H1 was the user hash which I renamed in _Hash, the same template name that for unordered containers. _H2 was always _Mod_range_hashing and previous _Hash always _Default_ranged_hash, both stateless types. Only _H1 and _H2 were stored in _Hash_code_base for instance. _H1 is still as _Hash and _H2 was just empty and moreover stored last so removing it has no impact. Right, and as I understood the code, it's all empty base objects anyway, so it boils down to whether a set of empty bases can change without causing an ABI break, and I don't think there's an ABI problem here because the actual _Hashtable is stored as a member of various containers, and its size doesn't change, and based on what you wrote, with which my code-reading agrees, the behaviour doesn't change either. So the patch seems okay to me. There's no guarantee that a program-defined hash object is actually empty.
Re: [PATCH][Hashtable 5/6] Remove H1/H2 template parameters
Because of this change printers.py has to be updated too. François On 11/17/19 10:15 PM, François Dumont wrote: H1 used to be a reference to the user Hash, now _Hashtable and unordered types agree on the same Hash type which is more intuitive. I also chose to not support anymore a stateful ranged hash functor. We only use _Mod_range_hashing and _Mask_range_hashing. Thanks to this simplification _M_bucket_index can also be simplified. * include/bits/hashtable_policy.h (_Hashtable<>): Remove _H1 and _H2 template parameters. (_Hastable_base<>): Likewise. (_Default_ranged_hash): Remove. (_Prime_rehash_policy::__ranged_hash): New. (_Power2_rehash_policy::__ranged_hash): New. (_Map_base<>): Remove _H1 and _H2 template parameters. (_Insert_base<>): Likewise. (_Insert<>): Likewise. (_Rehash_base<>): Likewise. (_Local_iterator_base<>): Remove _H1 and _H2 template parameters and add _RangedHash. (_Hash_code_base<>): Likewise. (_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, __hash_not_cached_t>): Remove. (_Hash_code_base<>::_M_bucket_index(const _Key&, __hash_code, size_t)): Replace by... (_Hash_code_base<>::_M_bucket_index(__hash_code, size_t)): ...this. (_Local_iterator<>): Remove _H1 and _H2 template parameters. (_Local_const_iterator<>): Likewise. (_Equality<>): Likewise. * include/bits/hashtable.h (_Hashtable<>): Remove _H1 and _H2 template parameters. * include/bits/node_handle.h: Adapt. * include/bits/unordered_map.h: Adapt. * include/bits/unordered_set.h: Adapt. * testsuite/23_containers/unordered_set/hash_policy/26132.cc: Adapt. * testsuite/23_containers/unordered_set/hash_policy/71181.cc: Adapt. * testsuite/23_containers/unordered_set/hash_policy/load_factor.cc: Adapt. * testsuite/23_containers/unordered_set/hash_policy/rehash.cc: Adapt. * testsuite/23_containers/unordered_set/insert/hash_policy.cc: Adapt. * testsuite/23_containers/unordered_set/max_load_factor/robustness.cc: Adapt. * testsuite/performance/23_containers/insert/54075.cc: Adapt. * testsuite/performance/23_containers/insert_erase/41975.cc: Adapt. * testsuite/performance/23_containers/insert_erase/ unordered_small_size.cc: Adapt. Tested under Linux x86_64. François diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 41be821782d..9dadc62e328 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -69,31 +69,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * and returns a bool-like value that is true if the two objects * are considered equal. * - * @tparam _H1 The hash function. A unary function object with + * @tparam _Hash The hash function. A unary function object with * argument type _Key and result type size_t. Return values should * be distributed over the entire range [0, numeric_limits:::max()]. * - * @tparam _H2 The range-hashing function (in the terminology of - * Tavori and Dreizin). A binary function object whose argument - * types and result type are all size_t. Given arguments r and N, - * the return value is in the range [0, N). - * - * @tparam _Hash The ranged hash function (Tavori and Dreizin). A - * binary function whose argument types are _Key and size_t and - * whose result type is size_t. Given arguments k and N, the - * return value is in the range [0, N). Default: hash(k, N) = - * h2(h1(k), N). If _Hash is anything other than the default, _H1 - * and _H2 are ignored. - * - * @tparam _RehashPolicy Policy class with three members, all of - * which govern the bucket count. _M_next_bkt(n) returns a bucket - * count no smaller than n. _M_bkt_for_elements(n) returns a - * bucket count appropriate for an element count of n. - * _M_need_rehash(n_bkt, n_elt, n_ins) determines whether, if the - * current bucket count is n_bkt and the current element count is - * n_elt, we need to increase the bucket count. If so, returns - * make_pair(true, n), where n is the new bucket count. If not, - * returns make_pair(false, ) + * @tparam _RehashPolicy Policy class with three members, all of which + * govern the bucket count. _M_next_bkt(n) returns a bucket count no smaller + * than n. _M_bkt_for_elements(n) returns a bucket count appropriate for an + * element count of n. _M_need_rehash(n_bkt, n_elt, n_ins) determines + * whether, if the current bucket count is n_bkt and the current element + * count is n_elt, we need to increase the bucket count for n_ins insertions. + * If so, returns make_pair(true, n), where n is the new bucket count. If + * not, returns make_pair(false, ) * * @tparam _Traits Compile-time class with three boolean * std::integral_constant members: __cache_hash_code, __constant_iterators, @@ -168,19 +155,19 @@
Re: [PATCH][Hashtable 5/6] Remove H1/H2 template parameters
On Mon, 18 Nov 2019 at 23:41, François Dumont wrote: > > Also, is > > this ABI-compatible > > for our unordered containers? > > > IMHO, yes it is. > > In hashtable_policy.h _H1 was the user hash which I renamed in _Hash, > the same template name that for unordered containers. > > _H2 was always _Mod_range_hashing and previous _Hash always > _Default_ranged_hash, both stateless types. Only _H1 and _H2 were stored > in _Hash_code_base for instance. _H1 is still as _Hash and _H2 was just > empty and moreover stored last so removing it has no impact. Right, and as I understood the code, it's all empty base objects anyway, so it boils down to whether a set of empty bases can change without causing an ABI break, and I don't think there's an ABI problem here because the actual _Hashtable is stored as a member of various containers, and its size doesn't change, and based on what you wrote, with which my code-reading agrees, the behaviour doesn't change either. So the patch seems okay to me.
Re: [PATCH][Hashtable 5/6] Remove H1/H2 template parameters
On 11/17/19 11:21 PM, Ville Voutilainen wrote: On Sun, 17 Nov 2019 at 23:15, François Dumont wrote: H1 used to be a reference to the user Hash, now _Hashtable and unordered types agree on the same Hash type which is more intuitive. I also chose to not support anymore a stateful ranged hash functor. We only use _Mod_range_hashing and _Mask_range_hashing. Thanks to this simplification _M_bucket_index can also be simplified. Do we know whether there are existing users that this breaks? That's the problem with this kind of extension, we don't know. However we never get any report neither about potential users. And I remember that I fixed some years ago a bug that users would have reported much sooner if there have been users. But it was some years ago. Also, is this ABI-compatible for our unordered containers? IMHO, yes it is. In hashtable_policy.h _H1 was the user hash which I renamed in _Hash, the same template name that for unordered containers. _H2 was always _Mod_range_hashing and previous _Hash always _Default_ranged_hash, both stateless types. Only _H1 and _H2 were stored in _Hash_code_base for instance. _H1 is still as _Hash and _H2 was just empty and moreover stored last so removing it has no impact. François
Re: [PATCH][Hashtable 5/6] Remove H1/H2 template parameters
On Sun, 17 Nov 2019 at 23:15, François Dumont wrote: > > H1 used to be a reference to the user Hash, now _Hashtable and unordered > types agree on the same Hash type which is more intuitive. > > I also chose to not support anymore a stateful ranged hash functor. We > only use _Mod_range_hashing and _Mask_range_hashing. > > Thanks to this simplification _M_bucket_index can also be simplified. Do we know whether there are existing users that this breaks? Also, is this ABI-compatible for our unordered containers?
[PATCH][Hashtable 5/6] Remove H1/H2 template parameters
H1 used to be a reference to the user Hash, now _Hashtable and unordered types agree on the same Hash type which is more intuitive. I also chose to not support anymore a stateful ranged hash functor. We only use _Mod_range_hashing and _Mask_range_hashing. Thanks to this simplification _M_bucket_index can also be simplified. * include/bits/hashtable_policy.h (_Hashtable<>): Remove _H1 and _H2 template parameters. (_Hastable_base<>): Likewise. (_Default_ranged_hash): Remove. (_Prime_rehash_policy::__ranged_hash): New. (_Power2_rehash_policy::__ranged_hash): New. (_Map_base<>): Remove _H1 and _H2 template parameters. (_Insert_base<>): Likewise. (_Insert<>): Likewise. (_Rehash_base<>): Likewise. (_Local_iterator_base<>): Remove _H1 and _H2 template parameters and add _RangedHash. (_Hash_code_base<>): Likewise. (_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, __hash_not_cached_t>): Remove. (_Hash_code_base<>::_M_bucket_index(const _Key&, __hash_code, size_t)): Replace by... (_Hash_code_base<>::_M_bucket_index(__hash_code, size_t)): ...this. (_Local_iterator<>): Remove _H1 and _H2 template parameters. (_Local_const_iterator<>): Likewise. (_Equality<>): Likewise. * include/bits/hashtable.h (_Hashtable<>): Remove _H1 and _H2 template parameters. * include/bits/node_handle.h: Adapt. * include/bits/unordered_map.h: Adapt. * include/bits/unordered_set.h: Adapt. * testsuite/23_containers/unordered_set/hash_policy/26132.cc: Adapt. * testsuite/23_containers/unordered_set/hash_policy/71181.cc: Adapt. * testsuite/23_containers/unordered_set/hash_policy/load_factor.cc: Adapt. * testsuite/23_containers/unordered_set/hash_policy/rehash.cc: Adapt. * testsuite/23_containers/unordered_set/insert/hash_policy.cc: Adapt. * testsuite/23_containers/unordered_set/max_load_factor/robustness.cc: Adapt. * testsuite/performance/23_containers/insert/54075.cc: Adapt. * testsuite/performance/23_containers/insert_erase/41975.cc: Adapt. * testsuite/performance/23_containers/insert_erase/ unordered_small_size.cc: Adapt. Tested under Linux x86_64. François diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index ad07a36eb83..d09c851e8a4 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -69,31 +69,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * and returns a bool-like value that is true if the two objects * are considered equal. * - * @tparam _H1 The hash function. A unary function object with + * @tparam _Hash The hash function. A unary function object with * argument type _Key and result type size_t. Return values should * be distributed over the entire range [0, numeric_limits:::max()]. * - * @tparam _H2 The range-hashing function (in the terminology of - * Tavori and Dreizin). A binary function object whose argument - * types and result type are all size_t. Given arguments r and N, - * the return value is in the range [0, N). - * - * @tparam _Hash The ranged hash function (Tavori and Dreizin). A - * binary function whose argument types are _Key and size_t and - * whose result type is size_t. Given arguments k and N, the - * return value is in the range [0, N). Default: hash(k, N) = - * h2(h1(k), N). If _Hash is anything other than the default, _H1 - * and _H2 are ignored. - * - * @tparam _RehashPolicy Policy class with three members, all of - * which govern the bucket count. _M_next_bkt(n) returns a bucket - * count no smaller than n. _M_bkt_for_elements(n) returns a - * bucket count appropriate for an element count of n. - * _M_need_rehash(n_bkt, n_elt, n_ins) determines whether, if the - * current bucket count is n_bkt and the current element count is - * n_elt, we need to increase the bucket count. If so, returns - * make_pair(true, n), where n is the new bucket count. If not, - * returns make_pair(false, ) + * @tparam _RehashPolicy Policy class with three members, all of which + * govern the bucket count. _M_next_bkt(n) returns a bucket count no smaller + * than n. _M_bkt_for_elements(n) returns a bucket count appropriate for an + * element count of n. _M_need_rehash(n_bkt, n_elt, n_ins) determines + * whether, if the current bucket count is n_bkt and the current element + * count is n_elt, we need to increase the bucket count for n_ins insertions. + * If so, returns make_pair(true, n), where n is the new bucket count. If + * not, returns make_pair(false, ) * * @tparam _Traits Compile-time class with three boolean * std::integral_constant members: __cache_hash_code, __constant_iterators, @@ -168,19 +155,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION */ template + typename _Hash, typename _RehashPolicy, typename _Traits> class
