linux内核中的红黑树代码解析

13544870125

　　1 红黑树的定义
　　     （1）每个节点或者为黑色，或者为红色。
　　     （2）根必须为黑色。
　　　  （3）每个叶子节点（不包含关键字的节点）都是黑色。
　　　  （4）如果有一个节点是红色，那么它的两个儿子都是黑色。
　　　  （5）对于每个节点，从该节点出发到其子孙节点的所有路径上包含相同数目的黑节点。
　　　　满足上面5个条件的树就是一颗红黑树，红黑树有着很好的性质，它类似于平衡二叉树（AVL）。一颗红黑树的高度不会超过2lg（n+1），而且插入和删除操作较AVL更快，由于它分别最多做2次和3次旋转来维护树的性质，所以在linux内核中大量使用了红黑树，如ext3文件系统中使用红黑色来记录目录项，虚拟内存区也是使用它来记录的。
　　2 linux内核实现的红黑树函数调用关系
　　 　  linux3.7.4内核实现红黑树的的文件是：include/linux/rbtree.h，include/linux/rbtree_augmented.h，lib/rbtree.c。linux3.7.4内核除了有红黑色的基本功能，而且还基于基本的红黑树实现了扩展的红黑树。rbtree.h头文件定义的就是基本的红黑树，rbtree_augmented.h头文件定义了扩展的红黑树，rbtree.c是对扩展红黑树的实现，由于扩展红黑色也可以用来实现基本红黑色。测试文件在lib/rbtree_test.c中。下面描述的是在测试文件中函数的调用关系。
　　2.1 普通的rbtree函数调用关系
　　　　插入节点
　　　　
　　　　删除节点
　　
　　2.2 扩展的rbtree函数调用关系
　　　　插入节点
　　
　　　　删除节点
　　
　　2 函数说明
　　insert函数：查找插入点，调用rb_link_node插入rb树中，调用rb_insert_color调整rb树的颜色。rb_insert_color函数直接调用__rb_insert，并将dummy_rotate（不做任何事）的回调函数传给__rb_insert。__rb_insert函数做主要是做rb树颜色的调整。
　　insert_augmented查找插入点，更新扩展域，调用rb_link_node插入rb树中，调用rb_insert_augmented调整rb树的颜色，并将augment_callbacks回调函数结构体传给rb_insert_augmented。rb_insert_augmented调用__rb_insert_augmented，将augment_callbacks中的rotate函数传给__rb_insert_augmented。_rb_insert_augmented直接调用__rb_insert。
　　erase函数直接调用rb_erase函数。rb_erase函数调用rb_erase_augmented，并将dummy_callbacks回调函数结构体传给rb_erase_augmented。rb_erase_augmented函数主要做节点的删除，并调用__rb_erase_color做rb树颜色的调整。__rb_erase_color主要做颜色的调整。
　　erase_augmented函数直接调用rb_erase_augmented函数，并将augment_callbacks回调函数结构体传给rb_erase_augmented。其它和上面是一样的。
　　3 扩展红黑色流程图
　　　　插入模块
　　
　　　　删除模块
　　
　　　　删除模块中的颜色调整
　　
　　rbtree的源码