libstdc++-v3/src/c++98/tree.cc

   1 // RB tree utilities implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003-2017 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 #if !_GLIBCXX_INLINE_VERSION
 154   /* Static keyword was missing on _Rb_tree_rotate_left.
 155      Export the symbol for backward compatibility until
 156      next ABI change.  */
 157   void
 158   _Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
 159                        _Rb_tree_node_base*& __root)
 160   { local_Rb_tree_rotate_left (__x, __root); }
 161 #endif
 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 #if !_GLIBCXX_INLINE_VERSION
 185   /* Static keyword was missing on _Rb_tree_rotate_right
 186      Export the symbol for backward compatibility until
 187      next ABI change.  */
 188   void
 189   _Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
 190                         _Rb_tree_node_base*& __root)
 191   { local_Rb_tree_rotate_right (__x, __root); }
 192 #endif
 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