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