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
