include/c++/stl/stl/_tree.c

   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: