linux 内核数据结构之红黑树.

时间:2021-12-15 12:06:45

转载:

http://www.cnblogs.com/haippy/archive/2012/09/02/2668099.html

https://zh.wikipedia.org/zh/%E7%BA%A2%E9%BB%91%E6%A0%91

  红黑树和avl树一样,是二叉平衡搜索树,目前内核中已经找不到avl树的代码,二叉平衡搜索树都是用红黑树的接口,因此红黑树还是比较重要的。在代码实现上,红黑树的节点插入和删除较avl树复杂,主要难度是在树的旋转和node的着色,这方面中文wiki上讲的已经很清楚,可以参考上面的链接,需要静下心来看。下面的内容给出红黑树的调用实例,达到帮助读者理解红黑树接口和阅读内核源码的目的。

 

正文:

Linux 内核红黑树的实现代码位于:lib/rbtree.c,同时头文件在 include/linux/rbtree.h 中,内核中很多模块都使用了红黑树,详细介绍参见内核文档 Documentation/rbtree.txt。

内核中红黑树定义如下:

 1 struct rb_node
 2 {
 3     unsigned long  rb_parent_color;
 4 #define    RB_RED        0
 5 #define    RB_BLACK    1
 6     struct rb_node *rb_right;
 7     struct rb_node *rb_left;
 8 } __attribute__((aligned(sizeof(long))));
 9 
10 struct rb_root
11 {
12     struct rb_node *rb_node;
13 };

在这里,重点需要理解rb_parent_color这个成员,粗略一看,这里似乎没有定义颜色的域,但这就是这里红黑树实现的一个巧妙的地方。rb_parent_color这个域其实同时包含了颜色信息以及父亲节点的指针,因为该域是一个long的类型,需要大小为sizeof(long)的对齐,那么在一般的32位机器上,其后两位的数值永远是0,于是可以拿其中的一位来表示颜色。事实上,这里就是使用了最低位来表示颜色信息。明白了这点,那么以下关于父亲指针和颜色信息的操作都比较容易理解了,其本质上都是对rb_parent_color的位进行操作。

 1 #define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3)) //低两位清0
 2 #define rb_color(r)   ((r)->rb_parent_color & 1)                       //取最后一位
 3 #define rb_is_red(r)   (!rb_color(r))                                  //最后一位为0?
 4 #define rb_is_black(r) rb_color(r)                                     //最后一位为1?
 5 #define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)    //最后一位置0
 6 #define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)   //最后一位置1
 7 
 8 static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) //设置父亲
 9 {
10     rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
11 }
12 static inline void rb_set_color(struct rb_node *rb, int color)          //设置颜色
13 {
14     rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
15 }

然后是几个宏定义:

1 #define RB_ROOT    (struct rb_root) { NULL, }                         //初始根节点指针
2 #define rb_entry(ptr, type, member) container_of(ptr, type, member)//包含ptr的结构体指针
3 #define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)              //判断树是否空
4 #define RB_EMPTY_NODE(node) (rb_parent(node) == node)              //判断节点是否空,父亲是否等于自身
5 #define RB_CLEAR_NODE(node) (rb_set_parent(node, node))            //设置节点为空,父亲等于自身

常用接口:

__rb_rotate_left和__rb_rotate_right就是对红黑树进行的左旋和右旋操作。注意,代码中的第一个if语句中是=而不是==,意思是先赋值,然后再对该值判断是否为空,如果不为空的情况下才设置该节点的父亲。这样代码显得非常简洁,但如果以为是==的比较,则可能会感到困惑,不够他这里也使用了两个小括号进行提示,因为一般情况只需一个括号即可。

1 void __rb_rotate_left(struct rb_node *node, struct rb_root *root);
2 void __rb_rotate_right(struct rb_node *node, struct rb_root *root);

而rb_insert_color则是把新插入的节点进行着色,并且修正红黑树使其达到平衡。

1 void rb_insert_color(struct rb_node *, struct rb_root *);

插入节点时需要把新节点指向其父亲节点,这可以通过rb_link_node函数完成:

1 void rb_link_node(struct rb_node * node, struct rb_node * parent, struct rb_node ** rb_link);

删除节点则通过rb_erase进行,然后通过__rb_erase_color进行红黑树的修正。

1 void rb_erase(struct rb_node *, struct rb_root *);
2 void __rb_erase_color(struct rb_node *node, struct rb_node *parent, struct rb_root *root);

可以通过调用rb_replace_node来替换一个节点,但是替换完成后并不会对红黑树做任何调整,所以如果新节点的值与被替换的值有所不同时,可能会出现问题。

1 void rb_replace_node(struct rb_node *old, struct rb_node *new, struct rb_root *tree);

另外有几个进行红黑树遍历的函数,其原理均非常简单,本质上就是这里的求后继、前驱、最小值、最大值的函数实现,不过这里的代码实现非常简洁和巧妙。

1 extern struct rb_node *rb_next(const struct rb_node *); //后继
2 extern struct rb_node *rb_prev(const struct rb_node *); //前驱
3 extern struct rb_node *rb_first(const struct rb_root *);//最小值
4 extern struct rb_node *rb_last(const struct rb_root *); //最大值

实际使用:

在使用内核的红黑树时,需将 struct rb_node 结构包含在自己的数据结构中,比如:

1  struct mynode {
2       struct rb_node node;
3       char *string;
4       /*more stuff of your structure hereby*/
5   };

可以通过container_of宏获取包含了 rb_node 结构的起始地址,也可以通过rb_entry(node, type, member),其实:

1 #define    rb_entry(ptr, type, member) container_of(ptr, type, member)

首先是搜索节点,基本思想就是根据二叉查找树的查找过程进行:

 1 struct mynode *my_search(struct rb_root *root, char *string)
 2 {
 3       struct rb_node *node = root->rb_node;
 4 
 5       while (node) {
 6           struct mynode *data = container_of(node, struct mynode, node);
 7         int result;
 8 
 9         result = strcmp(string, data->string);
10 
11         if (result < 0)
12               node = node->rb_left;
13         else if (result > 0)
14               node = node->rb_right;
15         else
16               return data;
17     }
18     return NULL;
19 }

然后是插入节点,需要在插入一个数据之前先要查找到适合插入的位置,然后将节点加入到树中并将树调整到平衡状态:

 1 int my_insert(struct rb_root *root, struct mynode *data)
 2 {
 3       struct rb_node **new = &(root->rb_node), *parent = NULL;
 4 
 5       /* Figure out where to put new node */
 6       while (*new) {
 7           struct mynode *this = container_of(*new, struct mynode, node);
 8           int result = strcmp(data->string, this->string);
 9 
10         parent = *new;
11           if (result < 0)
12               new = &((*new)->rb_left);
13           else if (result > 0)
14               new = &((*new)->rb_right);
15           else
16               return 0;
17       }
18 
19       /* Add new node and rebalance tree. */
20       rb_link_node(&data->node, parent, new);
21       rb_insert_color(&data->node, root);
22 
23     return 1;
24 }

释放某一节点空间:

 1 void my_free(struct mynode *node)
 2 {
 3     if (node != NULL) {
 4         if (node->string != NULL) {
 5             free(node->string);
 6             node->string = NULL;
 7         }
 8         free(node);
 9         node = NULL;
10     }
11 }

综合上面的代码:

 1 #define NUM_NODES 32
 2 
 3 int main()
 4 {
 5 
 6     struct mynode *mn[NUM_NODES];
 7 
 8     /* *insert */
 9     int i = 0;
10     for (; i < NUM_NODES; i++) {
11         mn[i] = (struct mynode *)malloc(sizeof(struct mynode));
12         mn[i]->string = (char *)malloc(sizeof(char) * 4);
13         sprintf(mn[i]->string, "%d", i);
14         my_insert(&mytree, mn[i]);
15     }
16     
17     /* *search */
18     struct rb_node *node;
19     for (node = rb_first(&mytree); node; node = rb_next(node))
20         printf("key = %s\n", rb_entry(node, struct mynode, node)->string);
21 
22     /* *delete */
23     printf("delete node 20: \n");
24     struct mynode *data = my_search(&mytree, "20");
25     if (data) {
26         rb_erase(&data->node, &mytree);
27         my_free(data);
28     }
29 
30 
31     /* *delete again*/
32     printf("delete node 10: \n");
33     data = my_search(&mytree, "10");
34     if (data) {
35         rb_erase(&data->node, &mytree);
36         my_free(data);
37     }
38 
39 
40     /* *delete once again*/
41     printf("delete node 15: \n");
42     data = my_search(&mytree, "15");
43     if (data) {
44         rb_erase(&data->node, &mytree);
45         my_free(data);
46     }
47 
48     /* *search again*/
49     printf("search again:\n");
50     for (node = rb_first(&mytree); node; node = rb_next(node))
51         printf("key = %s\n", rb_entry(node, struct mynode, node)->string);
52     return 0;
53 }