[PATCH][Hashtable 0/6] Code review
This is the begining of a patch series for _Hashtable
Initial patch to clarify code. I was tired to see true/false or
true_type/false_type without knowing what was true/false.
I also made code more consistent by chosing to specialize methods
through usage of __unique_keys_t/__multi_keys_t rather than calling them
_M_[multi]_XXX.
* include/bits/hashtable_policy.h (__detail::__unique_keys_t): New.
(__detail::__multi_keys_t): New.
(__detail::__constant_iterators_t): New.
(__detail::__mutable_iterators_t): New.
(__detail::__hash_cached_t): New.
(__detail::__hash_not_cached_t): New.
(_Hash_node<>): Change _Cache_hash_code template parameter from bool to
typename. Adapt partial specializations.
(_Node_iterator_base<>): Likewise.
(operator==(const _Node_iterator_base<>&,const
_Node_iterator_base<>&)):
Adapt.
(operator!=(const _Node_iterator_base<>&,const
_Node_iterator_base<>&)):
Adapt.
(_Node_iterator<>): Change __constant_iterators and __cache template
parameters from bool to typename.
(_Node_const_iterator<>): Likewise.
(_Map_base<>): Change _Unique_keys template parameter from bool to
typename. Adapt partial specializations.
(_Insert<>): Change _Constant_iterators template parameter from bool to
typename. Adapt partial specializations.
(_Local_iterator_base<>): Change __cache_hash_code template parameter
from bool to typename. Adapt partial specialization.
(_Hash_code_base<>): Likewise.
(operator==(const _Local_iterator_base<>&,
const _Local_iterator_base<>&)): Adapt.
(operator!=(const _Local_iterator_base<>&,
const _Local_iterator_base<>&)):
Adapt.
(_Local_iterator<>): Change __constant_iterators and __cache template
parameters from bool to typename.
(_Local_const_iterator<>): Likewise.
(_Hashtable_base<>): Adapt.
(_Equal_hash_code<>): Adapt.
(_Equality<>): Adapt.
* include/bits/hashtable.h (_Hashtable<>): Replace occurences of
true_type/false_type by respoectively __unique_type_t/__multi_type_t.
(_M_insert_unique_node(const key_type&, size_t, __hash_code,
__node_type*, size_t)): Replace by...
(_M_insert_node(__unique_keys_t, size_t, __hash_code, __node_type*,
size_t)): ...this.
(_M_insert_muti_node(__node_type*, const key_type&, __hash_code,
__node_type*)): Replace by...
(_M_insert_node(__multi_keys_t, __node_type*, __hash_code,
__node_type*)): ...this.
(_M_reinsert_node(node_type&&)): Replace by...
(_M_reinsert_node(node_type&&, __unique_keys_t)): ...this.
(_M_reinsert_node(const_iterator, node_type&&, __unique_keys_t)): New,
forward to latter.
(_M_reinsert_node_multi(const_iterator, node_type&&)): Replace by...
(_M_reinsert_node(const_iterator, node_type&&, __multi_keys_t)):
...this.
(_M_reinsert_node(node_type&&, __multi_keys_t)): New, forward to
latter.
(_M_reinsert_node(node_type&&)): New, use latters.
(_M_reinsert_node(const_iterator, node_type&&)): Likewise.
(_M_merge_unique(_Compatible_Hashtable&)): Replace by...
(_M_merge(__unique_keys_t, _Compatible_Hashtable&)): ...this.
(_M_merge_multi(_Compatible_Hashtable&)): Replace by...
(_M_merge(__multi_keys_t, _Compatible_Hashtable&)): ...this.
(_M_merge(_Compatible_Hashtable&)): New, use latters.
* include/bits/unordered_map.h
(unordered_map<>::insert(const_iterator, node_type&&)): Adapt.
(unordered_map<>::merge(unordered_map<>&)): Adapt.
(unordered_map<>::merge(unordered_multimap<>&)): Adapt.
(unordered_multimap<>::insert(node_type&&)): Adapt.
(unordered_multimap<>::insert(const_iterator, node_type&&)): Adapt.
(unordered_multimap<>::merge(unordered_multimap<>&)): Adapt.
(unordered_multimap<>::merge(unordered_map<>&)): Adapt.
* include/bits/unordered_set.h
(unordered_set<>::insert(const_iterator, node_type&&)): Adapt.
(unordered_set<>::merge(unordered_set<>&)): Adapt.
(unordered_set<>::merge(unordered_multiset<>&)): Adapt.
(unordered_multiset<>::insert(node_type&&)): Adapt.
(unordered_multiset<>::insert(const_iterator, node_type&&)): Adapt.
(unordered_multiset<>::merge(unordered_multiset<>&)): Adapt.
(unordered_multiset<>::merge(unordered_set<>&)): 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 c2b2219d471..ef71c090f3b 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -184,7 +184,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
private __detail::_Hashtable_alloc<
__alloc_rebind<_Alloc,
__detail::_Hash_node<_Value,
- _Traits::__hash_cached::value>>>
+ typename _Traits::__hash_cached>>>
{
static_assert(is_same::type, _Value>::value,
"unordered container must have a non-const, non-volatile value_type");
@@ -195,7 +195,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
using __traits_type = _Tra
Re: [PATCH][Hashtable 0/6] Code review
This patch also require an update of the printers.py file.
Here is an updated version.
François
On 11/17/19 9:42 PM, François Dumont wrote:
This is the begining of a patch series for _Hashtable
Initial patch to clarify code. I was tired to see true/false or
true_type/false_type without knowing what was true/false.
I also made code more consistent by chosing to specialize methods
through usage of __unique_keys_t/__multi_keys_t rather than calling
them _M_[multi]_XXX.
* include/bits/hashtable_policy.h (__detail::__unique_keys_t): New.
(__detail::__multi_keys_t): New.
(__detail::__constant_iterators_t): New.
(__detail::__mutable_iterators_t): New.
(__detail::__hash_cached_t): New.
(__detail::__hash_not_cached_t): New.
(_Hash_node<>): Change _Cache_hash_code template parameter from
bool to
typename. Adapt partial specializations.
(_Node_iterator_base<>): Likewise.
(operator==(const _Node_iterator_base<>&,const
_Node_iterator_base<>&)):
Adapt.
(operator!=(const _Node_iterator_base<>&,const
_Node_iterator_base<>&)):
Adapt.
(_Node_iterator<>): Change __constant_iterators and __cache template
parameters from bool to typename.
(_Node_const_iterator<>): Likewise.
(_Map_base<>): Change _Unique_keys template parameter from bool to
typename. Adapt partial specializations.
(_Insert<>): Change _Constant_iterators template parameter from
bool to
typename. Adapt partial specializations.
(_Local_iterator_base<>): Change __cache_hash_code template parameter
from bool to typename. Adapt partial specialization.
(_Hash_code_base<>): Likewise.
(operator==(const _Local_iterator_base<>&,
const _Local_iterator_base<>&)): Adapt.
(operator!=(const _Local_iterator_base<>&,
const _Local_iterator_base<>&)):
Adapt.
(_Local_iterator<>): Change __constant_iterators and __cache template
parameters from bool to typename.
(_Local_const_iterator<>): Likewise.
(_Hashtable_base<>): Adapt.
(_Equal_hash_code<>): Adapt.
(_Equality<>): Adapt.
* include/bits/hashtable.h (_Hashtable<>): Replace occurences of
true_type/false_type by respoectively __unique_type_t/__multi_type_t.
(_M_insert_unique_node(const key_type&, size_t, __hash_code,
__node_type*, size_t)): Replace by...
(_M_insert_node(__unique_keys_t, size_t, __hash_code, __node_type*,
size_t)): ...this.
(_M_insert_muti_node(__node_type*, const key_type&, __hash_code,
__node_type*)): Replace by...
(_M_insert_node(__multi_keys_t, __node_type*, __hash_code,
__node_type*)): ...this.
(_M_reinsert_node(node_type&&)): Replace by...
(_M_reinsert_node(node_type&&, __unique_keys_t)): ...this.
(_M_reinsert_node(const_iterator, node_type&&, __unique_keys_t)):
New,
forward to latter.
(_M_reinsert_node_multi(const_iterator, node_type&&)): Replace by...
(_M_reinsert_node(const_iterator, node_type&&, __multi_keys_t)):
...this.
(_M_reinsert_node(node_type&&, __multi_keys_t)): New, forward to
latter.
(_M_reinsert_node(node_type&&)): New, use latters.
(_M_reinsert_node(const_iterator, node_type&&)): Likewise.
(_M_merge_unique(_Compatible_Hashtable&)): Replace by...
(_M_merge(__unique_keys_t, _Compatible_Hashtable&)): ...this.
(_M_merge_multi(_Compatible_Hashtable&)): Replace by...
(_M_merge(__multi_keys_t, _Compatible_Hashtable&)): ...this.
(_M_merge(_Compatible_Hashtable&)): New, use latters.
* include/bits/unordered_map.h
(unordered_map<>::insert(const_iterator, node_type&&)): Adapt.
(unordered_map<>::merge(unordered_map<>&)): Adapt.
(unordered_map<>::merge(unordered_multimap<>&)): Adapt.
(unordered_multimap<>::insert(node_type&&)): Adapt.
(unordered_multimap<>::insert(const_iterator, node_type&&)): Adapt.
(unordered_multimap<>::merge(unordered_multimap<>&)): Adapt.
(unordered_multimap<>::merge(unordered_map<>&)): Adapt.
* include/bits/unordered_set.h
(unordered_set<>::insert(const_iterator, node_type&&)): Adapt.
(unordered_set<>::merge(unordered_set<>&)): Adapt.
(unordered_set<>::merge(unordered_multiset<>&)): Adapt.
(unordered_multiset<>::insert(node_type&&)): Adapt.
(unordered_multiset<>::insert(const_iterator, node_type&&)): Adapt.
(unordered_multiset<>::merge(unordered_multiset<>&)): Adapt.
(unordered_multiset<>::merge(unordered_set<>&)): 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 c2b2219d471..ef71c090f3b 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -184,7 +184,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
private __detail::_Hashtable_alloc<
__alloc_rebind<_Alloc,
__detail::_Hash_node<_Value,
- _Traits::__hash_cached::value>>>
+ typename _Traits::__hash_cached>>>
{
static_assert(is_same::type, _Value>::value,
"unorde
Re: [PATCH][Hashtable 0/6] Code review
After further work on pretty printers I prefer to stay closer to what is done currently. It works better with another patch I'll submit one day. The drawback is that I needed to consider versioned namespace in template parameters passed to lookup_templ_spec. François On 12/9/19 10:15 PM, François Dumont wrote: This patch also require an update of the printers.py file. Here is an updated version. François On 11/17/19 9:42 PM, François Dumont wrote: This is the begining of a patch series for _Hashtable Initial patch to clarify code. I was tired to see true/false or true_type/false_type without knowing what was true/false. I also made code more consistent by chosing to specialize methods through usage of __unique_keys_t/__multi_keys_t rather than calling them _M_[multi]_XXX. * include/bits/hashtable_policy.h (__detail::__unique_keys_t): New. (__detail::__multi_keys_t): New. (__detail::__constant_iterators_t): New. (__detail::__mutable_iterators_t): New. (__detail::__hash_cached_t): New. (__detail::__hash_not_cached_t): New. (_Hash_node<>): Change _Cache_hash_code template parameter from bool to typename. Adapt partial specializations. (_Node_iterator_base<>): Likewise. (operator==(const _Node_iterator_base<>&,const _Node_iterator_base<>&)): Adapt. (operator!=(const _Node_iterator_base<>&,const _Node_iterator_base<>&)): Adapt. (_Node_iterator<>): Change __constant_iterators and __cache template parameters from bool to typename. (_Node_const_iterator<>): Likewise. (_Map_base<>): Change _Unique_keys template parameter from bool to typename. Adapt partial specializations. (_Insert<>): Change _Constant_iterators template parameter from bool to typename. Adapt partial specializations. (_Local_iterator_base<>): Change __cache_hash_code template parameter from bool to typename. Adapt partial specialization. (_Hash_code_base<>): Likewise. (operator==(const _Local_iterator_base<>&, const _Local_iterator_base<>&)): Adapt. (operator!=(const _Local_iterator_base<>&, const _Local_iterator_base<>&)): Adapt. (_Local_iterator<>): Change __constant_iterators and __cache template parameters from bool to typename. (_Local_const_iterator<>): Likewise. (_Hashtable_base<>): Adapt. (_Equal_hash_code<>): Adapt. (_Equality<>): Adapt. * include/bits/hashtable.h (_Hashtable<>): Replace occurences of true_type/false_type by respoectively __unique_type_t/__multi_type_t. (_M_insert_unique_node(const key_type&, size_t, __hash_code, __node_type*, size_t)): Replace by... (_M_insert_node(__unique_keys_t, size_t, __hash_code, __node_type*, size_t)): ...this. (_M_insert_muti_node(__node_type*, const key_type&, __hash_code, __node_type*)): Replace by... (_M_insert_node(__multi_keys_t, __node_type*, __hash_code, __node_type*)): ...this. (_M_reinsert_node(node_type&&)): Replace by... (_M_reinsert_node(node_type&&, __unique_keys_t)): ...this. (_M_reinsert_node(const_iterator, node_type&&, __unique_keys_t)): New, forward to latter. (_M_reinsert_node_multi(const_iterator, node_type&&)): Replace by... (_M_reinsert_node(const_iterator, node_type&&, __multi_keys_t)): ...this. (_M_reinsert_node(node_type&&, __multi_keys_t)): New, forward to latter. (_M_reinsert_node(node_type&&)): New, use latters. (_M_reinsert_node(const_iterator, node_type&&)): Likewise. (_M_merge_unique(_Compatible_Hashtable&)): Replace by... (_M_merge(__unique_keys_t, _Compatible_Hashtable&)): ...this. (_M_merge_multi(_Compatible_Hashtable&)): Replace by... (_M_merge(__multi_keys_t, _Compatible_Hashtable&)): ...this. (_M_merge(_Compatible_Hashtable&)): New, use latters. * include/bits/unordered_map.h (unordered_map<>::insert(const_iterator, node_type&&)): Adapt. (unordered_map<>::merge(unordered_map<>&)): Adapt. (unordered_map<>::merge(unordered_multimap<>&)): Adapt. (unordered_multimap<>::insert(node_type&&)): Adapt. (unordered_multimap<>::insert(const_iterator, node_type&&)): Adapt. (unordered_multimap<>::merge(unordered_multimap<>&)): Adapt. (unordered_multimap<>::merge(unordered_map<>&)): Adapt. * include/bits/unordered_set.h (unordered_set<>::insert(const_iterator, node_type&&)): Adapt. (unordered_set<>::merge(unordered_set<>&)): Adapt. (unordered_set<>::merge(unordered_multiset<>&)): Adapt. (unordered_multiset<>::insert(node_type&&)): Adapt. (unordered_multiset<>::insert(const_iterator, node_type&&)): Adapt. (unordered_multiset<>::merge(unordered_multiset<>&)): Adapt. (unordered_multiset<>::merge(unordered_set<>&)): 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 c2b2219d471..f57e9ac0638 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/ha
Re: [PATCH][Hashtable 0/6] Code review
N.B. the 0/6 entry of a patch series is supposed to be a cover letter
describing the changes in the series, not one of the patches.
If you have patches 0/6, 1/6, 2/6 ... 6/6 then you actually have seven
patches, not six!
Anyway ...
On 19/12/19 20:17 +0100, François Dumont wrote:
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h
b/libstdc++-v3/include/bits/hashtable_policy.h
index f5809c7443a..b9320506bb2 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -172,6 +172,14 @@ namespace __detail
// Auxiliary types used for all instantiations of _Hashtable nodes
// and iterators.
+ using __unique_keys_t = true_type;
+ using __multi_keys_t = false_type;
+
+ using __constant_iterators_t = true_type;
+ using __mutable_iterators_t = false_type;
+
+ using __hash_cached_t = true_type;
+ using __hash_not_cached_t = false_type;
This is an ABI change, and the benefit doesn't seem large enough to
justify it. It will result in code size increases for anything that
links objects compiled before and after the change.
If we wanted to do this, I think it would be better to use enums, so:
enum _Unique_keys { __unique_keys, __multi_keys };
Otherwise you can use __hash_cached_t where __unique_keys_t is meant
to be used, so all you've done is introduce more names for the same
things.
If you want to replace the 'true' and 'false' literals with something
more descriptive, can't you just use constants?
constexpr bool __hash_cached = true;
constexpr bool __hash_not_cached = false;
Or just use comments:
struct _Local_iterator_base<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash, /*cached=*/ false>
Re: [PATCH][Hashtable 0/6] Code review
On 17/07/20 12:11 pm, Jonathan Wakely wrote:
N.B. the 0/6 entry of a patch series is supposed to be a cover letter
describing the changes in the series, not one of the patches.
If you have patches 0/6, 1/6, 2/6 ... 6/6 then you actually have seven
patches, not six!
Anyway ...
On 19/12/19 20:17 +0100, François Dumont wrote:
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h
b/libstdc++-v3/include/bits/hashtable_policy.h
index f5809c7443a..b9320506bb2 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -172,6 +172,14 @@ namespace __detail
// Auxiliary types used for all instantiations of _Hashtable nodes
// and iterators.
+ using __unique_keys_t = true_type;
+ using __multi_keys_t = false_type;
+
+ using __constant_iterators_t = true_type;
+ using __mutable_iterators_t = false_type;
+
+ using __hash_cached_t = true_type;
+ using __hash_not_cached_t = false_type;
This is an ABI change, and the benefit doesn't seem large enough to
justify it. It will result in code size increases for anything that
links objects compiled before and after the change.
If we wanted to do this, I think it would be better to use enums, so:
enum _Unique_keys { __unique_keys, __multi_keys };
Otherwise you can use __hash_cached_t where __unique_keys_t is meant
to be used, so all you've done is introduce more names for the same
things.
If you want to replace the 'true' and 'false' literals with something
more descriptive, can't you just use constants?
constexpr bool __hash_cached = true;
constexpr bool __hash_not_cached = false;
Or just use comments:
struct _Local_iterator_base<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash, /*cached=*/ false>
Ok, I'll review this patch with this simpler approach.
I even started to add comments in the patch you already approved.
