diff options
Diffstat (limited to 'libstdc++-v3/include/bits/hashtable_policy.h')
-rw-r--r-- | libstdc++-v3/include/bits/hashtable_policy.h | 114 |
1 files changed, 101 insertions, 13 deletions
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index e5aed59322d..ef15b0e5a77 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -1147,6 +1147,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>; using __ebo_h2 = _Hashtable_ebo_helper<2, _H2>; + // Gives the local iterator implementation access to _M_bucket_index(). + friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, + _Default_ranged_hash, false>; + public: typedef _H1 hasher; @@ -1228,7 +1232,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION private _Hashtable_ebo_helper<2, _H2> { private: - // Gives access to _M_h2() to the local iterator implementation. + // Gives the local iterator implementation access to _M_h2(). friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Default_ranged_hash, true>; @@ -1334,7 +1338,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION }; - /// Specialization. + /// Partial specialization used when nodes contain a cached hash code. template<typename _Key, typename _Value, typename _ExtractKey, typename _H1, typename _H2, typename _Hash> struct _Local_iterator_base<_Key, _Value, _ExtractKey, @@ -1346,7 +1350,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>; - public: _Local_iterator_base() = default; _Local_iterator_base(const __hash_code_base& __base, _Hash_node<_Value, true>* __p, @@ -1371,27 +1374,97 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Hash_node<_Value, true>* _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 + }; + + // Uninitialized storage for a _Hash_code_base. + // This type is DefaultConstructible and Assignable even if the + // _Hash_code_base type isn't, so that _Local_iterator_base<..., false> + // can be DefaultConstructible and Assignable. + template<typename _Tp, bool _IsEmpty = std::is_empty<_Tp>::value> + struct _Hash_code_storage + { + __gnu_cxx::__aligned_buffer<_Tp> _M_storage; + + _Tp* + _M_h() { return _M_storage._M_ptr(); } + + const _Tp* + _M_h() const { return _M_storage._M_ptr(); } + }; + + // Empty partial specialization for empty _Hash_code_base types. + template<typename _Tp> + struct _Hash_code_storage<_Tp, true> + { + static_assert( std::is_empty<_Tp>::value, "Type must be empty" ); + + // As _Tp is an empty type there will be no bytes written/read through + // the cast pointer, so no strict-aliasing violation. + _Tp* + _M_h() { return reinterpret_cast<_Tp*>(this); } + + const _Tp* + _M_h() const { return reinterpret_cast<const _Tp*>(this); } }; - /// Specialization. + template<typename _Key, typename _Value, typename _ExtractKey, + typename _H1, typename _H2, typename _Hash> + using __hash_code_for_local_iter + = _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey, + _H1, _H2, _Hash, false>>; + + // Partial specialization used when hash codes are not cached template<typename _Key, typename _Value, typename _ExtractKey, typename _H1, typename _H2, typename _Hash> struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false> - : private _Hash_code_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, false> + : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _H1, _H2, _Hash> { protected: using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false>; - public: - _Local_iterator_base() = default; + _Local_iterator_base() : _M_bucket_count(-1) { } + _Local_iterator_base(const __hash_code_base& __base, _Hash_node<_Value, false>* __p, std::size_t __bkt, std::size_t __bkt_count) - : __hash_code_base(__base), - _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { } + : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) + { _M_init(__base); } + + ~_Local_iterator_base() + { + if (_M_bucket_count != -1) + _M_destroy(); + } + + _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) + { + if (_M_bucket_count != -1) + _M_init(*__iter._M_h()); + } + + _Local_iterator_base& + operator=(const _Local_iterator_base& __iter) + { + if (_M_bucket_count != -1) + _M_destroy(); + _M_cur = __iter._M_cur; + _M_bucket = __iter._M_bucket; + _M_bucket_count = __iter._M_bucket_count; + if (_M_bucket_count != -1) + _M_init(*__iter._M_h()); + return *this; + } void _M_incr() @@ -1399,7 +1472,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_cur = _M_cur->_M_next(); if (_M_cur) { - std::size_t __bkt = this->_M_bucket_index(_M_cur, _M_bucket_count); + std::size_t __bkt = this->_M_h()->_M_bucket_index(_M_cur, + _M_bucket_count); if (__bkt != _M_bucket) _M_cur = nullptr; } @@ -1408,6 +1482,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Hash_node<_Value, false>* _M_cur; std::size_t _M_bucket; std::size_t _M_bucket_count; + + void + _M_init(const __hash_code_base& __base) + { ::new(this->_M_h()) __hash_code_base(__base); } + + void + _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, @@ -1417,7 +1505,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _H1, _H2, _Hash, __cache>& __x, const _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, __cache>& __y) - { return __x._M_cur == __y._M_cur; } + { return __x._M_curr() == __y._M_curr(); } template<typename _Key, typename _Value, typename _ExtractKey, typename _H1, typename _H2, typename _Hash, bool __cache> @@ -1426,7 +1514,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _H1, _H2, _Hash, __cache>& __x, const _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, __cache>& __y) - { return __x._M_cur != __y._M_cur; } + { return __x._M_curr() != __y._M_curr(); } /// local iterators template<typename _Key, typename _Value, typename _ExtractKey, |