红黑树(二)——linux 内核的设计实现

本文介绍了红黑树在linux kernel中实现，使用的内核版本为：centos 3.10.0-693.11.6

内核中的实现

源码位置

内核中关于红黑树的文件如下：

1
2
3
4
5


include/linux/rbtree_augmented.h
include/linux/rbtree.h
lib/rbtree.c 
lib/rbtree_test.c 
Documentation/rbtree.txt

rb_node

先说说红黑树的基本数据结构吧：

1
2
3
4
5
6
7
8


//本结构体四字节对齐，因而其地址中低位两个bit永远是0
//内核中用其中一个空闲的位来存储颜色信息
//__rb_parent_color成员实际上包含了父节点指针和自己的颜色信息
struct rb_node {
        unsigned long  __rb_parent_color; //保存父节点的指针值（父节点的地址）同时保存节点的color
        struct rb_node *rb_right;
        struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));

rb_node结构体描述了红黑树中的一个结点，但在linux的实现中没有key域，这是linux数据结构的一大特色，就是结构不包括数据，而是由数据和基本结构被包括在同一个struct中，就像list_head中没有data域，需要用链表的struct中要包含list_head域一样。（由结构体获取数据信息是通过container_of这个宏来实现的，它利用了一些编译器的特性，有兴趣的可以参考Linux的链表源码。）

rb_node结构体，被一个__attribute__((aligned(sizeof(long))))所包装(非常重要，技巧就在这!)， __attribute__((aligned(sizeof(long))))的意思是把结构体的地址按sizeof(long)对齐，对于32位机,sizeof(long)为4(即结构体内的数据类型的地址为4的倍数) ,对于64位机，sizeof(long)为8(即结构体内的数据类型的地址为8的倍数)。

所以以4（或8）为倍数的地址以二进制表示的特点是：以4为倍数(字节对齐)的地址（32位机器）最后两位肯定为零(看好了是存储变量的地址，而不是变量)，对于64位机器是后三位肯定为零。

对于红黑树中每一个节点，都需要标记一个颜色(要么是红、要么是黑)，而这里的技巧就在__attribute__((aligned(sizeof(long)))),因为红黑树的每个节点都用rb_node结构来表示，利用字节对齐技巧，任何rb_node结构体的地址的低两位肯定都是零，与其空着不用，还不如用它们表示颜色，反正颜色就两种，其实一位就已经够了。unsigned long rb_parent_color变量有两个作用（见名知义）：

存储父节点的地址
用后2位，标识此节点的color

rb_parent_color 相关的宏

rb_parent_color 成员保存了上提到的两个重要的信息，include/linux/rbtree_augmented.h和include/linux/rbtree.h有些与其相关的宏：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


 //获得父结点的地址
#define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))
#define __rb_parent(pc)    ((struct rb_node *)(pc & ~3))

// 判断结点的颜色
#define __rb_color(pc)     ((pc) & 1)
#define __rb_is_black(pc)  __rb_color(pc)
#define __rb_is_red(pc)    (!__rb_color(pc))
#define rb_color(rb)       __rb_color((rb)->__rb_parent_color)
#define rb_is_red(rb)      __rb_is_red((rb)->__rb_parent_color)
#define rb_is_black(rb)    __rb_is_black((rb)->__rb_parent_color)

// 设置结点的父结点
static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) 
{
        rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
}

// 设置结点的父结点和颜色
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;
}

//设置结点颜色为黑色
static inline void rb_set_black(struct rb_node *rb)
{
        rb->__rb_parent_color |= RB_BLACK;
}

基本接口

rb_erase：删除结点
rb_insert_color：插入结点

用于遍历的接口

rb_first: 寻找中序遍历的第一个结点，即最左的结点
rb_last: 寻找中序遍历的最后一个结点，即最右的结点
rb_next: 寻找中序遍历的下一个结点
rb_prev: 寻找中序遍历的上一个结点
rb_next_postorder: 找后续遍历的下一个结点
rb_first_postorder: 找后续遍历的第一个结点
rbtree_postorder_for_each_entry_safe：后续遍历红黑树

其他接口

rb_insert_augmented：增强的插入接口
__rb_insert_augmented：增强的插入接口

内核或者模块中红黑树的使用方法

本来想详细写内核中如何使用红黑树的，发现内核中的红黑树的测试代码逻辑很清晰，大家可以参考，代码位置：lib/rbtree_test.c。

另外，内核中的红黑树实现了增强的接口，称之为Augmented rbtrees，具体信息，请参阅：https://elixir.bootlin.com/linux/v4.17/source/Documentation/rbtree.txt#L229

Contents