[PATCH] _Hashtable fancy pointer support

[François Dumont]

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
>>