| 5248 | } |
| 5249 | |
| 5250 | static void tree_rebalance_remove(struct tree_s *t, struct node_s *parent, |
| 5251 | struct node_s *n) |
| 5252 | { |
| 5253 | struct node_s *tmp; |
| 5254 | while ((n == NULL || TREE_COLOR(n) == TREE_BLACK) && n != t->root) |
| 5255 | { |
| 5256 | if (TREE_LEFT(parent) == n) |
| 5257 | { |
| 5258 | tmp = TREE_RIGHT(parent); |
| 5259 | if (TREE_COLOR(tmp) == TREE_RED) |
| 5260 | { |
| 5261 | TREE_COLOR(tmp) = TREE_BLACK; |
| 5262 | TREE_COLOR(parent) = TREE_RED; |
| 5263 | tree_rotate_left(t, parent); |
| 5264 | tmp = TREE_RIGHT(parent); |
| 5265 | } |
| 5266 | if ((TREE_LEFT(tmp) == NULL || |
| 5267 | TREE_COLOR(TREE_LEFT(tmp)) == TREE_BLACK) && |
| 5268 | (TREE_RIGHT(tmp) == NULL || |
| 5269 | TREE_COLOR(TREE_RIGHT(tmp)) == TREE_BLACK)) |
| 5270 | { |
| 5271 | TREE_COLOR(tmp) = TREE_RED; |
| 5272 | n = parent; |
| 5273 | parent = TREE_PARENT(n); |
| 5274 | } |
| 5275 | else |
| 5276 | { |
| 5277 | if (TREE_RIGHT(tmp) == NULL || |
| 5278 | TREE_COLOR(TREE_RIGHT(tmp)) == TREE_BLACK) |
| 5279 | { |
| 5280 | struct node_s *oleft; |
| 5281 | if ((oleft = TREE_LEFT(tmp)) != NULL) |
| 5282 | TREE_COLOR(oleft) = TREE_BLACK; |
| 5283 | TREE_COLOR(tmp) = TREE_RED; |
| 5284 | tree_rotate_right(t, tmp); |
| 5285 | tmp = TREE_RIGHT(parent); |
| 5286 | } |
| 5287 | TREE_COLOR(tmp) = TREE_COLOR(parent); |
| 5288 | TREE_COLOR(parent) = TREE_BLACK; |
| 5289 | if (TREE_RIGHT(tmp)) |
| 5290 | TREE_COLOR(TREE_RIGHT(tmp)) = TREE_BLACK; |
| 5291 | tree_rotate_left(t, parent); |
| 5292 | n = t->root; |
| 5293 | break; |
| 5294 | } |
| 5295 | } |
| 5296 | else |
| 5297 | { |
| 5298 | tmp = TREE_LEFT(parent); |
| 5299 | if (TREE_COLOR(tmp) == TREE_RED) |
| 5300 | { |
| 5301 | TREE_COLOR(tmp) = TREE_BLACK; |
| 5302 | TREE_COLOR(parent) = TREE_RED; |
| 5303 | tree_rotate_right(t, parent); |
| 5304 | tmp = TREE_LEFT(parent); |
| 5305 | } |
| 5306 | if ((TREE_LEFT(tmp) == NULL || |
| 5307 | TREE_COLOR(TREE_LEFT(tmp)) == TREE_BLACK) && |
no test coverage detected