libstdc++-v3/src/stl_tree.cc

   1 // RB tree utilities implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003 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 2, 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 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 /*
  31  *
  32  * Copyright (c) 1996,1997
  33  * Silicon Graphics Computer Systems, Inc.
  34  *
  35  * Permission to use, copy, modify, distribute and sell this software
  36  * and its documentation for any purpose is hereby granted without fee,
  37  * provided that the above copyright notice appear in all copies and
  38  * that both that copyright notice and this permission notice appear
  39  * in supporting documentation.  Silicon Graphics makes no
  40  * representations about the suitability of this software for any
  41  * purpose.  It is provided "as is" without express or implied warranty.
  42  *
  43  *
  44  * Copyright (c) 1994
  45  * Hewlett-Packard Company
  46  *
  47  * Permission to use, copy, modify, distribute and sell this software
  48  * and its documentation for any purpose is hereby granted without fee,
  49  * provided that the above copyright notice appear in all copies and
  50  * that both that copyright notice and this permission notice appear
  51  * in supporting documentation.  Hewlett-Packard Company makes no
  52  * representations about the suitability of this software for any
  53  * purpose.  It is provided "as is" without express or implied warranty.
  54  *
  55  *
  56  */
  57
  58 #include <bits/stl_tree.h>
  59
  60 namespace std
  61 {
  62   _Rb_tree_node_base*
  63   _Rb_tree_increment(_Rb_tree_node_base* __x)
  64   {
  65     if (__x->_M_right != 0)
  66       {
  67         __x = __x->_M_right;
  68         while (__x->_M_left != 0)
  69           __x = __x->_M_left;
  70       }
  71     else
  72       {
  73         _Rb_tree_node_base* __y = __x->_M_parent;
  74         while (__x == __y->_M_right)
  75           {
  76             __x = __y;
  77             __y = __y->_M_parent;
  78           }
  79         if (__x->_M_right != __y)
  80           __x = __y;
  81       }
  82     return __x;
  83   }
  84
  85   _Rb_tree_node_base*
  86   _Rb_tree_decrement(_Rb_tree_node_base* __x)
  87   {
  88     if (__x->_M_color == _S_red
  89         && __x->_M_parent->_M_parent == __x)
  90       __x = __x->_M_right;
  91     else if (__x->_M_left != 0)
  92       {
  93         _Rb_tree_node_base* __y = __x->_M_left;
  94         while (__y->_M_right != 0)
  95           __y = __y->_M_right;
  96         __x = __y;
  97       }
  98     else
  99       {
 100         _Rb_tree_node_base* __y = __x->_M_parent;
 101         while (__x == __y->_M_left)
 102           {
 103             __x = __y;
 104             __y = __y->_M_parent;
 105           }
 106         __x = __y;
 107       }
 108     return __x;
 109   }
 110
 111   void
 112   _Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
 113                        _Rb_tree_node_base*& __root)
 114   {
 115     _Rb_tree_node_base* const __y = __x->_M_right;
 116
 117     __x->_M_right = __y->_M_left;
 118     if (__y->_M_left !=0)
 119       __y->_M_left->_M_parent = __x;
 120     __y->_M_parent = __x->_M_parent;
 121
 122     if (__x == __root)
 123       __root = __y;
 124     else if (__x == __x->_M_parent->_M_left)
 125       __x->_M_parent->_M_left = __y;
 126     else
 127       __x->_M_parent->_M_right = __y;
 128     __y->_M_left = __x;
 129     __x->_M_parent = __y;
 130   }
 131
 132   void
 133   _Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
 134                         _Rb_tree_node_base*& __root)
 135   {
 136     _Rb_tree_node_base* const __y = __x->_M_left;
 137
 138     __x->_M_left = __y->_M_right;
 139     if (__y->_M_right != 0)
 140       __y->_M_right->_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_right)
 146       __x->_M_parent->_M_right = __y;
 147     else
 148       __x->_M_parent->_M_left = __y;
 149     __y->_M_right = __x;
 150     __x->_M_parent = __y;
 151   }
 152
 153   void
 154   _Rb_tree_rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
 155   {
 156     __x->_M_color = _S_red;
 157
 158     while (__x != __root
 159            && __x->_M_parent->_M_color == _S_red)
 160       {
 161         _Rb_tree_node_base* const __xpp = __x->_M_parent->_M_parent;
 162
 163         if (__x->_M_parent == __xpp->_M_left)
 164           {
 165             _Rb_tree_node_base* const __y = __xpp->_M_right;
 166             if (__y && __y->_M_color == _S_red)
 167               {
 168                 __x->_M_parent->_M_color = _S_black;
 169                 __y->_M_color = _S_black;
 170                 __xpp->_M_color = _S_red;
 171                 __x = __xpp;
 172               }
 173             else
 174               {
 175                 if (__x == __x->_M_parent->_M_right)
 176                   {
 177                     __x = __x->_M_parent;
 178                     _Rb_tree_rotate_left(__x, __root);
 179                   }
 180                 __x->_M_parent->_M_color = _S_black;
 181                 __xpp->_M_color = _S_red;
 182                 _Rb_tree_rotate_right(__xpp, __root);
 183               }
 184           }
 185         else
 186           {
 187             _Rb_tree_node_base* const __y = __xpp->_M_left;
 188             if (__y && __y->_M_color == _S_red)
 189               {
 190                 __x->_M_parent->_M_color = _S_black;
 191                 __y->_M_color = _S_black;
 192                 __xpp->_M_color = _S_red;
 193                 __x = __xpp;
 194               }
 195             else
 196               {
 197                 if (__x == __x->_M_parent->_M_left)
 198                   {
 199                     __x = __x->_M_parent;
 200                     _Rb_tree_rotate_right(__x, __root);
 201                   }
 202                 __x->_M_parent->_M_color = _S_black;
 203                 __xpp->_M_color = _S_red;
 204                 _Rb_tree_rotate_left(__xpp, __root);
 205               }
 206           }
 207       }
 208     __root->_M_color = _S_black;
 209   }
 210
 211   _Rb_tree_node_base*
 212   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
 213                                _Rb_tree_node_base& __header)
 214   {
 215     _Rb_tree_node_base *& __root = __header._M_parent;
 216     _Rb_tree_node_base *& __leftmost = __header._M_left;
 217     _Rb_tree_node_base *& __rightmost = __header._M_right;
 218     _Rb_tree_node_base* __y = __z;
 219     _Rb_tree_node_base* __x = 0;
 220     _Rb_tree_node_base* __x_parent = 0;
 221
 222     if (__y->_M_left == 0)     // __z has at most one non-null child. y == z.
 223       __x = __y->_M_right;     // __x might be null.
 224     else
 225       if (__y->_M_right == 0)  // __z has exactly one non-null child. y == z.
 226         __x = __y->_M_left;    // __x is not null.
 227       else
 228         {
 229           // __z has two non-null children.  Set __y to
 230           __y = __y->_M_right;   //   __z's successor.  __x might be null.
 231           while (__y->_M_left != 0)
 232             __y = __y->_M_left;
 233           __x = __y->_M_right;
 234         }
 235     if (__y != __z)
 236       {
 237         // relink y in place of z.  y is z's successor
 238         __z->_M_left->_M_parent = __y;
 239         __y->_M_left = __z->_M_left;
 240         if (__y != __z->_M_right)
 241           {
 242             __x_parent = __y->_M_parent;
 243             if (__x) __x->_M_parent = __y->_M_parent;
 244             __y->_M_parent->_M_left = __x;   // __y must be a child of _M_left
 245             __y->_M_right = __z->_M_right;
 246             __z->_M_right->_M_parent = __y;
 247           }
 248         else
 249           __x_parent = __y;
 250         if (__root == __z)
 251           __root = __y;
 252         else if (__z->_M_parent->_M_left == __z)
 253           __z->_M_parent->_M_left = __y;
 254         else
 255           __z->_M_parent->_M_right = __y;
 256         __y->_M_parent = __z->_M_parent;
 257         std::swap(__y->_M_color, __z->_M_color);
 258         __y = __z;
 259         // __y now points to node to be actually deleted
 260       }
 261     else
 262       {                        // __y == __z
 263         __x_parent = __y->_M_parent;
 264         if (__x)
 265           __x->_M_parent = __y->_M_parent;
 266         if (__root == __z)
 267           __root = __x;
 268         else
 269           if (__z->_M_parent->_M_left == __z)
 270             __z->_M_parent->_M_left = __x;
 271           else
 272             __z->_M_parent->_M_right = __x;
 273         if (__leftmost == __z)
 274           if (__z->_M_right == 0)        // __z->_M_left must be null also
 275             __leftmost = __z->_M_parent;
 276         // makes __leftmost == _M_header if __z == __root
 277           else
 278             __leftmost = _Rb_tree_node_base::_S_minimum(__x);
 279         if (__rightmost == __z)
 280           if (__z->_M_left == 0)         // __z->_M_right must be null also
 281             __rightmost = __z->_M_parent;
 282         // makes __rightmost == _M_header if __z == __root
 283           else                      // __x == __z->_M_left
 284             __rightmost = _Rb_tree_node_base::_S_maximum(__x);
 285       }
 286     if (__y->_M_color != _S_red)
 287       {
 288         while (__x != __root && (__x == 0 || __x->_M_color == _S_black))
 289           if (__x == __x_parent->_M_left)
 290             {
 291               _Rb_tree_node_base* __w = __x_parent->_M_right;
 292               if (__w->_M_color == _S_red)
 293                 {
 294                   __w->_M_color = _S_black;
 295                   __x_parent->_M_color = _S_red;
 296                   _Rb_tree_rotate_left(__x_parent, __root);
 297                   __w = __x_parent->_M_right;
 298                 }
 299               if ((__w->_M_left == 0 ||
 300                    __w->_M_left->_M_color == _S_black) &&
 301                   (__w->_M_right == 0 ||
 302                    __w->_M_right->_M_color == _S_black))
 303                 {
 304                   __w->_M_color = _S_red;
 305                   __x = __x_parent;
 306                   __x_parent = __x_parent->_M_parent;
 307                 }
 308               else
 309                 {
 310                   if (__w->_M_right == 0
 311                       || __w->_M_right->_M_color == _S_black)
 312                     {
 313                       __w->_M_left->_M_color = _S_black;
 314                       __w->_M_color = _S_red;
 315                       _Rb_tree_rotate_right(__w, __root);
 316                       __w = __x_parent->_M_right;
 317                     }
 318                   __w->_M_color = __x_parent->_M_color;
 319                   __x_parent->_M_color = _S_black;
 320                   if (__w->_M_right)
 321                     __w->_M_right->_M_color = _S_black;
 322                   _Rb_tree_rotate_left(__x_parent, __root);
 323                   break;
 324                 }
 325             }
 326           else
 327             {
 328               // same as above, with _M_right <-> _M_left.
 329               _Rb_tree_node_base* __w = __x_parent->_M_left;
 330               if (__w->_M_color == _S_red)
 331                 {
 332                   __w->_M_color = _S_black;
 333                   __x_parent->_M_color = _S_red;
 334                   _Rb_tree_rotate_right(__x_parent, __root);
 335                   __w = __x_parent->_M_left;
 336                 }
 337               if ((__w->_M_right == 0 ||
 338                    __w->_M_right->_M_color == _S_black) &&
 339                   (__w->_M_left == 0 ||
 340                    __w->_M_left->_M_color == _S_black))
 341                 {
 342                   __w->_M_color = _S_red;
 343                   __x = __x_parent;
 344                   __x_parent = __x_parent->_M_parent;
 345                 }
 346               else
 347                 {
 348                   if (__w->_M_left == 0 || __w->_M_left->_M_color == _S_black)
 349                     {
 350                       __w->_M_right->_M_color = _S_black;
 351                       __w->_M_color = _S_red;
 352                       _Rb_tree_rotate_left(__w, __root);
 353                       __w = __x_parent->_M_left;
 354                     }
 355                   __w->_M_color = __x_parent->_M_color;
 356                   __x_parent->_M_color = _S_black;
 357                   if (__w->_M_left)
 358                     __w->_M_left->_M_color = _S_black;
 359                   _Rb_tree_rotate_right(__x_parent, __root);
 360                   break;
 361                 }
 362             }
 363         if (__x) __x->_M_color = _S_black;
 364       }
 365     return __y;
 366   }
 367
 368   unsigned int
 369   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
 370                        const _Rb_tree_node_base* __root)
 371   {
 372     if (__node == 0)
 373       return 0;
 374     unsigned int __sum = 0;
 375     do
 376       {
 377         if (__node->_M_color == _S_black)
 378           ++__sum;
 379         if (__node == __root)
 380           break;
 381         __node = __node->_M_parent;
 382       }
 383     while (1);
 384     return __sum;
 385   }
 386 } // namespace std