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
