if (p->rtrb_color == RTRB_BLACK) { for (; k > 1; k--) { struct rtrb_node *x; if (da[k - 1] == 0 || pa[k - 1]->rtrb_rtag == RTRB_CHILD) x = pa[k - 1]->rtrb_link[da[k - 1]]; else x = NULL; if (x != NULL && x->rtrb_color == RTRB_RED) { x->rtrb_color = RTRB_BLACK; break; } if (da[k - 1] == 0) { struct rtrb_node *w = pa[k - 1]->rtrb_link[1]; if (w->rtrb_color == RTRB_RED) { w->rtrb_color = RTRB_BLACK; pa[k - 1]->rtrb_color = RTRB_RED; pa[k - 1]->rtrb_link[1] = w->rtrb_link[0]; w->rtrb_link[0] = pa[k - 1]; pa[k - 2]->rtrb_link[da[k - 2]] = w; pa[k] = pa[k - 1]; da[k] = 0; pa[k - 1] = w; k++; w = pa[k - 1]->rtrb_link[1]; } if ((w->rtrb_link[0] == NULL || w->rtrb_link[0]->rtrb_color == RTRB_BLACK) && (w->rtrb_rtag == RTRB_THREAD || w->rtrb_link[1]->rtrb_color == RTRB_BLACK)) { w->rtrb_color = RTRB_RED; } else { if (w->rtrb_rtag == RTRB_THREAD || w->rtrb_link[1]->rtrb_color == RTRB_BLACK) { struct rtrb_node *y = w->rtrb_link[0]; y->rtrb_color = RTRB_BLACK; w->rtrb_color = RTRB_RED; w->rtrb_link[0] = y->rtrb_link[1]; y->rtrb_link[1] = w; w = pa[k - 1]->rtrb_link[1] = y; if (w->rtrb_rtag == RTRB_THREAD) { w->rtrb_rtag = RTRB_CHILD; w->rtrb_link[1]->rtrb_link[0] = NULL; } } w->rtrb_color = pa[k - 1]->rtrb_color; pa[k - 1]->rtrb_color = RTRB_BLACK; w->rtrb_link[1]->rtrb_color = RTRB_BLACK; pa[k - 1]->rtrb_link[1] = w->rtrb_link[0]; w->rtrb_link[0] = pa[k - 1]; pa[k - 2]->rtrb_link[da[k - 2]] = w; if (w->rtrb_link[0]->rtrb_link[1] == NULL) { w->rtrb_link[0]->rtrb_rtag = RTRB_THREAD; w->rtrb_link[0]->rtrb_link[1] = w; } break; } } else { struct rtrb_node *w = pa[k - 1]->rtrb_link[0]; if (w->rtrb_color == RTRB_RED) { w->rtrb_color = RTRB_BLACK; pa[k - 1]->rtrb_color = RTRB_RED; pa[k - 1]->rtrb_link[0] = w->rtrb_link[1]; w->rtrb_link[1] = pa[k - 1]; pa[k - 2]->rtrb_link[da[k - 2]] = w; pa[k] = pa[k - 1]; da[k] = 1; pa[k - 1] = w; k++; w = pa[k - 1]->rtrb_link[0]; } if ((w->rtrb_link[0] == NULL || w->rtrb_link[0]->rtrb_color == RTRB_BLACK) && (w->rtrb_rtag == RTRB_THREAD || w->rtrb_link[1]->rtrb_color == RTRB_BLACK)) { w->rtrb_color = RTRB_RED; } else { if (w->rtrb_link[0] == NULL || w->rtrb_link[0]->rtrb_color == RTRB_BLACK) { struct rtrb_node *y = w->rtrb_link[1]; y->rtrb_color = RTRB_BLACK; w->rtrb_color = RTRB_RED; w->rtrb_link[1] = y->rtrb_link[0]; y->rtrb_link[0] = w; w = pa[k - 1]->rtrb_link[0] = y; if (w->rtrb_link[0]->rtrb_link[1] == NULL) { w->rtrb_link[0]->rtrb_rtag = RTRB_THREAD; w->rtrb_link[0]->rtrb_link[1] = w; } } w->rtrb_color = pa[k - 1]->rtrb_color; pa[k - 1]->rtrb_color = RTRB_BLACK; w->rtrb_link[0]->rtrb_color = RTRB_BLACK; pa[k - 1]->rtrb_link[0] = w->rtrb_link[1]; w->rtrb_link[1] = pa[k - 1]; pa[k - 2]->rtrb_link[da[k - 2]] = w; if (w->rtrb_rtag == RTRB_THREAD) { w->rtrb_rtag = RTRB_CHILD; pa[k - 1]->rtrb_link[0] = NULL; } break; } } } if (tree->rtrb_root != NULL) tree->rtrb_root->rtrb_color = RTRB_BLACK; }