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