From 7f6dd1ca73bc6675a1d5c2ce919c105138579a89 Mon Sep 17 00:00:00 2001 From: Gawain Bolton Date: Fri, 4 Jul 2003 22:37:01 +0200 Subject: [PATCH] stl_tree.h: Performance and memory usage improvements. 2003-07-04 Gawain Bolton * include/bits/stl_tree.h: Performance and memory usage improvements. From-SVN: r68936 --- libstdc++-v3/ChangeLog | 5 ++ libstdc++-v3/include/bits/stl_tree.h | 165 +++++++++++++++++++++-------------- 2 files changed, 104 insertions(+), 66 deletions(-) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 469692d..75b511d 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,8 @@ +2003-07-04 Gawain Bolton + + * include/bits/stl_tree.h: Performance and memory usage + improvements. + 2003-07-04 H.J. Lu * Makefile.am: Replace PWD with PWD_COMMAND. diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h index 95482f2..33c8ebd 100644 --- a/libstdc++-v3/include/bits/stl_tree.h +++ b/libstdc++-v3/include/bits/stl_tree.h @@ -192,7 +192,7 @@ namespace std typedef _Rb_tree_node<_Val>* _Link_type; _Rb_tree_iterator() {} - _Rb_tree_iterator(_Link_type __x) { _M_node = __x; } + _Rb_tree_iterator(_Rb_tree_node_base* __x) { _M_node = __x; } _Rb_tree_iterator(const iterator& __it) { _M_node = __it._M_node; } reference @@ -528,13 +528,13 @@ namespace std get_allocator() const { return _M_node_allocator; } _Rb_tree_alloc_base(const allocator_type& __a) - : _M_node_allocator(__a), _M_header(0) {} + : _M_node_allocator(__a) {} protected: typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::allocator_type _M_node_allocator; - _Rb_tree_node<_Tp>* _M_header; + _Rb_tree_node_base _M_header; _Rb_tree_node<_Tp>* _M_get_node() { return _M_node_allocator.allocate(1); } @@ -552,10 +552,10 @@ namespace std typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type; allocator_type get_allocator() const { return allocator_type(); } - _Rb_tree_alloc_base(const allocator_type&) : _M_header(0) {} + _Rb_tree_alloc_base(const allocator_type&) {} protected: - _Rb_tree_node<_Tp>* _M_header; + _Rb_tree_node_base _M_header; typedef typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::_Alloc_type _Alloc_type; @@ -576,8 +576,7 @@ namespace std typedef typename _Base::allocator_type allocator_type; _Rb_tree_base(const allocator_type& __a) - : _Base(__a) { this->_M_header = _M_get_node(); } - ~_Rb_tree_base() { _M_put_node(this->_M_header); } + : _Base(__a) {} }; @@ -645,14 +644,17 @@ namespace std _Compare _M_key_compare; _Link_type& - _M_root() const { return (_Link_type&) this->_M_header->_M_parent; } + _M_root() const { return (_Link_type&) this->_M_header._M_parent; } _Link_type& - _M_leftmost() const { return (_Link_type&) this->_M_header->_M_left; } + _M_leftmost() const { return (_Link_type&) this->_M_header._M_left; } _Link_type& - _M_rightmost() const { return (_Link_type&) this->_M_header->_M_right; } + _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); } @@ -668,9 +670,6 @@ namespace std static const _Key& _S_key(_Link_type __x) { return _KeyOfValue()(_S_value(__x)); } - static _Rb_tree_color& - _S_color(_Link_type __x) { return __x->_M_color; } - static _Link_type& _S_left(_Base_ptr __x) { return (_Link_type&)(__x->_M_left); } @@ -687,7 +686,7 @@ namespace std _S_key(_Base_ptr __x) { return _KeyOfValue()(_S_value(_Link_type(__x)));} static _Rb_tree_color& - _S_color(_Base_ptr __x) { return (_Link_type(__x)->_M_color); } + _S_color(_Base_ptr __x) { return __x->_M_color; } static _Link_type _S_minimum(_Link_type __x) @@ -737,8 +736,8 @@ namespace std _M_empty_initialize(); else { - _S_color(this->_M_header) = _S_red; - _M_root() = _M_copy(__x._M_root(), this->_M_header); + _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()); } @@ -753,11 +752,11 @@ namespace std private: void _M_empty_initialize() { - _S_color(this->_M_header) = _S_red; // used to distinguish header from - // __root, in iterator.operator++ + // Used to distinguish header from __root, in iterator.operator++. + _S_color(&this->_M_header) = _S_red; _M_root() = 0; - _M_leftmost() = this->_M_header; - _M_rightmost() = this->_M_header; + _M_leftmost() = _M_end(); + _M_rightmost() = _M_end(); } public: @@ -772,10 +771,10 @@ namespace std begin() const { return _M_leftmost(); } iterator - end() { return this->_M_header; } + end() { return &this->_M_header; } - const_iterator - end() const { return this->_M_header; } + const_iterator + end() const { return const_cast<_Base_ptr>(&this->_M_header); } reverse_iterator rbegin() { return reverse_iterator(end()); } @@ -799,12 +798,7 @@ namespace std max_size() const { return size_type(-1); } void - swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t) - { - std::swap(this->_M_header, __t._M_header); - std::swap(_M_node_count, __t._M_node_count); - std::swap(_M_key_compare, __t._M_key_compare); - } + swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t); // Insert/erase. pair @@ -845,9 +839,9 @@ namespace std if (_M_node_count != 0) { _M_erase(_M_root()); - _M_leftmost() = this->_M_header; + _M_leftmost() = _M_end(); _M_root() = 0; - _M_rightmost() = this->_M_header; + _M_rightmost() = _M_end(); _M_node_count = 0; } } @@ -955,12 +949,12 @@ namespace std if (__x._M_root() == 0) { _M_root() = 0; - _M_leftmost() = this->_M_header; - _M_rightmost() = this->_M_header; + _M_leftmost() = _M_end(); + _M_rightmost() = _M_end(); } else { - _M_root() = _M_copy(__x._M_root(), this->_M_header); + _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; @@ -979,13 +973,13 @@ namespace std _Link_type __y = (_Link_type) __y_; _Link_type __z; - if (__y == this->_M_header || __x != 0 || + 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) + // when __y == &_M_header + if (__y == &this->_M_header) { _M_root() = __z; _M_rightmost() = __z; @@ -1004,7 +998,7 @@ namespace std _S_parent(__z) = __y; _S_left(__z) = 0; _S_right(__z) = 0; - _Rb_tree_rebalance(__z, this->_M_header->_M_parent); + _Rb_tree_rebalance(__z, this->_M_header._M_parent); ++_M_node_count; return iterator(__z); } @@ -1015,7 +1009,7 @@ namespace std _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: insert_equal(const _Val& __v) { - _Link_type __y = this->_M_header; + _Link_type __y = _M_end(); _Link_type __x = _M_root(); while (__x != 0) { @@ -1028,12 +1022,57 @@ namespace std template + void + _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: + swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t) + { + if (_M_root() == 0) + { + if (__t._M_root() != 0) + { + _M_root() = __t._M_root(); + _M_leftmost() = __t._M_leftmost(); + _M_rightmost() = __t._M_rightmost(); + _M_root()->_M_parent = _M_end(); + + __t._M_root() = 0; + __t._M_leftmost() = __t._M_end(); + __t._M_rightmost() = __t._M_end(); + } + } + else if (__t._M_root() == 0) + { + __t._M_root() = _M_root(); + __t._M_leftmost() = _M_leftmost(); + __t._M_rightmost() = _M_rightmost(); + __t._M_root()->_M_parent = __t._M_end(); + + _M_root() = 0; + _M_leftmost() = _M_end(); + _M_rightmost() = _M_end(); + } + else + { + std::swap(_M_root(),__t._M_root()); + std::swap(_M_leftmost(),__t._M_leftmost()); + std::swap(_M_rightmost(),__t._M_rightmost()); + + _M_root()->_M_parent = _M_end(); + __t._M_root()->_M_parent = __t._M_end(); + } + // No need to swap header's color as it does not change. + std::swap(this->_M_node_count, __t._M_node_count); + std::swap(this->_M_key_compare, __t._M_key_compare); + } + + template pair::iterator, bool> _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: insert_unique(const _Val& __v) { - _Link_type __y = this->_M_header; + _Link_type __y = _M_end(); _Link_type __x = _M_root(); bool __comp = true; while (__x != 0) @@ -1060,7 +1099,7 @@ namespace std _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: insert_unique(iterator __position, const _Val& __v) { - if (__position._M_node == this->_M_header->_M_left) + if (__position._M_node == this->_M_header._M_left) { // begin() if (size() > 0 && @@ -1070,7 +1109,7 @@ namespace std else return insert_unique(__v).first; } - else if (__position._M_node == this->_M_header) + else if (__position._M_node == &this->_M_header) { // end() if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v))) @@ -1102,7 +1141,7 @@ namespace std _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: insert_equal(iterator __position, const _Val& __v) { - if (__position._M_node == this->_M_header->_M_left) + if (__position._M_node == this->_M_header._M_left) { // begin() if (size() > 0 && @@ -1112,7 +1151,7 @@ namespace std else return insert_equal(__v); } - else if (__position._M_node == this->_M_header) + else if (__position._M_node == &this->_M_header) { // end() if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost()))) @@ -1168,9 +1207,9 @@ namespace std { _Link_type __y = (_Link_type) _Rb_tree_rebalance_for_erase(__position._M_node, - this->_M_header->_M_parent, - this->_M_header->_M_left, - this->_M_header->_M_right); + this->_M_header._M_parent, + this->_M_header._M_left, + this->_M_header._M_right); destroy_node(__y); --_M_node_count; } @@ -1264,9 +1303,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 - = this->_M_header; // Last node which is not less than __k. - _Link_type __x = _M_root(); // Current node. + _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)) @@ -1285,8 +1323,7 @@ namespace std _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: find(const _Key& __k) const { - _Link_type __y - = this->_M_header; // Last node which is not less than __k. + _Link_type __y = _M_end(); // Last node which is not less than __k. _Link_type __x = _M_root(); // Current node. while (__x != 0) @@ -1318,9 +1355,8 @@ namespace std _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: lower_bound(const _Key& __k) { - _Link_type __y - = this->_M_header; /* Last node which is not less than __k. */ - _Link_type __x = _M_root(); /* Current node. */ + _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)) @@ -1337,9 +1373,8 @@ namespace std _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: lower_bound(const _Key& __k) const { - _Link_type __y - = this->_M_header; /* Last node which is not less than __k. */ - _Link_type __x = _M_root(); /* Current node. */ + _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)) @@ -1356,9 +1391,8 @@ namespace std _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: upper_bound(const _Key& __k) { - _Link_type __y - = this->_M_header; /* Last node which is greater than __k. */ - _Link_type __x = _M_root(); /* 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))) @@ -1375,9 +1409,8 @@ namespace std _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>:: upper_bound(const _Key& __k) const { - _Link_type __y - = this->_M_header; /* Last node which is greater than __k. */ - _Link_type __x = _M_root(); /* 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))) @@ -1434,8 +1467,8 @@ namespace std { 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; + 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) -- 2.7.4