- struct interval_node *parent,
- struct interval_node **root)
-{
- struct interval_node *tmp;
- ENTRY;
-
- while (node_is_black_or_0(node) && node != *root) {
- if (parent->in_left == node) {
- tmp = parent->in_right;
- if (node_is_red(tmp)) {
- tmp->in_color = INTERVAL_BLACK;
- parent->in_color = INTERVAL_RED;
- __rotate_left(parent, root);
- tmp = parent->in_right;
- }
- if (node_is_black_or_0(tmp->in_left) &&
- node_is_black_or_0(tmp->in_right)) {
- tmp->in_color = INTERVAL_RED;
- node = parent;
- parent = node->in_parent;
- } else {
- if (node_is_black_or_0(tmp->in_right)) {
- struct interval_node *o_left;
- if ((o_left = tmp->in_left))
- o_left->in_color = INTERVAL_BLACK;
- tmp->in_color = INTERVAL_RED;
- __rotate_right(tmp, root);
- tmp = parent->in_right;
- }
- tmp->in_color = parent->in_color;
- parent->in_color = INTERVAL_BLACK;
- if (tmp->in_right)
- tmp->in_right->in_color = INTERVAL_BLACK;
- __rotate_left(parent, root);
- node = *root;
- break;
- }
- } else {
- tmp = parent->in_left;
- if (node_is_red(tmp)) {
- tmp->in_color = INTERVAL_BLACK;
- parent->in_color = INTERVAL_RED;
- __rotate_right(parent, root);
- tmp = parent->in_left;
- }
- if (node_is_black_or_0(tmp->in_left) &&
- node_is_black_or_0(tmp->in_right)) {
- tmp->in_color = INTERVAL_RED;
- node = parent;
- parent = node->in_parent;
- } else {
- if (node_is_black_or_0(tmp->in_left)) {
- struct interval_node *o_right;
- if ((o_right = tmp->in_right))
- o_right->in_color = INTERVAL_BLACK;
- tmp->in_color = INTERVAL_RED;
- __rotate_left(tmp, root);
- tmp = parent->in_left;
- }
- tmp->in_color = parent->in_color;
- parent->in_color = INTERVAL_BLACK;
- if (tmp->in_left)
- tmp->in_left->in_color = INTERVAL_BLACK;
- __rotate_right(parent, root);
- node = *root;
- break;
- }
- }
- }
- if (node)
- node->in_color = INTERVAL_BLACK;
- EXIT;
+ struct interval_node *parent,
+ struct interval_node **root)
+{
+ struct interval_node *tmp;
+
+ ENTRY;
+
+ while (node_is_black_or_0(node) && node != *root) {
+ if (parent->in_left == node) {
+ tmp = parent->in_right;
+ if (node_is_red(tmp)) {
+ tmp->in_color = INTERVAL_BLACK;
+ parent->in_color = INTERVAL_RED;
+ __rotate_left(parent, root);
+ tmp = parent->in_right;
+ }
+ if (node_is_black_or_0(tmp->in_left) &&
+ node_is_black_or_0(tmp->in_right)) {
+ tmp->in_color = INTERVAL_RED;
+ node = parent;
+ parent = node->in_parent;
+ } else {
+ if (node_is_black_or_0(tmp->in_right)) {
+ struct interval_node *o_left;
+
+ if ((o_left = tmp->in_left))
+ o_left->in_color =
+ INTERVAL_BLACK;
+ tmp->in_color = INTERVAL_RED;
+ __rotate_right(tmp, root);
+ tmp = parent->in_right;
+ }
+ tmp->in_color = parent->in_color;
+ parent->in_color = INTERVAL_BLACK;
+ if (tmp->in_right)
+ tmp->in_right->in_color =
+ INTERVAL_BLACK;
+ __rotate_left(parent, root);
+ node = *root;
+ break;
+ }
+ } else {
+ tmp = parent->in_left;
+ if (node_is_red(tmp)) {
+ tmp->in_color = INTERVAL_BLACK;
+ parent->in_color = INTERVAL_RED;
+ __rotate_right(parent, root);
+ tmp = parent->in_left;
+ }
+ if (node_is_black_or_0(tmp->in_left) &&
+ node_is_black_or_0(tmp->in_right)) {
+ tmp->in_color = INTERVAL_RED;
+ node = parent;
+ parent = node->in_parent;
+ } else {
+ if (node_is_black_or_0(tmp->in_left)) {
+ struct interval_node *o_right;
+
+ if ((o_right = tmp->in_right))
+ o_right->in_color =
+ INTERVAL_BLACK;
+ tmp->in_color = INTERVAL_RED;
+ __rotate_left(tmp, root);
+ tmp = parent->in_left;
+ }
+ tmp->in_color = parent->in_color;
+ parent->in_color = INTERVAL_BLACK;
+ if (tmp->in_left)
+ tmp->in_left->in_color = INTERVAL_BLACK;
+ __rotate_right(parent, root);
+ node = *root;
+ break;
+ }
+ }
+ }
+ if (node)
+ node->in_color = INTERVAL_BLACK;
+ EXIT;