红黑树底层原理及Linux内核红黑树算法深度研究( 三 ) _红黑树

2. 红黑树linux内核红黑树的算法都定义在
linux-2.6.38.8/include/linux/rbtree.h和linux-2.6.38.8/lib/rbtree.c两个文件中。
2.1 结构体红黑树和我们以
struct rb_node{    unsigned long  rb_parent_color;#define RB_RED      0#define RB_BLACK    1    struct rb_node *rb_right;    struct rb_node *rb_left;} __attribute__((aligned(sizeof(long))));这里的巧妙之处是使用成员rb_parent_color同时存储两种数据，一是其双亲结点的地址，另一是此结点的着色。__attribute__((aligned(sizeof(long))))属性保证了红黑树中的每个结点的首地址都是32位对齐的（在32位机上），也就是说每个结点首地址的bit[1]和bit[0]都是0，因此就可以使用bit[0]来存储结点的颜色属性而不干扰到其双亲结点首地址的存储。
操作rb_parent_color的函数：
#define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))  //获得其双亲结点的首地址#define rb_color(r)   ((r)->rb_parent_color & 1) //获得颜色属性#define rb_is_red(r)   (!rb_color(r))   //判断颜色属性是否为红#define rb_is_black(r) rb_color(r) //判断颜色属性是否为黑#define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)  //设置红色属性#define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0) //设置黑色属性 static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)  //设置其双亲结点首地址的函数{    rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;}static inline void rb_set_color(struct rb_node *rb, int color) //设置结点颜色属性的函数{    rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;} 初始化新结点：
static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,                struct rb_node ** rb_link){    node->rb_parent_color = (unsigned long )parent;   //设置其双亲结点的首地址(根结点的双亲结点为NULL),且颜色属性设为黑色    node->rb_left = node->rb_right = NULL;   //初始化新结点的左右子树     *rb_link = node;  //指向新结点} 指向红黑树根结点的指针：
struct rb_root{    struct rb_node *rb_node;};  #define RB_ROOT (struct rb_root) { NULL, }  //初始化指向红黑树根结点的指针#define rb_entry(ptr, type, member) container_of(ptr, type, member) //用来获得包含struct rb_node的结构体的首地址 #define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL) //判断树是否为空#define RB_EMPTY_NODE(node) (rb_parent(node) == node)  //判断node的双亲结点是否为自身#define RB_CLEAR_NODE(node) (rb_set_parent(node, node)) //设置双亲结点为自身2.2 插入首先像二叉查找树一样插入一个新结点，然后根据情况作出相应的调整，以使其满足红黑树的颜色属性（其实质是维持红黑树的平衡）。
函数rb_insert_color使用while循环不断地判断双亲结点是否存在，且颜色属性为红色。
若判断条件为真，则分成两部分执行后续的操作：
（1）、当双亲结点是祖父结点左子树的根时，则：
a、存在叔父结点，且颜色属性为红色。