Linux kernel rb-tree (4)

这篇继续分析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)