[PATCH][_Hashtable] Add fancy allocator pointer support
François Dumont
frs.dumont@gmail.com
Sat Jan 25 21:52:33 GMT 2025
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 d6d76a743bb..66634d6e08e 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 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 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 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,23 +1234,121 @@ _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
_M_bucket_index(__hash_code __c) const
{ return __hash_code_base::_M_bucket_index(__c, _M_bucket_count); }
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
+ // Like _M_bucket_index but when the node is coming from another
+ // container instance.
+ size_type
+ _M_bucket_index_ex(const _Node& __n) const
+ {
+ if constexpr (__hash_cached::value)
+ if constexpr (std::is_empty<_Hash>::value)
+ return _RangeHash{}(__n._M_hash_code, _M_bucket_count);
+
+ return _RangeHash{}
+ (this->_M_hash_code(_ExtractKey{}(__n._M_v())), _M_bucket_count);
+ }
+
+ size_type
+ _M_bucket_index_ex(const _Node_base& __n) const noexcept
+ { return _M_bucket_index_ex(static_cast<const _Node&>(__n)); }
+
+ void
+ _M_copy_code(_Node& __to, const _Node& __from) const
+ {
+ if constexpr (__hash_cached::value)
+ {
+ if constexpr (std::is_empty<_Hash>::value)
+ __to._M_hash_code = __from._M_hash_code;
+ else
+ __to._M_hash_code =
+ this->_M_hash_code(_ExtractKey{}(__from._M_v()));
+ }
+ }
+#pragma GCC diagnostic pop
+
+ 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
+ {
+ return __hashtable_base::_M_equals(__k, __c,
+ static_cast<const _Node&>(__n));
+ }
+
+ template<typename _Kt>
+ bool
+ _M_equals_tr(const _Kt& __k, __hash_code __c,
+ const _Node_base& __n) const
+ {
+ return __hashtable_base::_M_equals_tr(__k, __c,
+ static_cast<const _Node&>(__n));
+ }
+
+ bool
+ _M_node_equals(const _Node_base& __lhn, const _Node_base& __rhn) const
+ {
+ return __hashtable_base::_M_node_equals
+ (static_cast<const _Node&>(__lhn), static_cast<const _Node&>(__rhn));
+ }
+
+ bool
+ _M_node_equals(const _Node& __lhn, const _Node& __rhn) const
+ { return __hashtable_base::_M_node_equals(__lhn, __rhn); }
+
+ 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
@@ -828,21 +1361,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);
};
@@ -859,33 +1395,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])
{
@@ -905,15 +1441,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)
@@ -926,11 +1462,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).
@@ -940,13 +1476,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>
@@ -973,7 +1509,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
@@ -1136,6 +1672,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)
@@ -1158,7 +1711,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();
}
@@ -1176,24 +1729,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;
}
@@ -1201,7 +1754,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().
@@ -1211,14 +1779,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _H2>
__hash_code
_M_src_hash_code(const _H2&, const key_type& __k,
- const __node_value_type& __src_n) const
+ const _Node_base& __src_n) const
{
if constexpr (std::is_same_v<_H2, _Hash>)
if constexpr (std::is_empty_v<_Hash>)
// If the node has a cached hash code, it's OK to use it.
- return this->_M_hash_code(__src_n);
+ return _M_hash_code(__src_n);
- return this->_M_hash_code(__k);
+ return _M_hash_code(__k);
}
public:
@@ -1236,9 +1804,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;
}
@@ -1249,17 +1817,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)
@@ -1271,7 +1837,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;
}
@@ -1301,7 +1867,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;
@@ -1317,23 +1883,22 @@ _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);
const key_type& __k = _ExtractKey{}(__node._M_v());
// Hash code from this->hash_function():
auto __code = _M_src_hash_code(__src.hash_function(), __k, __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);
@@ -1348,7 +1913,7 @@ _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).
@@ -1359,7 +1924,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__hash_code __code
= _M_src_hash_code(__src.hash_function(), __k, *__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();
}
}
@@ -1452,11 +2018,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.
@@ -1501,9 +2067,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);
@@ -1584,23 +2150,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()));
- this->_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;
- this->_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;
}
@@ -1617,7 +2185,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;
}
@@ -1642,7 +2210,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;
}
@@ -1687,7 +2255,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),
@@ -1703,7 +2271,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),
@@ -1720,7 +2288,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;
}
@@ -1741,7 +2309,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),
@@ -1757,7 +2325,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),
@@ -1773,7 +2341,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
@@ -1781,7 +2349,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();
}
@@ -1809,7 +2377,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");
@@ -1837,7 +2405,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
@@ -1849,13 +2417,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);
@@ -1907,15 +2475,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,
@@ -1931,15 +2500,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
@@ -1962,7 +2532,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;
@@ -1984,9 +2554,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;
@@ -2005,11 +2575,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;
@@ -2034,7 +2602,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 };
@@ -2058,7 +2626,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 };
@@ -2078,10 +2646,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;
@@ -2092,18 +2660,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 };
@@ -2122,10 +2691,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;
@@ -2136,18 +2705,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 };
@@ -2165,19 +2735,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;
}
@@ -2195,19 +2765,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;
}
@@ -2230,18 +2800,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())
@@ -2258,10 +2827,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;
@@ -2300,7 +2869,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;
@@ -2308,7 +2877,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);
}
@@ -2348,7 +2917,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;
@@ -2392,26 +2961,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,
@@ -2422,7 +2992,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);
@@ -2440,9 +3010,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
this->_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,
@@ -2452,8 +3023,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);
@@ -2470,35 +3041,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,
@@ -2511,14 +3082,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,
@@ -2528,21 +3099,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;
@@ -2565,8 +3136,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);
@@ -2584,9 +3155,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;
@@ -2595,7 +3166,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;
@@ -2623,23 +3194,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;
@@ -2656,8 +3228,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,
@@ -2707,20 +3280,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;
@@ -2750,19 +3322,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)
{
@@ -2788,8 +3359,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;
}
@@ -2800,7 +3370,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;
@@ -2819,8 +3389,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;
}
@@ -2849,49 +3418,48 @@ _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(*__x_n);
+ std::size_t __ybkt = __other._M_bucket_index_ex(*__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(*__x_n);
+ std::size_t __ybkt = __other._M_bucket_index_ex(*__x_n);
auto __y_prev_n = __other._M_buckets[__ybkt];
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;
@@ -2900,15 +3468,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 1fa8c01d5e8..a147e0bfb5c 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); }
};
/**
@@ -359,6 +372,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); }
@@ -368,12 +385,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
@@ -393,6 +410,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
@@ -400,7 +418,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;
@@ -416,7 +434,7 @@ namespace __detail
_Node_iterator() = default;
explicit
- _Node_iterator(__node_type* __p) noexcept
+ _Node_iterator(_Node* __p) noexcept
: __base_type(__p) { }
reference
@@ -467,7 +485,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
@@ -484,7 +502,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
@@ -569,6 +587,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.
@@ -884,7 +903,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,
@@ -911,7 +933,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,
@@ -1083,7 +1105,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
@@ -1100,7 +1122,7 @@ 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); }
@@ -1108,21 +1130,12 @@ namespace __detail
_M_store_code(_Hash_node_code_cache<false>&, __hash_code) const
{ }
- void
- _M_copy_code(_Hash_node_code_cache<false>&,
- const _Hash_node_code_cache<false>&) const
- { }
-
void
_M_store_code(_Hash_node_code_cache<true>& __n, __hash_code __c) const
{ __n._M_hash_code = __c; }
-
- void
- _M_copy_code(_Hash_node_code_cache<true>& __to,
- const _Hash_node_code_cache<true>& __from) const
- { __to._M_hash_code = __from._M_hash_code; }
};
+#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>
@@ -1372,6 +1385,7 @@ namespace __detail
return __tmp;
}
};
+#endif
/**
* Primary class template _Hashtable_base.
@@ -1416,8 +1430,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 "
@@ -1428,8 +1441,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&>{},
@@ -1438,44 +1450,54 @@ 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
+ const _Hash_node_value<_Value, true>& __n) const
{
- if constexpr (__hash_cached::value)
- if (__c != __n._M_hash_code)
- return false;
+ if (__c != __n._M_hash_code)
+ return false;
return _M_key_equals(__k, __n);
}
+ bool
+ _M_equals(const _Key& __k, __hash_code,
+ const _Hash_node_value<_Value, false>& __n) const
+ { 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
+ const _Hash_node_value<_Value, true>& __n) const
{
- if constexpr (__hash_cached::value)
- if (__c != __n._M_hash_code)
- return false;
+ if (__c != __n._M_hash_code)
+ return false;
return _M_key_equals_tr(__k, __n);
}
+ template<typename _Kt>
+ bool
+ _M_equals_tr(const _Kt& __k, __hash_code,
+ const _Hash_node_value<_Value, false>& __n) const
+ { 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
+ const _Hash_node_value<_Value, true>& __lhn,
+ const _Hash_node_value<_Value, true>& __rhn) const
{
- if constexpr (__hash_cached::value)
- if (__lhn._M_hash_code != __rhn._M_hash_code)
- return false;
+ if (__lhn._M_hash_code != __rhn._M_hash_code)
+ return false;
return _M_key_equals(_ExtractKey{}(__lhn._M_v()), __rhn);
}
-#pragma GCC diagnostic pop
+
+ bool
+ _M_node_equals(
+ const _Hash_node_value<_Value, false>& __lhn,
+ const _Hash_node_value<_Value, false>& __rhn) const
+ { return _M_key_equals(_ExtractKey{}(__lhn._M_v()), __rhn); }
const _Equal&
_M_eq() const noexcept { return _M_equal._M_obj; }
@@ -1484,155 +1506,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/modifiers/merge.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/merge.cc
index 10b61464243..010181f7038 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/merge.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/merge.cc
@@ -417,6 +417,51 @@ test09()
VERIFY( c2.size() == 3 );
}
+struct slow_stateful_hash
+{
+ size_t seed = 0;
+
+ auto operator()(const int& i) const noexcept
+ { return std::hash<int>()(i) + seed; }
+};
+
+namespace std
+{
+ template<>
+ struct __is_fast_hash<slow_stateful_hash> : public std::false_type
+ { };
+}
+
+void
+test10()
+{
+ using map_type = std::unordered_map<int, int, slow_stateful_hash>;
+ map_type c1({ {1, 1}, {3, 3}, {5, 5} }, 0, slow_stateful_hash{1});
+ map_type c2({ {2, 2}, {4, 4}, {6, 6} }, 0, slow_stateful_hash{2});
+ const auto c3 = c2;
+
+ c1.merge(c2);
+ VERIFY( c1.size() == 6 );
+ VERIFY( c2.empty() );
+
+ c2 = c3;
+ c1.clear();
+ c1.merge(std::move(c2));
+ VERIFY( c1 == c3 );
+ VERIFY( c2.empty() );
+
+ c2.merge(std::move(c1));
+ VERIFY( c1.empty() );
+ VERIFY( c2 == c3 );
+
+ c2.merge(c1);
+ VERIFY( c1.empty() );
+ VERIFY( c2 == c3 );
+
+ c2.merge(c2);
+ VERIFY( c2 == c3 );
+}
+
int
main()
{
@@ -429,4 +474,5 @@ main()
test07();
test08();
test09();
+ test10();
}
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