本文继续分析__rb_insert，进入当父节点是红色节点的处理逻辑，开始有点复杂了
- 正文
// 下面进入父节点是红色节点的处理逻辑
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)
