From b4c70e89da092f437f0b1b8b97d5beef454d5198 Mon Sep 17 00:00:00 2001 From: Gawain Bolton Date: Wed, 30 Jul 2003 15:01:58 +0000 Subject: [PATCH] re PR libstdc++/11504 (-Wcast-qual vs. stl_tree) 2003-07-30 Gawain Bolton PR libstdc++/11504. * include/bits/stl_tree.h: Replace C-style casts with C++-style casts. Changes to avoid casting away constness. Eliminate _Rb_tree_base_iterator class. Change _Rb_tree_iterator to use initialization lists. Move out implementation of __black_count() to... * src/stl_tree.cc: ...here and rename _Rb_tree_black_count(). Rename_Rb_tree_base_iterator::_M_increment() to _Rb_tree_increment and _Rb_tree_base_iterator::_M_decrement() to _Rb_tree_decrement. * config/linker-map.gnu: Add and change symbols here. From-SVN: r69958 --- libstdc++-v3/ChangeLog | 14 ++ libstdc++-v3/config/linker-map.gnu | 5 +- libstdc++-v3/include/bits/stl_tree.h | 254 +++++++++++++++------------ libstdc++-v3/src/stl_tree.cc | 67 ++++--- 4 files changed, 203 insertions(+), 137 deletions(-) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 90626cc3de3..4dc6b15de44 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,17 @@ +2003-07-30 Gawain Bolton + + PR libstdc++/11504. + * include/bits/stl_tree.h: Replace C-style casts with C++-style + casts. Changes to avoid casting away constness. Eliminate + _Rb_tree_base_iterator class. Change _Rb_tree_iterator to use + initialization lists. Move out implementation of __black_count() + to... + * src/stl_tree.cc: ...here and rename _Rb_tree_black_count(). + Rename_Rb_tree_base_iterator::_M_increment() to + _Rb_tree_increment and _Rb_tree_base_iterator::_M_decrement() to + _Rb_tree_decrement. + * config/linker-map.gnu: Add and change symbols here. + 2003-07-30 Jonathan Wakely * docs/html/22_locale/howto.html: Use locale::classic() instead diff --git a/libstdc++-v3/config/linker-map.gnu b/libstdc++-v3/config/linker-map.gnu index 4f0db8d79d1..fa54dcf1a05 100644 --- a/libstdc++-v3/config/linker-map.gnu +++ b/libstdc++-v3/config/linker-map.gnu @@ -76,9 +76,10 @@ GLIBCXX_3.4 { _ZSt9has_facet*; # _Rb_tree - _ZNSt22_Rb_tree_base_iterator12_M_decrementEv; - _ZNSt22_Rb_tree_base_iterator12_M_incrementEv; + _ZSt18_Rb_tree_decrementPSt18_Rb_tree_node_base; + _ZSt18_Rb_tree_incrementPSt18_Rb_tree_node_base; _ZSt18_Rb_tree_rebalancePSt18_Rb_tree_node_baseRS0_; + _ZSt20_Rb_tree_black_countPKSt18_Rb_tree_node_baseS1_; _ZSt20_Rb_tree_rotate_leftPSt18_Rb_tree_node_baseRS0_; _ZSt21_Rb_tree_rotate_rightPSt18_Rb_tree_node_baseRS0_; _ZSt28_Rb_tree_rebalance_for_erasePSt18_Rb_tree_node_baseRS_; diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h index 920e591e09a..fd81a6755cd 100644 --- a/libstdc++-v3/include/bits/stl_tree.h +++ b/libstdc++-v3/include/bits/stl_tree.h @@ -95,6 +95,7 @@ namespace std struct _Rb_tree_node_base { typedef _Rb_tree_node_base* _Base_ptr; + typedef const _Rb_tree_node_base* _Const_Base_ptr; _Rb_tree_color _M_color; _Base_ptr _M_parent; @@ -108,12 +109,26 @@ namespace std return __x; } + static _Const_Base_ptr + _S_minimum(_Const_Base_ptr __x) + { + while (__x->_M_left != 0) __x = __x->_M_left; + return __x; + } + static _Base_ptr _S_maximum(_Base_ptr __x) { while (__x->_M_right != 0) __x = __x->_M_right; return __x; } + + static _Const_Base_ptr + _S_maximum(_Const_Base_ptr __x) + { + while (__x->_M_right != 0) __x = __x->_M_right; + return __x; + } }; template @@ -123,23 +138,14 @@ namespace std _Val _M_value_field; }; - struct _Rb_tree_base_iterator - { - typedef _Rb_tree_node_base::_Base_ptr _Base_ptr; - typedef bidirectional_iterator_tag iterator_category; - typedef ptrdiff_t difference_type; - - _Base_ptr _M_node; - - void - _M_increment(); + _Rb_tree_node_base* + _Rb_tree_increment(_Rb_tree_node_base* __x); - void - _M_decrement(); - }; + _Rb_tree_node_base* + _Rb_tree_decrement(_Rb_tree_node_base* __x); template - struct _Rb_tree_iterator : public _Rb_tree_base_iterator + struct _Rb_tree_iterator { typedef _Val value_type; typedef _Ref reference; @@ -147,23 +153,36 @@ namespace std typedef _Rb_tree_iterator<_Val, _Val&, _Val*> iterator; typedef _Rb_tree_iterator<_Val, const _Val&, const _Val*> const_iterator; + typedef _Rb_tree_node_base::_Base_ptr _Base_ptr; + typedef bidirectional_iterator_tag iterator_category; + typedef ptrdiff_t difference_type; typedef _Rb_tree_iterator<_Val, _Ref, _Ptr> _Self; typedef _Rb_tree_node<_Val>* _Link_type; + typedef const _Rb_tree_node<_Val>* _Const_Link_type; _Rb_tree_iterator() {} - _Rb_tree_iterator(_Rb_tree_node_base* __x) { _M_node = __x; } - _Rb_tree_iterator(const iterator& __it) { _M_node = __it._M_node; } + + _Rb_tree_iterator(_Link_type __x) + : _M_node(__x) {} + + _Rb_tree_iterator(_Const_Link_type __x) + : _M_node(const_cast<_Link_type>(__x)) {} + + _Rb_tree_iterator(const iterator& __it) + : _M_node(__it._M_node) {} reference - operator*() const { return _Link_type(_M_node)->_M_value_field; } + operator*() const + { return static_cast<_Link_type>(_M_node)->_M_value_field; } pointer - operator->() const { return &(operator*()); } + operator->() const + { return &static_cast<_Link_type>(_M_node)->_M_value_field; } _Self& operator++() { - _M_increment(); + _M_node = _Rb_tree_increment(_M_node); return *this; } @@ -171,20 +190,26 @@ namespace std operator++(int) { _Self __tmp = *this; - _M_increment(); + _M_node = _Rb_tree_increment(_M_node); return __tmp; } _Self& - operator--() { _M_decrement(); return *this; } + operator--() + { + _M_node = _Rb_tree_decrement(_M_node); + return *this; + } _Self operator--(int) { _Self __tmp = *this; - _M_decrement(); + _M_node = _Rb_tree_decrement(_M_node); return __tmp; } + + _Base_ptr _M_node; }; template @@ -312,6 +337,7 @@ namespace std protected: typedef _Rb_tree_node_base* _Base_ptr; + typedef const _Rb_tree_node_base* _Const_Base_ptr; typedef _Rb_tree_node<_Val> _Rb_tree_node; public: @@ -322,6 +348,7 @@ namespace std typedef value_type& reference; typedef const value_type& const_reference; typedef _Rb_tree_node* _Link_type; + typedef const _Rb_tree_node* _Const_Link_type; typedef size_t size_type; typedef ptrdiff_t difference_type; @@ -348,7 +375,7 @@ namespace std } _Link_type - _M_clone_node(_Link_type __x) + _M_clone_node(_Const_Link_type __x) { _Link_type __tmp = _M_create_node(__x->_M_value_field); __tmp->_M_color = __x->_M_color; @@ -367,58 +394,75 @@ namespace std size_type _M_node_count; // keeps track of size of tree _Compare _M_key_compare; - _Link_type& - _M_root() const { return (_Link_type&) this->_M_header._M_parent; } + _Base_ptr& + _M_root() { return this->_M_header._M_parent; } - _Link_type& - _M_leftmost() const { return (_Link_type&) this->_M_header._M_left; } + _Const_Base_ptr + _M_root() const { return this->_M_header._M_parent; } - _Link_type& - _M_rightmost() const { return (_Link_type&) this->_M_header._M_right; } + _Base_ptr& + _M_leftmost() { return this->_M_header._M_left; } + + _Const_Base_ptr + _M_leftmost() const { return this->_M_header._M_left; } + + _Base_ptr& + _M_rightmost() { return this->_M_header._M_right; } + + _Const_Base_ptr + _M_rightmost() const { return this->_M_header._M_right; } _Link_type - _M_end() const { return (_Link_type) &this->_M_header; } - - static _Link_type& - _S_left(_Link_type __x) { return (_Link_type&)(__x->_M_left); } + _M_begin() { return static_cast<_Link_type>(this->_M_header._M_parent); } + + _Const_Link_type + _M_begin() const { return static_cast<_Const_Link_type>(this->_M_header._M_parent); } - static _Link_type& - _S_right(_Link_type __x) { return (_Link_type&)(__x->_M_right); } + _Link_type + _M_end() { return static_cast<_Link_type>(&this->_M_header); } - static _Link_type& - _S_parent(_Link_type __x) { return (_Link_type&)(__x->_M_parent); } + _Const_Link_type + _M_end() const { return static_cast<_Const_Link_type>(&this->_M_header); } - static reference - _S_value(_Link_type __x) { return __x->_M_value_field; } + static const_reference + _S_value(_Const_Link_type __x) { return __x->_M_value_field; } static const _Key& - _S_key(_Link_type __x) { return _KeyOfValue()(_S_value(__x)); } + _S_key(_Const_Link_type __x) { return _KeyOfValue()(_S_value(__x)); } + + static _Link_type + _S_left(_Base_ptr __x) { return static_cast<_Link_type>(__x->_M_left); } - static _Link_type& - _S_left(_Base_ptr __x) { return (_Link_type&)(__x->_M_left); } + static _Const_Link_type + _S_left(_Const_Base_ptr __x) { return static_cast<_Const_Link_type>(__x->_M_left); } - static _Link_type& - _S_right(_Base_ptr __x) { return (_Link_type&)(__x->_M_right); } + static _Link_type + _S_right(_Base_ptr __x) { return static_cast<_Link_type>(__x->_M_right); } - static _Link_type& - _S_parent(_Base_ptr __x) { return (_Link_type&)(__x->_M_parent); } + static _Const_Link_type + _S_right(_Const_Base_ptr __x) { return static_cast<_Const_Link_type>(__x->_M_right); } - static reference - _S_value(_Base_ptr __x) { return ((_Link_type)__x)->_M_value_field; } + static const_reference + _S_value(_Const_Base_ptr __x) { return static_cast<_Const_Link_type>(__x)->_M_value_field; } static const _Key& - _S_key(_Base_ptr __x) { return _KeyOfValue()(_S_value(_Link_type(__x)));} + _S_key(_Const_Base_ptr __x) { return _KeyOfValue()(_S_value(__x)); } + + static _Base_ptr + _S_minimum(_Base_ptr __x) + { return _Rb_tree_node_base::_S_minimum(__x); } - static _Rb_tree_color& - _S_color(_Base_ptr __x) { return __x->_M_color; } + static _Const_Base_ptr + _S_minimum(_Const_Base_ptr __x) + { return _Rb_tree_node_base::_S_minimum(__x); } - static _Link_type - _S_minimum(_Link_type __x) - { return (_Link_type) _Rb_tree_node_base::_S_minimum(__x); } + static _Base_ptr + _S_maximum(_Base_ptr __x) + { return _Rb_tree_node_base::_S_maximum(__x); } - static _Link_type - _S_maximum(_Link_type __x) - { return (_Link_type) _Rb_tree_node_base::_S_maximum(__x); } + static _Const_Base_ptr + _S_maximum(_Const_Base_ptr __x) + { return _Rb_tree_node_base::_S_maximum(__x); } public: typedef _Rb_tree_iterator iterator; @@ -433,7 +477,7 @@ namespace std _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v); _Link_type - _M_copy(_Link_type __x, _Link_type __p); + _M_copy(_Const_Link_type __x, _Link_type __p); void _M_erase(_Link_type __x); @@ -460,8 +504,8 @@ namespace std _M_empty_initialize(); else { - _S_color(&this->_M_header) = _S_red; - _M_root() = _M_copy(__x._M_root(), _M_end()); + this->_M_header._M_color = _S_red; + _M_root() = _M_copy(__x._M_begin(), _M_end()); _M_leftmost() = _S_minimum(_M_root()); _M_rightmost() = _S_maximum(_M_root()); } @@ -477,7 +521,7 @@ namespace std void _M_empty_initialize() { // Used to distinguish header from __root, in iterator.operator++. - _S_color(&this->_M_header) = _S_red; + this->_M_header._M_color = _S_red; _M_root() = 0; _M_leftmost() = _M_end(); _M_rightmost() = _M_end(); @@ -489,16 +533,16 @@ namespace std key_comp() const { return _M_key_compare; } iterator - begin() { return _M_leftmost(); } + begin() { return static_cast<_Link_type>(this->_M_header._M_left); } const_iterator - begin() const { return _M_leftmost(); } + begin() const { return static_cast<_Const_Link_type>(this->_M_header._M_left); } iterator - end() { return &this->_M_header; } + end() { return static_cast<_Link_type>(&this->_M_header); } const_iterator - end() const { return const_cast<_Base_ptr>(&this->_M_header); } + end() const { return static_cast<_Const_Link_type>(&this->_M_header); } reverse_iterator rbegin() { return reverse_iterator(end()); } @@ -562,7 +606,7 @@ namespace std { if (_M_node_count != 0) { - _M_erase(_M_root()); + _M_erase(_M_begin()); _M_leftmost() = _M_end(); _M_root() = 0; _M_rightmost() = _M_end(); @@ -678,7 +722,7 @@ namespace std } else { - _M_root() = _M_copy(__x._M_root(), _M_end()); + _M_root() = _M_copy(__x._M_begin(), _M_end()); _M_leftmost() = _S_minimum(_M_root()); _M_rightmost() = _S_maximum(_M_root()); _M_node_count = __x._M_node_count; @@ -693,15 +737,15 @@ namespace std _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: _M_insert(_Base_ptr __x_, _Base_ptr __y_, const _Val& __v) { - _Link_type __x = (_Link_type) __x_; - _Link_type __y = (_Link_type) __y_; + _Link_type __x = static_cast<_Link_type>(__x_); + _Link_type __y = static_cast<_Link_type>(__y_); _Link_type __z; if (__y == &this->_M_header || __x != 0 || _M_key_compare(_KeyOfValue()(__v), _S_key(__y))) { __z = _M_create_node(__v); - _S_left(__y) = __z; // also makes _M_leftmost() = __z + __y->_M_left = __z; // also makes _M_leftmost() = __z // when __y == &_M_header if (__y == &this->_M_header) { @@ -714,14 +758,14 @@ namespace std else { __z = _M_create_node(__v); - _S_right(__y) = __z; + __y->_M_right = __z; // Maintain _M_rightmost() pointing to max node. if (__y == _M_rightmost()) _M_rightmost() = __z; } - _S_parent(__z) = __y; - _S_left(__z) = 0; - _S_right(__z) = 0; + __z->_M_parent = __y; + __z->_M_left = 0; + __z->_M_right = 0; _Rb_tree_rebalance(__z, this->_M_header._M_parent); ++_M_node_count; return iterator(__z); @@ -733,8 +777,8 @@ namespace std _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: insert_equal(const _Val& __v) { + _Link_type __x = _M_begin(); _Link_type __y = _M_end(); - _Link_type __x = _M_root(); while (__x != 0) { __y = __x; @@ -796,8 +840,8 @@ namespace std _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: insert_unique(const _Val& __v) { + _Link_type __x = _M_begin(); _Link_type __y = _M_end(); - _Link_type __x = _M_root(); bool __comp = true; while (__x != 0) { @@ -930,8 +974,8 @@ namespace std _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(iterator __position) { _Link_type __y = - (_Link_type) _Rb_tree_rebalance_for_erase(__position._M_node, - this->_M_header); + static_cast<_Link_type>(_Rb_tree_rebalance_for_erase(__position._M_node, + this->_M_header)); destroy_node(__y); --_M_node_count; } @@ -951,7 +995,7 @@ namespace std typename _Compare, typename _Alloc> typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type _Rb_tree<_Key,_Val,_KoV,_Compare,_Alloc>:: - _M_copy(_Link_type __x, _Link_type __p) + _M_copy(_Const_Link_type __x, _Link_type __p) { // Structural copy. __x and __p must be non-null. _Link_type __top = _M_clone_node(__x); @@ -1025,8 +1069,8 @@ namespace std typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k) { - _Link_type __y = _M_end(); // Last node which is not less than __k. - _Link_type __x = _M_root(); // Current node. + _Link_type __x = _M_begin(); // Current node. + _Link_type __y = _M_end(); // Last node which is not less than __k. while (__x != 0) if (!_M_key_compare(_S_key(__x), __k)) @@ -1045,8 +1089,8 @@ namespace std _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: find(const _Key& __k) const { - _Link_type __y = _M_end(); // Last node which is not less than __k. - _Link_type __x = _M_root(); // Current node. + _Const_Link_type __x = _M_begin(); // Current node. + _Const_Link_type __y = _M_end(); // Last node which is not less than __k. while (__x != 0) { @@ -1077,8 +1121,8 @@ namespace std _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: lower_bound(const _Key& __k) { - _Link_type __y = _M_end(); // Last node which is not less than __k - _Link_type __x = _M_root(); // Current node. + _Link_type __x = _M_begin(); // Current node. + _Link_type __y = _M_end(); // Last node which is not less than __k. while (__x != 0) if (!_M_key_compare(_S_key(__x), __k)) @@ -1095,8 +1139,8 @@ namespace std _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: lower_bound(const _Key& __k) const { - _Link_type __y = _M_end(); // Last node which is not less than __k. - _Link_type __x = _M_root(); // Current node. + _Const_Link_type __x = _M_begin(); // Current node. + _Const_Link_type __y = _M_end(); // Last node which is not less than __k. while (__x != 0) if (!_M_key_compare(_S_key(__x), __k)) @@ -1113,8 +1157,8 @@ namespace std _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: upper_bound(const _Key& __k) { + _Link_type __x = _M_begin(); // Current node. _Link_type __y = _M_end(); // Last node which is greater than __k. - _Link_type __x = _M_root(); // Current node. while (__x != 0) if (_M_key_compare(__k, _S_key(__x))) @@ -1131,8 +1175,8 @@ namespace std _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: upper_bound(const _Key& __k) const { - _Link_type __y = _M_end(); // Last node which is greater than __k. - _Link_type __x = _M_root(); // Current node. + _Const_Link_type __x = _M_begin(); // Current node. + _Const_Link_type __y = _M_end(); // Last node which is greater than __k. while (__x != 0) if (_M_key_compare(__k, _S_key(__x))) @@ -1164,23 +1208,9 @@ namespace std upper_bound(__k)); } - inline int - __black_count(_Rb_tree_node_base* __node, _Rb_tree_node_base* __root) - { - if (__node == 0) - return 0; - int __sum = 0; - do - { - if (__node->_M_color == _S_black) - ++__sum; - if (__node == __root) - break; - __node = __node->_M_parent; - } - while (1); - return __sum; - } + unsigned int + _Rb_tree_black_count(const _Rb_tree_node_base* __node, + const _Rb_tree_node_base* __root); template @@ -1192,12 +1222,12 @@ namespace std this->_M_header._M_left == &this->_M_header && this->_M_header._M_right == &this->_M_header; - int __len = __black_count(_M_leftmost(), _M_root()); + unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root()); for (const_iterator __it = begin(); __it != end(); ++__it) { - _Link_type __x = (_Link_type) __it._M_node; - _Link_type __L = _S_left(__x); - _Link_type __R = _S_right(__x); + _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node); + _Const_Link_type __L = _S_left(__x); + _Const_Link_type __R = _S_right(__x); if (__x->_M_color == _S_red) if ((__L && __L->_M_color == _S_red) @@ -1209,7 +1239,7 @@ namespace std if (__R && _M_key_compare(_S_key(__R), _S_key(__x))) return false; - if (!__L && !__R && __black_count(__x, _M_root()) != __len) + if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len) return false; } diff --git a/libstdc++-v3/src/stl_tree.cc b/libstdc++-v3/src/stl_tree.cc index 99f8143df1d..eac141f0f79 100644 --- a/libstdc++-v3/src/stl_tree.cc +++ b/libstdc++-v3/src/stl_tree.cc @@ -59,51 +59,53 @@ namespace std { - void - _Rb_tree_base_iterator::_M_increment() + _Rb_tree_node_base* + _Rb_tree_increment(_Rb_tree_node_base* __x) { - if (_M_node->_M_right != 0) + if (__x->_M_right != 0) { - _M_node = _M_node->_M_right; - while (_M_node->_M_left != 0) - _M_node = _M_node->_M_left; + __x = __x->_M_right; + while (__x->_M_left != 0) + __x = __x->_M_left; } else { - _Base_ptr __y = _M_node->_M_parent; - while (_M_node == __y->_M_right) + _Rb_tree_node_base* __y = __x->_M_parent; + while (__x == __y->_M_right) { - _M_node = __y; + __x = __y; __y = __y->_M_parent; } - if (_M_node->_M_right != __y) - _M_node = __y; + if (__x->_M_right != __y) + __x = __y; } + return __x; } - void - _Rb_tree_base_iterator::_M_decrement() + _Rb_tree_node_base* + _Rb_tree_decrement(_Rb_tree_node_base* __x) { - if (_M_node->_M_color == _S_red - && _M_node->_M_parent->_M_parent == _M_node) - _M_node = _M_node->_M_right; - else if (_M_node->_M_left != 0) + if (__x->_M_color == _S_red + && __x->_M_parent->_M_parent == __x) + __x = __x->_M_right; + else if (__x->_M_left != 0) { - _Base_ptr __y = _M_node->_M_left; + _Rb_tree_node_base* __y = __x->_M_left; while (__y->_M_right != 0) __y = __y->_M_right; - _M_node = __y; + __x = __y; } else { - _Base_ptr __y = _M_node->_M_parent; - while (_M_node == __y->_M_left) + _Rb_tree_node_base* __y = __x->_M_parent; + while (__x == __y->_M_left) { - _M_node = __y; + __x = __y; __y = __y->_M_parent; } - _M_node = __y; + __x = __y; } + return __x; } void @@ -362,4 +364,23 @@ namespace std } return __y; } + + unsigned int + _Rb_tree_black_count(const _Rb_tree_node_base* __node, + const _Rb_tree_node_base* __root) + { + if (__node == 0) + return 0; + unsigned int __sum = 0; + do + { + if (__node->_M_color == _S_black) + ++__sum; + if (__node == __root) + break; + __node = __node->_M_parent; + } + while (1); + return __sum; + } } // namespace std -- 2.30.2