* [PATCH][Hashtable 4/6] Clean local_iterator implementation
@ 2019-11-17 21:03 François Dumont
2020-07-17 10:45 ` Jonathan Wakely
0 siblings, 1 reply; 2+ messages in thread
From: François Dumont @ 2019-11-17 21:03 UTC (permalink / raw)
To: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1172 bytes --]
Simplify local_iterator implementation. It makes local_iterator and
iterator comparable which is used in debug containers.
   * include/bits/hashtable_policy.h (_Node_iterator_base()): New.
   (operator==(const _Node_iterator_base&, const _Node_iterator_base&)):
   Make hidden friend.
   (operator!=(const _Node_iterator_base&, const _Node_iterator_base&)):
   Make hidden friend.
   (_Local_iterator_base<>): Inherits _Node_iterator_base.
   (_Local_iterator_base<>::_M_cur): Remove.
   (_Local_iterator_base<>::_M_curr()): Remove.
   (operator==(const _Local_iterator_base&, const _Local_iterator_base&)):
   Remove.
   (operator!=(const _Local_iterator_base&, const _Local_iterator_base&)):
   Remove.
   * include/debug/unordered_map (unordered_map<>::_M_invalidate): Adapt.
   (unordered_multimap<>::_M_invalidate): Adapt.
   * include/debug/unordered_set (unordered_set<>::_M_invalidate): Adapt.
   (unordered_multiset<>::_M_invalidate): Adapt.
Tested under Linux x86_64.
François
[-- Attachment #2: hashtable#5.patch --]
[-- Type: text/x-patch, Size: 9356 bytes --]
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index f330f7f811b..5cc943b3d22 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -301,27 +301,24 @@ namespace __detail
__node_type* _M_cur;
+ _Node_iterator_base() = default;
_Node_iterator_base(__node_type* __p) noexcept
: _M_cur(__p) { }
void
_M_incr() noexcept
{ _M_cur = _M_cur->_M_next(); }
- };
- template<typename _Value, typename _Cache_hash_code>
- inline bool
- operator==(const _Node_iterator_base<_Value, _Cache_hash_code>& __x,
- const _Node_iterator_base<_Value, _Cache_hash_code >& __y)
- noexcept
- { return __x._M_cur == __y._M_cur; }
+ friend bool
+ operator==(const _Node_iterator_base& __x, const _Node_iterator_base& __y)
+ noexcept
+ { return __x._M_cur == __y._M_cur; }
- template<typename _Value, typename _Cache_hash_code>
- inline bool
- operator!=(const _Node_iterator_base<_Value, _Cache_hash_code>& __x,
- const _Node_iterator_base<_Value, _Cache_hash_code>& __y)
- noexcept
- { return __x._M_cur != __y._M_cur; }
+ friend bool
+ operator!=(const _Node_iterator_base& __x, const _Node_iterator_base& __y)
+ noexcept
+ { return __x._M_cur != __y._M_cur; }
+ };
/// Node iterators, used to iterate through all the hashtable.
template<typename _Value, typename _Constant_iterators,
@@ -345,7 +342,7 @@ namespace __detail
const _Value&, _Value&>::type;
_Node_iterator() noexcept
- : __base_type(0) { }
+ : __base_type(nullptr) { }
explicit
_Node_iterator(__node_type* __p) noexcept
@@ -394,7 +391,7 @@ namespace __detail
typedef const _Value& reference;
_Node_const_iterator() noexcept
- : __base_type(0) { }
+ : __base_type(nullptr) { }
explicit
_Node_const_iterator(__node_type* __p) noexcept
@@ -1426,9 +1423,11 @@ namespace __detail
struct _Local_iterator_base<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash, __hash_cached_t>
: private _Hashtable_ebo_helper<0, _H2>
+ , _Node_iterator_base<_Value, __hash_cached_t>
{
protected:
using __base_type = _Hashtable_ebo_helper<0, _H2>;
+ using __base_node_iter = _Node_iterator_base<_Value, __hash_cached_t>;
using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash,
__hash_cached_t>;
@@ -1437,31 +1436,27 @@ namespace __detail
_Local_iterator_base(const __hash_code_base& __base,
_Hash_node<_Value, __hash_cached_t>* __p,
std::size_t __bkt, std::size_t __bkt_count)
- : __base_type(__base._M_h2()),
- _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
+ : __base_type(__base._M_h2()), __base_node_iter(__p)
+ , _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
void
_M_incr()
{
- _M_cur = _M_cur->_M_next();
- if (_M_cur)
+ __base_node_iter::_M_incr();
+ if (this->_M_cur)
{
std::size_t __bkt
- = __base_type::_M_get()(_M_cur->_M_hash_code,
- _M_bucket_count);
+ = __base_type::_M_get()(this->_M_cur->_M_hash_code,
+ _M_bucket_count);
if (__bkt != _M_bucket)
- _M_cur = nullptr;
+ this->_M_cur = nullptr;
}
}
- _Hash_node<_Value, __hash_cached_t>* _M_cur;
std::size_t _M_bucket;
std::size_t _M_bucket_count;
public:
- const void*
- _M_curr() const { return _M_cur; } // for equality ops
-
std::size_t
_M_get_bucket() const { return _M_bucket; } // for debug mode
};
@@ -1510,18 +1505,20 @@ namespace __detail
struct _Local_iterator_base<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash, __hash_not_cached_t>
: __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _H1, _H2, _Hash>
+ , _Node_iterator_base<_Value, __hash_not_cached_t>
{
protected:
using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash,
__hash_not_cached_t>;
+ using __node_iter_base = _Node_iterator_base<_Value, __hash_not_cached_t>;
_Local_iterator_base() : _M_bucket_count(-1) { }
_Local_iterator_base(const __hash_code_base& __base,
_Hash_node<_Value, __hash_not_cached_t>* __p,
std::size_t __bkt, std::size_t __bkt_count)
- : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
+ : __node_iter_base(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
{ _M_init(__base); }
~_Local_iterator_base()
@@ -1531,8 +1528,8 @@ namespace __detail
}
_Local_iterator_base(const _Local_iterator_base& __iter)
- : _M_cur(__iter._M_cur), _M_bucket(__iter._M_bucket),
- _M_bucket_count(__iter._M_bucket_count)
+ : __node_iter_base(__iter), _M_bucket(__iter._M_bucket)
+ , _M_bucket_count(__iter._M_bucket_count)
{
if (_M_bucket_count != -1)
_M_init(*__iter._M_h());
@@ -1543,7 +1540,7 @@ namespace __detail
{
if (_M_bucket_count != -1)
_M_destroy();
- _M_cur = __iter._M_cur;
+ this->_M_cur = __iter._M_cur;
_M_bucket = __iter._M_bucket;
_M_bucket_count = __iter._M_bucket_count;
if (_M_bucket_count != -1)
@@ -1554,17 +1551,16 @@ namespace __detail
void
_M_incr()
{
- _M_cur = _M_cur->_M_next();
- if (_M_cur)
+ __node_iter_base::_M_incr();
+ if (this->_M_cur)
{
- std::size_t __bkt = this->_M_h()->_M_bucket_index(_M_cur,
+ std::size_t __bkt = this->_M_h()->_M_bucket_index(this->_M_cur,
_M_bucket_count);
if (__bkt != _M_bucket)
- _M_cur = nullptr;
+ this->_M_cur = nullptr;
}
}
- _Hash_node<_Value, __hash_not_cached_t>* _M_cur;
std::size_t _M_bucket;
std::size_t _M_bucket_count;
@@ -1576,33 +1572,10 @@ namespace __detail
_M_destroy() { this->_M_h()->~__hash_code_base(); }
public:
- const void*
- _M_curr() const { return _M_cur; } // for equality ops and debug mode
-
std::size_t
_M_get_bucket() const { return _M_bucket; } // for debug mode
};
- template<typename _Key, typename _Value, typename _ExtractKey,
- typename _H1, typename _H2, typename _Hash,
- typename _Cache_hash_code>
- inline bool
- operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey,
- _H1, _H2, _Hash, _Cache_hash_code>& __x,
- const _Local_iterator_base<_Key, _Value, _ExtractKey,
- _H1, _H2, _Hash, _Cache_hash_code>& __y)
- { return __x._M_curr() == __y._M_curr(); }
-
- template<typename _Key, typename _Value, typename _ExtractKey,
- typename _H1, typename _H2, typename _Hash,
- typename _Cache_hash_code>
- inline bool
- operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey,
- _H1, _H2, _Hash, _Cache_hash_code>& __x,
- const _Local_iterator_base<_Key, _Value, _ExtractKey,
- _H1, _H2, _Hash, _Cache_hash_code>& __y)
- { return __x._M_curr() != __y._M_curr(); }
-
/// local iterators
template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2, typename _Hash,
@@ -1615,6 +1588,7 @@ namespace __detail
using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash, _Cache_hash_code>;
using __hash_code_base = typename __base_type::__hash_code_base;
+
public:
typedef _Value value_type;
typedef typename std::conditional<_Constant_iterators::value,
diff --git a/libstdc++-v3/include/debug/unordered_map b/libstdc++-v3/include/debug/unordered_map
index d844ee9fa0e..157349ea4f9 100644
--- a/libstdc++-v3/include/debug/unordered_map
+++ b/libstdc++-v3/include/debug/unordered_map
@@ -621,7 +621,7 @@ namespace __debug
[__victim](_Base_const_iterator __it) { return __it == __victim; });
this->_M_invalidate_local_if(
[__victim](_Base_const_local_iterator __it)
- { return __it._M_curr() == __victim._M_cur; });
+ { return __it == __victim; });
}
_Base_iterator
@@ -1227,7 +1227,7 @@ namespace __debug
[__victim](_Base_const_iterator __it) { return __it == __victim; });
this->_M_invalidate_local_if(
[__victim](_Base_const_local_iterator __it)
- { return __it._M_curr() == __victim._M_cur; });
+ { return __it == __victim; });
}
_Base_iterator
diff --git a/libstdc++-v3/include/debug/unordered_set b/libstdc++-v3/include/debug/unordered_set
index ecc084e3846..924ff7671ee 100644
--- a/libstdc++-v3/include/debug/unordered_set
+++ b/libstdc++-v3/include/debug/unordered_set
@@ -506,7 +506,7 @@ namespace __debug
[__victim](_Base_const_iterator __it) { return __it == __victim; });
this->_M_invalidate_local_if(
[__victim](_Base_const_local_iterator __it)
- { return __it._M_curr() == __victim._M_cur; });
+ { return __it == __victim; });
}
_Base_iterator
@@ -1066,7 +1066,7 @@ namespace __debug
[__victim](_Base_const_iterator __it) { return __it == __victim; });
this->_M_invalidate_local_if(
[__victim](_Base_const_local_iterator __it)
- { return __it._M_curr() == __victim._M_cur; });
+ { return __it == __victim; });
}
_Base_iterator
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: [PATCH][Hashtable 4/6] Clean local_iterator implementation
2019-11-17 21:03 [PATCH][Hashtable 4/6] Clean local_iterator implementation François Dumont
@ 2020-07-17 10:45 ` Jonathan Wakely
0 siblings, 0 replies; 2+ messages in thread
From: Jonathan Wakely @ 2020-07-17 10:45 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
On 17/11/19 22:03 +0100, François Dumont wrote:
>Simplify local_iterator implementation. It makes local_iterator and
>iterator comparable which is used in debug containers.
>
>Â Â Â * include/bits/hashtable_policy.h (_Node_iterator_base()): New.
>Â Â Â (operator==(const _Node_iterator_base&, const _Node_iterator_base&)):
>Â Â Â Make hidden friend.
>Â Â Â (operator!=(const _Node_iterator_base&, const _Node_iterator_base&)):
>Â Â Â Make hidden friend.
>Â Â Â (_Local_iterator_base<>): Inherits _Node_iterator_base.
>Â Â Â (_Local_iterator_base<>::_M_cur): Remove.
>Â Â Â (_Local_iterator_base<>::_M_curr()): Remove.
>Â Â Â (operator==(const _Local_iterator_base&, const _Local_iterator_base&)):
>Â Â Â Remove.
>Â Â Â (operator!=(const _Local_iterator_base&, const _Local_iterator_base&)):
>Â Â Â Remove.
>Â Â Â * include/debug/unordered_map (unordered_map<>::_M_invalidate): Adapt.
>Â Â Â (unordered_multimap<>::_M_invalidate): Adapt.
>Â Â Â * include/debug/unordered_set (unordered_set<>::_M_invalidate): Adapt.
>Â Â Â (unordered_multiset<>::_M_invalidate): Adapt.
>
>Tested under Linux x86_64.
OK for master, with one (non-essential) change mentioned below ...
>diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
>index f330f7f811b..5cc943b3d22 100644
>--- a/libstdc++-v3/include/bits/hashtable_policy.h
>+++ b/libstdc++-v3/include/bits/hashtable_policy.h
>@@ -301,27 +301,24 @@ namespace __detail
>
> __node_type* _M_cur;
>
>+ _Node_iterator_base() = default;
> _Node_iterator_base(__node_type* __p) noexcept
> : _M_cur(__p) { }
>
> void
> _M_incr() noexcept
> { _M_cur = _M_cur->_M_next(); }
>- };
>
>- template<typename _Value, typename _Cache_hash_code>
>- inline bool
>- operator==(const _Node_iterator_base<_Value, _Cache_hash_code>& __x,
>- const _Node_iterator_base<_Value, _Cache_hash_code >& __y)
>- noexcept
>- { return __x._M_cur == __y._M_cur; }
>+ friend bool
>+ operator==(const _Node_iterator_base& __x, const _Node_iterator_base& __y)
>+ noexcept
>+ { return __x._M_cur == __y._M_cur; }
>
>- template<typename _Value, typename _Cache_hash_code>
>- inline bool
>- operator!=(const _Node_iterator_base<_Value, _Cache_hash_code>& __x,
>- const _Node_iterator_base<_Value, _Cache_hash_code>& __y)
>- noexcept
>- { return __x._M_cur != __y._M_cur; }
>+ friend bool
>+ operator!=(const _Node_iterator_base& __x, const _Node_iterator_base& __y)
>+ noexcept
>+ { return __x._M_cur != __y._M_cur; }
This operator!= can be surrounded by:
#if __cpp_impl_three_way_comparison < 201907L
...
#endif
because when three-way comparisons are supported (i.e. C++20 and
later) the operator!= can be generated by the compiler.
>+ };
>
> /// Node iterators, used to iterate through all the hashtable.
> template<typename _Value, typename _Constant_iterators,
>@@ -345,7 +342,7 @@ namespace __detail
> const _Value&, _Value&>::type;
>
> _Node_iterator() noexcept
>- : __base_type(0) { }
>+ : __base_type(nullptr) { }
>
> explicit
> _Node_iterator(__node_type* __p) noexcept
>@@ -394,7 +391,7 @@ namespace __detail
> typedef const _Value& reference;
>
> _Node_const_iterator() noexcept
>- : __base_type(0) { }
>+ : __base_type(nullptr) { }
>
> explicit
> _Node_const_iterator(__node_type* __p) noexcept
>@@ -1426,9 +1423,11 @@ namespace __detail
> struct _Local_iterator_base<_Key, _Value, _ExtractKey,
> _H1, _H2, _Hash, __hash_cached_t>
> : private _Hashtable_ebo_helper<0, _H2>
>+ , _Node_iterator_base<_Value, __hash_cached_t>
I was initially worried this is an ABI break, but it just moves the
_M_cur member into a new base class, which will be at the same offset
into the class, and won't change the sie or alignment. So I think it's
OK.
>@@ -1576,33 +1572,10 @@ namespace __detail
> _M_destroy() { this->_M_h()->~__hash_code_base(); }
>
> public:
>- const void*
>- _M_curr() const { return _M_cur; } // for equality ops and debug mode
>-
> std::size_t
> _M_get_bucket() const { return _M_bucket; } // for debug mode
> };
>
>- template<typename _Key, typename _Value, typename _ExtractKey,
>- typename _H1, typename _H2, typename _Hash,
>- typename _Cache_hash_code>
>- inline bool
>- operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey,
>- _H1, _H2, _Hash, _Cache_hash_code>& __x,
>- const _Local_iterator_base<_Key, _Value, _ExtractKey,
>- _H1, _H2, _Hash, _Cache_hash_code>& __y)
>- { return __x._M_curr() == __y._M_curr(); }
>-
>- template<typename _Key, typename _Value, typename _ExtractKey,
>- typename _H1, typename _H2, typename _Hash,
>- typename _Cache_hash_code>
>- inline bool
>- operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey,
>- _H1, _H2, _Hash, _Cache_hash_code>& __x,
>- const _Local_iterator_base<_Key, _Value, _ExtractKey,
>- _H1, _H2, _Hash, _Cache_hash_code>& __y)
>- { return __x._M_curr() != __y._M_curr(); }
>-
Removing these operators (and making the ones for the base hidden
friends) is a nice improvement.
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2020-07-17 10:45 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-11-17 21:03 [PATCH][Hashtable 4/6] Clean local_iterator implementation François Dumont
2020-07-17 10:45 ` Jonathan Wakely
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).