diff options
author | Jonathan Wakely <jwakely@redhat.com> | 2015-05-27 12:18:44 +0100 |
---|---|---|
committer | Jonathan Wakely <redi@gcc.gnu.org> | 2015-05-27 12:18:44 +0100 |
commit | 151fbaac5c78c4e9b749fc9e916f78b0ba63b153 (patch) | |
tree | 21ba4553e597d873f4bd7a0cf0bb337147febc99 /libstdc++-v3 | |
parent | 2097b5b029851d531a1424a0092992d4c9f650e4 (diff) | |
download | gcc-151fbaac5c78c4e9b749fc9e916f78b0ba63b153.zip gcc-151fbaac5c78c4e9b749fc9e916f78b0ba63b153.tar.gz gcc-151fbaac5c78c4e9b749fc9e916f78b0ba63b153.tar.bz2 |
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
Diffstat (limited to 'libstdc++-v3')
-rw-r--r-- | libstdc++-v3/ChangeLog | 23 | ||||
-rw-r--r-- | 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 1e5b30c..cadee83 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,5 +1,28 @@ 2015-05-27 Jonathan Wakely <jwakely@redhat.com> + * 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 d39042f..240f522 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<typename _NodeGen> _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<typename _Cmp::is_transparent>> { 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<typename _Cmp, typename _Link, typename _Kt> - 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<typename _Cmp, typename _Link, typename _Kt> - 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<typename _Kt, typename _Req = typename __is_transparent<_Compare, _Kt>::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<typename _Kt, @@ -1161,10 +1131,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION const_iterator _M_find_tr(const _Kt& __k) const { - 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; + auto __j = _M_lower_bound_tr(__k); + if (__j != end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node))) + __j = end(); + return __j; } template<typename _Kt, @@ -1181,8 +1151,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION iterator _M_lower_bound_tr(const _Kt& __k) { - auto& __cmp = _M_impl._M_key_compare; - return _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k); + const _Rb_tree* __const_this = this; + return __const_this->_M_lower_bound_tr(__k)._M_const_cast(); } template<typename _Kt, @@ -1190,8 +1160,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION const_iterator _M_lower_bound_tr(const _Kt& __k) const { - auto& __cmp = _M_impl._M_key_compare; - return _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k); + auto __x = _M_begin(); + auto __y = _M_end(); + while (__x != 0) + if (!_M_impl._M_key_compare(_S_key(__x), __k)) + { + __y = __x; + __x = _S_left(__x); + } + else + __x = _S_right(__x); + return const_iterator(__y); } template<typename _Kt, @@ -1199,8 +1178,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION iterator _M_upper_bound_tr(const _Kt& __k) { - auto& __cmp = _M_impl._M_key_compare; - return _S_upper_bound_tr(__cmp, _M_begin(), _M_end(), __k); + const _Rb_tree* __const_this = this; + return __const_this->_M_upper_bound_tr(__k)._M_const_cast(); } template<typename _Kt, @@ -1208,8 +1187,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION const_iterator _M_upper_bound_tr(const _Kt& __k) const { - auto& __cmp = _M_impl._M_key_compare; - return _S_upper_bound_tr(__cmp, _M_begin(), _M_end(), __k); + auto __x = _M_begin(); + auto __y = _M_end(); + while (__x != 0) + if (_M_impl._M_key_compare(__k, _S_key(__x))) + { + __y = __x; + __x = _S_left(__x); + } + else + __x = _S_right(__x); + return const_iterator(__y); } template<typename _Kt, @@ -1217,12 +1205,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION pair<iterator, iterator> _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 _Kt, @@ -1553,7 +1538,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION #endif { _Link_type __x = _M_begin(); - _Link_type __y = _M_end(); + _Base_ptr __y = _M_end(); while (__x != 0) { __y = __x; @@ -1568,7 +1553,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _NodeGen> 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<iterator, @@ -1721,7 +1707,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION equal_range(const _Key& __k) const { _Const_Link_type __x = _M_begin(); - _Const_Link_type __y = _M_end(); + _Const_Base_ptr __y = _M_end(); while (__x != 0) { if (_M_impl._M_key_compare(_S_key(__x), __k)) @@ -1730,7 +1716,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __y = __x, __x = _S_left(__x); else { - _Const_Link_type __xu(__x), __yu(__y); + _Const_Link_type __xu(__x); + _Const_Base_ptr __yu(__y); __y = __x, __x = _S_left(__x); __xu = _S_right(__xu); return pair<const_iterator, @@ -1802,7 +1789,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(); 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<typename _Key, typename _Val, typename _KeyOfValue, @@ -1976,7 +1963,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return _M_insert_(__res.first, __res.second, _GLIBCXX_FORWARD(_Arg, __v), __node_gen); - return iterator(static_cast<_Link_type>(__res.first)); + return iterator(__res.first); } template<typename _Key, typename _Val, typename _KeyOfValue, @@ -2102,7 +2089,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_insert_equal_lower_node(_Link_type __z) { _Link_type __x = _M_begin(); - _Link_type __y = _M_end(); + _Base_ptr __y = _M_end(); while (__x != 0) { __y = __x; @@ -2130,7 +2117,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return _Res(_M_insert_node(__res.first, __res.second, __z), true); _M_drop_node(__z); - return _Res(iterator(static_cast<_Link_type>(__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(...) { |