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