* [PATCH][_Hashtable] Fix some implementation inconsistencies
@ 2024-05-13 4:33 François Dumont
2024-05-22 4:50 ` François Dumont
2024-10-02 17:03 ` Jonathan Wakely
0 siblings, 2 replies; 5+ messages in thread
From: François Dumont @ 2024-05-13 4:33 UTC (permalink / raw)
To: libstdc++; +Cc: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1583 bytes --]
libstdc++: [_Hashtable] Fix some implementation inconsistencies
Get rid of the different usages of the mutable keyword except in
_Prime_rehash_policy where it is preserved for abi compatibility
reason.
Fix comment to explain that we need the computation of bucket index
noexcept
to be able to rehash the container when needed.
For Standard instantiations through std::unordered_xxx containers
we already
force caching of hash code when hash functor is not noexcep so it
is guarantied.
The static_assert purpose in _Hashtable on _M_bucket_index is thus
limited
to usages of _Hashtable with exotic _Hashtable_traits.
libstdc++-v3/ChangeLog:
* include/bits/hashtable_policy.h
(_NodeBuilder<>::_S_build): Remove
const qualification on _NodeGenerator instance.
(_ReuseOrAllocNode<>::operator()(_Args&&...)): Remove const qualification.
(_ReuseOrAllocNode<>::_M_nodes): Remove mutable.
(_Insert_base<>::_M_insert_range): Remove _NodeGetter const
qualification.
(_Hash_code_base<>::_M_bucket_index(const
_Hash_node_value<>&, size_t)):
Simplify noexcept declaration, we already static_assert
that _RangeHash functor
is noexcept.
* include/bits/hashtable.h: Rework comments. Remove const
qualifier on
_NodeGenerator& arguments.
Tested under Linux x64, ok to commit ?
François
[-- Attachment #2: hashtable_simplification.txt --]
[-- Type: text/plain, Size: 9214 bytes --]
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index cd3e1ac297c..e8e51714d72 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -48,7 +48,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
using __cache_default
= __not_<__and_<// Do not cache for fast hasher.
__is_fast_hash<_Hash>,
- // Mandatory to have erase not throwing.
+ // Mandatory for the rehash process.
__is_nothrow_invocable<const _Hash&, const _Tp&>>>;
// Helper to conditionally delete the default constructor.
@@ -481,7 +481,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Ht, typename _NodeGenerator>
void
- _M_assign(_Ht&&, const _NodeGenerator&);
+ _M_assign(_Ht&&, _NodeGenerator&);
void
_M_move_assign(_Hashtable&&, true_type);
@@ -919,7 +919,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Kt, typename _Arg, typename _NodeGenerator>
std::pair<iterator, bool>
- _M_insert_unique(_Kt&&, _Arg&&, const _NodeGenerator&);
+ _M_insert_unique(_Kt&&, _Arg&&, _NodeGenerator&);
template<typename _Kt>
static __conditional_t<
@@ -939,7 +939,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Arg, typename _NodeGenerator>
std::pair<iterator, bool>
- _M_insert_unique_aux(_Arg&& __arg, const _NodeGenerator& __node_gen)
+ _M_insert_unique_aux(_Arg&& __arg, _NodeGenerator& __node_gen)
{
return _M_insert_unique(
_S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))),
@@ -948,7 +948,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Arg, typename _NodeGenerator>
std::pair<iterator, bool>
- _M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen,
+ _M_insert(_Arg&& __arg, _NodeGenerator& __node_gen,
true_type /* __uks */)
{
using __to_value
@@ -959,7 +959,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Arg, typename _NodeGenerator>
iterator
- _M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen,
+ _M_insert(_Arg&& __arg, _NodeGenerator& __node_gen,
false_type __uks)
{
using __to_value
@@ -972,7 +972,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Arg, typename _NodeGenerator>
iterator
_M_insert(const_iterator, _Arg&& __arg,
- const _NodeGenerator& __node_gen, true_type __uks)
+ _NodeGenerator& __node_gen, true_type __uks)
{
return
_M_insert(std::forward<_Arg>(__arg), __node_gen, __uks).first;
@@ -982,7 +982,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Arg, typename _NodeGenerator>
iterator
_M_insert(const_iterator, _Arg&&,
- const _NodeGenerator&, false_type __uks);
+ _NodeGenerator&, false_type __uks);
size_type
_M_erase(true_type __uks, const key_type&);
@@ -1414,7 +1414,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
void
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_assign(_Ht&& __ht, const _NodeGenerator& __node_gen)
+ _M_assign(_Ht&& __ht, _NodeGenerator& __node_gen)
{
__buckets_ptr __buckets = nullptr;
if (!_M_buckets)
@@ -1656,8 +1656,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
~_Hashtable() noexcept
{
// Getting a bucket index from a node shall not throw because it is used
- // in methods (erase, swap...) that shall not throw. Need a complete
- // type to check this, so do it in the destructor not at class scope.
+ // during the rehash process. This static_assert purpose is limited to usage
+ // of _Hashtable with _Hashtable_traits requesting non-cached hash code.
+ // Need a complete type to check this, so do it in the destructor not at
+ // class scope.
static_assert(noexcept(declval<const __hash_code_base_access&>()
._M_bucket_index(declval<const __node_value_type&>(),
(std::size_t)0)),
@@ -2313,7 +2315,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_insert_unique(_Kt&& __k, _Arg&& __v,
- const _NodeGenerator& __node_gen)
+ _NodeGenerator& __node_gen)
-> pair<iterator, bool>
{
const size_type __size = size();
@@ -2351,7 +2353,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_insert(const_iterator __hint, _Arg&& __v,
- const _NodeGenerator& __node_gen,
+ _NodeGenerator& __node_gen,
false_type /* __uks */)
-> iterator
{
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 26def24f24e..1c121667ef0 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -155,7 +155,7 @@ namespace __detail
{
template<typename _Kt, typename _Arg, typename _NodeGenerator>
static auto
- _S_build(_Kt&& __k, _Arg&& __arg, const _NodeGenerator& __node_gen)
+ _S_build(_Kt&& __k, _Arg&& __arg, _NodeGenerator& __node_gen)
-> typename _NodeGenerator::__node_ptr
{
return __node_gen(std::forward<_Kt>(__k),
@@ -168,7 +168,7 @@ namespace __detail
{
template<typename _Kt, typename _Arg, typename _NodeGenerator>
static auto
- _S_build(_Kt&& __k, _Arg&&, const _NodeGenerator& __node_gen)
+ _S_build(_Kt&& __k, _Arg&&, _NodeGenerator& __node_gen)
-> typename _NodeGenerator::__node_ptr
{ return __node_gen(std::forward<_Kt>(__k)); }
};
@@ -212,7 +212,7 @@ namespace __detail
template<typename... _Args>
__node_ptr
- operator()(_Args&&... __args) const
+ operator()(_Args&&... __args)
{
if (!_M_nodes)
return _M_h._M_allocate_node(std::forward<_Args>(__args)...);
@@ -230,7 +230,7 @@ namespace __detail
}
private:
- mutable __node_ptr _M_nodes;
+ __node_ptr _M_nodes;
__hashtable_alloc& _M_h;
};
@@ -555,6 +555,7 @@ namespace __detail
{ return _M_max_load_factor; }
// Return a bucket size no smaller than n.
+ // TODO: 'const' qualifier is kept for abi compatibility reason.
std::size_t
_M_next_bkt(std::size_t __n) const;
@@ -567,6 +568,7 @@ namespace __detail
// and __n_ins is number of elements to be inserted. Do we need to
// increase bucket count? If so, return make_pair(true, n), where n
// is the new bucket count. If not, return make_pair(false, 0).
+ // TODO: 'const' qualifier is kept for abi compatibility reason.
std::pair<bool, std::size_t>
_M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
std::size_t __n_ins) const;
@@ -588,6 +590,8 @@ namespace __detail
static const std::size_t _S_growth_factor = 2;
float _M_max_load_factor;
+
+ // TODO: 'mutable' kept for abi compatibility reason.
mutable std::size_t _M_next_resize;
};
@@ -931,12 +935,12 @@ namespace __detail
template<typename _InputIterator, typename _NodeGetter>
void
_M_insert_range(_InputIterator __first, _InputIterator __last,
- const _NodeGetter&, true_type __uks);
+ _NodeGetter&, true_type __uks);
template<typename _InputIterator, typename _NodeGetter>
void
_M_insert_range(_InputIterator __first, _InputIterator __last,
- const _NodeGetter&, false_type __uks);
+ _NodeGetter&, false_type __uks);
public:
using iterator = _Node_iterator<_Value, __constant_iterators::value,
@@ -1012,7 +1016,7 @@ namespace __detail
_Hash, _RangeHash, _Unused,
_RehashPolicy, _Traits>::
_M_insert_range(_InputIterator __first, _InputIterator __last,
- const _NodeGetter& __node_gen, true_type __uks)
+ _NodeGetter& __node_gen, true_type __uks)
{
__hashtable& __h = _M_conjure_hashtable();
for (; __first != __last; ++__first)
@@ -1029,7 +1033,7 @@ namespace __detail
_Hash, _RangeHash, _Unused,
_RehashPolicy, _Traits>::
_M_insert_range(_InputIterator __first, _InputIterator __last,
- const _NodeGetter& __node_gen, false_type __uks)
+ _NodeGetter& __node_gen, false_type __uks)
{
using __rehash_guard_t = typename __hashtable::__rehash_guard_t;
using __pair_type = std::pair<bool, std::size_t>;
@@ -1359,9 +1363,7 @@ namespace __detail
std::size_t
_M_bucket_index(const _Hash_node_value<_Value, false>& __n,
std::size_t __bkt_count) const
- noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>()))
- && noexcept(declval<const _RangeHash&>()((__hash_code)0,
- (std::size_t)0)) )
+ noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>())) )
{
return _RangeHash{}(_M_hash_code(_ExtractKey{}(__n._M_v())),
__bkt_count);
@@ -1369,9 +1371,7 @@ namespace __detail
std::size_t
_M_bucket_index(const _Hash_node_value<_Value, true>& __n,
- std::size_t __bkt_count) const
- noexcept( noexcept(declval<const _RangeHash&>()((__hash_code)0,
- (std::size_t)0)) )
+ std::size_t __bkt_count) const noexcept
{ return _RangeHash{}(__n._M_hash_code, __bkt_count); }
void
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH][_Hashtable] Fix some implementation inconsistencies
2024-05-13 4:33 [PATCH][_Hashtable] Fix some implementation inconsistencies François Dumont
@ 2024-05-22 4:50 ` François Dumont
2024-06-06 17:02 ` François Dumont
2024-10-02 17:03 ` Jonathan Wakely
1 sibling, 1 reply; 5+ messages in thread
From: François Dumont @ 2024-05-22 4:50 UTC (permalink / raw)
To: libstdc++; +Cc: gcc-patches
Ping ?
On 13/05/2024 06:33, François Dumont wrote:
> libstdc++: [_Hashtable] Fix some implementation inconsistencies
>
> Get rid of the different usages of the mutable keyword except in
> _Prime_rehash_policy where it is preserved for abi compatibility
> reason.
>
> Fix comment to explain that we need the computation of bucket
> index noexcept
> to be able to rehash the container when needed.
>
> For Standard instantiations through std::unordered_xxx containers
> we already
> force caching of hash code when hash functor is not noexcep so it
> is guarantied.
>
> The static_assert purpose in _Hashtable on _M_bucket_index is thus
> limited
> to usages of _Hashtable with exotic _Hashtable_traits.
>
> libstdc++-v3/ChangeLog:
>
> * include/bits/hashtable_policy.h
> (_NodeBuilder<>::_S_build): Remove
> const qualification on _NodeGenerator instance.
> (_ReuseOrAllocNode<>::operator()(_Args&&...)): Remove const
> qualification.
> (_ReuseOrAllocNode<>::_M_nodes): Remove mutable.
> (_Insert_base<>::_M_insert_range): Remove _NodeGetter
> const qualification.
> (_Hash_code_base<>::_M_bucket_index(const
> _Hash_node_value<>&, size_t)):
> Simplify noexcept declaration, we already static_assert
> that _RangeHash functor
> is noexcept.
> * include/bits/hashtable.h: Rework comments. Remove const
> qualifier on
> _NodeGenerator& arguments.
>
> Tested under Linux x64, ok to commit ?
>
> François
>
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH][_Hashtable] Fix some implementation inconsistencies
2024-05-22 4:50 ` François Dumont
@ 2024-06-06 17:02 ` François Dumont
2024-06-24 4:53 ` François Dumont
0 siblings, 1 reply; 5+ messages in thread
From: François Dumont @ 2024-06-06 17:02 UTC (permalink / raw)
To: libstdc++; +Cc: gcc-patches
No chance ?
On 22/05/2024 06:50, François Dumont wrote:
> Ping ?
>
> On 13/05/2024 06:33, François Dumont wrote:
>> libstdc++: [_Hashtable] Fix some implementation inconsistencies
>>
>> Get rid of the different usages of the mutable keyword except in
>> _Prime_rehash_policy where it is preserved for abi compatibility
>> reason.
>>
>> Fix comment to explain that we need the computation of bucket
>> index noexcept
>> to be able to rehash the container when needed.
>>
>> For Standard instantiations through std::unordered_xxx containers
>> we already
>> force caching of hash code when hash functor is not noexcep so it
>> is guarantied.
>>
>> The static_assert purpose in _Hashtable on _M_bucket_index is
>> thus limited
>> to usages of _Hashtable with exotic _Hashtable_traits.
>>
>> libstdc++-v3/ChangeLog:
>>
>> * include/bits/hashtable_policy.h
>> (_NodeBuilder<>::_S_build): Remove
>> const qualification on _NodeGenerator instance.
>> (_ReuseOrAllocNode<>::operator()(_Args&&...)): Remove const
>> qualification.
>> (_ReuseOrAllocNode<>::_M_nodes): Remove mutable.
>> (_Insert_base<>::_M_insert_range): Remove _NodeGetter
>> const qualification.
>> (_Hash_code_base<>::_M_bucket_index(const
>> _Hash_node_value<>&, size_t)):
>> Simplify noexcept declaration, we already static_assert
>> that _RangeHash functor
>> is noexcept.
>> * include/bits/hashtable.h: Rework comments. Remove const
>> qualifier on
>> _NodeGenerator& arguments.
>>
>> Tested under Linux x64, ok to commit ?
>>
>> François
>>
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH][_Hashtable] Fix some implementation inconsistencies
2024-06-06 17:02 ` François Dumont
@ 2024-06-24 4:53 ` François Dumont
0 siblings, 0 replies; 5+ messages in thread
From: François Dumont @ 2024-06-24 4:53 UTC (permalink / raw)
To: libstdc++; +Cc: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1915 bytes --]
Hi
Still no time ?
Thanks
On 06/06/2024 19:02, François Dumont wrote:
> No chance ?
>
> On 22/05/2024 06:50, François Dumont wrote:
>> Ping ?
>>
>> On 13/05/2024 06:33, François Dumont wrote:
>>> libstdc++: [_Hashtable] Fix some implementation inconsistencies
>>>
>>> Get rid of the different usages of the mutable keyword except in
>>> _Prime_rehash_policy where it is preserved for abi compatibility
>>> reason.
>>>
>>> Fix comment to explain that we need the computation of bucket
>>> index noexcept
>>> to be able to rehash the container when needed.
>>>
>>> For Standard instantiations through std::unordered_xxx
>>> containers we already
>>> force caching of hash code when hash functor is not noexcep so
>>> it is guarantied.
>>>
>>> The static_assert purpose in _Hashtable on _M_bucket_index is
>>> thus limited
>>> to usages of _Hashtable with exotic _Hashtable_traits.
>>>
>>> libstdc++-v3/ChangeLog:
>>>
>>> * include/bits/hashtable_policy.h
>>> (_NodeBuilder<>::_S_build): Remove
>>> const qualification on _NodeGenerator instance.
>>> (_ReuseOrAllocNode<>::operator()(_Args&&...)): Remove const
>>> qualification.
>>> (_ReuseOrAllocNode<>::_M_nodes): Remove mutable.
>>> (_Insert_base<>::_M_insert_range): Remove _NodeGetter
>>> const qualification.
>>> (_Hash_code_base<>::_M_bucket_index(const
>>> _Hash_node_value<>&, size_t)):
>>> Simplify noexcept declaration, we already static_assert
>>> that _RangeHash functor
>>> is noexcept.
>>> * include/bits/hashtable.h: Rework comments. Remove
>>> const qualifier on
>>> _NodeGenerator& arguments.
>>>
>>> Tested under Linux x64, ok to commit ?
>>>
>>> François
>>>
[-- Attachment #2: hashtable_patch.txt --]
[-- Type: text/plain, Size: 9214 bytes --]
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 361da2b3b4d..7ed68bb6c3c 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -49,7 +49,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
using __cache_default
= __not_<__and_<// Do not cache for fast hasher.
__is_fast_hash<_Hash>,
- // Mandatory to have erase not throwing.
+ // Mandatory for the rehash process.
__is_nothrow_invocable<const _Hash&, const _Tp&>>>;
// Helper to conditionally delete the default constructor.
@@ -484,7 +484,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Ht, typename _NodeGenerator>
void
- _M_assign(_Ht&&, const _NodeGenerator&);
+ _M_assign(_Ht&&, _NodeGenerator&);
void
_M_move_assign(_Hashtable&&, true_type);
@@ -922,7 +922,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Kt, typename _Arg, typename _NodeGenerator>
std::pair<iterator, bool>
- _M_insert_unique(_Kt&&, _Arg&&, const _NodeGenerator&);
+ _M_insert_unique(_Kt&&, _Arg&&, _NodeGenerator&);
template<typename _Kt>
static __conditional_t<
@@ -942,7 +942,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Arg, typename _NodeGenerator>
std::pair<iterator, bool>
- _M_insert_unique_aux(_Arg&& __arg, const _NodeGenerator& __node_gen)
+ _M_insert_unique_aux(_Arg&& __arg, _NodeGenerator& __node_gen)
{
return _M_insert_unique(
_S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))),
@@ -951,7 +951,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Arg, typename _NodeGenerator>
std::pair<iterator, bool>
- _M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen,
+ _M_insert(_Arg&& __arg, _NodeGenerator& __node_gen,
true_type /* __uks */)
{
using __to_value
@@ -962,7 +962,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Arg, typename _NodeGenerator>
iterator
- _M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen,
+ _M_insert(_Arg&& __arg, _NodeGenerator& __node_gen,
false_type __uks)
{
using __to_value
@@ -975,7 +975,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Arg, typename _NodeGenerator>
iterator
_M_insert(const_iterator, _Arg&& __arg,
- const _NodeGenerator& __node_gen, true_type __uks)
+ _NodeGenerator& __node_gen, true_type __uks)
{
return
_M_insert(std::forward<_Arg>(__arg), __node_gen, __uks).first;
@@ -985,7 +985,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Arg, typename _NodeGenerator>
iterator
_M_insert(const_iterator, _Arg&&,
- const _NodeGenerator&, false_type __uks);
+ _NodeGenerator&, false_type __uks);
size_type
_M_erase(true_type __uks, const key_type&);
@@ -1415,7 +1415,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
void
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_assign(_Ht&& __ht, const _NodeGenerator& __node_gen)
+ _M_assign(_Ht&& __ht, _NodeGenerator& __node_gen)
{
__buckets_ptr __buckets = nullptr;
if (!_M_buckets)
@@ -1657,8 +1657,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
~_Hashtable() noexcept
{
// Getting a bucket index from a node shall not throw because it is used
- // in methods (erase, swap...) that shall not throw. Need a complete
- // type to check this, so do it in the destructor not at class scope.
+ // during the rehash process. This static_assert purpose is limited to usage
+ // of _Hashtable with _Hashtable_traits requesting non-cached hash code.
+ // Need a complete type to check this, so do it in the destructor not at
+ // class scope.
static_assert(noexcept(declval<const __hash_code_base_access&>()
._M_bucket_index(declval<const __node_value_type&>(),
(std::size_t)0)),
@@ -2314,7 +2316,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_insert_unique(_Kt&& __k, _Arg&& __v,
- const _NodeGenerator& __node_gen)
+ _NodeGenerator& __node_gen)
-> pair<iterator, bool>
{
const size_type __size = size();
@@ -2352,7 +2354,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_insert(const_iterator __hint, _Arg&& __v,
- const _NodeGenerator& __node_gen,
+ _NodeGenerator& __node_gen,
false_type /* __uks */)
-> iterator
{
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 26def24f24e..1c121667ef0 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -155,7 +155,7 @@ namespace __detail
{
template<typename _Kt, typename _Arg, typename _NodeGenerator>
static auto
- _S_build(_Kt&& __k, _Arg&& __arg, const _NodeGenerator& __node_gen)
+ _S_build(_Kt&& __k, _Arg&& __arg, _NodeGenerator& __node_gen)
-> typename _NodeGenerator::__node_ptr
{
return __node_gen(std::forward<_Kt>(__k),
@@ -168,7 +168,7 @@ namespace __detail
{
template<typename _Kt, typename _Arg, typename _NodeGenerator>
static auto
- _S_build(_Kt&& __k, _Arg&&, const _NodeGenerator& __node_gen)
+ _S_build(_Kt&& __k, _Arg&&, _NodeGenerator& __node_gen)
-> typename _NodeGenerator::__node_ptr
{ return __node_gen(std::forward<_Kt>(__k)); }
};
@@ -212,7 +212,7 @@ namespace __detail
template<typename... _Args>
__node_ptr
- operator()(_Args&&... __args) const
+ operator()(_Args&&... __args)
{
if (!_M_nodes)
return _M_h._M_allocate_node(std::forward<_Args>(__args)...);
@@ -230,7 +230,7 @@ namespace __detail
}
private:
- mutable __node_ptr _M_nodes;
+ __node_ptr _M_nodes;
__hashtable_alloc& _M_h;
};
@@ -555,6 +555,7 @@ namespace __detail
{ return _M_max_load_factor; }
// Return a bucket size no smaller than n.
+ // TODO: 'const' qualifier is kept for abi compatibility reason.
std::size_t
_M_next_bkt(std::size_t __n) const;
@@ -567,6 +568,7 @@ namespace __detail
// and __n_ins is number of elements to be inserted. Do we need to
// increase bucket count? If so, return make_pair(true, n), where n
// is the new bucket count. If not, return make_pair(false, 0).
+ // TODO: 'const' qualifier is kept for abi compatibility reason.
std::pair<bool, std::size_t>
_M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
std::size_t __n_ins) const;
@@ -588,6 +590,8 @@ namespace __detail
static const std::size_t _S_growth_factor = 2;
float _M_max_load_factor;
+
+ // TODO: 'mutable' kept for abi compatibility reason.
mutable std::size_t _M_next_resize;
};
@@ -931,12 +935,12 @@ namespace __detail
template<typename _InputIterator, typename _NodeGetter>
void
_M_insert_range(_InputIterator __first, _InputIterator __last,
- const _NodeGetter&, true_type __uks);
+ _NodeGetter&, true_type __uks);
template<typename _InputIterator, typename _NodeGetter>
void
_M_insert_range(_InputIterator __first, _InputIterator __last,
- const _NodeGetter&, false_type __uks);
+ _NodeGetter&, false_type __uks);
public:
using iterator = _Node_iterator<_Value, __constant_iterators::value,
@@ -1012,7 +1016,7 @@ namespace __detail
_Hash, _RangeHash, _Unused,
_RehashPolicy, _Traits>::
_M_insert_range(_InputIterator __first, _InputIterator __last,
- const _NodeGetter& __node_gen, true_type __uks)
+ _NodeGetter& __node_gen, true_type __uks)
{
__hashtable& __h = _M_conjure_hashtable();
for (; __first != __last; ++__first)
@@ -1029,7 +1033,7 @@ namespace __detail
_Hash, _RangeHash, _Unused,
_RehashPolicy, _Traits>::
_M_insert_range(_InputIterator __first, _InputIterator __last,
- const _NodeGetter& __node_gen, false_type __uks)
+ _NodeGetter& __node_gen, false_type __uks)
{
using __rehash_guard_t = typename __hashtable::__rehash_guard_t;
using __pair_type = std::pair<bool, std::size_t>;
@@ -1359,9 +1363,7 @@ namespace __detail
std::size_t
_M_bucket_index(const _Hash_node_value<_Value, false>& __n,
std::size_t __bkt_count) const
- noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>()))
- && noexcept(declval<const _RangeHash&>()((__hash_code)0,
- (std::size_t)0)) )
+ noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>())) )
{
return _RangeHash{}(_M_hash_code(_ExtractKey{}(__n._M_v())),
__bkt_count);
@@ -1369,9 +1371,7 @@ namespace __detail
std::size_t
_M_bucket_index(const _Hash_node_value<_Value, true>& __n,
- std::size_t __bkt_count) const
- noexcept( noexcept(declval<const _RangeHash&>()((__hash_code)0,
- (std::size_t)0)) )
+ std::size_t __bkt_count) const noexcept
{ return _RangeHash{}(__n._M_hash_code, __bkt_count); }
void
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH][_Hashtable] Fix some implementation inconsistencies
2024-05-13 4:33 [PATCH][_Hashtable] Fix some implementation inconsistencies François Dumont
2024-05-22 4:50 ` François Dumont
@ 2024-10-02 17:03 ` Jonathan Wakely
1 sibling, 0 replies; 5+ messages in thread
From: Jonathan Wakely @ 2024-10-02 17:03 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
On Mon, 13 May 2024 at 05:34, François Dumont <frs.dumont@gmail.com> wrote:
>
> libstdc++: [_Hashtable] Fix some implementation inconsistencies
>
> Get rid of the different usages of the mutable keyword except in
> _Prime_rehash_policy where it is preserved for abi compatibility
> reason.
>
> Fix comment to explain that we need the computation of bucket index
> noexcept
> to be able to rehash the container when needed.
>
> For Standard instantiations through std::unordered_xxx containers
> we already
> force caching of hash code when hash functor is not noexcep so it
> is guarantied.
>
> The static_assert purpose in _Hashtable on _M_bucket_index is thus
> limited
> to usages of _Hashtable with exotic _Hashtable_traits.
>
> libstdc++-v3/ChangeLog:
>
> * include/bits/hashtable_policy.h
> (_NodeBuilder<>::_S_build): Remove
> const qualification on _NodeGenerator instance.
> (_ReuseOrAllocNode<>::operator()(_Args&&...)): Remove const qualification.
> (_ReuseOrAllocNode<>::_M_nodes): Remove mutable.
> (_Insert_base<>::_M_insert_range): Remove _NodeGetter const
> qualification.
> (_Hash_code_base<>::_M_bucket_index(const
> _Hash_node_value<>&, size_t)):
> Simplify noexcept declaration, we already static_assert
> that _RangeHash functor
> is noexcept.
> * include/bits/hashtable.h: Rework comments. Remove const
> qualifier on
> _NodeGenerator& arguments.
>
> Tested under Linux x64, ok to commit ?
OK for trunk, thanks.
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2024-10-02 17:03 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2024-05-13 4:33 [PATCH][_Hashtable] Fix some implementation inconsistencies François Dumont
2024-05-22 4:50 ` François Dumont
2024-06-06 17:02 ` François Dumont
2024-06-24 4:53 ` François Dumont
2024-10-02 17:03 ` Jonathan Wakely
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).