URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libstdc++-v3/] [src/] [c++98/] [tree.cc] - Blame information for rev 749

Go to most recent revision | Details | Compare with Previous | View Log


// RB tree utilities implementation -*- C++ -*-
 
// Copyright (C) 2003, 2005, 2009, 2012 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;
  }
 
  /* 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

Browse

Tools

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libstdc++-v3/] [src/] [c++98/] [tree.cc] - Blame information for rev 749

Line No.	Rev	Author	Line
1	742	jeremybenn	`// RB tree utilities implementation -- C++ --`
2
3			`// Copyright (C) 2003, 2005, 2009, 2012 Free Software Foundation, Inc.`
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`
8			`// Free Software Foundation; either version 3, or (at your option)`
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
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.`
19
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/>.`
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
55			`namespace std _GLIBCXX_VISIBILITY(default)`
56			`{`
57			`_GLIBCXX_BEGIN_NAMESPACE_VERSION`
58
59			`static _Rb_tree_node_base*`
60			`local_Rb_tree_increment(_Rb_tree_node_base* __x) throw ()`
61			`{`
62			`if (__x->_M_right != 0)`
63			`{`
64			`__x = __x->_M_right;`
65			`while (__x->_M_left != 0)`
66			`__x = __x->_M_left;`
67			`}`
68			`else`
69			`{`
70			`_Rb_tree_node_base* __y = __x->_M_parent;`
71			`while (__x == __y->_M_right)`
72			`{`
73			`__x = __y;`
74			`__y = __y->_M_parent;`
75			`}`
76			`if (__x->_M_right != __y)`
77			`__x = __y;`
78			`}`
79			`return __x;`
80			`}`
81
82			`_Rb_tree_node_base*`
83			`_Rb_tree_increment(_Rb_tree_node_base* __x) throw ()`
84			`{`
85			`return local_Rb_tree_increment(__x);`
86			`}`
87
88			`const _Rb_tree_node_base*`
89			`_Rb_tree_increment(const _Rb_tree_node_base* __x) throw ()`
90			`{`
91			`return local_Rb_tree_increment(const_cast<_Rb_tree_node_base*>(__x));`
92			`}`
93
94			`static _Rb_tree_node_base*`
95			`local_Rb_tree_decrement(_Rb_tree_node_base* __x) throw ()`
96			`{`
97			`if (__x->_M_color == _S_red`
98			`&& __x->_M_parent->_M_parent == __x)`
99			`__x = __x->_M_right;`
100			`else if (__x->_M_left != 0)`
101			`{`
102			`_Rb_tree_node_base* __y = __x->_M_left;`
103			`while (__y->_M_right != 0)`
104			`__y = __y->_M_right;`
105			`__x = __y;`
106			`}`
107			`else`
108			`{`
109			`_Rb_tree_node_base* __y = __x->_M_parent;`
110			`while (__x == __y->_M_left)`
111			`{`
112			`__x = __y;`
113			`__y = __y->_M_parent;`
114			`}`
115			`__x = __y;`
116			`}`
117			`return __x;`
118			`}`
119
120			`_Rb_tree_node_base*`
121			`_Rb_tree_decrement(_Rb_tree_node_base* __x) throw ()`
122			`{`
123			`return local_Rb_tree_decrement(__x);`
124			`}`
125
126			`const _Rb_tree_node_base*`
127			`_Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ()`
128			`{`
129			`return local_Rb_tree_decrement(const_cast<_Rb_tree_node_base*>(__x));`
130			`}`
131
132			`static void`
133			`local_Rb_tree_rotate_left(_Rb_tree_node_base* const __x,`
134			`_Rb_tree_node_base*& __root)`
135			`{`
136			`_Rb_tree_node_base* const __y = __x->_M_right;`
137
138			`__x->_M_right = __y->_M_left;`
139			`if (__y->_M_left !=0)`
140			`__y->_M_left->_M_parent = __x;`
141			`__y->_M_parent = __x->_M_parent;`
142
143			`if (__x == __root)`
144			`__root = __y;`
145			`else if (__x == __x->_M_parent->_M_left)`
146			`__x->_M_parent->_M_left = __y;`
147			`else`
148			`__x->_M_parent->_M_right = __y;`
149			`__y->_M_left = __x;`
150			`__x->_M_parent = __y;`
151			`}`
152
153			`/* Static keyword was missing on _Rb_tree_rotate_left.`
154			`Export the symbol for backward compatibility until`
155			`next ABI change. */`
156			`void`
157			`_Rb_tree_rotate_left(_Rb_tree_node_base* const __x,`
158			`_Rb_tree_node_base*& __root)`
159			`{`
160			`local_Rb_tree_rotate_left (__x, __root);`
161			`}`
162
163			`static void`
164			`local_Rb_tree_rotate_right(_Rb_tree_node_base* const __x,`
165			`_Rb_tree_node_base*& __root)`
166			`{`
167			`_Rb_tree_node_base* const __y = __x->_M_left;`
168
169			`__x->_M_left = __y->_M_right;`
170			`if (__y->_M_right != 0)`
171			`__y->_M_right->_M_parent = __x;`
172			`__y->_M_parent = __x->_M_parent;`
173
174			`if (__x == __root)`
175			`__root = __y;`
176			`else if (__x == __x->_M_parent->_M_right)`
177			`__x->_M_parent->_M_right = __y;`
178			`else`
179			`__x->_M_parent->_M_left = __y;`
180			`__y->_M_right = __x;`
181			`__x->_M_parent = __y;`
182			`}`
183
184			`/* Static keyword was missing on _Rb_tree_rotate_right`
185			`Export the symbol for backward compatibility until`
186			`next ABI change. */`
187			`void`
188			`_Rb_tree_rotate_right(_Rb_tree_node_base* const __x,`
189			`_Rb_tree_node_base*& __root)`
190			`{`
191			`local_Rb_tree_rotate_right (__x, __root);`
192			`}`
193
194			`void`
195			`_Rb_tree_insert_and_rebalance(const bool __insert_left,`
196			`_Rb_tree_node_base* __x,`
197			`_Rb_tree_node_base* __p,`
198			`_Rb_tree_node_base& __header) throw ()`
199			`{`
200			`_Rb_tree_node_base *& __root = __header._M_parent;`
201
202			`// Initialize fields in new node to insert.`
203			`__x->_M_parent = __p;`
204			`__x->_M_left = 0;`
205			`__x->_M_right = 0;`
206			`__x->_M_color = _S_red;`
207
208			`// Insert.`
209			`// Make new node child of parent and maintain root, leftmost and`
210			`// rightmost nodes.`
211			`// N.B. First node is always inserted left.`
212			`if (__insert_left)`
213			`{`
214			`__p->_M_left = __x; // also makes leftmost = __x when __p == &__header`
215
216			`if (__p == &__header)`
217			`{`
218			`__header._M_parent = __x;`
219			`__header._M_right = __x;`
220			`}`
221			`else if (__p == __header._M_left)`
222			`__header._M_left = __x; // maintain leftmost pointing to min node`
223			`}`
224			`else`
225			`{`
226			`__p->_M_right = __x;`
227
228			`if (__p == __header._M_right)`
229			`__header._M_right = __x; // maintain rightmost pointing to max node`
230			`}`
231			`// Rebalance.`
232			`while (__x != __root`
233			`&& __x->_M_parent->_M_color == _S_red)`
234			`{`
235			`_Rb_tree_node_base* const __xpp = __x->_M_parent->_M_parent;`
236
237			`if (__x->_M_parent == __xpp->_M_left)`
238			`{`
239			`_Rb_tree_node_base* const __y = __xpp->_M_right;`
240			`if (__y && __y->_M_color == _S_red)`
241			`{`
242			`__x->_M_parent->_M_color = _S_black;`
243			`__y->_M_color = _S_black;`
244			`__xpp->_M_color = _S_red;`
245			`__x = __xpp;`
246			`}`
247			`else`
248			`{`
249			`if (__x == __x->_M_parent->_M_right)`
250			`{`
251			`__x = __x->_M_parent;`
252			`local_Rb_tree_rotate_left(__x, __root);`
253			`}`
254			`__x->_M_parent->_M_color = _S_black;`
255			`__xpp->_M_color = _S_red;`
256			`local_Rb_tree_rotate_right(__xpp, __root);`
257			`}`
258			`}`
259			`else`
260			`{`
261			`_Rb_tree_node_base* const __y = __xpp->_M_left;`
262			`if (__y && __y->_M_color == _S_red)`
263			`{`
264			`__x->_M_parent->_M_color = _S_black;`
265			`__y->_M_color = _S_black;`
266			`__xpp->_M_color = _S_red;`
267			`__x = __xpp;`
268			`}`
269			`else`
270			`{`
271			`if (__x == __x->_M_parent->_M_left)`
272			`{`
273			`__x = __x->_M_parent;`
274			`local_Rb_tree_rotate_right(__x, __root);`
275			`}`
276			`__x->_M_parent->_M_color = _S_black;`
277			`__xpp->_M_color = _S_red;`
278			`local_Rb_tree_rotate_left(__xpp, __root);`
279			`}`
280			`}`
281			`}`
282			`__root->_M_color = _S_black;`
283			`}`
284
285			`_Rb_tree_node_base*`
286			`_Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,`
287			`_Rb_tree_node_base& __header) throw ()`
288			`{`
289			`_Rb_tree_node_base *& __root = __header._M_parent;`
290			`_Rb_tree_node_base *& __leftmost = __header._M_left;`
291			`_Rb_tree_node_base *& __rightmost = __header._M_right;`
292			`_Rb_tree_node_base* __y = __z;`
293			`_Rb_tree_node_base* __x = 0;`
294			`_Rb_tree_node_base* __x_parent = 0;`
295
296			`if (__y->_M_left == 0) // __z has at most one non-null child. y == z.`
297			`__x = __y->_M_right; // __x might be null.`
298			`else`
299			`if (__y->_M_right == 0) // __z has exactly one non-null child. y == z.`
300			`__x = __y->_M_left; // __x is not null.`
301			`else`
302			`{`
303			`// __z has two non-null children. Set __y to`
304			`__y = __y->_M_right; // __z's successor. __x might be null.`
305			`while (__y->_M_left != 0)`
306			`__y = __y->_M_left;`
307			`__x = __y->_M_right;`
308			`}`
309			`if (__y != __z)`
310			`{`
311			`// relink y in place of z. y is z's successor`
312			`__z->_M_left->_M_parent = __y;`
313			`__y->_M_left = __z->_M_left;`
314			`if (__y != __z->_M_right)`
315			`{`
316			`__x_parent = __y->_M_parent;`
317			`if (__x) __x->_M_parent = __y->_M_parent;`
318			`__y->_M_parent->_M_left = __x; // __y must be a child of _M_left`
319			`__y->_M_right = __z->_M_right;`
320			`__z->_M_right->_M_parent = __y;`
321			`}`
322			`else`
323			`__x_parent = __y;`
324			`if (__root == __z)`
325			`__root = __y;`
326			`else if (__z->_M_parent->_M_left == __z)`
327			`__z->_M_parent->_M_left = __y;`
328			`else`
329			`__z->_M_parent->_M_right = __y;`
330			`__y->_M_parent = __z->_M_parent;`
331			`std::swap(__y->_M_color, __z->_M_color);`
332			`__y = __z;`
333			`// __y now points to node to be actually deleted`
334			`}`
335			`else`
336			`{ // __y == __z`
337			`__x_parent = __y->_M_parent;`
338			`if (__x)`
339			`__x->_M_parent = __y->_M_parent;`
340			`if (__root == __z)`
341			`__root = __x;`
342			`else`
343			`if (__z->_M_parent->_M_left == __z)`
344			`__z->_M_parent->_M_left = __x;`
345			`else`
346			`__z->_M_parent->_M_right = __x;`
347			`if (__leftmost == __z)`
348			`{`
349			`if (__z->_M_right == 0) // __z->_M_left must be null also`
350			`__leftmost = __z->_M_parent;`
351			`// makes __leftmost == _M_header if __z == __root`
352			`else`
353			`__leftmost = _Rb_tree_node_base::_S_minimum(__x);`
354			`}`
355			`if (__rightmost == __z)`
356			`{`
357			`if (__z->_M_left == 0) // __z->_M_right must be null also`
358			`__rightmost = __z->_M_parent;`
359			`// makes __rightmost == _M_header if __z == __root`
360			`else // __x == __z->_M_left`
361			`__rightmost = _Rb_tree_node_base::_S_maximum(__x);`
362			`}`
363			`}`
364			`if (__y->_M_color != _S_red)`
365			`{`
366			`while (__x != __root && (__x == 0 \|\| __x->_M_color == _S_black))`
367			`if (__x == __x_parent->_M_left)`
368			`{`
369			`_Rb_tree_node_base* __w = __x_parent->_M_right;`
370			`if (__w->_M_color == _S_red)`
371			`{`
372			`__w->_M_color = _S_black;`
373			`__x_parent->_M_color = _S_red;`
374			`local_Rb_tree_rotate_left(__x_parent, __root);`
375			`__w = __x_parent->_M_right;`
376			`}`
377			`if ((__w->_M_left == 0 \|\|`
378			`__w->_M_left->_M_color == _S_black) &&`
379			`(__w->_M_right == 0 \|\|`
380			`__w->_M_right->_M_color == _S_black))`
381			`{`
382			`__w->_M_color = _S_red;`
383			`__x = __x_parent;`
384			`__x_parent = __x_parent->_M_parent;`
385			`}`
386			`else`
387			`{`
388			`if (__w->_M_right == 0`
389			`\|\| __w->_M_right->_M_color == _S_black)`
390			`{`
391			`__w->_M_left->_M_color = _S_black;`
392			`__w->_M_color = _S_red;`
393			`local_Rb_tree_rotate_right(__w, __root);`
394			`__w = __x_parent->_M_right;`
395			`}`
396			`__w->_M_color = __x_parent->_M_color;`
397			`__x_parent->_M_color = _S_black;`
398			`if (__w->_M_right)`
399			`__w->_M_right->_M_color = _S_black;`
400			`local_Rb_tree_rotate_left(__x_parent, __root);`
401			`break;`
402			`}`
403			`}`
404			`else`
405			`{`
406			`// same as above, with _M_right <-> _M_left.`
407			`_Rb_tree_node_base* __w = __x_parent->_M_left;`
408			`if (__w->_M_color == _S_red)`
409			`{`
410			`__w->_M_color = _S_black;`
411			`__x_parent->_M_color = _S_red;`
412			`local_Rb_tree_rotate_right(__x_parent, __root);`
413			`__w = __x_parent->_M_left;`
414			`}`
415			`if ((__w->_M_right == 0 \|\|`
416			`__w->_M_right->_M_color == _S_black) &&`
417			`(__w->_M_left == 0 \|\|`
418			`__w->_M_left->_M_color == _S_black))`
419			`{`
420			`__w->_M_color = _S_red;`
421			`__x = __x_parent;`
422			`__x_parent = __x_parent->_M_parent;`
423			`}`
424			`else`
425			`{`
426			`if (__w->_M_left == 0 \|\| __w->_M_left->_M_color == _S_black)`
427			`{`
428			`__w->_M_right->_M_color = _S_black;`
429			`__w->_M_color = _S_red;`
430			`local_Rb_tree_rotate_left(__w, __root);`
431			`__w = __x_parent->_M_left;`
432			`}`
433			`__w->_M_color = __x_parent->_M_color;`
434			`__x_parent->_M_color = _S_black;`
435			`if (__w->_M_left)`
436			`__w->_M_left->_M_color = _S_black;`
437			`local_Rb_tree_rotate_right(__x_parent, __root);`
438			`break;`
439			`}`
440			`}`
441			`if (__x) __x->_M_color = _S_black;`
442			`}`
443			`return __y;`
444			`}`
445
446			`unsigned int`
447			`_Rb_tree_black_count(const _Rb_tree_node_base* __node,`
448			`const _Rb_tree_node_base* __root) throw ()`
449			`{`
450			`if (__node == 0)`
451			`return 0;`
452			`unsigned int __sum = 0;`
453			`do`
454			`{`
455			`if (__node->_M_color == _S_black)`
456			`++__sum;`
457			`if (__node == __root)`
458			`break;`
459			`__node = __node->_M_parent;`
460			`}`
461			`while (1);`
462			`return __sum;`
463			`}`
464
465			`_GLIBCXX_END_NAMESPACE_VERSION`
466			`} // namespace`