[PATCH][_Hashtable] Add fancy allocator pointer support
François Dumont
frs.dumont@gmail.com
Thu Feb 27 21:04:46 GMT 2025
Hi
I've refreshed the patch following latest Hashtable commit and also the PR:
https://forge.sourceware.org/gcc/gcc-TEST/pulls/32
Regards,
François
On 25/01/2025 22:52, François Dumont wrote:
> Hi
>
> Here is the patch to add allocator fancy pointer type support in
> _Hashtable.
>
> 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::__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<>::_M_bucket_begin): Remove.
> (_Hashtable<>::_S_v, _S_next, _M_single_bucket_ptr,
> _M_bucket_index): New.
> (_Hashtable<>::_M_key_equals, _M_key_equals_tr, _M_equals,
> _M_equals_tr,
> _M_node_equals, _M_hash_code): New.
> (_Hashtable<>::__location_type::_M_base_ptr): 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.
> (_Hashtable_base<>::_M_equals(const _Key&, __hash_code,
> const _Hash_node_value<_Value, false>&)): New.
> (_Hashtable_base<>::_M_equals_tr(const _Kt&, __hash_code,
> const _Hash_node_value<_Value, false>&)): New.
> (_Hashtable_base<>::_M_node_equals(const
> _Hash_node_value<_Value, false>&,
> const _Hash_node_value<_Value, false>)): New.
> * 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/requirements/explicit_instantiation/alloc_ptr.cc:
> New test case.
> *
> testsuite/23_containers/unordered_set/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
> New test case.
> * testsuite/util/testsuite_allocator.h
> (NullablePointer<>): Allow different pointer
> type comparison.
>
> Tested under Linux x64.
>
> Available as PR:
>
> https://forge.sourceware.org/gcc/gcc-TEST/pulls/32
>
> Ok to commit ?
>
> François
-------------- next part --------------
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 246e62afc6a..ebb52e141c1 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -67,6 +67,425 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
is_default_constructible<_Allocator>>{},
__detail::_Hash_node_base>;
+namespace __hashtable
+{
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE
+ 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<typename _Ptr>
+ using __element_t =
+ typename pointer_traits<_Ptr>::element_type;
+
+ template<typename _ValPtr>
+ struct _Node
+ : public __hashtable::_Node_base<std::__ptr_rebind<_ValPtr, void>>
+ , public __detail::_Hash_node_value<__element_t<_ValPtr>, true>
+ {
+ using _Node_ptr = __ptr_rebind<_ValPtr, _Node>;
+
+ _Node() = default;
+ _Node(_Node&&) = delete;
+
+ _Node_ptr
+ _M_node_ptr() noexcept
+ { return pointer_traits<_Node_ptr>::pointer_to(*this); }
+
+ _Node_ptr
+ _M_next() const noexcept
+ {
+ return this->_M_nxt
+ ? static_cast<__element_t<_Node_ptr>&>(*this->_M_nxt)._M_node_ptr()
+ : nullptr;
+ }
+ };
+
+ 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<bool _Const, bool _ConstantIterator, typename _ValPtr>
+ 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 = __hashtable::_Node<_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<false, _ConstantIterator, _ValPtr>& __it)
+ requires _Const
+#else
+ template<bool _OtherConst,
+ typename = __enable_if_t<_Const && !_OtherConst>>
+ constexpr
+ _Iterator(const _Iterator<_OtherConst, _ConstantIterator, _ValPtr>& __it)
+#endif
+ : _IteratorBase(__it._M_cur) { }
+
+ [[__nodiscard__]]
+ reference
+ operator*() const noexcept
+ { return static_cast<_Node&>(*this->_M_cur)._M_v(); }
+
+ [[__nodiscard__]]
+ pointer
+ operator->() const noexcept
+ { 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<bool _Const, bool _ConstantIterator, typename _ValPtr,
+ typename _RangeHash>
+ struct _Local_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 = ptrdiff_t;
+
+ using _IteratorBase = _Iterator_base<_ValPtr>;
+ using _Node = __hashtable::_Node<_ValPtr>;
+ using _Node_base = __hashtable::_Node_base<__ptr_rebind<_ValPtr, void>>;
+ using _Base_ptr = __ptr_rebind<_ValPtr, _Node_base>;
+
+ _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<false, _ConstantIterator,
+ _ValPtr, _RangeHash>& __it)
+ requires _Const
+#else
+ template<bool _OtherConst,
+ typename = __enable_if_t<_Const && !_OtherConst>>
+ constexpr
+ _Local_iterator(const _Local_iterator<_OtherConst, _ConstantIterator,
+ _ValPtr, _RangeHash>& __it)
+#endif
+ : _IteratorBase(__it._M_cur)
+ , _M_bucket(__it._M_bucket), _M_bucket_count(__it._M_bucket_count)
+ { }
+
+ [[__nodiscard__]]
+ reference
+ operator*() const noexcept
+ { return static_cast<_Node&>(*this->_M_cur)._M_v(); }
+
+ [[__nodiscard__]]
+ pointer
+ operator->() const noexcept
+ { return static_cast<_Node&>(*this->_M_cur)._M_valptr(); }
+
+ _GLIBCXX14_CONSTEXPR _Local_iterator&
+ operator++() noexcept
+ {
+ this->_M_cur = this->_M_cur->_M_nxt;
+ if (this->_M_cur)
+ {
+ size_t __bkt
+ = _RangeHash{}(static_cast<_Node&>(*this->_M_cur)._M_hash_code,
+ _M_bucket_count);
+ if (__bkt != _M_bucket)
+ this->_M_cur = nullptr;
+ }
+ 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 _Key, 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 _Key, typename _Val, typename _Traits>
+ struct _Node_traits<_Key, _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*;
+
+ static _Node_ptr
+ _S_cast(_Base_ptr __ptr) noexcept
+ { return static_cast<_Node_ptr>(__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 _NodeTraits = _Node_traits<_Key, _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 _Key, typename _Val, typename _ValPtr, typename _Traits>
+ struct _Node_traits
+ : _Node_traits<_Key, _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 _Key, typename _Val, typename _ValPtr, typename _Traits>
+ struct _Node_traits
+ {
+ using __hash_cached = true_type;
+
+ using value_type = _Val;
+ using _Node = __hashtable::_Node<_ValPtr>;
+ 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>;
+
+ static _Node_ptr
+ _S_cast(_Base_ptr __ptr) noexcept
+ { return static_cast<_Node&>(*__ptr)._M_node_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<_Key, _Val, _ValPtr, _Traits>;
+ using _Base_ptr = typename _NodeTraits::_Base_ptr;
+ using _Node_ptr = typename _NodeTraits::_Node_ptr;
+
+ using __hash_cached = typename _Traits::__hash_cached;
+ using __constant_iterators = typename _Traits::__constant_iterators;
+
+ using iterator =
+ __hashtable::_Iterator<false, __constant_iterators::value, _ValPtr>;
+ using const_iterator =
+ __hashtable::_Iterator<true, __constant_iterators::value, _ValPtr>;
+ using local_iterator =
+ __hashtable::_Local_iterator<false, __constant_iterators::value,
+ _ValPtr, _RangeHash>;
+ using const_local_iterator =
+ __hashtable::_Local_iterator<true, __constant_iterators::value,
+ _ValPtr, _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 +615,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<_Key, _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 +630,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<
+ _Key, _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 +664,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 +711,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,7 +728,7 @@ _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.
@@ -350,14 +766,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 +784,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 (auto __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 +832,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 +857,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 +875,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);
}
@@ -469,7 +895,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_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 +915,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 +956,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 +991,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 +1008,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;
@@ -635,11 +1061,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 +1077,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 +1097,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
@@ -700,36 +1126,45 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
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, nullptr, __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, nullptr, __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, nullptr, __bkt, _M_bucket_count);
+ }
float
load_factor() const noexcept
@@ -799,9 +1234,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
#endif // __glibcxx_generic_unordered_lookup
private:
+ static value_type&
+ _S_v(_Node_base& __n) noexcept
+ { return static_cast<_Node&>(__n)._M_v(); }
+
// Bucket index computation helpers.
size_type
- _M_bucket_index(const __node_value_type& __n) const noexcept
+ _M_bucket_index(const _Node_base& __n) const noexcept
+ { return _M_bucket_index(static_cast<const _Node&>(__n)); }
+
+ size_type
+ _M_bucket_index(const _Node_base& __n,
+ size_type __bkt_count) const noexcept
+ {
+ return __hash_code_base::_M_bucket_index
+ (static_cast<const _Node&>(__n), __bkt_count);
+ }
+
+ size_type
+ _M_bucket_index(const _Node& __n) const noexcept
{ return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
size_type
@@ -814,7 +1265,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// 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_hash_code_ext(const _Node& __from) const
{
if constexpr (__and_<__hash_cached, is_empty<_Hash>>::value)
return __from._M_hash_code;
@@ -825,33 +1276,99 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// 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_hash_code_ext(static_cast<const _Node&>(__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);
}
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
+ {
+ return __hashtable_base::_M_key_equals
+ (__k, static_cast<const _Node&>(__n));
+ }
+
+ template<typename _Kt>
+ bool
+ _M_key_equals_tr(const _Kt& __k, const _Node_base& __n) const
+ {
+ return __hashtable_base::_M_key_equals_tr
+ (__k, static_cast<const _Node&>(__n));
+ }
+
+ 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, __node);
+ }
+
+ 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, __node);
+ }
+
+ bool
+ _M_node_equals(const _Node_base& __lhn, const _Node_base& __rhn) const
+ {
+ return _M_node_equals(static_cast<const _Node&>(__lhn),
+ static_cast<const _Node&>(__rhn));
+ }
+
+ bool
+ _M_node_equals(const _Node& __lhn, const _Node& __rhn) const
+ {
+ if constexpr (__hash_cached::value)
+ if (__lhn._M_hash_code != __rhn._M_hash_code)
+ return false;
+
+ return __hashtable_base::_M_key_equals(_ExtractKey{}(__lhn._M_v()),
+ __rhn);
+ }
#pragma GCC diagnostic pop
+ using __hashtable_base::_M_hash_code;
+
+ __hash_code
+ _M_hash_code(const _Node_base& __n) const
+ { return __hashtable_base::_M_hash_code(static_cast<const _Node&>(__n)); }
+
// 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
@@ -864,21 +1381,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);
};
@@ -895,33 +1415,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])
{
@@ -941,15 +1461,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)
@@ -962,11 +1482,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).
@@ -976,13 +1496,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>
@@ -1009,7 +1529,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
@@ -1172,6 +1692,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)
@@ -1194,7 +1731,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();
}
@@ -1212,24 +1749,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;
}
@@ -1237,7 +1774,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().
@@ -1246,7 +1798,7 @@ _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)
@@ -1271,9 +1823,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;
}
@@ -1284,17 +1836,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)
@@ -1306,7 +1856,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;
}
@@ -1336,7 +1886,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;
@@ -1352,22 +1902,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);
// 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);
@@ -1382,17 +1931,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();
}
}
@@ -1485,11 +2035,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.
@@ -1534,9 +2084,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);
@@ -1617,23 +2167,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;
}
@@ -1650,7 +2202,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;
}
@@ -1675,7 +2227,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;
}
@@ -1720,7 +2272,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),
@@ -1736,7 +2288,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),
@@ -1753,7 +2305,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;
}
@@ -1774,7 +2326,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),
@@ -1790,7 +2342,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),
@@ -1806,7 +2358,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
@@ -1814,7 +2366,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();
}
@@ -1842,7 +2394,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// 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&>(),
+ ._M_bucket_index(declval<const _Node&>(),
(std::size_t)0)),
"Cache the hash code or qualify your functors involved"
" in hash code and bucket index computation with noexcept");
@@ -1870,7 +2422,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
@@ -1882,13 +2434,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);
@@ -1940,15 +2492,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,
@@ -1964,15 +2517,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
@@ -1995,7 +2549,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;
@@ -2017,9 +2571,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;
@@ -2038,11 +2592,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;
@@ -2067,7 +2619,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 };
@@ -2091,7 +2643,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 };
@@ -2111,10 +2663,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;
@@ -2125,18 +2677,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 };
@@ -2155,10 +2708,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;
@@ -2169,18 +2722,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 };
@@ -2198,19 +2752,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;
}
@@ -2228,19 +2782,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;
}
@@ -2263,18 +2817,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())
@@ -2291,10 +2844,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;
@@ -2333,7 +2886,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;
@@ -2341,7 +2894,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);
}
@@ -2381,7 +2934,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;
@@ -2425,26 +2978,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_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_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,
@@ -2455,7 +3009,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);
@@ -2473,9 +3027,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,
@@ -2485,8 +3040,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);
@@ -2503,35 +3058,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,
@@ -2544,14 +3099,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, _Node_traits::_S_cast(__n));
}
template<typename _Key, typename _Value, typename _Alloc,
@@ -2561,21 +3116,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;
@@ -2598,8 +3153,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);
@@ -2617,9 +3172,9 @@ _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;
@@ -2628,7 +3183,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
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;
@@ -2656,23 +3211,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;
@@ -2689,8 +3245,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,
@@ -2740,20 +3297,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;
@@ -2783,19 +3339,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)
{
@@ -2821,8 +3376,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;
}
@@ -2833,7 +3387,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;
@@ -2852,8 +3406,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;
}
@@ -2882,33 +3435,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);
@@ -2916,15 +3468,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;
@@ -2933,15 +3485,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..8902d85b6a7 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -33,12 +33,18 @@
#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 <bits/stl_uninitialized.h> // for __uninitialized_default_n
#include <ext/aligned_buffer.h> // for __gnu_cxx::__aligned_buffer
#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 +124,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 +137,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 +154,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 +181,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 +198,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 +213,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)...); }
@@ -296,6 +302,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 +374,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 +387,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
@@ -395,6 +412,7 @@ namespace __detail
#endif
};
+#if _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE <= 9000
/// Node iterators, used to iterate through all the hashtable.
template<typename _Value, bool __constant_iterators, bool __cache>
struct _Node_iterator
@@ -402,7 +420,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 +436,7 @@ namespace __detail
_Node_iterator() = default;
explicit
- _Node_iterator(__node_type* __p) noexcept
+ _Node_iterator(_Node* __p) noexcept
: __base_type(__p) { }
reference
@@ -469,7 +487,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 +504,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 +589,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 +905,10 @@ 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;
+ {
+ using _Node = typename __hashtable::_Node;
+ return static_cast<_Node&>(*__node)._M_v().second;
+ }
typename __hashtable::_Scoped_node __node {
__h,
@@ -913,7 +935,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,
@@ -1085,7 +1107,7 @@ namespace __detail
{ return _M_hash_code(_ExtractKey{}(__n._M_v())); }
__hash_code
- _M_hash_code(const _Hash_node_value<_Value, true>& __n) const
+ _M_hash_code(const _Hash_node_code_cache<true>& __n) const
{ return __n._M_hash_code; }
size_t
@@ -1102,11 +1124,12 @@ namespace __detail
}
size_t
- _M_bucket_index(const _Hash_node_value<_Value, true>& __n,
+ _M_bucket_index(const _Hash_node_code_cache<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 +1379,7 @@ namespace __detail
return __tmp;
}
};
+#endif
/**
* Primary class template _Hashtable_base.
@@ -1400,8 +1424,7 @@ namespace __detail
bool
_M_key_equals(const _Key& __k,
- const _Hash_node_value<_Value,
- __hash_cached::value>& __n) const
+ const _Hash_node_value_base<_Value>& __n) const
{
static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{},
"key equality predicate must be invocable with two arguments of "
@@ -1412,8 +1435,7 @@ namespace __detail
template<typename _Kt>
bool
_M_key_equals_tr(const _Kt& __k,
- const _Hash_node_value<_Value,
- __hash_cached::value>& __n) const
+ const _Hash_node_value_base<_Value>& __n) const
{
static_assert(
__is_invocable<const _Equal&, const _Kt&, const _Key&>{},
@@ -1422,45 +1444,6 @@ namespace __detail
return _M_eq()(__k, _ExtractKey{}(__n._M_v()));
}
-#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 +1451,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{};
+ 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>;
- 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; };
-
- 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..3e1a75f6b6d
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/requirements/explicit_instantiation/alloc_ptr.cc
@@ -0,0 +1,111 @@
+// { 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<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<int>> m1;
+ m.merge(m1);
+ std::unordered_multimap<int, int,
+ OtherHash, std::equal_to<int>,
+ Allocator<int>> mm1;
+ m.merge(mm1);
+#endif
+
+#if 0
+#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<int>> m2(std::from_range, r);
+ m2.assign_range(r);
+ m2.prepend_range(r);
+ m2.append_range(r);
+ m2.insert_range(m2.begin(), r);
+#endif
+#endif
+}
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..5bd4277aa8f
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/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_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<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<int>> m1;
+ m.merge(m1);
+ std::unordered_multimap<int, int,
+ OtherHash, std::equal_to<int>,
+ Allocator<int>> mm1;
+ m.merge(mm1);
+#endif
+
+#if 0
+#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<int>> m2(std::from_range, r);
+ m2.assign_range(r);
+ m2.prepend_range(r);
+ m2.append_range(r);
+ m2.insert_range(m2.begin(), r);
+#endif
+#endif
+}
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..fcbcfc7d9ec
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/requirements/explicit_instantiation/alloc_ptr.cc
@@ -0,0 +1,102 @@
+// { 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
+
+#if 0
+#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.assign_range(r);
+ s2.prepend_range(r);
+ s2.append_range(r);
+ s2.insert_range(s2.begin(), r);
+#endif
+#endif
+}
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/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..f2fb4fb9f37
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/requirements/explicit_instantiation/alloc_ptr.cc
@@ -0,0 +1,102 @@
+// { 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
+
+#if 0
+#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.assign_range(r);
+ s2.prepend_range(r);
+ s2.append_range(r);
+ s2.insert_range(s2.begin(), r);
+#endif
+#endif
+}
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"
diff --git a/libstdc++-v3/testsuite/util/testsuite_allocator.h b/libstdc++-v3/testsuite/util/testsuite_allocator.h
index be596bf00fb..b3cbafcce10 100644
--- a/libstdc++-v3/testsuite/util/testsuite_allocator.h
+++ b/libstdc++-v3/testsuite/util/testsuite_allocator.h
@@ -631,6 +631,20 @@ namespace __gnu_test
operator!=(NullablePointer lhs, NullablePointer rhs) noexcept
{ return lhs.value != rhs.value; }
+ friend inline Ptr
+ get_ptr(NullablePointer x) noexcept
+ { return x.value; }
+
+ template<typename OtherPtr>
+ friend inline bool
+ operator==(NullablePointer lhs, NullablePointer<OtherPtr> rhs) noexcept
+ { return lhs.value == get_ptr(rhs); }
+
+ template<typename OtherPtr>
+ friend inline bool
+ operator!=(NullablePointer lhs, NullablePointer<OtherPtr> rhs) noexcept
+ { return lhs.value != get_ptr(rhs); }
+
protected:
explicit NullablePointer(Ptr p) noexcept : value(p) { }
Ptr value;
More information about the Libstdc++
mailing list