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 30 if ((node->rb_right = right->rb_left)) 31 right->rb_left->rb_parent = node; 32 right->rb_left = node; 33 34 if ((right->rb_parent = node->rb_parent)) 35 { 36 if (node == node->rb_parent->rb_left) 37 node->rb_parent->rb_left = right; 38 else 39 node->rb_parent->rb_right = right; 40 } 41 else 42 root->rb_node = right; 43 node->rb_parent = right; 44 } 45 46 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) 47 { 48 struct rb_node *left = node->rb_left; 49 50 if ((node->rb_left = left->rb_right)) 51 left->rb_right->rb_parent = node; 52 left->rb_right = node; 53 54 if ((left->rb_parent = node->rb_parent)) 55 { 56 if (node == node->rb_parent->rb_right) 57 node->rb_parent->rb_right = left; 58 else 59 node->rb_parent->rb_left = left; 60 } 61 else 62 root->rb_node = left; 63 node->rb_parent = left; 64 } 65 66 void rb_insert_color(struct rb_node *node, struct rb_root *root) 67 { 68 struct rb_node *parent, *gparent; 69 70 while ((parent = node->rb_parent) && parent->rb_color == RB_RED) 71 { 72 gparent = parent->rb_parent; 73 74 if (parent == gparent->rb_left) 75 { 76 { 77 register struct rb_node *uncle = gparent->rb_right; 78 if (uncle && uncle->rb_color == RB_RED) 79 { 80 uncle->rb_color = RB_BLACK; 81 parent->rb_color = RB_BLACK; 82 gparent->rb_color = RB_RED; 83 node = gparent; 84 continue; 85 } 86 } 87 88 if (parent->rb_right == node) 89 { 90 register struct rb_node *tmp; 91 __rb_rotate_left(parent, root); 92 tmp = parent; 93 parent = node; 94 node = tmp; 95 } 96 97 parent->rb_color = RB_BLACK; 98 gparent->rb_color = RB_RED; 99 __rb_rotate_right(gparent, root); 100 } else { 101 { 102 register struct rb_node *uncle = gparent->rb_left; 103 if (uncle && uncle->rb_color == RB_RED) 104 { 105 uncle->rb_color = RB_BLACK; 106 parent->rb_color = RB_BLACK; 107 gparent->rb_color = RB_RED; 108 node = gparent; 109 continue; 110 } 111 } 112 113 if (parent->rb_left == node) 114 { 115 register struct rb_node *tmp; 116 __rb_rotate_right(parent, root); 117 tmp = parent; 118 parent = node; 119 node = tmp; 120 } 121 122 parent->rb_color = RB_BLACK; 123 gparent->rb_color = RB_RED; 124 __rb_rotate_left(gparent, root); 125 } 126 } 127 128 root->rb_node->rb_color = RB_BLACK; 129 } 130 EXPORT_SYMBOL(rb_insert_color); 131 132 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, 133 struct rb_root *root) 134 { 135 struct rb_node *other; 136 137 while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node) 138 { 139 if (parent->rb_left == node) 140 { 141 other = parent->rb_right; 142 if (other->rb_color == RB_RED) 143 { 144 other->rb_color = RB_BLACK; 145 parent->rb_color = RB_RED; 146 __rb_rotate_left(parent, root); 147 other = parent->rb_right; 148 } 149 if ((!other->rb_left || 150 other->rb_left->rb_color == RB_BLACK) 151 && (!other->rb_right || 152 other->rb_right->rb_color == RB_BLACK)) 153 { 154 other->rb_color = RB_RED; 155 node = parent; 156 parent = node->rb_parent; 157 } 158 else 159 { 160 if (!other->rb_right || 161 other->rb_right->rb_color == RB_BLACK) 162 { 163 register struct rb_node *o_left; 164 if ((o_left = other->rb_left)) 165 o_left->rb_color = RB_BLACK; 166 other->rb_color = RB_RED; 167 __rb_rotate_right(other, root); 168 other = parent->rb_right; 169 } 170 other->rb_color = parent->rb_color; 171 parent->rb_color = RB_BLACK; 172 if (other->rb_right) 173 other->rb_right->rb_color = RB_BLACK; 174 __rb_rotate_left(parent, root); 175 node = root->rb_node; 176 break; 177 } 178 } 179 else 180 { 181 other = parent->rb_left; 182 if (other->rb_color == RB_RED) 183 { 184 other->rb_color = RB_BLACK; 185 parent->rb_color = RB_RED; 186 __rb_rotate_right(parent, root); 187 other = parent->rb_left; 188 } 189 if ((!other->rb_left || 190 other->rb_left->rb_color == RB_BLACK) 191 && (!other->rb_right || 192 other->rb_right->rb_color == RB_BLACK)) 193 { 194 other->rb_color = RB_RED; 195 node = parent; 196 parent = node->rb_parent; 197 } 198 else 199 { 200 if (!other->rb_left || 201 other->rb_left->rb_color == RB_BLACK) 202 { 203 register struct rb_node *o_right; 204 if ((o_right = other->rb_right)) 205 o_right->rb_color = RB_BLACK; 206 other->rb_color = RB_RED; 207 __rb_rotate_left(other, root); 208 other = parent->rb_left; 209 } 210 other->rb_color = parent->rb_color; 211 parent->rb_color = RB_BLACK; 212 if (other->rb_left) 213 other->rb_left->rb_color = RB_BLACK; 214 __rb_rotate_right(parent, root); 215 node = root->rb_node; 216 break; 217 } 218 } 219 } 220 if (node) 221 node->rb_color = RB_BLACK; 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 = node->rb_parent; 242 color = node->rb_color; 243 244 if (child) 245 child->rb_parent = parent; 246 if (parent) 247 { 248 if (parent->rb_left == node) 249 parent->rb_left = child; 250 else 251 parent->rb_right = child; 252 } 253 else 254 root->rb_node = child; 255 256 if (node->rb_parent == old) 257 parent = node; 258 node->rb_parent = old->rb_parent; 259 node->rb_color = old->rb_color; 260 node->rb_right = old->rb_right; 261 node->rb_left = old->rb_left; 262 263 if (old->rb_parent) 264 { 265 if (old->rb_parent->rb_left == old) 266 old->rb_parent->rb_left = node; 267 else 268 old->rb_parent->rb_right = node; 269 } else 270 root->rb_node = node; 271 272 old->rb_left->rb_parent = node; 273 if (old->rb_right) 274 old->rb_right->rb_parent = node; 275 goto color; 276 } 277 278 parent = node->rb_parent; 279 color = node->rb_color; 280 281 if (child) 282 child->rb_parent = parent; 283 if (parent) 284 { 285 if (parent->rb_left == node) 286 parent->rb_left = child; 287 else 288 parent->rb_right = child; 289 } 290 else 291 root->rb_node = child; 292 293 color: 294 if (color == RB_BLACK) 295 __rb_erase_color(child, parent, root); 296 } 297 EXPORT_SYMBOL(rb_erase); 298 299 /* 300 * This function returns the first node (in sort order) of the tree. 301 */ 302 struct rb_node *rb_first(struct rb_root *root) 303 { 304 struct rb_node *n; 305 306 n = root->rb_node; 307 if (!n) 308 return NULL; 309 while (n->rb_left) 310 n = n->rb_left; 311 return n; 312 } 313 EXPORT_SYMBOL(rb_first); 314 315 struct rb_node *rb_last(struct rb_root *root) 316 { 317 struct rb_node *n; 318 319 n = root->rb_node; 320 if (!n) 321 return NULL; 322 while (n->rb_right) 323 n = n->rb_right; 324 return n; 325 } 326 EXPORT_SYMBOL(rb_last); 327 328 struct rb_node *rb_next(struct rb_node *node) 329 { 330 /* If we have a right-hand child, go down and then left as far 331 as we can. */ 332 if (node->rb_right) { 333 node = node->rb_right; 334 while (node->rb_left) 335 node=node->rb_left; 336 return node; 337 } 338 339 /* No right-hand children. Everything down and left is 340 smaller than us, so any 'next' node must be in the general 341 direction of our parent. Go up the tree; any time the 342 ancestor is a right-hand child of its parent, keep going 343 up. First time it's a left-hand child of its parent, said 344 parent is our 'next' node. */ 345 while (node->rb_parent && node == node->rb_parent->rb_right) 346 node = node->rb_parent; 347 348 return node->rb_parent; 349 } 350 EXPORT_SYMBOL(rb_next); 351 352 struct rb_node *rb_prev(struct rb_node *node) 353 { 354 /* If we have a left-hand child, go down and then right as far 355 as we can. */ 356 if (node->rb_left) { 357 node = node->rb_left; 358 while (node->rb_right) 359 node=node->rb_right; 360 return node; 361 } 362 363 /* No left-hand children. Go up till we find an ancestor which 364 is a right-hand child of its parent */ 365 while (node->rb_parent && node == node->rb_parent->rb_left) 366 node = node->rb_parent; 367 368 return node->rb_parent; 369 } 370 EXPORT_SYMBOL(rb_prev); 371 372 void rb_replace_node(struct rb_node *victim, struct rb_node *new, 373 struct rb_root *root) 374 { 375 struct rb_node *parent = victim->rb_parent; 376 377 /* Set the surrounding nodes to point to the replacement */ 378 if (parent) { 379 if (victim == parent->rb_left) 380 parent->rb_left = new; 381 else 382 parent->rb_right = new; 383 } else { 384 root->rb_node = new; 385 } 386 if (victim->rb_left) 387 victim->rb_left->rb_parent = new; 388 if (victim->rb_right) 389 victim->rb_right->rb_parent = new; 390 391 /* Copy the pointers/colour from the victim to the replacement */ 392 *new = *victim; 393 } 394 EXPORT_SYMBOL(rb_replace_node); 395