Linux kernel rb-tree (5)

本文继续分析__rb_insert，进入当父节点是红色节点的处理逻辑，开始有点复杂了

• 前情提要
  上文 分析了退出主循环的条件：parent 为空或者parent 的颜色为黑色; 还说明了rb_set_parent_color函数。
  第一篇 说了红黑树的几个原则。

• 正文

// 下面进入父节点是红色节点的处理逻辑

static __always_inline void
__rb_insert(struct rb_node *node, struct rb_root *root,
            void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
        struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;

        while (true) {

                // ...
                // 首先获取 grand parent 地址（红色节点的 __rb_parent_color 就是 parent 的地址)
                gparent = rb_red_parent(parent);

                // 获取 grand parent 的 右子节点
                tmp = gparent->rb_right;

                // 根据 parent 是 grand parent 的左 or 右子节点，进入第一层分支
                if (parent != tmp) {    /* parent == gparent->rb_left */
                        // 第一个待调整的情况:
                        //      - parent 是红色，grand parent是黑色
                        //      - parent 是 grand parent 的左子节点
                        //      - grand parent 的右子节点不为空
                        //      - grand parent 的右子节点为红色
                        // 如下图所示：G -> grand parent, p -> parent, u -> uncle, n -> node
                        // 大写表示 Black, 小写表示 Red
                        if (tmp && rb_is_red(tmp)) {
                                /*
                                 * Case 1 - color flips
                                 *
                                 *       G            g
                                 *      / \          / \
                                 *     p   u  -->   P   U
                                 *    /            /
                                 *   n            N
                                 *
                                 * However, since g's parent might be red, and
                                 * 4) does not allow this, we need to recurse
                                 * at g.
                                 */

                                // uncle 设置成黑色
                                rb_set_parent_color(tmp, gparent, RB_BLACK);
                                // parent 设置成黑色
                                rb_set_parent_color(parent, gparent, RB_BLACK);

                                // grand parent 设置成红色
                                node = gparent;
                                parent = rb_parent(node);
                                rb_set_parent_color(node, parent, RB_RED);

                                // 以grand parent 为 node， 它父节点为parent，继续循环
                                // 但是node什么时候变黑的???
                                continue;

                            
                        }
                }else{
                        // ...
                }
        }
}

#define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))

#define rb_is_red(rb)      __rb_is_red((rb)->__rb_parent_color)
#define __rb_is_red(pc)    (!__rb_color(pc))
#define __rb_color(pc)     ((pc) & 1)