| 313 | } |
| 314 | |
| 315 | static Node *remove(Tree *t, Node *n) |
| 316 | { |
| 317 | Node *child, *parent, *old = n; |
| 318 | size_t color; |
| 319 | if (RB_LEFT(n) == nullptr) |
| 320 | child = RB_RIGHT(n); |
| 321 | else if (RB_RIGHT(n) == nullptr) |
| 322 | child = RB_LEFT(n); |
| 323 | else |
| 324 | { |
| 325 | Node *left; |
| 326 | n = RB_RIGHT(n); |
| 327 | while ((left = RB_LEFT(n)) != nullptr) |
| 328 | n = left; |
| 329 | child = RB_RIGHT(n); |
| 330 | parent = RB_PARENT(n); |
| 331 | color = RB_COLOR(n); |
| 332 | if (child != nullptr) |
| 333 | RB_PARENT(child) = parent; |
| 334 | if (parent != nullptr) |
| 335 | { |
| 336 | if (RB_LEFT(parent) == n) |
| 337 | RB_LEFT(parent) = child; |
| 338 | else |
| 339 | RB_RIGHT(parent) = child; |
| 340 | fix(parent); |
| 341 | } |
| 342 | else |
| 343 | t->root = child; |
| 344 | if (RB_PARENT(n) == old) |
| 345 | parent = n; |
| 346 | RB_PARENT(n) = RB_PARENT(old); |
| 347 | RB_LEFT(n) = RB_LEFT(old); |
| 348 | RB_RIGHT(n) = RB_RIGHT(old); |
| 349 | RB_COLOR(n) = RB_COLOR(old); |
| 350 | if (RB_PARENT(old) != nullptr) |
| 351 | { |
| 352 | if (RB_LEFT(RB_PARENT(old)) == old) |
| 353 | RB_LEFT(RB_PARENT(old)) = n; |
| 354 | else |
| 355 | RB_RIGHT(RB_PARENT(old)) = n; |
| 356 | fix(RB_PARENT(old)); |
| 357 | } |
| 358 | else |
| 359 | t->root = n; |
| 360 | RB_PARENT(RB_LEFT(old)) = n; |
| 361 | if (RB_RIGHT(old) != nullptr) |
| 362 | RB_PARENT(RB_RIGHT(old)) = n; |
| 363 | if (parent) |
| 364 | { |
| 365 | left = parent; |
| 366 | do |
| 367 | { |
| 368 | fix(left); |
| 369 | } |
| 370 | while ((left = RB_PARENT(left)) != nullptr); |
| 371 | } |
| 372 | goto color; |
no test coverage detected