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