libstdc++-v3/src/c++98/tree.cc - gcc - Git at Google

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

 // Copyright (C) 2003-2022 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

   static _Rb_tree_node_base*
   local_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;
   }

   _Rb_tree_node_base*
   _Rb_tree_increment(_Rb_tree_node_base* __x) throw ()
   {
     return local_Rb_tree_increment(__x);
   }

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

   static _Rb_tree_node_base*
   local_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;
   }

   _Rb_tree_node_base*
   _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ()
   {
     return local_Rb_tree_decrement(__x);
   }

   const _Rb_tree_node_base*
   _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ()
   {
     return local_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;
   }

 #if !_GLIBCXX_INLINE_VERSION
   /* 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); }
 #endif

   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;
   }

 #if !_GLIBCXX_INLINE_VERSION
   /* 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); }
 #endif

   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
	// RB tree utilities implementation -- C++ --

	// Copyright (C) 2003-2022 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

	static _Rb_tree_node_base*
	local_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;
	}

	_Rb_tree_node_base*
	_Rb_tree_increment(_Rb_tree_node_base* __x) throw ()
	{
	return local_Rb_tree_increment(__x);
	}

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

	static _Rb_tree_node_base*
	local_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;
	}

	_Rb_tree_node_base*
	_Rb_tree_decrement(_Rb_tree_node_base* __x) throw ()
	{
	return local_Rb_tree_decrement(__x);
	}

	const _Rb_tree_node_base*
	_Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ()
	{
	return local_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;
	}

	#if !_GLIBCXX_INLINE_VERSION
	/* 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); }
	#endif

	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;
	}

	#if !_GLIBCXX_INLINE_VERSION
	/* 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); }
	#endif

	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