| 5193 | } |
| 5194 | |
| 5195 | static void tree_rebalance_insert(struct tree_s *t, struct node_s *n) |
| 5196 | { |
| 5197 | struct node_s *parent, *gparent, *tmp; |
| 5198 | while ((parent = TREE_PARENT(n)) != NULL && |
| 5199 | TREE_COLOR(parent) == TREE_RED) |
| 5200 | { |
| 5201 | gparent = TREE_PARENT(parent); |
| 5202 | if (parent == TREE_LEFT(gparent)) |
| 5203 | { |
| 5204 | tmp = TREE_RIGHT(gparent); |
| 5205 | if (tmp != NULL && TREE_COLOR(tmp) == TREE_RED) |
| 5206 | { |
| 5207 | TREE_COLOR(tmp) = TREE_BLACK; |
| 5208 | TREE_COLOR(parent) = TREE_BLACK; |
| 5209 | TREE_COLOR(gparent) = TREE_RED; |
| 5210 | n = gparent; |
| 5211 | continue; |
| 5212 | } |
| 5213 | if (TREE_RIGHT(parent) == n) |
| 5214 | { |
| 5215 | tree_rotate_left(t, parent); |
| 5216 | tmp = parent; |
| 5217 | parent = n; |
| 5218 | n = tmp; |
| 5219 | } |
| 5220 | TREE_COLOR(parent) = TREE_BLACK; |
| 5221 | TREE_COLOR(gparent) = TREE_RED; |
| 5222 | tree_rotate_right(t, gparent); |
| 5223 | } |
| 5224 | else |
| 5225 | { |
| 5226 | tmp = TREE_LEFT(gparent); |
| 5227 | if (tmp != NULL && TREE_COLOR(tmp) == TREE_RED) |
| 5228 | { |
| 5229 | TREE_COLOR(tmp) = TREE_BLACK; |
| 5230 | TREE_COLOR(parent) = TREE_BLACK; |
| 5231 | TREE_COLOR(gparent) = TREE_RED; |
| 5232 | n = gparent; |
| 5233 | continue; |
| 5234 | } |
| 5235 | if (TREE_LEFT(parent) == n) |
| 5236 | { |
| 5237 | tree_rotate_right(t, parent); |
| 5238 | tmp = parent; |
| 5239 | parent = n; |
| 5240 | n = tmp; |
| 5241 | } |
| 5242 | TREE_COLOR(parent) = TREE_BLACK; |
| 5243 | TREE_COLOR(gparent) = TREE_RED; |
| 5244 | tree_rotate_left(t, gparent); |
| 5245 | } |
| 5246 | } |
| 5247 | TREE_COLOR(t->root) = TREE_BLACK; |
| 5248 | } |
| 5249 | |
| 5250 | static void tree_rebalance_remove(struct tree_s *t, struct node_s *parent, |
| 5251 | struct node_s *n) |
no test coverage detected