This patch simplifies a number of implementations.
It tries as much as possible to avoid computing hash code. This is
especially true for the erase implementation in case of multi keys.
* include/bits/hashtable_policy.h (_Map_base<>::at): Use
_Hashtable<>::find.
(_Hashtable_base<>::_Equal_hash_code<>::_S_node_equals):New.
(_Hashtable_base<>::_M_node_equals): New, use latter.
* include/bits/hashtable.h (_Hashtable<>::_M_update_bbegin): New.
(_Hashtable<>::_M_assign): Use latter.
(_Hashtable<>::_M_move_assign): Likewise.
(_Hashtable<>(_Hashtable<>&&)): Likewise.
(_Hashtable<>(_Hashtable<>&&, const allocator_type&)): Likewise.
(_Hashtable<>::swap): Likewise.
(_Hashtable<>::find): Build iterator directly from _M_find_node result.
(_Hashtable<>::count): Use _Hashtable<>::find.
(_Hashtable<>::equal_range): Likewise.
(_Hashtable<>::_M_erase(false_type, const key_type&)): Use
_M_node_equals.
Tested under Linux x86_64.
François
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index ef71c090f3b..b8cfdde2f31 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -378,6 +378,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// numerous checks in the code to avoid 0 modulus.
__bucket_type _M_single_bucket = nullptr;
+ void
+ _M_update_bbegin()
+ {
+ if (_M_begin())
+ _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
+ }
+
+ void
+ _M_update_bbegin(__node_type* __n)
+ {
+ _M_before_begin._M_nxt = __n;
+ _M_update_bbegin();
+ }
+
bool
_M_uses_single_bucket(__bucket_type* __bkts) const
{ return __builtin_expect(__bkts == &_M_single_bucket, false); }
@@ -674,7 +688,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
std::pair
equal_range(const key_type& __k) const;
-protected:
+private:
// Bucket index computation helpers.
size_type
_M_bucket_index(__node_type* __n) const noexcept
@@ -1196,8 +1210,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
= __node_gen(__fwd_value(std::forward<_Ht>(__ht),
__ht_n->_M_v()));
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;
+ _M_update_bbegin(__this_n);
// Then deal with other nodes.
__node_base* __prev_n = __this_n;
@@ -1259,15 +1272,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_buckets = &_M_single_bucket;
_M_single_bucket = __ht._M_single_bucket;
}
+
_M_bucket_count = __ht._M_bucket_count;
_M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
_M_element_count = __ht._M_element_count;
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;
+ // Fix bucket containing the _M_before_begin pointer that can't be moved.
+ _M_update_bbegin();
__ht._M_reset();
}
@@ -1335,10 +1347,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_single_bucket = __ht._M_single_bucket;
}
- // 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;
+ // Fix bucket containing the _M_before_begin pointer that can't be moved.
+ _M_update_bbegin();
__ht._M_reset();
}
@@ -1389,11 +1399,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
else
_M_buckets = __ht._M_buckets;
- _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
- // Update, if necessary, bucket pointing to before begin that hasn't
+ // Fix bucket containing the _M_before_begin pointer that can't be
// moved.
- if (_M_begin())
- _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
+ _M_update_bbegin(__ht._M_begin());
+
__ht._M_reset();
}
else
@@ -1457,14 +1466,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
std::swap(_M_element_count, __x._M_element_count);
std::swap(_M_single_bucket, __x._M_single_bucket);
- // 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;
-
- if (__x._M_begin())
- __x._M_buckets[__x._M_bucket_index(__x._M_begin())]
- = &__x._M_before_begin;
+ // Fix bucket containing the _M_before_begin pointer that can't be swap.
+ _M_update_bbegin();
+ __x._M_update_bbegin();
}
template_M_hash_code(__k);
std::size_t __bkt = _M_bucket_index(__k, __code);
- __node_type* __p = _M_find_node(__bkt, __k, __code);
- return __p ? iterator(__p) : end();
+ return iterator(_M_find_node(__bkt, __k, __code));
}
template_M_hash_code(__k);
std::size_t __bkt