From 151fbaac5c78c4e9b749fc9e916f78b0ba63b153 Mon Sep 17 00:00:00 2001 From: Jonathan Wakely Date: Wed, 27 May 2015 12:18:44 +0100 Subject: [PATCH] stl_tree.h (_Rb_tree::_M_end()): Return _Base_ptr instead of downcasting. * include/bits/stl_tree.h (_Rb_tree::_M_end()): Return _Base_ptr instead of downcasting. (_Rb_tree::_M_copy): Change second parameter to _Base_ptr. (_Rb_tree::_M_lower_bound, _Rb_tree:_M_upper_bound): Likewise. (_Rb_tree::_S_iter): Remove. (_Rb_tree::_S_lower_bound_tr, _Rb_tree::_S_upper_bound_tr): Remove. (_Rb_tree::_M_find_tr(const _Kt&) const): Call _M_lower_bound_tr instead of _S_lower_bound_tr (_Rb_tree::_M_find_tr(const _Kt&)): Call const overload. (_Rb_tree::_M_lower_bound_tr(const _Kt&) const): Do the search here instead of calling _S_lower_bound_tr. (_Rb_tree::_M_lower_bound_tr(const _Kt&)): Call const overload. (_Rb_tree::_M_upper_bound_tr(const _Kt&) const): Do the search here instead of calling _S_upper_bound_tr. (_Rb_tree::_M_upper_bound_tr(const _Kt&)): Call const overload. (_Rb_tree::_M_equal_range_tr(const _Kt&)): Likewise. (_Rb_tree::equal_range): Use _Base_ptr for end pointer. (_Rb_tree::_M_get_insert_unique_pos): Likewise. (_Rb_tree::_M_get_insert_equal_pos): Likewise. (_Rb_tree::_M_insert_equal_lower_node): Likewise. (_Rb_tree::_M_insert_unique, _Rb_tree::_M_emplace_unique, _Rb_tree::_M_emplace_hint_unique): Remove static_cast. From-SVN: r223746 --- libstdc++-v3/ChangeLog | 23 +++++ libstdc++-v3/include/bits/stl_tree.h | 141 ++++++++++++--------------- 2 files changed, 87 insertions(+), 77 deletions(-) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 1e5b30c8aac..cadee8312b4 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,5 +1,28 @@ 2015-05-27 Jonathan Wakely + * include/bits/stl_tree.h (_Rb_tree::_M_end()): Return _Base_ptr + instead of downcasting. + (_Rb_tree::_M_copy): Change second parameter to _Base_ptr. + (_Rb_tree::_M_lower_bound, _Rb_tree:_M_upper_bound): Likewise. + (_Rb_tree::_S_iter): Remove. + (_Rb_tree::_S_lower_bound_tr, _Rb_tree::_S_upper_bound_tr): Remove. + (_Rb_tree::_M_find_tr(const _Kt&) const): Call _M_lower_bound_tr + instead of _S_lower_bound_tr + (_Rb_tree::_M_find_tr(const _Kt&)): Call const overload. + (_Rb_tree::_M_lower_bound_tr(const _Kt&) const): Do the search here + instead of calling _S_lower_bound_tr. + (_Rb_tree::_M_lower_bound_tr(const _Kt&)): Call const overload. + (_Rb_tree::_M_upper_bound_tr(const _Kt&) const): Do the search here + instead of calling _S_upper_bound_tr. + (_Rb_tree::_M_upper_bound_tr(const _Kt&)): Call const overload. + (_Rb_tree::_M_equal_range_tr(const _Kt&)): Likewise. + (_Rb_tree::equal_range): Use _Base_ptr for end pointer. + (_Rb_tree::_M_get_insert_unique_pos): Likewise. + (_Rb_tree::_M_get_insert_equal_pos): Likewise. + (_Rb_tree::_M_insert_equal_lower_node): Likewise. + (_Rb_tree::_M_insert_unique, _Rb_tree::_M_emplace_unique, + _Rb_tree::_M_emplace_hint_unique): Remove static_cast. + PR libstdc++/66017 * include/bits/stl_tree.h (_Rb_tree_node): Use __aligned_membuf. (_Rb_tree_iterator, _Rb_tree_const_iterator): Support construction diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h index d39042f1aaf..240f5228530 100644 --- a/libstdc++-v3/include/bits/stl_tree.h +++ b/libstdc++-v3/include/bits/stl_tree.h @@ -658,13 +658,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION (this->_M_impl._M_header._M_parent); } - _Link_type + _Base_ptr _M_end() _GLIBCXX_NOEXCEPT - { return reinterpret_cast<_Link_type>(&this->_M_impl._M_header); } + { return &this->_M_impl._M_header; } - _Const_Link_type + _Const_Base_ptr _M_end() const _GLIBCXX_NOEXCEPT - { return reinterpret_cast<_Const_Link_type>(&this->_M_impl._M_header); } + { return &this->_M_impl._M_header; } static const_reference _S_value(_Const_Link_type __x) @@ -774,10 +774,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template _Link_type - _M_copy(_Const_Link_type __x, _Link_type __p, _NodeGen&); + _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&); _Link_type - _M_copy(_Const_Link_type __x, _Link_type __p) + _M_copy(_Const_Link_type __x, _Base_ptr __p) { _Alloc_node __an(*this); return _M_copy(__x, __p, __an); @@ -787,19 +787,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_erase(_Link_type __x); iterator - _M_lower_bound(_Link_type __x, _Link_type __y, + _M_lower_bound(_Link_type __x, _Base_ptr __y, const _Key& __k); const_iterator - _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y, + _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y, const _Key& __k) const; iterator - _M_upper_bound(_Link_type __x, _Link_type __y, + _M_upper_bound(_Link_type __x, _Base_ptr __y, const _Key& __k); const_iterator - _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y, + _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y, const _Key& __k) const; public: @@ -1117,43 +1117,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __is_transparent<_Cmp, _Kt, __void_t> { typedef void type; }; - static auto _S_iter(_Link_type __x) { return iterator(__x); } - - static auto _S_iter(_Const_Link_type __x) { return const_iterator(__x); } - - template - static auto - _S_lower_bound_tr(_Cmp& __cmp, _Link __x, _Link __y, const _Kt& __k) - { - while (__x != 0) - if (!__cmp(_S_key(__x), __k)) - __y = __x, __x = _S_left(__x); - else - __x = _S_right(__x); - return _S_iter(__y); - } - - template - static auto - _S_upper_bound_tr(_Cmp& __cmp, _Link __x, _Link __y, const _Kt& __k) - { - while (__x != 0) - if (__cmp(__k, _S_key(__x))) - __y = __x, __x = _S_left(__x); - else - __x = _S_right(__x); - return _S_iter(__y); - } - template::type> iterator _M_find_tr(const _Kt& __k) { - auto& __cmp = _M_impl._M_key_compare; - auto __j = _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k); - return (__j == end() || __cmp(__k, _S_key(__j._M_node))) - ? end() : __j; + const _Rb_tree* __const_this = this; + return __const_this->_M_find_tr(__k)._M_const_cast(); } template_M_lower_bound_tr(__k)._M_const_cast(); } template_M_upper_bound_tr(__k)._M_const_cast(); } template _M_equal_range_tr(const _Kt& __k) { - auto __low = _M_lower_bound_tr(__k); - auto __high = __low; - auto& __cmp = _M_impl._M_key_compare; - while (__high != end() && !__cmp(__k, _S_key(__high._M_node))) - ++__high; - return { __low, __high }; + const _Rb_tree* __const_this = this; + auto __ret = __const_this->_M_equal_range_tr(__k); + return { __ret.first._M_const_cast(), __ret.second._M_const_cast() }; } template typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: - _M_copy(_Const_Link_type __x, _Link_type __p, _NodeGen& __node_gen) + _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen) { // Structural copy. __x and __p must be non-null. _Link_type __top = _M_clone_node(__x, __node_gen); @@ -1621,7 +1606,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: - _M_lower_bound(_Link_type __x, _Link_type __y, + _M_lower_bound(_Link_type __x, _Base_ptr __y, const _Key& __k) { while (__x != 0) @@ -1637,7 +1622,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: - _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y, + _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y, const _Key& __k) const { while (__x != 0) @@ -1653,7 +1638,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: - _M_upper_bound(_Link_type __x, _Link_type __y, + _M_upper_bound(_Link_type __x, _Base_ptr __y, const _Key& __k) { while (__x != 0) @@ -1669,7 +1654,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: - _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y, + _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y, const _Key& __k) const { while (__x != 0) @@ -1690,7 +1675,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION equal_range(const _Key& __k) { _Link_type __x = _M_begin(); - _Link_type __y = _M_end(); + _Base_ptr __y = _M_end(); while (__x != 0) { if (_M_impl._M_key_compare(_S_key(__x), __k)) @@ -1699,7 +1684,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __y = __x, __x = _S_left(__x); else { - _Link_type __xu(__x), __yu(__y); + _Link_type __xu(__x); + _Base_ptr __yu(__y); __y = __x, __x = _S_left(__x); __xu = _S_right(__xu); return pair _Res; _Link_type __x = _M_begin(); - _Link_type __y = _M_end(); + _Base_ptr __y = _M_end(); bool __comp = true; while (__x != 0) { @@ -1834,7 +1821,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { typedef pair<_Base_ptr, _Base_ptr> _Res; _Link_type __x = _M_begin(); - _Link_type __y = _M_end(); + _Base_ptr __y = _M_end(); while (__x != 0) { __y = __x; @@ -1870,7 +1857,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION true); } - return _Res(iterator(static_cast<_Link_type>(__res.first)), false); + return _Res(iterator(__res.first), false); } template(__res.first)); + return iterator(__res.first); } template(__res.first)), false); + return _Res(iterator(__res.first), false); } __catch(...) { @@ -2177,7 +2164,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return _M_insert_node(__res.first, __res.second, __z); _M_drop_node(__z); - return iterator(static_cast<_Link_type>(__res.first)); + return iterator(__res.first); } __catch(...) { -- 2.30.2