libstdc++-v3/src/tree.cc

   1 // 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