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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [libstdc++-v3/] [src/] [tree.cc] - Blame information for rev 826

Details | Compare with Previous | View Log


// 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>
 
_GLIBCXX_BEGIN_NAMESPACE(std)
 
  _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

Browse

Tools

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [libstdc++-v3/] [src/] [tree.cc] - Blame information for rev 826

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