免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 62778 | 回复: 72

Linux内核中的红黑树 [复制链接]

论坛徽章:
36
IT运维版块每日发帖之星
日期:2016-04-10 06:20:00IT运维版块每日发帖之星
日期:2016-04-16 06:20:0015-16赛季CBA联赛之广东
日期:2016-04-16 19:59:32IT运维版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-19 06:20:00每日论坛发贴之星
日期:2016-04-19 06:20:00IT运维版块每日发帖之星
日期:2016-04-25 06:20:00IT运维版块每日发帖之星
日期:2016-05-06 06:20:00IT运维版块每日发帖之星
日期:2016-05-08 06:20:00IT运维版块每日发帖之星
日期:2016-05-13 06:20:00IT运维版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-28 06:20:00
发表于 2008-12-31 10:36 |显示全部楼层
引用链接:http://www.kerneltravel.net/jiaoliu/kern-rbtree.html

红黑树是平衡二叉树的一种,它有很好的性质,树中的结点都是有序的,而且因为它本身就是平衡的,所以查找也不会出现非常恶劣的情况,基于二叉树的操作的时间复杂度是O(log(N))。Linux内核在管理vm_area_struct时就是采用了红黑树来维护内存块的。

先到include/linux/rbtree.h中看一下红黑树的一些定义,如下:
  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))));
复制代码
struct rb_root只是struct rb_node*的一个包装,这样做的好处是看起来不用传递二级指针了。不错,很简单。再看一下下面几个重要的宏,细心的你一定会发现,rb_parent_color其实没那么简单,Andrea Arcangeli在这里使用了一个小的技巧,不过非常棒。正如名字所暗示,这个成员其实包含指向parent的指针和此结点的颜色!它是怎么做到的呢?很简单,对齐起了作用。既然是sizeof(long)大小的对齐,那么在IA-32上,任何rb_node结构体的地址的低两位肯定都是零,与其空着不用,还不如用它们表示颜色,反正颜色就两种,其实一位就已经够了。

这样,提取parent指针只要把rb_parent_color成员的低两位清零即可:
  1. #define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))
复制代码
取颜色只要看最后一位即可:
  1. #define rb_color(r) ((r)->rb_parent_color & 1)
复制代码
测试颜色和设置颜色也是水到渠成的事了。需要特别指出的是下面的一个内联函数:
  1. static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, struct rb_node ** rb_link);
复制代码
它把parent设为node的父结点,并且让rb_link指向node。

我们把重点集中在lib/rbtree.c上,看看一些和红黑树相关的重要算法。开始之前我们一起回忆一下红黑树的规则:


1. 每个结点要么是红色要么是黑色;

2. 根结点必须是黑色;

3. 红结点如果有孩子,其孩子必须都是黑色;

4. 从根结点到叶子的每条路径必须包含相同数目的黑结点。

这四条规则可以限制一棵排序树是平衡的。

__rb_rotate_left是把以root为根的树中的node结点进行左旋,__rb_rotate_right是进行右旋。这两个函数是为后面的插入和删除服务,而不是为外部提供接口。

新插入的结点都设为叶子,染成红色,插入后如果破坏了上述规则,通过调整颜色和旋转可以恢复,二叉树又重新平衡。插入操作的接口函数是
  1. void rb_insert_color(struct rb_node *node, struct rb_root *root);
复制代码
它把已确定父结点的node结点融入到以root为根的红黑树中,具体算法的分析可以参考[1]中第14.3节,这里的实现和书中的讲解几乎完全一样。怎么确定node的父结点应该在调用rb_insert_color之前通过手工迭带完成。值得指出的一点是,虽然插入操作需要一个循环迭代,但是总的旋转次数不会超过两次!所以效率还是很乐观的。

删除操作多多少少都有点麻烦,它要先执行像普通二叉查找树的“删除”,然后根据删除结点的颜色来判断是否执行进一步的操作。删除的接口是:
  1. void rb_erase(struct rb_node *node, struct rb_root *root);
复制代码
其实它并没有真正删除node,而只是让它和以root为根的树脱离关系,最后它还要判断是否调用__rb_erase_color来调整。具体算法的讲解看参考[1]中第13.3和14.4节,__rb_erase_color对应书中的RB-DELETE-FIXUP,此处的实现和书上也基本上一致。

其余的几个接口就比较简单了。
  1. struct rb_node *rb_first(struct rb_root *root);
复制代码
在以root为根的树中找出并返回最小的那个结点,只要从根结点一直向左走就是了。
  1. struct rb_node *rb_last(struct rb_root *root);
复制代码
是找出并返回最大的那个,一直向右走。
  1. struct rb_node *rb_next(struct rb_node *node);
复制代码
返回node在树中的后继,这个稍微复杂一点。如果node的右孩子不为空,它只要返回node的右子树中最小的结点即可;如果为空,它要向上查找,找到迭带结点是其父亲的左孩子的结点,返回父结点。如果一直上述到了根结点,返回NULL。
  1. struct rb_node *rb_prev(struct rb_node *node);
复制代码
返回node的前驱,和rb_next中的操作对称。
  1. void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root);
复制代码
用new替换以root为根的树中的victim结点。

红黑树接口使用的一个典型例子如下:
  1. static inline struct page * rb_search_page_cache(struct inode * inode,
  2.                                                  unsigned long offset)
  3. {
  4.         struct rb_node * n = inode->i_rb_page_cache.rb_node;
  5.         struct page * page;

  6.         while (n)
  7.         {
  8.                 page = rb_entry(n, struct page, rb_page_cache);

  9.                 if (offset < page->offset)
  10.                         n = n->rb_left;
  11.                 else if (offset > page->offset)
  12.                         n = n->rb_right;
  13.                 else
  14.                         return page;
  15.         }
  16.         return NULL;
  17. }

  18. static inline struct page * __rb_insert_page_cache(struct inode * inode,
  19.                                                    unsigned long offset,
  20.                                                    struct rb_node * node)
  21. {
  22.         struct rb_node ** p = &inode->i_rb_page_cache.rb_node;
  23.         struct rb_node * parent = NULL;
  24.         struct page * page;

  25.         while (*p)
  26.         {
  27.                 parent = *p;
  28.                 page = rb_entry(parent, struct page, rb_page_cache);

  29.                 if (offset < page->offset)
  30.                         p = &(*p)->rb_left;
  31.                 else if (offset > page->offset)
  32.                         p = &(*p)->rb_right;
  33.                 else
  34.                         return page;
  35.         }

  36.         rb_link_node(node, parent, p);

  37.         return NULL;
  38. }

  39. static inline struct page * rb_insert_page_cache(struct inode * inode,
  40.                                                  unsigned long offset,
  41.                                                  struct rb_node * node)
  42. {
  43.         struct page * ret;
  44.         if ((ret = __rb_insert_page_cache(inode, offset, node)))
  45.                 goto out;
  46.         rb_insert_color(node, &inode->i_rb_page_cache);
  47. out:
  48.         return ret;
  49. }
复制代码
因为红黑树的这些良好性质和实现中接口的简易性,它被广泛应用到内核编程中,大大提高了内核的效率。



参考资料:


1. Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, MIT Press.

2. Understanding the Linux Kernel, 3rd Edition, Daniel P. Bovet, Marco Cesati, O'Reilly.

3. Linux Kernel 2.6.19 source code.

[ 本帖最后由 Godbach 于 2009-2-25 16:34 编辑 ]

论坛徽章:
36
IT运维版块每日发帖之星
日期:2016-04-10 06:20:00IT运维版块每日发帖之星
日期:2016-04-16 06:20:0015-16赛季CBA联赛之广东
日期:2016-04-16 19:59:32IT运维版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-19 06:20:00每日论坛发贴之星
日期:2016-04-19 06:20:00IT运维版块每日发帖之星
日期:2016-04-25 06:20:00IT运维版块每日发帖之星
日期:2016-05-06 06:20:00IT运维版块每日发帖之星
日期:2016-05-08 06:20:00IT运维版块每日发帖之星
日期:2016-05-13 06:20:00IT运维版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-28 06:20:00
发表于 2008-12-31 10:38 |显示全部楼层
转过来一篇介绍内核中红黑树接口的文章。

论坛徽章:
0
发表于 2008-12-31 11:01 |显示全部楼层
学习了,谢谢版主。

论坛徽章:
36
IT运维版块每日发帖之星
日期:2016-04-10 06:20:00IT运维版块每日发帖之星
日期:2016-04-16 06:20:0015-16赛季CBA联赛之广东
日期:2016-04-16 19:59:32IT运维版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-19 06:20:00每日论坛发贴之星
日期:2016-04-19 06:20:00IT运维版块每日发帖之星
日期:2016-04-25 06:20:00IT运维版块每日发帖之星
日期:2016-05-06 06:20:00IT运维版块每日发帖之星
日期:2016-05-08 06:20:00IT运维版块每日发帖之星
日期:2016-05-13 06:20:00IT运维版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-28 06:20:00
发表于 2008-12-31 11:09 |显示全部楼层

回复 #3 scutan 的帖子

呵呵,这两天因为要使用,所以得研究一下。大家一起交流。

论坛徽章:
36
IT运维版块每日发帖之星
日期:2016-04-10 06:20:00IT运维版块每日发帖之星
日期:2016-04-16 06:20:0015-16赛季CBA联赛之广东
日期:2016-04-16 19:59:32IT运维版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-19 06:20:00每日论坛发贴之星
日期:2016-04-19 06:20:00IT运维版块每日发帖之星
日期:2016-04-25 06:20:00IT运维版块每日发帖之星
日期:2016-05-06 06:20:00IT运维版块每日发帖之星
日期:2016-05-08 06:20:00IT运维版块每日发帖之星
日期:2016-05-13 06:20:00IT运维版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-28 06:20:00
发表于 2008-12-31 11:30 |显示全部楼层
如果哪位朋友使用内核的红黑树接口写了一些程序,方便的话拿上来大家一起学习一下

论坛徽章:
36
IT运维版块每日发帖之星
日期:2016-04-10 06:20:00IT运维版块每日发帖之星
日期:2016-04-16 06:20:0015-16赛季CBA联赛之广东
日期:2016-04-16 19:59:32IT运维版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-19 06:20:00每日论坛发贴之星
日期:2016-04-19 06:20:00IT运维版块每日发帖之星
日期:2016-04-25 06:20:00IT运维版块每日发帖之星
日期:2016-05-06 06:20:00IT运维版块每日发帖之星
日期:2016-05-08 06:20:00IT运维版块每日发帖之星
日期:2016-05-13 06:20:00IT运维版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-28 06:20:00
发表于 2008-12-31 11:53 |显示全部楼层
2.4.20内核中使用红黑树的好像就mmap等。2.6中使用的更广泛一些

论坛徽章:
0
发表于 2008-12-31 19:23 |显示全部楼层
红黑树在内核中有很多应用。
数据库中也应用的很多

论坛徽章:
36
IT运维版块每日发帖之星
日期:2016-04-10 06:20:00IT运维版块每日发帖之星
日期:2016-04-16 06:20:0015-16赛季CBA联赛之广东
日期:2016-04-16 19:59:32IT运维版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-19 06:20:00每日论坛发贴之星
日期:2016-04-19 06:20:00IT运维版块每日发帖之星
日期:2016-04-25 06:20:00IT运维版块每日发帖之星
日期:2016-05-06 06:20:00IT运维版块每日发帖之星
日期:2016-05-08 06:20:00IT运维版块每日发帖之星
日期:2016-05-13 06:20:00IT运维版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-28 06:20:00
发表于 2008-12-31 19:48 |显示全部楼层

回复 #7 emmoblin 的帖子

是啊。emmoblin兄对这方面有研究吧,什么时候分享一下。

论坛徽章:
0
发表于 2008-12-31 20:10 |显示全部楼层
内核 QoS 的 HTB 分层令牌桶用了 RBTREE,Godbach 可以参考一下

论坛徽章:
3
金牛座
日期:2014-06-14 22:04:062015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:49:45
发表于 2008-12-31 20:25 |显示全部楼层
rbtree现在用得越来越广了,连进程调度都使用了红黑树,前面学了一下,看来还需要深入掌握这个东西。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

DTCC2021中国数据库技术大会

【数造未来】2021年10月18日-20日第十二届中国数据库技术大会
ITPUB、大会的会员您们好: 因目前国内疫情严峻,为响应北京市最新疫情防控要求,保障参会人员的健康和安全,组委会经协商决定:DTCC2021第十二届中国数据库技术大会延期至10月18日-20日(周一~周三)在北京国际会议中心举行,由此给各位带来的不便,敬请谅解!

大会官网
  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP