* [PATCH] _Hashtable fancy pointer support
@ 2024-06-26 20:38 François Dumont
2024-06-26 21:41 ` Jonathan Wakely
0 siblings, 1 reply; 5+ messages in thread
From: François Dumont @ 2024-06-26 20:38 UTC (permalink / raw)
To: libstdc++; +Cc: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 3837 bytes --]
Hi
Here is my proposal to add support for fancy allocator pointer.
The only place where we still have C pointers is at the
iterator::pointer level but it's consistent with std::list
implementation and also logical considering that we do not get
value_type pointers from the allocator.
I also wondered if it was ok to use nullptr in different places or if I
should rather do __node_ptr{}. But recent modifications are using
nullptr so I think it's fine.
libstdc++: Use allocator::pointer in hashtable implementation
In _Hashtable implementation store the allocator::pointer returned
by the allocate
call as-is and return it on the deallocate when necessary. This is
true for both
the allocated nodes and the bucket array.
libstdc++-v3/ChangeLog:
* include/bits/hashtable_policy.h: Include
<bits/stl_uninitialized.h>.
(__alloc_val_ptr<>): New template alias.
(_Hash_pnode_base<>): New.
(_Hash_node<>::__node_ptr): New.
(_Hash_node<>::__node_type): New.
(_Hash_pnode<typename _ValuePtr, bool _Cache_hash_code>): New.
(__get_node_type<>): New, template alias to _Hash_node<> if
allocator pointer
type is a native pointer, _Hash_pnode<> otherwise.
(_Hashtable_iterator_base<typename _NodePtr>): New.
(_Node_iterator_base<>): Inherits from latter.
(_Hashtable_iterator<typename _NodePtr, bool
__constant_iterators>):
New.
(_Hashtable_const_iterator<typename _NodePtr, bool
__constant_iterators>):
New.
(_Insert_base<>::__alloc_ptr): New.
(_Insert_base<>::__hashtable_alloc): Remove.
(_Insert_base<>::__node_type): New.
(_Insert_base<>::__node_ptr): New.
(_Insert_base<>::iterator): Define conditionally to
_Node_iterator<>
or _Hashtable_iterator<> depending on __alloc_ptr being a
raw pointer.
(_Insert_base<>::const_iterator): Define conditionally to
_Node_const_iterator<> or _Hashtable_const_iterator<>
depending on
__alloc_ptr being a raw pointer.
(_Hashtable_local_iter_base<>): New.
(_Hashtable_local_iterator<>): New.
(_Hashtable_const_local_iterator<>): New.
(__local_iterator<>): New template alias.
(__const_local_iterator<>): New template alias.
(_Hashtable_alloc<>::__get_node_base): New struct.
(_Hashtable_alloc<>::__value_alloc_traits): Remove.
(_Hashtable_alloc<>::__node_ptr): Define as
__node_alloc_traits::pointer.
(_Hashtable_alloc<>::__node_base): Define as
__get_node_base<>::pointer.
(_Hashtable_alloc<>::__node_base_ptr): Define as
__ptr_rebind<__node_ptr, __node_base>.
* include/bits/hashtable.h (_Hashtable<>): Adapt.
*
testsuite/23_containers/unordered_map/allocator/ext_ptr.cc: New test.
*
testsuite/23_containers/unordered_multimap/allocator/ext_ptr.cc:
New test.
*
testsuite/23_containers/unordered_multiset/allocator/ext_ptr.cc:
New test.
*
testsuite/23_containers/unordered_set/allocator/ext_ptr.cc: Adapt.
Tested under Linux x64, ok to commit ?
François
[-- Attachment #2: hashtable_cust_ptr_patch.txt --]
[-- Type: text/plain, Size: 44769 bytes --]
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 361da2b3b4d..c9817adf910 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -200,8 +200,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_RehashPolicy, _Traits>,
private __detail::_Hashtable_alloc<
__alloc_rebind<_Alloc,
- __detail::_Hash_node<_Value,
- _Traits::__hash_cached::value>>>,
+ __detail::__get_node_type<_Alloc, _Value,
+ _Traits::__hash_cached::value>>>,
private _Hashtable_enable_default_ctor<_Equal, _Hash, _Alloc>
{
static_assert(is_same<typename remove_cv<_Value>::type, _Value>::value,
@@ -216,21 +216,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
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_type = __detail::__get_node_type<_Alloc, _Value,
+ _Traits::__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 __value_alloc_traits =
+ typename __node_alloc_traits::template rebind_traits<_Value>;
using __node_base = typename __hashtable_alloc::__node_base;
using __node_base_ptr = typename __hashtable_alloc::__node_base_ptr;
+ using __node_base_ptr_traits = std::pointer_traits<__node_base_ptr>;
using __buckets_ptr = typename __hashtable_alloc::__buckets_ptr;
+ using __buckets_ptr_traits = std::pointer_traits<__buckets_ptr>;
using __insert_base = __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey,
_Equal, _Hash,
@@ -258,15 +260,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
using const_iterator = typename __insert_base::const_iterator;
- using local_iterator = __detail::_Local_iterator<key_type, _Value,
- _ExtractKey, _Hash, _RangeHash, _Unused,
- __constant_iterators::value,
- __hash_cached::value>;
+ using local_iterator = __detail::__local_iterator<
+ __node_ptr, key_type, value_type,
+ _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 const_local_iterator = __detail::__const_local_iterator<
+ __node_ptr, key_type, value_type,
+ _ExtractKey, _Hash, _RangeHash, _Unused,
+ __constant_iterators::value, __hash_cached::value>;
private:
using __rehash_type = _RehashPolicy;
@@ -392,7 +394,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
#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;
size_type _M_element_count = 0;
@@ -406,11 +409,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// numerous checks in the code to avoid 0 modulus.
__node_base_ptr _M_single_bucket = nullptr;
+ __buckets_ptr
+ _M_single_bucket_ptr()
+ { return __buckets_ptr_traits::pointer_to(_M_single_bucket); }
+
+ __node_base_ptr
+ _M_before_begin_ptr()
+ { return __node_base_ptr_traits::pointer_to(_M_before_begin); }
+
void
_M_update_bbegin()
{
if (auto __begin = _M_begin())
- _M_buckets[_M_bucket_index(*__begin)] = &_M_before_begin;
+ _M_buckets[_M_bucket_index(*__begin)] = _M_before_begin_ptr();
}
void
@@ -422,7 +433,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
bool
_M_uses_single_bucket(__buckets_ptr __bkts) const
- { return __builtin_expect(__bkts == &_M_single_bucket, false); }
+ {
+ return __builtin_expect
+ (std::__to_address(__bkts) == std::addressof(_M_single_bucket),
+ false);
+ }
bool
_M_uses_single_bucket() const
@@ -444,7 +459,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
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);
@@ -463,18 +478,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_deallocate_buckets()
{ _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
+ static __node_ptr
+ _S_cast(__node_ptr __n)
+ { return __n; }
+
+ static __node_ptr
+ _S_cast(__detail::_Hash_node_base* __n)
+ { return static_cast<__node_ptr>(__n); }
+
// 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_base_ptr __n = _M_buckets[__bkt];
- return __n ? static_cast<__node_ptr>(__n->_M_nxt) : nullptr;
+ return __n ? _S_cast(__n->_M_nxt) : nullptr;
}
__node_ptr
_M_begin() const
- { return static_cast<__node_ptr>(_M_before_begin._M_nxt); }
+ { return _S_cast(_M_before_begin._M_nxt); }
// Assign *this using another _Hashtable instance. Whether elements
// are copied or moved depends on the _Ht reference.
@@ -824,7 +847,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
__node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c);
if (__before_n)
- return static_cast<__node_ptr>(__before_n->_M_nxt);
+ return _S_cast(__before_n->_M_nxt);
return nullptr;
}
@@ -835,7 +858,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
auto __before_n = _M_find_before_node_tr(__bkt, __key, __c);
if (__before_n)
- return static_cast<__node_ptr>(__before_n->_M_nxt);
+ return _S_cast(__before_n->_M_nxt);
return nullptr;
}
@@ -863,7 +886,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// _M_before_begin.
_M_buckets[_M_bucket_index(*__node->_M_next())] = __node;
- _M_buckets[__bkt] = &_M_before_begin;
+ _M_buckets[__bkt] = _M_before_begin_ptr();
}
}
@@ -1109,7 +1132,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
node_type
_M_extract_node(size_t __bkt, __node_base_ptr __prev_n)
{
- __node_ptr __n = static_cast<__node_ptr>(__prev_n->_M_nxt);
+ __node_ptr __n = _S_cast(__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);
@@ -1157,7 +1180,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
node_type __nh;
__hash_code __code = this->_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 (auto __prev_node = _M_find_before_node(__bkt, __k, __code))
__nh = _M_extract_node(__bkt, __prev_node);
return __nh;
}
@@ -1468,7 +1491,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;
}
@@ -1493,7 +1516,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;
}
@@ -1571,7 +1594,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;
}
@@ -1624,7 +1647,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
@@ -1694,13 +1717,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);
@@ -2035,12 +2058,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_find_before_node(const key_type& __k)
-> __node_base_ptr
{
- __node_base_ptr __prev_p = &_M_before_begin;
+ __node_base_ptr __prev_p = _M_before_begin_ptr();
if (!__prev_p->_M_nxt)
return nullptr;
- for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);
- __p != nullptr;
+ for (__node_ptr __p = _S_cast(__prev_p->_M_nxt); __p != nullptr;
__p = __p->_M_next())
{
if (this->_M_key_equals(__k, *__p))
@@ -2069,8 +2091,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (!__prev_p)
return nullptr;
- for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);;
- __p = __p->_M_next())
+ for (__node_ptr __p = _S_cast(__prev_p->_M_nxt);; __p = __p->_M_next())
{
if (this->_M_equals(__k, __code, *__p))
return __prev_p;
@@ -2099,8 +2120,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (!__prev_p)
return nullptr;
- for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);;
- __p = __p->_M_next())
+ for (__node_ptr __p = _S_cast(__prev_p->_M_nxt);; __p = __p->_M_next())
{
if (this->_M_equals_tr(__k, __code, *__p))
return __prev_p;
@@ -2273,10 +2293,11 @@ _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 __hint_base = __hint;
__node_base_ptr __prev
= __builtin_expect(__hint != nullptr, false)
&& this->_M_equals(__k, __code, *__hint)
- ? __hint
+ ? __hint_base
: _M_find_before_node(__bkt, __k, __code);
if (__prev)
@@ -2437,7 +2458,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return 0;
// We found a matching node, erase it.
- __n = static_cast<__node_ptr>(__prev_n->_M_nxt);
+ __n = _S_cast(__prev_n->_M_nxt);
__bkt = _M_bucket_index(*__n);
}
else
@@ -2451,7 +2472,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return 0;
// We found a matching node, erase it.
- __n = static_cast<__node_ptr>(__prev_n->_M_nxt);
+ __n = _S_cast(__prev_n->_M_nxt);
}
_M_erase(__bkt, __prev_n, __n);
@@ -2478,7 +2499,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return 0;
// We found a matching node, erase it.
- __n = static_cast<__node_ptr>(__prev_n->_M_nxt);
+ __n = _S_cast(__prev_n->_M_nxt);
__bkt = _M_bucket_index(*__n);
}
else
@@ -2491,7 +2512,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (!__prev_n)
return 0;
- __n = static_cast<__node_ptr>(__prev_n->_M_nxt);
+ __n = _S_cast(__prev_n->_M_nxt);
}
// _GLIBCXX_RESOLVE_LIB_DEFECTS
@@ -2633,7 +2654,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_ptr();
if (__p->_M_nxt)
__new_buckets[__bbegin_bkt] = __p;
__bbegin_bkt = __bkt;
@@ -2713,7 +2734,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_ptr();
if (__p->_M_nxt)
__new_buckets[__bbegin_bkt] = __p;
__bbegin_bkt = __bkt;
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 26def24f24e..225381ccb72 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -33,8 +33,9 @@
#include <tuple> // for std::tuple, std::forward_as_tuple
#include <bits/functional_hash.h> // for __is_fast_hash
-#include <bits/stl_algobase.h> // for std::min, std::is_permutation.
+#include <bits/stl_algobase.h> // for std::min, std::is_permutation
#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
@@ -82,6 +83,11 @@ namespace __detail
{ return __distance_fw(__first, __last,
std::__iterator_category(__first)); }
+ template<typename _Alloc, typename _Value>
+ using __alloc_val_ptr =
+ typename std::allocator_traits<__alloc_rebind<_Alloc,
+ _Value>>::pointer;
+
struct _Identity
{
template<typename _Tp>
@@ -321,6 +327,28 @@ namespace __detail
_Hash_node_base(_Hash_node_base* __next) noexcept : _M_nxt(__next) { }
};
+ /**
+ * struct _Hash_pnode_base
+ *
+ * Like _Hash_node_base but used in case of custom pointer type defined by the
+ * allocator.
+ */
+ template<typename _NodePtr>
+ struct _Hash_pnode_base
+ {
+ using __node_ptr = _NodePtr;
+
+ __node_ptr _M_nxt;
+
+ _Hash_pnode_base()
+ noexcept(std::is_nothrow_default_constructible<__node_ptr>::value)
+ : _M_nxt() { }
+
+ _Hash_pnode_base(__node_ptr __next)
+ noexcept(std::is_nothrow_copy_constructible<__node_ptr>::value)
+ : _M_nxt(__next) { }
+ };
+
/**
* struct _Hash_node_value_base
*
@@ -356,18 +384,23 @@ namespace __detail
/**
* Primary template struct _Hash_node_code_cache.
+ *
+ * No cache.
*/
template<bool _Cache_hash_code>
struct _Hash_node_code_cache
{ };
/**
- * Specialization for node with cache, struct _Hash_node_code_cache.
+ * Specialization for node with cache.
*/
template<>
struct _Hash_node_code_cache<true>
{ std::size_t _M_hash_code; };
+ /**
+ * Node with value and optionally a cache for the hash code.
+ */
template<typename _Value, bool _Cache_hash_code>
struct _Hash_node_value
: _Hash_node_value_base<_Value>
@@ -375,28 +408,64 @@ namespace __detail
{ };
/**
- * Primary template struct _Hash_node.
+ * struct _Hash_node.
+ *
+ * The node definition when the allocator is using raw pointers.
*/
template<typename _Value, bool _Cache_hash_code>
struct _Hash_node
: _Hash_node_base
, _Hash_node_value<_Value, _Cache_hash_code>
{
- _Hash_node*
+ using __node_ptr = _Hash_node*;
+ using __node_type = _Hash_node;
+
+ __node_ptr
+ _M_next() const noexcept
+ { return static_cast<__node_ptr>(this->_M_nxt); }
+ };
+
+ /**
+ * struct _Hash_pnode.
+ *
+ * The node definition used when the allocator define a custom pointer type.
+ */
+ template<typename _ValuePtr, bool _Cache_hash_code>
+ struct _Hash_pnode
+ : _Hash_pnode_base<__ptr_rebind<
+ _ValuePtr, _Hash_pnode<_ValuePtr, _Cache_hash_code>>>
+ , _Hash_node_value<
+ typename std::pointer_traits<_ValuePtr>::element_type, _Cache_hash_code>
+ {
+ using __node_ptr = __ptr_rebind<
+ _ValuePtr, _Hash_pnode<_ValuePtr, _Cache_hash_code>>;
+ using __node_type =
+ typename std::pointer_traits<__node_ptr>::element_type;
+ typedef typename std::pointer_traits<__node_ptr>::difference_type
+ difference_type;
+
+ __node_ptr
_M_next() const noexcept
- { return static_cast<_Hash_node*>(this->_M_nxt); }
+ { return this->_M_nxt; }
};
+ template<typename _Alloc, typename _Value, bool __hash_cached>
+ using __get_node_type = typename std::conditional<
+ std::is_pointer<__alloc_val_ptr<_Alloc, _Value>>::value,
+ _Hash_node<_Value, __hash_cached>,
+ _Hash_pnode<__alloc_val_ptr<_Alloc, _Value>, __hash_cached>>::type;
+
/// Base class for node iterators.
- template<typename _Value, bool _Cache_hash_code>
- struct _Node_iterator_base
+ template<typename _NodePtr>
+ struct _Hashtable_iterator_base
{
- using __node_type = _Hash_node<_Value, _Cache_hash_code>;
+ using __node_ptr = _NodePtr;
+ using __node_type = typename std::pointer_traits<_NodePtr>::element_type;
- __node_type* _M_cur;
+ __node_ptr _M_cur;
- _Node_iterator_base() : _M_cur(nullptr) { }
- _Node_iterator_base(__node_type* __p) noexcept
+ _Hashtable_iterator_base() : _M_cur() { }
+ _Hashtable_iterator_base(__node_ptr __p) noexcept
: _M_cur(__p) { }
void
@@ -404,18 +473,33 @@ namespace __detail
{ _M_cur = _M_cur->_M_next(); }
friend bool
- operator==(const _Node_iterator_base& __x, const _Node_iterator_base& __y)
- noexcept
+ operator==(const _Hashtable_iterator_base& __x,
+ const _Hashtable_iterator_base& __y) noexcept
{ return __x._M_cur == __y._M_cur; }
#if __cpp_impl_three_way_comparison < 201907L
friend bool
- operator!=(const _Node_iterator_base& __x, const _Node_iterator_base& __y)
- noexcept
+ operator!=(const _Hashtable_iterator_base& __x,
+ const _Hashtable_iterator_base& __y) noexcept
{ return __x._M_cur != __y._M_cur; }
#endif
};
+ /// Base class for node iterators.
+ template<typename _Value, bool _Cache_hash_code>
+ struct _Node_iterator_base
+ : _Hashtable_iterator_base<_Hash_node<_Value, _Cache_hash_code>*>
+ {
+ using __base_type =
+ _Hashtable_iterator_base<_Hash_node<_Value, _Cache_hash_code>*>;
+ using __node_ptr = typename __base_type::__node_ptr;
+ using __node_type = typename __base_type::__node_ptr;
+
+ _Node_iterator_base() = default;
+ _Node_iterator_base(__node_ptr __p) noexcept
+ : __base_type(__p) { }
+ };
+
/// Node iterators, used to iterate through all the hashtable.
template<typename _Value, bool __constant_iterators, bool __cache>
struct _Node_iterator
@@ -424,6 +508,7 @@ namespace __detail
private:
using __base_type = _Node_iterator_base<_Value, __cache>;
using __node_type = typename __base_type::__node_type;
+ using __node_ptr = typename __base_type::__node_ptr;
public:
using value_type = _Value;
@@ -439,7 +524,7 @@ namespace __detail
_Node_iterator() = default;
explicit
- _Node_iterator(__node_type* __p) noexcept
+ _Node_iterator(__node_ptr __p) noexcept
: __base_type(__p) { }
reference
@@ -474,6 +559,7 @@ namespace __detail
private:
using __base_type = _Node_iterator_base<_Value, __cache>;
using __node_type = typename __base_type::__node_type;
+ using __node_ptr = typename __base_type::__node_ptr;
public:
typedef _Value value_type;
@@ -486,7 +572,7 @@ namespace __detail
_Node_const_iterator() = default;
explicit
- _Node_const_iterator(__node_type* __p) noexcept
+ _Node_const_iterator(__node_ptr __p) noexcept
: __base_type(__p) { }
_Node_const_iterator(const _Node_iterator<_Value, __constant_iterators,
@@ -517,6 +603,110 @@ namespace __detail
}
};
+ /// Node iterators, used to iterate through all the hashtable.
+ template<typename _NodePtr, bool __constant_iterators>
+ struct _Hashtable_iterator
+ : public _Hashtable_iterator_base<_NodePtr>
+ {
+ private:
+ using __base_type = _Hashtable_iterator_base<_NodePtr>;
+ using __node_type = typename __base_type::__node_type;
+ using __node_ptr = typename __base_type::__node_ptr;
+
+ public:
+ typedef typename __node_type::value_type value_type;
+ typedef typename __node_type::difference_type difference_type;
+ typedef std::forward_iterator_tag iterator_category;
+
+ using pointer = typename std::conditional<__constant_iterators,
+ const value_type*, value_type*>::type;
+
+ using reference = typename std::conditional<__constant_iterators,
+ const value_type&, value_type&>::type;
+
+ _Hashtable_iterator() = default;
+
+ explicit
+ _Hashtable_iterator(__node_ptr __p) noexcept
+ : __base_type(__p) { }
+
+ reference
+ operator*() const noexcept
+ { return this->_M_cur->_M_v(); }
+
+ pointer
+ operator->() const noexcept
+ { return this->_M_cur->_M_valptr(); }
+
+ _Hashtable_iterator&
+ operator++() noexcept
+ {
+ this->_M_incr();
+ return *this;
+ }
+
+ _Hashtable_iterator
+ operator++(int) noexcept
+ {
+ _Hashtable_iterator __tmp(*this);
+ this->_M_incr();
+ return __tmp;
+ }
+ };
+
+ /// Node const_iterators, used to iterate through all the hashtable.
+ template<typename _NodePtr, bool __constant_iterators>
+ struct _Hashtable_const_iterator
+ : public _Hashtable_iterator_base<_NodePtr>
+ {
+ private:
+ using __base_type = _Hashtable_iterator_base<_NodePtr>;
+ using __node_type = typename __base_type::__node_type;
+ using __node_ptr = typename __base_type::__node_ptr;
+
+ public:
+ typedef typename __node_type::value_type value_type;
+ typedef typename __node_type::difference_type difference_type;
+ typedef std::forward_iterator_tag iterator_category;
+
+ typedef const value_type* pointer;
+ typedef const value_type& reference;
+
+ _Hashtable_const_iterator() = default;
+
+ explicit
+ _Hashtable_const_iterator(__node_ptr __p) noexcept
+ : __base_type(__p) { }
+
+ _Hashtable_const_iterator(
+ const _Hashtable_iterator<_NodePtr,
+ __constant_iterators>& __x) noexcept
+ : __base_type(__x._M_cur) { }
+
+ reference
+ operator*() const noexcept
+ { return this->_M_cur->_M_v(); }
+
+ pointer
+ operator->() const noexcept
+ { return this->_M_cur->_M_valptr(); }
+
+ _Hashtable_const_iterator&
+ operator++() noexcept
+ {
+ this->_M_incr();
+ return *this;
+ }
+
+ _Hashtable_const_iterator
+ operator++(int) noexcept
+ {
+ _Hashtable_const_iterator __tmp(*this);
+ this->_M_incr();
+ return __tmp;
+ }
+ };
+
// Many of class template _Hashtable's template parameters are policy
// classes. These are defaults for the policies.
@@ -912,16 +1102,16 @@ namespace __detail
using __hash_cached = typename _Traits::__hash_cached;
using __constant_iterators = typename _Traits::__constant_iterators;
+ using __alloc_ptr = __alloc_val_ptr<_Alloc, _Value>;
- using __hashtable_alloc = _Hashtable_alloc<
- __alloc_rebind<_Alloc, _Hash_node<_Value,
- __hash_cached::value>>>;
+ using __node_type = __get_node_type<_Alloc, _Value, __hash_cached::value>;
+ using __node_ptr = __ptr_rebind<__alloc_ptr, __node_type>;
+ using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
using value_type = typename __hashtable_base::value_type;
using size_type = typename __hashtable_base::size_type;
using __unique_keys = typename _Traits::__unique_keys;
- using __node_alloc_type = typename __hashtable_alloc::__node_alloc_type;
using __node_gen_type = _AllocNode<__node_alloc_type>;
__hashtable&
@@ -939,12 +1129,19 @@ namespace __detail
const _NodeGetter&, false_type __uks);
public:
- using iterator = _Node_iterator<_Value, __constant_iterators::value,
- __hash_cached::value>;
-
- using const_iterator = _Node_const_iterator<_Value,
- __constant_iterators::value,
- __hash_cached::value>;
+ using iterator =
+ typename std::conditional<std::is_pointer<__alloc_ptr>::value,
+ _Node_iterator<_Value,
+ __constant_iterators::value, __hash_cached::value>,
+ _Hashtable_iterator<__node_ptr,
+ __constant_iterators::value>>::type;
+
+ using const_iterator =
+ typename std::conditional<std::is_pointer<__alloc_ptr>::value,
+ _Node_const_iterator<_Value,
+ __constant_iterators::value, __hash_cached::value>,
+ _Hashtable_const_iterator<__node_ptr,
+ __constant_iterators::value>>::type;
using __ireturn_type = __conditional_t<__unique_keys::value,
std::pair<iterator, bool>,
@@ -1280,6 +1477,17 @@ namespace __detail
bool __cache_hash_code>
struct _Local_iterator_base;
+ /**
+ * Primary class template _Hashtable_local_iter_base.
+ *
+ * Base class for local iterators, used to iterate within a bucket
+ * but not between buckets.
+ */
+ template<typename _Key, typename _NodePtr, typename _ExtractKey,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ bool __cache_hash_code>
+ struct _Hashtable_local_iter_base;
+
/**
* Primary class template _Hash_code_base.
*
@@ -1440,6 +1648,49 @@ namespace __detail
_M_get_bucket() const { return _M_bucket; } // for debug mode
};
+ /// Partial specialization used when nodes contain a cached hash code.
+ template<typename _Key, typename _NodePtr, typename _ExtractKey,
+ typename _Hash, typename _RangeHash, typename _Unused>
+ struct _Hashtable_local_iter_base<_Key, _NodePtr, _ExtractKey,
+ _Hash, _RangeHash, _Unused, true>
+ : public _Hashtable_iterator_base<_NodePtr>
+ {
+ protected:
+ using __base_node_iter = _Hashtable_iterator_base<_NodePtr>;
+ using __node_ptr = typename __base_node_iter::__node_ptr;
+ using __node_type = typename __base_node_iter::__node_type;
+ using value_type = typename __node_type::value_type;
+ using __hash_code_base = _Hash_code_base<_Key, value_type, _ExtractKey,
+ _Hash, _RangeHash, _Unused, true>;
+
+ _Hashtable_local_iter_base() = default;
+ _Hashtable_local_iter_base(const __hash_code_base&,
+ __node_ptr __p,
+ std::size_t __bkt, std::size_t __bkt_count)
+ : __base_node_iter(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
+ { }
+
+ void
+ _M_incr()
+ {
+ __base_node_iter::_M_incr();
+ if (this->_M_cur)
+ {
+ std::size_t __bkt
+ = _RangeHash{}(this->_M_cur->_M_hash_code, _M_bucket_count);
+ if (__bkt != _M_bucket)
+ this->_M_cur = nullptr;
+ }
+ }
+
+ std::size_t _M_bucket;
+ std::size_t _M_bucket_count;
+
+ public:
+ std::size_t
+ _M_get_bucket() const { return _M_bucket; } // for debug mode
+ };
+
// Uninitialized storage for a _Hash_code_base.
// This type is DefaultConstructible and Assignable even if the
// _Hash_code_base type isn't, so that _Local_iterator_base<..., false>
@@ -1554,6 +1805,86 @@ namespace __detail
_M_get_bucket() const { return _M_bucket; } // for debug mode
};
+ // Partial specialization used when hash codes are not cached
+ template<typename _Key, typename _NodePtr, typename _ExtractKey,
+ typename _Hash, typename _RangeHash, typename _Unused>
+ struct _Hashtable_local_iter_base<_Key, _NodePtr, _ExtractKey,
+ _Hash, _RangeHash, _Unused, false>
+ : _Hash_code_storage<_Hash>
+ , _Hashtable_iterator_base<_NodePtr>
+ {
+ protected:
+ using __node_iter_base = _Hashtable_iterator_base<_NodePtr>;
+ using __node_type = typename __node_iter_base::__node_type;
+ using __node_ptr = typename __node_iter_base::__node_ptr;
+ using value_type = typename __node_type::value_type;
+ using __hash_code_base = _Hash_code_base<_Key, value_type, _ExtractKey,
+ _Hash, _RangeHash, _Unused, false>;
+
+ _Hashtable_local_iter_base() : _M_bucket_count(-1) { }
+
+ _Hashtable_local_iter_base(const __hash_code_base& __base,
+ __node_ptr __p,
+ std::size_t __bkt, std::size_t __bkt_count)
+ : __node_iter_base(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
+ { _M_init(__base.hash_function()); }
+
+ ~_Hashtable_local_iter_base()
+ {
+ if (_M_bucket_count != -1)
+ _M_destroy();
+ }
+
+ _Hashtable_local_iter_base(const _Hashtable_local_iter_base& __iter)
+ : __node_iter_base(__iter._M_cur), _M_bucket(__iter._M_bucket)
+ , _M_bucket_count(__iter._M_bucket_count)
+ {
+ if (_M_bucket_count != -1)
+ _M_init(*__iter._M_h());
+ }
+
+ _Hashtable_local_iter_base&
+ operator=(const _Hashtable_local_iter_base& __iter)
+ {
+ if (_M_bucket_count != -1)
+ _M_destroy();
+ this->_M_cur = __iter._M_cur;
+ _M_bucket = __iter._M_bucket;
+ _M_bucket_count = __iter._M_bucket_count;
+ if (_M_bucket_count != -1)
+ _M_init(*__iter._M_h());
+ return *this;
+ }
+
+ void
+ _M_incr()
+ {
+ __node_iter_base::_M_incr();
+ if (this->_M_cur)
+ {
+ std::size_t __bkt =
+ _RangeHash{}((*this->_M_h())(_ExtractKey{}(this->_M_cur->_M_v())),
+ _M_bucket_count);
+ if (__bkt != _M_bucket)
+ this->_M_cur = nullptr;
+ }
+ }
+
+ std::size_t _M_bucket;
+ std::size_t _M_bucket_count;
+
+ void
+ _M_init(const _Hash& __h)
+ { ::new(this->_M_h()) _Hash(__h); }
+
+ void
+ _M_destroy() { this->_M_h()->~_Hash(); }
+
+ public:
+ std::size_t
+ _M_get_bucket() const { return _M_bucket; } // for debug mode
+ };
+
/// local iterators
template<typename _Key, typename _Value, typename _ExtractKey,
typename _Hash, typename _RangeHash, typename _Unused,
@@ -1667,6 +1998,156 @@ namespace __detail
}
};
+ /// local iterators
+ template<typename _Key, typename _NodePtr, typename _ExtractKey,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ bool __constant_iterators, bool __cache>
+ struct _Hashtable_local_iterator
+ : public _Hashtable_local_iter_base<_Key, _NodePtr, _ExtractKey,
+ _Hash, _RangeHash, _Unused, __cache>
+ {
+ private:
+ using __base_type =
+ _Hashtable_local_iter_base<_Key, _NodePtr, _ExtractKey,
+ _Hash, _RangeHash, _Unused, __cache>;
+ using __hash_code_base = typename __base_type::__hash_code_base;
+ using __node_type = typename __base_type::__node_type;
+ using __node_ptr = typename __base_type::__node_ptr;
+
+ public:
+ typedef typename __base_type::value_type value_type;
+ typedef typename std::conditional<__constant_iterators,
+ const value_type*, value_type*>::type
+ pointer;
+ typedef typename std::conditional<__constant_iterators,
+ const value_type&, value_type&>::type
+ reference;
+ typedef typename __node_type::difference_type difference_type;
+ typedef std::forward_iterator_tag iterator_category;
+
+ _Hashtable_local_iterator() = default;
+
+ _Hashtable_local_iterator(const __hash_code_base& __base,
+ __node_ptr __n,
+ std::size_t __bkt, std::size_t __bkt_count)
+ : __base_type(__base, __n, __bkt, __bkt_count)
+ { }
+
+ reference
+ operator*() const
+ { return this->_M_cur->_M_v(); }
+
+ pointer
+ operator->() const
+ { return this->_M_cur->_M_valptr(); }
+
+ _Hashtable_local_iterator&
+ operator++()
+ {
+ this->_M_incr();
+ return *this;
+ }
+
+ _Hashtable_local_iterator
+ operator++(int)
+ {
+ _Hashtable_local_iterator __tmp(*this);
+ this->_M_incr();
+ return __tmp;
+ }
+ };
+
+ /// local const_iterators
+ template<typename _Key, typename _NodePtr, typename _ExtractKey,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ bool __constant_iterators, bool __cache>
+ struct _Hashtable_const_local_iterator
+ : public _Hashtable_local_iter_base<_Key, _NodePtr, _ExtractKey,
+ _Hash, _RangeHash, _Unused, __cache>
+ {
+ private:
+ using __base_type =
+ _Hashtable_local_iter_base<_Key, _NodePtr, _ExtractKey,
+ _Hash, _RangeHash, _Unused, __cache>;
+ using __hash_code_base = typename __base_type::__hash_code_base;
+ using __node_type = typename __base_type::__node_type;
+ using __node_ptr = typename __base_type::__node_ptr;
+
+ public:
+ typedef typename __base_type::value_type value_type;
+ typedef const value_type* pointer;
+ typedef const value_type& reference;
+ typedef typename __node_type::difference_type difference_type;
+ typedef std::forward_iterator_tag iterator_category;
+
+ _Hashtable_const_local_iterator() = default;
+
+ _Hashtable_const_local_iterator(const __hash_code_base& __base,
+ __node_ptr __n,
+ std::size_t __bkt, std::size_t __bkt_count)
+ : __base_type(__base, __n, __bkt, __bkt_count)
+ { }
+
+ _Hashtable_const_local_iterator(const _Hashtable_local_iterator<
+ _Key, _NodePtr, _ExtractKey,
+ _Hash, _RangeHash, _Unused,
+ __constant_iterators,
+ __cache>& __x)
+ : __base_type(__x)
+ { }
+
+ reference
+ operator*() const
+ { return this->_M_cur->_M_v(); }
+
+ pointer
+ operator->() const
+ { return this->_M_cur->_M_valptr(); }
+
+ _Hashtable_const_local_iterator&
+ operator++()
+ {
+ this->_M_incr();
+ return *this;
+ }
+
+ _Hashtable_const_local_iterator
+ operator++(int)
+ {
+ _Hashtable_const_local_iterator __tmp(*this);
+ this->_M_incr();
+ return __tmp;
+ }
+ };
+
+ template<typename _NodePtr, typename _Key, typename _Value,
+ typename _ExtractKey, typename _Hash,
+ typename _RangeHash, typename _Unused,
+ bool __constant_iterators, bool __hash_cached>
+ using __local_iterator = typename std::conditional<
+ std::is_pointer<_NodePtr>::value,
+ _Local_iterator<_Key, _Value,
+ _ExtractKey, _Hash, _RangeHash, _Unused,
+ __constant_iterators, __hash_cached>,
+ _Hashtable_local_iterator<_Key, _NodePtr,
+ _ExtractKey, _Hash, _RangeHash, _Unused,
+ __constant_iterators,
+ __hash_cached>>::type;
+
+ template<typename _NodePtr, typename _Key, typename _Value,
+ typename _ExtractKey, typename _Hash,
+ typename _RangeHash, typename _Unused,
+ bool __constant_iterators, bool __hash_cached>
+ using __const_local_iterator = typename std::conditional<
+ std::is_pointer<_NodePtr>::value,
+ _Local_const_iterator<_Key, _Value,
+ _ExtractKey, _Hash, _RangeHash, _Unused,
+ __constant_iterators, __hash_cached>,
+ _Hashtable_const_local_iterator<_Key, _NodePtr,
+ _ExtractKey, _Hash, _RangeHash, _Unused,
+ __constant_iterators,
+ __hash_cached>>::type;
+
/**
* Primary class template _Hashtable_base.
*
@@ -1943,10 +2424,16 @@ namespace __detail
using __ebo_node_alloc = _Hashtable_ebo_helper<0, _NodeAlloc>;
template<typename>
- struct __get_value_type;
+ struct __get_node_base;
template<typename _Val, bool _Cache_hash_code>
- struct __get_value_type<_Hash_node<_Val, _Cache_hash_code>>
- { using type = _Val; };
+ struct __get_node_base<_Hash_node<_Val, _Cache_hash_code>>
+ { using type = _Hash_node_base; };
+ template<typename _ValuePtr, bool _Cache_hash_code>
+ struct __get_node_base<_Hash_pnode<_ValuePtr, _Cache_hash_code>>
+ {
+ using type = _Hash_pnode_base<__ptr_rebind<
+ _ValuePtr, _Hash_pnode<_ValuePtr, _Cache_hash_code>>>;
+ };
public:
using __node_type = typename _NodeAlloc::value_type;
@@ -1954,16 +2441,13 @@ namespace __detail
// 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 __node_ptr = typename __node_alloc_traits::pointer;
+ using __node_base = typename __get_node_base<__node_type>::type;
+ using __node_base_ptr = __ptr_rebind<__node_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 __buckets_ptr = typename __buckets_alloc_traits::pointer;
_Hashtable_alloc() = default;
_Hashtable_alloc(const _Hashtable_alloc&) = default;
@@ -2017,17 +2501,16 @@ namespace __detail
{
auto& __alloc = _M_node_allocator();
auto __nptr = __node_alloc_traits::allocate(__alloc, 1);
- __node_ptr __n = std::__to_address(__nptr);
__try
{
- ::new ((void*)__n) __node_type;
- __node_alloc_traits::construct(__alloc, __n->_M_valptr(),
+ __node_alloc_traits::construct(__alloc, std::__to_address(__nptr));
+ __node_alloc_traits::construct(__alloc, __nptr->_M_valptr(),
std::forward<_Args>(__args)...);
- return __n;
+ return __nptr;
}
__catch(...)
{
- __n->~__node_type();
+ __node_alloc_traits::destroy(__alloc, std::__to_address(__nptr));
__node_alloc_traits::deallocate(__alloc, __nptr, 1);
__throw_exception_again;
}
@@ -2045,10 +2528,9 @@ namespace __detail
void
_Hashtable_alloc<_NodeAlloc>::_M_deallocate_node_ptr(__node_ptr __n)
{
- typedef typename __node_alloc_traits::pointer _Ptr;
- 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();
+ __node_alloc_traits::destroy(__alloc, std::__to_address(__n));
+ __node_alloc_traits::deallocate(__alloc, __n, 1);
}
template<typename _NodeAlloc>
@@ -2069,11 +2551,9 @@ namespace __detail
-> __buckets_ptr
{
__buckets_alloc_type __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;
+ std::__uninitialized_default_n(__ptr, __bkt_count);
+ return __ptr;
}
template<typename _NodeAlloc>
@@ -2082,10 +2562,9 @@ namespace __detail
_M_deallocate_buckets(__buckets_ptr __bkts,
std::size_t __bkt_count)
{
- typedef typename __buckets_alloc_traits::pointer _Ptr;
- auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__bkts);
__buckets_alloc_type __alloc(_M_node_allocator());
- __buckets_alloc_traits::deallocate(__alloc, __ptr, __bkt_count);
+ std::_Destroy_n(__bkts, __bkt_count);
+ __buckets_alloc_traits::deallocate(__alloc, __bkts, __bkt_count);
}
///@} hashtable-detail
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_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_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_set/allocator/ext_ptr.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/allocator/ext_ptr.cc
index afcc58e39f4..2c1bbe9ad3e 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
@@ -1,24 +1,4 @@
-// Copyright (C) 2013-2024 Free Software Foundation, Inc.
-//
-// This file is part of the GNU ISO C++ Library. This library is free
-// software; you can redistribute it and/or modify it under the
-// terms of the GNU General Public License as published by the
-// Free Software Foundation; either version 3, or (at your option)
-// any later version.
-
-// This library is distributed in the hope that it will be useful,
-// but WITHOUT ANY WARRANTY; without even the implied warranty of
-// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-// GNU General Public License for more details.
-
-// You should have received a copy of the GNU General Public License along
-// 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>
@@ -26,15 +6,22 @@
#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; }
+
+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> { };
+
+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()
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] _Hashtable fancy pointer support
2024-06-26 20:38 [PATCH] _Hashtable fancy pointer support François Dumont
@ 2024-06-26 21:41 ` Jonathan Wakely
2024-06-27 19:25 ` François Dumont
0 siblings, 1 reply; 5+ messages in thread
From: Jonathan Wakely @ 2024-06-26 21:41 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
On Wed, 26 Jun 2024 at 21:39, François Dumont <frs.dumont@gmail.com> wrote:
>
> Hi
>
> Here is my proposal to add support for fancy allocator pointer.
>
> The only place where we still have C pointers is at the
> iterator::pointer level but it's consistent with std::list
> implementation and also logical considering that we do not get
> value_type pointers from the allocator.
>
> I also wondered if it was ok to use nullptr in different places or if I
> should rather do __node_ptr{}. But recent modifications are using
> nullptr so I think it's fine.
I haven't reviewed the patch yet, but this answers the nullptr question:
https://en.cppreference.com/w/cpp/named_req/NullablePointer
(aka Cpp17NullablePointer in the C++ standard).
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] _Hashtable fancy pointer support
2024-06-26 21:41 ` Jonathan Wakely
@ 2024-06-27 19:25 ` François Dumont
2024-06-27 20:30 ` Jonathan Wakely
0 siblings, 1 reply; 5+ messages in thread
From: François Dumont @ 2024-06-27 19:25 UTC (permalink / raw)
To: Jonathan Wakely; +Cc: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 909 bytes --]
Thanks for the link, based on it I removed some of the nullptr usages
keeping only assignments.
François
On 26/06/2024 23:41, Jonathan Wakely wrote:
> On Wed, 26 Jun 2024 at 21:39, François Dumont <frs.dumont@gmail.com> wrote:
>> Hi
>>
>> Here is my proposal to add support for fancy allocator pointer.
>>
>> The only place where we still have C pointers is at the
>> iterator::pointer level but it's consistent with std::list
>> implementation and also logical considering that we do not get
>> value_type pointers from the allocator.
>>
>> I also wondered if it was ok to use nullptr in different places or if I
>> should rather do __node_ptr{}. But recent modifications are using
>> nullptr so I think it's fine.
> I haven't reviewed the patch yet, but this answers the nullptr question:
> https://en.cppreference.com/w/cpp/named_req/NullablePointer
> (aka Cpp17NullablePointer in the C++ standard).
>
[-- Attachment #2: hashtable_cust_ptr_patch.txt --]
[-- Type: text/plain, Size: 48335 bytes --]
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 361da2b3b4d..845792f7ba9 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -200,8 +200,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_RehashPolicy, _Traits>,
private __detail::_Hashtable_alloc<
__alloc_rebind<_Alloc,
- __detail::_Hash_node<_Value,
- _Traits::__hash_cached::value>>>,
+ __detail::__get_node_type<_Alloc, _Value,
+ _Traits::__hash_cached::value>>>,
private _Hashtable_enable_default_ctor<_Equal, _Hash, _Alloc>
{
static_assert(is_same<typename remove_cv<_Value>::type, _Value>::value,
@@ -216,21 +216,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
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_type = __detail::__get_node_type<_Alloc, _Value,
+ _Traits::__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 __value_alloc_traits =
+ typename __node_alloc_traits::template rebind_traits<_Value>;
using __node_base = typename __hashtable_alloc::__node_base;
using __node_base_ptr = typename __hashtable_alloc::__node_base_ptr;
+ using __node_base_ptr_traits = std::pointer_traits<__node_base_ptr>;
using __buckets_ptr = typename __hashtable_alloc::__buckets_ptr;
+ using __buckets_ptr_traits = std::pointer_traits<__buckets_ptr>;
using __insert_base = __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey,
_Equal, _Hash,
@@ -258,15 +260,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
using const_iterator = typename __insert_base::const_iterator;
- using local_iterator = __detail::_Local_iterator<key_type, _Value,
- _ExtractKey, _Hash, _RangeHash, _Unused,
- __constant_iterators::value,
- __hash_cached::value>;
+ using local_iterator = __detail::__local_iterator<
+ __node_ptr, key_type, value_type,
+ _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 const_local_iterator = __detail::__const_local_iterator<
+ __node_ptr, key_type, value_type,
+ _ExtractKey, _Hash, _RangeHash, _Unused,
+ __constant_iterators::value, __hash_cached::value>;
private:
using __rehash_type = _RehashPolicy;
@@ -392,7 +394,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
#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;
size_type _M_element_count = 0;
@@ -406,11 +409,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// numerous checks in the code to avoid 0 modulus.
__node_base_ptr _M_single_bucket = nullptr;
+ __buckets_ptr
+ _M_single_bucket_ptr()
+ { return __buckets_ptr_traits::pointer_to(_M_single_bucket); }
+
+ __node_base_ptr
+ _M_before_begin_ptr()
+ { return __node_base_ptr_traits::pointer_to(_M_before_begin); }
+
void
_M_update_bbegin()
{
if (auto __begin = _M_begin())
- _M_buckets[_M_bucket_index(*__begin)] = &_M_before_begin;
+ _M_buckets[_M_bucket_index(*__begin)] = _M_before_begin_ptr();
}
void
@@ -422,7 +433,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
bool
_M_uses_single_bucket(__buckets_ptr __bkts) const
- { return __builtin_expect(__bkts == &_M_single_bucket, false); }
+ {
+ return __builtin_expect
+ (std::__to_address(__bkts) == std::addressof(_M_single_bucket),
+ false);
+ }
bool
_M_uses_single_bucket() const
@@ -444,7 +459,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
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);
@@ -463,18 +478,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_deallocate_buckets()
{ _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
+ static __node_ptr
+ _S_cast(__node_ptr __n)
+ { return __n; }
+
+ static __node_ptr
+ _S_cast(__detail::_Hash_node_base* __n)
+ { return static_cast<__node_ptr>(__n); }
+
// 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_base_ptr __n = _M_buckets[__bkt];
- return __n ? static_cast<__node_ptr>(__n->_M_nxt) : nullptr;
+ return __n ? _S_cast(__n->_M_nxt) : __node_ptr{};
}
__node_ptr
_M_begin() const
- { return static_cast<__node_ptr>(_M_before_begin._M_nxt); }
+ { return _S_cast(_M_before_begin._M_nxt); }
// Assign *this using another _Hashtable instance. Whether elements
// are copied or moved depends on the _Ht reference.
@@ -824,8 +847,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
__node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c);
if (__before_n)
- return static_cast<__node_ptr>(__before_n->_M_nxt);
- return nullptr;
+ return _S_cast(__before_n->_M_nxt);
+ return __node_ptr{};
}
template<typename _Kt>
@@ -835,8 +858,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
auto __before_n = _M_find_before_node_tr(__bkt, __key, __c);
if (__before_n)
- return static_cast<__node_ptr>(__before_n->_M_nxt);
- return nullptr;
+ return _S_cast(__before_n->_M_nxt);
+ return __node_ptr{};
}
// Insert a node at the beginning of a bucket.
@@ -863,7 +886,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// _M_before_begin.
_M_buckets[_M_bucket_index(*__node->_M_next())] = __node;
- _M_buckets[__bkt] = &_M_before_begin;
+ _M_buckets[__bkt] = _M_before_begin_ptr();
}
}
@@ -1051,7 +1074,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
__glibcxx_assert(get_allocator() == __nh.get_allocator());
- __node_ptr __n = nullptr;
+ __node_ptr __n{};
const key_type& __k = __nh._M_key();
const size_type __size = size();
if (__size <= __small_size_threshold())
@@ -1109,7 +1132,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
node_type
_M_extract_node(size_t __bkt, __node_base_ptr __prev_n)
{
- __node_ptr __n = static_cast<__node_ptr>(__prev_n->_M_nxt);
+ __node_ptr __n = _S_cast(__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);
@@ -1157,7 +1180,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
node_type __nh;
__hash_code __code = this->_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 (auto __prev_node = _M_find_before_node(__bkt, __k, __code))
__nh = _M_extract_node(__bkt, __prev_node);
return __nh;
}
@@ -1199,7 +1222,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
= _M_src_hash_code(__src.hash_function(), __k, *__pos._M_cur);
size_type __bkt = _M_bucket_index(__code);
if (__size <= __small_size_threshold()
- || _M_find_node(__bkt, __k, __code) == nullptr)
+ || !_M_find_node(__bkt, __k, __code))
{
auto __nh = __src.extract(__pos);
_M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);
@@ -1220,7 +1243,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
node_type>, "Node types are compatible");
__glibcxx_assert(get_allocator() == __src.get_allocator());
- __node_ptr __hint = nullptr;
+ __node_ptr __hint{};
this->reserve(size() + __src.size());
for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
{
@@ -1368,7 +1391,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_assign_elements(_Ht&& __ht)
{
- __buckets_ptr __former_buckets = nullptr;
+ __buckets_ptr __former_buckets{};
std::size_t __former_bucket_count = _M_bucket_count;
__rehash_guard_t __rehash_guard(_M_rehash_policy);
@@ -1417,7 +1440,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_assign(_Ht&& __ht, const _NodeGenerator& __node_gen)
{
- __buckets_ptr __buckets = nullptr;
+ __buckets_ptr __buckets{};
if (!_M_buckets)
_M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
@@ -1468,7 +1491,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;
}
@@ -1493,7 +1516,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;
}
@@ -1571,7 +1594,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;
}
@@ -1624,7 +1647,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
@@ -1694,13 +1717,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);
@@ -1947,7 +1970,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
if (size() <= __small_size_threshold())
{
- __node_ptr __n, __beg = nullptr;
+ __node_ptr __n, __beg{};
for (__n = _M_begin(); __n; __n = __n->_M_next())
{
if (this->_M_key_equals_tr(__k, *__n))
@@ -1991,7 +2014,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
if (size() <= __small_size_threshold())
{
- __node_ptr __n, __beg = nullptr;
+ __node_ptr __n, __beg{};
for (__n = _M_begin(); __n; __n = __n->_M_next())
{
if (this->_M_key_equals_tr(__k, *__n))
@@ -2035,12 +2058,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_find_before_node(const key_type& __k)
-> __node_base_ptr
{
- __node_base_ptr __prev_p = &_M_before_begin;
+ __node_base_ptr __prev_p = _M_before_begin_ptr();
if (!__prev_p->_M_nxt)
- return nullptr;
+ return {};
- for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);
- __p != nullptr;
+ for (__node_ptr __p = _S_cast(__prev_p->_M_nxt); __p;
__p = __p->_M_next())
{
if (this->_M_key_equals(__k, *__p))
@@ -2049,7 +2071,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__prev_p = __p;
}
- return nullptr;
+ return {};
}
// Find the node before the one whose key compares equal to k in the bucket
@@ -2067,10 +2089,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
__node_base_ptr __prev_p = _M_buckets[__bkt];
if (!__prev_p)
- return nullptr;
+ return {};
- for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);;
- __p = __p->_M_next())
+ for (__node_ptr __p = _S_cast(__prev_p->_M_nxt);; __p = __p->_M_next())
{
if (this->_M_equals(__k, __code, *__p))
return __prev_p;
@@ -2080,7 +2101,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__prev_p = __p;
}
- return nullptr;
+ return {};
}
template<typename _Key, typename _Value, typename _Alloc,
@@ -2097,10 +2118,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
__node_base_ptr __prev_p = _M_buckets[__bkt];
if (!__prev_p)
- return nullptr;
+ return {};
- for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);;
- __p = __p->_M_next())
+ for (__node_ptr __p = _S_cast(__prev_p->_M_nxt);; __p = __p->_M_next())
{
if (this->_M_equals_tr(__k, __code, *__p))
return __prev_p;
@@ -2110,7 +2130,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__prev_p = __p;
}
- return nullptr;
+ return {};
}
template<typename _Key, typename _Value, typename _Alloc,
@@ -2273,10 +2293,11 @@ _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 __hint_base = __hint;
__node_base_ptr __prev
- = __builtin_expect(__hint != nullptr, false)
+ = __builtin_expect(__hint ? 1 : 0, 0)
&& this->_M_equals(__k, __code, *__hint)
- ? __hint
+ ? __hint_base
: _M_find_before_node(__bkt, __k, __code);
if (__prev)
@@ -2437,7 +2458,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return 0;
// We found a matching node, erase it.
- __n = static_cast<__node_ptr>(__prev_n->_M_nxt);
+ __n = _S_cast(__prev_n->_M_nxt);
__bkt = _M_bucket_index(*__n);
}
else
@@ -2451,7 +2472,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return 0;
// We found a matching node, erase it.
- __n = static_cast<__node_ptr>(__prev_n->_M_nxt);
+ __n = _S_cast(__prev_n->_M_nxt);
}
_M_erase(__bkt, __prev_n, __n);
@@ -2478,7 +2499,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return 0;
// We found a matching node, erase it.
- __n = static_cast<__node_ptr>(__prev_n->_M_nxt);
+ __n = _S_cast(__prev_n->_M_nxt);
__bkt = _M_bucket_index(*__n);
}
else
@@ -2491,7 +2512,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (!__prev_n)
return 0;
- __n = static_cast<__node_ptr>(__prev_n->_M_nxt);
+ __n = _S_cast(__prev_n->_M_nxt);
}
// _GLIBCXX_RESOLVE_LIB_DEFECTS
@@ -2633,7 +2654,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_ptr();
if (__p->_M_nxt)
__new_buckets[__bbegin_bkt] = __p;
__bbegin_bkt = __bkt;
@@ -2668,7 +2689,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_before_begin._M_nxt = nullptr;
std::size_t __bbegin_bkt = 0;
std::size_t __prev_bkt = 0;
- __node_ptr __prev_p = nullptr;
+ __node_ptr __prev_p{};
bool __check_bucket = false;
while (__p)
@@ -2713,7 +2734,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_ptr();
if (__p->_M_nxt)
__new_buckets[__bbegin_bkt] = __p;
__bbegin_bkt = __bkt;
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 26def24f24e..225381ccb72 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -33,8 +33,9 @@
#include <tuple> // for std::tuple, std::forward_as_tuple
#include <bits/functional_hash.h> // for __is_fast_hash
-#include <bits/stl_algobase.h> // for std::min, std::is_permutation.
+#include <bits/stl_algobase.h> // for std::min, std::is_permutation
#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
@@ -82,6 +83,11 @@ namespace __detail
{ return __distance_fw(__first, __last,
std::__iterator_category(__first)); }
+ template<typename _Alloc, typename _Value>
+ using __alloc_val_ptr =
+ typename std::allocator_traits<__alloc_rebind<_Alloc,
+ _Value>>::pointer;
+
struct _Identity
{
template<typename _Tp>
@@ -321,6 +327,28 @@ namespace __detail
_Hash_node_base(_Hash_node_base* __next) noexcept : _M_nxt(__next) { }
};
+ /**
+ * struct _Hash_pnode_base
+ *
+ * Like _Hash_node_base but used in case of custom pointer type defined by the
+ * allocator.
+ */
+ template<typename _NodePtr>
+ struct _Hash_pnode_base
+ {
+ using __node_ptr = _NodePtr;
+
+ __node_ptr _M_nxt;
+
+ _Hash_pnode_base()
+ noexcept(std::is_nothrow_default_constructible<__node_ptr>::value)
+ : _M_nxt() { }
+
+ _Hash_pnode_base(__node_ptr __next)
+ noexcept(std::is_nothrow_copy_constructible<__node_ptr>::value)
+ : _M_nxt(__next) { }
+ };
+
/**
* struct _Hash_node_value_base
*
@@ -356,18 +384,23 @@ namespace __detail
/**
* Primary template struct _Hash_node_code_cache.
+ *
+ * No cache.
*/
template<bool _Cache_hash_code>
struct _Hash_node_code_cache
{ };
/**
- * Specialization for node with cache, struct _Hash_node_code_cache.
+ * Specialization for node with cache.
*/
template<>
struct _Hash_node_code_cache<true>
{ std::size_t _M_hash_code; };
+ /**
+ * Node with value and optionally a cache for the hash code.
+ */
template<typename _Value, bool _Cache_hash_code>
struct _Hash_node_value
: _Hash_node_value_base<_Value>
@@ -375,28 +408,64 @@ namespace __detail
{ };
/**
- * Primary template struct _Hash_node.
+ * struct _Hash_node.
+ *
+ * The node definition when the allocator is using raw pointers.
*/
template<typename _Value, bool _Cache_hash_code>
struct _Hash_node
: _Hash_node_base
, _Hash_node_value<_Value, _Cache_hash_code>
{
- _Hash_node*
+ using __node_ptr = _Hash_node*;
+ using __node_type = _Hash_node;
+
+ __node_ptr
+ _M_next() const noexcept
+ { return static_cast<__node_ptr>(this->_M_nxt); }
+ };
+
+ /**
+ * struct _Hash_pnode.
+ *
+ * The node definition used when the allocator define a custom pointer type.
+ */
+ template<typename _ValuePtr, bool _Cache_hash_code>
+ struct _Hash_pnode
+ : _Hash_pnode_base<__ptr_rebind<
+ _ValuePtr, _Hash_pnode<_ValuePtr, _Cache_hash_code>>>
+ , _Hash_node_value<
+ typename std::pointer_traits<_ValuePtr>::element_type, _Cache_hash_code>
+ {
+ using __node_ptr = __ptr_rebind<
+ _ValuePtr, _Hash_pnode<_ValuePtr, _Cache_hash_code>>;
+ using __node_type =
+ typename std::pointer_traits<__node_ptr>::element_type;
+ typedef typename std::pointer_traits<__node_ptr>::difference_type
+ difference_type;
+
+ __node_ptr
_M_next() const noexcept
- { return static_cast<_Hash_node*>(this->_M_nxt); }
+ { return this->_M_nxt; }
};
+ template<typename _Alloc, typename _Value, bool __hash_cached>
+ using __get_node_type = typename std::conditional<
+ std::is_pointer<__alloc_val_ptr<_Alloc, _Value>>::value,
+ _Hash_node<_Value, __hash_cached>,
+ _Hash_pnode<__alloc_val_ptr<_Alloc, _Value>, __hash_cached>>::type;
+
/// Base class for node iterators.
- template<typename _Value, bool _Cache_hash_code>
- struct _Node_iterator_base
+ template<typename _NodePtr>
+ struct _Hashtable_iterator_base
{
- using __node_type = _Hash_node<_Value, _Cache_hash_code>;
+ using __node_ptr = _NodePtr;
+ using __node_type = typename std::pointer_traits<_NodePtr>::element_type;
- __node_type* _M_cur;
+ __node_ptr _M_cur;
- _Node_iterator_base() : _M_cur(nullptr) { }
- _Node_iterator_base(__node_type* __p) noexcept
+ _Hashtable_iterator_base() : _M_cur() { }
+ _Hashtable_iterator_base(__node_ptr __p) noexcept
: _M_cur(__p) { }
void
@@ -404,18 +473,33 @@ namespace __detail
{ _M_cur = _M_cur->_M_next(); }
friend bool
- operator==(const _Node_iterator_base& __x, const _Node_iterator_base& __y)
- noexcept
+ operator==(const _Hashtable_iterator_base& __x,
+ const _Hashtable_iterator_base& __y) noexcept
{ return __x._M_cur == __y._M_cur; }
#if __cpp_impl_three_way_comparison < 201907L
friend bool
- operator!=(const _Node_iterator_base& __x, const _Node_iterator_base& __y)
- noexcept
+ operator!=(const _Hashtable_iterator_base& __x,
+ const _Hashtable_iterator_base& __y) noexcept
{ return __x._M_cur != __y._M_cur; }
#endif
};
+ /// Base class for node iterators.
+ template<typename _Value, bool _Cache_hash_code>
+ struct _Node_iterator_base
+ : _Hashtable_iterator_base<_Hash_node<_Value, _Cache_hash_code>*>
+ {
+ using __base_type =
+ _Hashtable_iterator_base<_Hash_node<_Value, _Cache_hash_code>*>;
+ using __node_ptr = typename __base_type::__node_ptr;
+ using __node_type = typename __base_type::__node_ptr;
+
+ _Node_iterator_base() = default;
+ _Node_iterator_base(__node_ptr __p) noexcept
+ : __base_type(__p) { }
+ };
+
/// Node iterators, used to iterate through all the hashtable.
template<typename _Value, bool __constant_iterators, bool __cache>
struct _Node_iterator
@@ -424,6 +508,7 @@ namespace __detail
private:
using __base_type = _Node_iterator_base<_Value, __cache>;
using __node_type = typename __base_type::__node_type;
+ using __node_ptr = typename __base_type::__node_ptr;
public:
using value_type = _Value;
@@ -439,7 +524,7 @@ namespace __detail
_Node_iterator() = default;
explicit
- _Node_iterator(__node_type* __p) noexcept
+ _Node_iterator(__node_ptr __p) noexcept
: __base_type(__p) { }
reference
@@ -474,6 +559,7 @@ namespace __detail
private:
using __base_type = _Node_iterator_base<_Value, __cache>;
using __node_type = typename __base_type::__node_type;
+ using __node_ptr = typename __base_type::__node_ptr;
public:
typedef _Value value_type;
@@ -486,7 +572,7 @@ namespace __detail
_Node_const_iterator() = default;
explicit
- _Node_const_iterator(__node_type* __p) noexcept
+ _Node_const_iterator(__node_ptr __p) noexcept
: __base_type(__p) { }
_Node_const_iterator(const _Node_iterator<_Value, __constant_iterators,
@@ -517,6 +603,110 @@ namespace __detail
}
};
+ /// Node iterators, used to iterate through all the hashtable.
+ template<typename _NodePtr, bool __constant_iterators>
+ struct _Hashtable_iterator
+ : public _Hashtable_iterator_base<_NodePtr>
+ {
+ private:
+ using __base_type = _Hashtable_iterator_base<_NodePtr>;
+ using __node_type = typename __base_type::__node_type;
+ using __node_ptr = typename __base_type::__node_ptr;
+
+ public:
+ typedef typename __node_type::value_type value_type;
+ typedef typename __node_type::difference_type difference_type;
+ typedef std::forward_iterator_tag iterator_category;
+
+ using pointer = typename std::conditional<__constant_iterators,
+ const value_type*, value_type*>::type;
+
+ using reference = typename std::conditional<__constant_iterators,
+ const value_type&, value_type&>::type;
+
+ _Hashtable_iterator() = default;
+
+ explicit
+ _Hashtable_iterator(__node_ptr __p) noexcept
+ : __base_type(__p) { }
+
+ reference
+ operator*() const noexcept
+ { return this->_M_cur->_M_v(); }
+
+ pointer
+ operator->() const noexcept
+ { return this->_M_cur->_M_valptr(); }
+
+ _Hashtable_iterator&
+ operator++() noexcept
+ {
+ this->_M_incr();
+ return *this;
+ }
+
+ _Hashtable_iterator
+ operator++(int) noexcept
+ {
+ _Hashtable_iterator __tmp(*this);
+ this->_M_incr();
+ return __tmp;
+ }
+ };
+
+ /// Node const_iterators, used to iterate through all the hashtable.
+ template<typename _NodePtr, bool __constant_iterators>
+ struct _Hashtable_const_iterator
+ : public _Hashtable_iterator_base<_NodePtr>
+ {
+ private:
+ using __base_type = _Hashtable_iterator_base<_NodePtr>;
+ using __node_type = typename __base_type::__node_type;
+ using __node_ptr = typename __base_type::__node_ptr;
+
+ public:
+ typedef typename __node_type::value_type value_type;
+ typedef typename __node_type::difference_type difference_type;
+ typedef std::forward_iterator_tag iterator_category;
+
+ typedef const value_type* pointer;
+ typedef const value_type& reference;
+
+ _Hashtable_const_iterator() = default;
+
+ explicit
+ _Hashtable_const_iterator(__node_ptr __p) noexcept
+ : __base_type(__p) { }
+
+ _Hashtable_const_iterator(
+ const _Hashtable_iterator<_NodePtr,
+ __constant_iterators>& __x) noexcept
+ : __base_type(__x._M_cur) { }
+
+ reference
+ operator*() const noexcept
+ { return this->_M_cur->_M_v(); }
+
+ pointer
+ operator->() const noexcept
+ { return this->_M_cur->_M_valptr(); }
+
+ _Hashtable_const_iterator&
+ operator++() noexcept
+ {
+ this->_M_incr();
+ return *this;
+ }
+
+ _Hashtable_const_iterator
+ operator++(int) noexcept
+ {
+ _Hashtable_const_iterator __tmp(*this);
+ this->_M_incr();
+ return __tmp;
+ }
+ };
+
// Many of class template _Hashtable's template parameters are policy
// classes. These are defaults for the policies.
@@ -912,16 +1102,16 @@ namespace __detail
using __hash_cached = typename _Traits::__hash_cached;
using __constant_iterators = typename _Traits::__constant_iterators;
+ using __alloc_ptr = __alloc_val_ptr<_Alloc, _Value>;
- using __hashtable_alloc = _Hashtable_alloc<
- __alloc_rebind<_Alloc, _Hash_node<_Value,
- __hash_cached::value>>>;
+ using __node_type = __get_node_type<_Alloc, _Value, __hash_cached::value>;
+ using __node_ptr = __ptr_rebind<__alloc_ptr, __node_type>;
+ using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
using value_type = typename __hashtable_base::value_type;
using size_type = typename __hashtable_base::size_type;
using __unique_keys = typename _Traits::__unique_keys;
- using __node_alloc_type = typename __hashtable_alloc::__node_alloc_type;
using __node_gen_type = _AllocNode<__node_alloc_type>;
__hashtable&
@@ -939,12 +1129,19 @@ namespace __detail
const _NodeGetter&, false_type __uks);
public:
- using iterator = _Node_iterator<_Value, __constant_iterators::value,
- __hash_cached::value>;
-
- using const_iterator = _Node_const_iterator<_Value,
- __constant_iterators::value,
- __hash_cached::value>;
+ using iterator =
+ typename std::conditional<std::is_pointer<__alloc_ptr>::value,
+ _Node_iterator<_Value,
+ __constant_iterators::value, __hash_cached::value>,
+ _Hashtable_iterator<__node_ptr,
+ __constant_iterators::value>>::type;
+
+ using const_iterator =
+ typename std::conditional<std::is_pointer<__alloc_ptr>::value,
+ _Node_const_iterator<_Value,
+ __constant_iterators::value, __hash_cached::value>,
+ _Hashtable_const_iterator<__node_ptr,
+ __constant_iterators::value>>::type;
using __ireturn_type = __conditional_t<__unique_keys::value,
std::pair<iterator, bool>,
@@ -1280,6 +1477,17 @@ namespace __detail
bool __cache_hash_code>
struct _Local_iterator_base;
+ /**
+ * Primary class template _Hashtable_local_iter_base.
+ *
+ * Base class for local iterators, used to iterate within a bucket
+ * but not between buckets.
+ */
+ template<typename _Key, typename _NodePtr, typename _ExtractKey,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ bool __cache_hash_code>
+ struct _Hashtable_local_iter_base;
+
/**
* Primary class template _Hash_code_base.
*
@@ -1440,6 +1648,49 @@ namespace __detail
_M_get_bucket() const { return _M_bucket; } // for debug mode
};
+ /// Partial specialization used when nodes contain a cached hash code.
+ template<typename _Key, typename _NodePtr, typename _ExtractKey,
+ typename _Hash, typename _RangeHash, typename _Unused>
+ struct _Hashtable_local_iter_base<_Key, _NodePtr, _ExtractKey,
+ _Hash, _RangeHash, _Unused, true>
+ : public _Hashtable_iterator_base<_NodePtr>
+ {
+ protected:
+ using __base_node_iter = _Hashtable_iterator_base<_NodePtr>;
+ using __node_ptr = typename __base_node_iter::__node_ptr;
+ using __node_type = typename __base_node_iter::__node_type;
+ using value_type = typename __node_type::value_type;
+ using __hash_code_base = _Hash_code_base<_Key, value_type, _ExtractKey,
+ _Hash, _RangeHash, _Unused, true>;
+
+ _Hashtable_local_iter_base() = default;
+ _Hashtable_local_iter_base(const __hash_code_base&,
+ __node_ptr __p,
+ std::size_t __bkt, std::size_t __bkt_count)
+ : __base_node_iter(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
+ { }
+
+ void
+ _M_incr()
+ {
+ __base_node_iter::_M_incr();
+ if (this->_M_cur)
+ {
+ std::size_t __bkt
+ = _RangeHash{}(this->_M_cur->_M_hash_code, _M_bucket_count);
+ if (__bkt != _M_bucket)
+ this->_M_cur = nullptr;
+ }
+ }
+
+ std::size_t _M_bucket;
+ std::size_t _M_bucket_count;
+
+ public:
+ std::size_t
+ _M_get_bucket() const { return _M_bucket; } // for debug mode
+ };
+
// Uninitialized storage for a _Hash_code_base.
// This type is DefaultConstructible and Assignable even if the
// _Hash_code_base type isn't, so that _Local_iterator_base<..., false>
@@ -1554,6 +1805,86 @@ namespace __detail
_M_get_bucket() const { return _M_bucket; } // for debug mode
};
+ // Partial specialization used when hash codes are not cached
+ template<typename _Key, typename _NodePtr, typename _ExtractKey,
+ typename _Hash, typename _RangeHash, typename _Unused>
+ struct _Hashtable_local_iter_base<_Key, _NodePtr, _ExtractKey,
+ _Hash, _RangeHash, _Unused, false>
+ : _Hash_code_storage<_Hash>
+ , _Hashtable_iterator_base<_NodePtr>
+ {
+ protected:
+ using __node_iter_base = _Hashtable_iterator_base<_NodePtr>;
+ using __node_type = typename __node_iter_base::__node_type;
+ using __node_ptr = typename __node_iter_base::__node_ptr;
+ using value_type = typename __node_type::value_type;
+ using __hash_code_base = _Hash_code_base<_Key, value_type, _ExtractKey,
+ _Hash, _RangeHash, _Unused, false>;
+
+ _Hashtable_local_iter_base() : _M_bucket_count(-1) { }
+
+ _Hashtable_local_iter_base(const __hash_code_base& __base,
+ __node_ptr __p,
+ std::size_t __bkt, std::size_t __bkt_count)
+ : __node_iter_base(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
+ { _M_init(__base.hash_function()); }
+
+ ~_Hashtable_local_iter_base()
+ {
+ if (_M_bucket_count != -1)
+ _M_destroy();
+ }
+
+ _Hashtable_local_iter_base(const _Hashtable_local_iter_base& __iter)
+ : __node_iter_base(__iter._M_cur), _M_bucket(__iter._M_bucket)
+ , _M_bucket_count(__iter._M_bucket_count)
+ {
+ if (_M_bucket_count != -1)
+ _M_init(*__iter._M_h());
+ }
+
+ _Hashtable_local_iter_base&
+ operator=(const _Hashtable_local_iter_base& __iter)
+ {
+ if (_M_bucket_count != -1)
+ _M_destroy();
+ this->_M_cur = __iter._M_cur;
+ _M_bucket = __iter._M_bucket;
+ _M_bucket_count = __iter._M_bucket_count;
+ if (_M_bucket_count != -1)
+ _M_init(*__iter._M_h());
+ return *this;
+ }
+
+ void
+ _M_incr()
+ {
+ __node_iter_base::_M_incr();
+ if (this->_M_cur)
+ {
+ std::size_t __bkt =
+ _RangeHash{}((*this->_M_h())(_ExtractKey{}(this->_M_cur->_M_v())),
+ _M_bucket_count);
+ if (__bkt != _M_bucket)
+ this->_M_cur = nullptr;
+ }
+ }
+
+ std::size_t _M_bucket;
+ std::size_t _M_bucket_count;
+
+ void
+ _M_init(const _Hash& __h)
+ { ::new(this->_M_h()) _Hash(__h); }
+
+ void
+ _M_destroy() { this->_M_h()->~_Hash(); }
+
+ public:
+ std::size_t
+ _M_get_bucket() const { return _M_bucket; } // for debug mode
+ };
+
/// local iterators
template<typename _Key, typename _Value, typename _ExtractKey,
typename _Hash, typename _RangeHash, typename _Unused,
@@ -1667,6 +1998,156 @@ namespace __detail
}
};
+ /// local iterators
+ template<typename _Key, typename _NodePtr, typename _ExtractKey,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ bool __constant_iterators, bool __cache>
+ struct _Hashtable_local_iterator
+ : public _Hashtable_local_iter_base<_Key, _NodePtr, _ExtractKey,
+ _Hash, _RangeHash, _Unused, __cache>
+ {
+ private:
+ using __base_type =
+ _Hashtable_local_iter_base<_Key, _NodePtr, _ExtractKey,
+ _Hash, _RangeHash, _Unused, __cache>;
+ using __hash_code_base = typename __base_type::__hash_code_base;
+ using __node_type = typename __base_type::__node_type;
+ using __node_ptr = typename __base_type::__node_ptr;
+
+ public:
+ typedef typename __base_type::value_type value_type;
+ typedef typename std::conditional<__constant_iterators,
+ const value_type*, value_type*>::type
+ pointer;
+ typedef typename std::conditional<__constant_iterators,
+ const value_type&, value_type&>::type
+ reference;
+ typedef typename __node_type::difference_type difference_type;
+ typedef std::forward_iterator_tag iterator_category;
+
+ _Hashtable_local_iterator() = default;
+
+ _Hashtable_local_iterator(const __hash_code_base& __base,
+ __node_ptr __n,
+ std::size_t __bkt, std::size_t __bkt_count)
+ : __base_type(__base, __n, __bkt, __bkt_count)
+ { }
+
+ reference
+ operator*() const
+ { return this->_M_cur->_M_v(); }
+
+ pointer
+ operator->() const
+ { return this->_M_cur->_M_valptr(); }
+
+ _Hashtable_local_iterator&
+ operator++()
+ {
+ this->_M_incr();
+ return *this;
+ }
+
+ _Hashtable_local_iterator
+ operator++(int)
+ {
+ _Hashtable_local_iterator __tmp(*this);
+ this->_M_incr();
+ return __tmp;
+ }
+ };
+
+ /// local const_iterators
+ template<typename _Key, typename _NodePtr, typename _ExtractKey,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ bool __constant_iterators, bool __cache>
+ struct _Hashtable_const_local_iterator
+ : public _Hashtable_local_iter_base<_Key, _NodePtr, _ExtractKey,
+ _Hash, _RangeHash, _Unused, __cache>
+ {
+ private:
+ using __base_type =
+ _Hashtable_local_iter_base<_Key, _NodePtr, _ExtractKey,
+ _Hash, _RangeHash, _Unused, __cache>;
+ using __hash_code_base = typename __base_type::__hash_code_base;
+ using __node_type = typename __base_type::__node_type;
+ using __node_ptr = typename __base_type::__node_ptr;
+
+ public:
+ typedef typename __base_type::value_type value_type;
+ typedef const value_type* pointer;
+ typedef const value_type& reference;
+ typedef typename __node_type::difference_type difference_type;
+ typedef std::forward_iterator_tag iterator_category;
+
+ _Hashtable_const_local_iterator() = default;
+
+ _Hashtable_const_local_iterator(const __hash_code_base& __base,
+ __node_ptr __n,
+ std::size_t __bkt, std::size_t __bkt_count)
+ : __base_type(__base, __n, __bkt, __bkt_count)
+ { }
+
+ _Hashtable_const_local_iterator(const _Hashtable_local_iterator<
+ _Key, _NodePtr, _ExtractKey,
+ _Hash, _RangeHash, _Unused,
+ __constant_iterators,
+ __cache>& __x)
+ : __base_type(__x)
+ { }
+
+ reference
+ operator*() const
+ { return this->_M_cur->_M_v(); }
+
+ pointer
+ operator->() const
+ { return this->_M_cur->_M_valptr(); }
+
+ _Hashtable_const_local_iterator&
+ operator++()
+ {
+ this->_M_incr();
+ return *this;
+ }
+
+ _Hashtable_const_local_iterator
+ operator++(int)
+ {
+ _Hashtable_const_local_iterator __tmp(*this);
+ this->_M_incr();
+ return __tmp;
+ }
+ };
+
+ template<typename _NodePtr, typename _Key, typename _Value,
+ typename _ExtractKey, typename _Hash,
+ typename _RangeHash, typename _Unused,
+ bool __constant_iterators, bool __hash_cached>
+ using __local_iterator = typename std::conditional<
+ std::is_pointer<_NodePtr>::value,
+ _Local_iterator<_Key, _Value,
+ _ExtractKey, _Hash, _RangeHash, _Unused,
+ __constant_iterators, __hash_cached>,
+ _Hashtable_local_iterator<_Key, _NodePtr,
+ _ExtractKey, _Hash, _RangeHash, _Unused,
+ __constant_iterators,
+ __hash_cached>>::type;
+
+ template<typename _NodePtr, typename _Key, typename _Value,
+ typename _ExtractKey, typename _Hash,
+ typename _RangeHash, typename _Unused,
+ bool __constant_iterators, bool __hash_cached>
+ using __const_local_iterator = typename std::conditional<
+ std::is_pointer<_NodePtr>::value,
+ _Local_const_iterator<_Key, _Value,
+ _ExtractKey, _Hash, _RangeHash, _Unused,
+ __constant_iterators, __hash_cached>,
+ _Hashtable_const_local_iterator<_Key, _NodePtr,
+ _ExtractKey, _Hash, _RangeHash, _Unused,
+ __constant_iterators,
+ __hash_cached>>::type;
+
/**
* Primary class template _Hashtable_base.
*
@@ -1943,10 +2424,16 @@ namespace __detail
using __ebo_node_alloc = _Hashtable_ebo_helper<0, _NodeAlloc>;
template<typename>
- struct __get_value_type;
+ struct __get_node_base;
template<typename _Val, bool _Cache_hash_code>
- struct __get_value_type<_Hash_node<_Val, _Cache_hash_code>>
- { using type = _Val; };
+ struct __get_node_base<_Hash_node<_Val, _Cache_hash_code>>
+ { using type = _Hash_node_base; };
+ template<typename _ValuePtr, bool _Cache_hash_code>
+ struct __get_node_base<_Hash_pnode<_ValuePtr, _Cache_hash_code>>
+ {
+ using type = _Hash_pnode_base<__ptr_rebind<
+ _ValuePtr, _Hash_pnode<_ValuePtr, _Cache_hash_code>>>;
+ };
public:
using __node_type = typename _NodeAlloc::value_type;
@@ -1954,16 +2441,13 @@ namespace __detail
// 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 __node_ptr = typename __node_alloc_traits::pointer;
+ using __node_base = typename __get_node_base<__node_type>::type;
+ using __node_base_ptr = __ptr_rebind<__node_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 __buckets_ptr = typename __buckets_alloc_traits::pointer;
_Hashtable_alloc() = default;
_Hashtable_alloc(const _Hashtable_alloc&) = default;
@@ -2017,17 +2501,16 @@ namespace __detail
{
auto& __alloc = _M_node_allocator();
auto __nptr = __node_alloc_traits::allocate(__alloc, 1);
- __node_ptr __n = std::__to_address(__nptr);
__try
{
- ::new ((void*)__n) __node_type;
- __node_alloc_traits::construct(__alloc, __n->_M_valptr(),
+ __node_alloc_traits::construct(__alloc, std::__to_address(__nptr));
+ __node_alloc_traits::construct(__alloc, __nptr->_M_valptr(),
std::forward<_Args>(__args)...);
- return __n;
+ return __nptr;
}
__catch(...)
{
- __n->~__node_type();
+ __node_alloc_traits::destroy(__alloc, std::__to_address(__nptr));
__node_alloc_traits::deallocate(__alloc, __nptr, 1);
__throw_exception_again;
}
@@ -2045,10 +2528,9 @@ namespace __detail
void
_Hashtable_alloc<_NodeAlloc>::_M_deallocate_node_ptr(__node_ptr __n)
{
- typedef typename __node_alloc_traits::pointer _Ptr;
- 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();
+ __node_alloc_traits::destroy(__alloc, std::__to_address(__n));
+ __node_alloc_traits::deallocate(__alloc, __n, 1);
}
template<typename _NodeAlloc>
@@ -2069,11 +2551,9 @@ namespace __detail
-> __buckets_ptr
{
__buckets_alloc_type __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;
+ std::__uninitialized_default_n(__ptr, __bkt_count);
+ return __ptr;
}
template<typename _NodeAlloc>
@@ -2082,10 +2562,9 @@ namespace __detail
_M_deallocate_buckets(__buckets_ptr __bkts,
std::size_t __bkt_count)
{
- typedef typename __buckets_alloc_traits::pointer _Ptr;
- auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__bkts);
__buckets_alloc_type __alloc(_M_node_allocator());
- __buckets_alloc_traits::deallocate(__alloc, __ptr, __bkt_count);
+ std::_Destroy_n(__bkts, __bkt_count);
+ __buckets_alloc_traits::deallocate(__alloc, __bkts, __bkt_count);
}
///@} hashtable-detail
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_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_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_set/allocator/ext_ptr.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/allocator/ext_ptr.cc
index afcc58e39f4..2c1bbe9ad3e 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
@@ -1,24 +1,4 @@
-// Copyright (C) 2013-2024 Free Software Foundation, Inc.
-//
-// This file is part of the GNU ISO C++ Library. This library is free
-// software; you can redistribute it and/or modify it under the
-// terms of the GNU General Public License as published by the
-// Free Software Foundation; either version 3, or (at your option)
-// any later version.
-
-// This library is distributed in the hope that it will be useful,
-// but WITHOUT ANY WARRANTY; without even the implied warranty of
-// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-// GNU General Public License for more details.
-
-// You should have received a copy of the GNU General Public License along
-// 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>
@@ -26,15 +6,22 @@
#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; }
+
+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> { };
+
+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()
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] _Hashtable fancy pointer support
2024-06-27 19:25 ` François Dumont
@ 2024-06-27 20:30 ` Jonathan Wakely
2024-06-29 14:02 ` François Dumont
0 siblings, 1 reply; 5+ messages in thread
From: Jonathan Wakely @ 2024-06-27 20:30 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
On Thu, 27 Jun 2024 at 20:25, François Dumont <frs.dumont@gmail.com> wrote:
>
> Thanks for the link, based on it I removed some of the nullptr usages
> keeping only assignments.
That's not necessary. A nullable pointer type is equality comparable
with nullptr_t, and nullptr can be implicitly converted to the pointer
type.
Your _S_case function is wrong though: you can't construct the fancy
pointer type from a raw pointer. You need to use
pointer_traits<__node_ptr>::pointer_to(*rawptr).
>
> François
>
> On 26/06/2024 23:41, Jonathan Wakely wrote:
> > On Wed, 26 Jun 2024 at 21:39, François Dumont <frs.dumont@gmail.com> wrote:
> >> Hi
> >>
> >> Here is my proposal to add support for fancy allocator pointer.
> >>
> >> The only place where we still have C pointers is at the
> >> iterator::pointer level but it's consistent with std::list
> >> implementation and also logical considering that we do not get
> >> value_type pointers from the allocator.
> >>
> >> I also wondered if it was ok to use nullptr in different places or if I
> >> should rather do __node_ptr{}. But recent modifications are using
> >> nullptr so I think it's fine.
> > I haven't reviewed the patch yet, but this answers the nullptr question:
> > https://en.cppreference.com/w/cpp/named_req/NullablePointer
> > (aka Cpp17NullablePointer in the C++ standard).
> >
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] _Hashtable fancy pointer support
2024-06-27 20:30 ` Jonathan Wakely
@ 2024-06-29 14:02 ` François Dumont
0 siblings, 0 replies; 5+ messages in thread
From: François Dumont @ 2024-06-29 14:02 UTC (permalink / raw)
To: Jonathan Wakely; +Cc: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1846 bytes --]
On 27/06/2024 22:30, Jonathan Wakely wrote:
> On Thu, 27 Jun 2024 at 20:25, François Dumont <frs.dumont@gmail.com> wrote:
>> Thanks for the link, based on it I removed some of the nullptr usages
>> keeping only assignments.
> That's not necessary. A nullable pointer type is equality comparable
> with nullptr_t, and nullptr can be implicitly converted to the pointer
> type.
Do you prefer that I fully rollback this part then ?
In this new version I restored some nullptr usages and kept the removals
only when avoiding the conversion without impacting code clarity. But
that's questionable of course, let me know.
>
> Your _S_case function is wrong though: you can't construct the fancy
> pointer type from a raw pointer. You need to use
> pointer_traits<__node_ptr>::pointer_to(*rawptr).
The _S_cast taking a __node_base* is only used when the allocator do not
define any fancy pointer.
In this new version I've added a comment on it and simply used
__node_base* for clarity.
>
>> François
>>
>> On 26/06/2024 23:41, Jonathan Wakely wrote:
>>> On Wed, 26 Jun 2024 at 21:39, François Dumont <frs.dumont@gmail.com> wrote:
>>>> Hi
>>>>
>>>> Here is my proposal to add support for fancy allocator pointer.
>>>>
>>>> The only place where we still have C pointers is at the
>>>> iterator::pointer level but it's consistent with std::list
>>>> implementation and also logical considering that we do not get
>>>> value_type pointers from the allocator.
>>>>
>>>> I also wondered if it was ok to use nullptr in different places or if I
>>>> should rather do __node_ptr{}. But recent modifications are using
>>>> nullptr so I think it's fine.
>>> I haven't reviewed the patch yet, but this answers the nullptr question:
>>> https://en.cppreference.com/w/cpp/named_req/NullablePointer
>>> (aka Cpp17NullablePointer in the C++ standard).
>>>
[-- Attachment #2: hashtable_cust_ptr_patch.txt --]
[-- Type: text/plain, Size: 47527 bytes --]
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 361da2b3b4d..474b5e7a96c 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -200,8 +200,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_RehashPolicy, _Traits>,
private __detail::_Hashtable_alloc<
__alloc_rebind<_Alloc,
- __detail::_Hash_node<_Value,
- _Traits::__hash_cached::value>>>,
+ __detail::__get_node_type<_Alloc, _Value,
+ _Traits::__hash_cached::value>>>,
private _Hashtable_enable_default_ctor<_Equal, _Hash, _Alloc>
{
static_assert(is_same<typename remove_cv<_Value>::type, _Value>::value,
@@ -216,21 +216,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
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_type = __detail::__get_node_type<_Alloc, _Value,
+ _Traits::__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 __value_alloc_traits =
+ typename __node_alloc_traits::template rebind_traits<_Value>;
using __node_base = typename __hashtable_alloc::__node_base;
using __node_base_ptr = typename __hashtable_alloc::__node_base_ptr;
+ using __node_base_ptr_traits = std::pointer_traits<__node_base_ptr>;
using __buckets_ptr = typename __hashtable_alloc::__buckets_ptr;
+ using __buckets_ptr_traits = std::pointer_traits<__buckets_ptr>;
using __insert_base = __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey,
_Equal, _Hash,
@@ -258,15 +260,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
using const_iterator = typename __insert_base::const_iterator;
- using local_iterator = __detail::_Local_iterator<key_type, _Value,
- _ExtractKey, _Hash, _RangeHash, _Unused,
- __constant_iterators::value,
- __hash_cached::value>;
+ using local_iterator = __detail::__local_iterator<
+ __node_ptr, key_type, value_type,
+ _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 const_local_iterator = __detail::__const_local_iterator<
+ __node_ptr, key_type, value_type,
+ _ExtractKey, _Hash, _RangeHash, _Unused,
+ __constant_iterators::value, __hash_cached::value>;
private:
using __rehash_type = _RehashPolicy;
@@ -392,7 +394,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
#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;
size_type _M_element_count = 0;
@@ -406,11 +409,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// numerous checks in the code to avoid 0 modulus.
__node_base_ptr _M_single_bucket = nullptr;
+ __buckets_ptr
+ _M_single_bucket_ptr()
+ { return __buckets_ptr_traits::pointer_to(_M_single_bucket); }
+
+ __node_base_ptr
+ _M_before_begin_ptr()
+ { return __node_base_ptr_traits::pointer_to(_M_before_begin); }
+
void
_M_update_bbegin()
{
if (auto __begin = _M_begin())
- _M_buckets[_M_bucket_index(*__begin)] = &_M_before_begin;
+ _M_buckets[_M_bucket_index(*__begin)] = _M_before_begin_ptr();
}
void
@@ -422,7 +433,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
bool
_M_uses_single_bucket(__buckets_ptr __bkts) const
- { return __builtin_expect(__bkts == &_M_single_bucket, false); }
+ {
+ return __builtin_expect
+ (std::__to_address(__bkts) == std::addressof(_M_single_bucket),
+ false);
+ }
bool
_M_uses_single_bucket() const
@@ -444,7 +459,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
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);
@@ -463,18 +478,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_deallocate_buckets()
{ _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
+ // Used in case of custom pointer type.
+ static __node_ptr
+ _S_cast(__node_ptr __n)
+ { return __n; }
+
+ // Used in case of raw C pointer type.
+ static __node_ptr
+ _S_cast(__node_base* __n)
+ { return static_cast<__node_ptr>(__n); }
+
// 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_base_ptr __n = _M_buckets[__bkt];
- return __n ? static_cast<__node_ptr>(__n->_M_nxt) : nullptr;
+ return __n ? _S_cast(__n->_M_nxt) : nullptr;
}
__node_ptr
_M_begin() const
- { return static_cast<__node_ptr>(_M_before_begin._M_nxt); }
+ { return _S_cast(_M_before_begin._M_nxt); }
// Assign *this using another _Hashtable instance. Whether elements
// are copied or moved depends on the _Ht reference.
@@ -824,7 +849,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
__node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c);
if (__before_n)
- return static_cast<__node_ptr>(__before_n->_M_nxt);
+ return _S_cast(__before_n->_M_nxt);
return nullptr;
}
@@ -835,7 +860,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
auto __before_n = _M_find_before_node_tr(__bkt, __key, __c);
if (__before_n)
- return static_cast<__node_ptr>(__before_n->_M_nxt);
+ return _S_cast(__before_n->_M_nxt);
return nullptr;
}
@@ -863,7 +888,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// _M_before_begin.
_M_buckets[_M_bucket_index(*__node->_M_next())] = __node;
- _M_buckets[__bkt] = &_M_before_begin;
+ _M_buckets[__bkt] = _M_before_begin_ptr();
}
}
@@ -1051,7 +1076,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
__glibcxx_assert(get_allocator() == __nh.get_allocator());
- __node_ptr __n = nullptr;
+ __node_ptr __n{};
const key_type& __k = __nh._M_key();
const size_type __size = size();
if (__size <= __small_size_threshold())
@@ -1109,7 +1134,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
node_type
_M_extract_node(size_t __bkt, __node_base_ptr __prev_n)
{
- __node_ptr __n = static_cast<__node_ptr>(__prev_n->_M_nxt);
+ __node_ptr __n = _S_cast(__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);
@@ -1157,7 +1182,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
node_type __nh;
__hash_code __code = this->_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 (auto __prev_node = _M_find_before_node(__bkt, __k, __code))
__nh = _M_extract_node(__bkt, __prev_node);
return __nh;
}
@@ -1199,7 +1224,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
= _M_src_hash_code(__src.hash_function(), __k, *__pos._M_cur);
size_type __bkt = _M_bucket_index(__code);
if (__size <= __small_size_threshold()
- || _M_find_node(__bkt, __k, __code) == nullptr)
+ || !_M_find_node(__bkt, __k, __code))
{
auto __nh = __src.extract(__pos);
_M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);
@@ -1220,7 +1245,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
node_type>, "Node types are compatible");
__glibcxx_assert(get_allocator() == __src.get_allocator());
- __node_ptr __hint = nullptr;
+ __node_ptr __hint{};
this->reserve(size() + __src.size());
for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
{
@@ -1368,7 +1393,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_assign_elements(_Ht&& __ht)
{
- __buckets_ptr __former_buckets = nullptr;
+ __buckets_ptr __former_buckets{};
std::size_t __former_bucket_count = _M_bucket_count;
__rehash_guard_t __rehash_guard(_M_rehash_policy);
@@ -1417,7 +1442,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_assign(_Ht&& __ht, const _NodeGenerator& __node_gen)
{
- __buckets_ptr __buckets = nullptr;
+ __buckets_ptr __buckets{};
if (!_M_buckets)
_M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
@@ -1468,7 +1493,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;
}
@@ -1493,7 +1518,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;
}
@@ -1571,7 +1596,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;
}
@@ -1624,7 +1649,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
@@ -1694,13 +1719,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);
@@ -1947,7 +1972,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
if (size() <= __small_size_threshold())
{
- __node_ptr __n, __beg = nullptr;
+ __node_ptr __n, __beg{};
for (__n = _M_begin(); __n; __n = __n->_M_next())
{
if (this->_M_key_equals_tr(__k, *__n))
@@ -1991,7 +2016,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
if (size() <= __small_size_threshold())
{
- __node_ptr __n, __beg = nullptr;
+ __node_ptr __n, __beg{};
for (__n = _M_begin(); __n; __n = __n->_M_next())
{
if (this->_M_key_equals_tr(__k, *__n))
@@ -2035,12 +2060,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_find_before_node(const key_type& __k)
-> __node_base_ptr
{
- __node_base_ptr __prev_p = &_M_before_begin;
+ __node_base_ptr __prev_p = _M_before_begin_ptr();
if (!__prev_p->_M_nxt)
return nullptr;
- for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);
- __p != nullptr;
+ for (__node_ptr __p = _S_cast(__prev_p->_M_nxt); __p;
__p = __p->_M_next())
{
if (this->_M_key_equals(__k, *__p))
@@ -2069,8 +2093,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (!__prev_p)
return nullptr;
- for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);;
- __p = __p->_M_next())
+ for (__node_ptr __p = _S_cast(__prev_p->_M_nxt);; __p = __p->_M_next())
{
if (this->_M_equals(__k, __code, *__p))
return __prev_p;
@@ -2099,8 +2122,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (!__prev_p)
return nullptr;
- for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);;
- __p = __p->_M_next())
+ for (__node_ptr __p = _S_cast(__prev_p->_M_nxt);; __p = __p->_M_next())
{
if (this->_M_equals_tr(__k, __code, *__p))
return __prev_p;
@@ -2273,10 +2295,11 @@ _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 __hint_base = __hint;
__node_base_ptr __prev
- = __builtin_expect(__hint != nullptr, false)
+ = __builtin_expect(__hint ? 1 : 0, 0)
&& this->_M_equals(__k, __code, *__hint)
- ? __hint
+ ? __hint_base
: _M_find_before_node(__bkt, __k, __code);
if (__prev)
@@ -2437,7 +2460,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return 0;
// We found a matching node, erase it.
- __n = static_cast<__node_ptr>(__prev_n->_M_nxt);
+ __n = _S_cast(__prev_n->_M_nxt);
__bkt = _M_bucket_index(*__n);
}
else
@@ -2451,7 +2474,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return 0;
// We found a matching node, erase it.
- __n = static_cast<__node_ptr>(__prev_n->_M_nxt);
+ __n = _S_cast(__prev_n->_M_nxt);
}
_M_erase(__bkt, __prev_n, __n);
@@ -2478,7 +2501,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return 0;
// We found a matching node, erase it.
- __n = static_cast<__node_ptr>(__prev_n->_M_nxt);
+ __n = _S_cast(__prev_n->_M_nxt);
__bkt = _M_bucket_index(*__n);
}
else
@@ -2491,7 +2514,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (!__prev_n)
return 0;
- __n = static_cast<__node_ptr>(__prev_n->_M_nxt);
+ __n = _S_cast(__prev_n->_M_nxt);
}
// _GLIBCXX_RESOLVE_LIB_DEFECTS
@@ -2633,7 +2656,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_ptr();
if (__p->_M_nxt)
__new_buckets[__bbegin_bkt] = __p;
__bbegin_bkt = __bkt;
@@ -2668,7 +2691,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_before_begin._M_nxt = nullptr;
std::size_t __bbegin_bkt = 0;
std::size_t __prev_bkt = 0;
- __node_ptr __prev_p = nullptr;
+ __node_ptr __prev_p{};
bool __check_bucket = false;
while (__p)
@@ -2713,7 +2736,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_ptr();
if (__p->_M_nxt)
__new_buckets[__bbegin_bkt] = __p;
__bbegin_bkt = __bkt;
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 26def24f24e..225381ccb72 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -33,8 +33,9 @@
#include <tuple> // for std::tuple, std::forward_as_tuple
#include <bits/functional_hash.h> // for __is_fast_hash
-#include <bits/stl_algobase.h> // for std::min, std::is_permutation.
+#include <bits/stl_algobase.h> // for std::min, std::is_permutation
#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
@@ -82,6 +83,11 @@ namespace __detail
{ return __distance_fw(__first, __last,
std::__iterator_category(__first)); }
+ template<typename _Alloc, typename _Value>
+ using __alloc_val_ptr =
+ typename std::allocator_traits<__alloc_rebind<_Alloc,
+ _Value>>::pointer;
+
struct _Identity
{
template<typename _Tp>
@@ -321,6 +327,28 @@ namespace __detail
_Hash_node_base(_Hash_node_base* __next) noexcept : _M_nxt(__next) { }
};
+ /**
+ * struct _Hash_pnode_base
+ *
+ * Like _Hash_node_base but used in case of custom pointer type defined by the
+ * allocator.
+ */
+ template<typename _NodePtr>
+ struct _Hash_pnode_base
+ {
+ using __node_ptr = _NodePtr;
+
+ __node_ptr _M_nxt;
+
+ _Hash_pnode_base()
+ noexcept(std::is_nothrow_default_constructible<__node_ptr>::value)
+ : _M_nxt() { }
+
+ _Hash_pnode_base(__node_ptr __next)
+ noexcept(std::is_nothrow_copy_constructible<__node_ptr>::value)
+ : _M_nxt(__next) { }
+ };
+
/**
* struct _Hash_node_value_base
*
@@ -356,18 +384,23 @@ namespace __detail
/**
* Primary template struct _Hash_node_code_cache.
+ *
+ * No cache.
*/
template<bool _Cache_hash_code>
struct _Hash_node_code_cache
{ };
/**
- * Specialization for node with cache, struct _Hash_node_code_cache.
+ * Specialization for node with cache.
*/
template<>
struct _Hash_node_code_cache<true>
{ std::size_t _M_hash_code; };
+ /**
+ * Node with value and optionally a cache for the hash code.
+ */
template<typename _Value, bool _Cache_hash_code>
struct _Hash_node_value
: _Hash_node_value_base<_Value>
@@ -375,28 +408,64 @@ namespace __detail
{ };
/**
- * Primary template struct _Hash_node.
+ * struct _Hash_node.
+ *
+ * The node definition when the allocator is using raw pointers.
*/
template<typename _Value, bool _Cache_hash_code>
struct _Hash_node
: _Hash_node_base
, _Hash_node_value<_Value, _Cache_hash_code>
{
- _Hash_node*
+ using __node_ptr = _Hash_node*;
+ using __node_type = _Hash_node;
+
+ __node_ptr
+ _M_next() const noexcept
+ { return static_cast<__node_ptr>(this->_M_nxt); }
+ };
+
+ /**
+ * struct _Hash_pnode.
+ *
+ * The node definition used when the allocator define a custom pointer type.
+ */
+ template<typename _ValuePtr, bool _Cache_hash_code>
+ struct _Hash_pnode
+ : _Hash_pnode_base<__ptr_rebind<
+ _ValuePtr, _Hash_pnode<_ValuePtr, _Cache_hash_code>>>
+ , _Hash_node_value<
+ typename std::pointer_traits<_ValuePtr>::element_type, _Cache_hash_code>
+ {
+ using __node_ptr = __ptr_rebind<
+ _ValuePtr, _Hash_pnode<_ValuePtr, _Cache_hash_code>>;
+ using __node_type =
+ typename std::pointer_traits<__node_ptr>::element_type;
+ typedef typename std::pointer_traits<__node_ptr>::difference_type
+ difference_type;
+
+ __node_ptr
_M_next() const noexcept
- { return static_cast<_Hash_node*>(this->_M_nxt); }
+ { return this->_M_nxt; }
};
+ template<typename _Alloc, typename _Value, bool __hash_cached>
+ using __get_node_type = typename std::conditional<
+ std::is_pointer<__alloc_val_ptr<_Alloc, _Value>>::value,
+ _Hash_node<_Value, __hash_cached>,
+ _Hash_pnode<__alloc_val_ptr<_Alloc, _Value>, __hash_cached>>::type;
+
/// Base class for node iterators.
- template<typename _Value, bool _Cache_hash_code>
- struct _Node_iterator_base
+ template<typename _NodePtr>
+ struct _Hashtable_iterator_base
{
- using __node_type = _Hash_node<_Value, _Cache_hash_code>;
+ using __node_ptr = _NodePtr;
+ using __node_type = typename std::pointer_traits<_NodePtr>::element_type;
- __node_type* _M_cur;
+ __node_ptr _M_cur;
- _Node_iterator_base() : _M_cur(nullptr) { }
- _Node_iterator_base(__node_type* __p) noexcept
+ _Hashtable_iterator_base() : _M_cur() { }
+ _Hashtable_iterator_base(__node_ptr __p) noexcept
: _M_cur(__p) { }
void
@@ -404,18 +473,33 @@ namespace __detail
{ _M_cur = _M_cur->_M_next(); }
friend bool
- operator==(const _Node_iterator_base& __x, const _Node_iterator_base& __y)
- noexcept
+ operator==(const _Hashtable_iterator_base& __x,
+ const _Hashtable_iterator_base& __y) noexcept
{ return __x._M_cur == __y._M_cur; }
#if __cpp_impl_three_way_comparison < 201907L
friend bool
- operator!=(const _Node_iterator_base& __x, const _Node_iterator_base& __y)
- noexcept
+ operator!=(const _Hashtable_iterator_base& __x,
+ const _Hashtable_iterator_base& __y) noexcept
{ return __x._M_cur != __y._M_cur; }
#endif
};
+ /// Base class for node iterators.
+ template<typename _Value, bool _Cache_hash_code>
+ struct _Node_iterator_base
+ : _Hashtable_iterator_base<_Hash_node<_Value, _Cache_hash_code>*>
+ {
+ using __base_type =
+ _Hashtable_iterator_base<_Hash_node<_Value, _Cache_hash_code>*>;
+ using __node_ptr = typename __base_type::__node_ptr;
+ using __node_type = typename __base_type::__node_ptr;
+
+ _Node_iterator_base() = default;
+ _Node_iterator_base(__node_ptr __p) noexcept
+ : __base_type(__p) { }
+ };
+
/// Node iterators, used to iterate through all the hashtable.
template<typename _Value, bool __constant_iterators, bool __cache>
struct _Node_iterator
@@ -424,6 +508,7 @@ namespace __detail
private:
using __base_type = _Node_iterator_base<_Value, __cache>;
using __node_type = typename __base_type::__node_type;
+ using __node_ptr = typename __base_type::__node_ptr;
public:
using value_type = _Value;
@@ -439,7 +524,7 @@ namespace __detail
_Node_iterator() = default;
explicit
- _Node_iterator(__node_type* __p) noexcept
+ _Node_iterator(__node_ptr __p) noexcept
: __base_type(__p) { }
reference
@@ -474,6 +559,7 @@ namespace __detail
private:
using __base_type = _Node_iterator_base<_Value, __cache>;
using __node_type = typename __base_type::__node_type;
+ using __node_ptr = typename __base_type::__node_ptr;
public:
typedef _Value value_type;
@@ -486,7 +572,7 @@ namespace __detail
_Node_const_iterator() = default;
explicit
- _Node_const_iterator(__node_type* __p) noexcept
+ _Node_const_iterator(__node_ptr __p) noexcept
: __base_type(__p) { }
_Node_const_iterator(const _Node_iterator<_Value, __constant_iterators,
@@ -517,6 +603,110 @@ namespace __detail
}
};
+ /// Node iterators, used to iterate through all the hashtable.
+ template<typename _NodePtr, bool __constant_iterators>
+ struct _Hashtable_iterator
+ : public _Hashtable_iterator_base<_NodePtr>
+ {
+ private:
+ using __base_type = _Hashtable_iterator_base<_NodePtr>;
+ using __node_type = typename __base_type::__node_type;
+ using __node_ptr = typename __base_type::__node_ptr;
+
+ public:
+ typedef typename __node_type::value_type value_type;
+ typedef typename __node_type::difference_type difference_type;
+ typedef std::forward_iterator_tag iterator_category;
+
+ using pointer = typename std::conditional<__constant_iterators,
+ const value_type*, value_type*>::type;
+
+ using reference = typename std::conditional<__constant_iterators,
+ const value_type&, value_type&>::type;
+
+ _Hashtable_iterator() = default;
+
+ explicit
+ _Hashtable_iterator(__node_ptr __p) noexcept
+ : __base_type(__p) { }
+
+ reference
+ operator*() const noexcept
+ { return this->_M_cur->_M_v(); }
+
+ pointer
+ operator->() const noexcept
+ { return this->_M_cur->_M_valptr(); }
+
+ _Hashtable_iterator&
+ operator++() noexcept
+ {
+ this->_M_incr();
+ return *this;
+ }
+
+ _Hashtable_iterator
+ operator++(int) noexcept
+ {
+ _Hashtable_iterator __tmp(*this);
+ this->_M_incr();
+ return __tmp;
+ }
+ };
+
+ /// Node const_iterators, used to iterate through all the hashtable.
+ template<typename _NodePtr, bool __constant_iterators>
+ struct _Hashtable_const_iterator
+ : public _Hashtable_iterator_base<_NodePtr>
+ {
+ private:
+ using __base_type = _Hashtable_iterator_base<_NodePtr>;
+ using __node_type = typename __base_type::__node_type;
+ using __node_ptr = typename __base_type::__node_ptr;
+
+ public:
+ typedef typename __node_type::value_type value_type;
+ typedef typename __node_type::difference_type difference_type;
+ typedef std::forward_iterator_tag iterator_category;
+
+ typedef const value_type* pointer;
+ typedef const value_type& reference;
+
+ _Hashtable_const_iterator() = default;
+
+ explicit
+ _Hashtable_const_iterator(__node_ptr __p) noexcept
+ : __base_type(__p) { }
+
+ _Hashtable_const_iterator(
+ const _Hashtable_iterator<_NodePtr,
+ __constant_iterators>& __x) noexcept
+ : __base_type(__x._M_cur) { }
+
+ reference
+ operator*() const noexcept
+ { return this->_M_cur->_M_v(); }
+
+ pointer
+ operator->() const noexcept
+ { return this->_M_cur->_M_valptr(); }
+
+ _Hashtable_const_iterator&
+ operator++() noexcept
+ {
+ this->_M_incr();
+ return *this;
+ }
+
+ _Hashtable_const_iterator
+ operator++(int) noexcept
+ {
+ _Hashtable_const_iterator __tmp(*this);
+ this->_M_incr();
+ return __tmp;
+ }
+ };
+
// Many of class template _Hashtable's template parameters are policy
// classes. These are defaults for the policies.
@@ -912,16 +1102,16 @@ namespace __detail
using __hash_cached = typename _Traits::__hash_cached;
using __constant_iterators = typename _Traits::__constant_iterators;
+ using __alloc_ptr = __alloc_val_ptr<_Alloc, _Value>;
- using __hashtable_alloc = _Hashtable_alloc<
- __alloc_rebind<_Alloc, _Hash_node<_Value,
- __hash_cached::value>>>;
+ using __node_type = __get_node_type<_Alloc, _Value, __hash_cached::value>;
+ using __node_ptr = __ptr_rebind<__alloc_ptr, __node_type>;
+ using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
using value_type = typename __hashtable_base::value_type;
using size_type = typename __hashtable_base::size_type;
using __unique_keys = typename _Traits::__unique_keys;
- using __node_alloc_type = typename __hashtable_alloc::__node_alloc_type;
using __node_gen_type = _AllocNode<__node_alloc_type>;
__hashtable&
@@ -939,12 +1129,19 @@ namespace __detail
const _NodeGetter&, false_type __uks);
public:
- using iterator = _Node_iterator<_Value, __constant_iterators::value,
- __hash_cached::value>;
-
- using const_iterator = _Node_const_iterator<_Value,
- __constant_iterators::value,
- __hash_cached::value>;
+ using iterator =
+ typename std::conditional<std::is_pointer<__alloc_ptr>::value,
+ _Node_iterator<_Value,
+ __constant_iterators::value, __hash_cached::value>,
+ _Hashtable_iterator<__node_ptr,
+ __constant_iterators::value>>::type;
+
+ using const_iterator =
+ typename std::conditional<std::is_pointer<__alloc_ptr>::value,
+ _Node_const_iterator<_Value,
+ __constant_iterators::value, __hash_cached::value>,
+ _Hashtable_const_iterator<__node_ptr,
+ __constant_iterators::value>>::type;
using __ireturn_type = __conditional_t<__unique_keys::value,
std::pair<iterator, bool>,
@@ -1280,6 +1477,17 @@ namespace __detail
bool __cache_hash_code>
struct _Local_iterator_base;
+ /**
+ * Primary class template _Hashtable_local_iter_base.
+ *
+ * Base class for local iterators, used to iterate within a bucket
+ * but not between buckets.
+ */
+ template<typename _Key, typename _NodePtr, typename _ExtractKey,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ bool __cache_hash_code>
+ struct _Hashtable_local_iter_base;
+
/**
* Primary class template _Hash_code_base.
*
@@ -1440,6 +1648,49 @@ namespace __detail
_M_get_bucket() const { return _M_bucket; } // for debug mode
};
+ /// Partial specialization used when nodes contain a cached hash code.
+ template<typename _Key, typename _NodePtr, typename _ExtractKey,
+ typename _Hash, typename _RangeHash, typename _Unused>
+ struct _Hashtable_local_iter_base<_Key, _NodePtr, _ExtractKey,
+ _Hash, _RangeHash, _Unused, true>
+ : public _Hashtable_iterator_base<_NodePtr>
+ {
+ protected:
+ using __base_node_iter = _Hashtable_iterator_base<_NodePtr>;
+ using __node_ptr = typename __base_node_iter::__node_ptr;
+ using __node_type = typename __base_node_iter::__node_type;
+ using value_type = typename __node_type::value_type;
+ using __hash_code_base = _Hash_code_base<_Key, value_type, _ExtractKey,
+ _Hash, _RangeHash, _Unused, true>;
+
+ _Hashtable_local_iter_base() = default;
+ _Hashtable_local_iter_base(const __hash_code_base&,
+ __node_ptr __p,
+ std::size_t __bkt, std::size_t __bkt_count)
+ : __base_node_iter(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
+ { }
+
+ void
+ _M_incr()
+ {
+ __base_node_iter::_M_incr();
+ if (this->_M_cur)
+ {
+ std::size_t __bkt
+ = _RangeHash{}(this->_M_cur->_M_hash_code, _M_bucket_count);
+ if (__bkt != _M_bucket)
+ this->_M_cur = nullptr;
+ }
+ }
+
+ std::size_t _M_bucket;
+ std::size_t _M_bucket_count;
+
+ public:
+ std::size_t
+ _M_get_bucket() const { return _M_bucket; } // for debug mode
+ };
+
// Uninitialized storage for a _Hash_code_base.
// This type is DefaultConstructible and Assignable even if the
// _Hash_code_base type isn't, so that _Local_iterator_base<..., false>
@@ -1554,6 +1805,86 @@ namespace __detail
_M_get_bucket() const { return _M_bucket; } // for debug mode
};
+ // Partial specialization used when hash codes are not cached
+ template<typename _Key, typename _NodePtr, typename _ExtractKey,
+ typename _Hash, typename _RangeHash, typename _Unused>
+ struct _Hashtable_local_iter_base<_Key, _NodePtr, _ExtractKey,
+ _Hash, _RangeHash, _Unused, false>
+ : _Hash_code_storage<_Hash>
+ , _Hashtable_iterator_base<_NodePtr>
+ {
+ protected:
+ using __node_iter_base = _Hashtable_iterator_base<_NodePtr>;
+ using __node_type = typename __node_iter_base::__node_type;
+ using __node_ptr = typename __node_iter_base::__node_ptr;
+ using value_type = typename __node_type::value_type;
+ using __hash_code_base = _Hash_code_base<_Key, value_type, _ExtractKey,
+ _Hash, _RangeHash, _Unused, false>;
+
+ _Hashtable_local_iter_base() : _M_bucket_count(-1) { }
+
+ _Hashtable_local_iter_base(const __hash_code_base& __base,
+ __node_ptr __p,
+ std::size_t __bkt, std::size_t __bkt_count)
+ : __node_iter_base(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
+ { _M_init(__base.hash_function()); }
+
+ ~_Hashtable_local_iter_base()
+ {
+ if (_M_bucket_count != -1)
+ _M_destroy();
+ }
+
+ _Hashtable_local_iter_base(const _Hashtable_local_iter_base& __iter)
+ : __node_iter_base(__iter._M_cur), _M_bucket(__iter._M_bucket)
+ , _M_bucket_count(__iter._M_bucket_count)
+ {
+ if (_M_bucket_count != -1)
+ _M_init(*__iter._M_h());
+ }
+
+ _Hashtable_local_iter_base&
+ operator=(const _Hashtable_local_iter_base& __iter)
+ {
+ if (_M_bucket_count != -1)
+ _M_destroy();
+ this->_M_cur = __iter._M_cur;
+ _M_bucket = __iter._M_bucket;
+ _M_bucket_count = __iter._M_bucket_count;
+ if (_M_bucket_count != -1)
+ _M_init(*__iter._M_h());
+ return *this;
+ }
+
+ void
+ _M_incr()
+ {
+ __node_iter_base::_M_incr();
+ if (this->_M_cur)
+ {
+ std::size_t __bkt =
+ _RangeHash{}((*this->_M_h())(_ExtractKey{}(this->_M_cur->_M_v())),
+ _M_bucket_count);
+ if (__bkt != _M_bucket)
+ this->_M_cur = nullptr;
+ }
+ }
+
+ std::size_t _M_bucket;
+ std::size_t _M_bucket_count;
+
+ void
+ _M_init(const _Hash& __h)
+ { ::new(this->_M_h()) _Hash(__h); }
+
+ void
+ _M_destroy() { this->_M_h()->~_Hash(); }
+
+ public:
+ std::size_t
+ _M_get_bucket() const { return _M_bucket; } // for debug mode
+ };
+
/// local iterators
template<typename _Key, typename _Value, typename _ExtractKey,
typename _Hash, typename _RangeHash, typename _Unused,
@@ -1667,6 +1998,156 @@ namespace __detail
}
};
+ /// local iterators
+ template<typename _Key, typename _NodePtr, typename _ExtractKey,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ bool __constant_iterators, bool __cache>
+ struct _Hashtable_local_iterator
+ : public _Hashtable_local_iter_base<_Key, _NodePtr, _ExtractKey,
+ _Hash, _RangeHash, _Unused, __cache>
+ {
+ private:
+ using __base_type =
+ _Hashtable_local_iter_base<_Key, _NodePtr, _ExtractKey,
+ _Hash, _RangeHash, _Unused, __cache>;
+ using __hash_code_base = typename __base_type::__hash_code_base;
+ using __node_type = typename __base_type::__node_type;
+ using __node_ptr = typename __base_type::__node_ptr;
+
+ public:
+ typedef typename __base_type::value_type value_type;
+ typedef typename std::conditional<__constant_iterators,
+ const value_type*, value_type*>::type
+ pointer;
+ typedef typename std::conditional<__constant_iterators,
+ const value_type&, value_type&>::type
+ reference;
+ typedef typename __node_type::difference_type difference_type;
+ typedef std::forward_iterator_tag iterator_category;
+
+ _Hashtable_local_iterator() = default;
+
+ _Hashtable_local_iterator(const __hash_code_base& __base,
+ __node_ptr __n,
+ std::size_t __bkt, std::size_t __bkt_count)
+ : __base_type(__base, __n, __bkt, __bkt_count)
+ { }
+
+ reference
+ operator*() const
+ { return this->_M_cur->_M_v(); }
+
+ pointer
+ operator->() const
+ { return this->_M_cur->_M_valptr(); }
+
+ _Hashtable_local_iterator&
+ operator++()
+ {
+ this->_M_incr();
+ return *this;
+ }
+
+ _Hashtable_local_iterator
+ operator++(int)
+ {
+ _Hashtable_local_iterator __tmp(*this);
+ this->_M_incr();
+ return __tmp;
+ }
+ };
+
+ /// local const_iterators
+ template<typename _Key, typename _NodePtr, typename _ExtractKey,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ bool __constant_iterators, bool __cache>
+ struct _Hashtable_const_local_iterator
+ : public _Hashtable_local_iter_base<_Key, _NodePtr, _ExtractKey,
+ _Hash, _RangeHash, _Unused, __cache>
+ {
+ private:
+ using __base_type =
+ _Hashtable_local_iter_base<_Key, _NodePtr, _ExtractKey,
+ _Hash, _RangeHash, _Unused, __cache>;
+ using __hash_code_base = typename __base_type::__hash_code_base;
+ using __node_type = typename __base_type::__node_type;
+ using __node_ptr = typename __base_type::__node_ptr;
+
+ public:
+ typedef typename __base_type::value_type value_type;
+ typedef const value_type* pointer;
+ typedef const value_type& reference;
+ typedef typename __node_type::difference_type difference_type;
+ typedef std::forward_iterator_tag iterator_category;
+
+ _Hashtable_const_local_iterator() = default;
+
+ _Hashtable_const_local_iterator(const __hash_code_base& __base,
+ __node_ptr __n,
+ std::size_t __bkt, std::size_t __bkt_count)
+ : __base_type(__base, __n, __bkt, __bkt_count)
+ { }
+
+ _Hashtable_const_local_iterator(const _Hashtable_local_iterator<
+ _Key, _NodePtr, _ExtractKey,
+ _Hash, _RangeHash, _Unused,
+ __constant_iterators,
+ __cache>& __x)
+ : __base_type(__x)
+ { }
+
+ reference
+ operator*() const
+ { return this->_M_cur->_M_v(); }
+
+ pointer
+ operator->() const
+ { return this->_M_cur->_M_valptr(); }
+
+ _Hashtable_const_local_iterator&
+ operator++()
+ {
+ this->_M_incr();
+ return *this;
+ }
+
+ _Hashtable_const_local_iterator
+ operator++(int)
+ {
+ _Hashtable_const_local_iterator __tmp(*this);
+ this->_M_incr();
+ return __tmp;
+ }
+ };
+
+ template<typename _NodePtr, typename _Key, typename _Value,
+ typename _ExtractKey, typename _Hash,
+ typename _RangeHash, typename _Unused,
+ bool __constant_iterators, bool __hash_cached>
+ using __local_iterator = typename std::conditional<
+ std::is_pointer<_NodePtr>::value,
+ _Local_iterator<_Key, _Value,
+ _ExtractKey, _Hash, _RangeHash, _Unused,
+ __constant_iterators, __hash_cached>,
+ _Hashtable_local_iterator<_Key, _NodePtr,
+ _ExtractKey, _Hash, _RangeHash, _Unused,
+ __constant_iterators,
+ __hash_cached>>::type;
+
+ template<typename _NodePtr, typename _Key, typename _Value,
+ typename _ExtractKey, typename _Hash,
+ typename _RangeHash, typename _Unused,
+ bool __constant_iterators, bool __hash_cached>
+ using __const_local_iterator = typename std::conditional<
+ std::is_pointer<_NodePtr>::value,
+ _Local_const_iterator<_Key, _Value,
+ _ExtractKey, _Hash, _RangeHash, _Unused,
+ __constant_iterators, __hash_cached>,
+ _Hashtable_const_local_iterator<_Key, _NodePtr,
+ _ExtractKey, _Hash, _RangeHash, _Unused,
+ __constant_iterators,
+ __hash_cached>>::type;
+
/**
* Primary class template _Hashtable_base.
*
@@ -1943,10 +2424,16 @@ namespace __detail
using __ebo_node_alloc = _Hashtable_ebo_helper<0, _NodeAlloc>;
template<typename>
- struct __get_value_type;
+ struct __get_node_base;
template<typename _Val, bool _Cache_hash_code>
- struct __get_value_type<_Hash_node<_Val, _Cache_hash_code>>
- { using type = _Val; };
+ struct __get_node_base<_Hash_node<_Val, _Cache_hash_code>>
+ { using type = _Hash_node_base; };
+ template<typename _ValuePtr, bool _Cache_hash_code>
+ struct __get_node_base<_Hash_pnode<_ValuePtr, _Cache_hash_code>>
+ {
+ using type = _Hash_pnode_base<__ptr_rebind<
+ _ValuePtr, _Hash_pnode<_ValuePtr, _Cache_hash_code>>>;
+ };
public:
using __node_type = typename _NodeAlloc::value_type;
@@ -1954,16 +2441,13 @@ namespace __detail
// 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 __node_ptr = typename __node_alloc_traits::pointer;
+ using __node_base = typename __get_node_base<__node_type>::type;
+ using __node_base_ptr = __ptr_rebind<__node_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 __buckets_ptr = typename __buckets_alloc_traits::pointer;
_Hashtable_alloc() = default;
_Hashtable_alloc(const _Hashtable_alloc&) = default;
@@ -2017,17 +2501,16 @@ namespace __detail
{
auto& __alloc = _M_node_allocator();
auto __nptr = __node_alloc_traits::allocate(__alloc, 1);
- __node_ptr __n = std::__to_address(__nptr);
__try
{
- ::new ((void*)__n) __node_type;
- __node_alloc_traits::construct(__alloc, __n->_M_valptr(),
+ __node_alloc_traits::construct(__alloc, std::__to_address(__nptr));
+ __node_alloc_traits::construct(__alloc, __nptr->_M_valptr(),
std::forward<_Args>(__args)...);
- return __n;
+ return __nptr;
}
__catch(...)
{
- __n->~__node_type();
+ __node_alloc_traits::destroy(__alloc, std::__to_address(__nptr));
__node_alloc_traits::deallocate(__alloc, __nptr, 1);
__throw_exception_again;
}
@@ -2045,10 +2528,9 @@ namespace __detail
void
_Hashtable_alloc<_NodeAlloc>::_M_deallocate_node_ptr(__node_ptr __n)
{
- typedef typename __node_alloc_traits::pointer _Ptr;
- 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();
+ __node_alloc_traits::destroy(__alloc, std::__to_address(__n));
+ __node_alloc_traits::deallocate(__alloc, __n, 1);
}
template<typename _NodeAlloc>
@@ -2069,11 +2551,9 @@ namespace __detail
-> __buckets_ptr
{
__buckets_alloc_type __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;
+ std::__uninitialized_default_n(__ptr, __bkt_count);
+ return __ptr;
}
template<typename _NodeAlloc>
@@ -2082,10 +2562,9 @@ namespace __detail
_M_deallocate_buckets(__buckets_ptr __bkts,
std::size_t __bkt_count)
{
- typedef typename __buckets_alloc_traits::pointer _Ptr;
- auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__bkts);
__buckets_alloc_type __alloc(_M_node_allocator());
- __buckets_alloc_traits::deallocate(__alloc, __ptr, __bkt_count);
+ std::_Destroy_n(__bkts, __bkt_count);
+ __buckets_alloc_traits::deallocate(__alloc, __bkts, __bkt_count);
}
///@} hashtable-detail
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_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_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_set/allocator/ext_ptr.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/allocator/ext_ptr.cc
index afcc58e39f4..2c1bbe9ad3e 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
@@ -1,24 +1,4 @@
-// Copyright (C) 2013-2024 Free Software Foundation, Inc.
-//
-// This file is part of the GNU ISO C++ Library. This library is free
-// software; you can redistribute it and/or modify it under the
-// terms of the GNU General Public License as published by the
-// Free Software Foundation; either version 3, or (at your option)
-// any later version.
-
-// This library is distributed in the hope that it will be useful,
-// but WITHOUT ANY WARRANTY; without even the implied warranty of
-// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-// GNU General Public License for more details.
-
-// You should have received a copy of the GNU General Public License along
-// 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>
@@ -26,15 +6,22 @@
#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; }
+
+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> { };
+
+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()
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2024-06-29 14:02 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2024-06-26 20:38 [PATCH] _Hashtable fancy pointer support François Dumont
2024-06-26 21:41 ` Jonathan Wakely
2024-06-27 19:25 ` François Dumont
2024-06-27 20:30 ` Jonathan Wakely
2024-06-29 14:02 ` François Dumont
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).