| 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; |
no test coverage detected