typedef struct rbt_node_s  rbt_node_t;

struct rbt_node_s {
    rbt_key_t       key;
    rbt_node_t     *left;
    rbt_node_t     *right;
    rbt_node_t     *parent;
    u_char                 color;
    u_char                 data;
};


typedef struct rbt_s  rbt_t;

typedef void (*rbt_insert_pt) (rbt_node_t *root,
    rbt_node_t *node, rbt_node_t *sentinel);

struct rbt_s {
    rbt_node_t     *root;
    rbt_node_t     *sentinel;
    rbt_insert_pt   insert;
};

/*
if root is nil
    insert node to root and change to black
    return
insert a red node
loop if node not root && father is red:
    switch :
        case 1, father is black: 
            nothing todo
        case 2, father is red, uncle is red: 
            father and uncle change to black
            grandfather change to red
            now start to fix balance from grandfather, grandfather change to node
            continue loop
        case 3, father is red, uncle is black: 
            if (node is left child and father is right child) or (node is left right and father is left child)
                rotate father
            father change to black
            grandfather change to red
            rotate grandfather
change root to black 
*/
void
rbtree_insert(rbtree_t *tree, rbtree_node_t *node)
{
    rbtree_node_t  **root, *temp, *sentinel;

    /* a binary tree insert */

    root = &tree->root;
    sentinel = tree->sentinel;

    if (*root == sentinel) {
        node->parent = NULL;
        node->left = sentinel;
        node->right = sentinel;
        rbt_black(node);
        *root = node;

        return;
    }

    tree->insert(*root, node, sentinel);

    /* re-balance tree */

    while (node != *root && rbt_is_red(node->parent)) {

        if (node->parent == node->parent->parent->left) {
            temp = node->parent->parent->right;

            if (rbt_is_red(temp)) {
                rbt_black(node->parent);
                rbt_black(temp);
                rbt_red(node->parent->parent);
                node = node->parent->parent;

            } else {
                if (node == node->parent->right) {
                    node = node->parent;
                    rbtree_left_rotate(root, sentinel, node);
                }

                rbt_black(node->parent);
                rbt_red(node->parent->parent);
                rbtree_right_rotate(root, sentinel, node->parent->parent);
            }

        } else {
            temp = node->parent->parent->left;

            if (rbt_is_red(temp)) {
                rbt_black(node->parent);
                rbt_black(temp);
                rbt_red(node->parent->parent);
                node = node->parent->parent;

            } else {
                if (node == node->parent->left) {
                    node = node->parent;
                    rbtree_right_rotate(root, sentinel, node);
                }

                rbt_black(node->parent);
                rbt_red(node->parent->parent);
                rbtree_left_rotate(root, sentinel, node->parent->parent);
            }
        }
    }

    rbt_black(*root);
}

/*
delete node as rbt
    find subst where is used to replace node
    find temp whitch is used to replace subst
    use temp replace subst
    use subst replace node
if subst is red
    red node don't effect balance, no need to balance
    return
subst is black and subst has move, so need to balance
balance
    loop if temp not root && temp is black
        if temp is left child
            w is the brother of temp 
            if w is red
                w change to black
                temp's parent change to red(black ->red)
                left rotate temp's parent
                w update
                now w is not red
            if w is black && w's childs are black
                w change to red
                temp change to temp's parent(if temp is red, break the loop; temp change to red)
            if w is blcak && w's left child is red && w's right child is black
                w's left child change to black
                w change to red
                right rotate w
                update w
                now w is black && w's right child is red
            if w is black && w's right child is red
                w change to the color of temp's parent
                temp's parent change to black
                w's right child change to black
                right rotate w
                now balance(the side of temp add a black, so balance)
        if temp is right child
            ...
temp change to black
*/
void
rbtree_delete(rbtree_t *tree, rbtree_node_t *node)
{
    uint_t           red;
    rbtree_node_t  **root, *sentinel, *subst, *temp, *w;

    /* a binary tree delete */

    root = &tree->root;
    sentinel = tree->sentinel;

    if (node->left == sentinel) {
        temp = node->right;
        subst = node;

    } else if (node->right == sentinel) {
        temp = node->left;
        subst = node;

    } else {
        subst = rbtree_min(node->right, sentinel);
        temp = subst->right;
    }

    if (subst == *root) {
        *root = temp;
        rbt_black(temp);

        /* DEBUG stuff */
        node->left = NULL;
        node->right = NULL;
        node->parent = NULL;
        node->key = 0;

        return;
    }

    red = rbt_is_red(subst);

    if (subst == subst->parent->left) {
        subst->parent->left = temp;

    } else {
        subst->parent->right = temp;
    }

    if (subst == node) {

        temp->parent = subst->parent;

    } else {

        if (subst->parent == node) {
            temp->parent = subst;

        } else {
            temp->parent = subst->parent;
        }

        subst->left = node->left;
        subst->right = node->right;
        subst->parent = node->parent;
        rbt_copy_color(subst, node);

        if (node == *root) {
            *root = subst;

        } else {
            if (node == node->parent->left) {
                node->parent->left = subst;
            } else {
                node->parent->right = subst;
            }
        }

        if (subst->left != sentinel) {
            subst->left->parent = subst;
        }

        if (subst->right != sentinel) {
            subst->right->parent = subst;
        }
    }

    /* DEBUG stuff */
    node->left = NULL;
    node->right = NULL;
    node->parent = NULL;
    node->key = 0;

    if (red) {
        return;
    }

    /* a delete fixup */

    while (temp != *root && rbt_is_black(temp)) {

        if (temp == temp->parent->left) {
            w = temp->parent->right;

            if (rbt_is_red(w)) {
                rbt_black(w);
                rbt_red(temp->parent);
                rbtree_left_rotate(root, sentinel, temp->parent);
                w = temp->parent->right;
            }

            if (rbt_is_black(w->left) && rbt_is_black(w->right)) {
                rbt_red(w);
                temp = temp->parent;

            } else {
                if (rbt_is_black(w->right)) {
                    rbt_black(w->left);
                    rbt_red(w);
                    rbtree_right_rotate(root, sentinel, w);
                    w = temp->parent->right;
                }

                rbt_copy_color(w, temp->parent);
                rbt_black(temp->parent);
                rbt_black(w->right);
                rbtree_left_rotate(root, sentinel, temp->parent);
                temp = *root;
            }

        } else {
            w = temp->parent->left;

            if (rbt_is_red(w)) {
                rbt_black(w);
                rbt_red(temp->parent);
                rbtree_right_rotate(root, sentinel, temp->parent);
                w = temp->parent->left;
            }

            if (rbt_is_black(w->left) && rbt_is_black(w->right)) {
                rbt_red(w);
                temp = temp->parent;

            } else {
                if (rbt_is_black(w->left)) {
                    rbt_black(w->right);
                    rbt_red(w);
                    rbtree_left_rotate(root, sentinel, w);
                    w = temp->parent->left;
                }

                rbt_copy_color(w, temp->parent);
                rbt_black(temp->parent);
                rbt_black(w->left);
                rbtree_right_rotate(root, sentinel, temp->parent);
                temp = *root;
            }
        }
    }

    rbt_black(temp);
}