内核红黑树源码注解

忘是亡心i 2022-08-06 08:29 190阅读 0赞

# [内核红黑树源码注解][Link 1] #

![复制代码][copycode.gif]

1 typedef struct st_rb_node {   
     2     /**  
     3      * 本结构体四字节对齐，因而其地址中低位两个bit永远是0。  
     4      * Linux内核开发人员非常爱惜内存，他们用其中一个空闲的位来存储颜色信息。  
     5      * parent_color成员实际上包含了父节点指针和自己的颜色信息。  
     6      */  
     7     unsigned long parent_color;   
     8 #define RB_RED   0   
     9 #define RB_BLACK 1   
    10     struct st_rb_node *left, *right;   
    11 }__attribute__((aligned(sizeof(long)))) rb_node;

![复制代码][copycode.gif]

Linux的数据结构有个特点就是结构不包括数据，而是由数据来包括结构信息。由结构体获取数据信息是通过 CONTAINER\_OF 这个宏来实现的，它利用了一些编译器的特性，有兴趣的可以参考Linux的链表源码。

头文件中其它主要内容如下（比较好理解，未作注释）：

![复制代码][copycode.gif]

1 #define rb_parent(r)    ((rb_node *)((r)->parent_color & ~3))   
     2 #define rb_color(r)     ((r)->parent_color & 1)   
     3 #define rb_is_red(r)    (!rb_color(r))   
     4 #define rb_is_black(r)  rb_color(r)   
     5 #define rb_set_red(r)   do { (r)->parent_color &= ~1; } while (0)   
     6 #define rb_set_black(r) do { (r)->parent_color |= 1; } while (0)   
     7   
     8 static inline void rb_set_parent(rb_node *node, rb_node *p) {   
     9     node->parent_color = (node->parent_color & 3) | (unsigned long) p;   
    10 }   
    11   
    12 static inline void rb_set_color(rb_node *node, int color) {   
    13     node->parent_color = (node->parent_color & ~1) | color;   
    14 }   
    15   
    16 #define RB_ROOT (rb_root) { NULL, }   
    17 #define rb_entry(ptr, type, member) container_of(ptr, type, member)   
    18   
    19 #define RB_EMPTY_ROOT(root) ((root)->node == NULL)   
    20 #define RB_EMPTY_NODE(node) (rb_parent(node) == node)   
    21 #define RB_CLEAR_NODE(node) (rb_set_parent(node, node))   
    22   
    23 void rb_insert_color(rb_node *node, rb_root *root);   
    24 void rb_erase(rb_node *node, rb_root *root);   
    25   
    26 rb_node * rb_next(const rb_node *node);   
    27 rb_node * rb_prev(const rb_node *node);   
    28 rb_node * rb_first(const rb_root *root);   
    29 rb_node * rb_last(const rb_root *root);   
    30   
    31 void rb_replace_node(rb_node *victim, rb_node *new, rb_root *root);   
    32   
    33 static inline void rb_link_node(rb_node *node, rb_node *p, rb_node **link) {   
    34     node->parent_color = (unsigned long) p;   
    35     node->left = node->right = NULL;   
    36     *link = node;   
    37 }

![复制代码][copycode.gif]

两个基本操作：左旋与右旋（未注释，仅为方便参考）

![复制代码][copycode.gif]

1 /**  
     2  * 对node进行左旋。有关概念可参考WIKI等资源。  
     3  */  
     4 static void _rb_rotate_left(rb_node *node, rb_root *root) {   
     5     rb_node *right = node->right, *parent = rb_parent(node);   
     6   
     7     if ((node->right = right->left))   
     8         rb_set_parent(node->right, node);   
     9   
    10     right->left = node;   
    11     rb_set_parent(node, right);   
    12   
    13     if (parent) {   
    14         if (node == parent->left)   
    15             parent->left = right;   
    16         else  
    17             parent->right = right;   
    18     } else {   
    19         root->node = right;   
    20     }   
    21     rb_set_parent(right, parent);   
    22 }   
    23   
    24 /**  
    25  * 对node进行右旋。有关概念可参考WIKI等资源。  
    26  */  
    27 static void _rb_rotate_right(rb_node *node, rb_root *root) {   
    28     rb_node *left = node->left, *parent = rb_parent(node);   
    29   
    30     if ((node->left = left->right))   
    31         rb_set_parent(node->left, node);   
    32   
    33     left->right = node;   
    34     rb_set_parent(node, left);   
    35   
    36     if (parent) {   
    37         if (node == parent->left)   
    38             parent->left = left;   
    39         else  
    40             parent->right = left;   
    41     } else {   
    42         root->node = left;   
    43     }   
    44     rb_set_parent(left, parent);   
    45 }

![复制代码][copycode.gif]

插入操作的实现（前提是节点已经插入在目标位置，下面的函数只负责修正树的性质）：

![复制代码][copycode.gif]

1 /**  
     2  * node是新插入的结点，有着默认的红色。  
     3  * 本函数检查是否有违背红黑树性质的地方，并进行纠正。  
     4  */  
     5 void rb_insert_color(rb_node *node, rb_root *root) {   
     6     rb_node *parent, *gp;   
     7   
     8     /**  
     9      * 如果有父节点且父节点是红色，进行树的调整以保证树的性质。  
    10      */  
    11     while ((parent = rb_parent(node)) && rb_is_red(parent)) {   
    12         gp = rb_parent(parent);   
    13   
    14         if (parent == gp->left) {   
    15             /**  
    16              * 父节点是祖父节点左子的情况。  
    17              * "else"中的情况左右相反，这里只注释"if"里的代码。  
    18              */  
    19             register rb_node *uncle = gp->right;   
    20             if (uncle && rb_is_red(uncle)) {   
    21                 /**  
    22                  * 如果有红叔，则将红叔与红父均涂黑，并将祖父节点涂红。  
    23                  */  
    24                 rb_set_black(parent);   
    25                 rb_set_black(uncle);   
    26                 rb_set_red(gp);   
    27                 /**  
    28                  * 现在简单路径中黑节点个数仍然平衡，但祖父变成了红色，  
    29                  * 我们不确定有没有造成父子均红的情况，所以需要对祖父节点进行下一轮修复。  
    30                  */  
    31                 node = gp;   
    32                 continue;   
    33             }   
    34   
    35             /**  
    36              * 现在是叔节点为空或为黑的情况。  
    37              */  
    38             if (node == parent->right) {   
    39                 /**  
    40                  * 如果新节点是父节点的右子，对父节点进行左旋。  
    41                  * 旋转后树仍然平衡，但新节点占了原父节点的位子。  
    42                  * 这两个节点交换角色后，新的父节点是红的，其左子也是红的。  
    43                  */  
    44                 _rb_rotate_left(parent, root);   
    45                 register rb_node *tmp = node;   
    46                 node = parent;   
    47                 parent = tmp;   
    48             }   
    49             /**  
    50              * 此时父红左子红，树平衡但有连续红节点。  
    51              *  
    52              * 父涂黑，祖父涂红，再对祖父右旋，树即调整到合法状态。  
    53              */  
    54             rb_set_black(parent);   
    55             rb_set_red(gp);   
    56             _rb_rotate_right(gp, root);   
    57             return;   
    58         } else {   
    59             register rb_node *uncle = gp->left;   
    60             if (uncle && rb_is_red(uncle)) {   
    61                 rb_set_black(parent);   
    62                 rb_set_black(uncle);   
    63                 rb_set_red(gp);   
    64                 node = gp;   
    65                 continue;   
    66             }   
    67   
    68             if (node == parent->left) {   
    69                 _rb_rotate_right(parent, root);   
    70                 register rb_node *tmp = node;   
    71                 node = parent;   
    72                 parent = tmp;   
    73             }   
    74             rb_set_black(parent);   
    75             rb_set_red(gp);   
    76             _rb_rotate_left(gp, root);   
    77             return;   
    78         }   
    79     }   
    80     /**  
    81      * 若无父节点，只需将node涂黑；  
    82      * 若父节点为黑，插入红节点不影响树的性质。  
    83      * 循环体后直接将node涂黑，可以同时保证以上两点。  
    84      */  
    85      rb_set_black(root->node);   
    86 }

![复制代码][copycode.gif]

最复杂的是删除操作，分为两部分。

删除第一步，移出节点：

![复制代码][copycode.gif]

1 /**  
      2  * 删除node节点（其实只是将其与树脱离），并修正树。  
      3  * 红黑树的节点删除相对比插入更复杂，加之Linux的源码风格也不易懂，  
      4  * 此段代码需认真体会，可以多画画图，对各种情况标记、对照一下。  
      5  */  
      6 void rb_erase(rb_node *node, rb_root *root) {   
      7     rb_node *child, *parent;   
      8     int color;   
      9        
     10     /**  
     11      * 这里其实分成了两个大分枝。  
     12      * 如果node有任一空子，则记录child并跳至条件语句后的语句，具体位置参考注释；  
     13      * 如果两子均不为空，则进入"else"分枝。  
     14      */  
     15     if (!node->left) {   
     16         child = node->right;   
     17     } else if (!node->right) {   
     18         child = node->left;   
     19     } else {   
     20         /**  
     21          * 乾坤大挪移，将要删除的节点转换成只有一个子节点或无子节点的节点。  
     22          * 具体方法是，找到它的下一个节点，也即先找其右节点，再循环找左节点，  
     23          * 直到没有左子节点。找到的节点一定是比node"大"且紧邻node的节点。  
     24          * 将此找到的节点放到node位置，并保持node的原有颜色，树的性质并不会受影响。  
     25          * 此时问题转化成了删除找到的没有左子的节点。  
     26          * （提示：也可以找左子的右节点，循环下去，得到的将是“紧邻”的小于node的节点）  
     27          */  
     28         rb_node *old = node, *left;   
     29         node = node->right;   
     30         while ((left = node->left) != NULL)   
     31             node = left;   
     32            
     33         /**  
     34          * 找到节点后，将其“大挪移”过去。  
     35          * 首先用old的父亲或root指向新找到的节点node.  
     36          */  
     37         if (rb_parent(old)) {   
     38             if (rb_parent(old)->left == old)   
     39                 rb_parent(old)->left = node;   
     40             else  
     41                 rb_parent(old)->right = node;   
     42         } else {   
     43             root->node = node;   
     44         }   
     45            
     46         /**  
     47          * 记录找到的node节点相关信息。对于这种删除操作，node节点移至old位置后会沿用old的颜色属性，  
     48          * 树的性质不受影响，但原node位置将失去一个节点，我们要记录节点的相关信息以便做节点的删除工作。  
     49          */  
     50         child = node->right;   
     51         parent = rb_parent(node);   
     52         color = rb_color(node);   
     53            
     54         if (parent == old) {   
     55             /**  
     56              * 参考前面while循环，如果parent==old,则找到的单子节点只能是old节点的右子。  
     57              * 这里保存的parent可以理 解为将用作node原来子节点的亲父节点。对于old是node右子的情况，  
     58              * node取代old后，原node的父节点还是node.  
     59              */  
     60             parent = node;   
     61         } else {   
     62             /**  
     63              * node节点的删除处理。主要是将相应的父、子联结起来。  
     64              * 注意我们的“乾坤大挪移”可能会比较绕，删的数据是old节点，但我们将node转移过去占了old的位置，  
     65              * 所以对于节点结构来说，我们删除的是node原来的位置。  
     66              */  
     67             if (child)   
     68                 rb_set_parent(child, parent);   
     69             parent->left = child;   
     70                
     71             node->right = old->right;   
     72             rb_set_parent(old->right, node);   
     73         }   
     74            
     75         /**  
     76          * node移过去后继续使用old节点的颜色和父节点属性。  
     77          * parent_color同时保存了父节点信息和自己的颜色信息。  
     78          * 关于parent_color请参考头文件中的宏。  
     79          */  
     80         node->parent_color = old->parent_color;   
     81         /**  
     82          * 之前已将old的parent的指向old子节点的指针指向了node，  
     83          * 并且node也已经连接了old的右子（如果node与old是子与父的关系，则node保留原右子即可）  
     84          * 上面一句完成了node指向新父亲即设置颜色的操作，现在只剩下左子了，把它搞定！  
     85          */  
     86         node->left = old->left;   
     87         rb_set_parent(old->left, node);   
     88            
     89         /**  
     90          * 该删的该改的都已搞定，现在要检查颜色了。  
     91          */  
     92         goto color;   
     93     }   
     94        
     95     /**  
     96      * 这里的条件语句和goto语句实在是让人晕头转向。现在对应的是本函数最上面的if语句中前两个case。  
     97      *  
     98      * 如果node有任一空子，也即node无子或有单子。这里跳过了前面的“乾坤大挪移”，同时相比挪移的情况，  
     99      * 这里的区别是node可能是右子，也可能是左子。但这里的删除操作要简单些。  
    100      *  
    101      * 思考：挪移与不挪移的情况，最终都是把问题转到了一个无子或只有单子的节点上，  
    102      * 为什么不能让两种情况执行一段共同的删除代码呢？  
    103      * 我想应该是挪移本身已经使node从原位置消失了，两者删除操作有差别，加之Linux内核对速度的狂热，  
    104      * 就分情况写成了现在这种很绕的代码。  
    105      */  
    106     parent = rb_parent(node);   
    107     color = rb_color(node);   
    108        
    109     if (child)   
    110         rb_set_parent(child, parent);   
    111     if (parent) {   
    112         if (parent->left = node)   
    113             parent->left = child;   
    114         else  
    115             parent->right = child;   
    116     } else {   
    117         root->node = child;   
    118     }   
    119   
    120 color:   
    121     /**  
    122      * color是删除节点的颜色，删除的节点的层次正好在child参数与parent参数中间。  
    123      * 如果删除的是红节点，对树没有影响，所以只有删除的是黑节点时才修正颜色。  
    124      */  
    125     if (color == RB_BLACK)   
    126         _rb_erase_color(child, parent, root);   
    127 }

![复制代码][copycode.gif]

第二步，简单移出如果破坏了树的性质，则需要修复：

![复制代码][copycode.gif]

1 /**  
      2  * 前置环境：在node与parent之前，刚刚删除了一个黑色节点。现在树很可能不平衡，  
      3  * node与parent也可能红色冲突。  
      4  * 本函数进行树的性质的修正，以使树恢复平衡。在一些情况下问题会转移到上一层节点，  
      5  * 则须对上一层节点进行递归检查与修正。本函数中的while循环实际上实现了这种递归。  
      6  *  
      7  * 提示：这是红黑树里最绕的地方，看不明白可以多画画图。  
      8  */  
      9 static void _rb_erase_color(rb_node *node, rb_node *parent, rb_root *root) {   
     10     /**  
     11      * other用来保存兄弟节点，这是树的修正过程中一个重要的参考节点。  
     12      */  
     13     rb_node *other;   
     14     /**  
     15      * 循环条件：node不是红节点且node不是根节点。  
     16      * 解释：对于红节点或根节点，直接涂黑即可解决问题。  
     17      */  
     18     while ((!node || rb_is_black(node)) && node != root->node) {   
     19         /**  
     20          * 为方便程序处理各种情况，这里和节点插入一样将问题分成了左右对称的两类。  
     21          * if-else两个分枝里代码逻辑完全相同，只是左右相反。所以我们只研究node是parent左子的情况。  
     22          *  
     23          * 在开始之前，我们先总结一下当前状态：  
     24          * 1:因为删除的是黑色节点，所以node与parent都有可能是红色节点。  
     25          * 2:node与parent之间少了一个黑色节点，则所有通过node的路径都少了一个黑色节点，不妨画图时用-1标出来；  
     26          * 但node的兄弟节点（node一定有兄弟，可以根据删除前树的平衡性质来反推）高度并未变化，可以记作0。  
     27          *  
     28          * 提示：在进行旋转、涂色等操作时，可以画图观查平衡状态的变化。  
     29          */  
     30         if (parent->left == node) {   
     31             other = parent->right;   
     32             if (rb_is_red(other)) {   
     33                 /**  
     34                  * 如果兄弟节点是红色，则父节点是黑色，交换父、兄节点的颜色，并对父节点进行左旋。  
     35                  * 旋转后，兄节点占了老的父节点位置，且和老的父节点颜色相同，所以不会向上造成颜色冲突。  
     36                  * 我们仍然以老的父节点为父节点来看，现在的状态是：  
     37                  * 父节点右子保持平衡，只有经过node的路径少了一个黑色节点。  
     38                  * 现在问题和之前相似，但node有了一个黑色的兄弟（还有一个红色父亲）。  
     39                  */  
     40                 rb_set_black(other);   
     41                 rb_set_red(parent);   
     42                 _rb_rotate_left(parent, root);   
     43                 /**  
     44                  * other指向新的兄弟节点。other现在必然是一个黑色节点，而不会是空。这一点可以根据旋转之前树的性质反证。  
     45                  */  
     46                 other = parent->right;   
     47             }   
     48             /**  
     49              * 此时状态：  
     50              * node有黑色兄弟，父亲可能黑也可能红。  
     51              */  
     52             if ((!other->left || rb_is_black(other->left)) &&   
     53                 (!other->right || rb_is_black(other->right))) {   
     54                 /**  
     55                  * 如果other没有红色子节点，那我们就可以把other涂红，并向上转移问题。  
     56                  * other涂红的后果是，other分枝少了一个黑节点，与node分枝保持了平衡，但parent整体少了一个黑色节点。  
     57                  * 细心的人可能会发现，如果父亲是红色的，父亲与兄弟有颜色冲突，直接向上转移能纠正吗？当然是可以的。  
     58                  * 向上一层之后，while里的黑节点判断失败，会直接执行while后面的语句，直接将parent涂黑，则树恢复平衡。  
     59                  */  
     60                 rb_set_red(other);   
     61                 node = parent;   
     62                 parent = rb_parent(node);   
     63             } else {   
     64                 /**  
     65                  * 现在黑兄弟有红子节点，父亲颜色未知。  
     66                  */  
     67                 if (!other->right || rb_is_black(other->right)) {   
     68                     /**  
     69                      * 如果黑兄弟右节点为空或为黑，则左节点一定是红的，我们想办法把它调整为右子为红。  
     70                      * 至于为什么，看后面就知了。  
     71                      * other->left与other交换颜色，对other进行右旋，other指向新的兄弟。根据右旋转的特点，  
     72                      * 可知现在other仍然是黑色，且它有了一个红色右子。同时other分枝高度不变，颜色也没有冲突。  
     73                      */  
     74                     rb_set_black(other->left);   
     75                     rb_set_red(other);   
     76                     _rb_rotate_right(other, root);   
     77                     other = parent->right;   
     78                 }   
     79                 /**  
     80                  * 此时状态：黑兄弟有红色右子节点。  
     81                  * 不管parent是什么颜色，把other涂成父亲的颜色（之后旋转，other占据父亲的位置，向上没有颜色冲突），  
     82                  * 把父亲涂黑，把黑兄的other涂黑，这时node分枝高度可能有变化也可能没变化，other分枝多了一个黑节点。  
     83                  * 现在对父亲进行左旋转。旋转后的情况是右边分枝（原other右子）少了一个黑节点，重归平衡；  
     84                  * 左边分枝则增加了一个黑节点，也恢复了平衡。此时也没有颜色冲突  
     85                  */  
     86                 rb_set_color(other, rb_color(parent));   
     87                 rb_set_black(parent);   
     88                 rb_set_black(other->right);   
     89                 _rb_rotate_left(parent, root);   
     90                 /**  
     91                  * 树已平衡，node置为根节点，并跳出循环。  
     92                  * 疑问：这里为什么还要检查根节点呢？  
     93                  */  
     94                 node = root->node;   
     95                 break;   
     96             }   
     97         } else {   
     98             other = parent->left;   
     99             if (rb_is_red(other)) {   
    100                 rb_set_black(other);   
    101                 rb_set_red(parent);   
    102                 _rb_rotate_right(parent, root);   
    103                 other = parent->left;   
    104             }   
    105             if ((!other->left || rb_is_black(other->left)) &&   
    106                 (!other->right || rb_is_black(other->right))) {   
    107                 rb_set_red(other);   
    108                 node = parent;   
    109                 parent = rb_parent(node);   
    110             } else {   
    111                 if (!other->left || rb_is_black(other->left)) {   
    112                     rb_set_black(other->right);   
    113                     rb_set_red(other);   
    114                     _rb_rotate_left(other, root);   
    115                     other = parent->left;   
    116                 }   
    117                 rb_set_color(other, rb_color(parent));   
    118                 rb_set_black(parent);   
    119                 rb_set_black(other->left);   
    120                 _rb_rotate_right(parent, root);   
    121                 node = root->node;   
    122                 break;   
    123             }   
    124         }   
    125     }   
    126     /**  
    127      * 对于红节点或根节点，直接涂黑即可解决问题。  
    128      */  
    129     if (node)   
    130         rb_set_black(node);   
    131 }

![复制代码][copycode.gif]

转自 [http://www.iteye.com/topic/1119331][http_www.iteye.com_topic_1119331]

[Link 1]: http://www.cnblogs.com/li-hao/archive/2013/04/16/3024758.html
[copycode.gif]: /images/20220806/347dd401ee73489f8ab91b7cc7b9ebea.png
[http_www.iteye.com_topic_1119331]: http://www.iteye.com/topic/1119331