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