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