1 /* 2 Red Black Trees 3 (C) 1999 Andrea Arcangeli <andrea (at) suse.de> 4 (C) 2002 David Woodhouse <dwmw2 (at) 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 "rbtree.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 136 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, 137 struct rb_root *root) 138 { 139 struct rb_node *other; 140 141 while ((!node || rb_is_black(node)) && node != root->rb_node) 142 { 143 if (parent->rb_left == node) 144 { 145 other = parent->rb_right; 146 if (rb_is_red(other)) 147 { 148 rb_set_black(other); 149 rb_set_red(parent); 150 __rb_rotate_left(parent, root); 151 other = parent->rb_right; 152 } 153 if ((!other->rb_left || rb_is_black(other->rb_left)) && 154 (!other->rb_right || rb_is_black(other->rb_right))) 155 { 156 rb_set_red(other); 157 node = parent; 158 parent = rb_parent(node); 159 } 160 else 161 { 162 if (!other->rb_right || rb_is_black(other->rb_right)) 163 { 164 struct rb_node *o_left; 165 if ((o_left = other->rb_left)) 166 rb_set_black(o_left); 167 rb_set_red(other); 168 __rb_rotate_right(other, root); 169 other = parent->rb_right; 170 } 171 rb_set_color(other, rb_color(parent)); 172 rb_set_black(parent); 173 if (other->rb_right) 174 rb_set_black(other->rb_right); 175 __rb_rotate_left(parent, root); 176 node = root->rb_node; 177 break; 178 } 179 } 180 else 181 { 182 other = parent->rb_left; 183 if (rb_is_red(other)) 184 { 185 rb_set_black(other); 186 rb_set_red(parent); 187 __rb_rotate_right(parent, root); 188 other = parent->rb_left; 189 } 190 if ((!other->rb_left || rb_is_black(other->rb_left)) && 191 (!other->rb_right || rb_is_black(other->rb_right))) 192 { 193 rb_set_red(other); 194 node = parent; 195 parent = rb_parent(node); 196 } 197 else 198 { 199 if (!other->rb_left || rb_is_black(other->rb_left)) 200 { 201 register struct rb_node *o_right; 202 if ((o_right = other->rb_right)) 203 rb_set_black(o_right); 204 rb_set_red(other); 205 __rb_rotate_left(other, root); 206 other = parent->rb_left; 207 } 208 rb_set_color(other, rb_color(parent)); 209 rb_set_black(parent); 210 if (other->rb_left) 211 rb_set_black(other->rb_left); 212 __rb_rotate_right(parent, root); 213 node = root->rb_node; 214 break; 215 } 216 } 217 } 218 if (node) 219 rb_set_black(node); 220 } 221 222 void rb_erase(struct rb_node *node, struct rb_root *root) 223 { 224 struct rb_node *child, *parent; 225 int color; 226 227 if (!node->rb_left) 228 child = node->rb_right; 229 else if (!node->rb_right) 230 child = node->rb_left; 231 else 232 { 233 struct rb_node *old = node, *left; 234 235 node = node->rb_right; 236 while ((left = node->rb_left) != NULL) 237 node = left; 238 child = node->rb_right; 239 parent = rb_parent(node); 240 color = rb_color(node); 241 242 if (child) 243 rb_set_parent(child, parent); 244 if (parent == old) { 245 parent->rb_right = child; 246 parent = node; 247 } else 248 parent->rb_left = child; 249 250 node->rb_parent_color = old->rb_parent_color; 251 node->rb_right = old->rb_right; 252 node->rb_left = old->rb_left; 253 254 if (rb_parent(old)) 255 { 256 if (rb_parent(old)->rb_left == old) 257 rb_parent(old)->rb_left = node; 258 else 259 rb_parent(old)->rb_right = node; 260 } else 261 root->rb_node = node; 262 263 rb_set_parent(old->rb_left, node); 264 if (old->rb_right) 265 rb_set_parent(old->rb_right, node); 266 goto color; 267 } 268 269 parent = rb_parent(node); 270 color = rb_color(node); 271 272 if (child) 273 rb_set_parent(child, parent); 274 if (parent) 275 { 276 if (parent->rb_left == node) 277 parent->rb_left = child; 278 else 279 parent->rb_right = child; 280 } 281 else 282 root->rb_node = child; 283 284 color: 285 if (color == RB_BLACK) 286 __rb_erase_color(child, parent, root); 287 } 288 289 /* 290 * This function returns the first node (in sort order) of the tree. 291 */ 292 struct rb_node *rb_first(struct rb_root *root) 293 { 294 struct rb_node *n; 295 296 n = root->rb_node; 297 if (!n) 298 return NULL; 299 while (n->rb_left) 300 n = n->rb_left; 301 return n; 302 } 303 304 struct rb_node *rb_last(struct rb_root *root) 305 { 306 struct rb_node *n; 307 308 n = root->rb_node; 309 if (!n) 310 return NULL; 311 while (n->rb_right) 312 n = n->rb_right; 313 return n; 314 } 315 316 struct rb_node *rb_next(struct rb_node *node) 317 { 318 struct rb_node *parent; 319 320 if (rb_parent(node) == node) 321 return NULL; 322 323 /* If we have a right-hand child, go down and then left as far 324 as we can. */ 325 if (node->rb_right) { 326 node = node->rb_right; 327 while (node->rb_left) 328 node=node->rb_left; 329 return node; 330 } 331 332 /* No right-hand children. Everything down and left is 333 smaller than us, so any 'next' node must be in the general 334 direction of our parent. Go up the tree; any time the 335 ancestor is a right-hand child of its parent, keep going 336 up. First time it's a left-hand child of its parent, said 337 parent is our 'next' node. */ 338 while ((parent = rb_parent(node)) && node == parent->rb_right) 339 node = parent; 340 341 return parent; 342 } 343 344 struct rb_node *rb_prev(struct rb_node *node) 345 { 346 struct rb_node *parent; 347 348 if (rb_parent(node) == node) 349 return NULL; 350 351 /* If we have a left-hand child, go down and then right as far 352 as we can. */ 353 if (node->rb_left) { 354 node = node->rb_left; 355 while (node->rb_right) 356 node=node->rb_right; 357 return node; 358 } 359 360 /* No left-hand children. Go up till we find an ancestor which 361 is a right-hand child of its parent */ 362 while ((parent = rb_parent(node)) && node == parent->rb_left) 363 node = parent; 364 365 return parent; 366 } 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
