1.1 --- a/epoc32/include/stdapis/stlportv5/stl/_tree.c Wed Mar 31 12:27:01 2010 +0100
1.2 +++ b/epoc32/include/stdapis/stlportv5/stl/_tree.c Wed Mar 31 12:33:34 2010 +0100
1.3 @@ -10,13 +10,13 @@
1.4 * Copyright (c) 1997
1.5 * Moscow Center for SPARC Technology
1.6 *
1.7 - * Copyright (c) 1999
1.8 + * Copyright (c) 1999
1.9 * Boris Fomitchev
1.10 *
1.11 * This material is provided "as is", with absolutely no warranty expressed
1.12 * or implied. Any use is at your own risk.
1.13 *
1.14 - * Permission to use or copy this software for any purpose is hereby granted
1.15 + * Permission to use or copy this software for any purpose is hereby granted
1.16 * without fee, provided the above notices are retained on all copies.
1.17 * Permission to modify the code and to distribute modified code is granted,
1.18 * provided the above notices are retained, and a notice that the code was
1.19 @@ -32,34 +32,36 @@
1.20 #define _STLP_TREE_C
1.21
1.22 #ifndef _STLP_INTERNAL_TREE_H
1.23 -# include <stl/_tree.h>
1.24 +# include <stl/_tree.h>
1.25 +#endif
1.26 +
1.27 +#if defined (_STLP_DEBUG)
1.28 +# define _Rb_tree _STLP_NON_DBG_NAME(Rb_tree)
1.29 #endif
1.30
1.31 // fbp: these defines are for outline methods definitions.
1.32 // needed for definitions to be portable. Should not be used in method bodies.
1.33 -# if defined ( _STLP_NESTED_TYPE_PARAM_BUG )
1.34 -# define __iterator__ _Rb_tree_iterator<_Value, _Nonconst_traits<_Value> >
1.35 -# define __size_type__ size_t
1.36 +#if defined (_STLP_NESTED_TYPE_PARAM_BUG)
1.37 +# define __iterator__ _Rb_tree_iterator<_Value, _STLP_HEADER_TYPENAME _Traits::_NonConstTraits>
1.38 +# define __size_type__ size_t
1.39 # define iterator __iterator__
1.40 -# else
1.41 -# define __iterator__ _STLP_TYPENAME_ON_RETURN_TYPE _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc>::iterator
1.42 -# define __size_type__ _STLP_TYPENAME_ON_RETURN_TYPE _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc>::size_type
1.43 -# endif
1.44 -
1.45 -#if defined ( _STLP_DEBUG)
1.46 -# define _Rb_tree __WORKAROUND_DBG_RENAME(Rb_tree)
1.47 +#else
1.48 +# define __iterator__ _STLP_TYPENAME_ON_RETURN_TYPE _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc>::iterator
1.49 +# define __size_type__ _STLP_TYPENAME_ON_RETURN_TYPE _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc>::size_type
1.50 #endif
1.51
1.52 _STLP_BEGIN_NAMESPACE
1.53
1.54 -# if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION)
1.55 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.56 +
1.57 +#if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION)
1.58
1.59 template <class _Dummy> void _STLP_CALL
1.60 -_Rb_global<_Dummy>::_Rotate_left(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
1.61 -{
1.62 +_Rb_global<_Dummy>::_Rotate_left(_Rb_tree_node_base* __x,
1.63 + _Rb_tree_node_base*& __root) {
1.64 _Rb_tree_node_base* __y = __x->_M_right;
1.65 __x->_M_right = __y->_M_left;
1.66 - if (__y->_M_left !=0)
1.67 + if (__y->_M_left != 0)
1.68 __y->_M_left->_M_parent = __x;
1.69 __y->_M_parent = __x->_M_parent;
1.70
1.71 @@ -73,9 +75,9 @@
1.72 __x->_M_parent = __y;
1.73 }
1.74
1.75 -template <class _Dummy> void _STLP_CALL
1.76 -_Rb_global<_Dummy>::_Rotate_right(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
1.77 -{
1.78 +template <class _Dummy> void _STLP_CALL
1.79 +_Rb_global<_Dummy>::_Rotate_right(_Rb_tree_node_base* __x,
1.80 + _Rb_tree_node_base*& __root) {
1.81 _Rb_tree_node_base* __y = __x->_M_left;
1.82 __x->_M_left = __y->_M_right;
1.83 if (__y->_M_right != 0)
1.84 @@ -93,9 +95,8 @@
1.85 }
1.86
1.87 template <class _Dummy> void _STLP_CALL
1.88 -_Rb_global<_Dummy>::_Rebalance(_Rb_tree_node_base* __x,
1.89 - _Rb_tree_node_base*& __root)
1.90 -{
1.91 +_Rb_global<_Dummy>::_Rebalance(_Rb_tree_node_base* __x,
1.92 + _Rb_tree_node_base*& __root) {
1.93 __x->_M_color = _S_rb_tree_red;
1.94 while (__x != __root && __x->_M_parent->_M_color == _S_rb_tree_red) {
1.95 if (__x->_M_parent == __x->_M_parent->_M_parent->_M_left) {
1.96 @@ -140,26 +141,26 @@
1.97
1.98 template <class _Dummy> _Rb_tree_node_base* _STLP_CALL
1.99 _Rb_global<_Dummy>::_Rebalance_for_erase(_Rb_tree_node_base* __z,
1.100 - _Rb_tree_node_base*& __root,
1.101 - _Rb_tree_node_base*& __leftmost,
1.102 - _Rb_tree_node_base*& __rightmost)
1.103 -{
1.104 + _Rb_tree_node_base*& __root,
1.105 + _Rb_tree_node_base*& __leftmost,
1.106 + _Rb_tree_node_base*& __rightmost) {
1.107 _Rb_tree_node_base* __y = __z;
1.108 - _Rb_tree_node_base* __x = 0;
1.109 - _Rb_tree_node_base* __x_parent = 0;
1.110 + _Rb_tree_node_base* __x;
1.111 + _Rb_tree_node_base* __x_parent;
1.112 +
1.113 if (__y->_M_left == 0) // __z has at most one non-null child. y == z.
1.114 __x = __y->_M_right; // __x might be null.
1.115 - else
1.116 + else {
1.117 if (__y->_M_right == 0) // __z has exactly one non-null child. y == z.
1.118 __x = __y->_M_left; // __x is not null.
1.119 else { // __z has two non-null children. Set __y to
1.120 - __y = __y->_M_right; // __z's successor. __x might be null.
1.121 - while (__y->_M_left != 0)
1.122 - __y = __y->_M_left;
1.123 + __y = _Rb_tree_node_base::_S_minimum(__y->_M_right); // __z's successor. __x might be null.
1.124 __x = __y->_M_right;
1.125 }
1.126 + }
1.127 +
1.128 if (__y != __z) { // relink y in place of z. y is z's successor
1.129 - __z->_M_left->_M_parent = __y;
1.130 + __z->_M_left->_M_parent = __y;
1.131 __y->_M_left = __z->_M_left;
1.132 if (__y != __z->_M_right) {
1.133 __x_parent = __y->_M_parent;
1.134 @@ -169,12 +170,12 @@
1.135 __z->_M_right->_M_parent = __y;
1.136 }
1.137 else
1.138 - __x_parent = __y;
1.139 + __x_parent = __y;
1.140 if (__root == __z)
1.141 __root = __y;
1.142 else if (__z->_M_parent->_M_left == __z)
1.143 __z->_M_parent->_M_left = __y;
1.144 - else
1.145 + else
1.146 __z->_M_parent->_M_right = __y;
1.147 __y->_M_parent = __z->_M_parent;
1.148 _STLP_STD::swap(__y->_M_color, __z->_M_color);
1.149 @@ -183,28 +184,33 @@
1.150 }
1.151 else { // __y == __z
1.152 __x_parent = __y->_M_parent;
1.153 - if (__x) __x->_M_parent = __y->_M_parent;
1.154 + if (__x) __x->_M_parent = __y->_M_parent;
1.155 if (__root == __z)
1.156 __root = __x;
1.157 - else
1.158 + else {
1.159 if (__z->_M_parent->_M_left == __z)
1.160 __z->_M_parent->_M_left = __x;
1.161 else
1.162 __z->_M_parent->_M_right = __x;
1.163 - if (__leftmost == __z)
1.164 + }
1.165 +
1.166 + if (__leftmost == __z) {
1.167 if (__z->_M_right == 0) // __z->_M_left must be null also
1.168 __leftmost = __z->_M_parent;
1.169 // makes __leftmost == _M_header if __z == __root
1.170 else
1.171 __leftmost = _Rb_tree_node_base::_S_minimum(__x);
1.172 - if (__rightmost == __z)
1.173 + }
1.174 + if (__rightmost == __z) {
1.175 if (__z->_M_left == 0) // __z->_M_right must be null also
1.176 - __rightmost = __z->_M_parent;
1.177 + __rightmost = __z->_M_parent;
1.178 // makes __rightmost == _M_header if __z == __root
1.179 else // __x == __z->_M_left
1.180 __rightmost = _Rb_tree_node_base::_S_maximum(__x);
1.181 + }
1.182 }
1.183 - if (__y->_M_color != _S_rb_tree_red) {
1.184 +
1.185 + if (__y->_M_color != _S_rb_tree_red) {
1.186 while (__x != __root && (__x == 0 || __x->_M_color == _S_rb_tree_black))
1.187 if (__x == __x_parent->_M_left) {
1.188 _Rb_tree_node_base* __w = __x_parent->_M_right;
1.189 @@ -214,14 +220,14 @@
1.190 _Rotate_left(__x_parent, __root);
1.191 __w = __x_parent->_M_right;
1.192 }
1.193 - if ((__w->_M_left == 0 ||
1.194 - __w->_M_left->_M_color == _S_rb_tree_black) && (__w->_M_right == 0 ||
1.195 + if ((__w->_M_left == 0 ||
1.196 + __w->_M_left->_M_color == _S_rb_tree_black) && (__w->_M_right == 0 ||
1.197 __w->_M_right->_M_color == _S_rb_tree_black)) {
1.198 __w->_M_color = _S_rb_tree_red;
1.199 __x = __x_parent;
1.200 __x_parent = __x_parent->_M_parent;
1.201 } else {
1.202 - if (__w->_M_right == 0 ||
1.203 + if (__w->_M_right == 0 ||
1.204 __w->_M_right->_M_color == _S_rb_tree_black) {
1.205 if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black;
1.206 __w->_M_color = _S_rb_tree_red;
1.207 @@ -242,14 +248,14 @@
1.208 _Rotate_right(__x_parent, __root);
1.209 __w = __x_parent->_M_left;
1.210 }
1.211 - if ((__w->_M_right == 0 ||
1.212 - __w->_M_right->_M_color == _S_rb_tree_black) && (__w->_M_left == 0 ||
1.213 + if ((__w->_M_right == 0 ||
1.214 + __w->_M_right->_M_color == _S_rb_tree_black) && (__w->_M_left == 0 ||
1.215 __w->_M_left->_M_color == _S_rb_tree_black)) {
1.216 __w->_M_color = _S_rb_tree_red;
1.217 __x = __x_parent;
1.218 __x_parent = __x_parent->_M_parent;
1.219 } else {
1.220 - if (__w->_M_left == 0 ||
1.221 + if (__w->_M_left == 0 ||
1.222 __w->_M_left->_M_color == _S_rb_tree_black) {
1.223 if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black;
1.224 __w->_M_color = _S_rb_tree_red;
1.225 @@ -269,15 +275,11 @@
1.226 }
1.227
1.228 template <class _Dummy> _Rb_tree_node_base* _STLP_CALL
1.229 -_Rb_global<_Dummy>::_M_decrement(_Rb_tree_node_base* _M_node)
1.230 -{
1.231 +_Rb_global<_Dummy>::_M_decrement(_Rb_tree_node_base* _M_node) {
1.232 if (_M_node->_M_color == _S_rb_tree_red && _M_node->_M_parent->_M_parent == _M_node)
1.233 _M_node = _M_node->_M_right;
1.234 else if (_M_node->_M_left != 0) {
1.235 - _Base_ptr __y = _M_node->_M_left;
1.236 - while (__y->_M_right != 0)
1.237 - __y = __y->_M_right;
1.238 - _M_node = __y;
1.239 + _M_node = _Rb_tree_node_base::_S_maximum(_M_node->_M_left);
1.240 }
1.241 else {
1.242 _Base_ptr __y = _M_node->_M_parent;
1.243 @@ -291,12 +293,9 @@
1.244 }
1.245
1.246 template <class _Dummy> _Rb_tree_node_base* _STLP_CALL
1.247 -_Rb_global<_Dummy>::_M_increment(_Rb_tree_node_base* _M_node)
1.248 -{
1.249 +_Rb_global<_Dummy>::_M_increment(_Rb_tree_node_base* _M_node) {
1.250 if (_M_node->_M_right != 0) {
1.251 - _M_node = _M_node->_M_right;
1.252 - while (_M_node->_M_left != 0)
1.253 - _M_node = _M_node->_M_left;
1.254 + _M_node = _Rb_tree_node_base::_S_minimum(_M_node->_M_right);
1.255 }
1.256 else {
1.257 _Base_ptr __y = _M_node->_M_parent;
1.258 @@ -304,30 +303,35 @@
1.259 _M_node = __y;
1.260 __y = __y->_M_parent;
1.261 }
1.262 + // check special case: This is necessary if _M_node is the
1.263 + // _M_head and the tree contains only a single node __y. In
1.264 + // that case parent, left and right all point to __y!
1.265 if (_M_node->_M_right != __y)
1.266 _M_node = __y;
1.267 }
1.268 return _M_node;
1.269 }
1.270
1.271 -#endif /* defined (__BUILDING_STLPORT) || ! defined (_STLP_OWN_IOSTREAMS) */
1.272 +#endif /* _STLP_EXPOSE_GLOBALS_IMPLEMENTATION */
1.273
1.274
1.275 -template <class _Key, class _Value, class _KeyOfValue,
1.276 - class _Compare, class _Alloc> _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::operator=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x)
1.277 -{
1.278 +template <class _Key, class _Compare,
1.279 + class _Value, class _KeyOfValue, class _Traits, class _Alloc>
1.280 +_Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc>&
1.281 +_Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::operator=(
1.282 + const _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc>& __x) {
1.283 if (this != &__x) {
1.284 - // Note that _Key may be a constant type.
1.285 + // Note that _Key may be a constant type.
1.286 clear();
1.287 _M_node_count = 0;
1.288 - _M_key_compare = __x._M_key_compare;
1.289 + _M_key_compare = __x._M_key_compare;
1.290 if (__x._M_root() == 0) {
1.291 _M_root() = 0;
1.292 - _M_leftmost() = this->_M_header._M_data;
1.293 - _M_rightmost() = this->_M_header._M_data;
1.294 + _M_leftmost() = &this->_M_header._M_data;
1.295 + _M_rightmost() = &this->_M_header._M_data;
1.296 }
1.297 else {
1.298 - _M_root() = _M_copy(__x._M_root(), this->_M_header._M_data);
1.299 + _M_root() = _M_copy(__x._M_root(), &this->_M_header._M_data);
1.300 _M_leftmost() = _S_minimum(_M_root());
1.301 _M_rightmost() = _S_maximum(_M_root());
1.302 _M_node_count = __x._M_node_count;
1.303 @@ -336,238 +340,248 @@
1.304 return *this;
1.305 }
1.306
1.307 -// CRP 7/10/00 inserted argument __w_, which is another hint (meant to
1.308 -// act like __x_ and ignore a portion of the if conditions -- specify
1.309 -// __w_ != 0 to bypass comparison as false or __x_ != 0 to bypass
1.310 +// CRP 7/10/00 inserted argument __on_right, which is another hint (meant to
1.311 +// act like __on_left and ignore a portion of the if conditions -- specify
1.312 +// __on_right != 0 to bypass comparison as false or __on_left != 0 to bypass
1.313 // comparison as true)
1.314 -template <class _Key, class _Value, class _KeyOfValue,
1.315 - class _Compare, class _Alloc> __iterator__
1.316 -_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::_M_insert(_Rb_tree_node_base* __x_, _Rb_tree_node_base* __y_, const _Value& __v,
1.317 - _Rb_tree_node_base* __w_)
1.318 -{
1.319 - _Link_type __w = (_Link_type) __w_;
1.320 - _Link_type __x = (_Link_type) __x_;
1.321 - _Link_type __y = (_Link_type) __y_;
1.322 - _Link_type __z;
1.323 +template <class _Key, class _Compare,
1.324 + class _Value, class _KeyOfValue, class _Traits, class _Alloc>
1.325 +__iterator__
1.326 +_Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::_M_insert(_Rb_tree_node_base * __parent,
1.327 + const _Value& __val,
1.328 + _Rb_tree_node_base * __on_left,
1.329 + _Rb_tree_node_base * __on_right) {
1.330 + // We do not create the node here as, depending on tests, we might call
1.331 + // _M_key_compare that can throw an exception.
1.332 + _Base_ptr __new_node;
1.333
1.334 - if ( __y == this->_M_header._M_data ||
1.335 - ( __w == 0 && // If w != 0, the remainder fails to false
1.336 - ( __x != 0 || // If x != 0, the remainder succeeds to true
1.337 - _M_key_compare( _KeyOfValue()(__v), _S_key(__y) ) )
1.338 - )
1.339 - ) {
1.340 -
1.341 - __z = _M_create_node(__v);
1.342 - _S_left(__y) = __z; // also makes _M_leftmost() = __z
1.343 - // when __y == _M_header
1.344 - if (__y == this->_M_header._M_data) {
1.345 - _M_root() = __z;
1.346 - _M_rightmost() = __z;
1.347 - }
1.348 - else if (__y == _M_leftmost())
1.349 - _M_leftmost() = __z; // maintain _M_leftmost() pointing to min node
1.350 + if ( __parent == &this->_M_header._M_data ) {
1.351 + __new_node = _M_create_node(__val);
1.352 + _S_left(__parent) = __new_node; // also makes _M_leftmost() = __new_node
1.353 + _M_root() = __new_node;
1.354 + _M_rightmost() = __new_node;
1.355 + }
1.356 + else if ( __on_right == 0 && // If __on_right != 0, the remainder fails to false
1.357 + ( __on_left != 0 || // If __on_left != 0, the remainder succeeds to true
1.358 + _M_key_compare( _KeyOfValue()(__val), _S_key(__parent) ) ) ) {
1.359 + __new_node = _M_create_node(__val);
1.360 + _S_left(__parent) = __new_node;
1.361 + if (__parent == _M_leftmost())
1.362 + _M_leftmost() = __new_node; // maintain _M_leftmost() pointing to min node
1.363 }
1.364 else {
1.365 - __z = _M_create_node(__v);
1.366 - _S_right(__y) = __z;
1.367 - if (__y == _M_rightmost())
1.368 - _M_rightmost() = __z; // maintain _M_rightmost() pointing to max node
1.369 + __new_node = _M_create_node(__val);
1.370 + _S_right(__parent) = __new_node;
1.371 + if (__parent == _M_rightmost())
1.372 + _M_rightmost() = __new_node; // maintain _M_rightmost() pointing to max node
1.373 }
1.374 - _S_parent(__z) = __y;
1.375 - _S_left(__z) = 0;
1.376 - _S_right(__z) = 0;
1.377 - _Rb_global_inst::_Rebalance(__z, this->_M_header._M_data->_M_parent);
1.378 + _S_parent(__new_node) = __parent;
1.379 + _Rb_global_inst::_Rebalance(__new_node, this->_M_header._M_data._M_parent);
1.380 ++_M_node_count;
1.381 - return iterator(__z);
1.382 + return iterator(__new_node);
1.383 }
1.384
1.385 -template <class _Key, class _Value, class _KeyOfValue,
1.386 - class _Compare, class _Alloc> __iterator__
1.387 -_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::insert_equal(const _Value& __v)
1.388 -{
1.389 - _Link_type __y = this->_M_header._M_data;
1.390 - _Link_type __x = _M_root();
1.391 +template <class _Key, class _Compare,
1.392 + class _Value, class _KeyOfValue, class _Traits, class _Alloc>
1.393 +__iterator__
1.394 +_Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::insert_equal(const _Value& __val) {
1.395 + _Base_ptr __y = &this->_M_header._M_data;
1.396 + _Base_ptr __x = _M_root();
1.397 while (__x != 0) {
1.398 __y = __x;
1.399 - __x = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
1.400 - _S_left(__x) : _S_right(__x);
1.401 + if (_M_key_compare(_KeyOfValue()(__val), _S_key(__x))) {
1.402 + __x = _S_left(__x);
1.403 + }
1.404 + else
1.405 + __x = _S_right(__x);
1.406 }
1.407 - return _M_insert(__x, __y, __v);
1.408 + return _M_insert(__y, __val, __x);
1.409 }
1.410
1.411
1.412 -template <class _Key, class _Value, class _KeyOfValue,
1.413 - class _Compare, class _Alloc> pair< _Rb_tree_iterator<_Value, _Nonconst_traits<_Value> >, bool> _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::insert_unique(const _Value& __v)
1.414 -{
1.415 - _Link_type __y = this->_M_header._M_data;
1.416 - _Link_type __x = _M_root();
1.417 +template <class _Key, class _Compare,
1.418 + class _Value, class _KeyOfValue, class _Traits, class _Alloc>
1.419 +pair<__iterator__, bool>
1.420 +_Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::insert_unique(const _Value& __val) {
1.421 + _Base_ptr __y = &this->_M_header._M_data;
1.422 + _Base_ptr __x = _M_root();
1.423 bool __comp = true;
1.424 while (__x != 0) {
1.425 __y = __x;
1.426 - __comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x));
1.427 + __comp = _M_key_compare(_KeyOfValue()(__val), _S_key(__x));
1.428 __x = __comp ? _S_left(__x) : _S_right(__x);
1.429 }
1.430 - iterator __j = iterator(__y);
1.431 - if (__comp)
1.432 - if (__j == begin())
1.433 - return pair<iterator,bool>(_M_insert(/* __x*/ __y, __y, __v), true);
1.434 + iterator __j = iterator(__y);
1.435 + if (__comp) {
1.436 + if (__j == begin())
1.437 + return pair<iterator,bool>(_M_insert(__y, __val, /* __x*/ __y), true);
1.438 else
1.439 --__j;
1.440 - if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
1.441 - return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
1.442 + }
1.443 + if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__val))) {
1.444 + return pair<iterator,bool>(_M_insert(__y, __val, __x), true);
1.445 + }
1.446 return pair<iterator,bool>(__j, false);
1.447 }
1.448
1.449 // Modifications CRP 7/10/00 as noted to improve conformance and
1.450 // efficiency.
1.451 -template <class _Key, class _Value, class _KeyOfValue,
1.452 - class _Compare, class _Alloc> __iterator__
1.453 -_Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc> ::insert_unique(iterator __position, const _Value& __v)
1.454 -{
1.455 - if (__position._M_node == this->_M_header._M_data->_M_left) { // begin()
1.456 +template <class _Key, class _Compare,
1.457 + class _Value, class _KeyOfValue, class _Traits, class _Alloc>
1.458 +__iterator__
1.459 +_Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::insert_unique(iterator __position,
1.460 + const _Value& __val) {
1.461 + if (__position._M_node == this->_M_header._M_data._M_left) { // begin()
1.462
1.463 // if the container is empty, fall back on insert_unique.
1.464 - if (size() <= 0)
1.465 - return insert_unique(__v).first;
1.466 + if (empty())
1.467 + return insert_unique(__val).first;
1.468
1.469 - if ( _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node)))
1.470 - return _M_insert(__position._M_node, __position._M_node, __v);
1.471 - // first argument just needs to be non-null
1.472 + if (_M_key_compare(_KeyOfValue()(__val), _S_key(__position._M_node))) {
1.473 + return _M_insert(__position._M_node, __val, __position._M_node);
1.474 + }
1.475 + // first argument just needs to be non-null
1.476 + else {
1.477 + bool __comp_pos_v = _M_key_compare( _S_key(__position._M_node), _KeyOfValue()(__val) );
1.478 +
1.479 + if (__comp_pos_v == false) // compare > and compare < both false so compare equal
1.480 + return __position;
1.481 + //Below __comp_pos_v == true
1.482 +
1.483 + // Standard-conformance - does the insertion point fall immediately AFTER
1.484 + // the hint?
1.485 + iterator __after = __position;
1.486 + ++__after;
1.487 +
1.488 + // Check for only one member -- in that case, __position points to itself,
1.489 + // and attempting to increment will cause an infinite loop.
1.490 + if (__after._M_node == &this->_M_header._M_data)
1.491 + // Check guarantees exactly one member, so comparison was already
1.492 + // performed and we know the result; skip repeating it in _M_insert
1.493 + // by specifying a non-zero fourth argument.
1.494 + return _M_insert(__position._M_node, __val, 0, __position._M_node);
1.495 +
1.496 + // All other cases:
1.497 +
1.498 + // Optimization to catch insert-equivalent -- save comparison results,
1.499 + // and we get this for free.
1.500 + if (_M_key_compare( _KeyOfValue()(__val), _S_key(__after._M_node) )) {
1.501 + if (_S_right(__position._M_node) == 0)
1.502 + return _M_insert(__position._M_node, __val, 0, __position._M_node);
1.503 + else
1.504 + return _M_insert(__after._M_node, __val, __after._M_node);
1.505 + }
1.506 + else {
1.507 + return insert_unique(__val).first;
1.508 + }
1.509 + }
1.510 + }
1.511 + else if (__position._M_node == &this->_M_header._M_data) { // end()
1.512 + if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__val))) {
1.513 + // pass along to _M_insert that it can skip comparing
1.514 + // v, Key ; since compare Key, v was true, compare v, Key must be false.
1.515 + return _M_insert(_M_rightmost(), __val, 0, __position._M_node); // Last argument only needs to be non-null
1.516 + }
1.517 else
1.518 - {
1.519 - bool __comp_pos_v = _M_key_compare( _S_key(__position._M_node), _KeyOfValue()(__v) );
1.520 -
1.521 - if (__comp_pos_v == false) // compare > and compare < both false so compare equal
1.522 - return __position;
1.523 - //Below __comp_pos_v == true
1.524 + return insert_unique(__val).first;
1.525 + }
1.526 + else {
1.527 + iterator __before = __position;
1.528 + --__before;
1.529
1.530 - // Standard-conformance - does the insertion point fall immediately AFTER
1.531 - // the hint?
1.532 - iterator __after = __position;
1.533 - ++__after;
1.534 + bool __comp_v_pos = _M_key_compare(_KeyOfValue()(__val), _S_key(__position._M_node));
1.535
1.536 - // Check for only one member -- in that case, __position points to itself,
1.537 - // and attempting to increment will cause an infinite loop.
1.538 - if (__after._M_node == this->_M_header._M_data)
1.539 - // Check guarantees exactly one member, so comparison was already
1.540 - // performed and we know the result; skip repeating it in _M_insert
1.541 - // by specifying a non-zero fourth argument.
1.542 - return _M_insert(0, __position._M_node, __v, __position._M_node);
1.543 -
1.544 -
1.545 - // All other cases:
1.546 -
1.547 - // Optimization to catch insert-equivalent -- save comparison results,
1.548 - // and we get this for free.
1.549 - if(_M_key_compare( _KeyOfValue()(__v), _S_key(__after._M_node) )) {
1.550 - if (_S_right(__position._M_node) == 0)
1.551 - return _M_insert(0, __position._M_node, __v, __position._M_node);
1.552 - else
1.553 - return _M_insert(__after._M_node, __after._M_node, __v);
1.554 - } else {
1.555 - return insert_unique(__v).first;
1.556 - }
1.557 + if (__comp_v_pos
1.558 + && _M_key_compare( _S_key(__before._M_node), _KeyOfValue()(__val) )) {
1.559 +
1.560 + if (_S_right(__before._M_node) == 0)
1.561 + return _M_insert(__before._M_node, __val, 0, __before._M_node); // Last argument only needs to be non-null
1.562 + else
1.563 + return _M_insert(__position._M_node, __val, __position._M_node);
1.564 + // first argument just needs to be non-null
1.565 + }
1.566 + else {
1.567 + // Does the insertion point fall immediately AFTER the hint?
1.568 + iterator __after = __position;
1.569 + ++__after;
1.570 + // Optimization to catch equivalent cases and avoid unnecessary comparisons
1.571 + bool __comp_pos_v = !__comp_v_pos; // Stored this result earlier
1.572 + // If the earlier comparison was true, this comparison doesn't need to be
1.573 + // performed because it must be false. However, if the earlier comparison
1.574 + // was false, we need to perform this one because in the equal case, both will
1.575 + // be false.
1.576 + if (!__comp_v_pos) {
1.577 + __comp_pos_v = _M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__val));
1.578 }
1.579
1.580 - } else if (__position._M_node == this->_M_header._M_data) { // end()
1.581 - if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v)))
1.582 - // pass along to _M_insert that it can skip comparing
1.583 - // v, Key ; since compare Key, v was true, compare v, Key must be false.
1.584 - return _M_insert(0, _M_rightmost(), __v, __position._M_node); // Last argument only needs to be non-null
1.585 - else
1.586 - return insert_unique(__v).first;
1.587 - } else {
1.588 - iterator __before = __position;
1.589 - --__before;
1.590 -
1.591 - bool __comp_v_pos = _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node));
1.592 -
1.593 - if (__comp_v_pos
1.594 - && _M_key_compare( _S_key(__before._M_node), _KeyOfValue()(__v) )) {
1.595 -
1.596 - if (_S_right(__before._M_node) == 0)
1.597 - return _M_insert(0, __before._M_node, __v, __before._M_node); // Last argument only needs to be non-null
1.598 - else
1.599 - return _M_insert(__position._M_node, __position._M_node, __v);
1.600 - // first argument just needs to be non-null
1.601 - } else
1.602 - {
1.603 - // Does the insertion point fall immediately AFTER the hint?
1.604 - iterator __after = __position;
1.605 - ++__after;
1.606 -
1.607 - // Optimization to catch equivalent cases and avoid unnecessary comparisons
1.608 - bool __comp_pos_v = !__comp_v_pos; // Stored this result earlier
1.609 - // If the earlier comparison was true, this comparison doesn't need to be
1.610 - // performed because it must be false. However, if the earlier comparison
1.611 - // was false, we need to perform this one because in the equal case, both will
1.612 - // be false.
1.613 - if (!__comp_v_pos) __comp_pos_v = _M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v));
1.614 -
1.615 - if ( (!__comp_v_pos) // comp_v_pos true implies comp_v_pos false
1.616 - && __comp_pos_v
1.617 - && (__after._M_node == this->_M_header._M_data ||
1.618 - _M_key_compare( _KeyOfValue()(__v), _S_key(__after._M_node) ))) {
1.619 -
1.620 - if (_S_right(__position._M_node) == 0)
1.621 - return _M_insert(0, __position._M_node, __v, __position._M_node);
1.622 - else
1.623 - return _M_insert(__after._M_node, __after._M_node, __v);
1.624 - } else {
1.625 - // Test for equivalent case
1.626 - if (__comp_v_pos == __comp_pos_v)
1.627 - return __position;
1.628 - else
1.629 - return insert_unique(__v).first;
1.630 - }
1.631 + if ( (!__comp_v_pos) // comp_v_pos true implies comp_v_pos false
1.632 + && __comp_pos_v
1.633 + && (__after._M_node == &this->_M_header._M_data ||
1.634 + _M_key_compare( _KeyOfValue()(__val), _S_key(__after._M_node) ))) {
1.635 + if (_S_right(__position._M_node) == 0)
1.636 + return _M_insert(__position._M_node, __val, 0, __position._M_node);
1.637 + else
1.638 + return _M_insert(__after._M_node, __val, __after._M_node);
1.639 + } else {
1.640 + // Test for equivalent case
1.641 + if (__comp_v_pos == __comp_pos_v)
1.642 + return __position;
1.643 + else
1.644 + return insert_unique(__val).first;
1.645 }
1.646 + }
1.647 }
1.648 }
1.649
1.650 -
1.651 -template <class _Key, class _Value, class _KeyOfValue,
1.652 - class _Compare, class _Alloc> __iterator__
1.653 -_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::insert_equal(iterator __position, const _Value& __v)
1.654 -{
1.655 - if (__position._M_node == this->_M_header._M_data->_M_left) { // begin()
1.656 +template <class _Key, class _Compare,
1.657 + class _Value, class _KeyOfValue, class _Traits, class _Alloc>
1.658 +__iterator__
1.659 +_Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::insert_equal(iterator __position,
1.660 + const _Value& __val) {
1.661 + if (__position._M_node == this->_M_header._M_data._M_left) { // begin()
1.662
1.663 // Check for zero members
1.664 if (size() <= 0)
1.665 - return insert_equal(__v);
1.666 + return insert_equal(__val);
1.667
1.668 - if (!_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v)))
1.669 - return _M_insert(__position._M_node, __position._M_node, __v);
1.670 - else {
1.671 + if (!_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__val)))
1.672 + return _M_insert(__position._M_node, __val, __position._M_node);
1.673 + else {
1.674 // Check for only one member
1.675 if (__position._M_node->_M_left == __position._M_node)
1.676 // Unlike insert_unique, can't avoid doing a comparison here.
1.677 - return _M_insert(0, __position._M_node, __v);
1.678 -
1.679 + return _M_insert(__position._M_node, __val);
1.680 +
1.681 // All other cases:
1.682 // Standard-conformance - does the insertion point fall immediately AFTER
1.683 // the hint?
1.684 iterator __after = __position;
1.685 ++__after;
1.686 -
1.687 +
1.688 // Already know that compare(pos, v) must be true!
1.689 // Therefore, we want to know if compare(after, v) is false.
1.690 // (i.e., we now pos < v, now we want to know if v <= after)
1.691 // If not, invalid hint.
1.692 - if ( __after._M_node==this->_M_header._M_data ||
1.693 - !_M_key_compare( _S_key(__after._M_node), _KeyOfValue()(__v) ) ) {
1.694 + if ( __after._M_node == &this->_M_header._M_data ||
1.695 + !_M_key_compare( _S_key(__after._M_node), _KeyOfValue()(__val) ) ) {
1.696 if (_S_right(__position._M_node) == 0)
1.697 - return _M_insert(0, __position._M_node, __v, __position._M_node);
1.698 + return _M_insert(__position._M_node, __val, 0, __position._M_node);
1.699 else
1.700 - return _M_insert(__after._M_node, __after._M_node, __v);
1.701 - } else // Invalid hint
1.702 - return insert_equal(__v);
1.703 + return _M_insert(__after._M_node, __val, __after._M_node);
1.704 + }
1.705 + else { // Invalid hint
1.706 + return insert_equal(__val);
1.707 + }
1.708 }
1.709 - } else if (__position._M_node == this->_M_header._M_data) {// end()
1.710 - if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost())))
1.711 - return _M_insert(0, _M_rightmost(), __v, __position._M_node); // Last argument only needs to be non-null
1.712 - else
1.713 - return insert_equal(__v);
1.714 - } else {
1.715 + }
1.716 + else if (__position._M_node == &this->_M_header._M_data) { // end()
1.717 + if (!_M_key_compare(_KeyOfValue()(__val), _S_key(_M_rightmost())))
1.718 + return _M_insert(_M_rightmost(), __val, 0, __position._M_node); // Last argument only needs to be non-null
1.719 + else {
1.720 + return insert_equal(__val);
1.721 + }
1.722 + }
1.723 + else {
1.724 iterator __before = __position;
1.725 --__before;
1.726 // store the result of the comparison between pos and v so
1.727 @@ -575,88 +589,83 @@
1.728 // on the if, possibly harming efficiency in comparisons; I think the harm will
1.729 // be negligible, and to do what I want to do (save the result of a comparison so
1.730 // that it can be re-used) there is no alternative. Test here is for before <= v <= pos.
1.731 - bool __comp_pos_v = _M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v));
1.732 - if (!__comp_pos_v
1.733 - && !_M_key_compare(_KeyOfValue()(__v), _S_key(__before._M_node))) {
1.734 + bool __comp_pos_v = _M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__val));
1.735 + if (!__comp_pos_v &&
1.736 + !_M_key_compare(_KeyOfValue()(__val), _S_key(__before._M_node))) {
1.737 if (_S_right(__before._M_node) == 0)
1.738 - return _M_insert(0, __before._M_node, __v, __before._M_node); // Last argument only needs to be non-null
1.739 + return _M_insert(__before._M_node, __val, 0, __before._M_node); // Last argument only needs to be non-null
1.740 else
1.741 - return _M_insert(__position._M_node, __position._M_node, __v);
1.742 - } else {
1.743 + return _M_insert(__position._M_node, __val, __position._M_node);
1.744 + }
1.745 + else {
1.746 // Does the insertion point fall immediately AFTER the hint?
1.747 // Test for pos < v <= after
1.748 iterator __after = __position;
1.749 ++__after;
1.750 -
1.751 - if (__comp_pos_v
1.752 - && ( __after._M_node==this->_M_header._M_data
1.753 - || !_M_key_compare( _S_key(__after._M_node), _KeyOfValue()(__v) ) ) ) {
1.754 +
1.755 + if (__comp_pos_v &&
1.756 + ( __after._M_node == &this->_M_header._M_data ||
1.757 + !_M_key_compare( _S_key(__after._M_node), _KeyOfValue()(__val) ) ) ) {
1.758 if (_S_right(__position._M_node) == 0)
1.759 - return _M_insert(0, __position._M_node, __v, __position._M_node);
1.760 + return _M_insert(__position._M_node, __val, 0, __position._M_node);
1.761 else
1.762 - return _M_insert(__after._M_node, __after._M_node, __v);
1.763 - } else // Invalid hint
1.764 - return insert_equal(__v);
1.765 + return _M_insert(__after._M_node, __val, __after._M_node);
1.766 + }
1.767 + else { // Invalid hint
1.768 + return insert_equal(__val);
1.769 + }
1.770 }
1.771 }
1.772 }
1.773
1.774 -template <class _Key, class _Value, class _KeyOfValue, class _Compare, class _Alloc> _Rb_tree_node<_Value>*
1.775 -_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::_M_copy(_Rb_tree_node<_Value>* __x, _Rb_tree_node<_Value>* __p)
1.776 -{
1.777 - // structural copy. __x and __p must be non-null.
1.778 - _STLP_LEAVE_VOLATILE _Link_type __top = _M_clone_node(__x);
1.779 - __top->_M_parent = __p;
1.780 -
1.781 +template <class _Key, class _Compare,
1.782 + class _Value, class _KeyOfValue, class _Traits, class _Alloc>
1.783 +_Rb_tree_node_base*
1.784 +_Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::_M_copy(_Rb_tree_node_base* __x,
1.785 + _Rb_tree_node_base* __p) {
1.786 + // structural copy. __x and __p must be non-null.
1.787 + _Base_ptr __top = _M_clone_node(__x);
1.788 + _S_parent(__top) = __p;
1.789 +
1.790 _STLP_TRY {
1.791 - if (__x->_M_right)
1.792 - __top->_M_right = _M_copy(_S_right(__x), __top);
1.793 + if (_S_right(__x))
1.794 + _S_right(__top) = _M_copy(_S_right(__x), __top);
1.795 __p = __top;
1.796 __x = _S_left(__x);
1.797
1.798 while (__x != 0) {
1.799 - _Link_type __y = _M_clone_node(__x);
1.800 - __p->_M_left = __y;
1.801 - __y->_M_parent = __p;
1.802 - if (__x->_M_right)
1.803 - __y->_M_right = _M_copy(_S_right(__x), __y);
1.804 + _Base_ptr __y = _M_clone_node(__x);
1.805 + _S_left(__p) = __y;
1.806 + _S_parent(__y) = __p;
1.807 + if (_S_right(__x))
1.808 + _S_right(__y) = _M_copy(_S_right(__x), __y);
1.809 __p = __y;
1.810 __x = _S_left(__x);
1.811 }
1.812 }
1.813 - _STLP_UNWIND(_M_erase(__top));
1.814 + _STLP_UNWIND(_M_erase(__top))
1.815
1.816 return __top;
1.817 }
1.818
1.819 // this has to stay out-of-line : it's recursive
1.820 -template <class _Key, class _Value, class _KeyOfValue,
1.821 - class _Compare, class _Alloc> void
1.822 -_Rb_tree<_Key,_Value,_KeyOfValue,
1.823 - _Compare,_Alloc>::_M_erase(_Rb_tree_node<_Value>* __x)
1.824 -{
1.825 - // erase without rebalancing
1.826 +template <class _Key, class _Compare,
1.827 + class _Value, class _KeyOfValue, class _Traits, class _Alloc>
1.828 +void
1.829 +_Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc>::_M_erase(_Rb_tree_node_base *__x) {
1.830 + // erase without rebalancing
1.831 while (__x != 0) {
1.832 _M_erase(_S_right(__x));
1.833 - _Link_type __y = _S_left(__x);
1.834 - _STLP_STD::_Destroy(&__x->_M_value_field);
1.835 - this->_M_header.deallocate(__x,1);
1.836 + _Base_ptr __y = _S_left(__x);
1.837 + _STLP_STD::_Destroy(&_S_value(__x));
1.838 + this->_M_header.deallocate(__STATIC_CAST(_Link_type, __x),1);
1.839 __x = __y;
1.840 }
1.841 }
1.842
1.843 -template <class _Key, class _Value, class _KeyOfValue,
1.844 - class _Compare, class _Alloc> __size_type__
1.845 -_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::count(const _Key& __k) const
1.846 -{
1.847 - pair<const_iterator, const_iterator> __p = equal_range(__k);
1.848 - size_type __n = distance(__p.first, __p.second);
1.849 - return __n;
1.850 -}
1.851 -
1.852 -inline int
1.853 -__black_count(_Rb_tree_node_base* __node, _Rb_tree_node_base* __root)
1.854 -{
1.855 +#if defined (_STLP_DEBUG)
1.856 +inline int
1.857 +__black_count(_Rb_tree_node_base* __node, _Rb_tree_node_base* __root) {
1.858 if (__node == 0)
1.859 return 0;
1.860 else {
1.861 @@ -668,18 +677,20 @@
1.862 }
1.863 }
1.864
1.865 -template <class _Key, class _Value, class _KeyOfValue,
1.866 - class _Compare, class _Alloc> bool _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1.867 -{
1.868 +template <class _Key, class _Compare,
1.869 + class _Value, class _KeyOfValue, class _Traits, class _Alloc>
1.870 +bool _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc>::__rb_verify() const {
1.871 if (_M_node_count == 0 || begin() == end())
1.872 - return _M_node_count == 0 && begin() == end() && this->_M_header._M_data->_M_left == this->_M_header._M_data
1.873 - && this->_M_header._M_data->_M_right == this->_M_header._M_data;
1.874 -
1.875 + return ((_M_node_count == 0) &&
1.876 + (begin() == end()) &&
1.877 + (this->_M_header._M_data._M_left == &this->_M_header._M_data) &&
1.878 + (this->_M_header._M_data._M_right == &this->_M_header._M_data));
1.879 +
1.880 int __len = __black_count(_M_leftmost(), _M_root());
1.881 for (const_iterator __it = begin(); __it != end(); ++__it) {
1.882 - _Link_type __x = (_Link_type) __it._M_node;
1.883 - _Link_type __L = _S_left(__x);
1.884 - _Link_type __R = _S_right(__x);
1.885 + _Base_ptr __x = __it._M_node;
1.886 + _Base_ptr __L = _S_left(__x);
1.887 + _Base_ptr __R = _S_right(__x);
1.888
1.889 if (__x->_M_color == _S_rb_tree_red)
1.890 if ((__L && __L->_M_color == _S_rb_tree_red) ||
1.891 @@ -702,11 +713,15 @@
1.892
1.893 return true;
1.894 }
1.895 +#endif /* _STLP_DEBUG */
1.896 +
1.897 +_STLP_MOVE_TO_STD_NAMESPACE
1.898 _STLP_END_NAMESPACE
1.899
1.900 -# undef __iterator__
1.901 -# undef iterator
1.902 -# undef __size_type__
1.903 +#undef _Rb_tree
1.904 +#undef __iterator__
1.905 +#undef iterator
1.906 +#undef __size_type__
1.907
1.908 #endif /* _STLP_TREE_C */
1.909