2007-12-10 15:11:51 +03:00
/*
Red Black Trees
( C ) 1999 Andrea Arcangeli < andrea @ suse . de >
( C ) 2002 David Woodhouse < dwmw2 @ infradead . org >
This program 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 2 of the License , or
( at your option ) any later version .
This program 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 .
You should have received a copy of the GNU General Public License
along with this program ; if not , write to the Free Software
Foundation , Inc . , 59 Temple Place , Suite 330 , Boston , MA 02111 - 1307 USA
linux / lib / rbtree . c
*/
2017-01-08 22:52:47 +03:00
# include "replace.h"
2007-12-10 15:20:24 +03:00
# include "rbtree.h"
2019-05-24 17:08:58 +03:00
# include "fault.h"
2007-12-10 15:20:24 +03:00
# define RB_RED 0
# define RB_BLACK 1
# define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))
# define rb_color(r) ((r)->rb_parent_color & 1)
# define rb_is_red(r) (!rb_color(r))
# define rb_is_black(r) rb_color(r)
# define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0)
# define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0)
static void rb_set_parent ( struct rb_node * rb , struct rb_node * p )
{
rb - > rb_parent_color = ( rb - > rb_parent_color & 3 ) | ( unsigned long ) p ;
}
static void rb_set_color ( struct rb_node * rb , int color )
{
rb - > rb_parent_color = ( rb - > rb_parent_color & ~ 1 ) | color ;
}
# define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
# define RB_EMPTY_NODE(node) (rb_parent(node) == node)
# define RB_CLEAR_NODE(node) (rb_set_parent(node, node))
2007-12-10 15:11:51 +03:00
static void __rb_rotate_left ( struct rb_node * node , struct rb_root * root )
{
struct rb_node * right = node - > rb_right ;
struct rb_node * parent = rb_parent ( node ) ;
if ( ( node - > rb_right = right - > rb_left ) )
rb_set_parent ( right - > rb_left , node ) ;
right - > rb_left = node ;
rb_set_parent ( right , parent ) ;
if ( parent )
{
if ( node = = parent - > rb_left )
parent - > rb_left = right ;
else
parent - > rb_right = right ;
}
else
root - > rb_node = right ;
rb_set_parent ( node , right ) ;
}
static void __rb_rotate_right ( struct rb_node * node , struct rb_root * root )
{
struct rb_node * left = node - > rb_left ;
struct rb_node * parent = rb_parent ( node ) ;
if ( ( node - > rb_left = left - > rb_right ) )
rb_set_parent ( left - > rb_right , node ) ;
left - > rb_right = node ;
rb_set_parent ( left , parent ) ;
if ( parent )
{
if ( node = = parent - > rb_right )
parent - > rb_right = left ;
else
parent - > rb_left = left ;
}
else
root - > rb_node = left ;
rb_set_parent ( node , left ) ;
}
void rb_insert_color ( struct rb_node * node , struct rb_root * root )
{
struct rb_node * parent , * gparent ;
while ( ( parent = rb_parent ( node ) ) & & rb_is_red ( parent ) )
{
gparent = rb_parent ( parent ) ;
if ( parent = = gparent - > rb_left )
{
{
register struct rb_node * uncle = gparent - > rb_right ;
if ( uncle & & rb_is_red ( uncle ) )
{
rb_set_black ( uncle ) ;
rb_set_black ( parent ) ;
rb_set_red ( gparent ) ;
node = gparent ;
continue ;
}
}
if ( parent - > rb_right = = node )
{
register struct rb_node * tmp ;
__rb_rotate_left ( parent , root ) ;
tmp = parent ;
parent = node ;
node = tmp ;
}
rb_set_black ( parent ) ;
rb_set_red ( gparent ) ;
__rb_rotate_right ( gparent , root ) ;
} else {
{
register struct rb_node * uncle = gparent - > rb_left ;
if ( uncle & & rb_is_red ( uncle ) )
{
rb_set_black ( uncle ) ;
rb_set_black ( parent ) ;
rb_set_red ( gparent ) ;
node = gparent ;
continue ;
}
}
if ( parent - > rb_left = = node )
{
register struct rb_node * tmp ;
__rb_rotate_right ( parent , root ) ;
tmp = parent ;
parent = node ;
node = tmp ;
}
rb_set_black ( parent ) ;
rb_set_red ( gparent ) ;
__rb_rotate_left ( gparent , root ) ;
}
}
rb_set_black ( root - > rb_node ) ;
}
static void __rb_erase_color ( struct rb_node * node , struct rb_node * parent ,
struct rb_root * root )
{
struct rb_node * other ;
while ( ( ! node | | rb_is_black ( node ) ) & & node ! = root - > rb_node )
{
if ( parent - > rb_left = = node )
{
other = parent - > rb_right ;
2019-05-24 17:08:58 +03:00
if ( other = = NULL ) {
/* we should never get here */
smb_panic ( " corrupted rb tree " ) ;
/* satisfy static checkers */
return ;
}
2007-12-10 15:11:51 +03:00
if ( rb_is_red ( other ) )
{
rb_set_black ( other ) ;
rb_set_red ( parent ) ;
__rb_rotate_left ( parent , root ) ;
other = parent - > rb_right ;
}
if ( ( ! other - > rb_left | | rb_is_black ( other - > rb_left ) ) & &
( ! other - > rb_right | | rb_is_black ( other - > rb_right ) ) )
{
rb_set_red ( other ) ;
node = parent ;
parent = rb_parent ( node ) ;
}
else
{
if ( ! other - > rb_right | | rb_is_black ( other - > rb_right ) )
{
struct rb_node * o_left ;
if ( ( o_left = other - > rb_left ) )
rb_set_black ( o_left ) ;
rb_set_red ( other ) ;
__rb_rotate_right ( other , root ) ;
other = parent - > rb_right ;
}
rb_set_color ( other , rb_color ( parent ) ) ;
rb_set_black ( parent ) ;
if ( other - > rb_right )
rb_set_black ( other - > rb_right ) ;
__rb_rotate_left ( parent , root ) ;
node = root - > rb_node ;
break ;
}
}
else
{
other = parent - > rb_left ;
if ( rb_is_red ( other ) )
{
rb_set_black ( other ) ;
rb_set_red ( parent ) ;
__rb_rotate_right ( parent , root ) ;
other = parent - > rb_left ;
}
if ( ( ! other - > rb_left | | rb_is_black ( other - > rb_left ) ) & &
( ! other - > rb_right | | rb_is_black ( other - > rb_right ) ) )
{
rb_set_red ( other ) ;
node = parent ;
parent = rb_parent ( node ) ;
}
else
{
if ( ! other - > rb_left | | rb_is_black ( other - > rb_left ) )
{
register struct rb_node * o_right ;
if ( ( o_right = other - > rb_right ) )
rb_set_black ( o_right ) ;
rb_set_red ( other ) ;
__rb_rotate_left ( other , root ) ;
other = parent - > rb_left ;
}
rb_set_color ( other , rb_color ( parent ) ) ;
rb_set_black ( parent ) ;
if ( other - > rb_left )
rb_set_black ( other - > rb_left ) ;
__rb_rotate_right ( parent , root ) ;
node = root - > rb_node ;
break ;
}
}
}
if ( node )
rb_set_black ( node ) ;
}
void rb_erase ( struct rb_node * node , struct rb_root * root )
{
struct rb_node * child , * parent ;
int color ;
if ( ! node - > rb_left )
child = node - > rb_right ;
else if ( ! node - > rb_right )
child = node - > rb_left ;
else
{
struct rb_node * old = node , * left ;
node = node - > rb_right ;
while ( ( left = node - > rb_left ) ! = NULL )
node = left ;
child = node - > rb_right ;
parent = rb_parent ( node ) ;
color = rb_color ( node ) ;
if ( child )
rb_set_parent ( child , parent ) ;
if ( parent = = old ) {
parent - > rb_right = child ;
parent = node ;
} else
parent - > rb_left = child ;
node - > rb_parent_color = old - > rb_parent_color ;
node - > rb_right = old - > rb_right ;
node - > rb_left = old - > rb_left ;
if ( rb_parent ( old ) )
{
if ( rb_parent ( old ) - > rb_left = = old )
rb_parent ( old ) - > rb_left = node ;
else
rb_parent ( old ) - > rb_right = node ;
} else
root - > rb_node = node ;
rb_set_parent ( old - > rb_left , node ) ;
if ( old - > rb_right )
rb_set_parent ( old - > rb_right , node ) ;
goto color ;
}
parent = rb_parent ( node ) ;
color = rb_color ( node ) ;
if ( child )
rb_set_parent ( child , parent ) ;
if ( parent )
{
if ( parent - > rb_left = = node )
parent - > rb_left = child ;
else
parent - > rb_right = child ;
}
else
root - > rb_node = child ;
color :
if ( color = = RB_BLACK )
__rb_erase_color ( child , parent , root ) ;
}
/*
* This function returns the first node ( in sort order ) of the tree .
*/
struct rb_node * rb_first ( struct rb_root * root )
{
struct rb_node * n ;
n = root - > rb_node ;
if ( ! n )
return NULL ;
while ( n - > rb_left )
n = n - > rb_left ;
return n ;
}
struct rb_node * rb_last ( struct rb_root * root )
{
struct rb_node * n ;
n = root - > rb_node ;
if ( ! n )
return NULL ;
while ( n - > rb_right )
n = n - > rb_right ;
return n ;
}
struct rb_node * rb_next ( struct rb_node * node )
{
struct rb_node * parent ;
if ( rb_parent ( node ) = = node )
return NULL ;
/* If we have a right-hand child, go down and then left as far
as we can . */
if ( node - > rb_right ) {
node = node - > rb_right ;
while ( node - > rb_left )
node = node - > rb_left ;
return node ;
}
/* No right-hand children. Everything down and left is
smaller than us , so any ' next ' node must be in the general
direction of our parent . Go up the tree ; any time the
ancestor is a right - hand child of its parent , keep going
up . First time it ' s a left - hand child of its parent , said
parent is our ' next ' node . */
while ( ( parent = rb_parent ( node ) ) & & node = = parent - > rb_right )
node = parent ;
return parent ;
}
struct rb_node * rb_prev ( struct rb_node * node )
{
struct rb_node * parent ;
if ( rb_parent ( node ) = = node )
return NULL ;
/* If we have a left-hand child, go down and then right as far
as we can . */
if ( node - > rb_left ) {
node = node - > rb_left ;
while ( node - > rb_right )
node = node - > rb_right ;
return node ;
}
/* No left-hand children. Go up till we find an ancestor which
is a right - hand child of its parent */
while ( ( parent = rb_parent ( node ) ) & & node = = parent - > rb_left )
node = parent ;
return parent ;
}
2007-12-10 15:20:24 +03:00
void rb_replace_node ( struct rb_node * victim , struct rb_node * new_node ,
2007-12-10 15:11:51 +03:00
struct rb_root * root )
{
struct rb_node * parent = rb_parent ( victim ) ;
/* Set the surrounding nodes to point to the replacement */
if ( parent ) {
if ( victim = = parent - > rb_left )
2007-12-10 15:20:24 +03:00
parent - > rb_left = new_node ;
2007-12-10 15:11:51 +03:00
else
2007-12-10 15:20:24 +03:00
parent - > rb_right = new_node ;
2007-12-10 15:11:51 +03:00
} else {
2007-12-10 15:20:24 +03:00
root - > rb_node = new_node ;
2007-12-10 15:11:51 +03:00
}
if ( victim - > rb_left )
2007-12-10 15:20:24 +03:00
rb_set_parent ( victim - > rb_left , new_node ) ;
2007-12-10 15:11:51 +03:00
if ( victim - > rb_right )
2007-12-10 15:20:24 +03:00
rb_set_parent ( victim - > rb_right , new_node ) ;
2007-12-10 15:11:51 +03:00
/* Copy the pointers/colour from the victim to the replacement */
2007-12-10 15:20:24 +03:00
* new_node = * victim ;
}
void rb_link_node ( struct rb_node * node , struct rb_node * parent ,
struct rb_node * * rb_link )
{
node - > rb_parent_color = ( unsigned long ) parent ;
node - > rb_left = node - > rb_right = NULL ;
* rb_link = node ;
2007-12-10 15:11:51 +03:00
}