// RB tree utilities implementation -*- C++ -*-
// Copyright (C) 2003-2013 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
/*
*
* Copyright (c) 1996,1997
* Silicon Graphics Computer Systems, Inc.
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Silicon Graphics makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*
*
* Copyright (c) 1994
* Hewlett-Packard Company
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Hewlett-Packard Company makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*
*
*/
#include <bits/stl_tree.h>
namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
static _Rb_tree_node_base*
local_Rb_tree_increment(_Rb_tree_node_base* __x) throw ()
{
if (__x->_M_right != 0)
{
__x = __x->_M_right;
while (__x->_M_left != 0)
__x = __x->_M_left;
}
else
{
_Rb_tree_node_base* __y = __x->_M_parent;
while (__x == __y->_M_right)
{
__x = __y;
__y = __y->_M_parent;
}
if (__x->_M_right != __y)
__x = __y;
}
return __x;
}
_Rb_tree_node_base*
_Rb_tree_increment(_Rb_tree_node_base* __x) throw ()
{
return local_Rb_tree_increment(__x);
}
const _Rb_tree_node_base*
_Rb_tree_increment(const _Rb_tree_node_base* __x) throw ()
{
return local_Rb_tree_increment(const_cast<_Rb_tree_node_base*>(__x));
}
static _Rb_tree_node_base*
local_Rb_tree_decrement(_Rb_tree_node_base* __x) throw ()
{
if (__x->_M_color == _S_red
&& __x->_M_parent->_M_parent == __x)
__x = __x->_M_right;
else if (__x->_M_left != 0)
{
_Rb_tree_node_base* __y = __x->_M_left;
while (__y->_M_right != 0)
__y = __y->_M_right;
__x = __y;
}
else
{
_Rb_tree_node_base* __y = __x->_M_parent;
while (__x == __y->_M_left)
{
__x = __y;
__y = __y->_M_parent;
}
__x = __y;
}
return __x;
}
_Rb_tree_node_base*
_Rb_tree_decrement(_Rb_tree_node_base* __x) throw ()
{
return local_Rb_tree_decrement(__x);
}
const _Rb_tree_node_base*
_Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ()
{
return local_Rb_tree_decrement(const_cast<_Rb_tree_node_base*>(__x));
}
static void
local_Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
_Rb_tree_node_base*& __root)
{
_Rb_tree_node_base* const __y = __x->_M_right;
__x->_M_right = __y->_M_left;
if (__y->_M_left !=0)
__y->_M_left->_M_parent = __x;
__y->_M_parent = __x->_M_parent;
if (__x == __root)
__root = __y;
else if (__x == __x->_M_parent->_M_left)
__x->_M_parent->_M_left = __y;
else
__x->_M_parent->_M_right = __y;
__y->_M_left = __x;
__x->_M_parent = __y;
}
/* Static keyword was missing on _Rb_tree_rotate_left.
Export the symbol for backward compatibility until
next ABI change. */
void
_Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
_Rb_tree_node_base*& __root)
{
local_Rb_tree_rotate_left (__x, __root);
}
static void
local_Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
_Rb_tree_node_base*& __root)
{
_Rb_tree_node_base* const __y = __x->_M_left;
__x->_M_left = __y->_M_right;
if (__y->_M_right != 0)
__y->_M_right->_M_parent = __x;
__y->_M_parent = __x->_M_parent;
if (__x == __root)
__root = __y;
else if (__x == __x->_M_parent->_M_right)
__x->_M_parent->_M_right = __y;
else
__x->_M_parent->_M_left = __y;
__y->_M_right = __x;
__x->_M_parent = __y;
}
/* Static keyword was missing on _Rb_tree_rotate_right
Export the symbol for backward compatibility until
next ABI change. */
void
_Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
_Rb_tree_node_base*& __root)
{
local_Rb_tree_rotate_right (__x, __root);
}
void
_Rb_tree_insert_and_rebalance(const bool __insert_left,
_Rb_tree_node_base* __x,
_Rb_tree_node_base* __p,
_Rb_tree_node_base& __header) throw ()
{
_Rb_tree_node_base *& __root = __header._M_parent;
// Initialize fields in new node to insert.
__x->_M_parent = __p;
__x->_M_left = 0;
__x->_M_right = 0;
__x->_M_color = _S_red;
// Insert.
// Make new node child of parent and maintain root, leftmost and
// rightmost nodes.
// N.B. First node is always inserted left.
if (__insert_left)
{
__p->_M_left = __x; // also makes leftmost = __x when __p == &__header
if (__p == &__header)
{
__header._M_parent = __x;
__header._M_right = __x;
}
else if (__p == __header._M_left)
__header._M_left = __x; // maintain leftmost pointing to min node
}
else
{
__p->_M_right = __x;
if (__p == __header._M_right)
__header._M_right = __x; // maintain rightmost pointing to max node
}
// Rebalance.
while (__x != __root
&& __x->_M_parent->_M_color == _S_red)
{
_Rb_tree_node_base* const __xpp = __x->_M_parent->_M_parent;
if (__x->_M_parent == __xpp->_M_left)
{
_Rb_tree_node_base* const __y = __xpp->_M_right;
if (__y && __y->_M_color == _S_red)
{
__x->_M_parent->_M_color = _S_black;
__y->_M_color = _S_black;
__xpp->_M_color = _S_red;
__x = __xpp;
}
else
{
if (__x == __x->_M_parent->_M_right)
{
__x = __x->_M_parent;
local_Rb_tree_rotate_left(__x, __root);
}
__x->_M_parent->_M_color = _S_black;
__xpp->_M_color = _S_red;
local_Rb_tree_rotate_right(__xpp, __root);
}
}
else
{
_Rb_tree_node_base* const __y = __xpp->_M_left;
if (__y && __y->_M_color == _S_red)
{
__x->_M_parent->_M_color = _S_black;
__y->_M_color = _S_black;
__xpp->_M_color = _S_red;
__x = __xpp;
}
else
{
if (__x == __x->_M_parent->_M_left)
{
__x = __x->_M_parent;
local_Rb_tree_rotate_right(__x, __root);
}
__x->_M_parent->_M_color = _S_black;
__xpp->_M_color = _S_red;
local_Rb_tree_rotate_left(__xpp, __root);
}
}
}
__root->_M_color = _S_black;
}
_Rb_tree_node_base*
_Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
_Rb_tree_node_base& __header) throw ()
{
_Rb_tree_node_base *& __root = __header._M_parent;
_Rb_tree_node_base *& __leftmost = __header._M_left;
_Rb_tree_node_base *& __rightmost = __header._M_right;
_Rb_tree_node_base* __y = __z;
_Rb_tree_node_base* __x = 0;
_Rb_tree_node_base* __x_parent = 0;
if (__y->_M_left == 0) // __z has at most one non-null child. y == z.
__x = __y->_M_right; // __x might be null.
else
if (__y->_M_right == 0) // __z has exactly one non-null child. y == z.
__x = __y->_M_left; // __x is not null.
else
{
// __z has two non-null children. Set __y to
__y = __y->_M_right; // __z's successor. __x might be null.
while (__y->_M_left != 0)
__y = __y->_M_left;
__x = __y->_M_right;
}
if (__y != __z)
{
// relink y in place of z. y is z's successor
__z->_M_left->_M_parent = __y;
__y->_M_left = __z->_M_left;
if (__y != __z->_M_right)
{
__x_parent = __y->_M_parent;
if (__x) __x->_M_parent = __y->_M_parent;
__y->_M_parent->_M_left = __x; // __y must be a child of _M_left
__y->_M_right = __z->_M_right;
__z->_M_right->_M_parent = __y;
}
else
__x_parent = __y;
if (__root == __z)
__root = __y;
else if (__z->_M_parent->_M_left == __z)
__z->_M_parent->_M_left = __y;
else
__z->_M_parent->_M_right = __y;
__y->_M_parent = __z->_M_parent;
std::swap(__y->_M_color, __z->_M_color);
__y = __z;
// __y now points to node to be actually deleted
}
else
{ // __y == __z
__x_parent = __y->_M_parent;
if (__x)
__x->_M_parent = __y->_M_parent;
if (__root == __z)
__root = __x;
else
if (__z->_M_parent->_M_left == __z)
__z->_M_parent->_M_left = __x;
else
__z->_M_parent->_M_right = __x;
if (__leftmost == __z)
{
if (__z->_M_right == 0) // __z->_M_left must be null also
__leftmost = __z->_M_parent;
// makes __leftmost == _M_header if __z == __root
else
__leftmost = _Rb_tree_node_base::_S_minimum(__x);
}
if (__rightmost == __z)
{
if (__z->_M_left == 0) // __z->_M_right must be null also
__rightmost = __z->_M_parent;
// makes __rightmost == _M_header if __z == __root
else // __x == __z->_M_left
__rightmost = _Rb_tree_node_base::_S_maximum(__x);
}
}
if (__y->_M_color != _S_red)
{
while (__x != __root && (__x == 0 || __x->_M_color == _S_black))
if (__x == __x_parent->_M_left)
{
_Rb_tree_node_base* __w = __x_parent->_M_right;
if (__w->_M_color == _S_red)
{
__w->_M_color = _S_black;
__x_parent->_M_color = _S_red;
local_Rb_tree_rotate_left(__x_parent, __root);
__w = __x_parent->_M_right;
}
if ((__w->_M_left == 0 ||
__w->_M_left->_M_color == _S_black) &&
(__w->_M_right == 0 ||
__w->_M_right->_M_color == _S_black))
{
__w->_M_color = _S_red;
__x = __x_parent;
__x_parent = __x_parent->_M_parent;
}
else
{
if (__w->_M_right == 0
|| __w->_M_right->_M_color == _S_black)
{
__w->_M_left->_M_color = _S_black;
__w->_M_color = _S_red;
local_Rb_tree_rotate_right(__w, __root);
__w = __x_parent->_M_right;
}
__w->_M_color = __x_parent->_M_color;
__x_parent->_M_color = _S_black;
if (__w->_M_right)
__w->_M_right->_M_color = _S_black;
local_Rb_tree_rotate_left(__x_parent, __root);
break;
}
}
else
{
// same as above, with _M_right <-> _M_left.
_Rb_tree_node_base* __w = __x_parent->_M_left;
if (__w->_M_color == _S_red)
{
__w->_M_color = _S_black;
__x_parent->_M_color = _S_red;
local_Rb_tree_rotate_right(__x_parent, __root);
__w = __x_parent->_M_left;
}
if ((__w->_M_right == 0 ||
__w->_M_right->_M_color == _S_black) &&
(__w->_M_left == 0 ||
__w->_M_left->_M_color == _S_black))
{
__w->_M_color = _S_red;
__x = __x_parent;
__x_parent = __x_parent->_M_parent;
}
else
{
if (__w->_M_left == 0 || __w->_M_left->_M_color == _S_black)
{
__w->_M_right->_M_color = _S_black;
__w->_M_color = _S_red;
local_Rb_tree_rotate_left(__w, __root);
__w = __x_parent->_M_left;
}
__w->_M_color = __x_parent->_M_color;
__x_parent->_M_color = _S_black;
if (__w->_M_left)
__w->_M_left->_M_color = _S_black;
local_Rb_tree_rotate_right(__x_parent, __root);
break;
}
}
if (__x) __x->_M_color = _S_black;
}
return __y;
}
unsigned int
_Rb_tree_black_count(const _Rb_tree_node_base* __node,
const _Rb_tree_node_base* __root) throw ()
{
if (__node == 0)
return 0;
unsigned int __sum = 0;
do
{
if (__node->_M_color == _S_black)
++__sum;
if (__node == __root)
break;
__node = __node->_M_parent;
}
while (1);
return __sum;
}
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace