1 /* 2 * 3 * 4 * Copyright (c) 1994 5 * Hewlett-Packard Company 6 * 7 * Copyright (c) 1996,1997 8 * Silicon Graphics Computer Systems, Inc. 9 * 10 * Copyright (c) 1997 11 * Moscow Center for SPARC Technology 12 * 13 * Copyright (c) 1999 14 * Boris Fomitchev 15 * 16 * This material is provided "as is", with absolutely no warranty expressed 17 * or implied. Any use is at your own risk. 18 * 19 * Permission to use or copy this software for any purpose is hereby granted 20 * without fee, provided the above notices are retained on all copies. 21 * Permission to modify the code and to distribute modified code is granted, 22 * provided the above notices are retained, and a notice that the code was 23 * modified is included with the above copyright notice. 24 * 25 * Modified CRP 7/10/00 for improved conformance / efficiency on insert_unique / 26 * insert_equal with valid hint -- efficiency is improved all around, and it is 27 * should now be standard conforming for complexity on insert point immediately 28 * after hint (amortized constant time). 29 * 30 */ 31 #ifndef _STLP_TREE_C 32 #define _STLP_TREE_C 33 34 #ifndef _STLP_INTERNAL_TREE_H 35 # include <stl/_tree.h> 36 #endif 37 38 #if defined (_STLP_DEBUG) 39 # define _Rb_tree _STLP_NON_DBG_NAME(Rb_tree) 40 #endif 41 42 // fbp: these defines are for outline methods definitions. 43 // needed for definitions to be portable. Should not be used in method bodies. 44 #if defined (_STLP_NESTED_TYPE_PARAM_BUG) 45 # define __iterator__ _Rb_tree_iterator<_Value, _STLP_HEADER_TYPENAME _Traits::_NonConstTraits> 46 # define __size_type__ size_t 47 # define iterator __iterator__ 48 #else 49 # define __iterator__ _STLP_TYPENAME_ON_RETURN_TYPE _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc>::iterator 50 # define __size_type__ _STLP_TYPENAME_ON_RETURN_TYPE _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc>::size_type 51 #endif 52 53 _STLP_BEGIN_NAMESPACE 54 55 _STLP_MOVE_TO_PRIV_NAMESPACE 56 57 #if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION) 58 59 template <class _Dummy> void _STLP_CALL 60 _Rb_global<_Dummy>::_Rotate_left(_Rb_tree_node_base* __x, 61 _Rb_tree_node_base*& __root) { 62 _Rb_tree_node_base* __y = __x->_M_right; 63 __x->_M_right = __y->_M_left; 64 if (__y->_M_left != 0) 65 __y->_M_left->_M_parent = __x; 66 __y->_M_parent = __x->_M_parent; 67 68 if (__x == __root) 69 __root = __y; 70 else if (__x == __x->_M_parent->_M_left) 71 __x->_M_parent->_M_left = __y; 72 else 73 __x->_M_parent->_M_right = __y; 74 __y->_M_left = __x; 75 __x->_M_parent = __y; 76 } 77 78 template <class _Dummy> void _STLP_CALL 79 _Rb_global<_Dummy>::_Rotate_right(_Rb_tree_node_base* __x, 80 _Rb_tree_node_base*& __root) { 81 _Rb_tree_node_base* __y = __x->_M_left; 82 __x->_M_left = __y->_M_right; 83 if (__y->_M_right != 0) 84 __y->_M_right->_M_parent = __x; 85 __y->_M_parent = __x->_M_parent; 86 87 if (__x == __root) 88 __root = __y; 89 else if (__x == __x->_M_parent->_M_right) 90 __x->_M_parent->_M_right = __y; 91 else 92 __x->_M_parent->_M_left = __y; 93 __y->_M_right = __x; 94 __x->_M_parent = __y; 95 } 96 97 template <class _Dummy> void _STLP_CALL 98 _Rb_global<_Dummy>::_Rebalance(_Rb_tree_node_base* __x, 99 _Rb_tree_node_base*& __root) { 100 __x->_M_color = _S_rb_tree_red; 101 while (__x != __root && __x->_M_parent->_M_color == _S_rb_tree_red) { 102 if (__x->_M_parent == __x->_M_parent->_M_parent->_M_left) { 103 _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_right; 104 if (__y && __y->_M_color == _S_rb_tree_red) { 105 __x->_M_parent->_M_color = _S_rb_tree_black; 106 __y->_M_color = _S_rb_tree_black; 107 __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red; 108 __x = __x->_M_parent->_M_parent; 109 } 110 else { 111 if (__x == __x->_M_parent->_M_right) { 112 __x = __x->_M_parent; 113 _Rotate_left(__x, __root); 114 } 115 __x->_M_parent->_M_color = _S_rb_tree_black; 116 __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red; 117 _Rotate_right(__x->_M_parent->_M_parent, __root); 118 } 119 } 120 else { 121 _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_left; 122 if (__y && __y->_M_color == _S_rb_tree_red) { 123 __x->_M_parent->_M_color = _S_rb_tree_black; 124 __y->_M_color = _S_rb_tree_black; 125 __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red; 126 __x = __x->_M_parent->_M_parent; 127 } 128 else { 129 if (__x == __x->_M_parent->_M_left) { 130 __x = __x->_M_parent; 131 _Rotate_right(__x, __root); 132 } 133 __x->_M_parent->_M_color = _S_rb_tree_black; 134 __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red; 135 _Rotate_left(__x->_M_parent->_M_parent, __root); 136 } 137 } 138 } 139 __root->_M_color = _S_rb_tree_black; 140 } 141 142 template <class _Dummy> _Rb_tree_node_base* _STLP_CALL 143 _Rb_global<_Dummy>::_Rebalance_for_erase(_Rb_tree_node_base* __z, 144 _Rb_tree_node_base*& __root, 145 _Rb_tree_node_base*& __leftmost, 146 _Rb_tree_node_base*& __rightmost) { 147 _Rb_tree_node_base* __y = __z; 148 _Rb_tree_node_base* __x; 149 _Rb_tree_node_base* __x_parent; 150 151 if (__y->_M_left == 0) // __z has at most one non-null child. y == z. 152 __x = __y->_M_right; // __x might be null. 153 else { 154 if (__y->_M_right == 0) // __z has exactly one non-null child. y == z. 155 __x = __y->_M_left; // __x is not null. 156 else { // __z has two non-null children. Set __y to 157 __y = _Rb_tree_node_base::_S_minimum(__y->_M_right); // __z's successor. __x might be null. 158 __x = __y->_M_right; 159 } 160 } 161 162 if (__y != __z) { // relink y in place of z. y is z's successor 163 __z->_M_left->_M_parent = __y; 164 __y->_M_left = __z->_M_left; 165 if (__y != __z->_M_right) { 166 __x_parent = __y->_M_parent; 167 if (__x) __x->_M_parent = __y->_M_parent; 168 __y->_M_parent->_M_left = __x; // __y must be a child of _M_left 169 __y->_M_right = __z->_M_right; 170 __z->_M_right->_M_parent = __y; 171 } 172 else 173 __x_parent = __y; 174 if (__root == __z) 175 __root = __y; 176 else if (__z->_M_parent->_M_left == __z) 177 __z->_M_parent->_M_left = __y; 178 else 179 __z->_M_parent->_M_right = __y; 180 __y->_M_parent = __z->_M_parent; 181 _STLP_STD::swap(__y->_M_color, __z->_M_color); 182 __y = __z; 183 // __y now points to node to be actually deleted 184 } 185 else { // __y == __z 186 __x_parent = __y->_M_parent; 187 if (__x) __x->_M_parent = __y->_M_parent; 188 if (__root == __z) 189 __root = __x; 190 else { 191 if (__z->_M_parent->_M_left == __z) 192 __z->_M_parent->_M_left = __x; 193 else 194 __z->_M_parent->_M_right = __x; 195 } 196 197 if (__leftmost == __z) { 198 if (__z->_M_right == 0) // __z->_M_left must be null also 199 __leftmost = __z->_M_parent; 200 // makes __leftmost == _M_header if __z == __root 201 else 202 __leftmost = _Rb_tree_node_base::_S_minimum(__x); 203 } 204 if (__rightmost == __z) { 205 if (__z->_M_left == 0) // __z->_M_right must be null also 206 __rightmost = __z->_M_parent; 207 // makes __rightmost == _M_header if __z == __root 208 else // __x == __z->_M_left 209 __rightmost = _Rb_tree_node_base::_S_maximum(__x); 210 } 211 } 212 213 if (__y->_M_color != _S_rb_tree_red) { 214 while (__x != __root && (__x == 0 || __x->_M_color == _S_rb_tree_black)) 215 if (__x == __x_parent->_M_left) { 216 _Rb_tree_node_base* __w = __x_parent->_M_right; 217 if (__w->_M_color == _S_rb_tree_red) { 218 __w->_M_color = _S_rb_tree_black; 219 __x_parent->_M_color = _S_rb_tree_red; 220 _Rotate_left(__x_parent, __root); 221 __w = __x_parent->_M_right; 222 } 223 if ((__w->_M_left == 0 || 224 __w->_M_left->_M_color == _S_rb_tree_black) && (__w->_M_right == 0 || 225 __w->_M_right->_M_color == _S_rb_tree_black)) { 226 __w->_M_color = _S_rb_tree_red; 227 __x = __x_parent; 228 __x_parent = __x_parent->_M_parent; 229 } else { 230 if (__w->_M_right == 0 || 231 __w->_M_right->_M_color == _S_rb_tree_black) { 232 if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black; 233 __w->_M_color = _S_rb_tree_red; 234 _Rotate_right(__w, __root); 235 __w = __x_parent->_M_right; 236 } 237 __w->_M_color = __x_parent->_M_color; 238 __x_parent->_M_color = _S_rb_tree_black; 239 if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black; 240 _Rotate_left(__x_parent, __root); 241 break; 242 } 243 } else { // same as above, with _M_right <-> _M_left. 244 _Rb_tree_node_base* __w = __x_parent->_M_left; 245 if (__w->_M_color == _S_rb_tree_red) { 246 __w->_M_color = _S_rb_tree_black; 247 __x_parent->_M_color = _S_rb_tree_red; 248 _Rotate_right(__x_parent, __root); 249 __w = __x_parent->_M_left; 250 } 251 if ((__w->_M_right == 0 || 252 __w->_M_right->_M_color == _S_rb_tree_black) && (__w->_M_left == 0 || 253 __w->_M_left->_M_color == _S_rb_tree_black)) { 254 __w->_M_color = _S_rb_tree_red; 255 __x = __x_parent; 256 __x_parent = __x_parent->_M_parent; 257 } else { 258 if (__w->_M_left == 0 || 259 __w->_M_left->_M_color == _S_rb_tree_black) { 260 if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black; 261 __w->_M_color = _S_rb_tree_red; 262 _Rotate_left(__w, __root); 263 __w = __x_parent->_M_left; 264 } 265 __w->_M_color = __x_parent->_M_color; 266 __x_parent->_M_color = _S_rb_tree_black; 267 if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black; 268 _Rotate_right(__x_parent, __root); 269 break; 270 } 271 } 272 if (__x) __x->_M_color = _S_rb_tree_black; 273 } 274 return __y; 275 } 276 277 template <class _Dummy> _Rb_tree_node_base* _STLP_CALL 278 _Rb_global<_Dummy>::_M_decrement(_Rb_tree_node_base* _M_node) { 279 if (_M_node->_M_color == _S_rb_tree_red && _M_node->_M_parent->_M_parent == _M_node) 280 _M_node = _M_node->_M_right; 281 else if (_M_node->_M_left != 0) { 282 _M_node = _Rb_tree_node_base::_S_maximum(_M_node->_M_left); 283 } 284 else { 285 _Base_ptr __y = _M_node->_M_parent; 286 while (_M_node == __y->_M_left) { 287 _M_node = __y; 288 __y = __y->_M_parent; 289 } 290 _M_node = __y; 291 } 292 return _M_node; 293 } 294 295 template <class _Dummy> _Rb_tree_node_base* _STLP_CALL 296 _Rb_global<_Dummy>::_M_increment(_Rb_tree_node_base* _M_node) { 297 if (_M_node->_M_right != 0) { 298 _M_node = _Rb_tree_node_base::_S_minimum(_M_node->_M_right); 299 } 300 else { 301 _Base_ptr __y = _M_node->_M_parent; 302 while (_M_node == __y->_M_right) { 303 _M_node = __y; 304 __y = __y->_M_parent; 305 } 306 // check special case: This is necessary if _M_node is the 307 // _M_head and the tree contains only a single node __y. In 308 // that case parent, left and right all point to __y! 309 if (_M_node->_M_right != __y) 310 _M_node = __y; 311 } 312 return _M_node; 313 } 314 315 #endif /* _STLP_EXPOSE_GLOBALS_IMPLEMENTATION */ 316 317 318 template <class _Key, class _Compare, 319 class _Value, class _KeyOfValue, class _Traits, class _Alloc> 320 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc>& 321 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::operator=( 322 const _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc>& __x) { 323 if (this != &__x) { 324 // Note that _Key may be a constant type. 325 clear(); 326 _M_node_count = 0; 327 _M_key_compare = __x._M_key_compare; 328 if (__x._M_root() == 0) { 329 _M_root() = 0; 330 _M_leftmost() = &this->_M_header._M_data; 331 _M_rightmost() = &this->_M_header._M_data; 332 } 333 else { 334 _M_root() = _M_copy(__x._M_root(), &this->_M_header._M_data); 335 _M_leftmost() = _S_minimum(_M_root()); 336 _M_rightmost() = _S_maximum(_M_root()); 337 _M_node_count = __x._M_node_count; 338 } 339 } 340 return *this; 341 } 342 343 // CRP 7/10/00 inserted argument __on_right, which is another hint (meant to 344 // act like __on_left and ignore a portion of the if conditions -- specify 345 // __on_right != 0 to bypass comparison as false or __on_left != 0 to bypass 346 // comparison as true) 347 template <class _Key, class _Compare, 348 class _Value, class _KeyOfValue, class _Traits, class _Alloc> 349 __iterator__ 350 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::_M_insert(_Rb_tree_node_base * __parent, 351 const _Value& __val, 352 _Rb_tree_node_base * __on_left, 353 _Rb_tree_node_base * __on_right) { 354 // We do not create the node here as, depending on tests, we might call 355 // _M_key_compare that can throw an exception. 356 _Base_ptr __new_node; 357 358 if ( __parent == &this->_M_header._M_data ) { 359 __new_node = _M_create_node(__val); 360 _S_left(__parent) = __new_node; // also makes _M_leftmost() = __new_node 361 _M_root() = __new_node; 362 _M_rightmost() = __new_node; 363 } 364 else if ( __on_right == 0 && // If __on_right != 0, the remainder fails to false 365 ( __on_left != 0 || // If __on_left != 0, the remainder succeeds to true 366 _M_key_compare( _KeyOfValue()(__val), _S_key(__parent) ) ) ) { 367 __new_node = _M_create_node(__val); 368 _S_left(__parent) = __new_node; 369 if (__parent == _M_leftmost()) 370 _M_leftmost() = __new_node; // maintain _M_leftmost() pointing to min node 371 } 372 else { 373 __new_node = _M_create_node(__val); 374 _S_right(__parent) = __new_node; 375 if (__parent == _M_rightmost()) 376 _M_rightmost() = __new_node; // maintain _M_rightmost() pointing to max node 377 } 378 _S_parent(__new_node) = __parent; 379 _Rb_global_inst::_Rebalance(__new_node, this->_M_header._M_data._M_parent); 380 ++_M_node_count; 381 return iterator(__new_node); 382 } 383 384 template <class _Key, class _Compare, 385 class _Value, class _KeyOfValue, class _Traits, class _Alloc> 386 __iterator__ 387 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::insert_equal(const _Value& __val) { 388 _Base_ptr __y = &this->_M_header._M_data; 389 _Base_ptr __x = _M_root(); 390 while (__x != 0) { 391 __y = __x; 392 if (_M_key_compare(_KeyOfValue()(__val), _S_key(__x))) { 393 __x = _S_left(__x); 394 } 395 else 396 __x = _S_right(__x); 397 } 398 return _M_insert(__y, __val, __x); 399 } 400 401 402 template <class _Key, class _Compare, 403 class _Value, class _KeyOfValue, class _Traits, class _Alloc> 404 pair<__iterator__, bool> 405 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::insert_unique(const _Value& __val) { 406 _Base_ptr __y = &this->_M_header._M_data; 407 _Base_ptr __x = _M_root(); 408 bool __comp = true; 409 while (__x != 0) { 410 __y = __x; 411 __comp = _M_key_compare(_KeyOfValue()(__val), _S_key(__x)); 412 __x = __comp ? _S_left(__x) : _S_right(__x); 413 } 414 iterator __j = iterator(__y); 415 if (__comp) { 416 if (__j == begin()) 417 return pair<iterator,bool>(_M_insert(__y, __val, /* __x*/ __y), true); 418 else 419 --__j; 420 } 421 if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__val))) { 422 return pair<iterator,bool>(_M_insert(__y, __val, __x), true); 423 } 424 return pair<iterator,bool>(__j, false); 425 } 426 427 // Modifications CRP 7/10/00 as noted to improve conformance and 428 // efficiency. 429 template <class _Key, class _Compare, 430 class _Value, class _KeyOfValue, class _Traits, class _Alloc> 431 __iterator__ 432 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::insert_unique(iterator __position, 433 const _Value& __val) { 434 if (__position._M_node == this->_M_header._M_data._M_left) { // begin() 435 436 // if the container is empty, fall back on insert_unique. 437 if (empty()) 438 return insert_unique(__val).first; 439 440 if (_M_key_compare(_KeyOfValue()(__val), _S_key(__position._M_node))) { 441 return _M_insert(__position._M_node, __val, __position._M_node); 442 } 443 // first argument just needs to be non-null 444 else { 445 bool __comp_pos_v = _M_key_compare( _S_key(__position._M_node), _KeyOfValue()(__val) ); 446 447 if (__comp_pos_v == false) // compare > and compare < both false so compare equal 448 return __position; 449 //Below __comp_pos_v == true 450 451 // Standard-conformance - does the insertion point fall immediately AFTER 452 // the hint? 453 iterator __after = __position; 454 ++__after; 455 456 // Check for only one member -- in that case, __position points to itself, 457 // and attempting to increment will cause an infinite loop. 458 if (__after._M_node == &this->_M_header._M_data) 459 // Check guarantees exactly one member, so comparison was already 460 // performed and we know the result; skip repeating it in _M_insert 461 // by specifying a non-zero fourth argument. 462 return _M_insert(__position._M_node, __val, 0, __position._M_node); 463 464 // All other cases: 465 466 // Optimization to catch insert-equivalent -- save comparison results, 467 // and we get this for free. 468 if (_M_key_compare( _KeyOfValue()(__val), _S_key(__after._M_node) )) { 469 if (_S_right(__position._M_node) == 0) 470 return _M_insert(__position._M_node, __val, 0, __position._M_node); 471 else 472 return _M_insert(__after._M_node, __val, __after._M_node); 473 } 474 else { 475 return insert_unique(__val).first; 476 } 477 } 478 } 479 else if (__position._M_node == &this->_M_header._M_data) { // end() 480 if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__val))) { 481 // pass along to _M_insert that it can skip comparing 482 // v, Key ; since compare Key, v was true, compare v, Key must be false. 483 return _M_insert(_M_rightmost(), __val, 0, __position._M_node); // Last argument only needs to be non-null 484 } 485 else 486 return insert_unique(__val).first; 487 } 488 else { 489 iterator __before = __position; 490 --__before; 491 492 bool __comp_v_pos = _M_key_compare(_KeyOfValue()(__val), _S_key(__position._M_node)); 493 494 if (__comp_v_pos 495 && _M_key_compare( _S_key(__before._M_node), _KeyOfValue()(__val) )) { 496 497 if (_S_right(__before._M_node) == 0) 498 return _M_insert(__before._M_node, __val, 0, __before._M_node); // Last argument only needs to be non-null 499 else 500 return _M_insert(__position._M_node, __val, __position._M_node); 501 // first argument just needs to be non-null 502 } 503 else { 504 // Does the insertion point fall immediately AFTER the hint? 505 iterator __after = __position; 506 ++__after; 507 // Optimization to catch equivalent cases and avoid unnecessary comparisons 508 bool __comp_pos_v = !__comp_v_pos; // Stored this result earlier 509 // If the earlier comparison was true, this comparison doesn't need to be 510 // performed because it must be false. However, if the earlier comparison 511 // was false, we need to perform this one because in the equal case, both will 512 // be false. 513 if (!__comp_v_pos) { 514 __comp_pos_v = _M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__val)); 515 } 516 517 if ( (!__comp_v_pos) // comp_v_pos true implies comp_v_pos false 518 && __comp_pos_v 519 && (__after._M_node == &this->_M_header._M_data || 520 _M_key_compare( _KeyOfValue()(__val), _S_key(__after._M_node) ))) { 521 if (_S_right(__position._M_node) == 0) 522 return _M_insert(__position._M_node, __val, 0, __position._M_node); 523 else 524 return _M_insert(__after._M_node, __val, __after._M_node); 525 } else { 526 // Test for equivalent case 527 if (__comp_v_pos == __comp_pos_v) 528 return __position; 529 else 530 return insert_unique(__val).first; 531 } 532 } 533 } 534 } 535 536 template <class _Key, class _Compare, 537 class _Value, class _KeyOfValue, class _Traits, class _Alloc> 538 __iterator__ 539 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::insert_equal(iterator __position, 540 const _Value& __val) { 541 if (__position._M_node == this->_M_header._M_data._M_left) { // begin() 542 543 // Check for zero members 544 if (size() <= 0) 545 return insert_equal(__val); 546 547 if (!_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__val))) 548 return _M_insert(__position._M_node, __val, __position._M_node); 549 else { 550 // Check for only one member 551 if (__position._M_node->_M_left == __position._M_node) 552 // Unlike insert_unique, can't avoid doing a comparison here. 553 return _M_insert(__position._M_node, __val); 554 555 // All other cases: 556 // Standard-conformance - does the insertion point fall immediately AFTER 557 // the hint? 558 iterator __after = __position; 559 ++__after; 560 561 // Already know that compare(pos, v) must be true! 562 // Therefore, we want to know if compare(after, v) is false. 563 // (i.e., we now pos < v, now we want to know if v <= after) 564 // If not, invalid hint. 565 if ( __after._M_node == &this->_M_header._M_data || 566 !_M_key_compare( _S_key(__after._M_node), _KeyOfValue()(__val) ) ) { 567 if (_S_right(__position._M_node) == 0) 568 return _M_insert(__position._M_node, __val, 0, __position._M_node); 569 else 570 return _M_insert(__after._M_node, __val, __after._M_node); 571 } 572 else { // Invalid hint 573 return insert_equal(__val); 574 } 575 } 576 } 577 else if (__position._M_node == &this->_M_header._M_data) { // end() 578 if (!_M_key_compare(_KeyOfValue()(__val), _S_key(_M_rightmost()))) 579 return _M_insert(_M_rightmost(), __val, 0, __position._M_node); // Last argument only needs to be non-null 580 else { 581 return insert_equal(__val); 582 } 583 } 584 else { 585 iterator __before = __position; 586 --__before; 587 // store the result of the comparison between pos and v so 588 // that we don't have to do it again later. Note that this reverses the shortcut 589 // on the if, possibly harming efficiency in comparisons; I think the harm will 590 // be negligible, and to do what I want to do (save the result of a comparison so 591 // that it can be re-used) there is no alternative. Test here is for before <= v <= pos. 592 bool __comp_pos_v = _M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__val)); 593 if (!__comp_pos_v && 594 !_M_key_compare(_KeyOfValue()(__val), _S_key(__before._M_node))) { 595 if (_S_right(__before._M_node) == 0) 596 return _M_insert(__before._M_node, __val, 0, __before._M_node); // Last argument only needs to be non-null 597 else 598 return _M_insert(__position._M_node, __val, __position._M_node); 599 } 600 else { 601 // Does the insertion point fall immediately AFTER the hint? 602 // Test for pos < v <= after 603 iterator __after = __position; 604 ++__after; 605 606 if (__comp_pos_v && 607 ( __after._M_node == &this->_M_header._M_data || 608 !_M_key_compare( _S_key(__after._M_node), _KeyOfValue()(__val) ) ) ) { 609 if (_S_right(__position._M_node) == 0) 610 return _M_insert(__position._M_node, __val, 0, __position._M_node); 611 else 612 return _M_insert(__after._M_node, __val, __after._M_node); 613 } 614 else { // Invalid hint 615 return insert_equal(__val); 616 } 617 } 618 } 619 } 620 621 template <class _Key, class _Compare, 622 class _Value, class _KeyOfValue, class _Traits, class _Alloc> 623 _Rb_tree_node_base* 624 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::_M_copy(_Rb_tree_node_base* __x, 625 _Rb_tree_node_base* __p) { 626 // structural copy. __x and __p must be non-null. 627 _Base_ptr __top = _M_clone_node(__x); 628 _S_parent(__top) = __p; 629 630 _STLP_TRY { 631 if (_S_right(__x)) 632 _S_right(__top) = _M_copy(_S_right(__x), __top); 633 __p = __top; 634 __x = _S_left(__x); 635 636 while (__x != 0) { 637 _Base_ptr __y = _M_clone_node(__x); 638 _S_left(__p) = __y; 639 _S_parent(__y) = __p; 640 if (_S_right(__x)) 641 _S_right(__y) = _M_copy(_S_right(__x), __y); 642 __p = __y; 643 __x = _S_left(__x); 644 } 645 } 646 _STLP_UNWIND(_M_erase(__top)) 647 648 return __top; 649 } 650 651 // this has to stay out-of-line : it's recursive 652 template <class _Key, class _Compare, 653 class _Value, class _KeyOfValue, class _Traits, class _Alloc> 654 void 655 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc>::_M_erase(_Rb_tree_node_base *__x) { 656 // erase without rebalancing 657 while (__x != 0) { 658 _M_erase(_S_right(__x)); 659 _Base_ptr __y = _S_left(__x); 660 _STLP_STD::_Destroy(&_S_value(__x)); 661 this->_M_header.deallocate(__STATIC_CAST(_Link_type, __x),1); 662 __x = __y; 663 } 664 } 665 666 #if defined (_STLP_DEBUG) 667 inline int 668 __black_count(_Rb_tree_node_base* __node, _Rb_tree_node_base* __root) { 669 if (__node == 0) 670 return 0; 671 else { 672 int __bc = __node->_M_color == _S_rb_tree_black ? 1 : 0; 673 if (__node == __root) 674 return __bc; 675 else 676 return __bc + __black_count(__node->_M_parent, __root); 677 } 678 } 679 680 template <class _Key, class _Compare, 681 class _Value, class _KeyOfValue, class _Traits, class _Alloc> 682 bool _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc>::__rb_verify() const { 683 if (_M_node_count == 0 || begin() == end()) 684 return ((_M_node_count == 0) && 685 (begin() == end()) && 686 (this->_M_header._M_data._M_left == &this->_M_header._M_data) && 687 (this->_M_header._M_data._M_right == &this->_M_header._M_data)); 688 689 int __len = __black_count(_M_leftmost(), _M_root()); 690 for (const_iterator __it = begin(); __it != end(); ++__it) { 691 _Base_ptr __x = __it._M_node; 692 _Base_ptr __L = _S_left(__x); 693 _Base_ptr __R = _S_right(__x); 694 695 if (__x->_M_color == _S_rb_tree_red) 696 if ((__L && __L->_M_color == _S_rb_tree_red) || 697 (__R && __R->_M_color == _S_rb_tree_red)) 698 return false; 699 700 if (__L && _M_key_compare(_S_key(__x), _S_key(__L))) 701 return false; 702 if (__R && _M_key_compare(_S_key(__R), _S_key(__x))) 703 return false; 704 705 if (!__L && !__R && __black_count(__x, _M_root()) != __len) 706 return false; 707 } 708 709 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) 710 return false; 711 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) 712 return false; 713 714 return true; 715 } 716 #endif /* _STLP_DEBUG */ 717 718 _STLP_MOVE_TO_STD_NAMESPACE 719 _STLP_END_NAMESPACE 720 721 #undef _Rb_tree 722 #undef __iterator__ 723 #undef iterator 724 #undef __size_type__ 725 726 #endif /* _STLP_TREE_C */ 727 728 // Local Variables: 729 // mode:C++ 730 // End: 731
