if (y->rtavl_balance == -2) { struct rtavl_node *x = y->rtavl_link[0]; if (x->rtavl_balance == -1) { w = x; if (x->rtavl_rtag == RTAVL_THREAD) { x->rtavl_rtag = RTAVL_CHILD; y->rtavl_link[0] = NULL; } else y->rtavl_link[0] = x->rtavl_link[1]; x->rtavl_link[1] = y; x->rtavl_balance = y->rtavl_balance = 0; } else { assert (x->rtavl_balance == +1); w = x->rtavl_link[1]; x->rtavl_link[1] = w->rtavl_link[0]; w->rtavl_link[0] = x; y->rtavl_link[0] = w->rtavl_link[1]; w->rtavl_link[1] = y; if (w->rtavl_balance == -1) x->rtavl_balance = 0, y->rtavl_balance = +1; else if (w->rtavl_balance == 0) x->rtavl_balance = y->rtavl_balance = 0; else /* |w->rtavl_balance == +1| */ x->rtavl_balance = -1, y->rtavl_balance = 0; w->rtavl_balance = 0; if (x->rtavl_link[1] == NULL) { x->rtavl_rtag = RTAVL_THREAD; x->rtavl_link[1] = w; } if (w->rtavl_rtag == RTAVL_THREAD) { y->rtavl_link[0] = NULL; w->rtavl_rtag = RTAVL_CHILD; } } } else if (y->rtavl_balance == +2) { struct rtavl_node *x = y->rtavl_link[1]; if (x->rtavl_balance == +1) { w = x; if (x->rtavl_link[0] == NULL) { y->rtavl_rtag = RTAVL_THREAD; y->rtavl_link[1] = x; } else y->rtavl_link[1] = x->rtavl_link[0]; x->rtavl_link[0] = y; x->rtavl_balance = y->rtavl_balance = 0; } else { assert (x->rtavl_balance == -1); w = x->rtavl_link[0]; x->rtavl_link[0] = w->rtavl_link[1]; w->rtavl_link[1] = x; y->rtavl_link[1] = w->rtavl_link[0]; w->rtavl_link[0] = y; if (w->rtavl_balance == +1) x->rtavl_balance = 0, y->rtavl_balance = -1; else if (w->rtavl_balance == 0) x->rtavl_balance = y->rtavl_balance = 0; else /* |w->rtavl_balance == -1| */ x->rtavl_balance = +1, y->rtavl_balance = 0; w->rtavl_balance = 0; if (y->rtavl_link[1] == NULL) { y->rtavl_rtag = RTAVL_THREAD; y->rtavl_link[1] = w; } if (w->rtavl_rtag == RTAVL_THREAD) { x->rtavl_link[0] = NULL; w->rtavl_rtag = RTAVL_CHILD; } } } else return &n->rtavl_data; z->rtavl_link[y != z->rtavl_link[0]] = w; return &n->rtavl_data;