[PATCH] _Hashtable fancy pointer support
François Dumont
frs.dumont@gmail.com
Wed May 6 05:08:00 GMT 2026
Hi
I just refresh this PR.
https://forge.sourceware.org/gcc/gcc-TEST/pulls/32
libstdc++: [_Hashtable] Add fancy pointer support [PR57272]
The fancy allocator pointer type support is added to std::unordered_map,
std::unordered_multimap, std::unordered_multiset and std::unordered_set
through the underlying std::_Hashtable class.
To respect ABI a new parallel hierarchy of node types has been added.
This change introduces new class template parameterized on the allocator's
void_pointer type, __hashtable::_Node_base and
__hashtable::_Iterator_base, and
new class templates parameterized on the allocator's pointer type,
__hashtable::_Node,
__hashtable::_Node_legacy, __hashtable::_Iterator,
__hashtable::_Local_iterator.
The _Iterator class template is used for both iterator and
const_iterator. The
_Local_iterator class template is used for both local_iterator and
const_local_iterator.
Contrarily to the legacy iterator model the _Iterator and
_Local_iterator type
cannot be compared anymore.
Whether std::_Hashtable<K, V, A, KoV, E, H, RH, U, RP, T> should use the old
__detail::_Hash_node<V, T::__hash_cached::value> or new
__hashtable::_Node<A::pointer> type family internally is controlled by a new
__hashtable::_Node_traits traits template. Whether it should use the old
__detail::_Node_iterator<V, T::__constant_iterators::value,
T::__hash_cached::value>
or new __hashtable::_Iterator<Const, T::__constant_iterators::value,
A::pointer>
type family internally is controlled by __hashtable::_Iterator_traits traits
template.
Two new node models are being introduced. Both models have a hash code
cache member
so are not abi backward compatible with previous node model not caching
it. On the 2
new models one mimics the legacy node model with hash code cache for abi
compatibility.
The other model have a different abi to put the cached hash code right
after the next
node pointer so that it can be accessed with reduced risk of cache miss.
To control the abi compatibility the
_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE macro
can be used. Here are the different possible values:
*
0
Disable fancy pointer support, use legacy abi node model and raw C
pointers.
*
<= 9000
Use the fancy pointer type of the allocator. If this type is not
fancy, it is a
raw C pointer, then use the legacy node model. If its sizeof is
equal to the one
of a raw C pointer, use the new maybe abi-compatible node model.
Otherwise use
the new abi-incompatible node model.
*
9001
Always use the new maybe abi-compatible node model.
*
= 9002
Always use the new abi-incompatible node model.
This macro is currently undocumented, which needs to be fixed.
If _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE > 9000 the legacy node model is
simply not
defined.
libstdc++-v3/ChangeLog:
|PR libstdc++/57272 * include/bits/hashtable.h
(__hashtable::__element_t): New. (__hashtable::_Node_base,
__hashtable::_Node_hash_cache, __hashtable::_Node_data)
(__hashtable::_Node, __hashtable::_Node_legacy): New.
(__hashtable::__use_maybe_abi_compatible_node, __hashtable::__node_t):
New. (__hashtable::_Iterator_base, __hashtable::_Iterator)
(__hashtable::_Local_iterator): New. (__hashtable::_Node_traits,
__hashtable::_Iterator_traits): New. (__hashtable::__alloc_ptr): New.
(_Hashtable::__node_type, __node_alloc_type, __node_alloc_traits,
__node_ptr) (__node_base, __node_base_ptr, __buckets_ptr): Rename
respectively into... (_Hashtable::_Node, _Node_alloc,
_Node_alloc_traits, _Node_ptr) (_Node_base, _Base_ptr, _Buckets_ptr):
... those. (_Hashtable::_Buckets_ptr_traits): New.
(_Hashtable::__hash_code_base_access): Remove.
(_Hashtable::_M_bucket_begin): Remove. (_Hashtable::_S_v, _S_next,
_M_single_bucket_ptr): New. (_Hashtable::_M_hash_code, _M_hash_code_ext,
_M_bucket_index) (_M_bucket_index_ext, _M_key_equals, _M_key_equals_tr,
_M_equals, _M_equals_tr) (_M_node_equals): New.
(_Hashtable::__location_type::_M_base): New. (_Hashtable::_S_adapt):
New. (_Hashtable): Adapt. * include/bits/hashtable_policy.h: Include
<bits/ptr_traits.h>. Include <bits/stl_uninitialized.h>.
[_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE > 9000]: Remove include
<ext/aligned_buffer.h>. (_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE): New
macro, default to 1. (_Hash_node_base::_M_base_ptr): New.
(_Hash_node::_M_node_ptr): New. (_Hash_code_base::_M_hash_code,
_M_bucket_index): Remove. (_Hashtable_base::_M_key_equals,
_M_key_equals_tr): Adapt to only take key type.
(_Hashtable_base::_M_equals, _M_equals_tr, _M_node_equals): Remove.
(_Hashtable_alloc): Adapt. * include/debug/safe_unordered_container.h
(_UMContInvalidatePred::operator()): Compare iterator _M_cur member.
(_Safe_unordered_container::_M_invalidate_all): Likewise. *
testsuite/23_containers/unordered_map/115939.cc: Undefine
_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE as types associated with fancy
pointer support do not suffer from the ambiguity issue tested here. *
testsuite/23_containers/unordered_map/allocator/ext_ptr.cc: New test. *
testsuite/23_containers/unordered_map/requirements/explicit_instantiation/alloc_ptr.cc:
New test case. *
testsuite/23_containers/unordered_map/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
New test case. *
testsuite/23_containers/unordered_multimap/allocator/ext_ptr.cc: New
test case. *
testsuite/23_containers/unordered_multimap/requirements/explicit_instantiation/alloc_ptr.cc:
New test case. *
testsuite/23_containers/unordered_multimap/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
New test case. *
testsuite/23_containers/unordered_multiset/allocator/ext_ptr.cc: New
test case. *
testsuite/23_containers/unordered_multiset/requirements/explicit_instantiation/alloc_ptr.cc:
New test case. *
testsuite/23_containers/unordered_multiset/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
New test case. *
testsuite/23_containers/unordered_set/allocator/ext_ptr.cc: Adapt. *
testsuite/23_containers/unordered_set/instantiation_neg.cc: Undef
_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE. *
testsuite/23_containers/unordered_set/buckets/swap.cc: Test with slow
and fast hash functor. *
testsuite/23_containers/unordered_set/requirements/explicit_instantiation/alloc_ptr.cc:
New test case. *
testsuite/23_containers/unordered_set/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
New test case. |
Tested under Linux x86_64.
François
On 10/16/25 22:12, François Dumont wrote:
> Ping ?
>
> With the multiplication of PRs, great news by the way, it starts being
> lost in the limbos of sourceware.org :-)
>
>
> On 8/6/25 21:20, François Dumont wrote:
>> Hi
>>
>> Any chance to get a review for this patch ?
>>
>> I've been testing it for quite some time now with no problem.
>> Moreover it's mostly replication of what has been done on other
>> containers.
>>
>> libstdc++: Add fancy pointer support to std::_Hashtable [PR57272]
>>
>> The fancy allocator pointer type support is added to
>> std::unordered_map,
>> std::unordered_multimap, std::unordered_multiset and std::unordered_set
>> through the underlying std::_Hashtable class.
>>
>> To respect ABI a new parallel hierarchy of node types has been
>> added.
>> This change introduces new class template parameterized on the
>> allocator's
>> void_pointer type, __hashtable::_Node_base, and new class templates
>> parameterized on the allocator's pointer type, __hashtable::_Node,
>> __hashtable::_Iterator, __hashtable::_Local_iterator. The
>> _Iterator class
>> template is used for both iterator and const_iterator. The
>> _Local_iterator
>> class template is used for both local_iterator and
>> const_local_iterator.
>> Whether std::_Hashtable<K, V, A, KoV, E, H, RH, U, RP, T> should
>> use the old
>> __detail::_Hash_node<V, T::__hash_cached::value> or new
>> __hashtable::_Node<A::pointer> type family internally is
>> controlled by a new
>> __hashtable::_Node_traits traits template. Whether it should use
>> the old
>> __detail::_Node_iterator<V, T::__constant_iterators::value,
>> T::__hash_cached::value>
>> or new __hashtable::_Iterator<Const,
>> T::__constant_iterators::value, A::pointer>
>> type family internally is controlled by
>> __hashtable::_Iterator_traits traits
>> template.
>>
>> In case anybody is currently using std::_Hashtable with an
>> allocator that has a
>> fancy pointer, this change will be an ABI break, because their
>> std::_Hashtable
>> instantiations would start to (correctly) use the fancy pointer
>> type. Note that
>> the new type family used in this case is always caching the hash
>> code at node
>> level.
>>
>> Because std::_Hashtable will never use fancy pointers in C++98
>> mode, recompiling
>> everything to use fancy pointers isn't even possible if mixing
>> C++98 and C++11
>> code that uses std::_Hashtable. To alleviate this problem,
>> compiling with
>> -D_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE=0 will force
>> std::_Hashtable to have the
>> old, non-conforming behaviour and use raw pointers internally.
>> For testing
>> purposes, compiling with
>> -D_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE=9001 will force
>> std::_Hashtable to always use the new node types.
>>
>> This macro is currently undocumented, which needs to be fixed.
>>
>> libstdc++-v3/ChangeLog:
>>
>> PR libstdc++/57272
>> * include/bits/hashtable.h
>> (__hashtable::_Node_base<>, __hashtable::_Node<>): New.
>> (__hashtable::_Iterator_base<>,
>> __hashtable::_Iterator<>): New.
>> (__hashtable::_Local_iterator<>): New.
>> (__hashtable::_Node_traits<>,
>> __hashtable::_Iterator_traits<>): New.
>> (__hashtable::__alloc_ptr<>): New template alias.
>> (_Hashtable<>::__node_type, __node_alloc_type,
>> __node_alloc_traits, __node_ptr)
>> (__node_base, __node_base_ptr, __buckets_ptr): Rename
>> respectively into...
>> (_Hashtable<>::_Node, _Node_alloc, _Node_alloc_traits,
>> _Node_ptr)
>> (_Node_base, _Base_ptr, _Buckets_ptr): ... those.
>> (_Hashtable<>::_Buckets_ptr_traits): New.
>> (_Hashtable<>::__hash_code_base_access): Remove.
>> (_Hashtable<>::_S_v, _S_next, _M_single_bucket_ptr): New.
>> (_Hashtable<>::_M_node_hash_code, _M_node_hash_code_ext,
>> _M_bucket_index)
>> (_M_bucket_index_ext, _M_key_equals, _M_key_equals_tr,
>> _M_equals, _M_equals_tr)
>> (_M_node_equals): New.
>> (_Hashtable<>::__location_type::_M_base): New.
>> (_Hashtable<>::_S_adapt): New.
>> (_Hashtable<>): Adapt.
>> * include/bits/hashtable_policy.h: Include
>> <bits/ptr_traits.h>.
>> Include <bits/stl_uninitialized.h>.
>> (_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE): New macro,
>> default to 1.
>> (_Hash_node_base::_M_base_ptr): New.
>> (_Hash_node<>::_M_node_ptr): New.
>> (_Hash_code_base<>::_M_hash_code, _M_bucket_index): Remove.
>> (_Hashtable_base<>::_M_key_equals, _M_key_equals_tr):
>> Adapt to only take key
>> type.
>> (_Hashtable_base<>::_M_equals, _M_equals_tr,
>> _M_node_equals): Remove.
>> (_Hashtable_alloc<>): Adapt.
>> * testsuite/23_containers/unordered_map/115939.cc: #undef
>> _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE as types associated
>> with fancy pointer
>> support do not suffer from the ambiguity issue tested here.
>> *
>> testsuite/23_containers/unordered_map/allocator/ext_ptr.cc: New test.
>> *
>> testsuite/23_containers/unordered_map/requirements/explicit_instantiation/alloc_ptr.cc:
>> New test case.
>> *
>> testsuite/23_containers/unordered_map/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
>> New test case.
>> *
>> testsuite/23_containers/unordered_multimap/allocator/ext_ptr.cc: New
>> test case.
>> *
>> testsuite/23_containers/unordered_multimap/requirements/explicit_instantiation/alloc_ptr.cc:
>> New test case.
>> *
>> testsuite/23_containers/unordered_multimap/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
>> New test case.
>> *
>> testsuite/23_containers/unordered_multiset/allocator/ext_ptr.cc: New
>> test case.
>> *
>> testsuite/23_containers/unordered_multiset/requirements/explicit_instantiation/alloc_ptr.cc:
>> New test case.
>> *
>> testsuite/23_containers/unordered_multiset/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
>> New test case.
>> *
>> testsuite/23_containers/unordered_set/allocator/ext_ptr.cc: Adapt.
>> *
>> testsuite/23_containers/unordered_set/instantiation_neg.cc:
>> Undef _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE.
>> *
>> testsuite/23_containers/unordered_set/requirements/explicit_instantiation/alloc_ptr.cc:
>> New test case.
>> *
>> testsuite/23_containers/unordered_set/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
>> New test case.
>>
>> https://forge.sourceware.org/gcc/gcc-TEST/pulls/32
>>
>> Thanks,
>>
>> François
>>
>>
>> On 06/07/2025 16:04, François Dumont wrote:
>>> I've eventually decided to preserve abi if the sizeof of the fancy
>>> pointer type is equal to the sizeof of a C pointer that we are
>>> currently using. That's a prerequisite to potentially have abi
>>> backward compatibility.
>>>
>>> The only diff now with the legacy node/iterator implementations is
>>> on the local_iterator for which I haven't reproduce the complicated
>>> code to store of the hash functor on the local_iterator instance
>>> when the hash code is not cached. Instead, when hash code is not
>>> cached, the end(bucket) method is finding the last node of the
>>> bucket. The drawback is that the loop on bucket's local_iterator
>>> will be done twice, once to compute end and then the user code loop.
>>>
>>> PR updated here:
>>>
>>> https://forge.sourceware.org/gcc/gcc-TEST/pulls/32
>>>
>>> François
>>>
>>> On 26/06/2025 19:39, François Dumont wrote:
>>>> No chance to just answer to the question below about how
>>>> conservative I should be ?
>>>>
>>>> Thanks
>>>>
>>>> On 02/06/2025 07:07, François Dumont wrote:
>>>>> Hi
>>>>>
>>>>> It would be nice if someone got some time to review this PR.
>>>>>
>>>>> Compared to other containers for which support of fancy allocator
>>>>> pointer type have been added the main difference is that in
>>>>> std::_Hashtable usage of the new node types is an abi breaking
>>>>> change, no matter how fancy or not is the allocator's pointer
>>>>> type. This is because in this case hash code is always cached and
>>>>> is put in memory just after pointer to next node. Let me know if I
>>>>> need to be more conservative.
>>>>>
>>>>> libstdc++: Add fancy pointer support to std::_Hashtable [PR57272]
>>>>>
>>>>> The fancy allocator pointer type support is added to
>>>>> std::unordered_map,
>>>>> std::unordered_multimap, std::unordered_multiset and
>>>>> std::unordered_set
>>>>> through the underlying std::_Hashtable class.
>>>>>
>>>>> To respect ABI a new parallel hierarchy of node types has been
>>>>> added.
>>>>> This change introduces new class template parameterized on the
>>>>> allocator's
>>>>> void_pointer type, __hashtable::_Node_base, and new class
>>>>> templates
>>>>> parameterized on the allocator's pointer type,
>>>>> __hashtable::_Node,
>>>>> __hashtable::_Iterator, __hashtable::_Local_iterator. The
>>>>> _Iterator class
>>>>> template is used for both iterator and const_iterator. The
>>>>> _Local_iterator
>>>>> class template is used for both local_iterator and
>>>>> const_local_iterator.
>>>>> Whether std::_Hashtable<K, V, A, KoV, E, H, RH, U, RP, T>
>>>>> should use the old
>>>>> __detail::_Hash_node<V, T::__hash_cached::value> or new
>>>>> __hashtable::_Node<A::pointer> type family internally is
>>>>> controlled by a new
>>>>> __hashtable::_Node_traits traits template. Whether it should
>>>>> use the old
>>>>> __detail::_Node_iterator<V, T::__constant_iterators::value,
>>>>> T::__hash_cached::value>
>>>>> or new __hashtable::_Iterator<Const,
>>>>> T::__constant_iterators::value, A::pointer>
>>>>> type family internally is controlled by
>>>>> __hashtable::_Iterator_traits traits
>>>>> template.
>>>>>
>>>>> In case anybody is currently using std::_Hashtable with an
>>>>> allocator that has a
>>>>> fancy pointer, this change will be an ABI break, because their
>>>>> std::_Hashtable
>>>>> instantiations would start to (correctly) use the fancy
>>>>> pointer type. Note that
>>>>> the new type family used in this case is always caching the
>>>>> hash code at node
>>>>> level.
>>>>>
>>>>> Because std::_Hashtable will never use fancy pointers in C++98
>>>>> mode, recompiling
>>>>> everything to use fancy pointers isn't even possible if mixing
>>>>> C++98 and C++11
>>>>> code that uses std::_Hashtable. To alleviate this problem,
>>>>> compiling with
>>>>> -D_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE=0 will force
>>>>> std::_Hashtable to have the
>>>>> old, non-conforming behaviour and use raw pointers internally.
>>>>> For testing
>>>>> purposes, compiling with
>>>>> -D_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE=9001 will force
>>>>> std::_Hashtable to always use the new node types.
>>>>>
>>>>> This macro is currently undocumented, which needs to be fixed.
>>>>>
>>>>> libstdc++-v3/ChangeLog:
>>>>>
>>>>> PR libstdc++/57272
>>>>> * include/bits/hashtable.h
>>>>> (__hashtable::_Node_base<>, __hashtable::_Node<>): New.
>>>>> (__hashtable::_Iterator_base<>,
>>>>> __hashtable::_Iterator<>): New.
>>>>> (__hashtable::_Local_iterator<>): New.
>>>>> (__hashtable::_Node_traits<>,
>>>>> __hashtable::_Iterator_traits<>): New.
>>>>> (__hashtable::__alloc_ptr<>): New template alias.
>>>>> (_Hashtable<>::__node_type, __node_alloc_type,
>>>>> __node_alloc_traits, __node_ptr)
>>>>> (__node_base, __node_base_ptr, __buckets_ptr): Rename
>>>>> respectively into...
>>>>> (_Hashtable<>::_Node, _Node_alloc, _Node_alloc_traits,
>>>>> _Node_ptr)
>>>>> (_Node_base, _Base_ptr, _Buckets_ptr): ... those.
>>>>> (_Hashtable<>::_Buckets_ptr_traits): New.
>>>>> (_Hashtable<>::__hash_code_base_access): Remove.
>>>>> (_Hashtable<>::_S_v, _S_next, _M_single_bucket_ptr): New.
>>>>> (_Hashtable<>::_M_node_hash_code,
>>>>> _M_node_hash_code_ext, _M_bucket_index)
>>>>> (_M_bucket_index_ext, _M_key_equals, _M_key_equals_tr,
>>>>> _M_equals, _M_equals_tr)
>>>>> (_M_node_equals): New.
>>>>> (_Hashtable<>::__location_type::_M_base): New.
>>>>> (_Hashtable<>::_S_adapt): New.
>>>>> (_Hashtable<>): Adapt.
>>>>> * include/bits/hashtable_policy.h: Include
>>>>> <bits/ptr_traits.h>.
>>>>> Include <bits/stl_uninitialized.h>.
>>>>> (_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE): New macro,
>>>>> default to 1.
>>>>> (_Hash_node_base::_M_base_ptr): New.
>>>>> (_Hash_node<>::_M_node_ptr): New.
>>>>> (_Hash_code_base<>::_M_hash_code, _M_bucket_index):
>>>>> Remove.
>>>>> (_Hashtable_base<>::_M_key_equals, _M_key_equals_tr):
>>>>> Adapt to only take key
>>>>> type.
>>>>> (_Hashtable_base<>::_M_equals, _M_equals_tr,
>>>>> _M_node_equals): Remove.
>>>>> (_Hashtable_alloc<>): Adapt.
>>>>> * testsuite/23_containers/unordered_map/115939.cc: #undef
>>>>> _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE as types
>>>>> associated with fancy pointer
>>>>> support do not suffer from the ambiguity issue tested
>>>>> here.
>>>>> *
>>>>> testsuite/23_containers/unordered_map/allocator/ext_ptr.cc: New test.
>>>>> *
>>>>> testsuite/23_containers/unordered_map/requirements/explicit_instantiation/alloc_ptr.cc:
>>>>> New test case.
>>>>> *
>>>>> testsuite/23_containers/unordered_map/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
>>>>> New test case.
>>>>> *
>>>>> testsuite/23_containers/unordered_multimap/allocator/ext_ptr.cc:
>>>>> New test case.
>>>>> *
>>>>> testsuite/23_containers/unordered_multimap/requirements/explicit_instantiation/alloc_ptr.cc:
>>>>> New test case.
>>>>> *
>>>>> testsuite/23_containers/unordered_multimap/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
>>>>> New test case.
>>>>> *
>>>>> testsuite/23_containers/unordered_multiset/allocator/ext_ptr.cc:
>>>>> New test case.
>>>>> *
>>>>> testsuite/23_containers/unordered_multiset/requirements/explicit_instantiation/alloc_ptr.cc:
>>>>> New test case.
>>>>> *
>>>>> testsuite/23_containers/unordered_multiset/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
>>>>> New test case.
>>>>> *
>>>>> testsuite/23_containers/unordered_set/allocator/ext_ptr.cc: Adapt.
>>>>> *
>>>>> testsuite/23_containers/unordered_set/instantiation_neg.cc:
>>>>> Undef _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE.
>>>>> *
>>>>> testsuite/23_containers/unordered_set/requirements/explicit_instantiation/alloc_ptr.cc:
>>>>> New test case.
>>>>> *
>>>>> testsuite/23_containers/unordered_set/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
>>>>> New test case.
>>>>>
>>>>> Ok to commit ?
>>>>>
>>>>> See also:
>>>>>
>>>>> https://forge.sourceware.org/gcc/gcc-TEST/pulls/32
>>>>>
>>>>> François
>>>>>
>>>>>
>>>>> On 19/03/2025 21:09, François Dumont wrote:
>>>>>> Hi
>>>>>>
>>>>>> Following latest changes on unordered container I've rebased and
>>>>>> updated this patch to add fancy allocator 's pointer type support
>>>>>> in unordered containers.
>>>>>>
>>>>>> libstdc++: Add fancy pointer support to std::_Hashtable
>>>>>> [PR57272]
>>>>>>
>>>>>> The fancy allocator pointer type support is added to
>>>>>> std::unordered_map,
>>>>>> std::unordered_multimap, std::unordered_multiset and
>>>>>> std::unordered_set
>>>>>> through the underlying std::_Hashtable class.
>>>>>>
>>>>>> To respect ABI a new parralel hierarchy of node types has
>>>>>> been added.
>>>>>> This change introduces new class template parameterized on
>>>>>> the allocator's
>>>>>> void_pointer type, __hashtable::_Node_base, and new class
>>>>>> templates
>>>>>> parameterized on the allocator's pointer type,
>>>>>> __hashtable::_Node,
>>>>>> __hashtable::_Iterator, __hashtable::_Local_iterator. The
>>>>>> _Iterator class
>>>>>> template is used for both iterator and const_iterator. The
>>>>>> _Local_iterator
>>>>>> class template is used for both local_iterator and
>>>>>> const_local_iterator.
>>>>>> Whether std::_Hashtable<K, V, A, KoV, E, H, RH, U, RP, T>
>>>>>> should use the old
>>>>>> __detail::_Hash_node<V, T::__hash_cached::value> or new
>>>>>> __hashtable::_Node<A::pointer> type family internally is
>>>>>> controlled by a new
>>>>>> __hashtable::_Node_traits traits template. Whether it should
>>>>>> use the old
>>>>>> __detail::_Node_iterator<V, T::__constant_iterators::value,
>>>>>> T::__hash_cached::value>
>>>>>> or new __hashtable::_Iterator<Const,
>>>>>> T::__constant_iterators::value, A::pointer>
>>>>>> type family internally is controlled by
>>>>>> __hashtable::_Iterator_traits traits
>>>>>> template.
>>>>>>
>>>>>> In case anybody is currently using std::_Hashtable with an
>>>>>> allocator that has a
>>>>>> fancy pointer, this change would be an ABI break, because
>>>>>> their std::_Hashtable
>>>>>> instantiations would start to (correctly) use the fancy
>>>>>> pointer type. If the
>>>>>> fancy pointer just contains a single pointer and so has the
>>>>>> same size, layout,
>>>>>> and object representation as a raw pointer, the code might
>>>>>> still work (despite
>>>>>> being an ODR violation). But if their fancy pointer has a
>>>>>> different
>>>>>> representation, they would need to recompile all their code
>>>>>> using that
>>>>>> allocator with std::_Hashtable. Because std::_Hashtable will
>>>>>> never use fancy
>>>>>> pointers in C++98 mode, recompiling everything to use fancy
>>>>>> pointers isn't
>>>>>> even possible if mixing C++98 and C++11 code that uses
>>>>>> std::_Hashtable. To
>>>>>> alleviate this problem, compiling with
>>>>>> -D_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE=0
>>>>>> will force std::_Hashtable to have the old, non-conforming
>>>>>> behaviour and use
>>>>>> raw pointers internally. For testing purposes, compiling with
>>>>>> -D_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE=9001 will force
>>>>>> std::_Hashtable to
>>>>>> always use the new node types. This macro is currently
>>>>>> undocumented, which
>>>>>> needs to be fixed.
>>>>>>
>>>>>> Note that the new type family used in case of fancy allocator
>>>>>> pointer type is
>>>>>> always caching the hash code at node level.
>>>>>>
>>>>>> libstdc++-v3/ChangeLog:
>>>>>>
>>>>>> PR libstdc++/57272
>>>>>> * include/bits/hashtable.h
>>>>>> (__hashtable::_Node_base<>, __hashtable::_Node<>): New.
>>>>>> (__hashtable::_Iterator_base<>,
>>>>>> __hashtable::_Iterator<>): New.
>>>>>> (__hashtable::_Local_iterator<>): New.
>>>>>> (__hashtable::_Node_traits<>,
>>>>>> __hashtable::_Iterator_traits<>): New.
>>>>>> (_Hashtable<>::__node_type, __node_alloc_type,
>>>>>> __node_alloc_traits,
>>>>>> __node_ptr, __node_base, __node_base_ptr,
>>>>>> __buckets_ptr): Rename
>>>>>> respectively into...
>>>>>> (__hashtable::__alloc_ptr<>): New template alias.
>>>>>> (_Hashtable<>::_Node, _Node_alloc,
>>>>>> _Node_alloc_traits, _Node_ptr,
>>>>>> _Node_base, _Base_ptr, _Buckets_ptr): ... those.
>>>>>> (_Hashtable<>::_Buckets_ptr_traits): New.
>>>>>> (_Hashtable<>::__hash_code_base_access): Remove.
>>>>>> (_Hashtable<>::_S_v, _S_next, _M_single_bucket_ptr):
>>>>>> New.
>>>>>> (_Hashtable<>::_M_node_hash_code,
>>>>>> _M_node_hash_code_ext, _M_bucket_index,
>>>>>> _M_bucket_index_ext, _M_key_equals, _M_key_equals_tr,
>>>>>> _M_equals, _M_equals_tr,
>>>>>> _M_node_equals): New.
>>>>>> (_Hashtable<>::__location_type::_M_base): New.
>>>>>> (_Hashtable<>::_S_adapt): New.
>>>>>> (_Hashtable<>): Adapt.
>>>>>> * include/bits/hashtable_policy.h: Include
>>>>>> <bits/ptr_traits.h>.
>>>>>> Include <bits/stl_uninitialized.h>.
>>>>>> (_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE): New macro,
>>>>>> default to 1.
>>>>>> (_Hash_node_base::_M_base_ptr): New.
>>>>>> (_Hash_node<>::_M_node_ptr): New.
>>>>>> (_Hash_code_base<>::_M_hash_code, _M_bucket_index):
>>>>>> Remove.
>>>>>> (_Hashtable_base<>::_M_key_equals, _M_key_equals_tr):
>>>>>> Adapt to only take key
>>>>>> type.
>>>>>> (_Hashtable_base<>::_M_equals, _M_equals_tr,
>>>>>> _M_node_equals): Remove.
>>>>>> (_Hashtable_alloc<>): Adapt.
>>>>>> * testsuite/23_containers/unordered_map/115939.cc:
>>>>>> #undef
>>>>>> _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE as types
>>>>>> associated with fancy pointer
>>>>>> support do not suffer from the ambiguity issue tested
>>>>>> here.
>>>>>> *
>>>>>> testsuite/23_containers/unordered_map/allocator/ext_ptr.cc: New
>>>>>> test.
>>>>>> *
>>>>>> testsuite/23_containers/unordered_map/requirements/explicit_instantiation/alloc_ptr.cc:
>>>>>> New test case.
>>>>>> *
>>>>>> testsuite/23_containers/unordered_map/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
>>>>>> New test case.
>>>>>> *
>>>>>> testsuite/23_containers/unordered_multimap/allocator/ext_ptr.cc:
>>>>>> New test case.
>>>>>> *
>>>>>> testsuite/23_containers/unordered_multimap/requirements/explicit_instantiation/alloc_ptr.cc:
>>>>>> New test case.
>>>>>> *
>>>>>> testsuite/23_containers/unordered_multimap/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
>>>>>> New test case.
>>>>>> *
>>>>>> testsuite/23_containers/unordered_multiset/allocator/ext_ptr.cc:
>>>>>> New test case.
>>>>>> *
>>>>>> testsuite/23_containers/unordered_multiset/requirements/explicit_instantiation/alloc_ptr.cc:
>>>>>> New test case.
>>>>>> *
>>>>>> testsuite/23_containers/unordered_multiset/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
>>>>>> New test case.
>>>>>> *
>>>>>> testsuite/23_containers/unordered_set/allocator/ext_ptr.cc: Adapt.
>>>>>> *
>>>>>> testsuite/23_containers/unordered_set/instantiation_neg.cc:
>>>>>> Undef _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE.
>>>>>> *
>>>>>> testsuite/23_containers/unordered_set/requirements/explicit_instantiation/alloc_ptr.cc:
>>>>>> New test case.
>>>>>> *
>>>>>> testsuite/23_containers/unordered_set/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
>>>>>> New test case.
>>>>>>
>>>>>> Available as a PR here:
>>>>>>
>>>>>> https://forge.sourceware.org/gcc/gcc-TEST/pulls/32
>>>>>>
>>>>>> François
>>>>>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20260506/d8027aff/attachment-0001.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: hashtable_fancy_pointer_patch.txt.bz2
Type: application/x-bzip2
Size: 20147 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20260506/d8027aff/attachment-0001.bz2>
More information about the Libstdc++
mailing list