This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: RE :Re: RE :Re: hashtable local iterator
- From: François Dumont <frs dot dumont at gmail dot com>
- To: Paolo Carlini <paolo dot carlini at oracle dot com>
- Cc: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>, gcc-patches at gcc dot gnu dot org
- Date: Thu, 29 Dec 2011 19:00:36 +0100
- Subject: Re: RE :Re: RE :Re: hashtable local iterator
- References: <178044935.53839.1324627267265.JavaMail.seven@ap8.p7.uk.7sys.net> <4EF5EBD5.1050600@gmail.com> <4EF9A797.30900@oracle.com> <4EFAE355.3050109@gmail.com> <alpine.DEB.2.02.1112281136440.2419@laptop-mg.saclay.inria.fr> <4EFB064D.1020207@oracle.com>
Attached patch applied.
2011-12-29 François Dumont <fdumont@gcc.gnu.org>
PR libstdc++/51608
* include/bits/hashtable_policy.h (_Equal_helper<>): New,
change the
way the _Equal functor is used depending on whether hash code is
cached or not.
(_Ebo_helper<>): New helper type to introduce EBO when possible.
(_Hash_code_base): Use _Ebo_helper to limit memory footprint. Move
_Equal functor management...
(_Hashtable_base): ...here, new, use _Equal_helper.
(_Local_iterator_base<>, _Locale_iterator<>,
_Locale_const_iterator<>):
New, use _Hash_code_base, implementation of...
* include/bits/hashtable.h (_Hashtable<>::local_iterator,
_Hashtable<>::const_local_iterator): ...those. Add static
assertions
checking that some functors are empty depending on whether hash
code
is cache or not.
(_Hashtable<>::_M_bucket_index): New overloads using current bucket
count, use through out the _Hastable<> implementation.
* include/bits/unordered_set.h (__unordered_set<>,
__unordered_multiset<>): Cache hash code iff hash functor is not
empty and not final.
* include/bits/unordered_map.h (__unordered_map<>,
__unordered_multimap<>): Likewise.
* include/debug/unordered_map
(unordered_map<>::_S_to_local, unordered_multimap<>::_S_to_local):
Adapt to match new local iterator implementation.
* include/debug/unordered_set (unordered_set<>::_S_to_local,
unordered_multiset<>::_S_to_local): Likewise.
* include/profile/unordered_map
(unordered_map<>::_M_profile_destruct,
unordered_multimap<>::_M_profile_destruct): Enhance thanks to
usage of
local iterators.
* include/profile/unordered_set
(unordered_set<>::_M_profile_destruct,
unordered_multiset<>::_M_profile_destruct): Likewise.
* testsuite_files/23_containers/unordered_set/instantiation_neg.cc:
Fix error line.
* testsuite_files/23_containers/unordered_set/final_hash.cc: New.
*
testsuite_files/23_containers/unordered_multiset/final_hash.cc: New.
* testsuite_files/23_containers/unordered_map/final_hash.cc: New.
*
testsuite_files/23_containers/unordered_multimap/final_hash.cc: New.
François
On 12/28/2011 01:06 PM, Paolo Carlini wrote:
On 12/28/2011 11:49 AM, Marc Glisse wrote:
it looks like (I haven't really checked) with _Ebo_helper we get
public inheritance all the way from unordered_set to
unary_function<_Value,_Value> (from _Identity). I don't think it
causes any issue, but do we maybe want a private inheritance
somewhere along the way?
(please don't let that prevent you from committing)
Yes, unless there are other more substantive issues, let's ho ahead
with the patch and close the PR, let's first make sure we don't have
this regression in the codebase. Then, Francois, consider Marc's
suggestion for a separate piece of work, which maybe could also at
once fix the comments in hashtable.h and elsewhere explicitly
mentioning unary_function, which actually is deprecated in C++11 and
can be at most an implementation detail.
Paolo.
Index: include/debug/unordered_map
===================================================================
--- include/debug/unordered_map (revision 182685)
+++ include/debug/unordered_map (working copy)
@@ -418,11 +418,19 @@
static _Base_local_iterator
_S_to_local(_Base_iterator __it)
- { return _Base_local_iterator(__it._M_cur); }
+ {
+ // The returned local iterator will not be incremented so we don't
+ // need to compute __it's node bucket
+ return _Base_local_iterator(__it._M_cur, 0, 0);
+ }
static _Base_const_local_iterator
_S_to_local(_Base_const_iterator __it)
- { return _Base_const_local_iterator(__it._M_cur); }
+ {
+ // The returned local iterator will not be incremented so we don't
+ // need to compute __it's node bucket
+ return _Base_const_local_iterator(__it._M_cur, 0, 0);
+ }
};
template<typename _Key, typename _Tp, typename _Hash,
@@ -820,11 +828,19 @@
static _Base_local_iterator
_S_to_local(_Base_iterator __it)
- { return _Base_local_iterator(__it._M_cur); }
+ {
+ // The returned local iterator will not be incremented so we don't
+ // need to compute __it's node bucket
+ return _Base_local_iterator(__it._M_cur, 0, 0);
+ }
static _Base_const_local_iterator
_S_to_local(_Base_const_iterator __it)
- { return _Base_const_local_iterator(__it._M_cur); }
+ {
+ // The returned local iterator will not be incremented so we don't
+ // need to compute __it's node bucket
+ return _Base_const_local_iterator(__it._M_cur, 0, 0);
+ }
};
template<typename _Key, typename _Tp, typename _Hash,
Index: include/debug/unordered_set
===================================================================
--- include/debug/unordered_set (revision 182685)
+++ include/debug/unordered_set (working copy)
@@ -417,11 +417,19 @@
static _Base_local_iterator
_S_to_local(_Base_iterator __it)
- { return _Base_local_iterator(__it._M_cur); }
+ {
+ // The returned local iterator will not be incremented so we don't
+ // need to compute __it's node bucket
+ return _Base_local_iterator(__it._M_cur, 0, 0);
+ }
static _Base_const_local_iterator
_S_to_local(_Base_const_iterator __it)
- { return _Base_const_local_iterator(__it._M_cur); }
+ {
+ // The returned local iterator will not be incremented so we don't
+ // need to compute __it's node bucket
+ return _Base_const_local_iterator(__it._M_cur, 0, 0);
+ }
};
template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
@@ -805,11 +813,19 @@
static _Base_local_iterator
_S_to_local(_Base_iterator __it)
- { return _Base_local_iterator(__it._M_cur); }
+ {
+ // The returned local iterator will not be incremented so we don't
+ // need to compute __it's node bucket
+ return _Base_local_iterator(__it._M_cur, 0, 0);
+ }
static _Base_const_local_iterator
_S_to_local(_Base_const_iterator __it)
- { return _Base_const_local_iterator(__it._M_cur); }
+ {
+ // The returned local iterator will not be incremented so we don't
+ // need to compute __it's node bucket
+ return _Base_const_local_iterator(__it._M_cur, 0, 0);
+ }
};
template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
Index: include/profile/unordered_map
===================================================================
--- include/profile/unordered_map (revision 182685)
+++ include/profile/unordered_map (working copy)
@@ -308,9 +308,9 @@
while (__it != this->end())
{
size_type __bkt = this->bucket(__it->first);
- for (++__it; __it != this->end()
- && this->bucket(__it->first) == __bkt;
- ++__it)
+ auto __lit = this->begin(__bkt);
+ auto __lend = this->end(__bkt);
+ for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
++__chain;
if (__chain)
{
@@ -577,9 +577,9 @@
while (__it != this->end())
{
size_type __bkt = this->bucket(__it->first);
- for (++__it; __it != this->end()
- && this->bucket(__it->first) == __bkt;
- ++__it)
+ auto __lit = this->begin(__bkt);
+ auto __lend = this->end(__bkt);
+ for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
++__chain;
if (__chain)
{
Index: include/profile/unordered_set
===================================================================
--- include/profile/unordered_set (revision 182685)
+++ include/profile/unordered_set (working copy)
@@ -277,10 +277,10 @@
while (__it != this->end())
{
size_type __bkt = this->bucket(*__it);
- for (++__it; __it != this->end() && this->bucket(*__it) == __bkt;
- ++__it)
+ auto __lit = this->begin(__bkt);
+ auto __lend = this->end(__bkt);
+ for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
++__chain;
-
if (__chain)
{
++__chain;
@@ -539,10 +539,10 @@
while (__it != this->end())
{
size_type __bkt = this->bucket(*__it);
- for (++__it; __it != this->end() && this->bucket(*__it) == __bkt;
- ++__it)
+ auto __lit = this->begin(__bkt);
+ auto __lend = this->end(__bkt);
+ for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
++__chain;
-
if (__chain)
{
++__chain;
Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h (revision 182685)
+++ include/bits/hashtable.h (working copy)
@@ -155,7 +155,7 @@
__cache_hash_code,
__constant_iterators,
__unique_keys> >,
- public __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
+ public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
_H1, _H2, _Hash, __cache_hash_code>,
public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys,
_Hashtable<_Key, _Value, _Allocator,
@@ -174,9 +174,37 @@
__constant_iterators,
__unique_keys> >
{
- static_assert(__or_<integral_constant<bool, __cache_hash_code>,
- __detail::__is_noexcept_hash<_Key, _H1>>::value,
+ template<typename _Cond>
+ using __if_hash_code_cached
+ = __or_<__not_<integral_constant<bool, __cache_hash_code>>, _Cond>;
+
+ template<typename _Cond>
+ using __if_hash_code_not_cached
+ = __or_<integral_constant<bool, __cache_hash_code>, _Cond>;
+
+ static_assert(__if_hash_code_not_cached<__detail::__is_noexcept_hash<_Key,
+ _H1>>::value,
"Cache the hash code or qualify your hash functor with noexcept");
+
+ // Following two static assertions are necessary to guarantee that
+ // swapping two hashtable instances won't invalidate associated local
+ // iterators.
+
+ // When hash codes are cached local iterator only uses H2 which must then
+ // be empty.
+ static_assert(__if_hash_code_cached<is_empty<_H2>>::value,
+ "Functor used to map hash code to bucket index must be empty");
+
+ typedef __detail::_Hash_code_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash,
+ __cache_hash_code> _HCBase;
+
+ // When hash codes are not cached local iterator is going to use _HCBase
+ // above to compute node bucket index so it has to be empty.
+ static_assert(__if_hash_code_not_cached<is_empty<_HCBase>>::value,
+ "Cache the hash code or make functors involved in hash code"
+ " and bucket index computation empty");
+
public:
typedef _Allocator allocator_type;
typedef _Value value_type;
@@ -191,17 +219,24 @@
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
+ typedef __detail::_Local_iterator<key_type, value_type, _ExtractKey,
+ _H1, _H2, _Hash,
+ __constant_iterators,
+ __cache_hash_code>
+ local_iterator;
+ typedef __detail::_Local_const_iterator<key_type, value_type, _ExtractKey,
+ _H1, _H2, _Hash,
+ __constant_iterators,
+ __cache_hash_code>
+ const_local_iterator;
typedef __detail::_Node_iterator<value_type, __constant_iterators,
__cache_hash_code>
- local_iterator;
+ iterator;
typedef __detail::_Node_const_iterator<value_type,
__constant_iterators,
__cache_hash_code>
- const_local_iterator;
+ const_iterator;
- typedef local_iterator iterator;
- typedef const_local_iterator const_iterator;
-
template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2,
typename _Hashtable2>
friend struct __detail::_Map_base;
@@ -212,7 +247,6 @@
typedef typename _Allocator::template rebind<_Node>::other
_Node_allocator_type;
typedef _Node* _Bucket;
- //typedef __detail::_Bucket<_Value, __cache_hash_code> _Bucket;
typedef typename _Allocator::template rebind<_Bucket>::other
_Bucket_allocator_type;
@@ -253,14 +287,6 @@
_Node*
_M_bucket_end(size_type __bkt) const;
- // Gets the bucket node after the last if any
- _Node*
- _M_bucket_past_the_end(size_type __bkt) const
- {
- _Node* __end = _M_bucket_end(__bkt);
- return __end ? __end->_M_next : nullptr;
- }
-
public:
// Constructor, destructor, assignment, swap
_Hashtable(size_type __bucket_hint,
@@ -364,35 +390,35 @@
size_type
bucket(const key_type& __k) const
- {
- return this->_M_bucket_index(__k, this->_M_hash_code(__k),
- bucket_count());
- }
+ { return _M_bucket_index(__k, this->_M_hash_code(__k)); }
local_iterator
begin(size_type __n)
- { return local_iterator(_M_bucket_begin(__n)); }
+ { return local_iterator(_M_bucket_begin(__n), __n,
+ _M_bucket_count); }
local_iterator
end(size_type __n)
- { return local_iterator(_M_bucket_past_the_end(__n)); }
+ { return local_iterator(nullptr, __n, _M_bucket_count); }
const_local_iterator
begin(size_type __n) const
- { return const_local_iterator(_M_bucket_begin(__n)); }
+ { return const_local_iterator(_M_bucket_begin(__n), __n,
+ _M_bucket_count); }
const_local_iterator
end(size_type __n) const
- { return const_local_iterator(_M_bucket_past_the_end(__n)); }
+ { return const_local_iterator(nullptr, __n, _M_bucket_count); }
// DR 691.
const_local_iterator
cbegin(size_type __n) const
- { return const_local_iterator(_M_bucket_begin(__n)); }
+ { return const_local_iterator(_M_bucket_begin(__n), __n,
+ _M_bucket_count); }
const_local_iterator
cend(size_type __n) const
- { return const_local_iterator(_M_bucket_past_the_end(__n)); }
+ { return const_local_iterator(nullptr, __n, _M_bucket_count); }
float
load_factor() const noexcept
@@ -428,6 +454,15 @@
equal_range(const key_type& __k) const;
private:
+ size_type
+ _M_bucket_index(_Node* __n) const
+ { return _HCBase::_M_bucket_index(__n, _M_bucket_count); }
+
+ size_type
+ _M_bucket_index(const key_type& __k,
+ typename _Hashtable::_Hash_code_type __c) const
+ { return _HCBase::_M_bucket_index(__k, __c, _M_bucket_count); }
+
// Find and insert helper functions and types
_Node*
_M_find_node(size_type, const key_type&,
@@ -679,9 +714,7 @@
_Node* __n = _M_bucket_begin(__bkt);
if (__n)
for (;; __n = __n->_M_next)
- if (!__n->_M_next
- || this->_M_bucket_index(__n->_M_next, _M_bucket_count)
- != __bkt)
+ if (!__n->_M_next || _M_bucket_index(__n->_M_next) != __bkt)
break;
return __n;
}
@@ -697,9 +730,9 @@
const _Equal& __eq, const _ExtractKey& __exk,
const allocator_type& __a)
: __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
- __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
- _H1, _H2, _Hash, __chc>(__exk, __eq,
- __h1, __h2, __h),
+ __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
+ _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h,
+ __eq),
__detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
_M_node_allocator(__a),
_M_bucket_count(0),
@@ -727,9 +760,9 @@
const _Equal& __eq, const _ExtractKey& __exk,
const allocator_type& __a)
: __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
- __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
- _H1, _H2, _Hash, __chc>(__exk, __eq,
- __h1, __h2, __h),
+ __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
+ _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h,
+ __eq),
__detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
_M_node_allocator(__a),
_M_bucket_count(0),
@@ -768,7 +801,7 @@
_H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
_Hashtable(const _Hashtable& __ht)
: __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
- __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
+ __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
_H1, _H2, _Hash, __chc>(__ht),
__detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
_M_node_allocator(__ht._M_node_allocator),
@@ -833,7 +866,7 @@
_H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
_Hashtable(_Hashtable&& __ht)
: __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
- __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
+ __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
_H1, _H2, _Hash, __chc>(__ht),
__detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
_M_node_allocator(std::move(__ht._M_node_allocator)),
@@ -874,8 +907,7 @@
// The only base class with member variables is hash_code_base. We
// define _Hash_code_base::_M_swap because different specializations
// have different members.
- __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
- _H1, _H2, _Hash, __chc>::_M_swap(__x);
+ this->_M_swap(__x);
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 431. Swapping containers with unequal allocators.
@@ -916,7 +948,7 @@
find(const key_type& __k)
{
typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
- std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+ std::size_t __n = _M_bucket_index(__k, __code);
_Node* __p = _M_find_node(__n, __k, __code);
return __p ? iterator(__p) : this->end();
}
@@ -933,7 +965,7 @@
find(const key_type& __k) const
{
typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
- std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+ std::size_t __n = _M_bucket_index(__k, __code);
_Node* __p = _M_find_node(__n, __k, __code);
return __p ? const_iterator(__p) : this->end();
}
@@ -950,7 +982,7 @@
count(const key_type& __k) const
{
typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
- std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+ std::size_t __n = _M_bucket_index(__k, __code);
_Node* __p = _M_bucket_begin(__n);
if (!__p)
return 0;
@@ -958,16 +990,14 @@
std::size_t __result = 0;
for (;; __p = __p->_M_next)
{
- if (this->_M_compare(__k, __code, __p))
+ if (this->_M_equals(__k, __code, __p))
++__result;
else if (__result)
// All equivalent values are next to each other, if we found a not
// equivalent value after an equivalent one it means that we won't
// find anymore an equivalent value.
break;
- if (!__p->_M_next
- || this->_M_bucket_index(__p->_M_next, _M_bucket_count)
- != __n)
+ if (!__p->_M_next || _M_bucket_index(__p->_M_next) != __n)
break;
}
return __result;
@@ -990,15 +1020,14 @@
equal_range(const key_type& __k)
{
typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
- std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+ std::size_t __n = _M_bucket_index(__k, __code);
_Node* __p = _M_find_node(__n, __k, __code);
if (__p)
{
_Node* __p1 = __p->_M_next;
- while (__p1
- && this->_M_bucket_index(__p1, _M_bucket_count) == __n
- && this->_M_compare(__k, __code, __p1))
+ while (__p1 && _M_bucket_index(__p1) == __n
+ && this->_M_equals(__k, __code, __p1))
__p1 = __p1->_M_next;
return std::make_pair(iterator(__p), iterator(__p1));
@@ -1024,15 +1053,14 @@
equal_range(const key_type& __k) const
{
typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
- std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+ std::size_t __n = _M_bucket_index(__k, __code);
_Node* __p = _M_find_node(__n, __k, __code);
if (__p)
{
_Node* __p1 = __p->_M_next;
- while (__p1
- && this->_M_bucket_index(__p1, _M_bucket_count) == __n
- && this->_M_compare(__k, __code, __p1))
+ while (__p1 && _M_bucket_index(__p1) == __n
+ && this->_M_equals(__k, __code, __p1))
__p1 = __p1->_M_next;
return std::make_pair(const_iterator(__p), const_iterator(__p1));
@@ -1060,10 +1088,9 @@
return nullptr;
for (;; __p = __p->_M_next)
{
- if (this->_M_compare(__k, __code, __p))
+ if (this->_M_equals(__k, __code, __p))
return __p;
- if (!(__p->_M_next)
- || this->_M_bucket_index(__p->_M_next, _M_bucket_count) != __n)
+ if (!(__p->_M_next) || _M_bucket_index(__p->_M_next) != __n)
break;
}
return nullptr;
@@ -1119,8 +1146,7 @@
{
if (__prev_n->_M_next)
{
- size_type __next_bkt =
- this->_M_bucket_index(__prev_n->_M_next, _M_bucket_count);
+ size_type __next_bkt = _M_bucket_index(__prev_n->_M_next);
if (__next_bkt != __bkt)
_M_buckets[__next_bkt] = __new_n;
}
@@ -1196,11 +1222,10 @@
_Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
__try
{
- const key_type& __k = this->_M_extract(__new_node->_M_v);
+ const key_type& __k = this->_M_extract()(__new_node->_M_v);
typename _Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k);
- size_type __bkt
- = this->_M_bucket_index(__k, __code, _M_bucket_count);
+ size_type __bkt = _M_bucket_index(__k, __code);
if (_Node* __p = _M_find_node(__bkt, __k, __code))
{
@@ -1220,7 +1245,7 @@
if (__do_rehash.first)
{
_M_rehash(__do_rehash.second, __saved_state);
- __bkt = this->_M_bucket_index(__k, __code, _M_bucket_count);
+ __bkt = _M_bucket_index(__k, __code);
}
if (_M_buckets[__bkt])
@@ -1258,12 +1283,11 @@
_Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
__try
{
- const key_type& __k = this->_M_extract(__new_node->_M_v);
+ const key_type& __k = this->_M_extract()(__new_node->_M_v);
typename _Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k);
this->_M_store_code(__new_node, __code);
- size_type __bkt
- = this->_M_bucket_index(__k, __code, _M_bucket_count);
+ size_type __bkt = _M_bucket_index(__k, __code);
// Second find the node, avoid rehash if compare throws.
_Node* __prev = _M_find_node(__bkt, __k, __code);
@@ -1271,7 +1295,7 @@
if (__do_rehash.first)
{
_M_rehash(__do_rehash.second, __saved_state);
- __bkt = this->_M_bucket_index(__k, __code, _M_bucket_count);
+ __bkt = _M_bucket_index(__k, __code);
// __prev is still valid because rehash do not invalidate nodes
}
@@ -1322,8 +1346,8 @@
if (__do_rehash.first)
{
- const key_type& __k = this->_M_extract(__v);
- __n = this->_M_bucket_index(__k, __code, __do_rehash.second);
+ const key_type& __k = this->_M_extract()(__v);
+ __n = _HCBase::_M_bucket_index(__k, __code, __do_rehash.second);
}
_Node* __new_node = nullptr;
@@ -1367,9 +1391,9 @@
_H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
_M_insert(_Arg&& __v, std::true_type)
{
- const key_type& __k = this->_M_extract(__v);
+ const key_type& __k = this->_M_extract()(__v);
typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
- size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+ size_type __n = _M_bucket_index(__k, __code);
if (_Node* __p = _M_find_node(__n, __k, __code))
return std::make_pair(iterator(__p), false);
@@ -1395,9 +1419,9 @@
= _M_rehash_policy._M_need_rehash(_M_bucket_count,
_M_element_count, 1);
- const key_type& __k = this->_M_extract(__v);
+ const key_type& __k = this->_M_extract()(__v);
typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
- size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+ size_type __n = _M_bucket_index(__k, __code);
// First find the node, avoid leaking new_node if compare throws.
_Node* __prev = _M_find_node(__n, __k, __code);
@@ -1410,7 +1434,7 @@
if (__do_rehash.first)
{
_M_rehash(__do_rehash.second, __saved_state);
- __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+ __n = _M_bucket_index(__k, __code);
// __prev is still valid because rehash do not invalidate nodes
}
@@ -1477,7 +1501,7 @@
erase(const_iterator __it)
{
_Node* __n = __it._M_cur;
- std::size_t __bkt = this->_M_bucket_index(__n, _M_bucket_count);
+ std::size_t __bkt = _M_bucket_index(__n);
// Look for previous node to unlink it from the erased one, this is why
// we need buckets to contain the before begin node of the bucket to make
@@ -1485,12 +1509,10 @@
_Node* __prev_n = _M_get_previous_node(__bkt, __n);
if (__n == _M_bucket_begin(__bkt))
_M_remove_bucket_begin(__bkt, __n->_M_next,
- __n->_M_next ? this->_M_bucket_index(__n->_M_next, _M_bucket_count)
- : 0);
+ __n->_M_next ? _M_bucket_index(__n->_M_next) : 0);
else if (__n->_M_next)
{
- size_type __next_bkt =
- this->_M_bucket_index(__n->_M_next, _M_bucket_count);
+ size_type __next_bkt = _M_bucket_index(__n->_M_next);
if (__next_bkt != __bkt)
_M_buckets[__next_bkt] = __prev_n;
}
@@ -1516,7 +1538,7 @@
erase(const key_type& __k)
{
typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
- std::size_t __bkt = this->_M_bucket_index(__k, __code, _M_bucket_count);
+ std::size_t __bkt = _M_bucket_index(__k, __code);
// Look for the first matching node with its previous node at the same
// time
_Node* __n = _M_buckets[__bkt];
@@ -1531,10 +1553,9 @@
bool __is_bucket_begin = true;
for (;; __prev_n = __n, __n = __n->_M_next)
{
- if (this->_M_compare(__k, __code, __n))
+ if (this->_M_equals(__k, __code, __n))
break;
- if (!(__n->_M_next)
- || this->_M_bucket_index(__n->_M_next, _M_bucket_count) != __bkt)
+ if (!(__n->_M_next) || _M_bucket_index(__n->_M_next) != __bkt)
return 0;
__is_bucket_begin = false;
}
@@ -1551,7 +1572,7 @@
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 526. Is it undefined if a function in the standard changes
// in parameters?
- if (std::__addressof(this->_M_extract(__p->_M_v))
+ if (std::__addressof(this->_M_extract()(__p->_M_v))
!= std::__addressof(__k))
_M_deallocate_node(__p);
else
@@ -1560,9 +1581,9 @@
++__result;
if (!__next_n)
break;
- __next_bkt = this->_M_bucket_index(__next_n, _M_bucket_count);
+ __next_bkt = _M_bucket_index(__next_n);
}
- while (__next_bkt == __bkt && this->_M_compare(__k, __code, __next_n));
+ while (__next_bkt == __bkt && this->_M_equals(__k, __code, __next_n));
if (__saved_n)
_M_deallocate_node(__saved_n);
@@ -1591,7 +1612,7 @@
if (__n == __last_n)
return iterator(__n);
- std::size_t __bkt = this->_M_bucket_index(__n, _M_bucket_count);
+ std::size_t __bkt = _M_bucket_index(__n);
_Node* __prev_n = _M_get_previous_node(__bkt, __n);
bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
@@ -1606,7 +1627,7 @@
--_M_element_count;
if (!__n)
break;
- __n_bkt = this->_M_bucket_index(__n, _M_bucket_count);
+ __n_bkt = _M_bucket_index(__n);
}
while (__n != __last_n && __n_bkt == __bkt);
if (__is_bucket_begin)
@@ -1672,7 +1693,7 @@
while (__p)
{
_Node* __next = __p->_M_next;
- std::size_t __new_index = this->_M_bucket_index(__p, __n);
+ std::size_t __new_index = _HCBase::_M_bucket_index(__p, __n);
if (!__new_buckets[__new_index])
// Store temporarily bucket end node in _M_buckets if possible.
// This will boost second loop where we need to access bucket
Index: include/bits/hashtable_policy.h
===================================================================
--- include/bits/hashtable_policy.h (revision 182685)
+++ include/bits/hashtable_policy.h (working copy)
@@ -101,8 +101,7 @@
_M_next() { }
};
- // Local iterators, used to iterate within a bucket but not between
- // buckets.
+ // Node iterators, used to iterate through all the hashtable.
template<typename _Value, bool __cache>
struct _Node_iterator_base
{
@@ -425,8 +424,7 @@
{
_Hashtable* __h = static_cast<_Hashtable*>(this);
typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
- std::size_t __n = __h->_M_bucket_index(__k, __code,
- __h->_M_bucket_count);
+ std::size_t __n = __h->_M_bucket_index(__k, __code);
typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
if (!__p)
@@ -443,8 +441,7 @@
{
_Hashtable* __h = static_cast<_Hashtable*>(this);
typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
- std::size_t __n = __h->_M_bucket_index(__k, __code,
- __h->_M_bucket_count);
+ std::size_t __n = __h->_M_bucket_index(__k, __code);
typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
if (!__p)
@@ -462,8 +459,7 @@
{
_Hashtable* __h = static_cast<_Hashtable*>(this);
typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
- std::size_t __n = __h->_M_bucket_index(__k, __code,
- __h->_M_bucket_count);
+ std::size_t __n = __h->_M_bucket_index(__k, __code);
typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
if (!__p)
@@ -479,8 +475,7 @@
{
const _Hashtable* __h = static_cast<const _Hashtable*>(this);
typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
- std::size_t __n = __h->_M_bucket_index(__k, __code,
- __h->_M_bucket_count);
+ std::size_t __n = __h->_M_bucket_index(__k, __code);
typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
if (!__p)
@@ -518,6 +513,49 @@
}
};
+ // Helper class using EBO when it is not forbidden, type is not final,
+ // and when it worth it, type is empty.
+ template<int _N, typename _Tp,
+ bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)>
+ struct _Ebo_helper;
+
+ // Specialization using EBO
+ template<int _N, typename _Tp>
+ struct _Ebo_helper<_N, _Tp, true> : _Tp
+ {
+ _Ebo_helper() = default;
+ _Ebo_helper(const _Tp& __tp) : _Tp(__tp)
+ { }
+
+ static const _Tp&
+ _S_cget(const _Ebo_helper<_N, _Tp, true>& __eboh)
+ { return static_cast<const _Tp&>(__eboh); }
+
+ static _Tp&
+ _S_get(_Ebo_helper<_N, _Tp, true>& __eboh)
+ { return static_cast<_Tp&>(__eboh); }
+ };
+
+ // Specialization not using EBO
+ template<int _N, typename _Tp>
+ struct _Ebo_helper<_N, _Tp, false>
+ {
+ _Ebo_helper() = default;
+ _Ebo_helper(const _Tp& __tp) : m_tp(__tp)
+ { }
+
+ static const _Tp&
+ _S_cget(const _Ebo_helper<_N, _Tp, false>& __eboh)
+ { return __eboh.m_tp; }
+
+ static _Tp&
+ _S_get(_Ebo_helper<_N, _Tp, false>& __eboh)
+ { return __eboh.m_tp; }
+
+ private:
+ _Tp m_tp;
+ };
+
// Class template _Hash_code_base. Encapsulates two policy issues that
// aren't quite orthogonal.
// (1) the difference between using a ranged hash function and using
@@ -526,28 +564,36 @@
// we have a dummy type as placeholder.
// (2) Whether or not we cache hash codes. Caching hash codes is
// meaningless if we have a ranged hash function.
- // We also put the key extraction and equality comparison function
- // objects here, for convenience.
+ // We also put the key extraction objects here, for convenience.
+ //
+ // Each specialization derives from one or more of the template parameters to
+ // benefit from Ebo. This is important as this type is inherited in some cases
+ // by the _Local_iterator_base type used to implement local_iterator and
+ // const_local_iterator. As with any iterator type we prefer to make it as
+ // small as possible.
// Primary template: unused except as a hook for specializations.
- template<typename _Key, typename _Value,
- typename _ExtractKey, typename _Equal,
+ template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2, typename _Hash,
bool __cache_hash_code>
struct _Hash_code_base;
// Specialization: ranged hash function, no caching hash codes. H1
// and H2 are provided but ignored. We define a dummy hash code type.
- template<typename _Key, typename _Value,
- typename _ExtractKey, typename _Equal,
+ template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2, typename _Hash>
- struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
- _Hash, false>
+ struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false>
+ : _Ebo_helper<0, _ExtractKey>, _Ebo_helper<1, _Hash>
{
+ private:
+ typedef _Ebo_helper<0, _ExtractKey> _EboExtractKey;
+ typedef _Ebo_helper<1, _Hash> _EboHash;
protected:
- _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
+ // We need the default constructor for the local iterators.
+ _Hash_code_base() = default;
+ _Hash_code_base(const _ExtractKey& __ex,
const _H1&, const _H2&, const _Hash& __h)
- : _M_extract(__ex), _M_eq(__eq), _M_ranged_hash(__h) { }
+ : _EboExtractKey(__ex), _EboHash(__h) { }
typedef void* _Hash_code_type;
@@ -558,18 +604,13 @@
std::size_t
_M_bucket_index(const _Key& __k, _Hash_code_type,
std::size_t __n) const
- { return _M_ranged_hash(__k, __n); }
+ { return _M_ranged_hash()(__k, __n); }
std::size_t
_M_bucket_index(const _Hash_node<_Value, false>* __p,
std::size_t __n) const
- { return _M_ranged_hash(_M_extract(__p->_M_v), __n); }
+ { return _M_ranged_hash()(_M_extract()(__p->_M_v), __n); }
- bool
- _M_compare(const _Key& __k, _Hash_code_type,
- _Hash_node<_Value, false>* __n) const
- { return _M_eq(__k, _M_extract(__n->_M_v)); }
-
void
_M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
{ }
@@ -582,73 +623,76 @@
void
_M_swap(_Hash_code_base& __x)
{
- std::swap(_M_extract, __x._M_extract);
- std::swap(_M_eq, __x._M_eq);
- std::swap(_M_ranged_hash, __x._M_ranged_hash);
+ std::swap(_M_extract(), __x._M_extract());
+ std::swap(_M_ranged_hash(), __x._M_ranged_hash());
}
protected:
- _ExtractKey _M_extract;
- _Equal _M_eq;
- _Hash _M_ranged_hash;
+ const _ExtractKey&
+ _M_extract() const { return _EboExtractKey::_S_cget(*this); }
+ _ExtractKey&
+ _M_extract() { return _EboExtractKey::_S_get(*this); }
+ const _Hash&
+ _M_ranged_hash() const { return _EboHash::_S_cget(*this); }
+ _Hash&
+ _M_ranged_hash() { return _EboHash::_S_get(*this); }
};
-
// No specialization for ranged hash function while caching hash codes.
// That combination is meaningless, and trying to do it is an error.
-
// Specialization: ranged hash function, cache hash codes. This
// combination is meaningless, so we provide only a declaration
// and no definition.
- template<typename _Key, typename _Value,
- typename _ExtractKey, typename _Equal,
+ template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2, typename _Hash>
- struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
- _Hash, true>;
+ struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;
// Specialization: hash function and range-hashing function, no
- // caching of hash codes. H is provided but ignored. Provides
- // typedef and accessor required by TR1.
- template<typename _Key, typename _Value,
- typename _ExtractKey, typename _Equal,
+ // caching of hash codes.
+ // Provides typedef and accessor required by TR1.
+ template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2>
- struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
+ struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
_Default_ranged_hash, false>
+ : _Ebo_helper<0, _ExtractKey>, _Ebo_helper<1, _H1>, _Ebo_helper<2, _H2>
{
+ private:
+ typedef _Ebo_helper<0, _ExtractKey> _EboExtractKey;
+ typedef _Ebo_helper<1, _H1> _EboH1;
+ typedef _Ebo_helper<2, _H2> _EboH2;
+
+ public:
typedef _H1 hasher;
hasher
hash_function() const
- { return _M_h1; }
+ { return _M_h1(); }
protected:
- _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
+ // We need the default constructor for the local iterators.
+ _Hash_code_base() = default;
+ _Hash_code_base(const _ExtractKey& __ex,
const _H1& __h1, const _H2& __h2,
const _Default_ranged_hash&)
- : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
+ : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { }
typedef std::size_t _Hash_code_type;
_Hash_code_type
_M_hash_code(const _Key& __k) const
- { return _M_h1(__k); }
+ { return _M_h1()(__k); }
std::size_t
_M_bucket_index(const _Key&, _Hash_code_type __c,
std::size_t __n) const
- { return _M_h2(__c, __n); }
+ { return _M_h2()(__c, __n); }
std::size_t
_M_bucket_index(const _Hash_node<_Value, false>* __p,
std::size_t __n) const
- { return _M_h2(_M_h1(_M_extract(__p->_M_v)), __n); }
+ { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v)), __n); }
- bool
- _M_compare(const _Key& __k, _Hash_code_type,
- _Hash_node<_Value, false>* __n) const
- { return _M_eq(__k, _M_extract(__n->_M_v)); }
-
void
_M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
{ }
@@ -661,61 +705,69 @@
void
_M_swap(_Hash_code_base& __x)
{
- std::swap(_M_extract, __x._M_extract);
- std::swap(_M_eq, __x._M_eq);
- std::swap(_M_h1, __x._M_h1);
- std::swap(_M_h2, __x._M_h2);
+ std::swap(_M_extract(), __x._M_extract());
+ std::swap(_M_h1(), __x._M_h1());
+ std::swap(_M_h2(), __x._M_h2());
}
protected:
- _ExtractKey _M_extract;
- _Equal _M_eq;
- _H1 _M_h1;
- _H2 _M_h2;
+ const _ExtractKey&
+ _M_extract() const { return _EboExtractKey::_S_cget(*this); }
+ _ExtractKey&
+ _M_extract() { return _EboExtractKey::_S_get(*this); }
+ const _H1&
+ _M_h1() const { return _EboH1::_S_cget(*this); }
+ _H1&
+ _M_h1() { return _EboH1::_S_get(*this); }
+ const _H2&
+ _M_h2() const { return _EboH2::_S_cget(*this); }
+ _H2&
+ _M_h2() { return _EboH2::_S_get(*this); }
};
// Specialization: hash function and range-hashing function,
// caching hash codes. H is provided but ignored. Provides
// typedef and accessor required by TR1.
- template<typename _Key, typename _Value,
- typename _ExtractKey, typename _Equal,
+ template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2>
- struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
+ struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
_Default_ranged_hash, true>
+ : _Ebo_helper<0, _ExtractKey>, _Ebo_helper<1, _H1>, _Ebo_helper<2, _H2>
{
+ private:
+ typedef _Ebo_helper<0, _ExtractKey> _EboExtractKey;
+ typedef _Ebo_helper<1, _H1> _EboH1;
+ typedef _Ebo_helper<2, _H2> _EboH2;
+
+ public:
typedef _H1 hasher;
hasher
hash_function() const
- { return _M_h1; }
+ { return _M_h1(); }
protected:
- _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
+ _Hash_code_base(const _ExtractKey& __ex,
const _H1& __h1, const _H2& __h2,
const _Default_ranged_hash&)
- : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
+ : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { }
typedef std::size_t _Hash_code_type;
_Hash_code_type
_M_hash_code(const _Key& __k) const
- { return _M_h1(__k); }
+ { return _M_h1()(__k); }
std::size_t
_M_bucket_index(const _Key&, _Hash_code_type __c,
std::size_t __n) const
- { return _M_h2(__c, __n); }
+ { return _M_h2()(__c, __n); }
std::size_t
_M_bucket_index(const _Hash_node<_Value, true>* __p,
std::size_t __n) const
- { return _M_h2(__p->_M_hash_code, __n); }
+ { return _M_h2()(__p->_M_hash_code, __n); }
- bool
- _M_compare(const _Key& __k, _Hash_code_type __c,
- _Hash_node<_Value, true>* __n) const
- { return __c == __n->_M_hash_code && _M_eq(__k, _M_extract(__n->_M_v)); }
-
void
_M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const
{ __n->_M_hash_code = __c; }
@@ -728,20 +780,293 @@
void
_M_swap(_Hash_code_base& __x)
{
- std::swap(_M_extract, __x._M_extract);
- std::swap(_M_eq, __x._M_eq);
- std::swap(_M_h1, __x._M_h1);
- std::swap(_M_h2, __x._M_h2);
+ std::swap(_M_extract(), __x._M_extract());
+ std::swap(_M_h1(), __x._M_h1());
+ std::swap(_M_h2(), __x._M_h2());
}
protected:
- _ExtractKey _M_extract;
- _Equal _M_eq;
- _H1 _M_h1;
- _H2 _M_h2;
+ const _ExtractKey&
+ _M_extract() const { return _EboExtractKey::_S_cget(*this); }
+ _ExtractKey&
+ _M_extract() { return _EboExtractKey::_S_get(*this); }
+ const _H1&
+ _M_h1() const { return _EboH1::_S_cget(*this); }
+ _H1&
+ _M_h1() { return _EboH1::_S_get(*this); }
+ const _H2&
+ _M_h2() const { return _EboH2::_S_cget(*this); }
+ _H2&
+ _M_h2() { return _EboH2::_S_get(*this); }
};
+ template <typename _Key, typename _Value, typename _ExtractKey,
+ typename _Equal, typename _HashCodeType,
+ bool __cache_hash_code>
+ struct _Equal_helper;
+ template<typename _Key, typename _Value, typename _ExtractKey,
+ typename _Equal, typename _HashCodeType>
+ struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, true>
+ {
+ static bool
+ _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
+ const _Key& __k, _HashCodeType __c,
+ _Hash_node<_Value, true>* __n)
+ { return __c == __n->_M_hash_code
+ && __eq(__k, __extract(__n->_M_v)); }
+ };
+
+ template<typename _Key, typename _Value, typename _ExtractKey,
+ typename _Equal, typename _HashCodeType>
+ struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, false>
+ {
+ static bool
+ _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
+ const _Key& __k, _HashCodeType,
+ _Hash_node<_Value, false>* __n)
+ { return __eq(__k, __extract(__n->_M_v)); }
+ };
+
+ // Helper class adding management of _Equal functor to _Hash_code_base
+ // type.
+ template<typename _Key, typename _Value,
+ typename _ExtractKey, typename _Equal,
+ typename _H1, typename _H2, typename _Hash,
+ bool __cache_hash_code>
+ struct _Hashtable_base
+ : _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
+ __cache_hash_code>,
+ _Ebo_helper<0, _Equal>
+ {
+ private:
+ typedef _Ebo_helper<0, _Equal> _EboEqual;
+
+ protected:
+ typedef _Hash_code_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, __cache_hash_code> _HCBase;
+ typedef typename _HCBase::_Hash_code_type _Hash_code_type;
+
+ _Hashtable_base(const _ExtractKey& __ex,
+ const _H1& __h1, const _H2& __h2,
+ const _Hash& __hash, const _Equal& __eq)
+ : _HCBase(__ex, __h1, __h2, __hash), _EboEqual(__eq) { }
+
+ bool
+ _M_equals(const _Key& __k, _Hash_code_type __c,
+ _Hash_node<_Value, __cache_hash_code>* __n) const
+ {
+ typedef _Equal_helper<_Key, _Value, _ExtractKey,
+ _Equal, _Hash_code_type,
+ __cache_hash_code> _EqualHelper;
+ return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(), __k, __c, __n);
+ }
+
+ void
+ _M_swap(_Hashtable_base& __x)
+ {
+ _HCBase::_M_swap(__x);
+ std::swap(_M_eq(), __x._M_eq());
+ }
+
+ private:
+ const _Equal&
+ _M_eq() const { return _EboEqual::_S_cget(*this); }
+ _Equal&
+ _M_eq() { return _EboEqual::_S_get(*this); }
+ };
+
+ // Local iterators, used to iterate within a bucket but not between
+ // buckets.
+ template<typename _Key, typename _Value, typename _ExtractKey,
+ typename _H1, typename _H2, typename _Hash,
+ bool __cache_hash_code>
+ struct _Local_iterator_base;
+
+ template<typename _Key, typename _Value, typename _ExtractKey,
+ typename _H1, typename _H2, typename _Hash>
+ struct _Local_iterator_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, true>
+ : _H2
+ {
+ _Local_iterator_base() = default;
+ _Local_iterator_base(_Hash_node<_Value, true>* __p,
+ std::size_t __bkt, std::size_t __bkt_count)
+ : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
+
+ void
+ _M_incr()
+ {
+ _M_cur = _M_cur->_M_next;
+ if (_M_cur)
+ {
+ std::size_t __bkt = _M_h2()(_M_cur->_M_hash_code, _M_bucket_count);
+ if (__bkt != _M_bucket)
+ _M_cur = nullptr;
+ }
+ }
+
+ const _H2& _M_h2() const
+ { return *this; }
+
+ _Hash_node<_Value, true>* _M_cur;
+ std::size_t _M_bucket;
+ std::size_t _M_bucket_count;
+ };
+
+ template<typename _Key, typename _Value, typename _ExtractKey,
+ typename _H1, typename _H2, typename _Hash>
+ struct _Local_iterator_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, false>
+ : _Hash_code_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, false>
+ {
+ _Local_iterator_base() = default;
+ _Local_iterator_base(_Hash_node<_Value, false>* __p,
+ std::size_t __bkt, std::size_t __bkt_count)
+ : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
+
+ void
+ _M_incr()
+ {
+ _M_cur = _M_cur->_M_next;
+ if (_M_cur)
+ {
+ std::size_t __bkt = this->_M_bucket_index(_M_cur, _M_bucket_count);
+ if (__bkt != _M_bucket)
+ _M_cur = nullptr;
+ }
+ }
+
+ _Hash_node<_Value, false>* _M_cur;
+ std::size_t _M_bucket;
+ std::size_t _M_bucket_count;
+ };
+
+ template<typename _Key, typename _Value, typename _ExtractKey,
+ typename _H1, typename _H2, typename _Hash, bool __cache>
+ inline bool
+ operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, __cache>& __x,
+ const _Local_iterator_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, __cache>& __y)
+ { return __x._M_cur == __y._M_cur; }
+
+ template<typename _Key, typename _Value, typename _ExtractKey,
+ typename _H1, typename _H2, typename _Hash, bool __cache>
+ inline bool
+ operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, __cache>& __x,
+ const _Local_iterator_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, __cache>& __y)
+ { return __x._M_cur != __y._M_cur; }
+
+ template<typename _Key, typename _Value, typename _ExtractKey,
+ typename _H1, typename _H2, typename _Hash,
+ bool __constant_iterators, bool __cache>
+ struct _Local_iterator
+ : public _Local_iterator_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, __cache>
+ {
+ typedef _Value value_type;
+ typedef typename std::conditional<__constant_iterators,
+ const _Value*, _Value*>::type
+ pointer;
+ typedef typename std::conditional<__constant_iterators,
+ const _Value&, _Value&>::type
+ reference;
+ typedef std::ptrdiff_t difference_type;
+ typedef std::forward_iterator_tag iterator_category;
+
+ _Local_iterator() = default;
+
+ explicit
+ _Local_iterator(_Hash_node<_Value, __cache>* __p,
+ std::size_t __bkt, std::size_t __bkt_count)
+ : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
+ __cache>(__p, __bkt, __bkt_count)
+ { }
+
+ reference
+ operator*() const
+ { return this->_M_cur->_M_v; }
+
+ pointer
+ operator->() const
+ { return std::__addressof(this->_M_cur->_M_v); }
+
+ _Local_iterator&
+ operator++()
+ {
+ this->_M_incr();
+ return *this;
+ }
+
+ _Local_iterator
+ operator++(int)
+ {
+ _Local_iterator __tmp(*this);
+ this->_M_incr();
+ return __tmp;
+ }
+ };
+
+ template<typename _Key, typename _Value, typename _ExtractKey,
+ typename _H1, typename _H2, typename _Hash,
+ bool __constant_iterators, bool __cache>
+ struct _Local_const_iterator
+ : public _Local_iterator_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, __cache>
+ {
+ typedef _Value value_type;
+ typedef const _Value* pointer;
+ typedef const _Value& reference;
+ typedef std::ptrdiff_t difference_type;
+ typedef std::forward_iterator_tag iterator_category;
+
+ _Local_const_iterator() = default;
+
+ explicit
+ _Local_const_iterator(_Hash_node<_Value, __cache>* __p,
+ std::size_t __bkt, std::size_t __bkt_count)
+ : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
+ __cache>(__p, __bkt, __bkt_count)
+ { }
+
+ _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash,
+ __constant_iterators,
+ __cache>& __x)
+ : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
+ __cache>(__x._M_cur, __x._M_bucket,
+ __x._M_bucket_count)
+ { }
+
+ reference
+ operator*() const
+ { return this->_M_cur->_M_v; }
+
+ pointer
+ operator->() const
+ { return std::__addressof(this->_M_cur->_M_v); }
+
+ _Local_const_iterator&
+ operator++()
+ {
+ this->_M_incr();
+ return *this;
+ }
+
+ _Local_const_iterator
+ operator++(int)
+ {
+ _Local_const_iterator __tmp(*this);
+ this->_M_incr();
+ return __tmp;
+ }
+ };
+
+
// Class template _Equality_base. This is for implementing equality
// comparison for unordered containers, per N3068, by John Lakos and
// Pablo Halpern. Algorithmically, we follow closely the reference
Index: include/bits/unordered_map.h
===================================================================
--- include/bits/unordered_map.h (revision 182685)
+++ include/bits/unordered_map.h (working copy)
@@ -41,7 +41,8 @@
class _Pred = std::equal_to<_Key>,
class _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
bool __cache_hash_code =
- __not_<__and_<is_integral<_Key>,
+ __not_<__and_<is_integral<_Key>, is_empty<_Hash>,
+ integral_constant<bool, !__is_final(_Hash)>,
__detail::__is_noexcept_hash<_Key, _Hash>>>::value>
class __unordered_map
: public _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc,
@@ -112,7 +113,8 @@
class _Pred = std::equal_to<_Key>,
class _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
bool __cache_hash_code =
- __not_<__and_<is_integral<_Key>,
+ __not_<__and_<is_integral<_Key>, is_empty<_Hash>,
+ integral_constant<bool, !__is_final(_Hash)>,
__detail::__is_noexcept_hash<_Key, _Hash>>>::value>
class __unordered_multimap
: public _Hashtable<_Key, std::pair<const _Key, _Tp>,
Index: include/bits/unordered_set.h
===================================================================
--- include/bits/unordered_set.h (revision 182685)
+++ include/bits/unordered_set.h (working copy)
@@ -41,7 +41,8 @@
class _Pred = std::equal_to<_Value>,
class _Alloc = std::allocator<_Value>,
bool __cache_hash_code =
- __not_<__and_<is_integral<_Value>,
+ __not_<__and_<is_integral<_Value>, is_empty<_Hash>,
+ integral_constant<bool, !__is_final(_Hash)>,
__detail::__is_noexcept_hash<_Value, _Hash>>>::value>
class __unordered_set
: public _Hashtable<_Value, _Value, _Alloc,
@@ -124,7 +125,8 @@
class _Pred = std::equal_to<_Value>,
class _Alloc = std::allocator<_Value>,
bool __cache_hash_code =
- __not_<__and_<is_integral<_Value>,
+ __not_<__and_<is_integral<_Value>, is_empty<_Hash>,
+ integral_constant<bool, !__is_final(_Hash)>,
__detail::__is_noexcept_hash<_Value, _Hash>>>::value>
class __unordered_multiset
: public _Hashtable<_Value, _Value, _Alloc,
Index: testsuite/23_containers/unordered_map/final_hash.cc
===================================================================
--- testsuite/23_containers/unordered_map/final_hash.cc (revision 0)
+++ testsuite/23_containers/unordered_map/final_hash.cc (revision 0)
@@ -0,0 +1,39 @@
+// { dg-do compile }
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2011 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 Pred 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/>.
+
+#include <string>
+#include <unordered_map>
+
+namespace
+{
+ template<typename _Tp>
+ struct final_hash final
+ {
+ std::size_t operator() (const _Tp&) const noexcept
+ { return 0; }
+ };
+}
+
+// A non-integral type:
+template class std::unordered_map<std::string, int, final_hash<std::string>>;
+
+// An integral type;
+template class std::unordered_map<int, int, final_hash<int>>;
+
Index: testsuite/23_containers/unordered_multimap/final_hash.cc
===================================================================
--- testsuite/23_containers/unordered_multimap/final_hash.cc (revision 0)
+++ testsuite/23_containers/unordered_multimap/final_hash.cc (revision 0)
@@ -0,0 +1,40 @@
+// { dg-do compile }
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2011 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 Pred 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/>.
+
+#include <string>
+#include <unordered_map>
+
+namespace
+{
+ template<typename _Tp>
+ struct final_hash final
+ {
+ std::size_t operator() (const _Tp&) const noexcept
+ { return 0; }
+ };
+}
+
+// A non-integral type:
+template class std::unordered_multimap<std::string, int,
+ final_hash<std::string>>;
+
+// An integral type;
+template class std::unordered_multimap<int, int, final_hash<int>>;
+
Index: testsuite/23_containers/unordered_set/final_hash.cc
===================================================================
--- testsuite/23_containers/unordered_set/final_hash.cc (revision 0)
+++ testsuite/23_containers/unordered_set/final_hash.cc (revision 0)
@@ -0,0 +1,39 @@
+// { dg-do compile }
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2011 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 Pred 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/>.
+
+#include <string>
+#include <unordered_set>
+
+namespace
+{
+ template<typename _Tp>
+ struct final_hash final
+ {
+ std::size_t operator() (const _Tp&) const noexcept
+ { return 0; }
+ };
+}
+
+// A non-integral type:
+template class std::unordered_set<std::string, final_hash<std::string>>;
+
+// An integral type;
+template class std::unordered_set<int, final_hash<int>>;
+
Index: testsuite/23_containers/unordered_set/instantiation_neg.cc
===================================================================
--- testsuite/23_containers/unordered_set/instantiation_neg.cc (revision 182685)
+++ 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 "static assertion failed" "" { target *-*-* } 177 }
+// { dg-error "static assertion failed" "" { target *-*-* } 185 }
#include <unordered_set>
Index: testsuite/23_containers/unordered_multiset/final_hash.cc
===================================================================
--- testsuite/23_containers/unordered_multiset/final_hash.cc (revision 0)
+++ testsuite/23_containers/unordered_multiset/final_hash.cc (revision 0)
@@ -0,0 +1,39 @@
+// { dg-do compile }
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2011 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 Pred 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/>.
+
+#include <string>
+#include <unordered_set>
+
+namespace
+{
+ template<typename _Tp>
+ struct final_hash final
+ {
+ std::size_t operator() (const _Tp&) const noexcept
+ { return 0; }
+ };
+}
+
+// A non-integral type:
+template class std::unordered_multiset<std::string, final_hash<std::string>>;
+
+// An integral type;
+template class std::unordered_multiset<int, final_hash<int>>;
+