libstdc++-v3/src/tree.cc

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