This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: Limit template parameters in hashtable
- From: François Dumont <frs dot dumont at gmail dot com>
- To: Jonathan Wakely <jwakely dot gcc at gmail dot com>
- Cc: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>
- Date: Wed, 17 Jul 2013 22:53:57 +0200
- Subject: Re: Limit template parameters in hashtable
- References: <51E45D4D dot 8020208 at gmail dot com> <CAH6eHdQi2f2LRB65cGsGQbYXxNE6kK0-76vw3b9fyBQEieKrCA at mail dot gmail dot com>
On 07/16/2013 11:03 AM, Jonathan Wakely wrote:
On 15 July 2013 21:36, François Dumont wrote:
Hi
Here is a patch proposal to limit number of template parameters in
recently introduced _ReuseOrAllocNode and _AllocNode types. I hope it is
what you had in mind Jonathan. I have isolated most of allocation code into
a new _Hashtable_alloc class and inherit from it in _Hashtable. It greatly
reduce the number of template parameters for a number of methods that used
to be in _Hashtable.
Yes, that's what I was thinking, thanks for doing it. Would it be
possible to rebind the allocator before instantiating _Hashtable, and
have _Hastable_alloc<_Alloc, __cache> and get the value_type from the
allocator? That would mean these two specializations would share more
code:
unordered_map<int, int, P, C, allocator<pair<int,int>>>
unordered_map<int, int, P, C, allocator<pair<const int,int>>>
because they would both use the same specialization of _Hashtable and
_Hashtable_alloc.
If that makes change too complicated it isn't essential.
Here is another proposal. I haven't rebound the allocator to
instantiate _Hashtable but only to instantiate _Hashtable_alloc. I
prefered to keep the definition of allocator_type into _Hashtable so
that it isolates unordered_XXX from this kind of implementation detail.
As allocator_type typedef must match _Alloc template parameters it has
to be done before it is rebound.
The drawback is of course that it introduces a binary breaking change,
is it fine ?
Did we already do that for 4.9 anyway?
AFAIK no, no binary incompatibility so far. But I can't see how to do
this simplification without this breaking change. _M_bbegin could be
restore in its previous place but the allocator instance must be managed
by _Hashtable_alloc so it will necessarily generate this breaking change.
François
Index: include/bits/hashtable_policy.h
===================================================================
--- include/bits/hashtable_policy.h (revision 200963)
+++ include/bits/hashtable_policy.h (working copy)
@@ -102,25 +102,26 @@
{ return std::get<0>(std::forward<_Tp>(__x)); }
};
+ template<typename _ValueAlloc, bool __cache_hash_code>
+ struct _Hashtable_alloc;
+
// Functor recycling a pool of nodes and using allocation once the pool is
// empty.
- template<typename _Key, typename _Value, typename _Alloc,
- typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash,
- typename _RehashPolicy, typename _Traits>
+ template<typename _ValueAlloc, bool __cache_hash_code>
struct _ReuseOrAllocNode
{
private:
- using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
- _Equal, _H1, _H2, _Hash,
- _RehashPolicy, _Traits>;
- using __val_alloc_type = typename __hashtable::_Value_alloc_type;
- using __val_alloc_traits = typename __hashtable::_Value_alloc_traits;
- using __node_alloc_traits = typename __hashtable::_Node_alloc_traits;
- using __node_type = typename __hashtable::__node_type;
+ using __value_alloc_type = _ValueAlloc;
+ using __hashtable_alloc =
+ _Hashtable_alloc<__value_alloc_type, __cache_hash_code>;
+ using __value_alloc_traits =
+ typename __hashtable_alloc::__value_alloc_traits;
+ using __node_alloc_traits =
+ typename __hashtable_alloc::__node_alloc_traits;
+ using __node_type = typename __hashtable_alloc::__node_type;
public:
- _ReuseOrAllocNode(__node_type* __nodes, __hashtable& __h)
+ _ReuseOrAllocNode(__node_type* __nodes, __hashtable_alloc& __h)
: _M_nodes(__nodes), _M_h(__h) { }
_ReuseOrAllocNode(const _ReuseOrAllocNode&) = delete;
@@ -136,12 +137,12 @@
__node_type* __node = _M_nodes;
_M_nodes = _M_nodes->_M_next();
__node->_M_nxt = nullptr;
- __val_alloc_type __a(_M_h._M_node_allocator());
- __val_alloc_traits::destroy(__a, __node->_M_valptr());
+ __value_alloc_type __a(_M_h._M_node_allocator());
+ __value_alloc_traits::destroy(__a, __node->_M_valptr());
__try
{
- __val_alloc_traits::construct(__a, __node->_M_valptr(),
- std::forward<_Arg>(__arg));
+ __value_alloc_traits::construct(__a, __node->_M_valptr(),
+ std::forward<_Arg>(__arg));
}
__catch(...)
{
@@ -157,24 +158,20 @@
private:
mutable __node_type* _M_nodes;
- __hashtable& _M_h;
+ __hashtable_alloc& _M_h;
};
// Functor similar to the previous one but without any pool of node to recycle.
- template<typename _Key, typename _Value, typename _Alloc,
- typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash,
- typename _RehashPolicy, typename _Traits>
+ template<typename _ValueAlloc, bool __cache_hash_code>
struct _AllocNode
{
private:
- using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
- _Equal, _H1, _H2, _Hash,
- _RehashPolicy, _Traits>;
- using __node_type = typename __hashtable::__node_type;
+ using __hashtable_alloc =
+ _Hashtable_alloc<_ValueAlloc, __cache_hash_code>;
+ using __node_type = typename __hashtable_alloc::__node_type;
public:
- _AllocNode(__hashtable& __h)
+ _AllocNode(__hashtable_alloc& __h)
: _M_h(__h) { }
template<typename _Arg>
@@ -183,7 +180,7 @@
{ return _M_h._M_allocate_node(std::forward<_Arg>(__arg)); }
private:
- __hashtable& _M_h;
+ __hashtable_alloc& _M_h;
};
// Auxiliary types used for all instantiations of _Hashtable nodes
@@ -697,9 +694,10 @@
using __unique_keys = typename __hashtable_base::__unique_keys;
using __ireturn_type = typename __hashtable_base::__ireturn_type;
- using __node_gen_type = _AllocNode<_Key, _Value, _Alloc, _ExtractKey,
- _Equal, _H1, _H2, _Hash,
- _RehashPolicy, _Traits>;
+ using __value_alloc_type =
+ typename __alloctr_rebind<_Alloc, _Value>::__type;
+ using __node_gen_type
+ = _AllocNode<__value_alloc_type, _Traits::__hash_cached::value>;
__hashtable&
_M_conjure_hashtable()
@@ -1804,6 +1802,148 @@
{ }
};
+ template<typename _ValueAlloc, bool __cache_hash_code>
+ struct _Hashtable_alloc
+ {
+ using __value_type = typename _ValueAlloc::value_type;
+ using __value_alloc_type = _ValueAlloc;
+ using __value_alloc_traits = std::allocator_traits<__value_alloc_type>;
+
+ using __node_base = __detail::_Hash_node_base;
+ using __bucket_type = __node_base*;
+ using __node_type = _Hash_node<__value_type, __cache_hash_code>;
+
+ using __node_alloc_type =
+ typename __alloctr_rebind<__value_alloc_type, __node_type>::__type;
+
+ // Use __gnu_cxx to benefit from _S_always_equal and al.
+ using __node_alloc_traits = __gnu_cxx::__alloc_traits<__node_alloc_type>;
+
+ using __bucket_alloc_type =
+ typename __alloctr_rebind<__value_alloc_type, __bucket_type>::__type;
+ using __bucket_alloc_traits = std::allocator_traits<__bucket_alloc_type>;
+
+ using __before_begin = __detail::_Before_begin<__node_alloc_type>;
+
+ __before_begin _M_bbegin;
+
+ _Hashtable_alloc(const _Hashtable_alloc&) = default;
+ _Hashtable_alloc(_Hashtable_alloc&&) = default;
+
+ template<typename _NodeAlloc>
+ _Hashtable_alloc(_NodeAlloc&& __a)
+ : _M_bbegin(std::forward<_NodeAlloc>(__a))
+ { }
+
+ __node_alloc_type&
+ _M_node_allocator()
+ { return _M_bbegin; }
+
+ const __node_alloc_type&
+ _M_node_allocator() const
+ { return _M_bbegin; }
+
+ __node_base&
+ _M_before_begin()
+ { return _M_bbegin._M_node; }
+
+ const __node_base&
+ _M_before_begin() const
+ { return _M_bbegin._M_node; }
+
+ template<typename... _Args>
+ __node_type*
+ _M_allocate_node(_Args&&... __args);
+
+ void
+ _M_deallocate_node(__node_type* __n);
+
+ // Deallocate the linked list of nodes pointed to by __n
+ void
+ _M_deallocate_nodes(__node_type* __n);
+
+ __bucket_type*
+ _M_allocate_buckets(std::size_t __n);
+
+ void
+ _M_deallocate_buckets(__bucket_type*, std::size_t __n);
+ };
+
+ // Definitions of class template _Hashtable_alloc's out-of-line member
+ // functions.
+ template<typename _ValueAlloc, bool __cache_hash_code>
+ template<typename... _Args>
+ typename _Hashtable_alloc<_ValueAlloc, __cache_hash_code>::__node_type*
+ _Hashtable_alloc<_ValueAlloc, __cache_hash_code>::
+ _M_allocate_node(_Args&&... __args)
+ {
+ auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1);
+ __node_type* __n = std::__addressof(*__nptr);
+ __try
+ {
+ __value_alloc_type __a(_M_node_allocator());
+ ::new ((void*)__n) __node_type();
+ __value_alloc_traits::construct(__a, __n->_M_valptr(),
+ std::forward<_Args>(__args)...);
+ return __n;
+ }
+ __catch(...)
+ {
+ __node_alloc_traits::deallocate(_M_node_allocator(), __nptr, 1);
+ __throw_exception_again;
+ }
+ }
+
+ template<typename _ValueAlloc, bool __cache_hash_code>
+ void
+ _Hashtable_alloc<_ValueAlloc, __cache_hash_code>::
+ _M_deallocate_node(__node_type* __n)
+ {
+ typedef typename __node_alloc_traits::pointer _Ptr;
+ auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__n);
+ __value_alloc_type __a(_M_node_allocator());
+ __value_alloc_traits::destroy(__a, __n->_M_valptr());
+ __n->~__node_type();
+ __node_alloc_traits::deallocate(_M_node_allocator(), __ptr, 1);
+ }
+
+ template<typename _ValueAlloc, bool __cache_hash_code>
+ void
+ _Hashtable_alloc<_ValueAlloc, __cache_hash_code>::
+ _M_deallocate_nodes(__node_type* __n)
+ {
+ while (__n)
+ {
+ __node_type* __tmp = __n;
+ __n = __n->_M_next();
+ _M_deallocate_node(__tmp);
+ }
+ }
+
+ template<typename _ValueAlloc, bool __cache_hash_code>
+ typename _Hashtable_alloc<_ValueAlloc, __cache_hash_code>::__bucket_type*
+ _Hashtable_alloc<_ValueAlloc, __cache_hash_code>::
+ _M_allocate_buckets(std::size_t __n)
+ {
+ __bucket_alloc_type __alloc(_M_node_allocator());
+
+ auto __ptr = __bucket_alloc_traits::allocate(__alloc, __n);
+ __bucket_type* __p = std::__addressof(*__ptr);
+ __builtin_memset(__p, 0, __n * sizeof(__bucket_type));
+ return __p;
+ }
+
+ template<typename _ValueAlloc, bool __cache_hash_code>
+ void
+ _Hashtable_alloc<_ValueAlloc, __cache_hash_code>::
+ _M_deallocate_buckets(__bucket_type* __bkts, std::size_t __n)
+ {
+ typedef typename __bucket_alloc_traits::pointer _Ptr;
+ auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__bkts);
+ __bucket_alloc_type __alloc(_M_node_allocator());
+ __bucket_alloc_traits::deallocate(__alloc, __ptr, __n);
+ }
+
//@} hashtable-detail
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace __detail
Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h (revision 200963)
+++ include/bits/hashtable.h (working copy)
@@ -181,13 +181,23 @@
public __detail::_Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_H1, _H2, _Hash, _RehashPolicy, _Traits>,
public __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>
+ _H1, _H2, _Hash, _RehashPolicy, _Traits>,
+ private __detail::_Hashtable_alloc<typename __alloctr_rebind<_Alloc, _Value>::__type,
+ _Traits::__hash_cached::value>
{
- typedef std::allocator_traits<_Alloc> _Alloc_traits;
- typedef typename _Alloc_traits::template rebind_alloc<_Value>
- _Value_alloc_type;
- typedef __gnu_cxx::__alloc_traits<_Value_alloc_type> _Value_alloc_traits;
+ using __value_alloc_type =
+ typename __alloctr_rebind<_Alloc, _Value>::__type;
+ using __hashtable_alloc = __detail::
+ _Hashtable_alloc<__value_alloc_type, _Traits::__hash_cached::value>;
+
+ using __value_alloc_traits =
+ typename __hashtable_alloc::__value_alloc_traits;
+ using __node_alloc_type =
+ typename __hashtable_alloc::__node_alloc_type;
+ using __node_alloc_traits =
+ typename __hashtable_alloc::__node_alloc_traits;
+
public:
typedef _Key key_type;
typedef _Value value_type;
@@ -196,8 +206,8 @@
// mapped_type, if present, comes from _Map_base.
// hasher, if present, comes from _Hash_code_base/_Hashtable_base.
- typedef typename _Value_alloc_traits::pointer pointer;
- typedef typename _Value_alloc_traits::const_pointer const_pointer;
+ typedef typename __value_alloc_traits::pointer pointer;
+ typedef typename __value_alloc_traits::const_pointer const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;
@@ -240,9 +250,7 @@
_RehashPolicy, _Traits>;
using __reuse_or_alloc_node_type =
- __detail::_ReuseOrAllocNode<_Key, _Value, _Alloc,
- _ExtractKey, _Equal, _H1, _H2, _Hash,
- _RehashPolicy, _Traits>;
+ __detail::_ReuseOrAllocNode<__value_alloc_type, __hash_cached::value>;
// Metaprogramming for picking apart hash caching.
template<typename _Cond>
@@ -309,18 +317,6 @@
bool _Constant_iteratorsa, bool _Unique_keysa>
friend struct __detail::_Insert;
- template<typename _Keya, typename _Valuea, typename _Alloca,
- typename _ExtractKeya, typename _Equala,
- typename _H1a, typename _H2a, typename _Hasha,
- typename _RehashPolicya, typename _Traitsa>
- friend struct __detail::_ReuseOrAllocNode;
-
- template<typename _Keya, typename _Valuea, typename _Alloca,
- typename _ExtractKeya, typename _Equala,
- typename _H1a, typename _H2a, typename _Hasha,
- typename _RehashPolicya, typename _Traitsa>
- friend struct __detail::_AllocNode;
-
public:
using size_type = typename __hashtable_base::size_type;
using difference_type = typename __hashtable_base::difference_type;
@@ -333,60 +329,19 @@
const_local_iterator;
private:
- typedef typename _Alloc_traits::template rebind_alloc<__node_type>
- _Node_alloc_type;
- // Use __gnu_cxx to benefit from _S_always_equal and al.
- typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits;
-
- typedef
- typename _Alloc_traits::template rebind_alloc<__bucket_type>
- _Bucket_alloc_type;
- typedef std::allocator_traits<_Bucket_alloc_type> _Bucket_alloc_traits;
-
- using __before_begin = __detail::_Before_begin<_Node_alloc_type>;
-
__bucket_type* _M_buckets;
size_type _M_bucket_count;
- __before_begin _M_bbegin;
size_type _M_element_count;
_RehashPolicy _M_rehash_policy;
- _Node_alloc_type&
- _M_node_allocator()
- { return _M_bbegin; }
+ __hashtable_alloc&
+ _M_base_alloc() { return *this; }
- const _Node_alloc_type&
- _M_node_allocator() const
- { return _M_bbegin; }
+ using __hashtable_alloc::_M_deallocate_buckets;
- __node_base&
- _M_before_begin()
- { return _M_bbegin._M_node; }
-
- const __node_base&
- _M_before_begin() const
- { return _M_bbegin._M_node; }
-
- template<typename... _Args>
- __node_type*
- _M_allocate_node(_Args&&... __args);
-
void
- _M_deallocate_node(__node_type* __n);
-
- // Deallocate the linked list of nodes pointed to by __n
- void
- _M_deallocate_nodes(__node_type* __n);
-
- __bucket_type*
- _M_allocate_buckets(size_type __n);
-
- void
- _M_deallocate_buckets(__bucket_type*, size_type __n);
-
- void
_M_deallocate_buckets()
- { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
+ { this->_M_deallocate_buckets(_M_buckets, _M_bucket_count); }
// Gets bucket begin, deals with the fact that non-empty buckets contain
// their before begin node.
@@ -395,7 +350,7 @@
__node_type*
_M_begin() const
- { return static_cast<__node_type*>(_M_before_begin()._M_nxt); }
+ { return static_cast<__node_type*>(this->_M_before_begin()._M_nxt); }
template<typename _NodeGenerator>
void
@@ -477,11 +432,11 @@
_Hashtable&
operator=(_Hashtable&& __ht)
- noexcept(_Node_alloc_traits::_S_nothrow_move())
+ noexcept(__node_alloc_traits::_S_nothrow_move())
{
constexpr bool __move_storage =
- _Node_alloc_traits::_S_propagate_on_move_assign()
- || _Node_alloc_traits::_S_always_equal();
+ __node_alloc_traits::_S_propagate_on_move_assign()
+ || __node_alloc_traits::_S_always_equal();
_M_move_assign(std::move(__ht),
integral_constant<bool, __move_storage>());
return *this;
@@ -491,7 +446,7 @@
operator=(initializer_list<value_type> __l)
{
__reuse_or_alloc_node_type __roan(_M_begin(), *this);
- _M_before_begin()._M_nxt = nullptr;
+ this->_M_before_begin()._M_nxt = nullptr;
clear();
this->_M_insert_range(__l.begin(), __l.end(), __roan);
return *this;
@@ -501,7 +456,7 @@
void
swap(_Hashtable&)
- noexcept(_Node_alloc_traits::_S_nothrow_swap());
+ noexcept(__node_alloc_traits::_S_nothrow_swap());
// Basic container operations
iterator
@@ -538,11 +493,11 @@
allocator_type
get_allocator() const noexcept
- { return allocator_type(_M_node_allocator()); }
+ { return allocator_type(this->_M_node_allocator()); }
size_type
max_size() const noexcept
- { return _Node_alloc_traits::max_size(_M_node_allocator()); }
+ { return __node_alloc_traits::max_size(this->_M_node_allocator()); }
// Observers
key_equal
@@ -807,101 +762,6 @@
typename _Alloc, typename _ExtractKey, typename _Equal,
typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
typename _Traits>
- template<typename... _Args>
- typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::__node_type*
- _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
- _M_allocate_node(_Args&&... __args)
- {
- auto __nptr = _Node_alloc_traits::allocate(_M_node_allocator(), 1);
- __node_type* __n = std::__addressof(*__nptr);
- __try
- {
- _Value_alloc_type __a(_M_node_allocator());
- ::new ((void*)__n) __node_type();
- _Value_alloc_traits::construct(__a, __n->_M_valptr(),
- std::forward<_Args>(__args)...);
- return __n;
- }
- __catch(...)
- {
- _Node_alloc_traits::deallocate(_M_node_allocator(), __nptr, 1);
- __throw_exception_again;
- }
- }
-
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
- void
- _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
- _M_deallocate_node(__node_type* __n)
- {
- typedef typename _Node_alloc_traits::pointer _Ptr;
- auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__n);
- _Value_alloc_type __a(_M_node_allocator());
- _Value_alloc_traits::destroy(__a, __n->_M_valptr());
- __n->~__node_type();
- _Node_alloc_traits::deallocate(_M_node_allocator(), __ptr, 1);
- }
-
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
- void
- _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
- _M_deallocate_nodes(__node_type* __n)
- {
- while (__n)
- {
- __node_type* __tmp = __n;
- __n = __n->_M_next();
- _M_deallocate_node(__tmp);
- }
- }
-
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
- typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::__bucket_type*
- _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
- _M_allocate_buckets(size_type __n)
- {
- _Bucket_alloc_type __alloc(_M_node_allocator());
-
- auto __ptr = _Bucket_alloc_traits::allocate(__alloc, __n);
- __bucket_type* __p = std::__addressof(*__ptr);
- __builtin_memset(__p, 0, __n * sizeof(__bucket_type));
- return __p;
- }
-
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
- void
- _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _H1, _H2, _Hash, _RehashPolicy, _Traits>::
- _M_deallocate_buckets(__bucket_type* __bkts, size_type __n)
- {
- typedef typename _Bucket_alloc_traits::pointer _Ptr;
- auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__bkts);
- _Bucket_alloc_type __alloc(_M_node_allocator());
- _Bucket_alloc_traits::deallocate(__alloc, __ptr, __n);
- }
-
- template<typename _Key, typename _Value,
- typename _Alloc, typename _ExtractKey, typename _Equal,
- typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
- typename _Traits>
typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
_Equal, _H1, _H2, _Hash, _RehashPolicy,
_Traits>::__node_type*
@@ -926,12 +786,12 @@
: __hashtable_base(__exk, __h1, __h2, __h, __eq),
__map_base(),
__rehash_base(),
- _M_bbegin(__a),
+ __hashtable_alloc(__node_alloc_type(__a)),
_M_element_count(0),
_M_rehash_policy()
{
_M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
- _M_buckets = _M_allocate_buckets(_M_bucket_count);
+ _M_buckets = this->_M_allocate_buckets(_M_bucket_count);
}
template<typename _Key, typename _Value,
@@ -949,7 +809,7 @@
: __hashtable_base(__exk, __h1, __h2, __h, __eq),
__map_base(),
__rehash_base(),
- _M_bbegin(__a),
+ __hashtable_alloc(__node_alloc_type(__a)),
_M_element_count(0),
_M_rehash_policy()
{
@@ -959,7 +819,7 @@
std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
__bucket_hint));
- _M_buckets = _M_allocate_buckets(_M_bucket_count);
+ _M_buckets = this->_M_allocate_buckets(_M_bucket_count);
__try
{
for (; __f != __l; ++__f)
@@ -987,15 +847,15 @@
if (&__ht == this)
return *this;
- if (_Node_alloc_traits::_S_propagate_on_copy_assign())
+ if (__node_alloc_traits::_S_propagate_on_copy_assign())
{
auto& __this_alloc = this->_M_node_allocator();
auto& __that_alloc = __ht._M_node_allocator();
- if (!_Node_alloc_traits::_S_always_equal()
+ if (!__node_alloc_traits::_S_always_equal()
&& __this_alloc != __that_alloc)
{
// Replacement allocator cannot free existing storage.
- _M_deallocate_nodes(_M_begin());
+ this->_M_deallocate_nodes(_M_begin());
if (__builtin_expect(_M_bucket_count != 0, true))
_M_deallocate_buckets();
_M_reset();
@@ -1008,7 +868,7 @@
{
_M_assign(__ht,
[this](const __node_type* __n)
- { return _M_allocate_node(__n->_M_v()); });
+ { return this->_M_allocate_node(__n->_M_v()); });
}
__catch(...)
{
@@ -1030,7 +890,7 @@
if (_M_bucket_count != __ht._M_bucket_count)
{
__former_buckets = _M_buckets;
- _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
+ _M_buckets = this->_M_allocate_buckets(__ht._M_bucket_count);
_M_bucket_count = __ht._M_bucket_count;
}
else
@@ -1043,12 +903,13 @@
_M_element_count = __ht._M_element_count;
_M_rehash_policy = __ht._M_rehash_policy;
__reuse_or_alloc_node_type __roan(_M_begin(), *this);
- _M_before_begin()._M_nxt = nullptr;
+ this->_M_before_begin()._M_nxt = nullptr;
_M_assign(__ht,
[&__roan](const __node_type* __n)
{ return __roan(__n->_M_v()); });
if (__former_buckets)
- _M_deallocate_buckets(__former_buckets, __former_bucket_count);
+ this->_M_deallocate_buckets(__former_buckets,
+ __former_bucket_count);
}
__catch(...)
{
@@ -1079,7 +940,7 @@
{
__bucket_type* __buckets = nullptr;
if (!_M_buckets)
- _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
+ _M_buckets = __buckets = this->_M_allocate_buckets(_M_bucket_count);
__try
{
@@ -1091,8 +952,8 @@
__node_type* __ht_n = __ht._M_begin();
__node_type* __this_n = __node_gen(__ht_n);
this->_M_copy_code(__this_n, __ht_n);
- _M_before_begin()._M_nxt = __this_n;
- _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin();
+ this->_M_before_begin()._M_nxt = __this_n;
+ _M_buckets[_M_bucket_index(__this_n)] = &this->_M_before_begin();
// Then deal with other nodes.
__node_base* __prev_n = __this_n;
@@ -1128,7 +989,7 @@
_M_rehash_policy._M_reset();
_M_bucket_count = 0;
_M_buckets = nullptr;
- _M_before_begin()._M_nxt = nullptr;
+ this->_M_before_begin()._M_nxt = nullptr;
_M_element_count = 0;
}
@@ -1141,7 +1002,7 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
_M_move_assign(_Hashtable&& __ht, std::true_type)
{
- _M_deallocate_nodes(_M_begin());
+ this->_M_deallocate_nodes(_M_begin());
if (__builtin_expect(_M_bucket_count != 0, true))
_M_deallocate_buckets();
@@ -1149,14 +1010,14 @@
_M_rehash_policy = __ht._M_rehash_policy;
_M_buckets = __ht._M_buckets;
_M_bucket_count = __ht._M_bucket_count;
- _M_before_begin()._M_nxt = __ht._M_before_begin()._M_nxt;
+ this->_M_before_begin()._M_nxt = __ht._M_before_begin()._M_nxt;
_M_element_count = __ht._M_element_count;
- std::__alloc_on_move(_M_node_allocator(), __ht._M_node_allocator());
+ std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator());
// Fix buckets containing the _M_before_begin pointers that can't be
// moved.
if (_M_begin())
- _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin();
+ _M_buckets[_M_bucket_index(_M_begin())] = &this->_M_before_begin();
__ht._M_reset();
}
@@ -1169,7 +1030,7 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
_M_move_assign(_Hashtable&& __ht, std::false_type)
{
- if (__ht._M_node_allocator() == _M_node_allocator())
+ if (__ht._M_node_allocator() == this->_M_node_allocator())
_M_move_assign(std::move(__ht), std::true_type());
else
{
@@ -1181,7 +1042,7 @@
if (_M_bucket_count != __ht._M_bucket_count)
{
__former_buckets = _M_buckets;
- _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
+ _M_buckets = this->_M_allocate_buckets(__ht._M_bucket_count);
_M_bucket_count = __ht._M_bucket_count;
}
else
@@ -1194,7 +1055,7 @@
_M_element_count = __ht._M_element_count;
_M_rehash_policy = __ht._M_rehash_policy;
__reuse_or_alloc_node_type __roan(_M_begin(), *this);
- _M_before_begin()._M_nxt = nullptr;
+ this->_M_before_begin()._M_nxt = nullptr;
_M_assign(__ht,
[&__roan](__node_type* __n)
{ return __roan(std::move_if_noexcept(__n->_M_v())); });
@@ -1226,16 +1087,16 @@
: __hashtable_base(__ht),
__map_base(__ht),
__rehash_base(__ht),
+ __hashtable_alloc(
+ __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
_M_buckets(),
_M_bucket_count(__ht._M_bucket_count),
- _M_bbegin(_Node_alloc_traits::_S_select_on_copy(
- __ht._M_node_allocator())),
_M_element_count(__ht._M_element_count),
_M_rehash_policy(__ht._M_rehash_policy)
{
_M_assign(__ht,
[this](const __node_type* __n)
- { return _M_allocate_node(__n->_M_v()); });
+ { return this->_M_allocate_node(__n->_M_v()); });
}
template<typename _Key, typename _Value,
@@ -1248,16 +1109,16 @@
: __hashtable_base(__ht),
__map_base(__ht),
__rehash_base(__ht),
+ __hashtable_alloc(std::move(__ht._M_base_alloc())),
_M_buckets(__ht._M_buckets),
_M_bucket_count(__ht._M_bucket_count),
- _M_bbegin(std::move(__ht._M_bbegin)),
_M_element_count(__ht._M_element_count),
_M_rehash_policy(__ht._M_rehash_policy)
{
// Update, if necessary, bucket pointing to before begin that hasn't
// moved.
if (_M_begin())
- _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin();
+ _M_buckets[_M_bucket_index(_M_begin())] = &this->_M_before_begin();
__ht._M_reset();
}
@@ -1271,15 +1132,15 @@
: __hashtable_base(__ht),
__map_base(__ht),
__rehash_base(__ht),
+ __hashtable_alloc(__node_alloc_type(__a)),
_M_buckets(),
_M_bucket_count(__ht._M_bucket_count),
- _M_bbegin(_Node_alloc_type(__a)),
_M_element_count(__ht._M_element_count),
_M_rehash_policy(__ht._M_rehash_policy)
{
_M_assign(__ht,
[this](const __node_type* __n)
- { return _M_allocate_node(__n->_M_v()); });
+ { return this->_M_allocate_node(__n->_M_v()); });
}
template<typename _Key, typename _Value,
@@ -1292,20 +1153,20 @@
: __hashtable_base(__ht),
__map_base(__ht),
__rehash_base(__ht),
+ __hashtable_alloc(__node_alloc_type(__a)),
_M_buckets(),
_M_bucket_count(__ht._M_bucket_count),
- _M_bbegin(_Node_alloc_type(__a)),
_M_element_count(__ht._M_element_count),
_M_rehash_policy(__ht._M_rehash_policy)
{
- if (__ht._M_node_allocator() == _M_node_allocator())
+ if (__ht._M_node_allocator() == this->_M_node_allocator())
{
_M_buckets = __ht._M_buckets;
- _M_before_begin()._M_nxt = __ht._M_before_begin()._M_nxt;
+ this->_M_before_begin()._M_nxt = __ht._M_before_begin()._M_nxt;
// Update, if necessary, bucket pointing to before begin that hasn't
// moved.
if (_M_begin())
- _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin();
+ _M_buckets[_M_bucket_index(_M_begin())] = &this->_M_before_begin();
__ht._M_reset();
}
else
@@ -1313,7 +1174,7 @@
_M_assign(__ht,
[this](__node_type* __n)
{
- return _M_allocate_node(
+ return this->_M_allocate_node(
std::move_if_noexcept(__n->_M_v()));
});
__ht.clear();
@@ -1341,24 +1202,24 @@
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
swap(_Hashtable& __x)
- noexcept(_Node_alloc_traits::_S_nothrow_swap())
+ noexcept(__node_alloc_traits::_S_nothrow_swap())
{
// The only base class with member variables is hash_code_base.
// We define _Hash_code_base::_M_swap because different
// specializations have different members.
this->_M_swap(__x);
- std::__alloc_on_swap(_M_node_allocator(), __x._M_node_allocator());
+ std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
std::swap(_M_rehash_policy, __x._M_rehash_policy);
std::swap(_M_buckets, __x._M_buckets);
std::swap(_M_bucket_count, __x._M_bucket_count);
- std::swap(_M_before_begin()._M_nxt, __x._M_before_begin()._M_nxt);
+ std::swap(this->_M_before_begin()._M_nxt, __x._M_before_begin()._M_nxt);
std::swap(_M_element_count, __x._M_element_count);
// Fix buckets containing the _M_before_begin pointers that can't be
// swapped.
if (_M_begin())
- _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin();
+ _M_buckets[_M_bucket_index(_M_begin())] = &this->_M_before_begin();
if (__x._M_begin())
__x._M_buckets[__x._M_bucket_index(__x._M_begin())]
= &(__x._M_before_begin());
@@ -1580,13 +1441,13 @@
// The bucket is empty, the new node is inserted at the
// beginning of the singly-linked list and the bucket will
// contain _M_before_begin pointer.
- __node->_M_nxt = _M_before_begin()._M_nxt;
- _M_before_begin()._M_nxt = __node;
+ __node->_M_nxt = this->_M_before_begin()._M_nxt;
+ this->_M_before_begin()._M_nxt = __node;
if (__node->_M_nxt)
// We must update former begin bucket that is pointing to
// _M_before_begin.
_M_buckets[_M_bucket_index(__node->_M_next())] = __node;
- _M_buckets[__bkt] = &_M_before_begin();
+ _M_buckets[__bkt] = &this->_M_before_begin();
}
}
@@ -1608,8 +1469,8 @@
_M_buckets[__next_bkt] = _M_buckets[__bkt];
// Second update before begin node if necessary
- if (&_M_before_begin() == _M_buckets[__bkt])
- _M_before_begin()._M_nxt = __next;
+ if (&this->_M_before_begin() == _M_buckets[__bkt])
+ this->_M_before_begin()._M_nxt = __next;
_M_buckets[__bkt] = nullptr;
}
}
@@ -1645,7 +1506,7 @@
_M_emplace(std::true_type, _Args&&... __args)
{
// First build the node to get access to the hash code
- __node_type* __node = _M_allocate_node(std::forward<_Args>(__args)...);
+ __node_type* __node = this->_M_allocate_node(std::forward<_Args>(__args)...);
const key_type& __k = this->_M_extract()(__node->_M_v());
__hash_code __code;
__try
@@ -1654,7 +1515,7 @@
}
__catch(...)
{
- _M_deallocate_node(__node);
+ this->_M_deallocate_node(__node);
__throw_exception_again;
}
@@ -1662,7 +1523,7 @@
if (__node_type* __p = _M_find_node(__bkt, __k, __code))
{
// There is already an equivalent node, no insertion
- _M_deallocate_node(__node);
+ this->_M_deallocate_node(__node);
return std::make_pair(iterator(__p), false);
}
@@ -1684,7 +1545,8 @@
_M_emplace(const_iterator __hint, std::false_type, _Args&&... __args)
{
// First build the node to get its hash code.
- __node_type* __node = _M_allocate_node(std::forward<_Args>(__args)...);
+ __node_type* __node =
+ this->_M_allocate_node(std::forward<_Args>(__args)...);
__hash_code __code;
__try
@@ -1693,7 +1555,7 @@
}
__catch(...)
{
- _M_deallocate_node(__node);
+ this->_M_deallocate_node(__node);
__throw_exception_again;
}
@@ -1733,7 +1595,7 @@
}
__catch(...)
{
- _M_deallocate_node(__node);
+ this->_M_deallocate_node(__node);
__throw_exception_again;
}
}
@@ -1799,7 +1661,7 @@
}
__catch(...)
{
- _M_deallocate_node(__node);
+ this->_M_deallocate_node(__node);
__throw_exception_again;
}
}
@@ -1899,7 +1761,7 @@
__prev_n->_M_nxt = __n->_M_nxt;
iterator __result(__n->_M_next());
- _M_deallocate_node(__n);
+ this->_M_deallocate_node(__n);
--_M_element_count;
return __result;
@@ -1972,7 +1834,7 @@
do
{
__node_type* __p = __n->_M_next();
- _M_deallocate_node(__n);
+ this->_M_deallocate_node(__n);
__n = __p;
++__result;
--_M_element_count;
@@ -2014,7 +1876,7 @@
{
__node_type* __tmp = __n;
__n = __n->_M_next();
- _M_deallocate_node(__tmp);
+ this->_M_deallocate_node(__tmp);
--_M_element_count;
if (!__n)
break;
@@ -2044,10 +1906,10 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
clear() noexcept
{
- _M_deallocate_nodes(_M_begin());
+ this->_M_deallocate_nodes(_M_begin());
__builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(__bucket_type));
_M_element_count = 0;
- _M_before_begin()._M_nxt = nullptr;
+ this->_M_before_begin()._M_nxt = nullptr;
}
template<typename _Key, typename _Value,
@@ -2104,9 +1966,9 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
_M_rehash_aux(size_type __n, std::true_type)
{
- __bucket_type* __new_buckets = _M_allocate_buckets(__n);
+ __bucket_type* __new_buckets = this->_M_allocate_buckets(__n);
__node_type* __p = _M_begin();
- _M_before_begin()._M_nxt = nullptr;
+ this->_M_before_begin()._M_nxt = nullptr;
std::size_t __bbegin_bkt = 0;
while (__p)
{
@@ -2114,9 +1976,9 @@
std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
if (!__new_buckets[__bkt])
{
- __p->_M_nxt = _M_before_begin()._M_nxt;
- _M_before_begin()._M_nxt = __p;
- __new_buckets[__bkt] = &_M_before_begin();
+ __p->_M_nxt = this->_M_before_begin()._M_nxt;
+ this->_M_before_begin()._M_nxt = __p;
+ __new_buckets[__bkt] = &this->_M_before_begin();
if (__p->_M_nxt)
__new_buckets[__bbegin_bkt] = __p;
__bbegin_bkt = __bkt;
@@ -2146,10 +2008,10 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
_M_rehash_aux(size_type __n, std::false_type)
{
- __bucket_type* __new_buckets = _M_allocate_buckets(__n);
+ __bucket_type* __new_buckets = this->_M_allocate_buckets(__n);
__node_type* __p = _M_begin();
- _M_before_begin()._M_nxt = nullptr;
+ this->_M_before_begin()._M_nxt = nullptr;
std::size_t __bbegin_bkt = 0;
std::size_t __prev_bkt = 0;
__node_type* __prev_p = nullptr;
@@ -2194,9 +2056,9 @@
if (!__new_buckets[__bkt])
{
- __p->_M_nxt = _M_before_begin()._M_nxt;
- _M_before_begin()._M_nxt = __p;
- __new_buckets[__bkt] = &_M_before_begin();
+ __p->_M_nxt = this->_M_before_begin()._M_nxt;
+ this->_M_before_begin()._M_nxt = __p;
+ __new_buckets[__bkt] = &this->_M_before_begin();
if (__p->_M_nxt)
__new_buckets[__bbegin_bkt] = __p;
__bbegin_bkt = __bkt;
Index: testsuite/23_containers/unordered_set/instantiation_neg.cc
===================================================================
--- testsuite/23_containers/unordered_set/instantiation_neg.cc (revision 200963)
+++ testsuite/23_containers/unordered_set/instantiation_neg.cc (working copy)
@@ -19,7 +19,7 @@
// with this library; see the file COPYING3. If not see
// <http://www.gnu.org/licenses/>.
-// { dg-error "with noexcept" "" { target *-*-* } 258 }
+// { dg-error "with noexcept" "" { target *-*-* } 266 }
#include <unordered_set>
Index: testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc
===================================================================
--- testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc (revision 200963)
+++ testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc (working copy)
@@ -19,7 +19,7 @@
// with this library; see the file COPYING3. If not see
// <http://www.gnu.org/licenses/>.
-// { dg-error "default constructible" "" { target *-*-* } 276 }
+// { dg-error "default constructible" "" { target *-*-* } 284 }
#include <unordered_set>