这篇继续分析API的实现细节，本文讲rb_insert_color
- 调用示例
static void __insert_vmap_area(struct vmap_area *va)
{
struct rb_node **p = &vmap_area_root.rb_node;
struct rb_node *parent = NULL;
struct rb_node *tmp;
// 遍历 rb_tree
while (*p) {
struct vmap_area *tmp_va;
parent = *p;
tmp_va = rb_entry(parent, struct vmap_area, rb_node);
// 比较，找到合适的插入位置
if (va->va_start < tmp_va->va_end)
p = &(*p)->rb_left;
else if (va->va_end > tmp_va->va_start)
p = &(*p)->rb_right;
else
BUG();
}
// 插入节点
rb_link_node(&va->rb_node, parent, p);
// 上色
rb_insert_color(&va->rb_node, &vmap_area_root);
//...
}
- 实现细节
void rb_insert_color(struct rb_node *node, struct rb_root *root)
{
__rb_insert(node, root, dummy_rotate);
}
EXPORT_SYMBOL(rb_insert_color);
static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {}
/**
* 功能：
* 没什么内容，简单的封装__rb_insert，多了个空函数dummy_rotate
* 参数：
* node - 待插入的节点(struct rb_node *) 跟rb_link_node一样
* root - 待插入的树的根节点地址 (struct rb_root *)
**/
进入__rb_insert
// lib/rbtree.c
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;
// ...
}
/*
* 参数：
* node - 待插入的节点(struct rb_node *) 跟 rb_link_node 一样
* root - 待插入的树的根节点地址 (struct rb_root *)
*
* 说明：
* - 上来先定义三个 rb_node 指针
* - rb_red_parent 并没有做什么事情，就是取 rb_node->__rb_parent_color
* - 由于参数 node 是 rb_link_node 处理过的 node, 所以取出的就是 parent 的地址
*
* */
static inline struct rb_node *rb_red_parent(struct rb_node *red)
{
return (struct rb_node *)red->__rb_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) {
/*
* Loop invariant: node is red
*
* If there is a black parent, we are done.
* Otherwise, take some corrective action as we don't
* want a red root or two consecutive red nodes.
*/
if (!parent) {
rb_set_parent_color(node, NULL, RB_BLACK);
break;
} else if (rb_is_black(parent))
break;
// ...
}
}
/*
* 说明：
* - 函数的主体是一个大循环体
* - 首先判断如果 parent 为空，表示 node 是插入的第一个节点，调用rb_set_parent_color 进行设置并退出循环
* - 如果 parent 不为空就判断 parent 的颜色是否是黑色，如果是就不需要调整直接退出循环（为什么呢？）
* - 回顾一下红黑树的几条原则，当 parent 为红色的时候，子节点必须是黑色， 而当parent为黑色的时候就没有限制
* - 而 rb_link_node 中设置 parent 地址的同时，实际上颜色已经设置为红色了(最低位是0)，所以这里也没有再调用rb_set_parent_color
* - 大概这也是上一步中那个函数叫 rb_red_parent 的原因
**/
static inline void rb_set_parent_color(struct rb_node *rb,
struct rb_node *p, int color)
{
rb->__rb_parent_color = (unsigned long)p | color;
}
/*
* 参数：
* rb - 当前需要设置的 node
* p - 当前 node 的 parent 地址
* color - 当前 node 的颜色
*
* 说明：
* - rb_set_parent_color 把当前节点的 __rb_parent_color 设置为父节点地址和 color 的`或运算`结果
* - rb_set_parent_color 这个函数名的含义其实是设置当前node的parent和当前node的color，而不是设置当前node的parent的color
*
* */
#define __rb_color(pc) ((pc) & 1)
#define __rb_is_black(pc) __rb_color(pc)
#define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color)
