This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Update: [Patch]: Separate classes for constant iterators and miscellaneousoptimizations
- From: Gawain Bolton <gbolton at free dot fr>
- To: libstdc++ at gcc dot gnu dot org
- Date: Thu, 07 Aug 2003 23:43:28 +0200
- Subject: Update: [Patch]: Separate classes for constant iterators and miscellaneousoptimizations
- Reply-to: gp dot bolton at computer dot org
This is an update for the patch posted previously here:
http://gcc.gnu.org/ml/libstdc++/2003-08/msg00018.html
It fixes a bug that was present in the previous patch in the
_Rb_tree::_M_insert() function.
This patch also moves even move code out of the stl_tree.h header file
into the stl_tree.cc implementation file than the previous patch.
This results in a reduction in code size for applications inserting
elements in the std::{set|map|multiset|multimap} containers.
With respect to DRs about const_iterators and iterators as hinted at here:
http://gcc.gnu.org/ml/libstdc++/2003-08/msg00019.html
I found the following two items:
http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-defects.html#179
http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-defects.html#322
Concerning Item 179 "Comparison of const_iterators to iterators doesn't
work", I have added the required global comparison operators so that
comparisons between constant and non-constant iterators are possible.
This is what I understand from the proposed resolution of this DR -
although the notes are confusing.
As for Item 322 " iterator and const_iterator should have the same value
type", the constant and non-constant iterators in this patch have the
same value_type so I don't see any issue here.
Otherwise, the patch is as previously posted and explained.
The new performance numbers using Bjarne Stroustrup's Standard Container
Benchmark are very similar to the previous patch - perhaps slightly
better even.
For completeness, here is the new set of numbers obtained with the patch:
size array vector(1) vector(2) deque list set multiset
10 3.15 3.16 3.31 5.64 10.42 5.73 9.84
100 1.85 1.87 1.95 3.48 5.13 3.90 6.07
1000 1.79 1.78 1.97 3.21 4.68 3.41 5.41
10000 1.86 1.85 2.04 3.20 5.44 3.96 6.24
100000 2.05 2.04 2.17 3.23 7.53 5.83 8.40
(1) with pointers
(2) with iterators
Cheers,
Gawain
Index: config/linker-map.gnu
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/config/linker-map.gnu,v
retrieving revision 1.46
diff -c -3 -p -r1.46 linker-map.gnu
*** config/linker-map.gnu 30 Jul 2003 15:01:58 -0000 1.46
--- config/linker-map.gnu 7 Aug 2003 21:34:12 -0000
*************** GLIBCXX_3.4 {
*** 76,88 ****
_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_;
# virtual table
_ZTVNSt8ios_base7failureE;
--- 76,90 ----
_ZSt9has_facet*;
# _Rb_tree
+ _ZSt18_Rb_tree_decrementPKSt18_Rb_tree_node_base;
_ZSt18_Rb_tree_decrementPSt18_Rb_tree_node_base;
+ _ZSt18_Rb_tree_incrementPKSt18_Rb_tree_node_base;
_ZSt18_Rb_tree_incrementPSt18_Rb_tree_node_base;
_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_;
+ _ZSt29_Rb_tree_insert_and_rebalancebPSt18_Rb_tree_node_baseS0_RS_;
# virtual table
_ZTVNSt8ios_base7failureE;
Index: include/bits/list.tcc
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/include/bits/list.tcc,v
retrieving revision 1.7
diff -c -3 -p -r1.7 list.tcc
*** include/bits/list.tcc 6 Jul 2003 00:58:52 -0000 1.7
--- include/bits/list.tcc 7 Aug 2003 21:34:12 -0000
*************** namespace std
*** 77,84 ****
std::_Destroy(&__tmp->_M_data);
_M_put_node(__tmp);
}
- this->_M_node._M_next = &this->_M_node;
- this->_M_node._M_prev = &this->_M_node;
}
template<typename _Tp, typename _Alloc>
--- 77,82 ----
Index: include/bits/stl_list.h
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/include/bits/stl_list.h,v
retrieving revision 1.30
diff -c -3 -p -r1.30 stl_list.h
*** include/bits/stl_list.h 15 Jul 2003 06:15:57 -0000 1.30
--- include/bits/stl_list.h 7 Aug 2003 21:34:13 -0000
*************** namespace std
*** 86,167 ****
/**
! * @if maint
! * @brief Common part of a list::iterator.
*
! * A simple type to walk a doubly-linked list. All operations here should
! * be self-explanatory after taking any decent introductory data structures
! * course.
* @endif
*/
! struct _List_iterator_base
{
! typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef bidirectional_iterator_tag iterator_category;
! /// The only member points to the %list element.
! _List_node_base* _M_node;
!
! _List_iterator_base(_List_node_base* __x)
: _M_node(__x)
{ }
! _List_iterator_base()
! { }
! /// Walk the %list forward.
! void
! _M_incr()
! { _M_node = _M_node->_M_next; }
! /// Walk the %list backward.
! void
! _M_decr()
! { _M_node = _M_node->_M_prev; }
bool
! operator==(const _List_iterator_base& __x) const
{ return _M_node == __x._M_node; }
!
bool
! operator!=(const _List_iterator_base& __x) const
{ return _M_node != __x._M_node; }
};
/**
! * @brief A list::iterator.
! *
! * In addition to being used externally, a list holds one of these
! * internally, pointing to the sequence of data.
*
* @if maint
* All the functions are op overloads.
* @endif
*/
! template<typename _Tp, typename _Ref, typename _Ptr>
! struct _List_iterator : public _List_iterator_base
{
! typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator;
! typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
! typedef _List_iterator<_Tp,_Ref,_Ptr> _Self;
!
! typedef _Tp value_type;
! typedef _Ptr pointer;
! typedef _Ref reference;
! typedef _List_node<_Tp> _Node;
! _List_iterator(_Node* __x)
! : _List_iterator_base(__x)
! { }
! _List_iterator()
{ }
!
! _List_iterator(const iterator& __x)
! : _List_iterator_base(__x._M_node)
{ }
!
reference
operator*() const
{ return static_cast<_Node*>(_M_node)->_M_data; }
--- 86,199 ----
/**
! * @brief A list::iterator.
*
! * @if maint
! * All the functions are op overloads.
* @endif
*/
! template<typename _Tp>
! struct _List_iterator
{
! typedef _List_iterator<_Tp> _Self;
! typedef _List_node<_Tp> _Node;
!
typedef ptrdiff_t difference_type;
typedef bidirectional_iterator_tag iterator_category;
+ typedef _Tp value_type;
+ typedef _Tp* pointer;
+ typedef _Tp& reference;
! _List_iterator()
! { }
!
! _List_iterator(_List_node_base* __x)
: _M_node(__x)
{ }
+
+ reference
+ operator*() const
+ { return static_cast<_Node*>(_M_node)->_M_data; }
+ // Must downcast from List_node_base to _List_node to get to _M_data.
! pointer
! operator->() const
! { return &static_cast<_Node*>(_M_node)->_M_data; }
! _Self&
! operator++()
! {
! _M_node = _M_node->_M_next;
! return *this;
! }
! _Self
! operator++(int)
! {
! _Self __tmp = *this;
! _M_node = _M_node->_M_next;
! return __tmp;
! }
!
! _Self&
! operator--()
! {
! _M_node = _M_node->_M_prev;
! return *this;
! }
+ _Self
+ operator--(int)
+ {
+ _Self __tmp = *this;
+ _M_node = _M_node->_M_prev;
+ return __tmp;
+ }
+
bool
! operator==(const _Self& __x) const
{ return _M_node == __x._M_node; }
!
bool
! operator!=(const _Self& __x) const
{ return _M_node != __x._M_node; }
+
+ // The only member points to the %list element.
+ _List_node_base* _M_node;
};
+
/**
! * @brief A list::const_iterator.
*
* @if maint
* All the functions are op overloads.
* @endif
*/
! template<typename _Tp>
! struct _List_const_iterator
{
! typedef _List_const_iterator<_Tp> _Self;
! typedef const _List_node<_Tp> _Node;
! typedef _List_iterator<_Tp> iterator;
! typedef ptrdiff_t difference_type;
! typedef bidirectional_iterator_tag iterator_category;
! typedef _Tp value_type;
! typedef const _Tp* pointer;
! typedef const _Tp& reference;
! _List_const_iterator()
{ }
!
! _List_const_iterator(const _List_node_base* __x)
! : _M_node(__x)
{ }
!
! _List_const_iterator(const iterator& __x)
! : _M_node(__x._M_node)
! { }
!
reference
operator*() const
{ return static_cast<_Node*>(_M_node)->_M_data; }
*************** namespace std
*** 169,180 ****
pointer
operator->() const
! { return &(operator*()); }
_Self&
operator++()
{
! this->_M_incr();
return *this;
}
--- 201,212 ----
pointer
operator->() const
! { return &static_cast<_Node*>(_M_node)->_M_data; }
_Self&
operator++()
{
! _M_node = _M_node->_M_next;
return *this;
}
*************** namespace std
*** 182,195 ****
operator++(int)
{
_Self __tmp = *this;
! this->_M_incr();
return __tmp;
}
_Self&
operator--()
{
! this->_M_decr();
return *this;
}
--- 214,227 ----
operator++(int)
{
_Self __tmp = *this;
! _M_node = _M_node->_M_next;
return __tmp;
}
_Self&
operator--()
{
! _M_node = _M_node->_M_prev;
return *this;
}
*************** namespace std
*** 197,208 ****
operator--(int)
{
_Self __tmp = *this;
! this->_M_decr();
return __tmp;
}
};
!
!
/// @if maint Primary default version. @endif
/**
* @if maint
--- 229,262 ----
operator--(int)
{
_Self __tmp = *this;
! _M_node = _M_node->_M_prev;
return __tmp;
}
+
+ bool
+ operator==(const _Self& __x) const
+ { return _M_node == __x._M_node; }
+
+ bool
+ operator!=(const _Self& __x) const
+ { return _M_node != __x._M_node; }
+
+ // The only member points to the %list element.
+ const _List_node_base* _M_node;
};
!
! template<typename _Val>
! inline bool
! operator==(const _List_iterator<_Val>& __x,
! const _List_const_iterator<_Val>& __y)
! { return __x._M_node == __y._M_node; }
!
! template<typename _Val>
! inline bool
! operator!=(const _List_iterator<_Val>& __x,
! const _List_const_iterator<_Val>& __y)
! { return __x._M_node != __y._M_node; }
!
/// @if maint Primary default version. @endif
/**
* @if maint
*************** namespace std
*** 301,308 ****
_List_base(const allocator_type& __a)
: _Base(__a)
{
! this->_M_node._M_next = &this->_M_node;
! this->_M_node._M_prev = &this->_M_node;
}
// This is what actually destroys the list.
--- 355,361 ----
_List_base(const allocator_type& __a)
: _Base(__a)
{
! __init();
}
// This is what actually destroys the list.
*************** namespace std
*** 313,318 ****
--- 366,378 ----
void
__clear();
+
+ void
+ __init()
+ {
+ this->_M_node._M_next = &this->_M_node;
+ this->_M_node._M_prev = &this->_M_node;
+ }
};
*************** namespace std
*** 372,379 ****
typedef _Tp value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
! typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator;
! typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef value_type& reference;
--- 432,439 ----
typedef _Tp value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
! typedef _List_iterator<_Tp> iterator;
! typedef _List_const_iterator<_Tp> const_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef value_type& reference;
*************** namespace std
*** 565,592 ****
* %list. Iteration is done in ordinary element order.
*/
iterator
! begin() { return static_cast<_Node*>(this->_M_node._M_next); }
/**
* Returns a read-only (constant) iterator that points to the first element
* in the %list. Iteration is done in ordinary element order.
*/
const_iterator
! begin() const { return static_cast<_Node*>(this->_M_node._M_next); }
/**
* Returns a read/write iterator that points one past the last element in
* the %list. Iteration is done in ordinary element order.
*/
iterator
! end() { return static_cast<_Node*>(&this->_M_node); }
/**
* Returns a read-only (constant) iterator that points one past the last
* element in the %list. Iteration is done in ordinary element order.
*/
const_iterator
! end() const { return const_cast<_Node *>(static_cast<const _Node*>(&this->_M_node)); }
/**
* Returns a read/write reverse iterator that points to the last element in
--- 625,652 ----
* %list. Iteration is done in ordinary element order.
*/
iterator
! begin() { return this->_M_node._M_next; }
/**
* Returns a read-only (constant) iterator that points to the first element
* in the %list. Iteration is done in ordinary element order.
*/
const_iterator
! begin() const { return this->_M_node._M_next; }
/**
* Returns a read/write iterator that points one past the last element in
* the %list. Iteration is done in ordinary element order.
*/
iterator
! end() { return &this->_M_node; }
/**
* Returns a read-only (constant) iterator that points one past the last
* element in the %list. Iteration is done in ordinary element order.
*/
const_iterator
! end() const { return &this->_M_node; }
/**
* Returns a read/write reverse iterator that points to the last element in
*************** namespace std
*** 861,867 ****
* the user's responsibilty.
*/
void
! clear() { _Base::__clear(); }
// [23.2.2.4] list operations
/**
--- 921,931 ----
* the user's responsibilty.
*/
void
! clear()
! {
! _Base::__clear();
! _Base::__init();
! }
// [23.2.2.4] list operations
/**
Index: include/bits/stl_tree.h
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/include/bits/stl_tree.h,v
retrieving revision 1.28
diff -c -3 -p -r1.28 stl_tree.h
*** include/bits/stl_tree.h 30 Jul 2003 15:01:58 -0000 1.28
--- include/bits/stl_tree.h 7 Aug 2003 21:34:13 -0000
*************** namespace std
*** 141,176 ****
_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;
! typedef _Ptr pointer;
! 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; }
--- 141,174 ----
_Rb_tree_node_base*
_Rb_tree_increment(_Rb_tree_node_base* __x);
+ const _Rb_tree_node_base*
+ _Rb_tree_increment(const _Rb_tree_node_base* __x);
+
_Rb_tree_node_base*
_Rb_tree_decrement(_Rb_tree_node_base* __x);
! const _Rb_tree_node_base*
! _Rb_tree_decrement(const _Rb_tree_node_base* __x);
!
! template<typename _Tp>
struct _Rb_tree_iterator
{
! typedef _Tp value_type;
! typedef _Tp& reference;
! typedef _Tp* pointer;
!
typedef bidirectional_iterator_tag iterator_category;
! typedef ptrdiff_t difference_type;
!
! typedef _Rb_tree_iterator<_Tp> _Self;
! typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
! typedef _Rb_tree_node<_Tp>* _Link_type;
_Rb_tree_iterator() {}
_Rb_tree_iterator(_Link_type __x)
: _M_node(__x) {}
reference
operator*() const
{ return static_cast<_Link_type>(_M_node)->_M_value_field; }
*************** namespace std
*** 209,261 ****
return __tmp;
}
_Base_ptr _M_node;
};
! template<typename _Val, typename _Ref, typename _Ptr>
! inline bool
! operator==(const _Rb_tree_iterator<_Val, _Ref, _Ptr>& __x,
! const _Rb_tree_iterator<_Val, _Ref, _Ptr>& __y)
! { return __x._M_node == __y._M_node; }
! template<typename _Val>
! inline bool
! operator==(const _Rb_tree_iterator<_Val, const _Val&, const _Val*>& __x,
! const _Rb_tree_iterator<_Val, _Val&, _Val*>& __y)
! { return __x._M_node == __y._M_node; }
! template<typename _Val>
! inline bool
! operator==(const _Rb_tree_iterator<_Val, _Val&, _Val*>& __x,
! const _Rb_tree_iterator<_Val, const _Val&, const _Val*>& __y)
! { return __x._M_node == __y._M_node; }
! template<typename _Val, typename _Ref, typename _Ptr>
! inline bool
! operator!=(const _Rb_tree_iterator<_Val, _Ref, _Ptr>& __x,
! const _Rb_tree_iterator<_Val, _Ref, _Ptr>& __y)
! { return __x._M_node != __y._M_node; }
template<typename _Val>
inline bool
! operator!=(const _Rb_tree_iterator<_Val, const _Val&, const _Val*>& __x,
! const _Rb_tree_iterator<_Val, _Val&, _Val*>& __y)
! { return __x._M_node != __y._M_node; }
template<typename _Val>
inline bool
! operator!=(const _Rb_tree_iterator<_Val, _Val&, _Val*>& __x,
! const _Rb_tree_iterator<_Val, const _Val&, const _Val*>& __y)
{ return __x._M_node != __y._M_node; }
void
! _Rb_tree_rotate_left(_Rb_tree_node_base* const __x, _Rb_tree_node_base*& __root);
void
! _Rb_tree_rotate_right(_Rb_tree_node_base* const __x, _Rb_tree_node_base*& __root);
void
! _Rb_tree_rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root);
_Rb_tree_node_base*
_Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
--- 207,321 ----
return __tmp;
}
+ bool
+ operator==(const _Self& __x) const
+ { return _M_node == __x._M_node; }
+
+ bool
+ operator!=(const _Self& __x) const
+ { return _M_node != __x._M_node; }
+
_Base_ptr _M_node;
};
! template<typename _Tp>
! struct _Rb_tree_const_iterator
! {
! typedef _Tp value_type;
! typedef const _Tp& reference;
! typedef const _Tp* pointer;
! typedef _Rb_tree_iterator<_Tp> iterator;
! typedef bidirectional_iterator_tag iterator_category;
! typedef ptrdiff_t difference_type;
! typedef _Rb_tree_const_iterator<_Tp> _Self;
! typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
! typedef const _Rb_tree_node<_Tp>* _Link_type;
!
! _Rb_tree_const_iterator() {}
!
! _Rb_tree_const_iterator(_Link_type __x)
! : _M_node(__x) {}
!
! _Rb_tree_const_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;
! }
!
! _Self
! 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;
! }
!
! bool
! operator==(const _Self& __x) const
! { return _M_node == __x._M_node; }
!
! bool
! operator!=(const _Self& __x) const
! { return _M_node != __x._M_node; }
!
! _Base_ptr _M_node;
! };
template<typename _Val>
inline bool
! operator==(const _Rb_tree_iterator<_Val>& __x,
! const _Rb_tree_const_iterator<_Val>& __y)
! { return __x._M_node == __y._M_node; }
template<typename _Val>
inline bool
! operator!=(const _Rb_tree_iterator<_Val>& __x,
! const _Rb_tree_const_iterator<_Val>& __y)
{ return __x._M_node != __y._M_node; }
void
! _Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
! _Rb_tree_node_base*& __root);
void
! _Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
! _Rb_tree_node_base*& __root);
void
! _Rb_tree_insert_and_rebalance(const bool __insert_left,
! _Rb_tree_node_base* __x,
! _Rb_tree_node_base* __p,
! _Rb_tree_node_base& __header);
_Rb_tree_node_base*
_Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
*************** namespace std
*** 465,476 ****
{ return _Rb_tree_node_base::_S_maximum(__x); }
public:
! typedef _Rb_tree_iterator<value_type, reference, pointer> iterator;
! typedef _Rb_tree_iterator<value_type, const_reference, const_pointer>
! const_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
- typedef std::reverse_iterator<iterator> reverse_iterator;
private:
iterator
--- 525,535 ----
{ return _Rb_tree_node_base::_S_maximum(__x); }
public:
! typedef _Rb_tree_iterator<value_type> iterator;
! typedef _Rb_tree_const_iterator<value_type> const_iterator;
+ typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
private:
iterator
*************** namespace std
*** 512,518 ****
_M_node_count = __x._M_node_count;
}
! ~_Rb_tree() { clear(); }
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>&
operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x);
--- 571,577 ----
_M_node_count = __x._M_node_count;
}
! ~_Rb_tree() { _M_erase(_M_begin()); }
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>&
operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x);
*************** namespace std
*** 601,618 ****
void
erase(const key_type* __first, const key_type* __last);
! void
! clear()
{
! if (_M_node_count != 0)
! {
! _M_erase(_M_begin());
! _M_leftmost() = _M_end();
! _M_root() = 0;
! _M_rightmost() = _M_end();
! _M_node_count = 0;
! }
! }
// Set operations.
iterator
--- 660,674 ----
void
erase(const key_type* __first, const key_type* __last);
! void
! clear()
{
! _M_erase(_M_begin());
! _M_leftmost() = _M_end();
! _M_root() = 0;
! _M_rightmost() = _M_end();
! _M_node_count = 0;
! }
// Set operations.
iterator
*************** namespace std
*** 712,726 ****
{
// Note that _Key may be a constant type.
clear();
- _M_node_count = 0;
_M_key_compare = __x._M_key_compare;
! if (__x._M_root() == 0)
! {
! _M_root() = 0;
! _M_leftmost() = _M_end();
! _M_rightmost() = _M_end();
! }
! else
{
_M_root() = _M_copy(__x._M_begin(), _M_end());
_M_leftmost() = _S_minimum(_M_root());
--- 768,775 ----
{
// Note that _Key may be a constant type.
clear();
_M_key_compare = __x._M_key_compare;
! if (__x._M_root() != 0)
{
_M_root() = _M_copy(__x._M_begin(), _M_end());
_M_leftmost() = _S_minimum(_M_root());
*************** namespace std
*** 735,772 ****
typename _Compare, typename _Alloc>
typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
_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)
! {
! _M_root() = __z;
! _M_rightmost() = __z;
! }
! else if (__y == _M_leftmost())
! _M_leftmost() = __z; // maintain _M_leftmost() pointing to min node
! }
! 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);
}
--- 784,798 ----
typename _Compare, typename _Alloc>
typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
! _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
{
! _Link_type __z = _M_create_node(__v);
! bool __insert_left;
!
! __insert_left = __x != 0 || __p == _M_end() ||
! _M_key_compare(_KeyOfValue()(__v), _S_key(__p));
!
! _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, this->_M_header);
++_M_node_count;
return iterator(__z);
}
*************** namespace std
*** 867,873 ****
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
insert_unique(iterator __position, const _Val& __v)
{
! if (__position._M_node == this->_M_header._M_left)
{
// begin()
if (size() > 0 &&
--- 893,899 ----
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
insert_unique(iterator __position, const _Val& __v)
{
! if (__position._M_node == _M_leftmost())
{
// begin()
if (size() > 0 &&
*************** namespace std
*** 877,883 ****
else
return insert_unique(__v).first;
}
! else if (__position._M_node == &this->_M_header)
{
// end()
if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v)))
--- 903,909 ----
else
return insert_unique(__v).first;
}
! else if (__position._M_node == _M_end())
{
// end()
if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v)))
*************** namespace std
*** 909,915 ****
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
insert_equal(iterator __position, const _Val& __v)
{
! if (__position._M_node == this->_M_header._M_left)
{
// begin()
if (size() > 0 &&
--- 935,941 ----
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
insert_equal(iterator __position, const _Val& __v)
{
! if (__position._M_node == _M_leftmost())
{
// begin()
if (size() > 0 &&
*************** namespace std
*** 919,925 ****
else
return insert_equal(__v);
}
! else if (__position._M_node == &this->_M_header)
{
// end()
if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost())))
--- 945,951 ----
else
return insert_equal(__v);
}
! else if (__position._M_node == _M_end())
{
// end()
if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost())))
*************** namespace std
*** 1219,1226 ****
{
if (_M_node_count == 0 || begin() == end())
return _M_node_count == 0 && begin() == end() &&
! 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)
--- 1245,1252 ----
{
if (_M_node_count == 0 || begin() == end())
return _M_node_count == 0 && begin() == end() &&
! this->_M_header._M_left == _M_end() &&
! this->_M_header._M_right == _M_end();
unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
for (const_iterator __it = begin(); __it != end(); ++__it)
Index: src/stl_tree.cc
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/src/stl_tree.cc,v
retrieving revision 1.2
diff -c -3 -p -r1.2 stl_tree.cc
*** src/stl_tree.cc 30 Jul 2003 15:01:58 -0000 1.2
--- src/stl_tree.cc 7 Aug 2003 21:34:26 -0000
*************** namespace std
*** 82,87 ****
--- 82,93 ----
return __x;
}
+ const _Rb_tree_node_base*
+ _Rb_tree_increment(const _Rb_tree_node_base* __x)
+ {
+ return _Rb_tree_increment(const_cast<_Rb_tree_node_base*>(__x));
+ }
+
_Rb_tree_node_base*
_Rb_tree_decrement(_Rb_tree_node_base* __x)
{
*************** namespace std
*** 108,113 ****
--- 114,125 ----
return __x;
}
+ const _Rb_tree_node_base*
+ _Rb_tree_decrement(const _Rb_tree_node_base* __x)
+ {
+ return _Rb_tree_decrement(const_cast<_Rb_tree_node_base*>(__x));
+ }
+
void
_Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
_Rb_tree_node_base*& __root)
*************** namespace std
*** 151,160 ****
}
void
! _Rb_tree_rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
{
__x->_M_color = _S_red;
while (__x != __root
&& __x->_M_parent->_M_color == _S_red)
{
--- 163,205 ----
}
void
! _Rb_tree_insert_and_rebalance(const bool __insert_left,
! _Rb_tree_node_base* __x,
! _Rb_tree_node_base* __p,
! _Rb_tree_node_base& __header)
{
+ _Rb_tree_node_base *& __root = __header._M_parent;
+
+ // Initialize fields in new node to insert.
+ __x->_M_parent = __p;
+ __x->_M_left = 0;
+ __x->_M_right = 0;
__x->_M_color = _S_red;
+ // Insert.
+ // Make new node child of parent and maintain root, leftmost and
+ // rightmost nodes.
+ // N.B. First node is always inserted left.
+ if (__insert_left)
+ {
+ __p->_M_left = __x; // also makes leftmost = __x when __p == &__header
+
+ if (__p == &__header)
+ {
+ __header._M_parent = __x;
+ __header._M_right = __x;
+ }
+ else if (__p == __header._M_left)
+ __header._M_left = __x; // maintain leftmost pointing to min node
+ }
+ else
+ {
+ __p->_M_right = __x;
+
+ if (__p == __header._M_right)
+ __header._M_right = __x; // maintain rightmost pointing to max node
+ }
+ // Rebalance.
while (__x != __root
&& __x->_M_parent->_M_color == _S_red)
{