Function rebalanceInsert

src/e9patch/e9alloc.cpp:168–223

}

static void rebalanceInsert(Tree *t, Node *n)
{
    Node *parent, *gparent, *tmp;
    for (Node *m = n; m != nullptr; m = RB_PARENT(m))
        fix(m);
    while ((parent = RB_PARENT(n)) != nullptr &&
                RB_COLOR(parent) == RB_RED)
    {
        gparent = RB_PARENT(parent);
        if (parent == RB_LEFT(gparent))
        {
            tmp = RB_RIGHT(gparent);
            if (tmp != nullptr && RB_COLOR(tmp) == RB_RED)
            {
                RB_COLOR(tmp)     = RB_BLACK;
                RB_COLOR(parent)  = RB_BLACK;
                RB_COLOR(gparent) = RB_RED;
                n = gparent;
                continue;
            }
            if (RB_RIGHT(parent) == n)
            {
                rotateLeft(t, parent);
                tmp = parent;
                parent = n;
                n = tmp;
            }
            RB_COLOR(parent)  = RB_BLACK;
            RB_COLOR(gparent) = RB_RED;
            rotateRight(t, gparent);
        }
        else
        {
            tmp = RB_LEFT(gparent);
            if (tmp != nullptr && RB_COLOR(tmp) == RB_RED)
            {
                RB_COLOR(tmp)     = RB_BLACK;
                RB_COLOR(parent)  = RB_BLACK;
                RB_COLOR(gparent) = RB_RED;
                n = gparent;
                continue;
            }
            if (RB_LEFT(parent) == n)
            {
                rotateRight(t, parent);
                tmp = parent;
                parent = n;
                n = tmp;
            }
            RB_COLOR(parent)  = RB_BLACK;
            RB_COLOR(gparent) = RB_RED;
            rotateLeft(t, gparent);
        }
    }
    RB_COLOR(t->root) = RB_BLACK;
}

static void rebalanceRemove(Tree *t, Node *parent, Node *n)