This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[Patch]: libstdc++/PR11504 + constness and casting clean up
- From: Gawain Bolton <gbolton at free dot fr>
- To: libstdc++ at gcc dot gnu dot org
- Date: Sun, 27 Jul 2003 14:50:59 +0200
- Subject: [Patch]: libstdc++/PR11504 + constness and casting clean up
- Reply-to: gp dot bolton at computer dot org
Ok, after spending more time than I care to admit I've prepared another
patch which solves libstdc++/PR11504 and cleans up the constness and
casting done in stl_tree.h
Again, all C-style casts have been replaced with C++ style casts.
Changes were made where required to avoid casting away constness. With
this patch only static_casts and a single const_cast are done in the
stl_tree.h header file.
This patch also removes the _Rb_tree_base_iterator class to simplify the
_Rb_tree_iterator class and allow its constructors to use member
initialization lists.
The debugging function __black_count() has been renamed
_Rb_tree_black_count() and is no longer an inline function.
I'm also pleased to annonce this patch has nice symmetry. Adding the
_M_begin() function in fact increases the symmetry of the code with the
existing _M_end() function.
Tested with std::set, std::multiset, std::map and std::multimap on
i686-pc-linux-gnu with compile flags "-Wall -W -Wcast-align -Wcast-qual"
and gcc version 3.4 20030702 (experimental).
Cheers,
Gawain
--
Gawain Bolton
Coignieres, France
PGP Info: Key server: http://wwwkeys.pgp.net
Key id: 6EBEDEA6
Fingerprint: 65C0 0030 21D1 7A01 546A E7DB D60F 47E0 6EBE DEA6
Index: config/linker-map.gnu
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/config/linker-map.gnu,v
retrieving revision 1.45
diff -c -3 -p -r1.45 linker-map.gnu
*** config/linker-map.gnu 18 Jul 2003 02:27:13 -0000 1.45
--- config/linker-map.gnu 27 Jul 2003 12:36:03 -0000
*************** GLIBCXX_3.4 {
*** 76,84 ****
_ZSt9has_facet*;
# _Rb_tree
! _ZNSt22_Rb_tree_base_iterator12_M_decrementEv;
! _ZNSt22_Rb_tree_base_iterator12_M_incrementEv;
_ZSt18_Rb_tree_rebalancePSt18_Rb_tree_node_baseRS0_;
_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_;
--- 76,85 ----
_ZSt9has_facet*;
# _Rb_tree
! _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_;
Index: include/bits/stl_tree.h
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/include/bits/stl_tree.h,v
retrieving revision 1.27
diff -c -3 -p -r1.27 stl_tree.h
*** include/bits/stl_tree.h 14 Jul 2003 02:52:04 -0000 1.27
--- include/bits/stl_tree.h 27 Jul 2003 12:36:03 -0000
*************** namespace std
*** 95,100 ****
--- 95,101 ----
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;
*************** namespace std
*** 108,119 ****
--- 109,134 ----
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<typename _Val>
*************** namespace std
*** 123,145 ****
_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();
! void
! _M_decrement();
! };
template<typename _Val, typename _Ref, typename _Ptr>
! struct _Rb_tree_iterator : public _Rb_tree_base_iterator
{
typedef _Val value_type;
typedef _Ref reference;
--- 138,151 ----
_Val _M_value_field;
};
! _Rb_tree_node_base*
! _Rb_tree_increment(_Rb_tree_node_base* __x);
! _Rb_tree_node_base*
! _Rb_tree_decrement(_Rb_tree_node_base* __x);
template<typename _Val, typename _Ref, typename _Ptr>
! struct _Rb_tree_iterator
{
typedef _Val value_type;
typedef _Ref reference;
*************** namespace std
*** 147,169 ****
typedef _Rb_tree_iterator<_Val, _Val&, _Val*> iterator;
typedef _Rb_tree_iterator<_Val, const _Val&, const _Val*>
const_iterator;
typedef _Rb_tree_iterator<_Val, _Ref, _Ptr> _Self;
typedef _Rb_tree_node<_Val>* _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; }
reference
! operator*() const { return _Link_type(_M_node)->_M_value_field; }
pointer
! operator->() const { return &(operator*()); }
_Self&
operator++()
{
! _M_increment();
return *this;
}
--- 153,188 ----
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(_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 static_cast<_Link_type>(_M_node)->_M_value_field; }
pointer
! operator->() const
! { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
_Self&
operator++()
{
! _M_node = _Rb_tree_increment(_M_node);
return *this;
}
*************** namespace std
*** 171,190 ****
operator++(int)
{
_Self __tmp = *this;
! _M_increment();
return __tmp;
}
_Self&
! operator--() { _M_decrement(); return *this; }
_Self
operator--(int)
{
_Self __tmp = *this;
! _M_decrement();
return __tmp;
}
};
template<typename _Val, typename _Ref, typename _Ptr>
--- 190,215 ----
operator++(int)
{
_Self __tmp = *this;
! _M_node = _Rb_tree_increment(_M_node);
return __tmp;
}
_Self&
! operator--()
! {
! _M_node = _Rb_tree_decrement(_M_node);
! return *this;
! }
_Self
operator--(int)
{
_Self __tmp = *this;
! _M_node = _Rb_tree_decrement(_M_node);
return __tmp;
}
+
+ _Base_ptr _M_node;
};
template<typename _Val, typename _Ref, typename _Ptr>
*************** namespace std
*** 312,317 ****
--- 337,343 ----
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:
*************** namespace std
*** 322,327 ****
--- 348,354 ----
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;
*************** namespace std
*** 348,354 ****
}
_Link_type
! _M_clone_node(_Link_type __x)
{
_Link_type __tmp = _M_create_node(__x->_M_value_field);
__tmp->_M_color = __x->_M_color;
--- 375,381 ----
}
_Link_type
! _M_clone_node(_const_Link_type __x)
{
_Link_type __tmp = _M_create_node(__x->_M_value_field);
__tmp->_M_color = __x->_M_color;
*************** namespace std
*** 367,424 ****
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; }
! _Link_type&
! _M_leftmost() const { return (_Link_type&) this->_M_header._M_left; }
! _Link_type&
! _M_rightmost() const { return (_Link_type&) 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); }
! static _Link_type&
! _S_right(_Link_type __x) { return (_Link_type&)(__x->_M_right); }
! static _Link_type&
! _S_parent(_Link_type __x) { return (_Link_type&)(__x->_M_parent); }
! static reference
! _S_value(_Link_type __x) { return __x->_M_value_field; }
static const _Key&
! _S_key(_Link_type __x) { return _KeyOfValue()(_S_value(__x)); }
! static _Link_type&
! _S_left(_Base_ptr __x) { return (_Link_type&)(__x->_M_left); }
! static _Link_type&
! _S_right(_Base_ptr __x) { return (_Link_type&)(__x->_M_right); }
! static _Link_type&
! _S_parent(_Base_ptr __x) { return (_Link_type&)(__x->_M_parent); }
! static reference
! _S_value(_Base_ptr __x) { return ((_Link_type)__x)->_M_value_field; }
! static const _Key&
! _S_key(_Base_ptr __x) { return _KeyOfValue()(_S_value(_Link_type(__x)));}
! static _Rb_tree_color&
! _S_color(_Base_ptr __x) { return __x->_M_color; }
! static _Link_type
! _S_minimum(_Link_type __x)
! { return (_Link_type) _Rb_tree_node_base::_S_minimum(__x); }
!
! static _Link_type
! _S_maximum(_Link_type __x)
! { return (_Link_type) _Rb_tree_node_base::_S_maximum(__x); }
public:
typedef _Rb_tree_iterator<value_type, reference, pointer> iterator;
--- 394,468 ----
size_type _M_node_count; // keeps track of size of tree
_Compare _M_key_compare;
! _Base_ptr&
! _M_root() { return this->_M_header._M_parent; }
! _const_Base_ptr
! _M_root() const { return this->_M_header._M_parent; }
! _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_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); }
! _Link_type
! _M_end() { return static_cast<_Link_type>(&this->_M_header); }
! _const_Link_type
! _M_end() const { return static_cast<_const_Link_type>(&this->_M_header); }
! static const_reference
! _S_value(_const_Link_type __x) { return __x->_M_value_field; }
static const _Key&
! _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 _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 static_cast<_Link_type>(__x->_M_right); }
! static _const_Link_type
! _S_right(_const_Base_ptr __x) { return static_cast<_const_Link_type>(__x->_M_right); }
! static const_reference
! _S_value(_const_Base_ptr __x) { return static_cast<_const_Link_type>(__x)->_M_value_field; }
! static const _Key&
! _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 _const_Base_ptr
! _S_minimum(_const_Base_ptr __x)
! { return _Rb_tree_node_base::_S_minimum(__x); }
!
! static _Base_ptr
! _S_maximum(_Base_ptr __x)
! { return _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<value_type, reference, pointer> iterator;
*************** namespace std
*** 433,439 ****
_M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
_Link_type
! _M_copy(_Link_type __x, _Link_type __p);
void
_M_erase(_Link_type __x);
--- 477,483 ----
_M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
_Link_type
! _M_copy(_const_Link_type __x, _Link_type __p);
void
_M_erase(_Link_type __x);
*************** namespace std
*** 460,467 ****
_M_empty_initialize();
else
{
! _S_color(&this->_M_header) = _S_red;
! _M_root() = _M_copy(__x._M_root(), _M_end());
_M_leftmost() = _S_minimum(_M_root());
_M_rightmost() = _S_maximum(_M_root());
}
--- 504,511 ----
_M_empty_initialize();
else
{
! 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());
}
*************** namespace std
*** 477,483 ****
void _M_empty_initialize()
{
// Used to distinguish header from __root, in iterator.operator++.
! _S_color(&this->_M_header) = _S_red;
_M_root() = 0;
_M_leftmost() = _M_end();
_M_rightmost() = _M_end();
--- 521,527 ----
void _M_empty_initialize()
{
// Used to distinguish header from __root, in iterator.operator++.
! this->_M_header._M_color = _S_red;
_M_root() = 0;
_M_leftmost() = _M_end();
_M_rightmost() = _M_end();
*************** namespace std
*** 489,504 ****
key_comp() const { return _M_key_compare; }
iterator
! begin() { return _M_leftmost(); }
const_iterator
! begin() const { return _M_leftmost(); }
iterator
! end() { return &this->_M_header; }
const_iterator
! end() const { return const_cast<_Base_ptr>(&this->_M_header); }
reverse_iterator
rbegin() { return reverse_iterator(end()); }
--- 533,548 ----
key_comp() const { return _M_key_compare; }
iterator
! begin() { return static_cast<_Link_type>(this->_M_header._M_left); }
const_iterator
! begin() const { return static_cast<_const_Link_type>(this->_M_header._M_left); }
iterator
! end() { return static_cast<_Link_type>(&this->_M_header); }
const_iterator
! end() const { return static_cast<_const_Link_type>(&this->_M_header); }
reverse_iterator
rbegin() { return reverse_iterator(end()); }
*************** namespace std
*** 562,568 ****
{
if (_M_node_count != 0)
{
! _M_erase(_M_root());
_M_leftmost() = _M_end();
_M_root() = 0;
_M_rightmost() = _M_end();
--- 606,612 ----
{
if (_M_node_count != 0)
{
! _M_erase(_M_begin());
_M_leftmost() = _M_end();
_M_root() = 0;
_M_rightmost() = _M_end();
*************** namespace std
*** 678,684 ****
}
else
{
! _M_root() = _M_copy(__x._M_root(), _M_end());
_M_leftmost() = _S_minimum(_M_root());
_M_rightmost() = _S_maximum(_M_root());
_M_node_count = __x._M_node_count;
--- 722,728 ----
}
else
{
! _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;
*************** namespace std
*** 693,707 ****
_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 __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
// when __y == &_M_header
if (__y == &this->_M_header)
{
--- 737,751 ----
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
_M_insert(_Base_ptr __x_, _Base_ptr __y_, const _Val& __v)
{
! _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);
! __y->_M_left = __z; // also makes _M_leftmost() = __z
// when __y == &_M_header
if (__y == &this->_M_header)
{
*************** namespace std
*** 714,727 ****
else
{
__z = _M_create_node(__v);
! _S_right(__y) = __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;
_Rb_tree_rebalance(__z, this->_M_header._M_parent);
++_M_node_count;
return iterator(__z);
--- 758,771 ----
else
{
__z = _M_create_node(__v);
! __y->_M_right = __z;
// Maintain _M_rightmost() pointing to max node.
if (__y == _M_rightmost())
_M_rightmost() = __z;
}
! __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);
*************** namespace std
*** 733,740 ****
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
insert_equal(const _Val& __v)
{
_Link_type __y = _M_end();
- _Link_type __x = _M_root();
while (__x != 0)
{
__y = __x;
--- 777,784 ----
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
insert_equal(const _Val& __v)
{
+ _Link_type __x = _M_begin();
_Link_type __y = _M_end();
while (__x != 0)
{
__y = __x;
*************** namespace std
*** 796,803 ****
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
insert_unique(const _Val& __v)
{
_Link_type __y = _M_end();
- _Link_type __x = _M_root();
bool __comp = true;
while (__x != 0)
{
--- 840,847 ----
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
insert_unique(const _Val& __v)
{
+ _Link_type __x = _M_begin();
_Link_type __y = _M_end();
bool __comp = true;
while (__x != 0)
{
*************** namespace std
*** 930,937 ****
_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);
destroy_node(__y);
--_M_node_count;
}
--- 974,981 ----
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(iterator __position)
{
_Link_type __y =
! static_cast<_Link_type>(_Rb_tree_rebalance_for_erase(__position._M_node,
! this->_M_header));
destroy_node(__y);
--_M_node_count;
}
*************** namespace std
*** 951,957 ****
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)
{
// Structural copy. __x and __p must be non-null.
_Link_type __top = _M_clone_node(__x);
--- 995,1001 ----
typename _Compare, typename _Alloc>
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)
{
// Structural copy. __x and __p must be non-null.
_Link_type __top = _M_clone_node(__x);
*************** namespace std
*** 1025,1032 ****
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.
while (__x != 0)
if (!_M_key_compare(_S_key(__x), __k))
--- 1069,1076 ----
typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k)
{
! _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))
*************** namespace std
*** 1045,1052 ****
_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.
while (__x != 0)
{
--- 1089,1096 ----
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
find(const _Key& __k) const
{
! _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)
{
*************** namespace std
*** 1077,1084 ****
_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.
while (__x != 0)
if (!_M_key_compare(_S_key(__x), __k))
--- 1121,1128 ----
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
lower_bound(const _Key& __k)
{
! _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))
*************** namespace std
*** 1095,1102 ****
_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.
while (__x != 0)
if (!_M_key_compare(_S_key(__x), __k))
--- 1139,1146 ----
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
lower_bound(const _Key& __k) const
{
! _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))
*************** namespace std
*** 1113,1120 ****
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
upper_bound(const _Key& __k)
{
_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)))
--- 1157,1164 ----
_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.
while (__x != 0)
if (_M_key_compare(__k, _S_key(__x)))
*************** namespace std
*** 1131,1138 ****
_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.
while (__x != 0)
if (_M_key_compare(__k, _S_key(__x)))
--- 1175,1182 ----
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
upper_bound(const _Key& __k) const
{
! _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)))
*************** namespace std
*** 1164,1186 ****
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;
! }
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
--- 1208,1216 ----
upper_bound(__k));
}
! unsigned int
! _Rb_tree_black_count(const _Rb_tree_node_base* __node,
! const _Rb_tree_node_base* __root);
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
*************** namespace std
*** 1192,1203 ****
this->_M_header._M_left == &this->_M_header &&
this->_M_header._M_right == &this->_M_header;
! int __len = __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);
if (__x->_M_color == _S_red)
if ((__L && __L->_M_color == _S_red)
--- 1222,1233 ----
this->_M_header._M_left == &this->_M_header &&
this->_M_header._M_right == &this->_M_header;
! unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
for (const_iterator __it = begin(); __it != end(); ++__it)
{
! _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)
*************** namespace std
*** 1209,1215 ****
if (__R && _M_key_compare(_S_key(__R), _S_key(__x)))
return false;
! if (!__L && !__R && __black_count(__x, _M_root()) != __len)
return false;
}
--- 1239,1245 ----
if (__R && _M_key_compare(_S_key(__R), _S_key(__x)))
return false;
! if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
return false;
}
Index: src/stl_tree.cc
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/src/stl_tree.cc,v
retrieving revision 1.1
diff -c -3 -p -r1.1 stl_tree.cc
*** src/stl_tree.cc 9 Jul 2003 20:58:32 -0000 1.1
--- src/stl_tree.cc 27 Jul 2003 12:36:04 -0000
***************
*** 59,109 ****
namespace std
{
! void
! _Rb_tree_base_iterator::_M_increment()
{
! if (_M_node->_M_right != 0)
{
! _M_node = _M_node->_M_right;
! while (_M_node->_M_left != 0)
! _M_node = _M_node->_M_left;
}
else
{
! _Base_ptr __y = _M_node->_M_parent;
! while (_M_node == __y->_M_right)
{
! _M_node = __y;
__y = __y->_M_parent;
}
! if (_M_node->_M_right != __y)
! _M_node = __y;
}
}
! void
! _Rb_tree_base_iterator::_M_decrement()
{
! 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)
{
! _Base_ptr __y = _M_node->_M_left;
while (__y->_M_right != 0)
__y = __y->_M_right;
! _M_node = __y;
}
else
{
! _Base_ptr __y = _M_node->_M_parent;
! while (_M_node == __y->_M_left)
{
! _M_node = __y;
__y = __y->_M_parent;
}
! _M_node = __y;
}
}
void
--- 59,111 ----
namespace std
{
! _Rb_tree_node_base*
! _Rb_tree_increment(_Rb_tree_node_base* __x)
{
! if (__x->_M_right != 0)
{
! __x = __x->_M_right;
! while (__x->_M_left != 0)
! __x = __x->_M_left;
}
else
{
! _Rb_tree_node_base* __y = __x->_M_parent;
! while (__x == __y->_M_right)
{
! __x = __y;
__y = __y->_M_parent;
}
! if (__x->_M_right != __y)
! __x = __y;
}
+ return __x;
}
! _Rb_tree_node_base*
! _Rb_tree_decrement(_Rb_tree_node_base* __x)
{
! if (__x->_M_color == _S_red
! && __x->_M_parent->_M_parent == __x)
! __x = __x->_M_right;
! else if (__x->_M_left != 0)
{
! _Rb_tree_node_base* __y = __x->_M_left;
while (__y->_M_right != 0)
__y = __y->_M_right;
! __x = __y;
}
else
{
! _Rb_tree_node_base* __y = __x->_M_parent;
! while (__x == __y->_M_left)
{
! __x = __y;
__y = __y->_M_parent;
}
! __x = __y;
}
+ return __x;
}
void
*************** namespace std
*** 361,365 ****
--- 363,386 ----
if (__x) __x->_M_color = _S_black;
}
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