红黑树是平衡二叉树的一种，它有很好的性质，树中的结点都是有序的，而且因为它本身就是平衡的，所以查找也不会出现非常恶劣的情况，基于二叉树的操作的时间复杂度是O(log(N))。Linux内核在管理vm_area_struct时就是采用了红黑树来维护内存块的。
先到include/linux/rbtree.h中看一下红黑树的一些定义，如下：
structrb_node { unsignedlong rb_parent_color; #defineRB_RED 0 #defineRB_BLACK 1 structrb_node *rb_right; structrb_node *rb_left; }__attribute__((aligned(sizeof(long)))); |
structrb_root只是structrb_node*的一个包装，这样做的好处是看起来不用传递二级指针了。不错，很简单。再看一下下面几个重要的宏，细心的你一定会发现，rb_parent_color其实没那么简单，AndreaArcangeli在这里使用了一个小的技巧，不过非常棒。正如名字所暗示，这个成员其实包含指向parent的指针和此结点的颜色！它是怎么做到的呢？很简单，对齐起了作用。既然是sizeof(long)大小的对齐，那么在IA-32上，任何rb_node结构体的地址的低两位肯定都是零，与其空着不用，还不如用它们表示颜色，反正颜色就两种，其实一位就已经够了。
这样，提取parent指针只要把rb_parent_color成员的低两位清零即可：
| #definerb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3)) |
取颜色只要看最后一位即可：
| #definerb_color(r) ((r)->rb_parent_color & 1) |
