[PATCH] _Hashtable fancy pointer support
François Dumont
frs.dumont@gmail.com
Sun Jul 6 14:04:48 GMT 2025
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 --------------
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 20f9bd98d5b..82090f58de5 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -50,22 +50,526 @@ namespace std _GLIBCXX_VISIBILITY(default)
_GLIBCXX_BEGIN_NAMESPACE_VERSION
/// @cond undocumented
- template<typename _Tp, typename _Hash>
+ template<typename _Key, typename _Hash>
using __cache_default
= __not_<__and_<// Do not cache for fast hasher.
__is_fast_hash<_Hash>,
// Mandatory for the rehash process.
- __is_nothrow_invocable<const _Hash&, const _Tp&>>>;
+ __is_nothrow_invocable<const _Hash&, const _Key&>>>;
// Helper to conditionally delete the default constructor.
- // The _Hash_node_base type is used to distinguish this specialization
+ // The _Hashtable_hash_traits type is used to distinguish this specialization
// from any other potentially-overlapping subobjects of the hashtable.
template<typename _Equal, typename _Hash, typename _Allocator>
using _Hashtable_enable_default_ctor
= _Enable_default_constructor<__and_<is_default_constructible<_Equal>,
is_default_constructible<_Hash>,
is_default_constructible<_Allocator>>{},
- __detail::_Hash_node_base>;
+ __detail::_Hashtable_hash_traits<_Hash>>;
+
+namespace __hashtable
+{
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE
+ template<typename _Ptr>
+ using __element_t = typename std::pointer_traits<_Ptr>::element_type;
+
+ template<typename _VoidPtr>
+ struct _Node_base
+ {
+ using _Base_ptr = __ptr_rebind<_VoidPtr, _Node_base>;
+
+ _Node_base() = default;
+ _Node_base(_Base_ptr __nxt) noexcept : _M_nxt(__nxt) { }
+ _Node_base(_Node_base&&) = delete;
+
+ _Base_ptr _M_nxt = nullptr;
+
+ // This is not const-correct, but it's only used in a const access path
+ // by std::_Hashtable::_M_locate() where the pointer is only used as
+ // before-begin node to bootstrap a research.
+ _Base_ptr
+ _M_base_ptr() const noexcept
+ {
+ return pointer_traits<_Base_ptr>::pointer_to
+ (*const_cast<_Node_base*>(this));
+ }
+ };
+
+ template<bool _Cache_hash_code>
+ struct _Node_hash_cache
+ { size_t _M_hash_code; };
+
+ template<>
+ struct _Node_hash_cache<false>
+ { };
+
+ template<typename _ValPtr>
+ struct _Node_data
+ {
+ using value_type = __element_t<_ValPtr>;
+
+ _Node_data() = default;
+ _Node_data(_Node_data&&) = delete;
+
+ union _Uninit_storage
+ {
+ _Uninit_storage() noexcept { }
+ ~_Uninit_storage() { }
+
+ value_type _M_data;
+ };
+ _Uninit_storage _M_u;
+
+ value_type*
+ _M_valptr() noexcept { return std::__addressof(_M_u._M_data); }
+
+ value_type const*
+ _M_valptr() const noexcept { return std::__addressof(_M_u._M_data); }
+
+ value_type&
+ _M_v() noexcept
+ { return *_M_valptr(); }
+
+ const value_type&
+ _M_v() const noexcept
+ { return *_M_valptr(); }
+ };
+
+ template<typename _ValPtr>
+ struct _Node
+ : public __hashtable::_Node_base<std::__ptr_rebind<_ValPtr, void>>
+ , public _Node_hash_cache<true>
+ , public _Node_data<_ValPtr>
+ {
+ using _Node_ptr = __ptr_rebind<_ValPtr, _Node>;
+
+ _Node() = default;
+ _Node(_Node&&) = delete;
+
+ _Node_ptr
+ _M_node_ptr() noexcept
+ {
+ using __ptr_traits = pointer_traits<_Node_ptr>;
+ return __ptr_traits::pointer_to(*this);
+ }
+
+ _Node_ptr
+ _M_next() const noexcept
+ {
+ return this->_M_nxt
+ ? static_cast<_Node&>(*this->_M_nxt)._M_node_ptr()
+ : nullptr;
+ }
+ };
+
+ // Mimics abi of __detail::_Hash_node to potentially preserve it.
+ template<typename _ValPtr, bool _Cache_hash_code>
+ struct _Node_legacy
+ : public __hashtable::_Node_base<std::__ptr_rebind<_ValPtr, void>>
+ , public _Node_data<_ValPtr>
+ , public _Node_hash_cache<_Cache_hash_code>
+ {
+ using _Node_ptr = __ptr_rebind<_ValPtr, _Node_legacy>;
+
+ _Node_legacy() = default;
+ _Node_legacy(_Node_legacy&&) = delete;
+
+ _Node_ptr
+ _M_node_ptr() noexcept
+ {
+ using __ptr_traits = pointer_traits<_Node_ptr>;
+ return __ptr_traits::pointer_to(*this);
+ }
+
+ _Node_ptr
+ _M_next() const noexcept
+ {
+ return this->_M_nxt
+ ? static_cast<_Node_legacy&>(*this->_M_nxt)._M_node_ptr()
+ : nullptr;
+ }
+ };
+
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE >= 9002
+ template<typename _ValPtr>
+ using __use_maybe_abi_backward_compatible_node = false_type;
+#elif _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE >= 9001
+ template<typename _ValPtr>
+ using __use_maybe_abi_backward_compatible_node = true_type;
+#else
+ template<typename _ValPtr>
+ using __use_maybe_abi_backward_compatible_node =
+ __bool_constant<sizeof(__element_t<_ValPtr>*) == sizeof(_ValPtr)>;
+#endif
+
+ template<typename _ValPtr, bool _Cache_hash_code>
+ using __node_t = __conditional_t<
+ __use_maybe_abi_backward_compatible_node<_ValPtr>::value,
+ _Node_legacy<_ValPtr, _Cache_hash_code>,
+ _Node<_ValPtr>>;
+
+ template<typename _ValPtr>
+ struct _Iterator_base
+ {
+ using _Node_base = __hashtable::_Node_base<__ptr_rebind<_ValPtr, void>>;
+ using _Base_ptr = __ptr_rebind<_ValPtr, _Node_base>;
+
+ _Iterator_base() noexcept
+ : _M_cur() { }
+
+ constexpr explicit
+ _Iterator_base(_Base_ptr __x) noexcept
+ : _M_cur(__x) { }
+
+ _Iterator_base(const _Iterator_base&) = default;
+ _Iterator_base& operator=(const _Iterator_base&) = default;
+
+ [[__nodiscard__]]
+ friend bool
+ operator==(const _Iterator_base& __x, const _Iterator_base& __y) noexcept
+ { return __x._M_cur == __y._M_cur; }
+
+#if ! __cpp_lib_three_way_comparison
+ [[__nodiscard__]]
+ friend bool
+ operator!=(const _Iterator_base& __x, const _Iterator_base& __y) noexcept
+ { return __x._M_cur != __y._M_cur; }
+#endif
+
+ _Base_ptr _M_cur;
+ };
+
+ template<typename _ValPtr, bool _Hash_code_cached,
+ bool _Const, bool _ConstantIterator>
+ struct _Iterator : public _Iterator_base<_ValPtr>
+ {
+ template<typename _Tp>
+ using __maybe_const = __conditional_t<_Const || _ConstantIterator,
+ const _Tp, _Tp>;
+
+ using __ptr_traits = pointer_traits<_ValPtr>;
+ using value_type = typename __ptr_traits::element_type;
+ using reference = __maybe_const<value_type>&;
+ using pointer = __maybe_const<value_type>*;
+
+ using iterator_category = forward_iterator_tag;
+ using difference_type = typename __ptr_traits::difference_type;
+
+ using _IteratorBase = _Iterator_base<_ValPtr>;
+ using _Node_base = typename _IteratorBase::_Node_base;
+ using _Base_ptr = typename _IteratorBase::_Base_ptr;
+
+ _Iterator() = default;
+
+ constexpr explicit
+ _Iterator(_Base_ptr __x) noexcept
+ : _IteratorBase(__x) { }
+
+ _Iterator(const _Iterator&) = default;
+ _Iterator& operator=(const _Iterator&) = default;
+
+#ifdef __glibcxx_concepts
+ constexpr
+ _Iterator(const _Iterator<_ValPtr, _Hash_code_cached,
+ false, _ConstantIterator>& __it)
+ requires _Const
+#else
+ template<bool _OtherConst,
+ typename = __enable_if_t<_Const && !_OtherConst>>
+ constexpr
+ _Iterator(const _Iterator<_ValPtr, _Hash_code_cached,
+ _OtherConst, _ConstantIterator>& __it)
+#endif
+ : _IteratorBase(__it._M_cur) { }
+
+ [[__nodiscard__]]
+ reference
+ operator*() const noexcept
+ {
+ using _Node = __node_t<_ValPtr, _Hash_code_cached>;
+ return static_cast<_Node&>(*this->_M_cur)._M_v();
+ }
+
+ [[__nodiscard__]]
+ pointer
+ operator->() const noexcept
+ {
+ using _Node = __node_t<_ValPtr, _Hash_code_cached>;
+ return static_cast<_Node&>(*this->_M_cur)._M_valptr();
+ }
+
+ _GLIBCXX14_CONSTEXPR _Iterator&
+ operator++() noexcept
+ {
+ this->_M_cur = this->_M_cur->_M_nxt;
+ return *this;
+ }
+
+ _GLIBCXX14_CONSTEXPR _Iterator
+ operator++(int) noexcept
+ {
+ _Iterator __tmp(this->_M_cur);
+ ++*this;
+ return __tmp;
+ }
+ };
+
+ template<typename _ValPtr, bool _Hash_code_cached,
+ bool _Const, bool _ConstantIterator,
+ typename _RangeHash>
+ struct _Local_iterator : public _Iterator<_ValPtr, _Hash_code_cached,
+ _Const, _ConstantIterator>
+ {
+ using _IteratorBase = _Iterator<_ValPtr, _Hash_code_cached,
+ _Const, _ConstantIterator>;
+ using _Base_ptr = typename _IteratorBase::_Base_ptr;
+
+ _Local_iterator() = default;
+
+ constexpr
+ _Local_iterator(_Base_ptr __x, size_t __bkt, size_t __bkt_count) noexcept
+ : _IteratorBase(__x), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
+ { }
+
+ _Local_iterator(const _Local_iterator&) = default;
+ _Local_iterator& operator=(const _Local_iterator&) = default;
+
+#ifdef __glibcxx_concepts
+ constexpr
+ _Local_iterator(const _Local_iterator<
+ _ValPtr, _Hash_code_cached,
+ false, _ConstantIterator, _RangeHash>& __it)
+ requires _Const
+#else
+ template<bool _OtherConst,
+ typename = __enable_if_t<_Const && !_OtherConst>>
+ constexpr
+ _Local_iterator(const _Local_iterator<
+ _ValPtr, _Hash_code_cached,
+ _OtherConst, _ConstantIterator, _RangeHash>& __it)
+#endif
+ : _IteratorBase(__it._M_cur)
+ , _M_bucket(__it._M_bucket), _M_bucket_count(__it._M_bucket_count)
+ { }
+
+ _GLIBCXX14_CONSTEXPR _Local_iterator&
+ operator++() noexcept
+ {
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
+ this->_M_cur = this->_M_cur->_M_nxt;
+ if constexpr (_Hash_code_cached)
+ {
+ if (this->_M_cur)
+ {
+ using _Node = __node_t<_ValPtr, _Hash_code_cached>;
+ size_t __bkt =
+ _RangeHash{}(static_cast<_Node&>(*this->_M_cur)._M_hash_code,
+ _M_bucket_count);
+ if (__bkt != _M_bucket)
+ this->_M_cur = nullptr;
+ }
+ }
+#pragma GCC diagnostic pop
+ return *this;
+ }
+
+ _GLIBCXX14_CONSTEXPR _Local_iterator
+ operator++(int) noexcept
+ {
+ _Local_iterator __tmp(*this);
+ ++*this;
+ return __tmp;
+ }
+
+ size_t
+ _M_get_bucket() const { return _M_bucket; } // for debug mode
+
+ size_t _M_bucket = 0;
+ size_t _M_bucket_count = 0;
+ };
+#endif // USE_ALLOC_PTR_FOR_HASHTABLE
+
+ // Determine the node types used by std::_Hashtable.
+ template<typename _Val, typename _ValPtr, typename _Traits>
+ struct _Node_traits;
+
+ // Determine the iterator types used by std::_Hashtable.
+ template<typename _Key, typename _Val, typename _ValPtr,
+ typename _ExtractKey, typename _Hash, typename _RangeHash,
+ typename _Unused, typename _Traits>
+ struct _Iterator_traits;
+
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE <= 9000
+ // Specialization for the simple case where the allocator's pointer type
+ // is the same type as value_type*.
+ // For ABI compatibility we can't change the types used for this case.
+ template<typename _Val, typename _Traits>
+ struct _Node_traits<_Val, _Val*, _Traits>
+ {
+ using __hash_cached = typename _Traits::__hash_cached;
+
+ using value_type = _Val;
+ using _Node = __detail::_Hash_node<_Val, __hash_cached::value>;
+ using _Node_ptr = _Node*;
+ using _Node_base = __detail::_Hash_node_base;
+ using _Base_ptr = _Node_base*;
+ using _Buckets_ptr = _Base_ptr*;
+ };
+
+ template<typename _Key, typename _Val,
+ typename _ExtractKey, typename _Hash, typename _RangeHash,
+ typename _Unused, typename _Traits>
+ struct _Iterator_traits<_Key, _Val, _Val*,
+ _ExtractKey, _Hash, _RangeHash, _Unused, _Traits>
+ {
+ using __find_local_iterator_end = false_type;
+ using _NodeTraits = _Node_traits<_Val, _Val*, _Traits>;
+ using _Base_ptr = typename _NodeTraits::_Base_ptr;
+ using _Node_ptr = typename _NodeTraits::_Node_ptr;
+
+ using __constant_iterators = typename _Traits::__constant_iterators;
+ using __hash_cached = typename _Traits::__hash_cached;
+
+ using iterator =
+ __detail::_Node_iterator<_Val,
+ __constant_iterators::value,
+ __hash_cached::value>;
+
+ using const_iterator
+ = __detail::_Node_const_iterator<_Val,
+ __constant_iterators::value,
+ __hash_cached::value>;
+
+ using local_iterator =
+ __detail::_Local_iterator<_Key, _Val, _ExtractKey, _Hash,
+ _RangeHash, _Unused,
+ __constant_iterators::value,
+ __hash_cached::value>;
+
+ using const_local_iterator =
+ __detail::_Local_const_iterator<_Key, _Val, _ExtractKey, _Hash,
+ _RangeHash, _Unused,
+ __constant_iterators::value,
+ __hash_cached::value>;
+
+ static iterator
+ _S_iterator(_Base_ptr __p) noexcept
+ { return iterator(static_cast<_Node_ptr>(__p)); }
+
+ static const_iterator
+ _S_const_iterator(_Base_ptr __p) noexcept
+ { return const_iterator(static_cast<_Node_ptr>(__p)); }
+
+ using __hash_code_base =
+ __detail::_Hash_code_base<_Key, _Val, _ExtractKey, _Hash, _RangeHash,
+ _Unused, __hash_cached::value>;
+
+ static local_iterator
+ _S_local_iterator(const __hash_code_base& __base,
+ _Base_ptr __p, size_t __bkt, size_t __bkt_count)
+ {
+ return local_iterator(__base, static_cast<_Node_ptr>(__p),
+ __bkt, __bkt_count);
+ }
+
+ static const_local_iterator
+ _S_const_local_iterator(const __hash_code_base& __base,
+ _Base_ptr __p, size_t __bkt, size_t __bkt_count)
+ {
+ return const_local_iterator(__base, static_cast<_Node_ptr>(__p),
+ __bkt, __bkt_count);
+ }
+ };
+#endif
+
+#if ! _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE
+ // Always use the T* specialization.
+ template<typename _Val, typename _ValPtr, typename _Traits>
+ struct _Node_traits
+ : _Node_traits<_Val, _Val*, _Traits>
+ { };
+
+ template<typename _Key, typename _Val, typename _ValPtr,
+ typename _ExtractKey, typename _Hash, typename _RangeHash,
+ typename _Unused, typename _Traits>
+ struct _Iterator_traits
+ : _Iterator_traits<_Key, _Val, _Val*,
+ _ExtractKey, _Hash, _RangeHash, _Unused, _Traits>
+ { };
+#else
+ // Primary template used when the allocator uses fancy pointers.
+ template<typename _Val, typename _ValPtr, typename _Traits>
+ struct _Node_traits
+ {
+ using value_type = _Val;
+ using __hash_cached = std::__conditional_t<
+ __use_maybe_abi_backward_compatible_node<_ValPtr>::value,
+ typename _Traits::__hash_cached,
+ true_type>;
+ using _Node = __node_t<_ValPtr, __hash_cached::value>;
+ using _Node_ptr = __ptr_rebind<_ValPtr, _Node>;
+ using _Node_base = __hashtable::_Node_base<__ptr_rebind<_ValPtr, void>>;
+ using _Base_ptr = __ptr_rebind<_ValPtr, _Node_base>;
+ using _Buckets_ptr = __ptr_rebind<_ValPtr, _Base_ptr>;
+ };
+
+ template<typename _Key, typename _Val, typename _ValPtr,
+ typename _ExtractKey, typename _Hash, typename _RangeHash,
+ typename _Unused, typename _Traits>
+ struct _Iterator_traits
+ {
+ using _NodeTraits = _Node_traits<_Val, _ValPtr, _Traits>;
+ using _Base_ptr = typename _NodeTraits::_Base_ptr;
+ using _Node_ptr = typename _NodeTraits::_Node_ptr;
+
+ using __node_hash_cached = typename _NodeTraits::__hash_cached;
+ using __find_local_iterator_end =
+ __bool_constant<!__node_hash_cached::value>;
+ using __hash_cached = typename _Traits::__hash_cached;
+ using __constant_iterators = typename _Traits::__constant_iterators;
+
+ using iterator =
+ __hashtable::_Iterator<_ValPtr, __node_hash_cached::value,
+ false, __constant_iterators::value>;
+ using const_iterator =
+ __hashtable::_Iterator<_ValPtr, __node_hash_cached::value,
+ true, __constant_iterators::value>;
+ using local_iterator = __hashtable::_Local_iterator<
+ _ValPtr, __node_hash_cached::value,
+ false, __constant_iterators::value, _RangeHash>;
+ using const_local_iterator = __hashtable::_Local_iterator<
+ _ValPtr, __node_hash_cached::value,
+ true, __constant_iterators::value, _RangeHash>;
+
+ static iterator
+ _S_iterator(_Base_ptr __p) noexcept
+ { return iterator(__p); }
+
+ static const_iterator
+ _S_const_iterator(_Base_ptr __p) noexcept
+ { return const_iterator(__p); }
+
+ using __hash_code_base =
+ __detail::_Hash_code_base<_Key, _Val, _ExtractKey, _Hash, _RangeHash,
+ _Unused, __hash_cached::value>;
+
+ static local_iterator
+ _S_local_iterator(const __hash_code_base&,
+ _Base_ptr __p, size_t __bkt, size_t __bkt_count)
+ { return local_iterator(__p, __bkt, __bkt_count); }
+
+ static const_local_iterator
+ _S_const_local_iterator(const __hash_code_base&,
+ _Base_ptr __p, size_t __bkt, size_t __bkt_count)
+ { return const_local_iterator(__p, __bkt, __bkt_count); }
+ };
+#endif
+
+ template<typename _Alloc>
+ using __alloc_ptr =
+ typename __gnu_cxx::__alloc_traits<_Alloc>::pointer;
+} // namespace __hashtable
/**
* Primary class template _Hashtable.
@@ -196,9 +700,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Hash, _RangeHash, _Unused,
_RehashPolicy, _Traits>,
private __detail::_Hashtable_alloc<
- __alloc_rebind<_Alloc,
- __detail::_Hash_node<_Value,
- _Traits::__hash_cached::value>>>,
+ __hashtable::_Node_traits<_Value,
+ __hashtable::__alloc_ptr<__alloc_rebind<_Alloc, _Value>>, _Traits>,
+ _Alloc>,
private _Hashtable_enable_default_ctor<_Equal, _Hash, _Alloc>
{
static_assert(is_same<typename remove_cv<_Value>::type, _Value>::value,
@@ -211,23 +715,33 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
"hash function must be copy constructible");
using __traits_type = _Traits;
- using __hash_cached = typename __traits_type::__hash_cached;
using __constant_iterators = typename __traits_type::__constant_iterators;
- using __node_type = __detail::_Hash_node<_Value, __hash_cached::value>;
- using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
-
- using __hashtable_alloc = __detail::_Hashtable_alloc<__node_alloc_type>;
-
- using __node_value_type =
- __detail::_Hash_node_value<_Value, __hash_cached::value>;
- using __node_ptr = typename __hashtable_alloc::__node_ptr;
- using __value_alloc_traits =
- typename __hashtable_alloc::__value_alloc_traits;
- using __node_alloc_traits =
- typename __hashtable_alloc::__node_alloc_traits;
- using __node_base = typename __hashtable_alloc::__node_base;
- using __node_base_ptr = typename __hashtable_alloc::__node_base_ptr;
- using __buckets_ptr = typename __hashtable_alloc::__buckets_ptr;
+
+ using _Value_alloc = __alloc_rebind<_Alloc, _Value>;
+ using _Value_alloc_traits = std::allocator_traits<_Value_alloc>;
+
+ using _Node_traits = __hashtable::_Node_traits<
+ _Value, __hashtable::__alloc_ptr<_Value_alloc>, _Traits>;
+ using __hash_cached = typename _Node_traits::__hash_cached;
+
+ using _Iterator_traits = __hashtable::_Iterator_traits<
+ _Key, _Value, __hashtable::__alloc_ptr<_Value_alloc>,
+ _ExtractKey, _Hash, _RangeHash, _Unused, _Traits>;
+
+ using _Node = typename _Node_traits::_Node;
+ using _Node_alloc = __alloc_rebind<_Alloc, _Node>;
+
+ // Use __gnu_cxx to benefit from _S_always_equal and al.
+ using _Node_alloc_traits = __gnu_cxx::__alloc_traits<_Node_alloc>;
+
+ using __hashtable_alloc =
+ __detail::_Hashtable_alloc<_Node_traits, _Alloc>;
+
+ using _Node_ptr = typename _Node_traits::_Node_ptr;
+ using _Node_base = typename _Node_traits::_Node_base;
+ using _Base_ptr = typename _Node_traits::_Base_ptr;
+ using _Buckets_ptr = typename _Node_traits::_Buckets_ptr;
+ using _Buckets_ptr_traits = pointer_traits<_Buckets_ptr>;
using __enable_default_ctor
= _Hashtable_enable_default_ctor<_Equal, _Hash, _Alloc>;
@@ -235,35 +749,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
= __detail::_RehashStateGuard<_RehashPolicy>;
public:
- typedef _Key key_type;
- typedef _Value value_type;
- typedef _Alloc allocator_type;
- typedef _Equal key_equal;
+ using key_type = _Key;
+ using value_type = _Value;
+ using allocator_type = _Alloc;
+ using key_equal = _Equal;
// mapped_type, if present, comes from _Map_base.
// hasher, if present, comes from _Hash_code_base/_Hashtable_base.
- typedef typename __value_alloc_traits::pointer pointer;
- typedef typename __value_alloc_traits::const_pointer const_pointer;
- typedef value_type& reference;
- typedef const value_type& const_reference;
+ using pointer = typename _Value_alloc_traits::pointer;
+ using const_pointer = typename _Value_alloc_traits::const_pointer;
+ using reference = value_type&;
+ using const_reference = const value_type&;
- using iterator
- = __detail::_Node_iterator<_Value, __constant_iterators::value,
- __hash_cached::value>;
-
- using const_iterator
- = __detail::_Node_const_iterator<_Value, __constant_iterators::value,
- __hash_cached::value>;
-
- using local_iterator = __detail::_Local_iterator<key_type, _Value,
- _ExtractKey, _Hash, _RangeHash, _Unused,
- __constant_iterators::value,
- __hash_cached::value>;
-
- using const_local_iterator = __detail::_Local_const_iterator<
- key_type, _Value,
- _ExtractKey, _Hash, _RangeHash, _Unused,
- __constant_iterators::value, __hash_cached::value>;
+ using iterator = typename _Iterator_traits::iterator;
+ using const_iterator = typename _Iterator_traits::const_iterator;
+ using local_iterator = typename _Iterator_traits::local_iterator;
+ using const_local_iterator = typename _Iterator_traits::const_local_iterator;
private:
using __rehash_type = _RehashPolicy;
@@ -295,7 +796,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
struct _Scoped_node
{
// Take ownership of a node with a constructed element.
- _Scoped_node(__node_ptr __n, __hashtable_alloc* __h)
+ _Scoped_node(_Node_ptr __n, __hashtable_alloc* __h)
: _M_h(__h), _M_node(__n) { }
// Allocate a node and construct an element within it.
@@ -312,16 +813,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Scoped_node& operator=(const _Scoped_node&) = delete;
__hashtable_alloc* _M_h;
- __node_ptr _M_node;
+ _Node_ptr _M_node;
};
// Compile-time diagnostics.
- // _Hash_code_base has everything protected, so use this derived type to
- // access it.
- struct __hash_code_base_access : __hash_code_base
- { using __hash_code_base::_M_bucket_index; };
-
// To get bucket index we need _RangeHash to be non-throwing.
static_assert(is_nothrow_default_constructible<_RangeHash>::value,
"Functor used to map hash code to bucket index"
@@ -350,14 +846,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
using difference_type = typename __hashtable_base::difference_type;
#if __cplusplus > 201402L
- using node_type = _Node_handle<_Key, _Value, __node_alloc_type>;
+ using node_type = _Node_handle<_Key, _Value, _Node_alloc>;
using insert_return_type = _Node_insert_return<iterator, node_type>;
#endif
private:
- __buckets_ptr _M_buckets = &_M_single_bucket;
+ _Buckets_ptr _M_buckets =
+ _Buckets_ptr_traits::pointer_to(_M_single_bucket);
size_type _M_bucket_count = 1;
- __node_base _M_before_begin;
+ _Node_base _M_before_begin;
size_type _M_element_count = 0;
_RehashPolicy _M_rehash_policy;
@@ -367,25 +864,39 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// qualified.
// Note that we can't leave hashtable with 0 bucket without adding
// numerous checks in the code to avoid 0 modulus.
- __node_base_ptr _M_single_bucket = nullptr;
+ _Base_ptr _M_single_bucket = nullptr;
+
+ static _Base_ptr
+ _S_next(_Base_ptr __p) noexcept
+ { return __p ? __p->_M_nxt : nullptr; }
+
+ _Buckets_ptr
+ _M_single_bucket_ptr()
+ { return _Buckets_ptr_traits::pointer_to(_M_single_bucket); }
void
_M_update_bbegin()
{
- if (auto __begin = _M_begin())
- _M_buckets[_M_bucket_index(*__begin)] = &_M_before_begin;
+ if (_Base_ptr __begin = _M_before_begin._M_nxt)
+ {
+ _M_buckets[_M_bucket_index(*__begin)] =
+ _M_before_begin._M_base_ptr();
+ }
}
void
- _M_update_bbegin(__node_ptr __n)
+ _M_update_bbegin(_Base_ptr __n)
{
_M_before_begin._M_nxt = __n;
_M_update_bbegin();
}
bool
- _M_uses_single_bucket(__buckets_ptr __bkts) const
- { return __builtin_expect(__bkts == &_M_single_bucket, false); }
+ _M_uses_single_bucket(_Buckets_ptr __bkts) const
+ {
+ return __builtin_expect
+ (std::addressof(*__bkts) == std::addressof(_M_single_bucket), 0);
+ }
bool
_M_uses_single_bucket() const
@@ -401,20 +912,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__hashtable_alloc&
_M_base_alloc() { return *this; }
- __buckets_ptr
+ _Buckets_ptr
_M_allocate_buckets(size_type __bkt_count)
{
if (__builtin_expect(__bkt_count == 1, false))
{
_M_single_bucket = nullptr;
- return &_M_single_bucket;
+ return _M_single_bucket_ptr();
}
return __hashtable_alloc::_M_allocate_buckets(__bkt_count);
}
void
- _M_deallocate_buckets(__buckets_ptr __bkts, size_type __bkt_count)
+ _M_deallocate_buckets(_Buckets_ptr __bkts, size_type __bkt_count)
{
if (_M_uses_single_bucket(__bkts))
return;
@@ -426,19 +937,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_deallocate_buckets()
{ _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
- // Gets bucket begin, deals with the fact that non-empty buckets contain
- // their before begin node.
- __node_ptr
- _M_bucket_begin(size_type __bkt) const
+ _Node_ptr
+ _M_begin() const
{
- __node_base_ptr __n = _M_buckets[__bkt];
- return __n ? static_cast<__node_ptr>(__n->_M_nxt) : nullptr;
+ return _M_before_begin._M_nxt
+ ? static_cast<_Node&>(*_M_before_begin._M_nxt)._M_node_ptr()
+ : nullptr;
}
- __node_ptr
- _M_begin() const
- { return static_cast<__node_ptr>(_M_before_begin._M_nxt); }
-
// Assign *this using another _Hashtable instance. Whether elements
// are copied or moved depends on the _Ht reference.
template<typename _Ht>
@@ -449,7 +955,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
void
_M_assign(_Ht&& __ht)
{
- __detail::_AllocNode<__node_alloc_type> __alloc_node_gen(*this);
+ __detail::_AllocNode<_Node_traits, _Alloc> __alloc_node_gen(*this);
_M_assign(std::forward<_Ht>(__ht), __alloc_node_gen);
}
@@ -466,10 +972,31 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
void
_M_reset() noexcept;
+ _Base_ptr
+ _M_end_ptr(size_type __bkt) const
+ {
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
+ _Base_ptr __end_ptr = nullptr;
+ if constexpr (!_Iterator_traits::__find_local_iterator_end::value)
+ return __end_ptr;
+ else
+ {
+ _Node_base __n_base { _S_next(_M_buckets[__bkt]) };
+ __end_ptr = __n_base._M_base_ptr();
+ for (; __end_ptr->_M_nxt; __end_ptr = __end_ptr->_M_nxt)
+ if (_M_bucket_index(*__end_ptr->_M_nxt) != __bkt)
+ break;
+
+ return __end_ptr->_M_nxt;
+ }
+#pragma GCC diagnostic pop
+ }
+
_Hashtable(const _Hash& __h, const _Equal& __eq,
const allocator_type& __a)
: __hashtable_base(__h, __eq),
- __hashtable_alloc(__node_alloc_type(__a)),
+ __hashtable_alloc(_Node_alloc(__a)),
__enable_default_ctor(_Enable_default_constructor_tag{})
{ }
@@ -489,11 +1016,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
#endif
}
- _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
+ _Hashtable(_Hashtable&& __ht, _Node_alloc&& __a,
true_type /* alloc always equal */)
noexcept(_S_nothrow_move());
- _Hashtable(_Hashtable&&, __node_alloc_type&&,
+ _Hashtable(_Hashtable&&, _Node_alloc&&,
false_type /* alloc always equal */);
template<typename _InputIterator>
@@ -530,14 +1057,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{ }
_Hashtable(_Hashtable&& __ht, const allocator_type& __a)
- noexcept(_S_nothrow_move<__node_alloc_traits::_S_always_equal()>())
- : _Hashtable(std::move(__ht), __node_alloc_type(__a),
- typename __node_alloc_traits::is_always_equal{})
+ noexcept(_S_nothrow_move<_Node_alloc_traits::_S_always_equal()>())
+ : _Hashtable(std::move(__ht), _Node_alloc(__a),
+ typename _Node_alloc_traits::is_always_equal{})
{ }
explicit
_Hashtable(const allocator_type& __a)
- : __hashtable_alloc(__node_alloc_type(__a)),
+ : __hashtable_alloc(_Node_alloc(__a)),
__enable_default_ctor(_Enable_default_constructor_tag{})
{ }
@@ -565,13 +1092,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Hashtable&
operator=(_Hashtable&& __ht)
- noexcept(__node_alloc_traits::_S_nothrow_move()
+ noexcept(_Node_alloc_traits::_S_nothrow_move()
&& is_nothrow_move_assignable<_Hash>::value
&& is_nothrow_move_assignable<_Equal>::value)
{
constexpr bool __move_storage =
- __node_alloc_traits::_S_propagate_on_move_assign()
- || __node_alloc_traits::_S_always_equal();
+ _Node_alloc_traits::_S_propagate_on_move_assign()
+ || _Node_alloc_traits::_S_always_equal();
_M_move_assign(std::move(__ht), __bool_constant<__move_storage>());
return *this;
}
@@ -582,7 +1109,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
operator=(initializer_list<value_type> __l)
{
using __reuse_or_alloc_node_gen_t =
- __detail::_ReuseOrAllocNode<__node_alloc_type>;
+ __detail::_ReuseOrAllocNode<_Node_traits, _Alloc>;
__reuse_or_alloc_node_gen_t __roan(_M_begin(), *this);
_M_before_begin._M_nxt = nullptr;
@@ -614,7 +1141,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
else
{
- __code = this->_M_hash_code(__k);
+ __code = _M_hash_code(__k);
__bkt = _M_bucket_index(__code);
}
@@ -635,11 +1162,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// Basic container operations
iterator
begin() noexcept
- { return iterator(_M_begin()); }
+ { return _Iterator_traits::_S_iterator(_M_before_begin._M_nxt); }
const_iterator
begin() const noexcept
- { return const_iterator(_M_begin()); }
+ { return _Iterator_traits::_S_const_iterator(_M_before_begin._M_nxt); }
iterator
end() noexcept
@@ -651,7 +1178,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
const_iterator
cbegin() const noexcept
- { return const_iterator(_M_begin()); }
+ { return _Iterator_traits::_S_const_iterator(_M_before_begin._M_nxt); }
const_iterator
cend() const noexcept
@@ -671,7 +1198,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
size_type
max_size() const noexcept
- { return __node_alloc_traits::max_size(this->_M_node_allocator()); }
+ { return _Node_alloc_traits::max_size(this->_M_node_allocator()); }
// Observers
key_equal
@@ -695,41 +1222,50 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
size_type
bucket(const key_type& __k) const
- { return _M_bucket_index(this->_M_hash_code(__k)); }
+ { return _M_bucket_index(_M_hash_code(__k)); }
local_iterator
begin(size_type __bkt)
{
- return local_iterator(*this, _M_bucket_begin(__bkt),
- __bkt, _M_bucket_count);
+ return _Iterator_traits::_S_local_iterator
+ (*this, _S_next(_M_buckets[__bkt]), __bkt, _M_bucket_count);
}
local_iterator
end(size_type __bkt)
- { return local_iterator(*this, nullptr, __bkt, _M_bucket_count); }
+ {
+ return _Iterator_traits::_S_local_iterator
+ (*this, _M_end_ptr(__bkt), __bkt, _M_bucket_count);
+ }
const_local_iterator
begin(size_type __bkt) const
{
- return const_local_iterator(*this, _M_bucket_begin(__bkt),
- __bkt, _M_bucket_count);
+ return _Iterator_traits::_S_const_local_iterator
+ (*this, _S_next(_M_buckets[__bkt]), __bkt, _M_bucket_count);
}
const_local_iterator
end(size_type __bkt) const
- { return const_local_iterator(*this, nullptr, __bkt, _M_bucket_count); }
+ {
+ return _Iterator_traits::_S_const_local_iterator
+ (*this, _M_end_ptr(__bkt), __bkt, _M_bucket_count);
+ }
// DR 691.
const_local_iterator
cbegin(size_type __bkt) const
{
- return const_local_iterator(*this, _M_bucket_begin(__bkt),
- __bkt, _M_bucket_count);
+ return _Iterator_traits::_S_const_local_iterator
+ (*this, _S_next(_M_buckets[__bkt]), __bkt, _M_bucket_count);
}
const_local_iterator
cend(size_type __bkt) const
- { return const_local_iterator(*this, nullptr, __bkt, _M_bucket_count); }
+ {
+ return _Iterator_traits::_S_const_local_iterator
+ (*this, _M_end_ptr(__bkt), __bkt, _M_bucket_count);
+ }
float
load_factor() const noexcept
@@ -801,59 +1337,137 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
void _M_rehash_insert(size_type __n);
private:
- // Bucket index computation helpers.
- size_type
- _M_bucket_index(const __node_value_type& __n) const noexcept
- { return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
+ static value_type&
+ _S_v(_Node_base& __n) noexcept
+ { return static_cast<_Node&>(__n)._M_v(); }
- size_type
- _M_bucket_index(__hash_code __c) const
- { return __hash_code_base::_M_bucket_index(__c, _M_bucket_count); }
+ using __hashtable_base::_M_hash_code;
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
+ __hash_code
+ _M_node_hash_code(const _Node_base& __n) const
+ {
+ const _Node& __from = static_cast<const _Node&>(__n);
+ if constexpr (__hash_cached::value)
+ return __from._M_hash_code;
+ else
+ return _M_hash_code(_ExtractKey{}(__from._M_v()));
+ }
+
// Get hash code for a node that comes from another _Hashtable.
// Reuse a cached hash code if the hash function is stateless,
// otherwise recalculate it using our own hash function.
__hash_code
- _M_hash_code_ext(const __node_value_type& __from) const
+ _M_node_hash_code_ext(const _Node_base& __n) const
{
+ const _Node& __from = static_cast<const _Node&>(__n);
if constexpr (__and_<__hash_cached, is_empty<_Hash>>::value)
return __from._M_hash_code;
else
- return this->_M_hash_code(_ExtractKey{}(__from._M_v()));
+ return _M_hash_code(_ExtractKey{}(__from._M_v()));
}
+ // Bucket index computation helpers.
+ size_type
+ _M_bucket_index(const _Node_base& __n) const noexcept
+ { return _RangeHash{}(_M_node_hash_code(__n), _M_bucket_count); }
+
+ size_type
+ _M_bucket_index(const _Node_base& __n,
+ size_type __bkt_count) const noexcept
+ { return _RangeHash{}(_M_node_hash_code(__n), __bkt_count); }
+
+ size_type
+ _M_bucket_index(__hash_code __c) const
+ { return _RangeHash{}(__c, _M_bucket_count); }
+
// Like _M_bucket_index but when the node is coming from another
// container instance.
size_type
- _M_bucket_index_ext(const __node_value_type& __from) const
- { return _RangeHash{}(_M_hash_code_ext(__from), _M_bucket_count); }
+ _M_bucket_index_ext(const _Node_base& __from) const
+ { return _RangeHash{}(_M_node_hash_code_ext(__from), _M_bucket_count); }
void
- _M_copy_code(__node_value_type& __to,
- const __node_value_type& __from) const
+ _M_copy_code(_Node& __to, const _Node& __from) const
{
if constexpr (__hash_cached::value)
- __to._M_hash_code = _M_hash_code_ext(__from);
+ __to._M_hash_code = _M_node_hash_code_ext(__from);
}
void
- _M_store_code(__node_value_type& __to, __hash_code __code) const
+ _M_store_code(_Node& __to, __hash_code __code) const
{
if constexpr (__hash_cached::value)
__to._M_hash_code = __code;
}
+
+ bool
+ _M_key_equals(const key_type& __k, const _Node_base& __n) const
+ {
+ const _Node& __node = static_cast<const _Node&>(__n);
+ return __hashtable_base::_M_key_equals
+ (__k, _ExtractKey{}(__node._M_v()));
+ }
+
+ template<typename _Kt>
+ bool
+ _M_key_equals_tr(const _Kt& __k, const _Node_base& __n) const
+ {
+ const _Node& __node = static_cast<const _Node&>(__n);
+ return __hashtable_base::_M_key_equals_tr
+ (__k, _ExtractKey{}(__node._M_v()));
+ }
+
+ bool
+ _M_equals(const key_type& __k, __hash_code __c,
+ const _Node_base& __n) const
+ {
+ const _Node& __node = static_cast<const _Node&>(__n);
+ if constexpr (__hash_cached::value)
+ if (__node._M_hash_code != __c)
+ return false;
+
+ return __hashtable_base::_M_key_equals
+ (__k, _ExtractKey{}(__node._M_v()));
+ }
+
+ template<typename _Kt>
+ bool
+ _M_equals_tr(const _Kt& __k, __hash_code __c,
+ const _Node_base& __n) const
+ {
+ const _Node& __node = static_cast<const _Node&>(__n);
+ if constexpr (__hash_cached::value)
+ if (__node._M_hash_code != __c)
+ return false;
+
+ return __hashtable_base::_M_key_equals_tr
+ (__k, _ExtractKey{}(__node._M_v()));
+ }
+
+ bool
+ _M_node_equals(const _Node_base& __lhn, const _Node_base& __rhn) const
+ {
+ const _Node& __lhnode = static_cast<const _Node&>(__lhn);
+ const _Node& __rhnode = static_cast<const _Node&>(__rhn);
+ if constexpr (__hash_cached::value)
+ if (__lhnode._M_hash_code != __rhnode._M_hash_code)
+ return false;
+
+ return __hashtable_base::_M_key_equals(_ExtractKey{}(__lhnode._M_v()),
+ _ExtractKey{}(__rhnode._M_v()));
+ }
#pragma GCC diagnostic pop
// Find and insert helper functions and types
// Find the node before the one matching the criteria.
- __node_base_ptr
+ _Base_ptr
_M_find_before_node(size_type, const key_type&, __hash_code) const;
template<typename _Kt>
- __node_base_ptr
+ _Base_ptr
_M_find_before_node_tr(size_type, const _Kt&, __hash_code) const;
// A pointer to a particular node and/or a hash code and bucket index
@@ -866,21 +1480,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// An iterator that refers to the node, or end().
explicit operator iterator() const noexcept
- { return iterator(_M_node()); }
+ { return _Iterator_traits::_S_iterator(_M_base()); }
// A const_iterator that refers to the node, or cend().
explicit operator const_iterator() const noexcept
- { return const_iterator(_M_node()); }
+ { return _Iterator_traits::_S_const_iterator(_M_base()); }
// A pointer to the node, or null.
- __node_ptr _M_node() const
+ _Node_ptr _M_node() const
{
- if (_M_before)
- return static_cast<__node_ptr>(_M_before->_M_nxt);
- return __node_ptr();
+ if (_M_before && _M_before->_M_nxt)
+ return static_cast<_Node&>(*_M_before->_M_nxt)._M_node_ptr();
+ return nullptr;
}
- __node_base_ptr _M_before{}; // Must only be used to get _M_nxt
+ _Base_ptr _M_base() const noexcept
+ { return _M_before ? _M_before->_M_nxt : nullptr;}
+
+ _Base_ptr _M_before{}; // Must only be used to get _M_nxt
__hash_code _M_hash_code{}; // Only valid if _M_bucket_index != -1
size_type _M_bucket_index = size_type(-1);
};
@@ -897,33 +1514,33 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// key will be set, allowing a new node to be inserted at that location.
// (The hash code and bucket might also be set when a node is found.)
// The _M_before pointer might point to _M_before_begin, so must not be
- // cast to __node_ptr, and it must not be used to modify *_M_before
+ // cast to _Node_ptr, and it must not be used to modify *_M_before
// except in non-const member functions, such as erase.
__location_type
_M_locate(const key_type& __k) const;
- __node_ptr
+ _Base_ptr
_M_find_node(size_type __bkt, const key_type& __key,
__hash_code __c) const
{
- if (__node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c))
- return static_cast<__node_ptr>(__before_n->_M_nxt);
+ if (_Base_ptr __before_n = _M_find_before_node(__bkt, __key, __c))
+ return __before_n->_M_nxt;
return nullptr;
}
template<typename _Kt>
- __node_ptr
+ _Base_ptr
_M_find_node_tr(size_type __bkt, const _Kt& __key,
__hash_code __c) const
{
if (auto __before_n = _M_find_before_node_tr(__bkt, __key, __c))
- return static_cast<__node_ptr>(__before_n->_M_nxt);
+ return __before_n->_M_nxt;
return nullptr;
}
// Insert a node at the beginning of a bucket.
void
- _M_insert_bucket_begin(size_type __bkt, __node_ptr __node)
+ _M_insert_bucket_begin(size_type __bkt, _Base_ptr __node)
{
if (_M_buckets[__bkt])
{
@@ -943,15 +1560,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__node->_M_nxt)
// We must update former begin bucket that is pointing to
// _M_before_begin.
- _M_buckets[_M_bucket_index(*__node->_M_next())] = __node;
+ _M_buckets[_M_bucket_index(*__node->_M_nxt)] = __node;
- _M_buckets[__bkt] = &_M_before_begin;
+ _M_buckets[__bkt] = _M_before_begin._M_base_ptr();
}
}
// Remove the bucket first node
void
- _M_remove_bucket_begin(size_type __bkt, __node_ptr __next_n,
+ _M_remove_bucket_begin(size_type __bkt, _Base_ptr __next_n,
size_type __next_bkt)
{
if (!__next_n)
@@ -964,11 +1581,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
// Get the node before __n in the bucket __bkt
- __node_base_ptr
- _M_get_previous_node(size_type __bkt, __node_ptr __n);
+ _Base_ptr
+ _M_get_previous_node(size_type __bkt, _Base_ptr __n);
- pair<__node_ptr, __hash_code>
- _M_compute_hash_code(__node_ptr __hint, const key_type& __k) const;
+ pair<_Base_ptr, __hash_code>
+ _M_compute_hash_code(_Base_ptr __hint, const key_type& __k) const;
// Insert node __n with hash code __code, in bucket __bkt (or another
// bucket if rehashing is needed).
@@ -978,13 +1595,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// used as a hint for rehashing when inserting a range.
iterator
_M_insert_unique_node(size_type __bkt, __hash_code,
- __node_ptr __n, size_type __n_elt = 1);
+ _Node_ptr __n, size_type __n_elt = 1);
// Insert node __n with key __k and hash code __code.
// Takes ownership of __n if insertion succeeds, throws otherwise.
iterator
- _M_insert_multi_node(__node_ptr __hint,
- __hash_code __code, __node_ptr __n);
+ _M_insert_multi_node(_Base_ptr __hint,
+ __hash_code __code, _Node_ptr __n);
template<typename... _Args>
std::pair<iterator, bool>
@@ -1011,7 +1628,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_emplace_multi(const_iterator, _Args&&... __args);
iterator
- _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n);
+ _M_erase(size_type __bkt, _Base_ptr __prev_n, _Node_ptr __n);
template<typename _InputIterator>
void
@@ -1174,6 +1791,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// reserve, if present, comes from _Rehash_base.
#if __glibcxx_node_extract // >= C++17 && HOSTED
+ static _Node_ptr
+ _S_adapt(typename _Node_alloc_traits::pointer __ptr)
+ {
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE
+ return __ptr;
+#else
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
+ using __alloc_ptr = typename _Node_alloc_traits::pointer;
+ if constexpr (is_same<_Node_ptr, __alloc_ptr>::value)
+ return __ptr;
+ else
+ return std::__to_address(__ptr);
+#pragma GCC diagnostic pop
+#endif
+ }
+
/// Re-insert an extracted node into a container with unique keys.
insert_return_type
_M_reinsert_node(node_type&& __nh)
@@ -1196,7 +1830,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto __code = __loc._M_hash_code;
auto __bkt = __loc._M_bucket_index;
__ret.position
- = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
+ = _M_insert_unique_node(__bkt, __code, _S_adapt(__nh._M_ptr));
__ret.inserted = true;
__nh.release();
}
@@ -1214,24 +1848,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_assert(get_allocator() == __nh.get_allocator());
const key_type& __k = __nh._M_key();
- auto __code = this->_M_hash_code(__k);
+ auto __code = _M_hash_code(__k);
auto __ret
- = _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr);
+ = _M_insert_multi_node(__hint._M_cur, __code, _S_adapt(__nh._M_ptr));
__nh.release();
return __ret;
}
private:
node_type
- _M_extract_node(size_t __bkt, __node_base_ptr __prev_n)
+ _M_extract_node(size_t __bkt, _Base_ptr __prev_n)
{
- __node_ptr __n = static_cast<__node_ptr>(__prev_n->_M_nxt);
+ auto __n = __prev_n->_M_nxt;
if (__prev_n == _M_buckets[__bkt])
- _M_remove_bucket_begin(__bkt, __n->_M_next(),
- __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0);
+ _M_remove_bucket_begin(__bkt, __n->_M_nxt,
+ __n->_M_nxt ? _M_bucket_index(*__n->_M_nxt) : 0);
else if (__n->_M_nxt)
{
- size_type __next_bkt = _M_bucket_index(*__n->_M_next());
+ size_type __next_bkt = _M_bucket_index(*__n->_M_nxt);
if (__next_bkt != __bkt)
_M_buckets[__next_bkt] = __prev_n;
}
@@ -1239,7 +1873,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__prev_n->_M_nxt = __n->_M_nxt;
__n->_M_nxt = nullptr;
--_M_element_count;
- return { __n, this->_M_node_allocator() };
+ auto __node_ptr = static_cast<_Node&>(*__n)._M_node_ptr();
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE
+ return { __node_ptr, this->_M_node_allocator() };
+#else
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
+ using __alloc_ptr = typename _Node_alloc_traits::pointer;
+ if constexpr (is_same<_Node_ptr, __alloc_ptr>::value)
+ return { __node_ptr, this->_M_node_allocator() };
+ else
+ {
+ auto __ap = pointer_traits<__alloc_ptr>::pointer_to(*__node_ptr);
+ return { __ap, this->_M_node_allocator() };
+ }
+#pragma GCC diagnostic pop
+#endif
}
// Hash code for node __src_n with key __k, using this->hash_function().
@@ -1248,14 +1897,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// with a hash function that might not match this->hash_function().
template<typename _H2>
__hash_code
- _M_src_hash_code(const _H2&, const __node_value_type& __src_n) const
+ _M_src_hash_code(const _H2&, const _Node& __src_n) const
{
if constexpr (__and_<__hash_cached,
is_same<_H2, _Hash>, is_empty<_Hash>>::value)
// If the node has a cached hash code, it's OK to use it.
return __src_n._M_hash_code;
else
- return this->_M_hash_code(_ExtractKey{}(__src_n._M_v()));
+ return _M_hash_code(_ExtractKey{}(__src_n._M_v()));
}
public:
@@ -1273,9 +1922,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
extract(const _Key& __k)
{
node_type __nh;
- __hash_code __code = this->_M_hash_code(__k);
+ __hash_code __code = _M_hash_code(__k);
std::size_t __bkt = _M_bucket_index(__code);
- if (__node_base_ptr __prev_node = _M_find_before_node(__bkt, __k, __code))
+ if (_Base_ptr __prev_node = _M_find_before_node(__bkt, __k, __code))
__nh = _M_extract_node(__bkt, __prev_node);
return __nh;
}
@@ -1286,17 +1935,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
__glibcxx_assert(get_allocator() == __src.get_allocator());
- using _PTr = pointer_traits<__node_base_ptr>;
-
auto __n_elt = __src.size();
size_type __first = 1;
// For a container of identical type we can use its private members,
// __src._M_before_begin, __src._M_bucket_index etc.
- auto __prev = _PTr::pointer_to(__src._M_before_begin);
+ auto __prev = __src._M_before_begin._M_base_ptr();
while (__n_elt--)
{
const auto __next = __prev->_M_nxt;
- const auto& __node = static_cast<__node_type&>(*__next);
+ const auto& __node = static_cast<_Node&>(*__next);
const key_type& __k = _ExtractKey{}(__node._M_v());
const auto __loc = _M_locate(__k);
if (__loc)
@@ -1308,7 +1955,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto __src_bkt = __src._M_bucket_index(__node);
auto __nh = __src._M_extract_node(__src_bkt, __prev);
_M_insert_unique_node(__loc._M_bucket_index, __loc._M_hash_code,
- __nh._M_ptr, __first * __n_elt + 1);
+ _S_adapt(__nh._M_ptr), __first * __n_elt + 1);
__nh.release();
__first = 0;
}
@@ -1338,7 +1985,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto __nh = __src.extract(__pos);
_M_insert_unique_node(__loc._M_bucket_index,
- __loc._M_hash_code, __nh._M_ptr,
+ __loc._M_hash_code, _S_adapt(__nh._M_ptr),
__first * __n_elt + 1);
__nh.release();
__first = 0;
@@ -1354,22 +2001,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__src.size() == 0) [[__unlikely__]]
return;
- using _PTr = pointer_traits<__node_base_ptr>;
-
- __node_ptr __hint = nullptr;
+ _Base_ptr __hint = nullptr;
this->reserve(size() + __src.size());
// For a container of identical type we can use its private members,
// __src._M_before_begin, __src._M_bucket_index etc.
- auto __prev = _PTr::pointer_to(__src._M_before_begin);
+ auto __prev = __src._M_before_begin._M_base_ptr();
do
{
- const auto& __node = static_cast<__node_type&>(*__prev->_M_nxt);
+ const auto& __node = static_cast<_Node&>(*__prev->_M_nxt);
// Hash code from this:
- auto __code = _M_hash_code_ext(__node);
+ auto __code = _M_node_hash_code_ext(__node);
// Bucket index in __src, using code from __src.hash_function():
size_type __src_bkt = __src._M_bucket_index(__node);
auto __nh = __src._M_extract_node(__src_bkt, __prev);
- __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur;
+ __hint = _M_insert_multi_node(__hint, __code,
+ _S_adapt(__nh._M_ptr))._M_cur;
__nh.release();
}
while (__prev->_M_nxt != nullptr);
@@ -1384,17 +2030,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
node_type>, "Node types are compatible");
__glibcxx_assert(get_allocator() == __src.get_allocator());
- __node_ptr __hint = nullptr;
+ _Base_ptr __hint = nullptr;
this->reserve(size() + __src.size());
// For a compatible container we can only use the public API,
// so cbegin(), cend(), hash_function(), and extract(iterator).
for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
{
auto __pos = __i++;
- __hash_code __code
- = _M_src_hash_code(__src.hash_function(), *__pos._M_cur);
+ __hash_code __code = _M_src_hash_code
+ (__src.hash_function(), static_cast<_Node&>(*__pos._M_cur));
auto __nh = __src.extract(__pos);
- __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur;
+ __hint = _M_insert_multi_node
+ (__hint, __code, _S_adapt(__nh._M_ptr))._M_cur;
__nh.release();
}
}
@@ -1487,11 +2134,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (&__ht == this)
return *this;
- if (__node_alloc_traits::_S_propagate_on_copy_assign())
+ if (_Node_alloc_traits::_S_propagate_on_copy_assign())
{
auto& __this_alloc = this->_M_node_allocator();
auto& __that_alloc = __ht._M_node_allocator();
- if (!__node_alloc_traits::_S_always_equal()
+ if (!_Node_alloc_traits::_S_always_equal()
&& __this_alloc != __that_alloc)
{
// Replacement allocator cannot free existing storage.
@@ -1536,9 +2183,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_assign_elements(_Ht&& __ht)
{
using __reuse_or_alloc_node_gen_t =
- __detail::_ReuseOrAllocNode<__node_alloc_type>;
+ __detail::_ReuseOrAllocNode<_Node_traits, _Alloc>;
- __buckets_ptr __former_buckets = nullptr;
+ _Buckets_ptr __former_buckets = nullptr;
std::size_t __former_bucket_count = _M_bucket_count;
__rehash_guard_t __rehash_guard(_M_rehash_policy);
@@ -1619,23 +2266,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// First deal with the special first node pointed to by
// _M_before_begin.
- __node_ptr __ht_n = __ht._M_begin();
- __node_ptr __this_n
- = __node_gen(static_cast<_FromVal>(__ht_n->_M_v()));
- _M_copy_code(*__this_n, *__ht_n);
- _M_update_bbegin(__this_n);
+ _Base_ptr __ht_n = __ht._M_before_begin._M_nxt;
+ _Node_ptr __this_n
+ = __node_gen(static_cast<_FromVal>(_S_v(*__ht_n)));
+ _M_copy_code(*__this_n, static_cast<_Node&>(*__ht_n));
+ _Base_ptr __base_n = __this_n->_M_base_ptr();
+ _M_update_bbegin(__base_n);
// Then deal with other nodes.
- __node_ptr __prev_n = __this_n;
- for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
+ _Base_ptr __prev_n = __base_n;
+ for (__ht_n = __ht_n->_M_nxt; __ht_n; __ht_n = __ht_n->_M_nxt)
{
- __this_n = __node_gen(static_cast<_FromVal>(__ht_n->_M_v()));
- __prev_n->_M_nxt = __this_n;
- _M_copy_code(*__this_n, *__ht_n);
+ __this_n = __node_gen(static_cast<_FromVal>(_S_v(*__ht_n)));
+ __base_n = __this_n->_M_base_ptr();
+ __prev_n->_M_nxt = __base_n;
+ _M_copy_code(*__this_n, static_cast<_Node&>(*__ht_n));
size_type __bkt = _M_bucket_index(*__this_n);
if (!_M_buckets[__bkt])
_M_buckets[__bkt] = __prev_n;
- __prev_n = __this_n;
+ __prev_n = __base_n;
}
__guard._M_ht = nullptr;
}
@@ -1652,7 +2301,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_rehash_policy._M_reset();
_M_bucket_count = 1;
_M_single_bucket = nullptr;
- _M_buckets = &_M_single_bucket;
+ _M_buckets = _M_single_bucket_ptr();
_M_before_begin._M_nxt = nullptr;
_M_element_count = 0;
}
@@ -1677,7 +2326,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_buckets = __ht._M_buckets;
else
{
- _M_buckets = &_M_single_bucket;
+ _M_buckets = _M_single_bucket_ptr();
_M_single_bucket = __ht._M_single_bucket;
}
@@ -1722,7 +2371,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__map_base(__ht),
__rehash_base(__ht),
__hashtable_alloc(
- __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
+ _Node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
__enable_default_ctor(__ht),
_M_buckets(nullptr),
_M_bucket_count(__ht._M_bucket_count),
@@ -1738,7 +2387,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typename _RehashPolicy, typename _Traits>
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
+ _Hashtable(_Hashtable&& __ht, _Node_alloc&& __a,
true_type /* alloc always equal */)
noexcept(_S_nothrow_move())
: __hashtable_base(__ht),
@@ -1755,7 +2404,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// Update buckets if __ht is using its single bucket.
if (__ht._M_uses_single_bucket())
{
- _M_buckets = &_M_single_bucket;
+ _M_buckets = _M_single_bucket_ptr();
_M_single_bucket = __ht._M_single_bucket;
}
@@ -1776,7 +2425,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
: __hashtable_base(__ht),
__map_base(__ht),
__rehash_base(__ht),
- __hashtable_alloc(__node_alloc_type(__a)),
+ __hashtable_alloc(_Node_alloc(__a)),
__enable_default_ctor(__ht),
_M_buckets(),
_M_bucket_count(__ht._M_bucket_count),
@@ -1792,7 +2441,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typename _RehashPolicy, typename _Traits>
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
+ _Hashtable(_Hashtable&& __ht, _Node_alloc&& __a,
false_type /* alloc always equal */)
: __hashtable_base(__ht),
__map_base(__ht),
@@ -1808,7 +2457,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
if (__ht._M_uses_single_bucket())
{
- _M_buckets = &_M_single_bucket;
+ _M_buckets = _M_single_bucket_ptr();
_M_single_bucket = __ht._M_single_bucket;
}
else
@@ -1816,7 +2465,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// Fix bucket containing the _M_before_begin pointer that can't be
// moved.
- _M_update_bbegin(__ht._M_begin());
+ _M_update_bbegin(__ht._M_before_begin._M_nxt);
__ht._M_reset();
}
@@ -1843,11 +2492,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// 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)),
+ static_assert(__or_<__hash_cached,
+ __is_nothrow_invocable<const _Hash&, const _Key&>>::value,
"Cache the hash code or qualify your functors involved"
- " in hash code and bucket index computation with noexcept");
+ " in hash code computation with noexcept");
this->_M_deallocate_nodes(_M_begin());
_M_deallocate_buckets();
@@ -1872,7 +2520,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
- if constexpr (__node_alloc_traits::propagate_on_container_swap::value)
+ if constexpr (_Node_alloc_traits::propagate_on_container_swap::value)
swap(this->_M_node_allocator(), __x._M_node_allocator());
#pragma GCC diagnostic pop
@@ -1884,13 +2532,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (!__x._M_uses_single_bucket())
{
_M_buckets = __x._M_buckets;
- __x._M_buckets = &__x._M_single_bucket;
+ __x._M_buckets = __x._M_single_bucket_ptr();
}
}
else if (__x._M_uses_single_bucket())
{
__x._M_buckets = _M_buckets;
- _M_buckets = &_M_single_bucket;
+ _M_buckets = _M_single_bucket_ptr();
}
else
std::swap(_M_buckets, __x._M_buckets);
@@ -1942,15 +2590,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
if (size() <= __small_size_threshold())
{
- for (auto __n = _M_begin(); __n; __n = __n->_M_next())
- if (this->_M_key_equals_tr(__k, *__n))
- return iterator(__n);
+ for (auto __n = _M_before_begin._M_nxt; __n; __n = __n->_M_nxt)
+ if (_M_key_equals_tr(__k, *__n))
+ return _Iterator_traits::_S_iterator(__n);
return end();
}
__hash_code __code = this->_M_hash_code_tr(__k);
std::size_t __bkt = _M_bucket_index(__code);
- return iterator(_M_find_node_tr(__bkt, __k, __code));
+ return _Iterator_traits::_S_iterator
+ (_M_find_node_tr(__bkt, __k, __code));
}
template<typename _Key, typename _Value, typename _Alloc,
@@ -1966,15 +2615,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
if (size() <= __small_size_threshold())
{
- for (auto __n = _M_begin(); __n; __n = __n->_M_next())
- if (this->_M_key_equals_tr(__k, *__n))
- return const_iterator(__n);
+ for (auto __n = _M_before_begin._M_nxt; __n; __n = __n->_M_nxt)
+ if (_M_key_equals_tr(__k, *__n))
+ return _Iterator_traits::_S_const_iterator(__n);
return end();
}
__hash_code __code = this->_M_hash_code_tr(__k);
std::size_t __bkt = _M_bucket_index(__code);
- return const_iterator(_M_find_node_tr(__bkt, __k, __code));
+ return _Iterator_traits::_S_const_iterator
+ (_M_find_node_tr(__bkt, __k, __code));
}
#endif
@@ -1997,7 +2647,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
size_type __result = 1;
for (auto __ref = __it++;
- __it._M_cur && this->_M_node_equals(*__ref._M_cur, *__it._M_cur);
+ __it._M_cur && _M_node_equals(*__ref._M_cur, *__it._M_cur);
++__it)
++__result;
@@ -2019,9 +2669,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (size() <= __small_size_threshold())
{
size_type __result = 0;
- for (auto __n = _M_begin(); __n; __n = __n->_M_next())
+ for (auto __n = _M_before_begin._M_nxt; __n; __n = __n->_M_nxt)
{
- if (this->_M_key_equals_tr(__k, *__n))
+ if (_M_key_equals_tr(__k, *__n))
{
++__result;
continue;
@@ -2040,11 +2690,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (!__n)
return 0;
- iterator __it(__n);
size_type __result = 1;
- for (++__it;
- __it._M_cur && this->_M_equals_tr(__k, __code, *__it._M_cur);
- ++__it)
+ for (__n = __n->_M_nxt; __n && _M_equals_tr(__k, __code, *__n);
+ __n = __n->_M_nxt)
++__result;
return __result;
@@ -2069,7 +2717,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__unique_keys::value)
return { __beg, __ite };
- while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur))
+ while (__ite._M_cur && _M_node_equals(*__beg._M_cur, *__ite._M_cur))
++__ite;
return { __beg, __ite };
@@ -2093,7 +2741,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__unique_keys::value)
return { __beg, __ite };
- while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur))
+ while (__ite._M_cur && _M_node_equals(*__beg._M_cur, *__ite._M_cur))
++__ite;
return { __beg, __ite };
@@ -2113,10 +2761,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
if (size() <= __small_size_threshold())
{
- __node_ptr __n, __beg = nullptr;
- for (__n = _M_begin(); __n; __n = __n->_M_next())
+ _Base_ptr __n, __beg = nullptr;
+ for (__n = _M_before_begin._M_nxt; __n; __n = __n->_M_nxt)
{
- if (this->_M_key_equals_tr(__k, *__n))
+ if (_M_key_equals_tr(__k, *__n))
{
if (!__beg)
__beg = __n;
@@ -2127,18 +2775,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
break;
}
- return { iterator(__beg), iterator(__n) };
+ return { _Iterator_traits::_S_iterator(__beg),
+ _Iterator_traits::_S_iterator(__n) };
}
__hash_code __code = this->_M_hash_code_tr(__k);
std::size_t __bkt = _M_bucket_index(__code);
auto __n = _M_find_node_tr(__bkt, __k, __code);
- iterator __ite(__n);
+ iterator __ite = _Iterator_traits::_S_iterator(__n);
if (!__n)
return { __ite, __ite };
auto __beg = __ite++;
- while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
+ while (__ite._M_cur && _M_equals_tr(__k, __code, *__ite._M_cur))
++__ite;
return { __beg, __ite };
@@ -2157,10 +2806,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
if (size() <= __small_size_threshold())
{
- __node_ptr __n, __beg = nullptr;
- for (__n = _M_begin(); __n; __n = __n->_M_next())
+ _Base_ptr __n, __beg = nullptr;
+ for (__n = _M_before_begin._M_nxt; __n; __n = __n->_M_nxt)
{
- if (this->_M_key_equals_tr(__k, *__n))
+ if (_M_key_equals_tr(__k, *__n))
{
if (!__beg)
__beg = __n;
@@ -2171,18 +2820,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
break;
}
- return { const_iterator(__beg), const_iterator(__n) };
+ return { _Iterator_traits::_S_const_iterator(__beg),
+ _Iterator_traits::_S_const_iterator(__n) };
}
__hash_code __code = this->_M_hash_code_tr(__k);
std::size_t __bkt = _M_bucket_index(__code);
auto __n = _M_find_node_tr(__bkt, __k, __code);
- const_iterator __ite(__n);
+ const_iterator __ite = _Iterator_traits::_S_const_iterator(__n);
if (!__n)
return { __ite, __ite };
auto __beg = __ite++;
- while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
+ while (__ite._M_cur && _M_equals_tr(__k, __code, *__ite._M_cur))
++__ite;
return { __beg, __ite };
@@ -2200,19 +2850,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_find_before_node(size_type __bkt, const key_type& __k,
__hash_code __code) const
- -> __node_base_ptr
+ -> _Base_ptr
{
- __node_base_ptr __prev_p = _M_buckets[__bkt];
+ _Base_ptr __prev_p = _M_buckets[__bkt];
if (!__prev_p)
return nullptr;
- for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);;
- __p = __p->_M_next())
+ for (auto __p = __prev_p->_M_nxt;; __p = __p->_M_nxt)
{
- if (this->_M_equals(__k, __code, *__p))
+ if (_M_equals(__k, __code, *__p))
return __prev_p;
- if (__builtin_expect (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt, 0))
+ if (__builtin_expect(!__p->_M_nxt
+ || _M_bucket_index(*__p->_M_nxt) != __bkt, 0))
break;
__prev_p = __p;
}
@@ -2230,19 +2880,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_find_before_node_tr(size_type __bkt, const _Kt& __k,
__hash_code __code) const
- -> __node_base_ptr
+ -> _Base_ptr
{
- __node_base_ptr __prev_p = _M_buckets[__bkt];
+ _Base_ptr __prev_p = _M_buckets[__bkt];
if (!__prev_p)
return nullptr;
- for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);;
- __p = __p->_M_next())
+ for (auto __p = __prev_p->_M_nxt;; __p = __p->_M_nxt)
{
- if (this->_M_equals_tr(__k, __code, *__p))
+ if (_M_equals_tr(__k, __code, *__p))
return __prev_p;
- if (__builtin_expect (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt, 0))
+ if (__builtin_expect (!__p->_M_nxt
+ || _M_bucket_index(*__p->_M_nxt) != __bkt, 0))
break;
__prev_p = __p;
}
@@ -2265,18 +2915,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__size <= __small_size_threshold())
{
- __loc._M_before = pointer_traits<__node_base_ptr>::
- pointer_to(const_cast<__node_base&>(_M_before_begin));
+ __loc._M_before = _M_before_begin._M_base_ptr();
while (__loc._M_before->_M_nxt)
{
- if (this->_M_key_equals(__k, *__loc._M_node()))
+ if (_M_key_equals(__k, *__loc._M_before->_M_nxt))
return __loc;
__loc._M_before = __loc._M_before->_M_nxt;
}
__loc._M_before = nullptr; // Didn't find it.
}
- __loc._M_hash_code = this->_M_hash_code(__k);
+ __loc._M_hash_code = _M_hash_code(__k);
__loc._M_bucket_index = _M_bucket_index(__loc._M_hash_code);
if (__size > __small_size_threshold())
@@ -2293,10 +2942,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_get_previous_node(size_type __bkt, __node_ptr __n)
- -> __node_base_ptr
+ _M_get_previous_node(size_type __bkt, _Base_ptr __n)
+ -> _Base_ptr
{
- __node_base_ptr __prev_n = _M_buckets[__bkt];
+ _Base_ptr __prev_n = _M_buckets[__bkt];
while (__prev_n->_M_nxt != __n)
__prev_n = __prev_n->_M_nxt;
return __prev_n;
@@ -2335,7 +2984,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
}
- _Scoped_node __node { __node_ptr(), this }; // Do not create node yet.
+ _Scoped_node __node { _Node_ptr(), this }; // Do not create node yet.
__hash_code __code = 0;
size_type __bkt = 0;
@@ -2343,7 +2992,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
// Didn't extract a key from the args, so build the node.
__node._M_node
- = this->_M_allocate_node(std::forward<_Args>(__args)...);
+ = this->_M_allocate_node(std::forward<_Args>(__args)...);
const key_type& __key = _ExtractKey{}(__node._M_node->_M_v());
__kp = std::__addressof(__key);
}
@@ -2383,7 +3032,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Scoped_node __node { this, std::forward<_Args>(__args)... };
const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
- auto __res = this->_M_compute_hash_code(__hint._M_cur, __k);
+ auto __res = _M_compute_hash_code(__hint._M_cur, __k);
auto __pos
= _M_insert_multi_node(__res.first, __res.second, __node._M_node);
__node._M_node = nullptr;
@@ -2436,26 +3085,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_compute_hash_code(__node_ptr __hint, const key_type& __k) const
- -> pair<__node_ptr, __hash_code>
+ _M_compute_hash_code(_Base_ptr __hint, const key_type& __k) const
+ -> pair<_Base_ptr, __hash_code>
{
if (size() <= __small_size_threshold())
{
if (__hint)
{
- for (auto __it = __hint; __it; __it = __it->_M_next())
- if (this->_M_key_equals(__k, *__it))
- return { __it, this->_M_hash_code(*__it) };
+ for (auto __it = __hint; __it; __it = __it->_M_nxt)
+ if (_M_key_equals(__k, *__it))
+ return { __it, _M_node_hash_code(*__it) };
}
- for (auto __it = _M_begin(); __it != __hint; __it = __it->_M_next())
- if (this->_M_key_equals(__k, *__it))
- return { __it, this->_M_hash_code(*__it) };
+ for (auto __it = _M_before_begin._M_nxt; __it != __hint;
+ __it = __it->_M_nxt)
+ if (_M_key_equals(__k, *__it))
+ return { __it, _M_node_hash_code(*__it) };
__hint = nullptr;
}
- return { __hint, this->_M_hash_code(__k) };
+ return { __hint, _M_hash_code(__k) };
}
template<typename _Key, typename _Value, typename _Alloc,
@@ -2466,7 +3116,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_insert_unique_node(size_type __bkt, __hash_code __code,
- __node_ptr __node, size_type __n_elt)
+ _Node_ptr __node, size_type __n_elt)
-> iterator
{
__rehash_guard_t __rehash_guard(_M_rehash_policy);
@@ -2484,9 +3134,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_store_code(*__node, __code);
// Always insert at the beginning of the bucket.
- _M_insert_bucket_begin(__bkt, __node);
+ _Base_ptr __base = __node->_M_base_ptr();
+ _M_insert_bucket_begin(__bkt, __base);
++_M_element_count;
- return iterator(__node);
+ return _Iterator_traits::_S_iterator(__base);
}
template<typename _Key, typename _Value, typename _Alloc,
@@ -2496,8 +3147,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_insert_multi_node(__node_ptr __hint,
- __hash_code __code, __node_ptr __node)
+ _M_insert_multi_node(_Base_ptr __hint,
+ __hash_code __code, _Node_ptr __node)
-> iterator
{
__rehash_guard_t __rehash_guard(_M_rehash_policy);
@@ -2514,35 +3165,35 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// Find the node before an equivalent one or use hint if it exists and
// if it is equivalent.
- __node_base_ptr __prev
- = __builtin_expect(__hint != nullptr, false)
- && this->_M_equals(__k, __code, *__hint)
+ _Base_ptr __prev
+ = __builtin_expect(__hint != nullptr, 0)
+ && _M_equals(__k, __code, *__hint)
? __hint
: _M_find_before_node(__bkt, __k, __code);
+ auto __base = __node->_M_base_ptr();
if (__prev)
{
// Insert after the node before the equivalent one.
- __node->_M_nxt = __prev->_M_nxt;
- __prev->_M_nxt = __node;
+ __base->_M_nxt = __prev->_M_nxt;
+ __prev->_M_nxt = __base;
if (__builtin_expect(__prev == __hint, false))
// hint might be the last bucket node, in this case we need to
// update next bucket.
- if (__node->_M_nxt
- && !this->_M_equals(__k, __code, *__node->_M_next()))
+ if (__base->_M_nxt && !_M_equals(__k, __code, *__base->_M_nxt))
{
- size_type __next_bkt = _M_bucket_index(*__node->_M_next());
+ size_type __next_bkt = _M_bucket_index(*__base->_M_nxt);
if (__next_bkt != __bkt)
- _M_buckets[__next_bkt] = __node;
+ _M_buckets[__next_bkt] = __base;
}
}
else
// The inserted node has no equivalent in the hashtable. We must
// insert the new node at the beginning of the bucket to preserve
// equivalent elements' relative positions.
- _M_insert_bucket_begin(__bkt, __node);
+ _M_insert_bucket_begin(__bkt, __base);
++_M_element_count;
- return iterator(__node);
+ return _Iterator_traits::_S_iterator(__base);
}
template<typename _Key, typename _Value, typename _Alloc,
@@ -2555,14 +3206,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
erase(const_iterator __it)
-> iterator
{
- __node_ptr __n = __it._M_cur;
+ auto __n = __it._M_cur;
std::size_t __bkt = _M_bucket_index(*__n);
// Look for previous node to unlink it from the erased one, this
// is why we need buckets to contain the before begin to make
// this search fast.
- __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
- return _M_erase(__bkt, __prev_n, __n);
+ _Base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
+ return _M_erase(__bkt, __prev_n, static_cast<_Node&>(*__n)._M_node_ptr());
}
template<typename _Key, typename _Value, typename _Alloc,
@@ -2572,21 +3223,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n)
+ _M_erase(size_type __bkt, _Base_ptr __prev_n, _Node_ptr __n)
-> iterator
{
if (__prev_n == _M_buckets[__bkt])
- _M_remove_bucket_begin(__bkt, __n->_M_next(),
- __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0);
+ _M_remove_bucket_begin(__bkt, __n->_M_nxt,
+ __n->_M_nxt ? _M_bucket_index(*__n->_M_nxt) : 0);
else if (__n->_M_nxt)
{
- size_type __next_bkt = _M_bucket_index(*__n->_M_next());
+ size_type __next_bkt = _M_bucket_index(*__n->_M_nxt);
if (__next_bkt != __bkt)
_M_buckets[__next_bkt] = __prev_n;
}
__prev_n->_M_nxt = __n->_M_nxt;
- iterator __result(__n->_M_next());
+ iterator __result = _Iterator_traits::_S_iterator(__n->_M_nxt);
this->_M_deallocate_node(__n);
--_M_element_count;
@@ -2609,8 +3260,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (!__loc)
return 0;
- __node_base_ptr __prev_n = __loc._M_before;
- __node_ptr __n = __loc._M_node();
+ _Base_ptr __prev_n = __loc._M_before;
+ _Node_ptr __n = __loc._M_node();
auto __bkt = __loc._M_bucket_index;
if (__bkt == size_type(-1))
__bkt = _M_bucket_index(*__n);
@@ -2628,23 +3279,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// We use one loop to find all matching nodes and another to
// deallocate them so that the key stays valid during the first loop.
// It might be invalidated indirectly when destroying nodes.
- __node_ptr __n_last = __n->_M_next();
- while (__n_last && this->_M_node_equals(*__n, *__n_last))
- __n_last = __n_last->_M_next();
+ _Base_ptr __n_last = __n->_M_nxt;
+ while (__n_last && _M_node_equals(*__n, *__n_last))
+ __n_last = __n_last->_M_nxt;
std::size_t __n_last_bkt
= __n_last ? _M_bucket_index(*__n_last) : __bkt;
// Deallocate nodes.
+ _Node_ptr __node_last = __n_last
+ ? static_cast<_Node&>(*__n_last)._M_node_ptr()
+ : nullptr;
size_type __result = 0;
do
{
- __node_ptr __p = __n->_M_next();
+ _Node_ptr __p = __n->_M_next();
this->_M_deallocate_node(__n);
__n = __p;
++__result;
}
- while (__n != __n_last);
+ while (__n != __node_last);
_M_element_count -= __result;
if (__prev_n == _M_buckets[__bkt])
@@ -2667,23 +3321,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
erase(const_iterator __first, const_iterator __last)
-> iterator
{
- __node_ptr __n = __first._M_cur;
- __node_ptr __last_n = __last._M_cur;
+ _Base_ptr __n = __first._M_cur;
+ _Base_ptr __last_n = __last._M_cur;
if (__n == __last_n)
- return iterator(__n);
+ return _Iterator_traits::_S_iterator(__n);
std::size_t __bkt = _M_bucket_index(*__n);
- __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
- bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
+ _Base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
+ bool __is_bucket_begin = __prev_n == _M_buckets[__bkt];
std::size_t __n_bkt = __bkt;
for (;;)
{
do
{
- __node_ptr __tmp = __n;
- __n = __n->_M_next();
- this->_M_deallocate_node(__tmp);
+ _Base_ptr __tmp = __n;
+ __n = __n->_M_nxt;
+ this->_M_deallocate_node
+ (static_cast<_Node&>(*__tmp)._M_node_ptr());
--_M_element_count;
if (!__n)
break;
@@ -2700,8 +3355,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__n && (__n_bkt != __bkt || __is_bucket_begin))
_M_buckets[__n_bkt] = __prev_n;
+
__prev_n->_M_nxt = __n;
- return iterator(__n);
+ return _Iterator_traits::_S_iterator(__n);
}
template<typename _Key, typename _Value, typename _Alloc,
@@ -2751,20 +3407,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_rehash(size_type __bkt_count, true_type /* __uks */)
{
- __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
- __node_ptr __p = _M_begin();
+ _Buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
+ auto __p = _M_before_begin._M_nxt;
_M_before_begin._M_nxt = nullptr;
std::size_t __bbegin_bkt = 0;
while (__p)
{
- __node_ptr __next = __p->_M_next();
- std::size_t __bkt
- = __hash_code_base::_M_bucket_index(*__p, __bkt_count);
+ auto __next = __p->_M_nxt;
+ std::size_t __bkt = _M_bucket_index(*__p, __bkt_count);
if (!__new_buckets[__bkt])
{
__p->_M_nxt = _M_before_begin._M_nxt;
_M_before_begin._M_nxt = __p;
- __new_buckets[__bkt] = &_M_before_begin;
+ __new_buckets[__bkt] = _M_before_begin._M_base_ptr();
if (__p->_M_nxt)
__new_buckets[__bbegin_bkt] = __p;
__bbegin_bkt = __bkt;
@@ -2794,19 +3449,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_rehash(size_type __bkt_count, false_type /* __uks */)
{
- __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
- __node_ptr __p = _M_begin();
+ _Buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
+ _Base_ptr __p = _M_before_begin._M_nxt;
_M_before_begin._M_nxt = nullptr;
std::size_t __bbegin_bkt = 0;
std::size_t __prev_bkt = 0;
- __node_ptr __prev_p = nullptr;
+ _Base_ptr __prev_p = nullptr;
bool __check_bucket = false;
while (__p)
{
- __node_ptr __next = __p->_M_next();
- std::size_t __bkt
- = __hash_code_base::_M_bucket_index(*__p, __bkt_count);
+ _Base_ptr __next = __p->_M_nxt;
+ std::size_t __bkt = _M_bucket_index(*__p, __bkt_count);
if (__prev_p && __prev_bkt == __bkt)
{
@@ -2832,8 +3486,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__prev_p->_M_nxt)
{
std::size_t __next_bkt
- = __hash_code_base::_M_bucket_index(
- *__prev_p->_M_next(), __bkt_count);
+ = _M_bucket_index(*__prev_p->_M_nxt, __bkt_count);
if (__next_bkt != __prev_bkt)
__new_buckets[__next_bkt] = __prev_p;
}
@@ -2844,7 +3497,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
__p->_M_nxt = _M_before_begin._M_nxt;
_M_before_begin._M_nxt = __p;
- __new_buckets[__bkt] = &_M_before_begin;
+ __new_buckets[__bkt] = _M_before_begin._M_base_ptr();
if (__p->_M_nxt)
__new_buckets[__bbegin_bkt] = __p;
__bbegin_bkt = __bkt;
@@ -2863,8 +3516,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__check_bucket && __prev_p->_M_nxt)
{
std::size_t __next_bkt
- = __hash_code_base::_M_bucket_index(*__prev_p->_M_next(),
- __bkt_count);
+ = _M_bucket_index(*__prev_p->_M_nxt, __bkt_count);
if (__next_bkt != __prev_bkt)
__new_buckets[__next_bkt] = __prev_p;
}
@@ -2893,33 +3545,32 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return false;
if constexpr (__unique_keys::value)
- for (auto __x_n = _M_begin(); __x_n; __x_n = __x_n->_M_next())
+ for (auto __x_n = _M_before_begin._M_nxt; __x_n; __x_n = __x_n->_M_nxt)
{
std::size_t __ybkt = __other._M_bucket_index_ext(*__x_n);
auto __prev_n = __other._M_buckets[__ybkt];
if (!__prev_n)
return false;
- for (__node_ptr __n = static_cast<__node_ptr>(__prev_n->_M_nxt);;
- __n = __n->_M_next())
+ for (_Base_ptr __n = __prev_n->_M_nxt;; __n = __n->_M_nxt)
{
- if (__n->_M_v() == __x_n->_M_v())
+ if (_S_v(*__n) == _S_v(*__x_n))
break;
if (!__n->_M_nxt
- || __other._M_bucket_index(*__n->_M_next()) != __ybkt)
+ || __other._M_bucket_index(*__n->_M_nxt) != __ybkt)
return false;
}
}
else // non-unique keys
- for (auto __x_n = _M_begin(); __x_n;)
+ for (auto __x_n = _M_before_begin._M_nxt; __x_n;)
{
std::size_t __x_count = 1;
- auto __x_n_end = __x_n->_M_next();
+ auto __x_n_end = __x_n->_M_nxt;
for (; __x_n_end
- && key_eq()(_ExtractKey{}(__x_n->_M_v()),
- _ExtractKey{}(__x_n_end->_M_v()));
- __x_n_end = __x_n_end->_M_next())
+ && key_eq()(_ExtractKey{}(_S_v(*__x_n)),
+ _ExtractKey{}(_S_v(*__x_n_end)));
+ __x_n_end = __x_n_end->_M_nxt)
++__x_count;
std::size_t __ybkt = __other._M_bucket_index_ext(*__x_n);
@@ -2927,15 +3578,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (!__y_prev_n)
return false;
- __node_ptr __y_n = static_cast<__node_ptr>(__y_prev_n->_M_nxt);
+ auto __y_n = __y_prev_n->_M_nxt;
for (;;)
{
- if (key_eq()(_ExtractKey{}(__y_n->_M_v()),
- _ExtractKey{}(__x_n->_M_v())))
+ if (key_eq()(_ExtractKey{}(_S_v(*__y_n)),
+ _ExtractKey{}(_S_v(*__x_n))))
break;
auto __y_ref_n = __y_n;
- for (__y_n = __y_n->_M_next(); __y_n; __y_n = __y_n->_M_next())
+ for (__y_n = __y_n->_M_nxt; __y_n; __y_n = __y_n->_M_nxt)
if (!__other._M_node_equals(*__y_ref_n, *__y_n))
break;
@@ -2944,15 +3595,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
auto __y_n_end = __y_n;
- for (; __y_n_end; __y_n_end = __y_n_end->_M_next())
+ for (; __y_n_end; __y_n_end = __y_n_end->_M_nxt)
if (--__x_count == 0)
break;
if (__x_count != 0)
return false;
- const_iterator __itx(__x_n), __itx_end(__x_n_end);
- const_iterator __ity(__y_n);
+ const_iterator
+ __itx = _Iterator_traits::_S_const_iterator(__x_n),
+ __itx_end = _Iterator_traits::_S_const_iterator(__x_n_end),
+ __ity = _Iterator_traits::_S_const_iterator(__y_n);
if (!std::is_permutation(__itx, __itx_end, __ity))
return false;
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 048855d5405..db2e7475d86 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -33,12 +33,20 @@
#include <tuple> // for std::tuple, std::forward_as_tuple
#include <bits/functional_hash.h> // for __is_fast_hash
+#include <bits/ptr_traits.h> // for std::pointer_traits
#include <bits/stl_algobase.h> // for std::min
#include <bits/stl_pair.h> // for std::pair
-#include <ext/aligned_buffer.h> // for __gnu_cxx::__aligned_buffer
+#include <bits/stl_uninitialized.h> // for __uninitialized_default_n
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE <= 9000
+# include <ext/aligned_buffer.h> // for __gnu_cxx::__aligned_buffer
+#endif
#include <ext/alloc_traits.h> // for std::__alloc_rebind
#include <ext/numeric_traits.h> // for __gnu_cxx::__int_traits
+#ifndef _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE
+# define _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE 1
+#endif
+
namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
@@ -118,7 +126,7 @@ namespace __detail
template<typename _Kt, typename _Arg, typename _NodeGenerator>
static auto
_S_build(_Kt&& __k, _Arg&& __arg, _NodeGenerator& __node_gen)
- -> typename _NodeGenerator::__node_ptr
+ -> typename _NodeGenerator::_Node_ptr
{
return __node_gen(std::forward<_Kt>(__k),
std::forward<_Arg>(__arg).second);
@@ -131,7 +139,7 @@ namespace __detail
template<typename _Kt, typename _Arg, typename _NodeGenerator>
static auto
_S_build(_Kt&& __k, _Arg&&, _NodeGenerator& __node_gen)
- -> typename _NodeGenerator::__node_ptr
+ -> typename _NodeGenerator::_Node_ptr
{ return __node_gen(std::forward<_Kt>(__k)); }
};
@@ -148,24 +156,24 @@ namespace __detail
}
};
- template<typename _NodeAlloc>
+ template<typename _NodeTraits, typename _Alloc>
struct _Hashtable_alloc;
// Functor recycling a pool of nodes and using allocation once the pool is
// empty.
- template<typename _NodeAlloc>
+ template<typename _NodeTraits, typename _Alloc>
struct _ReuseOrAllocNode
{
private:
- using __node_alloc_type = _NodeAlloc;
- using __hashtable_alloc = _Hashtable_alloc<__node_alloc_type>;
- using __node_alloc_traits =
- typename __hashtable_alloc::__node_alloc_traits;
+ using __hashtable_alloc = _Hashtable_alloc<_NodeTraits, _Alloc>;
+ using _Node = typename _NodeTraits::_Node;
+ using _Node_alloc = __alloc_rebind<_Alloc, _Node>;
+ using _Node_alloc_traits = std::allocator_traits<_Node_alloc>;
public:
- using __node_ptr = typename __hashtable_alloc::__node_ptr;
+ using _Node_ptr = typename _NodeTraits::_Node_ptr;
- _ReuseOrAllocNode(__node_ptr __nodes, __hashtable_alloc& __h)
+ _ReuseOrAllocNode(_Node_ptr __nodes, __hashtable_alloc& __h)
: _M_nodes(__nodes), _M_h(__h) { }
_ReuseOrAllocNode(const _ReuseOrAllocNode&) = delete;
@@ -175,15 +183,15 @@ namespace __detail
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
template<typename _Arg>
- __node_ptr
+ _Node_ptr
operator()(_Arg&& __arg)
{
if (!_M_nodes)
return _M_h._M_allocate_node(std::forward<_Arg>(__arg));
- using value_type = typename _NodeAlloc::value_type::value_type;
+ using value_type = typename _NodeTraits::value_type;
- __node_ptr __node = _M_nodes;
+ _Node_ptr __node = _M_nodes;
if constexpr (is_assignable<value_type&, _Arg>::value)
{
__node->_M_v() = std::forward<_Arg>(__arg);
@@ -192,13 +200,13 @@ namespace __detail
}
else
{
- _M_nodes = _M_nodes->_M_next();
+ _M_nodes = __node->_M_next();
__node->_M_nxt = nullptr;
auto& __a = _M_h._M_node_allocator();
- __node_alloc_traits::destroy(__a, __node->_M_valptr());
- _NodePtrGuard<__hashtable_alloc, __node_ptr>
+ _Node_alloc_traits::destroy(__a, __node->_M_valptr());
+ _NodePtrGuard<__hashtable_alloc, _Node_ptr>
__guard{ _M_h, __node };
- __node_alloc_traits::construct(__a, __node->_M_valptr(),
+ _Node_alloc_traits::construct(__a, __node->_M_valptr(),
std::forward<_Arg>(__arg));
__guard._M_ptr = nullptr;
}
@@ -207,26 +215,26 @@ namespace __detail
#pragma GCC diagnostic pop
private:
- __node_ptr _M_nodes;
+ _Node_ptr _M_nodes;
__hashtable_alloc& _M_h;
};
// Functor similar to the previous one but without any pool of nodes to
// recycle.
- template<typename _NodeAlloc>
+ template<typename _NodeTraits, typename _Alloc>
struct _AllocNode
{
private:
- using __hashtable_alloc = _Hashtable_alloc<_NodeAlloc>;
+ using __hashtable_alloc = _Hashtable_alloc<_NodeTraits, _Alloc>;
public:
- using __node_ptr = typename __hashtable_alloc::__node_ptr;
+ using _Node_ptr = typename __hashtable_alloc::_Node_ptr;
_AllocNode(__hashtable_alloc& __h)
: _M_h(__h) { }
template<typename... _Args>
- __node_ptr
+ _Node_ptr
operator()(_Args&&... __args) const
{ return _M_h._M_allocate_node(std::forward<_Args>(__args)...); }
@@ -281,6 +289,7 @@ namespace __detail
{ return std::__is_fast_hash<_Hash>::value ? 0 : 20; }
};
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE <= 9000
/**
* struct _Hash_node_base
*
@@ -296,6 +305,13 @@ namespace __detail
_Hash_node_base() noexcept : _M_nxt() { }
_Hash_node_base(_Hash_node_base* __next) noexcept : _M_nxt(__next) { }
+
+ // This is not const-correct, but it's only used in a const access path
+ // by std::_Hashtable::_M_locate() where the pointer is only used as
+ // before-begin node to bootstrap a research.
+ _Hash_node_base*
+ _M_base_ptr() const noexcept
+ { return const_cast<_Hash_node_base*>(this); }
};
/**
@@ -361,6 +377,10 @@ namespace __detail
: _Hash_node_base
, _Hash_node_value<_Value, _Cache_hash_code>
{
+ _Hash_node*
+ _M_node_ptr() noexcept
+ { return this; }
+
_Hash_node*
_M_next() const noexcept
{ return static_cast<_Hash_node*>(this->_M_nxt); }
@@ -370,12 +390,12 @@ namespace __detail
template<typename _Value, bool _Cache_hash_code>
struct _Node_iterator_base
{
- using __node_type = _Hash_node<_Value, _Cache_hash_code>;
+ using _Node = _Hash_node<_Value, _Cache_hash_code>;
- __node_type* _M_cur;
+ _Node* _M_cur;
_Node_iterator_base() : _M_cur(nullptr) { }
- _Node_iterator_base(__node_type* __p) noexcept
+ _Node_iterator_base(_Node* __p) noexcept
: _M_cur(__p) { }
void
@@ -402,7 +422,7 @@ namespace __detail
{
private:
using __base_type = _Node_iterator_base<_Value, __cache>;
- using __node_type = typename __base_type::__node_type;
+ using _Node = typename __base_type::_Node;
public:
using value_type = _Value;
@@ -418,7 +438,7 @@ namespace __detail
_Node_iterator() = default;
explicit
- _Node_iterator(__node_type* __p) noexcept
+ _Node_iterator(_Node* __p) noexcept
: __base_type(__p) { }
reference
@@ -469,7 +489,7 @@ namespace __detail
{
private:
using __base_type = _Node_iterator_base<_Value, __cache>;
- using __node_type = typename __base_type::__node_type;
+ using _Node = typename __base_type::_Node;
// The corresponding non-const iterator.
using __iterator
@@ -486,7 +506,7 @@ namespace __detail
_Node_const_iterator() = default;
explicit
- _Node_const_iterator(__node_type* __p) noexcept
+ _Node_const_iterator(_Node* __p) noexcept
: __base_type(__p) { }
_Node_const_iterator(const __iterator& __x) noexcept
@@ -571,6 +591,7 @@ namespace __detail
{ return !(__x == __y); }
#endif
};
+#endif
// Many of class template _Hashtable's template parameters are policy
// classes. These are defaults for the policies.
@@ -886,7 +907,7 @@ namespace __detail
__hash_code __code = __h->_M_hash_code(__k);
size_t __bkt = __h->_M_bucket_index(__code);
if (auto __node = __h->_M_find_node(__bkt, __k, __code))
- return __node->_M_v().second;
+ return __hashtable::_S_v(*__node).second;
typename __hashtable::_Scoped_node __node {
__h,
@@ -913,7 +934,7 @@ namespace __detail
__hash_code __code = __h->_M_hash_code(__k);
size_t __bkt = __h->_M_bucket_index(__code);
if (auto __node = __h->_M_find_node(__bkt, __k, __code))
- return __node->_M_v().second;
+ return __hashtable::_S_v(*__node).second;
typename __hashtable::_Scoped_node __node {
__h,
@@ -1025,6 +1046,7 @@ namespace __detail
};
#endif
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE <= 9000
/**
* Primary class template _Local_iterator_base.
*
@@ -1035,6 +1057,7 @@ namespace __detail
typename _Hash, typename _RangeHash, typename _Unused,
bool __cache_hash_code>
struct _Local_iterator_base;
+#endif
// Wraps the _Hash object and provides some utility functions for using it.
template<typename _Key, typename _Value, typename _ExtractKey,
@@ -1042,10 +1065,12 @@ namespace __detail
bool /* __cache_hash_code */>
struct _Hash_code_base
{
- // Gives the local iterator implementation access to _M_bucket_index().
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE <= 9000
+ // Gives the local iterator implementation access to _M_hash.
friend struct _Local_iterator_base<_Key, _Value, _ExtractKey,
_Hash, _RangeHash, _Unused, false>;
- public:
+#endif
+
using hasher = _Hash;
hasher
@@ -1079,34 +1104,9 @@ namespace __detail
"hash function must be invocable with an argument of key type");
return _M_hash._M_obj(__k);
}
-
- __hash_code
- _M_hash_code(const _Hash_node_value<_Value, false>& __n) const
- { return _M_hash_code(_ExtractKey{}(__n._M_v())); }
-
- __hash_code
- _M_hash_code(const _Hash_node_value<_Value, true>& __n) const
- { return __n._M_hash_code; }
-
- size_t
- _M_bucket_index(__hash_code __c, size_t __bkt_count) const
- { return _RangeHash{}(__c, __bkt_count); }
-
- size_t
- _M_bucket_index(const _Hash_node_value<_Value, false>& __n,
- size_t __bkt_count) const
- noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>())) )
- {
- return _RangeHash{}(_M_hash_code(_ExtractKey{}(__n._M_v())),
- __bkt_count);
- }
-
- size_t
- _M_bucket_index(const _Hash_node_value<_Value, true>& __n,
- size_t __bkt_count) const noexcept
- { return _RangeHash{}(__n._M_hash_code, __bkt_count); }
};
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE <= 9000
/// Partial specialization used when nodes contain a cached hash code.
template<typename _Key, typename _Value, typename _ExtractKey,
typename _Hash, typename _RangeHash, typename _Unused>
@@ -1356,6 +1356,7 @@ namespace __detail
return __tmp;
}
};
+#endif
/**
* Primary class template _Hashtable_base.
@@ -1399,68 +1400,25 @@ namespace __detail
{ }
bool
- _M_key_equals(const _Key& __k,
- const _Hash_node_value<_Value,
- __hash_cached::value>& __n) const
+ _M_key_equals(const _Key& __lhs, const _Key& __rhs) const
{
static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{},
"key equality predicate must be invocable with two arguments of "
"key type");
- return _M_eq()(__k, _ExtractKey{}(__n._M_v()));
+ return _M_eq()(__lhs, __rhs);
}
template<typename _Kt>
bool
- _M_key_equals_tr(const _Kt& __k,
- const _Hash_node_value<_Value,
- __hash_cached::value>& __n) const
+ _M_key_equals_tr(const _Kt& __lhs, const _Key& __rhs) const
{
static_assert(
__is_invocable<const _Equal&, const _Kt&, const _Key&>{},
"key equality predicate must be invocable with the argument type "
"and the key type");
- return _M_eq()(__k, _ExtractKey{}(__n._M_v()));
+ return _M_eq()(__lhs, __rhs);
}
-#pragma GCC diagnostic push
-#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
- bool
- _M_equals(const _Key& __k, __hash_code __c,
- const _Hash_node_value<_Value, __hash_cached::value>& __n) const
- {
- if constexpr (__hash_cached::value)
- if (__c != __n._M_hash_code)
- return false;
-
- return _M_key_equals(__k, __n);
- }
-
- template<typename _Kt>
- bool
- _M_equals_tr(const _Kt& __k, __hash_code __c,
- const _Hash_node_value<_Value,
- __hash_cached::value>& __n) const
- {
- if constexpr (__hash_cached::value)
- if (__c != __n._M_hash_code)
- return false;
-
- return _M_key_equals_tr(__k, __n);
- }
-
- bool
- _M_node_equals(
- const _Hash_node_value<_Value, __hash_cached::value>& __lhn,
- const _Hash_node_value<_Value, __hash_cached::value>& __rhn) const
- {
- if constexpr (__hash_cached::value)
- if (__lhn._M_hash_code != __rhn._M_hash_code)
- return false;
-
- return _M_key_equals(_ExtractKey{}(__lhn._M_v()), __rhn);
- }
-#pragma GCC diagnostic pop
-
const _Equal&
_M_eq() const noexcept { return _M_equal._M_obj; }
};
@@ -1468,155 +1426,197 @@ namespace __detail
/**
* This type deals with all allocation and keeps an allocator instance.
*/
- template<typename _NodeAlloc>
+ template<typename _NodeTraits, typename _Alloc>
struct _Hashtable_alloc
{
- private:
- [[__no_unique_address__]] _Hashtable_ebo_helper<_NodeAlloc> _M_alloc{};
-
- template<typename>
- struct __get_value_type;
- template<typename _Val, bool _Cache_hash_code>
- struct __get_value_type<_Hash_node<_Val, _Cache_hash_code>>
- { using type = _Val; };
+ using _Node_alloc = __alloc_rebind<_Alloc, typename _NodeTraits::_Node>;
+ using _Node = typename _Node_alloc::value_type;
+ using _Node_alloc_traits = std::allocator_traits<_Node_alloc>;
- public:
- using __node_type = typename _NodeAlloc::value_type;
- using __node_alloc_type = _NodeAlloc;
- // Use __gnu_cxx to benefit from _S_always_equal and al.
- using __node_alloc_traits = __gnu_cxx::__alloc_traits<__node_alloc_type>;
-
- using __value_alloc_traits = typename __node_alloc_traits::template
- rebind_traits<typename __get_value_type<__node_type>::type>;
-
- using __node_ptr = __node_type*;
- using __node_base = _Hash_node_base;
- using __node_base_ptr = __node_base*;
- using __buckets_alloc_type =
- __alloc_rebind<__node_alloc_type, __node_base_ptr>;
- using __buckets_alloc_traits = std::allocator_traits<__buckets_alloc_type>;
- using __buckets_ptr = __node_base_ptr*;
+ using _Node_ptr = typename _NodeTraits::_Node_ptr;
+ using _Base_ptr = typename _NodeTraits::_Base_ptr;
+ using _BucketsAlloc = __alloc_rebind<_Node_alloc, _Base_ptr>;
+ using _Buckets_alloc_traits = std::allocator_traits<_BucketsAlloc>;
+ using _Buckets_ptr = typename _NodeTraits::_Buckets_ptr;
_Hashtable_alloc() = default;
_Hashtable_alloc(const _Hashtable_alloc&) = default;
_Hashtable_alloc(_Hashtable_alloc&&) = default;
- template<typename _Alloc>
- _Hashtable_alloc(_Alloc&& __a)
- : _M_alloc{std::forward<_Alloc>(__a)}
+ template<typename _Alloc2>
+ _Hashtable_alloc(_Alloc2&& __a)
+ : _M_alloc{std::forward<_Alloc2>(__a)}
{ }
- __node_alloc_type&
+ _Node_alloc&
_M_node_allocator()
{ return _M_alloc._M_obj; }
- const __node_alloc_type&
+ const _Node_alloc&
_M_node_allocator() const
{ return _M_alloc._M_obj; }
// Allocate a node and construct an element within it.
template<typename... _Args>
- __node_ptr
+ _Node_ptr
_M_allocate_node(_Args&&... __args);
// Destroy the element within a node and deallocate the node.
void
- _M_deallocate_node(__node_ptr __n);
+ _M_deallocate_node(_Node_ptr __n);
// Deallocate a node.
void
- _M_deallocate_node_ptr(__node_ptr __n);
+ _M_deallocate_node_ptr(_Node_ptr __n);
// Deallocate the linked list of nodes pointed to by __n.
// The elements within the nodes are destroyed.
void
- _M_deallocate_nodes(__node_ptr __n);
+ _M_deallocate_nodes(_Node_ptr __n);
- __buckets_ptr
+ _Buckets_ptr
_M_allocate_buckets(size_t __bkt_count);
void
- _M_deallocate_buckets(__buckets_ptr, size_t __bkt_count);
+ _M_deallocate_buckets(_Buckets_ptr, size_t __bkt_count);
+
+ private:
+ [[__no_unique_address__]] _Hashtable_ebo_helper<_Node_alloc> _M_alloc{};
};
// Definitions of class template _Hashtable_alloc's out-of-line member
// functions.
- template<typename _NodeAlloc>
+ template<typename _NodeTraits, typename _Alloc>
template<typename... _Args>
auto
- _Hashtable_alloc<_NodeAlloc>::_M_allocate_node(_Args&&... __args)
- -> __node_ptr
+ _Hashtable_alloc<_NodeTraits, _Alloc>::_M_allocate_node(_Args&&... __args)
+ -> _Node_ptr
{
+ using _Alloc_ptr = typename _Node_alloc_traits::pointer;
auto& __alloc = _M_node_allocator();
- auto __nptr = __node_alloc_traits::allocate(__alloc, 1);
- __node_ptr __n = std::__to_address(__nptr);
+ _Alloc_ptr __nptr;
+ _Node_ptr __n;
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE
+ __n = __nptr = _Node_alloc_traits::allocate(__alloc, 1);
+#else
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
+ if constexpr (is_same<_Node_ptr, _Alloc_ptr>::value)
+ __n = __nptr = _Node_alloc_traits::allocate(__alloc, 1);
+ else
+ {
+ __nptr = _Node_alloc_traits::allocate(__alloc, 1);
+ __n = std::__to_address(__nptr);
+ }
+#pragma GCC diagnostic pop
+#endif
__try
{
- ::new ((void*)__n) __node_type;
- __node_alloc_traits::construct(__alloc, __n->_M_valptr(),
+ ::new ((void*)std::__to_address(__nptr)) _Node;
+ _Node_alloc_traits::construct(__alloc, __nptr->_M_valptr(),
std::forward<_Args>(__args)...);
return __n;
}
__catch(...)
{
- __n->~__node_type();
- __node_alloc_traits::deallocate(__alloc, __nptr, 1);
+ __nptr->~_Node();
+ _Node_alloc_traits::deallocate(__alloc, __nptr, 1);
__throw_exception_again;
}
}
- template<typename _NodeAlloc>
+ template<typename _NodeTraits, typename _Alloc>
void
- _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node(__node_ptr __n)
+ _Hashtable_alloc<_NodeTraits, _Alloc>::_M_deallocate_node(_Node_ptr __n)
{
- __node_alloc_traits::destroy(_M_node_allocator(), __n->_M_valptr());
+ _Node_alloc_traits::destroy(_M_node_allocator(), __n->_M_valptr());
_M_deallocate_node_ptr(__n);
}
- template<typename _NodeAlloc>
+ template<typename _NodeTraits, typename _Alloc>
void
- _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node_ptr(__node_ptr __n)
+ _Hashtable_alloc<_NodeTraits, _Alloc>::_M_deallocate_node_ptr(_Node_ptr __p)
{
- using _Ptr = typename __node_alloc_traits::pointer;
- auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__n);
- __n->~__node_type();
- __node_alloc_traits::deallocate(_M_node_allocator(), __ptr, 1);
+ auto& __alloc = _M_node_allocator();
+ __p->~_Node();
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE
+ _Node_alloc_traits::deallocate(__alloc, __p, 1);
+#else
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
+ using _Alloc_ptr = typename _Node_alloc_traits::pointer;
+ if constexpr (is_same<_Node_ptr, _Alloc_ptr>::value)
+ _Node_alloc_traits::deallocate(__alloc, __p, 1);
+ else
+ {
+ // When not using the allocator's pointer type internally we must
+ // convert __ptr to _Alloc_ptr so it can be deallocated.
+ auto __ptr = std::pointer_traits<_Alloc_ptr>::pointer_to(*__p);
+ _Node_alloc_traits::deallocate(__alloc, __ptr, 1);
+ }
+#pragma GCC diagnostic pop
+#endif
}
- template<typename _NodeAlloc>
+ template<typename _NodeTraits, typename _Alloc>
void
- _Hashtable_alloc<_NodeAlloc>::_M_deallocate_nodes(__node_ptr __n)
+ _Hashtable_alloc<_NodeTraits, _Alloc>::_M_deallocate_nodes(_Node_ptr __n)
{
while (__n)
{
- __node_ptr __tmp = __n;
+ _Node_ptr __tmp = __n;
__n = __n->_M_next();
_M_deallocate_node(__tmp);
}
}
- template<typename _NodeAlloc>
+ template<typename _NodeTraits, typename _Alloc>
auto
- _Hashtable_alloc<_NodeAlloc>::_M_allocate_buckets(size_t __bkt_count)
- -> __buckets_ptr
+ _Hashtable_alloc<_NodeTraits, _Alloc>::
+ _M_allocate_buckets(size_t __bkt_count)
+ -> _Buckets_ptr
{
- __buckets_alloc_type __alloc(_M_node_allocator());
+ _BucketsAlloc __alloc(_M_node_allocator());
- auto __ptr = __buckets_alloc_traits::allocate(__alloc, __bkt_count);
- __buckets_ptr __p = std::__to_address(__ptr);
- __builtin_memset(__p, 0, __bkt_count * sizeof(__node_base_ptr));
- return __p;
+ auto __ptr = _Buckets_alloc_traits::allocate(__alloc, __bkt_count);
+ std::__uninitialized_default_n(__ptr, __bkt_count);
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
+ return __ptr;
+#else
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
+ using __alloc_ptr = typename _Buckets_alloc_traits::pointer;
+ if constexpr (is_same<_Buckets_ptr, __alloc_ptr>::value)
+ return __ptr;
+ else
+ return std::__to_address(__ptr);
+#pragma GCC diagnostic pop
+#endif
}
- template<typename _NodeAlloc>
+ template<typename _NodeTraits, typename _Alloc>
void
- _Hashtable_alloc<_NodeAlloc>::
- _M_deallocate_buckets(__buckets_ptr __bkts, size_t __bkt_count)
+ _Hashtable_alloc<_NodeTraits, _Alloc>::
+ _M_deallocate_buckets(_Buckets_ptr __bkts, size_t __bkt_count)
{
- using _Ptr = typename __buckets_alloc_traits::pointer;
- auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__bkts);
- __buckets_alloc_type __alloc(_M_node_allocator());
- __buckets_alloc_traits::deallocate(__alloc, __ptr, __bkt_count);
+ _BucketsAlloc __alloc(_M_node_allocator());
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE
+ _Buckets_alloc_traits::deallocate(__alloc, __bkts, __bkt_count);
+#else
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
+ using _Alloc_ptr = typename _Buckets_alloc_traits::pointer;
+ if constexpr (is_same<_Buckets_ptr, _Alloc_ptr>::value)
+ _Buckets_alloc_traits::deallocate(__alloc, __bkts, __bkt_count);
+ else
+ {
+ // When not using the allocator's pointer type internally we must
+ // convert __ptr to _Alloc_ptr so it can be deallocated.
+ auto __ptr = std::pointer_traits<_Alloc_ptr>::pointer_to(*__bkts);
+ _Buckets_alloc_traits::deallocate(__alloc, __ptr, __bkt_count);
+ }
+#pragma GCC diagnostic pop
+#endif
}
///@} hashtable-detail
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/115939.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/115939.cc
index 3a68acaff77..d708ab38b36 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_map/115939.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/115939.cc
@@ -3,6 +3,11 @@
// Bug 115939 - Cannot unambiguously compare iterators in std::unordered_map
+// The code to manage allocator fancy pointer do not suffer from
+// the ambiguity problem tested here so make sure that this code
+// is not being used.
+#undef _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE
+
#include <unordered_map>
struct any_conv
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/allocator/ext_ptr.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/allocator/ext_ptr.cc
new file mode 100644
index 00000000000..5a7096a51fc
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/allocator/ext_ptr.cc
@@ -0,0 +1,40 @@
+// { dg-do run { target c++11 } }
+
+#include <unordered_map>
+#include <memory>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+bool operator==(const T& l, const T& r)
+{ return l.i == r.i; }
+
+struct H
+{
+ std::size_t
+ operator()(const T& t) const noexcept
+ { return t.i; }
+};
+
+struct E : std::equal_to<T>
+{ };
+
+using __gnu_test::CustomPointerAlloc;
+
+template class std::unordered_map<T, int, H, E,
+ CustomPointerAlloc<std::pair<const T, int>>>;
+
+void test01()
+{
+ typedef CustomPointerAlloc<std::pair<const T, int>> alloc_type;
+ typedef std::unordered_map<T, int, H, E, alloc_type> test_type;
+ test_type v;
+ v.insert({ T(), 0 });
+ VERIFY( ++v.begin() == v.end() );
+}
+
+int main()
+{
+ test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/requirements/explicit_instantiation/alloc_ptr.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/requirements/explicit_instantiation/alloc_ptr.cc
new file mode 100644
index 00000000000..381b1fc0ab9
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/requirements/explicit_instantiation/alloc_ptr.cc
@@ -0,0 +1,106 @@
+// { dg-do compile { target c++11 } }
+
+#include <unordered_map>
+#include <testsuite_allocator.h>
+
+// An allocator that uses __gnu_cxx::_Pointer_adapter as its pointer type.
+template class std::unordered_map<int, int,
+ std::hash<int>, std::equal_to<int>,
+ __gnu_test::CustomPointerAlloc<std::pair<const int, int>>>;
+
+// Unlike __gnu_cxx::_Pointer_adapter, this fancy pointer supports neither
+// implicit nor explicit conversions from raw pointers. The constructor from
+// a raw pointer is explicit and requires a second parameter. The only way for
+// containers to construct one of these pointers is pointer_traits::pointer_to.
+template<typename T>
+struct Pointer : __gnu_test::PointerBase<Pointer<T>, T>
+{
+ using Base = __gnu_test::PointerBase<Pointer<T>, T>;
+
+ Pointer() = default;
+ Pointer(std::nullptr_t) : Base() { }
+ explicit Pointer(T* p, int) : Base(p) { }
+
+ // Allow conversions to const_pointer and to void_pointer
+ template<typename U, typename = typename std::enable_if<
+ (!std::is_const<U>::value && std::is_same<T, const U>::value)
+ || (std::is_void<T>::value && std::is_convertible<U*, T*>::value)
+ >::type>
+ Pointer(const Pointer<U>& p) : Base(p.operator->()) { }
+
+ template<typename U>
+ static typename std::enable_if<std::is_same<U, T>::value, Pointer>::type
+ pointer_to(U& t)
+ { return Pointer(std::addressof(t), 1); }
+};
+
+// A minimal allocator that uses Pointer as its pointer type.
+template<typename T>
+struct Allocator
+{
+ using value_type = T;
+ using pointer = Pointer<T>;
+
+ Allocator() = default;
+ template<typename U>
+ Allocator(const Allocator<U>&) { }
+
+ pointer allocate(std::size_t n)
+ { return pointer(std::allocator<T>().allocate(n), 1); }
+
+ void deallocate(pointer p, std::size_t n)
+ {
+ std::allocator<T>().deallocate(p.operator->(), n);
+ }
+
+ bool operator==(const Allocator&) const { return true; }
+ bool operator!=(const Allocator&) const { return false; }
+};
+
+template class std::unordered_map<int, int,
+ std::hash<int>, std::equal_to<int>,
+ Allocator<std::pair<const int, int>>>;
+
+#include <testsuite_iterators.h>
+
+struct OtherHash
+{
+ std::size_t
+ operator()(int v) const noexcept
+ { return std::hash<int>{}(v); }
+};
+
+void
+test_template_members(__gnu_test::input_container<std::pair<short, int>>& c)
+{
+ // Use member functions that are not included in explicit instantiations.
+ std::unordered_map<int, int,
+ std::hash<int>, std::equal_to<int>,
+ Allocator<std::pair<const int, int>>> m(c.begin(), c.end());
+ m.emplace(1, 1);
+ m.emplace_hint(m.begin(), 1, 1);
+ m.insert(c.begin(), c.end());
+#if __glibcxx_unordered_map_try_emplace
+ m.try_emplace(2, 2);
+#endif
+
+#ifdef __cpp_lib_node_extract
+ std::unordered_map<int, int,
+ OtherHash, std::equal_to<int>,
+ Allocator<std::pair<const int, int>>> m1;
+ m.merge(m1);
+ std::unordered_multimap<int, int,
+ OtherHash, std::equal_to<int>,
+ Allocator<std::pair<const int, int>>> mm1;
+ m.merge(mm1);
+#endif
+
+#ifdef __glibcxx_ranges_to_container
+ std::pair<short, int> arr[2];
+ __gnu_test::test_input_range<std::pair<short, int>> r(arr);
+ std::unordered_map<int, int,
+ std::hash<int>, std::equal_to<int>,
+ Allocator<std::pair<const int, int>>> m2(std::from_range, r);
+ m2.insert_range(r);
+#endif
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/requirements/explicit_instantiation/alloc_ptr_abi_incompatible.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/requirements/explicit_instantiation/alloc_ptr_abi_incompatible.cc
new file mode 100644
index 00000000000..1c9642e4748
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/requirements/explicit_instantiation/alloc_ptr_abi_incompatible.cc
@@ -0,0 +1,4 @@
+// { dg-options "-Wp,-w -D_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE=9001" }
+// { dg-do compile { target c++11 } }
+
+#include "alloc_ptr.cc"
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/requirements/explicit_instantiation/alloc_ptr_ignored.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/requirements/explicit_instantiation/alloc_ptr_ignored.cc
new file mode 100644
index 00000000000..15c16d0c2cd
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/requirements/explicit_instantiation/alloc_ptr_ignored.cc
@@ -0,0 +1,4 @@
+// { dg-options "-Wp,-w -D_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE=0" }
+// { dg-do compile { target c++11 } }
+
+#include "alloc_ptr.cc"
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/allocator/ext_ptr.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/allocator/ext_ptr.cc
new file mode 100644
index 00000000000..5034175b8a9
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/allocator/ext_ptr.cc
@@ -0,0 +1,40 @@
+// { dg-do run { target c++11 } }
+
+#include <unordered_map>
+#include <memory>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+bool operator==(const T& l, const T& r)
+{ return l.i == r.i; }
+
+struct H
+{
+ std::size_t
+ operator()(const T& t) const noexcept
+ { return t.i; }
+};
+
+struct E : std::equal_to<T>
+{ };
+
+using __gnu_test::CustomPointerAlloc;
+
+template class std::unordered_multimap<T, int, H, E,
+ CustomPointerAlloc<std::pair<const T, int>>>;
+
+void test01()
+{
+ typedef CustomPointerAlloc<std::pair<const T, int>> alloc_type;
+ typedef std::unordered_multimap<T, int, H, E, alloc_type> test_type;
+ test_type v;
+ v.insert({ T(), 0 });
+ VERIFY( ++v.begin() == v.end() );
+}
+
+int main()
+{
+ test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/requirements/explicit_instantiation/alloc_ptr.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/requirements/explicit_instantiation/alloc_ptr.cc
new file mode 100644
index 00000000000..2a854b5e7d1
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/requirements/explicit_instantiation/alloc_ptr.cc
@@ -0,0 +1,101 @@
+// { dg-do compile { target c++11 } }
+
+#include <unordered_map>
+#include <testsuite_allocator.h>
+
+// An allocator that uses __gnu_cxx::_Pointer_adapter as its pointer type.
+template class std::unordered_multimap<int, int,
+ std::hash<int>, std::equal_to<int>,
+ __gnu_test::CustomPointerAlloc<std::pair<const int, int>>>;
+
+// Unlike __gnu_cxx::_Pointer_adapter, this fancy pointer supports neither
+// implicit nor explicit conversions from raw pointers. The constructor from
+// a raw pointer is explicit and requires a second parameter. The only way for
+// containers to construct one of these pointers is pointer_traits::pointer_to.
+template<typename T>
+struct Pointer : __gnu_test::PointerBase<Pointer<T>, T>
+{
+ using Base = __gnu_test::PointerBase<Pointer<T>, T>;
+
+ Pointer() = default;
+ Pointer(std::nullptr_t) : Base() { }
+ explicit Pointer(T* p, int) : Base(p) { }
+
+ // Allow conversions to const_pointer and to void_pointer
+ template<typename U, typename = typename std::enable_if<
+ (!std::is_const<U>::value && std::is_same<T, const U>::value)
+ || (std::is_void<T>::value && std::is_convertible<U*, T*>::value)
+ >::type>
+ Pointer(const Pointer<U>& p) : Base(p.operator->()) { }
+
+ template<typename U>
+ static typename std::enable_if<std::is_same<U, T>::value, Pointer>::type
+ pointer_to(U& t)
+ { return Pointer(std::addressof(t), 1); }
+};
+
+// A minimal allocator that uses Pointer as its pointer type.
+template<typename T>
+struct Allocator
+{
+ using value_type = T;
+ using pointer = Pointer<T>;
+
+ Allocator() = default;
+ template<typename U>
+ Allocator(const Allocator<U>&) { }
+
+ pointer allocate(std::size_t n)
+ { return pointer(std::allocator<T>().allocate(n), 1); }
+
+ void deallocate(pointer p, std::size_t n)
+ {
+ std::allocator<T>().deallocate(p.operator->(), n);
+ }
+
+ bool operator==(const Allocator&) const { return true; }
+ bool operator!=(const Allocator&) const { return false; }
+};
+
+template class std::unordered_multimap<int, int,
+ std::hash<int>, std::equal_to<int>,
+ Allocator<std::pair<const int, int>>>;
+
+#include <testsuite_iterators.h>
+
+struct OtherHash
+{
+ std::size_t
+ operator()(int v) const noexcept
+ { return std::hash<int>{}(v); }
+};
+
+void
+test_template_members(__gnu_test::input_container<std::pair<short, int>>& c)
+{
+ // Use member functions that are not included in explicit instantiations.
+ std::unordered_multimap<int, int,
+ std::hash<int>, std::equal_to<int>,
+ Allocator<std::pair<const int, int>>> m(c.begin(), c.end());
+ m.insert(c.begin(), c.end());
+
+#ifdef __cpp_lib_node_extract
+ std::unordered_map<int, int,
+ OtherHash, std::equal_to<int>,
+ Allocator<std::pair<const int, int>>> m1;
+ m.merge(m1);
+ std::unordered_multimap<int, int,
+ OtherHash, std::equal_to<int>,
+ Allocator<std::pair<const int, int>>> mm1;
+ m.merge(mm1);
+#endif
+
+#ifdef __glibcxx_ranges_to_container
+ std::pair<short, int> arr[2];
+ __gnu_test::test_input_range<std::pair<short, int>> r(arr);
+ std::unordered_multimap<int, int,
+ std::hash<int>, std::equal_to<int>,
+ Allocator<std::pair<const int, int>>> m2(std::from_range, r);
+ m2.insert_range(r);
+#endif
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/requirements/explicit_instantiation/alloc_ptr_abi_incompatible.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/requirements/explicit_instantiation/alloc_ptr_abi_incompatible.cc
new file mode 100644
index 00000000000..1c9642e4748
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/requirements/explicit_instantiation/alloc_ptr_abi_incompatible.cc
@@ -0,0 +1,4 @@
+// { dg-options "-Wp,-w -D_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE=9001" }
+// { dg-do compile { target c++11 } }
+
+#include "alloc_ptr.cc"
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/requirements/explicit_instantiation/alloc_ptr_ignored.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/requirements/explicit_instantiation/alloc_ptr_ignored.cc
new file mode 100644
index 00000000000..15c16d0c2cd
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/requirements/explicit_instantiation/alloc_ptr_ignored.cc
@@ -0,0 +1,4 @@
+// { dg-options "-Wp,-w -D_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE=0" }
+// { dg-do compile { target c++11 } }
+
+#include "alloc_ptr.cc"
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/allocator/ext_ptr.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/allocator/ext_ptr.cc
new file mode 100644
index 00000000000..8e8ceb1ed10
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/allocator/ext_ptr.cc
@@ -0,0 +1,39 @@
+// { dg-do run { target c++11 } }
+
+#include <unordered_set>
+#include <memory>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+bool operator==(const T& l, const T& r)
+{ return l.i == r.i; }
+
+struct H
+{
+ std::size_t
+ operator()(const T& t) const noexcept
+ { return t.i; }
+};
+
+struct E : std::equal_to<T>
+{ };
+
+using __gnu_test::CustomPointerAlloc;
+
+template class std::unordered_multiset<T, H, E, CustomPointerAlloc<T>>;
+
+void test01()
+{
+ typedef CustomPointerAlloc<T> alloc_type;
+ typedef std::unordered_multiset<T, H, E, alloc_type> test_type;
+ test_type v;
+ v.insert(T());
+ VERIFY( ++v.begin() == v.end() );
+}
+
+int main()
+{
+ test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/requirements/explicit_instantiation/alloc_ptr.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/requirements/explicit_instantiation/alloc_ptr.cc
new file mode 100644
index 00000000000..5f687bc685e
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/requirements/explicit_instantiation/alloc_ptr.cc
@@ -0,0 +1,97 @@
+// { dg-do compile { target c++11 } }
+
+#include <unordered_set>
+#include <testsuite_allocator.h>
+
+// An allocator that uses __gnu_cxx::_Pointer_adapter as its pointer type.
+template class std::unordered_multiset<int, std::hash<int>, std::equal_to<int>,
+ __gnu_test::CustomPointerAlloc<int>>;
+
+// Unlike __gnu_cxx::_Pointer_adapter, this fancy pointer supports neither
+// implicit nor explicit conversions from raw pointers. The constructor from
+// a raw pointer is explicit and requires a second parameter. The only way for
+// containers to construct one of these pointers is pointer_traits::pointer_to.
+template<typename T>
+struct Pointer : __gnu_test::PointerBase<Pointer<T>, T>
+{
+ using Base = __gnu_test::PointerBase<Pointer<T>, T>;
+
+ Pointer() = default;
+ Pointer(std::nullptr_t) : Base() { }
+ explicit Pointer(T* p, int) : Base(p) { }
+
+ // Allow conversions to const_pointer and to void_pointer
+ template<typename U, typename = typename std::enable_if<
+ (!std::is_const<U>::value && std::is_same<T, const U>::value)
+ || (std::is_void<T>::value && std::is_convertible<U*, T*>::value)
+ >::type>
+ Pointer(const Pointer<U>& p) : Base(p.operator->()) { }
+
+ template<typename U>
+ static typename std::enable_if<std::is_same<U, T>::value, Pointer>::type
+ pointer_to(U& t)
+ { return Pointer(std::addressof(t), 1); }
+};
+
+// A minimal allocator that uses Pointer as its pointer type.
+template<typename T>
+struct Allocator
+{
+ using value_type = T;
+ using pointer = Pointer<T>;
+
+ Allocator() = default;
+ template<typename U>
+ Allocator(const Allocator<U>&) { }
+
+ pointer allocate(std::size_t n)
+ { return pointer(std::allocator<T>().allocate(n), 1); }
+
+ void deallocate(pointer p, std::size_t n)
+ {
+ std::allocator<T>().deallocate(p.operator->(), n);
+ }
+
+ bool operator==(const Allocator&) const { return true; }
+ bool operator!=(const Allocator&) const { return false; }
+};
+
+template class std::unordered_multiset<int, std::hash<int>, std::equal_to<int>,
+ Allocator<int>>;
+
+#include <testsuite_iterators.h>
+
+struct OtherHash
+{
+ std::size_t
+ operator()(int v) const noexcept
+ { return std::hash<int>{}(v); }
+};
+
+void
+test_template_members(__gnu_test::input_container<short>& c)
+{
+ // Use member functions that are not included in explicit instantiations.
+ std::unordered_multiset<int, std::hash<int>, std::equal_to<int>,
+ Allocator<int>> s(c.begin(), c.end());
+ s.emplace(1);
+ s.emplace_hint(s.begin(), 1);
+ s.insert(c.begin(), c.end());
+
+#ifdef __cpp_lib_node_extract
+ std::unordered_set<int, OtherHash, std::equal_to<int>,
+ Allocator<int>> s1;
+ s.merge(s1);
+ std::unordered_multiset<int, OtherHash, std::equal_to<int>,
+ Allocator<int>> ms1;
+ s.merge(ms1);
+#endif
+
+#ifdef __glibcxx_ranges_to_container
+ short arr[2];
+ __gnu_test::test_input_range<short> r(arr);
+ std::unordered_multiset<int, std::hash<int>, std::equal_to<int>,
+ Allocator<int>> s2(std::from_range, r);
+ s2.insert_range(r);
+#endif
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/requirements/explicit_instantiation/alloc_ptr_abi_incompatible.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/requirements/explicit_instantiation/alloc_ptr_abi_incompatible.cc
new file mode 100644
index 00000000000..1c9642e4748
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/requirements/explicit_instantiation/alloc_ptr_abi_incompatible.cc
@@ -0,0 +1,4 @@
+// { dg-options "-Wp,-w -D_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE=9001" }
+// { dg-do compile { target c++11 } }
+
+#include "alloc_ptr.cc"
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/requirements/explicit_instantiation/alloc_ptr_ignored.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/requirements/explicit_instantiation/alloc_ptr_ignored.cc
new file mode 100644
index 00000000000..15c16d0c2cd
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/requirements/explicit_instantiation/alloc_ptr_ignored.cc
@@ -0,0 +1,4 @@
+// { dg-options "-Wp,-w -D_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE=0" }
+// { dg-do compile { target c++11 } }
+
+#include "alloc_ptr.cc"
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/allocator/ext_ptr.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/allocator/ext_ptr.cc
index 2f774bdad7d..8da4a07fdec 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_set/allocator/ext_ptr.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/allocator/ext_ptr.cc
@@ -15,10 +15,7 @@
// with this library; see the file COPYING3. If not see
// <http://www.gnu.org/licenses/>.
-// This test fails to compile since C++17 (see xfail-if below) so we can only
-// do a "run" test for C++11 and C++14, and a "compile" test for C++17 and up.
-// { dg-do run { target { c++11_only || c++14_only } } }
-// { dg-do compile { target c++17 } }
+// { dg-do run { target { c++11 } } }
#include <unordered_set>
#include <memory>
@@ -33,8 +30,6 @@ struct E : std::equal_to<T> { };
using __gnu_test::CustomPointerAlloc;
-// { dg-xfail-if "node reinsertion assumes raw pointers" { c++17 } }
-// TODO when removing this xfail change the test back to "dg-do run".
template class std::unordered_set<T, H, E, CustomPointerAlloc<T>>;
void test01()
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/buckets/swap.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/buckets/swap.cc
index b32f4895bfa..de39bf39927 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_set/buckets/swap.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/buckets/swap.cc
@@ -34,37 +34,56 @@ namespace
int _M_modulo;
};
+
+ struct slow_hash : hash
+ {
+ slow_hash() = default;
+ slow_hash(int modulo)
+ : hash(modulo)
+ { }
+ };
}
-void
-test01()
+namespace std
{
- // static_assert(std::__cache_default<int, hash>::value,
- // "Unexpected default cache value");
- typedef std::unordered_set<int, hash> us_t;
- us_t us1(10, hash(13));
- us_t us2(10, hash(7));
+ template<>
+ struct __is_fast_hash<slow_hash> : public std::false_type
+ { };
+}
+
+static_assert(!std::__cache_default<int, hash>::value,
+ "Unexpected default cache value");
+static_assert(std::__cache_default<int, slow_hash>::value,
+ "Unexpected default cache value");
- VERIFY( us1.hash_function()._M_modulo == 13 );
- VERIFY( us2.hash_function()._M_modulo == 7 );
+template<typename _Hash>
+ void
+ test01()
+ {
+ typedef std::unordered_set<int, _Hash> us_t;
+ us_t us1(10, _Hash(13));
+ us_t us2(10, _Hash(7));
- const int nb = 5;
- for (int i = 0; i != nb * us1.hash_function()._M_modulo; ++i)
- us1.insert(i);
+ VERIFY( us1.hash_function()._M_modulo == 13 );
+ VERIFY( us2.hash_function()._M_modulo == 7 );
- us_t::local_iterator lit = us1.begin(12);
- us_t::local_iterator litend = us1.end(12);
- VERIFY( std::distance(lit, litend) == nb );
+ const int nb = 5;
+ for (int i = 0; i != nb * us1.hash_function()._M_modulo; ++i)
+ us1.insert(i);
- us1.swap(us2);
+ auto lit = us1.begin(12);
+ auto litend = us1.end(12);
+ VERIFY( std::distance(lit, litend) == nb );
- VERIFY( us1.hash_function()._M_modulo == 7 );
- VERIFY( us2.hash_function()._M_modulo == 13 );
+ us1.swap(us2);
+ VERIFY( us1.hash_function()._M_modulo == 7 );
+ VERIFY( us2.hash_function()._M_modulo == 13 );
- VERIFY( std::distance(lit, litend) == nb );
-}
+ VERIFY( std::distance(lit, litend) == nb );
+ }
int main()
{
- test01();
+ test01<hash>();
+ test01<slow_hash>();
}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/buckets/swap_with_new_abi_alloc_ptr.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/buckets/swap_with_new_abi_alloc_ptr.cc
new file mode 100644
index 00000000000..363c57b5e76
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/buckets/swap_with_new_abi_alloc_ptr.cc
@@ -0,0 +1,4 @@
+// { dg-options "-Wp,-w -D_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE=9002" }
+// { dg-do run { target c++11 } }
+
+#include "swap.cc"
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/buckets/swap_with_new_alloc_ptr.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/buckets/swap_with_new_alloc_ptr.cc
new file mode 100644
index 00000000000..505104ab29c
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/buckets/swap_with_new_alloc_ptr.cc
@@ -0,0 +1,4 @@
+// { dg-options "-Wp,-w -D_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE=9001" }
+// { dg-do run { target c++11 } }
+
+#include "swap.cc"
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc
index 0178eb26fee..5c22c27db08 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc
@@ -1,5 +1,6 @@
// { dg-do compile { target c++11 } }
// { dg-require-normal-mode "" }
+// { dg-add-options no_pch }
// Copyright (C) 2011-2025 Free Software Foundation, Inc.
//
@@ -20,6 +21,11 @@
// { dg-error "qualify your functors .* with noexcept" "" { target *-*-* } 0 }
+// _Hashtable code to use allocator fancy pointer type is always caching
+// the hash code so if this mode is forced thanks to below macro the test
+// won't fail. Undef the macro so that this code is not used.
+#undef _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE
+
#include <unordered_set>
namespace
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/requirements/explicit_instantiation/alloc_ptr.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/requirements/explicit_instantiation/alloc_ptr.cc
new file mode 100644
index 00000000000..4b4a780afef
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/requirements/explicit_instantiation/alloc_ptr.cc
@@ -0,0 +1,97 @@
+// { dg-do compile { target c++11 } }
+
+#include <unordered_set>
+#include <testsuite_allocator.h>
+
+// An allocator that uses __gnu_cxx::_Pointer_adapter as its pointer type.
+template class std::unordered_set<int, std::hash<int>, std::equal_to<int>,
+ __gnu_test::CustomPointerAlloc<int>>;
+
+// Unlike __gnu_cxx::_Pointer_adapter, this fancy pointer supports neither
+// implicit nor explicit conversions from raw pointers. The constructor from
+// a raw pointer is explicit and requires a second parameter. The only way for
+// containers to construct one of these pointers is pointer_traits::pointer_to.
+template<typename T>
+struct Pointer : __gnu_test::PointerBase<Pointer<T>, T>
+{
+ using Base = __gnu_test::PointerBase<Pointer<T>, T>;
+
+ Pointer() = default;
+ Pointer(std::nullptr_t) : Base() { }
+ explicit Pointer(T* p, int) : Base(p) { }
+
+ // Allow conversions to const_pointer and to void_pointer
+ template<typename U, typename = typename std::enable_if<
+ (!std::is_const<U>::value && std::is_same<T, const U>::value)
+ || (std::is_void<T>::value && std::is_convertible<U*, T*>::value)
+ >::type>
+ Pointer(const Pointer<U>& p) : Base(p.operator->()) { }
+
+ template<typename U>
+ static typename std::enable_if<std::is_same<U, T>::value, Pointer>::type
+ pointer_to(U& t)
+ { return Pointer(std::addressof(t), 1); }
+};
+
+// A minimal allocator that uses Pointer as its pointer type.
+template<typename T>
+struct Allocator
+{
+ using value_type = T;
+ using pointer = Pointer<T>;
+
+ Allocator() = default;
+ template<typename U>
+ Allocator(const Allocator<U>&) { }
+
+ pointer allocate(std::size_t n)
+ { return pointer(std::allocator<T>().allocate(n), 1); }
+
+ void deallocate(pointer p, std::size_t n)
+ {
+ std::allocator<T>().deallocate(p.operator->(), n);
+ }
+
+ bool operator==(const Allocator&) const { return true; }
+ bool operator!=(const Allocator&) const { return false; }
+};
+
+template class std::unordered_set<int, std::hash<int>, std::equal_to<int>,
+ Allocator<int>>;
+
+#include <testsuite_iterators.h>
+
+struct OtherHash
+{
+ std::size_t
+ operator()(int v) const noexcept
+ { return std::hash<int>{}(v); }
+};
+
+void
+test_template_members(__gnu_test::input_container<short>& c)
+{
+ // Use member functions that are not included in explicit instantiations.
+ std::unordered_set<int, std::hash<int>, std::equal_to<int>,
+ Allocator<int>> s(c.begin(), c.end());
+ s.emplace(1);
+ s.emplace_hint(s.begin(), 1);
+ s.insert(c.begin(), c.end());
+
+#ifdef __cpp_lib_node_extract
+ std::unordered_set<int, OtherHash, std::equal_to<int>,
+ Allocator<int>> s1;
+ s.merge(s1);
+ std::unordered_multiset<int, OtherHash, std::equal_to<int>,
+ Allocator<int>> m1;
+ s.merge(m1);
+#endif
+
+#ifdef __glibcxx_ranges_to_container
+ short arr[2];
+ __gnu_test::test_input_range<short> r(arr);
+ std::unordered_set<int, std::hash<int>, std::equal_to<int>,
+ Allocator<int>> s2(std::from_range, r);
+ s2.insert_range(r);
+#endif
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/requirements/explicit_instantiation/alloc_ptr_abi_incompatible.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/requirements/explicit_instantiation/alloc_ptr_abi_incompatible.cc
new file mode 100644
index 00000000000..1c9642e4748
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/requirements/explicit_instantiation/alloc_ptr_abi_incompatible.cc
@@ -0,0 +1,4 @@
+// { dg-options "-Wp,-w -D_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE=9001" }
+// { dg-do compile { target c++11 } }
+
+#include "alloc_ptr.cc"
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/requirements/explicit_instantiation/alloc_ptr_ignored.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/requirements/explicit_instantiation/alloc_ptr_ignored.cc
new file mode 100644
index 00000000000..15c16d0c2cd
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/requirements/explicit_instantiation/alloc_ptr_ignored.cc
@@ -0,0 +1,4 @@
+// { dg-options "-Wp,-w -D_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE=0" }
+// { dg-do compile { target c++11 } }
+
+#include "alloc_ptr.cc"
More information about the Libstdc++
mailing list