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