- {
- node gp = *gparentp;
- node p = *parentp;
- /* There are two main cases:
- 1. The edge types (left or right) of the two red edges differ.
- 2. Both red edges are of the same type.
- There exist two symmetries of each case, so there is a total of
- 4 cases. */
- if ((p_r > 0) != (gp_r > 0))
- {
- /* Put the child at the top of the tree, with its parent
- and grandparent as successors. */
- p->red = 1;
- gp->red = 1;
- root->red = 0;
- if (p_r < 0)
- {
- /* Child is left of parent. */
- p->left = *rp;
- *rp = p;
- gp->right = *lp;
- *lp = gp;
- }
- else
- {
- /* Child is right of parent. */
- p->right = *lp;
- *lp = p;
- gp->left = *rp;
- *rp = gp;
- }
- *gparentp = root;
- }
- else
- {
- *gparentp = *parentp;
- /* Parent becomes the top of the tree, grandparent and
- child are its successors. */
- p->red = 0;
- gp->red = 1;
- if (p_r < 0)
- {
- /* Left edges. */
- gp->left = p->right;
- p->right = gp;
- }
- else
- {
- /* Right edges. */
- gp->right = p->left;
- p->left = gp;
- }
- }
- }
+ {
+ node gp = *gparentp;
+ node p = *parentp;
+ /* There are two main cases:
+ 1. The edge types (left or right) of the two red edges differ.
+ 2. Both red edges are of the same type.
+ There exist two symmetries of each case, so there is a total of
+ 4 cases. */
+ if ((p_r > 0) != (gp_r > 0))
+ {
+ /* Put the child at the top of the tree, with its parent
+ and grandparent as successors. */
+ p->red = 1;
+ gp->red = 1;
+ root->red = 0;
+ if (p_r < 0)
+ {
+ /* Child is left of parent. */
+ p->left = *rp;
+ *rp = p;
+ gp->right = *lp;
+ *lp = gp;
+ }
+ else
+ {
+ /* Child is right of parent. */
+ p->right = *lp;
+ *lp = p;
+ gp->left = *rp;
+ *rp = gp;
+ }
+ *gparentp = root;
+ }
+ else
+ {
+ *gparentp = *parentp;
+ /* Parent becomes the top of the tree, grandparent and
+ child are its successors. */
+ p->red = 0;
+ gp->red = 1;
+ if (p_r < 0)
+ {
+ /* Left edges. */
+ gp->left = p->right;
+ p->right = gp;
+ }
+ else
+ {
+ /* Right edges. */
+ gp->right = p->left;
+ p->left = gp;
+ }
+ }
+ }
- {
- node *pp = nodestack[sp - 1];
- p = *pp;
- /* Two symmetric cases. */
- if (r == p->left)
- {
- /* Q is R's brother, P is R's parent. The subtree with root
- R has one black edge less than the subtree with root Q. */
- q = p->right;
- if (q->red)
- {
- /* If Q is red, we know that P is black. We rotate P left
- so that Q becomes the top node in the tree, with P below
- it. P is colored red, Q is colored black.
- This action does not change the black edge count for any
- leaf in the tree, but we will be able to recognize one
- of the following situations, which all require that Q
- is black. */
- q->red = 0;
- p->red = 1;
- /* Left rotate p. */
- p->right = q->left;
- q->left = p;
- *pp = q;
- /* Make sure pp is right if the case below tries to use
- it. */
- nodestack[sp++] = pp = &q->left;
- q = p->right;
- }
- /* We know that Q can't be NULL here. We also know that Q is
- black. */
- if ((q->left == NULL || !q->left->red)
- && (q->right == NULL || !q->right->red))
- {
- /* Q has two black successors. We can simply color Q red.
- The whole subtree with root P is now missing one black
- edge. Note that this action can temporarily make the
- tree invalid (if P is red). But we will exit the loop
- in that case and set P black, which both makes the tree
- valid and also makes the black edge count come out
- right. If P is black, we are at least one step closer
- to the root and we'll try again the next iteration. */
- q->red = 1;
- r = p;
- }
- else
- {
- /* Q is black, one of Q's successors is red. We can
- repair the tree with one operation and will exit the
- loop afterwards. */
- if (q->right == NULL || !q->right->red)
- {
- /* The left one is red. We perform the same action as
- in maybe_split_for_insert where two red edges are
- adjacent but point in different directions:
- Q's left successor (let's call it Q2) becomes the
- top of the subtree we are looking at, its parent (Q)
- and grandparent (P) become its successors. The former
- successors of Q2 are placed below P and Q.
- P becomes black, and Q2 gets the color that P had.
- This changes the black edge count only for node R and
- its successors. */
- node q2 = q->left;
- q2->red = p->red;
- p->right = q2->left;
- q->left = q2->right;
- q2->right = q;
- q2->left = p;
- *pp = q2;
- p->red = 0;
- }
- else
- {
- /* It's the right one. Rotate P left. P becomes black,
- and Q gets the color that P had. Q's right successor
- also becomes black. This changes the black edge
- count only for node R and its successors. */
- q->red = p->red;
- p->red = 0;
-
- q->right->red = 0;
-
- /* left rotate p */
- p->right = q->left;
- q->left = p;
- *pp = q;
- }
-
- /* We're done. */
- sp = 1;
- r = NULL;
- }
- }
- else
- {
- /* Comments: see above. */
- q = p->left;
- if (q->red)
- {
- q->red = 0;
- p->red = 1;
- p->left = q->right;
- q->right = p;
- *pp = q;
- nodestack[sp++] = pp = &q->right;
- q = p->left;
- }
- if ((q->right == NULL || !q->right->red)
- && (q->left == NULL || !q->left->red))
- {
- q->red = 1;
- r = p;
- }
- else
- {
- if (q->left == NULL || !q->left->red)
- {
- node q2 = q->right;
- q2->red = p->red;
- p->left = q2->right;
- q->right = q2->left;
- q2->left = q;
- q2->right = p;
- *pp = q2;
- p->red = 0;
- }
- else
- {
- q->red = p->red;
- p->red = 0;
- q->left->red = 0;
- p->left = q->right;
- q->right = p;
- *pp = q;
- }
- sp = 1;
- r = NULL;
- }
- }
- --sp;
- }
+ {
+ node *pp = nodestack[sp - 1];
+ p = *pp;
+ /* Two symmetric cases. */
+ if (r == p->left)
+ {
+ /* Q is R's brother, P is R's parent. The subtree with root
+ R has one black edge less than the subtree with root Q. */
+ q = p->right;
+ if (q->red)
+ {
+ /* If Q is red, we know that P is black. We rotate P left
+ so that Q becomes the top node in the tree, with P below
+ it. P is colored red, Q is colored black.
+ This action does not change the black edge count for any
+ leaf in the tree, but we will be able to recognize one
+ of the following situations, which all require that Q
+ is black. */
+ q->red = 0;
+ p->red = 1;
+ /* Left rotate p. */
+ p->right = q->left;
+ q->left = p;
+ *pp = q;
+ /* Make sure pp is right if the case below tries to use
+ it. */
+ nodestack[sp++] = pp = &q->left;
+ q = p->right;
+ }
+ /* We know that Q can't be NULL here. We also know that Q is
+ black. */
+ if ((q->left == NULL || !q->left->red)
+ && (q->right == NULL || !q->right->red))
+ {
+ /* Q has two black successors. We can simply color Q red.
+ The whole subtree with root P is now missing one black
+ edge. Note that this action can temporarily make the
+ tree invalid (if P is red). But we will exit the loop
+ in that case and set P black, which both makes the tree
+ valid and also makes the black edge count come out
+ right. If P is black, we are at least one step closer
+ to the root and we'll try again the next iteration. */
+ q->red = 1;
+ r = p;
+ }
+ else
+ {
+ /* Q is black, one of Q's successors is red. We can
+ repair the tree with one operation and will exit the
+ loop afterwards. */
+ if (q->right == NULL || !q->right->red)
+ {
+ /* The left one is red. We perform the same action as
+ in maybe_split_for_insert where two red edges are
+ adjacent but point in different directions:
+ Q's left successor (let's call it Q2) becomes the
+ top of the subtree we are looking at, its parent (Q)
+ and grandparent (P) become its successors. The former
+ successors of Q2 are placed below P and Q.
+ P becomes black, and Q2 gets the color that P had.
+ This changes the black edge count only for node R and
+ its successors. */
+ node q2 = q->left;
+ q2->red = p->red;
+ p->right = q2->left;
+ q->left = q2->right;
+ q2->right = q;
+ q2->left = p;
+ *pp = q2;
+ p->red = 0;
+ }
+ else
+ {
+ /* It's the right one. Rotate P left. P becomes black,
+ and Q gets the color that P had. Q's right successor
+ also becomes black. This changes the black edge
+ count only for node R and its successors. */
+ q->red = p->red;
+ p->red = 0;
+
+ q->right->red = 0;
+
+ /* left rotate p */
+ p->right = q->left;
+ q->left = p;
+ *pp = q;
+ }
+
+ /* We're done. */
+ sp = 1;
+ r = NULL;
+ }
+ }
+ else
+ {
+ /* Comments: see above. */
+ q = p->left;
+ if (q->red)
+ {
+ q->red = 0;
+ p->red = 1;
+ p->left = q->right;
+ q->right = p;
+ *pp = q;
+ nodestack[sp++] = pp = &q->right;
+ q = p->left;
+ }
+ if ((q->right == NULL || !q->right->red)
+ && (q->left == NULL || !q->left->red))
+ {
+ q->red = 1;
+ r = p;
+ }
+ else
+ {
+ if (q->left == NULL || !q->left->red)
+ {
+ node q2 = q->right;
+ q2->red = p->red;
+ p->left = q2->right;
+ q->right = q2->left;
+ q2->left = q;
+ q2->right = p;
+ *pp = q2;
+ p->red = 0;
+ }
+ else
+ {
+ q->red = p->red;
+ p->red = 0;
+ q->left->red = 0;
+ p->left = q->right;
+ q->right = p;
+ *pp = q;
+ }
+ sp = 1;
+ r = NULL;
+ }
+ }
+ --sp;
+ }
projects / gnulib.git / blobdiff