[thirdparty/gcc.git] / libstdc++-v3 / src / tree.cc

// RB tree utilities implementation -*- C++ -*-

// Copyright (C) 2003, 2005, 2009 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/*
 *
 * Copyright (c) 1996,1997
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Silicon Graphics makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 */

#include <bits/stl_tree.h>

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

  _Rb_tree_node_base*
  _Rb_tree_increment(_Rb_tree_node_base* __x) throw ()
  {
    if (__x->_M_right != 0) 
      {
        __x = __x->_M_right;
        while (__x->_M_left != 0)
          __x = __x->_M_left;
      }
    else 
      {
        _Rb_tree_node_base* __y = __x->_M_parent;
        while (__x == __y->_M_right) 
          {
            __x = __y;
            __y = __y->_M_parent;
          }
        if (__x->_M_right != __y)
          __x = __y;
      }
    return __x;
  }

  const _Rb_tree_node_base*
  _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ()
  {
    return _Rb_tree_increment(const_cast<_Rb_tree_node_base*>(__x));
  }

  _Rb_tree_node_base*
  _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ()
  {
    if (__x->_M_color == _S_red 
        && __x->_M_parent->_M_parent == __x)
      __x = __x->_M_right;
    else if (__x->_M_left != 0) 
      {
        _Rb_tree_node_base* __y = __x->_M_left;
        while (__y->_M_right != 0)
          __y = __y->_M_right;
        __x = __y;
      }
    else 
      {
        _Rb_tree_node_base* __y = __x->_M_parent;
        while (__x == __y->_M_left) 
          {
            __x = __y;
            __y = __y->_M_parent;
          }
        __x = __y;
      }
    return __x;
  }

  const _Rb_tree_node_base*
  _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ()
  {
    return _Rb_tree_decrement(const_cast<_Rb_tree_node_base*>(__x));
  }

  static void 
  local_Rb_tree_rotate_left(_Rb_tree_node_base* const __x, 
		             _Rb_tree_node_base*& __root)
  {
    _Rb_tree_node_base* const __y = __x->_M_right;

    __x->_M_right = __y->_M_left;
    if (__y->_M_left !=0)
      __y->_M_left->_M_parent = __x;
    __y->_M_parent = __x->_M_parent;
    
    if (__x == __root)
      __root = __y;
    else if (__x == __x->_M_parent->_M_left)
      __x->_M_parent->_M_left = __y;
    else
      __x->_M_parent->_M_right = __y;
    __y->_M_left = __x;
    __x->_M_parent = __y;
  }

  /* Static keyword was missing on _Rb_tree_rotate_left.
     Export the symbol for backward compatibility until
     next ABI change.  */
  void 
  _Rb_tree_rotate_left(_Rb_tree_node_base* const __x, 
		       _Rb_tree_node_base*& __root)
  {
    local_Rb_tree_rotate_left (__x, __root);
  }

  static void 
  local_Rb_tree_rotate_right(_Rb_tree_node_base* const __x, 
			     _Rb_tree_node_base*& __root)
  {
    _Rb_tree_node_base* const __y = __x->_M_left;

    __x->_M_left = __y->_M_right;
    if (__y->_M_right != 0)
      __y->_M_right->_M_parent = __x;
    __y->_M_parent = __x->_M_parent;

    if (__x == __root)
      __root = __y;
    else if (__x == __x->_M_parent->_M_right)
      __x->_M_parent->_M_right = __y;
    else
      __x->_M_parent->_M_left = __y;
    __y->_M_right = __x;
    __x->_M_parent = __y;
  }

  /* Static keyword was missing on _Rb_tree_rotate_right
     Export the symbol for backward compatibility until
     next ABI change.  */
  void 
  _Rb_tree_rotate_right(_Rb_tree_node_base* const __x, 
			_Rb_tree_node_base*& __root)
  {
    local_Rb_tree_rotate_right (__x, __root);
  }

  void 
  _Rb_tree_insert_and_rebalance(const bool          __insert_left,
                                _Rb_tree_node_base* __x,
                                _Rb_tree_node_base* __p,
                                _Rb_tree_node_base& __header) throw ()
  {
    _Rb_tree_node_base *& __root = __header._M_parent;

    // Initialize fields in new node to insert.
    __x->_M_parent = __p;
    __x->_M_left = 0;
    __x->_M_right = 0;
    __x->_M_color = _S_red;

    // Insert.
    // Make new node child of parent and maintain root, leftmost and
    // rightmost nodes.
    // N.B. First node is always inserted left.
    if (__insert_left)
      {
        __p->_M_left = __x; // also makes leftmost = __x when __p == &__header

        if (__p == &__header)
        {
            __header._M_parent = __x;
            __header._M_right = __x;
        }
        else if (__p == __header._M_left)
          __header._M_left = __x; // maintain leftmost pointing to min node
      }
    else
      {
        __p->_M_right = __x;

        if (__p == __header._M_right)
          __header._M_right = __x; // maintain rightmost pointing to max node
      }
    // Rebalance.
    while (__x != __root 
	   && __x->_M_parent->_M_color == _S_red) 
      {
	_Rb_tree_node_base* const __xpp = __x->_M_parent->_M_parent;

	if (__x->_M_parent == __xpp->_M_left) 
	  {
	    _Rb_tree_node_base* const __y = __xpp->_M_right;
	    if (__y && __y->_M_color == _S_red) 
	      {
		__x->_M_parent->_M_color = _S_black;
		__y->_M_color = _S_black;
		__xpp->_M_color = _S_red;
		__x = __xpp;
	      }
	    else 
	      {
		if (__x == __x->_M_parent->_M_right) 
		  {
		    __x = __x->_M_parent;
		    local_Rb_tree_rotate_left(__x, __root);
		  }
		__x->_M_parent->_M_color = _S_black;
		__xpp->_M_color = _S_red;
		local_Rb_tree_rotate_right(__xpp, __root);
	      }
	  }
	else 
	  {
	    _Rb_tree_node_base* const __y = __xpp->_M_left;
	    if (__y && __y->_M_color == _S_red) 
	      {
		__x->_M_parent->_M_color = _S_black;
		__y->_M_color = _S_black;
		__xpp->_M_color = _S_red;
		__x = __xpp;
	      }
	    else 
	      {
		if (__x == __x->_M_parent->_M_left) 
		  {
		    __x = __x->_M_parent;
		    local_Rb_tree_rotate_right(__x, __root);
		  }
		__x->_M_parent->_M_color = _S_black;
		__xpp->_M_color = _S_red;
		local_Rb_tree_rotate_left(__xpp, __root);
	      }
	  }
      }
    __root->_M_color = _S_black;
  }

  _Rb_tree_node_base*
  _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z, 
			       _Rb_tree_node_base& __header) throw ()
  {
    _Rb_tree_node_base *& __root = __header._M_parent;
    _Rb_tree_node_base *& __leftmost = __header._M_left;
    _Rb_tree_node_base *& __rightmost = __header._M_right;
    _Rb_tree_node_base* __y = __z;
    _Rb_tree_node_base* __x = 0;
    _Rb_tree_node_base* __x_parent = 0;

    if (__y->_M_left == 0)     // __z has at most one non-null child. y == z.
      __x = __y->_M_right;     // __x might be null.
    else
      if (__y->_M_right == 0)  // __z has exactly one non-null child. y == z.
	__x = __y->_M_left;    // __x is not null.
      else 
	{
	  // __z has two non-null children.  Set __y to
	  __y = __y->_M_right;   //   __z's successor.  __x might be null.
	  while (__y->_M_left != 0)
	    __y = __y->_M_left;
	  __x = __y->_M_right;
	}
    if (__y != __z) 
      {
	// relink y in place of z.  y is z's successor
	__z->_M_left->_M_parent = __y; 
	__y->_M_left = __z->_M_left;
	if (__y != __z->_M_right) 
	  {
	    __x_parent = __y->_M_parent;
	    if (__x) __x->_M_parent = __y->_M_parent;
	    __y->_M_parent->_M_left = __x;   // __y must be a child of _M_left
	    __y->_M_right = __z->_M_right;
	    __z->_M_right->_M_parent = __y;
	  }
	else
	  __x_parent = __y;  
	if (__root == __z)
	  __root = __y;
	else if (__z->_M_parent->_M_left == __z)
	  __z->_M_parent->_M_left = __y;
	else 
	  __z->_M_parent->_M_right = __y;
	__y->_M_parent = __z->_M_parent;
	std::swap(__y->_M_color, __z->_M_color);
	__y = __z;
	// __y now points to node to be actually deleted
      }
    else 
      {                        // __y == __z
	__x_parent = __y->_M_parent;
	if (__x) 
	  __x->_M_parent = __y->_M_parent;   
	if (__root == __z)
	  __root = __x;
	else 
	  if (__z->_M_parent->_M_left == __z)
	    __z->_M_parent->_M_left = __x;
	  else
	    __z->_M_parent->_M_right = __x;
	if (__leftmost == __z) 
	  {
	    if (__z->_M_right == 0)        // __z->_M_left must be null also
	      __leftmost = __z->_M_parent;
	    // makes __leftmost == _M_header if __z == __root
	    else
	      __leftmost = _Rb_tree_node_base::_S_minimum(__x);
	  }
	if (__rightmost == __z)  
	  {
	    if (__z->_M_left == 0)         // __z->_M_right must be null also
	      __rightmost = __z->_M_parent;  
	    // makes __rightmost == _M_header if __z == __root
	    else                      // __x == __z->_M_left
	      __rightmost = _Rb_tree_node_base::_S_maximum(__x);
	  }
      }
    if (__y->_M_color != _S_red) 
      { 
	while (__x != __root && (__x == 0 || __x->_M_color == _S_black))
	  if (__x == __x_parent->_M_left) 
	    {
	      _Rb_tree_node_base* __w = __x_parent->_M_right;
	      if (__w->_M_color == _S_red) 
		{
		  __w->_M_color = _S_black;
		  __x_parent->_M_color = _S_red;
		  local_Rb_tree_rotate_left(__x_parent, __root);
		  __w = __x_parent->_M_right;
		}
	      if ((__w->_M_left == 0 || 
		   __w->_M_left->_M_color == _S_black) &&
		  (__w->_M_right == 0 || 
		   __w->_M_right->_M_color == _S_black)) 
		{
		  __w->_M_color = _S_red;
		  __x = __x_parent;
		  __x_parent = __x_parent->_M_parent;
		} 
	      else 
		{
		  if (__w->_M_right == 0 
		      || __w->_M_right->_M_color == _S_black) 
		    {
		      __w->_M_left->_M_color = _S_black;
		      __w->_M_color = _S_red;
		      local_Rb_tree_rotate_right(__w, __root);
		      __w = __x_parent->_M_right;
		    }
		  __w->_M_color = __x_parent->_M_color;
		  __x_parent->_M_color = _S_black;
		  if (__w->_M_right) 
		    __w->_M_right->_M_color = _S_black;
		  local_Rb_tree_rotate_left(__x_parent, __root);
		  break;
		}
	    } 
	  else 
	    {   
	      // same as above, with _M_right <-> _M_left.
	      _Rb_tree_node_base* __w = __x_parent->_M_left;
	      if (__w->_M_color == _S_red) 
		{
		  __w->_M_color = _S_black;
		  __x_parent->_M_color = _S_red;
		  local_Rb_tree_rotate_right(__x_parent, __root);
		  __w = __x_parent->_M_left;
		}
	      if ((__w->_M_right == 0 || 
		   __w->_M_right->_M_color == _S_black) &&
		  (__w->_M_left == 0 || 
		   __w->_M_left->_M_color == _S_black)) 
		{
		  __w->_M_color = _S_red;
		  __x = __x_parent;
		  __x_parent = __x_parent->_M_parent;
		} 
	      else 
		{
		  if (__w->_M_left == 0 || __w->_M_left->_M_color == _S_black) 
		    {
		      __w->_M_right->_M_color = _S_black;
		      __w->_M_color = _S_red;
		      local_Rb_tree_rotate_left(__w, __root);
		      __w = __x_parent->_M_left;
		    }
		  __w->_M_color = __x_parent->_M_color;
		  __x_parent->_M_color = _S_black;
		  if (__w->_M_left) 
		    __w->_M_left->_M_color = _S_black;
		  local_Rb_tree_rotate_right(__x_parent, __root);
		  break;
		}
	    }
	if (__x) __x->_M_color = _S_black;
      }
    return __y;
  }

  unsigned int
  _Rb_tree_black_count(const _Rb_tree_node_base* __node,
                       const _Rb_tree_node_base* __root) throw ()
  {
    if (__node == 0)
      return 0;
    unsigned int __sum = 0;
    do 
      {
	if (__node->_M_color == _S_black) 
	  ++__sum;
	if (__node == __root) 
	  break;
	__node = __node->_M_parent;
      } 
    while (1);
    return __sum;
  }

_GLIBCXX_END_NAMESPACE_VERSION
} // namespace
Commit	Line	Data
ca1c7011 GB	1	// RB tree utilities implementation -- C++ --
ca1c7011 GB	2
748086b7	3	// Copyright (C) 2003, 2005, 2009 Free Software Foundation, Inc.
ca1c7011 GB	4	//
	5	// This file is part of the GNU ISO C++ Library. This library is free
	6	// software; you can redistribute it and/or modify it under the
	7	// terms of the GNU General Public License as published by the
748086b7	8	// Free Software Foundation; either version 3, or (at your option)
ca1c7011 GB	9	// any later version.
	10
	11	// This library is distributed in the hope that it will be useful,
	12	// but WITHOUT ANY WARRANTY; without even the implied warranty of
	13	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	14	// GNU General Public License for more details.
	15
748086b7 JJ	16	// Under Section 7 of GPL version 3, you are granted additional
	17	// permissions described in the GCC Runtime Library Exception, version
	18	// 3.1, as published by the Free Software Foundation.
ca1c7011	19
748086b7 JJ	20	// You should have received a copy of the GNU General Public License and
	21	// a copy of the GCC Runtime Library Exception along with this program;
	22	// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
	23	// <http://www.gnu.org/licenses/>.
ca1c7011 GB	24
	25	/*
	26	*
	27	* Copyright (c) 1996,1997
	28	* Silicon Graphics Computer Systems, Inc.
	29	*
	30	* Permission to use, copy, modify, distribute and sell this software
	31	* and its documentation for any purpose is hereby granted without fee,
	32	* provided that the above copyright notice appear in all copies and
	33	* that both that copyright notice and this permission notice appear
	34	* in supporting documentation. Silicon Graphics makes no
	35	* representations about the suitability of this software for any
	36	* purpose. It is provided "as is" without express or implied warranty.
	37	*
	38	*
	39	* Copyright (c) 1994
	40	* Hewlett-Packard Company
	41	*
	42	* Permission to use, copy, modify, distribute and sell this software
	43	* and its documentation for any purpose is hereby granted without fee,
	44	* provided that the above copyright notice appear in all copies and
	45	* that both that copyright notice and this permission notice appear
	46	* in supporting documentation. Hewlett-Packard Company makes no
	47	* representations about the suitability of this software for any
	48	* purpose. It is provided "as is" without express or implied warranty.
	49	*
	50	*
	51	*/
	52
	53	#include <bits/stl_tree.h>
	54
12ffa228 BK	55	namespace std _GLIBCXX_VISIBILITY(default)
	56	{
	57	_GLIBCXX_BEGIN_NAMESPACE_VERSION
3cbc7af0	58
b4c70e89	59	_Rb_tree_node_base*
1cf1c842	60	_Rb_tree_increment(_Rb_tree_node_base* __x) throw ()
ca1c7011	61	{
b4c70e89	62	if (__x->_M_right != 0)
ca1c7011	63	{
b4c70e89 GB	64	__x = __x->_M_right;
	65	while (__x->_M_left != 0)
	66	__x = __x->_M_left;
ca1c7011 GB	67	}
	68	else
	69	{
b4c70e89 GB	70	_Rb_tree_node_base* __y = __x->_M_parent;
b4c70e89 GB	71	while (__x == __y->_M_right)
ca1c7011	72	{
b4c70e89	73	__x = __y;
ca1c7011 GB	74	__y = __y->_M_parent;
ca1c7011 GB	75	}
b4c70e89 GB	76	if (__x->_M_right != __y)
b4c70e89 GB	77	__x = __y;
ca1c7011	78	}
b4c70e89	79	return __x;
ca1c7011 GB	80	}
ca1c7011 GB	81
e135a038	82	const _Rb_tree_node_base*
1cf1c842	83	_Rb_tree_increment(const _Rb_tree_node_base* __x) throw ()
e135a038 BK	84	{
	85	return _Rb_tree_increment(const_cast<_Rb_tree_node_base*>(__x));
	86	}
	87
b4c70e89	88	_Rb_tree_node_base*
1cf1c842	89	_Rb_tree_decrement(_Rb_tree_node_base* __x) throw ()
ca1c7011	90	{
b4c70e89 GB	91	if (__x->_M_color == _S_red
	92	&& __x->_M_parent->_M_parent == __x)
	93	__x = __x->_M_right;
	94	else if (__x->_M_left != 0)
ca1c7011	95	{
b4c70e89	96	_Rb_tree_node_base* __y = __x->_M_left;
ca1c7011 GB	97	while (__y->_M_right != 0)
ca1c7011 GB	98	__y = __y->_M_right;
b4c70e89	99	__x = __y;
ca1c7011 GB	100	}
	101	else
	102	{
b4c70e89 GB	103	_Rb_tree_node_base* __y = __x->_M_parent;
b4c70e89 GB	104	while (__x == __y->_M_left)
ca1c7011	105	{
b4c70e89	106	__x = __y;
ca1c7011 GB	107	__y = __y->_M_parent;
ca1c7011 GB	108	}
b4c70e89	109	__x = __y;
ca1c7011	110	}
b4c70e89	111	return __x;
ca1c7011 GB	112	}
ca1c7011 GB	113
e135a038	114	const _Rb_tree_node_base*
1cf1c842	115	_Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ()
e135a038 BK	116	{
	117	return _Rb_tree_decrement(const_cast<_Rb_tree_node_base*>(__x));
	118	}
	119
1cf1c842 JH	120	static void
	121	local_Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
	122	_Rb_tree_node_base*& __root)
ca1c7011 GB	123	{
	124	_Rb_tree_node_base* const __y = __x->_M_right;
	125
	126	__x->_M_right = __y->_M_left;
	127	if (__y->_M_left !=0)
	128	__y->_M_left->_M_parent = __x;
	129	__y->_M_parent = __x->_M_parent;
	130
	131	if (__x == __root)
	132	__root = __y;
	133	else if (__x == __x->_M_parent->_M_left)
	134	__x->_M_parent->_M_left = __y;
	135	else
	136	__x->_M_parent->_M_right = __y;
	137	__y->_M_left = __x;
	138	__x->_M_parent = __y;
	139	}
	140
1cf1c842 JH	141	/* Static keyword was missing on _Rb_tree_rotate_left.
	142	Export the symbol for backward compatibility until
	143	next ABI change. */
ca1c7011	144	void
1cf1c842 JH	145	_Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
	146	_Rb_tree_node_base*& __root)
	147	{
	148	local_Rb_tree_rotate_left (__x, __root);
	149	}
	150
	151	static void
	152	local_Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
	153	_Rb_tree_node_base*& __root)
ca1c7011 GB	154	{
	155	_Rb_tree_node_base* const __y = __x->_M_left;
	156
	157	__x->_M_left = __y->_M_right;
	158	if (__y->_M_right != 0)
	159	__y->_M_right->_M_parent = __x;
	160	__y->_M_parent = __x->_M_parent;
	161
	162	if (__x == __root)
	163	__root = __y;
	164	else if (__x == __x->_M_parent->_M_right)
	165	__x->_M_parent->_M_right = __y;
	166	else
	167	__x->_M_parent->_M_left = __y;
	168	__y->_M_right = __x;
	169	__x->_M_parent = __y;
	170	}
	171
1cf1c842 JH	172	/* Static keyword was missing on _Rb_tree_rotate_right
	173	Export the symbol for backward compatibility until
	174	next ABI change. */
	175	void
	176	_Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
	177	_Rb_tree_node_base*& __root)
	178	{
	179	local_Rb_tree_rotate_right (__x, __root);
	180	}
	181
ca1c7011	182	void
e135a038 BK	183	_Rb_tree_insert_and_rebalance(const bool __insert_left,
	184	_Rb_tree_node_base* __x,
	185	_Rb_tree_node_base* __p,
1cf1c842	186	_Rb_tree_node_base& __header) throw ()
ca1c7011	187	{
e135a038 BK	188	_Rb_tree_node_base *& __root = __header._M_parent;
	189
	190	// Initialize fields in new node to insert.
	191	__x->_M_parent = __p;
	192	__x->_M_left = 0;
	193	__x->_M_right = 0;
ca1c7011 GB	194	__x->_M_color = _S_red;
ca1c7011 GB	195
e135a038 BK	196	// Insert.
	197	// Make new node child of parent and maintain root, leftmost and
	198	// rightmost nodes.
	199	// N.B. First node is always inserted left.
	200	if (__insert_left)
	201	{
	202	__p->_M_left = __x; // also makes leftmost = __x when __p == &__header
	203
	204	if (__p == &__header)
	205	{
	206	__header._M_parent = __x;
	207	__header._M_right = __x;
	208	}
	209	else if (__p == __header._M_left)
	210	__header._M_left = __x; // maintain leftmost pointing to min node
	211	}
	212	else
	213	{
	214	__p->_M_right = __x;
	215
	216	if (__p == __header._M_right)
	217	__header._M_right = __x; // maintain rightmost pointing to max node
	218	}
	219	// Rebalance.
ca1c7011 GB	220	while (__x != __root
	221	&& __x->_M_parent->_M_color == _S_red)
	222	{
	223	_Rb_tree_node_base* const __xpp = __x->_M_parent->_M_parent;
	224
	225	if (__x->_M_parent == __xpp->_M_left)
	226	{
	227	_Rb_tree_node_base* const __y = __xpp->_M_right;
	228	if (__y && __y->_M_color == _S_red)
	229	{
	230	__x->_M_parent->_M_color = _S_black;
	231	__y->_M_color = _S_black;
	232	__xpp->_M_color = _S_red;
	233	__x = __xpp;
	234	}
	235	else
	236	{
	237	if (__x == __x->_M_parent->_M_right)
	238	{
	239	__x = __x->_M_parent;
1cf1c842	240	local_Rb_tree_rotate_left(__x, __root);
ca1c7011 GB	241	}
	242	__x->_M_parent->_M_color = _S_black;
	243	__xpp->_M_color = _S_red;
1cf1c842	244	local_Rb_tree_rotate_right(__xpp, __root);
ca1c7011 GB	245	}
	246	}
	247	else
	248	{
	249	_Rb_tree_node_base* const __y = __xpp->_M_left;
	250	if (__y && __y->_M_color == _S_red)
	251	{
	252	__x->_M_parent->_M_color = _S_black;
	253	__y->_M_color = _S_black;
	254	__xpp->_M_color = _S_red;
	255	__x = __xpp;
	256	}
	257	else
	258	{
	259	if (__x == __x->_M_parent->_M_left)
	260	{
	261	__x = __x->_M_parent;
1cf1c842	262	local_Rb_tree_rotate_right(__x, __root);
ca1c7011 GB	263	}
	264	__x->_M_parent->_M_color = _S_black;
	265	__xpp->_M_color = _S_red;
1cf1c842	266	local_Rb_tree_rotate_left(__xpp, __root);
ca1c7011 GB	267	}
	268	}
	269	}
	270	__root->_M_color = _S_black;
	271	}
	272
	273	_Rb_tree_node_base*
	274	_Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
1cf1c842	275	_Rb_tree_node_base& __header) throw ()
ca1c7011 GB	276	{
	277	_Rb_tree_node_base *& __root = __header._M_parent;
	278	_Rb_tree_node_base *& __leftmost = __header._M_left;
	279	_Rb_tree_node_base *& __rightmost = __header._M_right;
	280	_Rb_tree_node_base* __y = __z;
	281	_Rb_tree_node_base* __x = 0;
	282	_Rb_tree_node_base* __x_parent = 0;
	283
	284	if (__y->_M_left == 0) // __z has at most one non-null child. y == z.
	285	__x = __y->_M_right; // __x might be null.
	286	else
	287	if (__y->_M_right == 0) // __z has exactly one non-null child. y == z.
	288	__x = __y->_M_left; // __x is not null.
	289	else
	290	{
	291	// __z has two non-null children. Set __y to
	292	__y = __y->_M_right; // __z's successor. __x might be null.
	293	while (__y->_M_left != 0)
	294	__y = __y->_M_left;
	295	__x = __y->_M_right;
	296	}
	297	if (__y != __z)
	298	{
	299	// relink y in place of z. y is z's successor
	300	__z->_M_left->_M_parent = __y;
	301	__y->_M_left = __z->_M_left;
	302	if (__y != __z->_M_right)
	303	{
	304	__x_parent = __y->_M_parent;
	305	if (__x) __x->_M_parent = __y->_M_parent;
	306	__y->_M_parent->_M_left = __x; // __y must be a child of _M_left
	307	__y->_M_right = __z->_M_right;
	308	__z->_M_right->_M_parent = __y;
	309	}
	310	else
	311	__x_parent = __y;
	312	if (__root == __z)
	313	__root = __y;
	314	else if (__z->_M_parent->_M_left == __z)
	315	__z->_M_parent->_M_left = __y;
	316	else
	317	__z->_M_parent->_M_right = __y;
	318	__y->_M_parent = __z->_M_parent;
	319	std::swap(__y->_M_color, __z->_M_color);
	320	__y = __z;
	321	// __y now points to node to be actually deleted
	322	}
	323	else
	324	{ // __y == __z
	325	__x_parent = __y->_M_parent;
	326	if (__x)
	327	__x->_M_parent = __y->_M_parent;
	328	if (__root == __z)
	329	__root = __x;
	330	else
	331	if (__z->_M_parent->_M_left == __z)
	332	__z->_M_parent->_M_left = __x;
	333	else
	334	__z->_M_parent->_M_right = __x;
	335	if (__leftmost == __z)
2a67bec2 ILT	336	{
	337	if (__z->_M_right == 0) // __z->_M_left must be null also
	338	__leftmost = __z->_M_parent;
	339	// makes __leftmost == _M_header if __z == __root
	340	else
	341	__leftmost = _Rb_tree_node_base::_S_minimum(__x);
	342	}
ca1c7011	343	if (__rightmost == __z)
2a67bec2 ILT	344	{
	345	if (__z->_M_left == 0) // __z->_M_right must be null also
	346	__rightmost = __z->_M_parent;
	347	// makes __rightmost == _M_header if __z == __root
	348	else // __x == __z->_M_left
	349	__rightmost = _Rb_tree_node_base::_S_maximum(__x);
	350	}
ca1c7011 GB	351	}
	352	if (__y->_M_color != _S_red)
	353	{
	354	while (__x != __root && (__x == 0 \|\| __x->_M_color == _S_black))
	355	if (__x == __x_parent->_M_left)
	356	{
	357	_Rb_tree_node_base* __w = __x_parent->_M_right;
	358	if (__w->_M_color == _S_red)
	359	{
	360	__w->_M_color = _S_black;
	361	__x_parent->_M_color = _S_red;
1cf1c842	362	local_Rb_tree_rotate_left(__x_parent, __root);
ca1c7011 GB	363	__w = __x_parent->_M_right;
	364	}
	365	if ((__w->_M_left == 0 \|\|
	366	__w->_M_left->_M_color == _S_black) &&
	367	(__w->_M_right == 0 \|\|
	368	__w->_M_right->_M_color == _S_black))
	369	{
	370	__w->_M_color = _S_red;
	371	__x = __x_parent;
	372	__x_parent = __x_parent->_M_parent;
	373	}
	374	else
	375	{
	376	if (__w->_M_right == 0
	377	\|\| __w->_M_right->_M_color == _S_black)
	378	{
	379	__w->_M_left->_M_color = _S_black;
	380	__w->_M_color = _S_red;
1cf1c842	381	local_Rb_tree_rotate_right(__w, __root);
ca1c7011 GB	382	__w = __x_parent->_M_right;
	383	}
	384	__w->_M_color = __x_parent->_M_color;
	385	__x_parent->_M_color = _S_black;
	386	if (__w->_M_right)
	387	__w->_M_right->_M_color = _S_black;
1cf1c842	388	local_Rb_tree_rotate_left(__x_parent, __root);
ca1c7011 GB	389	break;
	390	}
	391	}
	392	else
	393	{
	394	// same as above, with _M_right <-> _M_left.
	395	_Rb_tree_node_base* __w = __x_parent->_M_left;
	396	if (__w->_M_color == _S_red)
	397	{
	398	__w->_M_color = _S_black;
	399	__x_parent->_M_color = _S_red;
1cf1c842	400	local_Rb_tree_rotate_right(__x_parent, __root);
ca1c7011 GB	401	__w = __x_parent->_M_left;
	402	}
	403	if ((__w->_M_right == 0 \|\|
	404	__w->_M_right->_M_color == _S_black) &&
	405	(__w->_M_left == 0 \|\|
	406	__w->_M_left->_M_color == _S_black))
	407	{
	408	__w->_M_color = _S_red;
	409	__x = __x_parent;
	410	__x_parent = __x_parent->_M_parent;
	411	}
	412	else
	413	{
	414	if (__w->_M_left == 0 \|\| __w->_M_left->_M_color == _S_black)
	415	{
	416	__w->_M_right->_M_color = _S_black;
	417	__w->_M_color = _S_red;
1cf1c842	418	local_Rb_tree_rotate_left(__w, __root);
ca1c7011 GB	419	__w = __x_parent->_M_left;
	420	}
	421	__w->_M_color = __x_parent->_M_color;
	422	__x_parent->_M_color = _S_black;
	423	if (__w->_M_left)
	424	__w->_M_left->_M_color = _S_black;
1cf1c842	425	local_Rb_tree_rotate_right(__x_parent, __root);
ca1c7011 GB	426	break;
	427	}
	428	}
	429	if (__x) __x->_M_color = _S_black;
	430	}
	431	return __y;
	432	}
b4c70e89 GB	433
	434	unsigned int
	435	_Rb_tree_black_count(const _Rb_tree_node_base* __node,
1cf1c842	436	const _Rb_tree_node_base* __root) throw ()
b4c70e89 GB	437	{
	438	if (__node == 0)
	439	return 0;
	440	unsigned int __sum = 0;
	441	do
	442	{
	443	if (__node->_M_color == _S_black)
	444	++__sum;
	445	if (__node == __root)
	446	break;
	447	__node = __node->_M_parent;
	448	}
	449	while (1);
	450	return __sum;
	451	}
3cbc7af0	452
12ffa228 BK	453	_GLIBCXX_END_NAMESPACE_VERSION
12ffa228 BK	454	} // namespace