1e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat/* 2e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat Red Black Trees 3e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat (C) 1999 Andrea Arcangeli <andrea@suse.de> 4e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat (C) 2002 David Woodhouse <dwmw2@infradead.org> 5e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 6e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat This program is free software; you can redistribute it and/or modify 7e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat it under the terms of the GNU General Public License as published by 8e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat the Free Software Foundation; either version 2 of the License, or 9e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat (at your option) any later version. 10e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 11e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat This program is distributed in the hope that it will be useful, 12e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat but WITHOUT ANY WARRANTY; without even the implied warranty of 13e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat GNU General Public License for more details. 15e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 16e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat You should have received a copy of the GNU General Public License 17e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat along with this program; if not, write to the Free Software 18e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 19e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 20e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat linux/lib/rbtree.c 21e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat*/ 22e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 23e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat#include "rbtree.h" 24e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 25e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatstatic void __rb_rotate_left(struct rb_node *node, struct rb_root *root) 26e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat{ 27e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_node *right = node->rb_right; 28e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_node *parent = rb_parent(node); 29e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 30e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if ((node->rb_right = right->rb_left)) 31e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_parent(right->rb_left, node); 32e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat right->rb_left = node; 33e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 34e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_parent(right, parent); 35e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 36e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (parent) 37e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat { 38e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (node == parent->rb_left) 39e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat parent->rb_left = right; 40e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat else 41e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat parent->rb_right = right; 42e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 43e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat else 44e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat root->rb_node = right; 45e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_parent(node, right); 46e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat} 47e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 48e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatstatic void __rb_rotate_right(struct rb_node *node, struct rb_root *root) 49e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat{ 50e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_node *left = node->rb_left; 51e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_node *parent = rb_parent(node); 52e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 53e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if ((node->rb_left = left->rb_right)) 54e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_parent(left->rb_right, node); 55e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat left->rb_right = node; 56e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 57e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_parent(left, parent); 58e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 59e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (parent) 60e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat { 61e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (node == parent->rb_right) 62e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat parent->rb_right = left; 63e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat else 64e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat parent->rb_left = left; 65e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 66e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat else 67e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat root->rb_node = left; 68e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_parent(node, left); 69e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat} 70e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 71e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatvoid rb_insert_color(struct rb_node *node, struct rb_root *root) 72e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat{ 73e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_node *parent, *gparent; 74e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 75e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat while ((parent = rb_parent(node)) && rb_is_red(parent)) 76e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat { 77e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat gparent = rb_parent(parent); 78e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 79e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (parent == gparent->rb_left) 80e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat { 81e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat { 82e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat register struct rb_node *uncle = gparent->rb_right; 83e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (uncle && rb_is_red(uncle)) 84e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat { 85e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_black(uncle); 86e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_black(parent); 87e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_red(gparent); 88e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat node = gparent; 89e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat continue; 90e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 91e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 92e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 93e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (parent->rb_right == node) 94e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat { 95e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat register struct rb_node *tmp; 96e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat __rb_rotate_left(parent, root); 97e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat tmp = parent; 98e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat parent = node; 99e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat node = tmp; 100e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 101e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 102e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_black(parent); 103e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_red(gparent); 104e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat __rb_rotate_right(gparent, root); 105e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } else { 106e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat { 107e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat register struct rb_node *uncle = gparent->rb_left; 108e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (uncle && rb_is_red(uncle)) 109e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat { 110e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_black(uncle); 111e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_black(parent); 112e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_red(gparent); 113e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat node = gparent; 114e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat continue; 115e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 116e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 117e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 118e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (parent->rb_left == node) 119e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat { 120e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat register struct rb_node *tmp; 121e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat __rb_rotate_right(parent, root); 122e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat tmp = parent; 123e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat parent = node; 124e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat node = tmp; 125e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 126e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 127e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_black(parent); 128e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_red(gparent); 129e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat __rb_rotate_left(gparent, root); 130e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 131e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 132e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 133e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_black(root->rb_node); 134e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat} 135e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 136e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatstatic void __rb_erase_color(struct rb_node *node, struct rb_node *parent, 137e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_root *root) 138e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat{ 139e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_node *other; 140e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 141e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat while ((!node || rb_is_black(node)) && node != root->rb_node) 142e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat { 143e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (parent->rb_left == node) 144e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat { 145e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat other = parent->rb_right; 146e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (rb_is_red(other)) 147e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat { 148e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_black(other); 149e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_red(parent); 150e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat __rb_rotate_left(parent, root); 151e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat other = parent->rb_right; 152e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 153e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if ((!other->rb_left || rb_is_black(other->rb_left)) && 154e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat (!other->rb_right || rb_is_black(other->rb_right))) 155e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat { 156e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_red(other); 157e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat node = parent; 158e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat parent = rb_parent(node); 159e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 160e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat else 161e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat { 162e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (!other->rb_right || rb_is_black(other->rb_right)) 163e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat { 164e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_node *o_left; 165e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if ((o_left = other->rb_left)) 166e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_black(o_left); 167e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_red(other); 168e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat __rb_rotate_right(other, root); 169e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat other = parent->rb_right; 170e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 171e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_color(other, rb_color(parent)); 172e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_black(parent); 173e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (other->rb_right) 174e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_black(other->rb_right); 175e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat __rb_rotate_left(parent, root); 176e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat node = root->rb_node; 177e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat break; 178e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 179e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 180e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat else 181e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat { 182e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat other = parent->rb_left; 183e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (rb_is_red(other)) 184e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat { 185e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_black(other); 186e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_red(parent); 187e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat __rb_rotate_right(parent, root); 188e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat other = parent->rb_left; 189e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 190e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if ((!other->rb_left || rb_is_black(other->rb_left)) && 191e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat (!other->rb_right || rb_is_black(other->rb_right))) 192e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat { 193e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_red(other); 194e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat node = parent; 195e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat parent = rb_parent(node); 196e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 197e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat else 198e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat { 199e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (!other->rb_left || rb_is_black(other->rb_left)) 200e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat { 201e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat register struct rb_node *o_right; 202e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if ((o_right = other->rb_right)) 203e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_black(o_right); 204e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_red(other); 205e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat __rb_rotate_left(other, root); 206e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat other = parent->rb_left; 207e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 208e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_color(other, rb_color(parent)); 209e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_black(parent); 210e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (other->rb_left) 211e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_black(other->rb_left); 212e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat __rb_rotate_right(parent, root); 213e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat node = root->rb_node; 214e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat break; 215e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 216e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 217e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 218e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (node) 219e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_black(node); 220e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat} 221e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 222e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatvoid rb_erase(struct rb_node *node, struct rb_root *root) 223e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat{ 224e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_node *child, *parent; 225e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat int color; 226e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 227e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (!node->rb_left) 228e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat child = node->rb_right; 229e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat else if (!node->rb_right) 230e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat child = node->rb_left; 231e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat else 232e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat { 233e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_node *old = node, *left; 234e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 235e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat node = node->rb_right; 236e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat while ((left = node->rb_left) != NULL) 237e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat node = left; 238e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat child = node->rb_right; 239e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat parent = rb_parent(node); 240e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat color = rb_color(node); 241e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 242e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (child) 243e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_parent(child, parent); 244e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (parent == old) { 245e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat parent->rb_right = child; 246e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat parent = node; 247e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } else 248e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat parent->rb_left = child; 249e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 250e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat node->rb_parent_color = old->rb_parent_color; 251e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat node->rb_right = old->rb_right; 252e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat node->rb_left = old->rb_left; 253e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 254e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (rb_parent(old)) 255e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat { 256e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (rb_parent(old)->rb_left == old) 257e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_parent(old)->rb_left = node; 258e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat else 259e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_parent(old)->rb_right = node; 260e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } else 261e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat root->rb_node = node; 262e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 263e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_parent(old->rb_left, node); 264e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (old->rb_right) 265e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_parent(old->rb_right, node); 266e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat goto color; 267e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 268e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 269e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat parent = rb_parent(node); 270e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat color = rb_color(node); 271e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 272e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (child) 273e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_parent(child, parent); 274e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (parent) 275e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat { 276e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (parent->rb_left == node) 277e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat parent->rb_left = child; 278e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat else 279e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat parent->rb_right = child; 280e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 281e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat else 282e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat root->rb_node = child; 283e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 284e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat color: 285e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (color == RB_BLACK) 286e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat __rb_erase_color(child, parent, root); 287e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat} 288e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 289e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat/* 290e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat * This function returns the first node (in sort order) of the tree. 291e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat */ 292e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatstruct rb_node *rb_first(struct rb_root *root) 293e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat{ 294e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_node *n; 295e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 296e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat n = root->rb_node; 297e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (!n) 298e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat return NULL; 299e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat while (n->rb_left) 300e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat n = n->rb_left; 301e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat return n; 302e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat} 303e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 304e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatstruct rb_node *rb_last(struct rb_root *root) 305e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat{ 306e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_node *n; 307e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 308e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat n = root->rb_node; 309e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (!n) 310e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat return NULL; 311e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat while (n->rb_right) 312e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat n = n->rb_right; 313e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat return n; 314e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat} 315e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 316e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatstruct rb_node *rb_next(struct rb_node *node) 317e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat{ 318e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_node *parent; 319e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 320e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (rb_parent(node) == node) 321e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat return NULL; 322e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 323e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat /* If we have a right-hand child, go down and then left as far 324e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat as we can. */ 325e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (node->rb_right) { 326e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat node = node->rb_right; 327e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat while (node->rb_left) 328e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat node=node->rb_left; 329e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat return node; 330e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 331e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 332e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat /* No right-hand children. Everything down and left is 333e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat smaller than us, so any 'next' node must be in the general 334e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat direction of our parent. Go up the tree; any time the 335e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat ancestor is a right-hand child of its parent, keep going 336e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat up. First time it's a left-hand child of its parent, said 337e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat parent is our 'next' node. */ 338e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat while ((parent = rb_parent(node)) && node == parent->rb_right) 339e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat node = parent; 340e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 341e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat return parent; 342e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat} 343e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 344e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatstruct rb_node *rb_prev(struct rb_node *node) 345e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat{ 346e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_node *parent; 347e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 348e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (rb_parent(node) == node) 349e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat return NULL; 350e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 351e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat /* If we have a left-hand child, go down and then right as far 352e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat as we can. */ 353e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (node->rb_left) { 354e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat node = node->rb_left; 355e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat while (node->rb_right) 356e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat node=node->rb_right; 357e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat return node; 358e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 359e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 360e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat /* No left-hand children. Go up till we find an ancestor which 361e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat is a right-hand child of its parent */ 362e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat while ((parent = rb_parent(node)) && node == parent->rb_left) 363e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat node = parent; 364e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 365e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat return parent; 366e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat} 367e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 368e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehatvoid rb_replace_node(struct rb_node *victim, struct rb_node *new, 369e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_root *root) 370e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat{ 371e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat struct rb_node *parent = rb_parent(victim); 372e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 373e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat /* Set the surrounding nodes to point to the replacement */ 374e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (parent) { 375e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (victim == parent->rb_left) 376e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat parent->rb_left = new; 377e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat else 378e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat parent->rb_right = new; 379e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } else { 380e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat root->rb_node = new; 381e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat } 382e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (victim->rb_left) 383e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_parent(victim->rb_left, new); 384e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat if (victim->rb_right) 385e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat rb_set_parent(victim->rb_right, new); 386e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat 387e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat /* Copy the pointers/colour from the victim to the replacement */ 388e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat *new = *victim; 389e20e1347b9914aa05e30548c15d7cd5e412cc0e2San Mehat} 390