rbtree

#define RED 0
#define BLACK 1
#define MASK 3

#define container_of(pointer, type, member) (type *) ((char*)pointer - offsetof(type, member));
struct rb_node {
        int key; /**just for test***/
        unsigned long parent_color; //
        struct rb_node *lchild;
        struct rb_node *rchild;
};
struct rb_head {
        //int count;
        struct rb_node *head;
};

void init_head(struct rb_head *root)
{
        root->head = NULL;
}

bool is_red(struct rb_node *node)
{
        unsigned long color;
        if (node)
                color = node->parent_color & MASK;
        else
                color = BLACK;
        return color == RED;
}

#define is_black(node) (!is_red(node))
/**** color == -1 表示color颜色不变****/
static inline void set_parent_color(struct rb_node *node, \
                struct rb_node *p, int color)
{
        if (node) {
                if (color == -1)
                        color = node->parent_color & MASK;
                node->parent_color = (unsigned long) p | color;
        }
}

struct rb_node *get_parent(struct rb_node *node)
{
        if (node)
                return (struct rb_node *) (node->parent_color & ~MASK);
        else
                return NULL;
}


/*(which) must be pointed to the address of one of parent's children*/
void rb_new_link(struct rb_node *new, struct rb_node *parent,\
                struct rb_node **which)
{
        new->parent_color = (unsigned long) parent;
        new->lchild = new->rchild = NULL;
        *which = new;
}

static void rb_change_link(struct rb_node *new, struct rb_node *old, \
                struct rb_node *father, struct rb_head *root)
{
        if (father) {
                if (old == father->lchild)
                        father->lchild = new;
                else
                        father->rchild = new;
        } else
                root->head = new;
}void rb_insert(struct rb_node *new, struct rb_head *root)
{
        struct rb_node *parent, *gp, *tmp;

        parent = get_parent(new);
        while (true) {
                /*case 1; reach the root*/
                if (!parent) {
                        set_parent_color(new, NULL, BLACK);
                        break;
                }
                /*case 2: father is black*/
                if (is_black(parent))
                        break;

                gp = get_parent(parent);

                /*case 3: father is red, uncle is red*/
                if (is_red(gp->lchild) && is_red(gp->rchild)) {
                        set_parent_color(gp->lchild, gp, BLACK);
                        set_parent_color(gp->rchild, gp, BLACK);

                        new = gp;
                        parent = get_parent(new);
                        set_parent_color(new, parent, RED);
                        continue;
                }
                /*case 4: father is red, uncle is black*/
                if (gp->lchild == parent) {
                        if (new == parent->rchild) {

                                parent->rchild = new->lchild;
                                new->lchild = parent;
                                /*after rotating, didn't chage new's father*/
                                set_parent_color(parent->rchild, parent, BLACK);
                                set_parent_color(parent, new, RED);

                                tmp = parent;
                                parent = new;
                                new = tmp;
                                /***need do a right rotate followed***/
                        }
              tmp = get_parent(gp); //record the gp's father

                        gp->lchild = parent->rchild;
                        parent->rchild = gp;

                        set_parent_color(gp->lchild, gp, BLACK);
                        set_parent_color(gp, parent, RED);
                        set_parent_color(parent, tmp, BLACK);

                        rb_change_link(parent, gp, tmp, root);
                        break;
                } else {
                        if (new == parent->lchild) {
                                parent->lchild = new->rchild;
                                new->rchild = parent;

                                set_parent_color(parent->lchild, parent, BLACK);
                                set_parent_color(parent, new, RED);

                                tmp = parent;
                                parent = new;
                                new = tmp;
                        }
  tmp = get_parent(gp);

                        gp->rchild = parent->lchild;
                        parent->lchild = gp;

                        set_parent_color(gp->rchild, gp, BLACK);
                        set_parent_color(gp, parent, RED);
                        set_parent_color(parent, tmp, BLACK);

                        rb_change_link(parent, gp, tmp, root);
                        break;
                }
        }
}
void do_del(struct rb_node *parent, struct rb_head *root)
{
        struct rb_node *now, *sibling, *gp;
        struct rb_node *sl, *sr;

        now = NULL;

        while (true) {
                bool parent_is_red;
                gp = get_parent(parent);
                if (now == parent->lchild) {
                        sibling = parent->rchild;
                        /* case 1; sibling is red */
                        if (is_red(sibling)) {
                                parent->rchild = sibling->lchild;
                                sibling->lchild = parent;

                                set_parent_color(parent->rchild, parent, BLACK);
                                set_parent_color(parent, sibling, RED);
                                set_parent_color(sibling, gp, BLACK);

                                rb_change_link(sibling, parent, gp, root);
                                sibling = parent->rchild;

                        }

                        parent_is_red = is_red(parent);
                        sl = sibling->lchild;
                        sr = sibling->rchild;
                        /*case 2: sibling is black, sibling's children are black*/
 if (is_black(sl) && is_black(sr)) {

                                set_parent_color(sibling, parent, RED);
                                set_parent_color(parent, gp, BLACK);

                                if (parent_is_red || gp == NULL) //gp == NULL ,可以排除parent_is_black但gp==NULL
                                        break;
                                else if (gp){
                                        now = parent;
                                        parent = gp;
                                        continue;
                                }
                        }
                        /*case 3: sibling is balck, and slibling's lchild is red*/
                        if (is_red(sl) && is_black(sr)) {
                                sibling->lchild = sl->rchild;
                                sl->rchild = sibling;

                                set_parent_color(sibling->lchild, sibling, BLACK);
                                set_parent_color(sibling, sl, RED);
                                set_parent_color(sl, parent, BLACK);

                                sibling = sl;
                                sl = sibling->lchild;
                                sr = sibling->rchild;
                        }
                        /*case 4: sibling is black, and slibling's rchild is red*/
  parent->rchild = sl;
                        sibling->lchild = parent;

                        set_parent_color(parent->rchild, parent, -1);
                        set_parent_color(parent, sibling, BLACK);
                        set_parent_color(sr, sibling, BLACK);
                        if (parent_is_red)
                                set_parent_color(sibling, gp, RED);
                        else
                                set_parent_color(sibling, gp, BLACK);

                        rb_change_link(sibling, parent, gp, root);
                        break;
                } else {
                        sibling = parent->lchild;

                        if (is_red(sibling)) {
                                parent->lchild = sibling->rchild;
                                sibling->rchild = parent;

                                set_parent_color(parent->lchild, parent, BLACK);
                                set_parent_color(parent, sibling, RED);
                                set_parent_color(sibling, gp, BLACK);

                                rb_change_link(sibling, parent, gp, root);

                                sibling = parent->lchild;
                        }
 sl = sibling->lchild;
                        sr = sibling->rchild;
                        parent_is_red = is_red(parent);

                        if (is_black(sl) && is_black(sr)) {

                                set_parent_color(sibling, parent, RED);
                                set_parent_color(parent, gp, BLACK);

                                if (parent_is_red)
                                        break;
                                else if (gp) {
                                        now = parent;
                                        parent = gp;
                                        continue;
                                } else
                                        break;
                        }
 if (is_red(sr) && is_black(sl)) {
                                sibling->rchild = sr->lchild;
                                sr->lchild = sibling;

                                set_parent_color(sibling->rchild, sibling, BLACK);
                                set_parent_color(sibling, sr, RED);
                                set_parent_color(sr, parent, BLACK);

                                sibling = sr;
                                sl = sibling->lchild;
                                sr = sibling->rchild;
                        }

                        parent->lchild = sr;
                        sibling->rchild = parent;

                        set_parent_color(parent->lchild, parent, -1);
                        set_parent_color(parent, sibling, BLACK);
                        set_parent_color(sl, sibling, BLACK);

                        if (parent_is_red)
                                set_parent_color(sibling, gp, RED);
                        else
                                set_parent_color(sibling, gp, BLACK);

                        rb_change_link(sibling, parent, gp, root);
                        break;
                }
        }
}void rb_del(struct rb_node *node, struct rb_head *root)
{
        struct rb_node *child, *parent;
        struct rb_node *victim;

        victim = node;
        if (node->lchild && node->rchild) {
                victim = node->lchild;
                while (victim->rchild)
                        victim = victim->rchild;
        }

        parent = get_parent(victim);
        child = victim->lchild ? victim->lchild : victim->rchild;


/***now , node only has no more one child
*case 1: node is red and a real leaf; node is not root;
*case 2: node is black with a red child; node  maybe the root;
*case 3: node is black and real leaf; node maybe the root;
*/
 rb_change_link(child, victim, parent, root);
        /*case 2*/
        if (child)
                set_parent_color(child, parent, BLACK);
        /***case 3****/
        else if(is_black(victim) && parent)
                do_del(parent, root);
        if (victim != node) {
                *victim = *node;
                set_parent_color(victim->lchild, victim, -1);
                set_parent_color(victim->rchild, victim, -1);
                rb_change_link(victim, node, get_parent(node), root);
        }
}
void  del(struct rb_head *root, int key)
{
        struct test_elem *elem;
        struct rb_node *node, *parent;

        node = root->head;

        while (node) {
                int ret = cmp(key, node);
                if (ret < 0)
                        node = node->lchild;
                else if (ret > 0)
                        node = node->rchild;
                else
                        break;
        }

        if (node) {
                rb_del(node, root);
                elem = container_of(node, struct test_elem, node);
                free (elem);
        } else
                fprintf(stderr, "del : this key is not bound\n");
}
struct test_elem {
        int key;
        struct rb_node node;
};
static int cmp(int key, const struct rb_node *sec)
{
        struct test_elem *elem;
        elem = container_of(sec, struct test_elem, node);
        return key - elem->key;
}
void insert(struct rb_head *root, int key)
{
        struct rb_node *parent, **which;
        struct rb_node *node;
        struct test_elem *data;
        int ret;

        parent = root->head;
        which = &root->head; //-> prior to &
        while (*which) {
                parent = *which;
                ret = cmp(key, *which);
                if (ret < 0)
                        which = &(*which)->lchild;
                else if (ret > 0)
                        which = &(*which)->rchild;
                else
                        break;
        }

        if (*which) {
                fprintf(stderr, "my_insert: this key has been bound!\n");
        }else {
 data = malloc(sizeof(struct test_elem)); //suppose malloc always succeed
                data->key = key;
                node = &data->node;
                rb_new_link(node, parent, which);
                rb_insert(node, root);
        }

}
void do_travel(struct rb_node *node)
{
        struct rb_node *father;
        struct test_elem *elem;
        int key, f;
        char c;
        if (node) {
                do_travel(node->lchild);
                elem = container_of(node, struct test_elem, node);
                key = elem->key;

                father = get_parent(node);
                elem = container_of(father, struct test_elem, node);
                f = father ? elem->key : -1;

                c = is_red(node) ? 'r' : 'b';

                printf("%d:%c:%d    ", key, c, f);
                do_travel(node->rchild);
        }
}

void travel(struct rb_head *root)
{
        do_travel(root->head);
        printf("\n");
}
int main()
{
        struct rb_head root;
        init_head(&root);

        while (true);
        return 0;
}