找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

Linux 内核红黑树分析

admin 2019-10-13 05:30 248人围观 Linux相关

Android binder 内核实现是用红黑树的,理解红黑树我觉得是每一个Linux er的重中之重,感谢格子森同学的投稿,周末愉快。


内核版本为 linux4.2.1 本文主要从红黑树的代码实现入手,来讨论linux内核中是如何实现红黑树的(主要是插入和删除操作),其中涉及到的函数有三个__rb_insert __rb_erase_augmented ____rb_erase_color,本文将用图示的方式解析这三个函数。

1.红黑树性质


1.节点是红色或者黑色2.根节点是黑色3.所有叶子节点(null)都为黑色4.红色节点的子节点都是黑色5.从根节点到叶子节点所有路径上黑色节点数相同

2.基础

2.1 节点结构

    struct rb_node { unsigned long __rb_parent_color; struct rb_node *rb_right; struct rb_node *rb_left;} __attribute__((aligned(sizeof(long))));
    不难看出 rb_left 和 rb_right 是该节点左右子节点的指针,结构体后面的__attribute__((aligned(sizeof(long))))让这个结构体按照4字节对齐(64位是8字节)。 __rb_parent_color这个参数名字有点奇怪,父亲的颜色?啥意思?不过当我们理解了这个参数的意义之后发现还真就应该叫这个名字。这个名字的意思其实是 "父亲和颜色",它即代表了父节点的地址,也代表了自身的颜色。有人可能要问了,就这一个参数,怎么代表了两个东西?这个其实也简单,之前我们不是提到了这个rb_node是按照4字节对齐的嘛,那么当我们声明一个rb_node实例的时候,它的首地址必然是4的整数倍。首地址是4的整数倍,那地址的0bit和1bit肯定都是0嘛,不管怎么玩它都是0,那不就没啥"意义"了么,不如拿过来放颜色。那我们就让这个__rb_parent_color 最低位,也就是第0bit来表示颜色,0代表红色,1代表黑色。当我们需要颜色的时候我们就看第0bit,当我们需要父节点地址的时候我们就把最低两位弄成0就行啦。
      //颜色宏#define RB_RED 0#define RB_BLACK 1

      2.2 左旋和右旋


      对E进行左旋

      对S进行右旋

      当然图片中演示的是一个大致流程,因为红黑树节点中还包含父节点地址以及自身颜色等信息,所以在实际旋转的时候需要考虑更多。

      2.3 辅助函数__rb_rotate_set_parents


      这个函数的作用:将old的颜色和父节点给new,之后old将new作为新的父节点并且设置自己的颜色为color
        static inline void__rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, struct rb_root *root, int color){ struct rb_node *parent = rb_parent(old); new->__rb_parent_color = old->__rb_parent_color;//步骤1 rb_set_parent_color(old, new, color);//步骤2 __rb_change_child(old, new, parent, root);//步骤3}

        在图中我们可以注意到一个点,就是old指向子节点的指针没有改变,在实际程序中是需要将它指向正确位置的,不过并不是由这个辅助函数完成。

        3.插入操作


        在插入时,我们默认插入的节点是红色,并且只有插入节点的父节点是红色的时候才需要调整(因为违反了性质4),并且我们也能保证每次调整过后,红黑树只会因为不满足性质4而需要再次调整,这点非常重要。在看代码之前,我们需要先讨论一下插入总共涉及到几种情况。插入后一共有6种情况(本质上3种),在逻辑上涉及到这几个节点,祖父节点G,父节点P,叔叔节点U和插入的节点N。其中P是G左孩子有3种情况,P是G右孩子有3种情况,它们是对称的,在逻辑上一致,所以我们可以认为插入操作本质上只有3种情况需要讨论,这里假设P是G的左孩子。

        1.

        U是红色,此时我们需要变色

        2.

        U是黑色,并且G、P、N不在一条直线上,折了一下,比如
          G / \ P U \ N
          这种情况,我们需要对P进行左旋(对称情况是右旋),让G、P、N处于同一条直线上,进入情况3

          3.

          U是黑色,并且G、P、U在同一条直线上,比如
            G / \ P U / N
            这种情况,我们需要对G进行右旋(对称情况是左旋),旋转完成后红黑树调整完毕。

            这里我们可以注意到一个特点,在每次调整完成之后,node总是指向局部满足的子树的根节点。 由此除了case3调整完直接结束之外,我们还能得到另外两个结束条件。

            1.

            Parent为空,这证明Node已经是根节点了,局部满足即为整体满足,调整结束,另外为了满足根节点为黑色,需要将Node(根节点)设置成黑色。

            2.

            Parent为黑色,之前我们有说过 "每次调整过后,红黑树只会因为不满足性质4而需要再次调整",既然Parent为黑色,那无论Node是什么颜色,Node和Parent都不可能为红色,也就必然不会违反性质4,所以调整结束。
              static __always_inline void__rb_insert(struct rb_node *node, struct rb_root *root, void (*augment_rotate)(struct rb_node *old, struct rb_node *new)){ struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
              while (true) { /* * Loop invariant: node is red * * If there is a black parent, we are done. * Otherwise, take some corrective action as we don't * want a red root or two consecutive red nodes. */ if (!parent) { rb_set_parent_color(node, NULL, RB_BLACK); break; } else if (rb_is_black(parent)) break;
              gparent = rb_red_parent(parent);
              tmp = gparent->rb_right; if (parent != tmp) { /* parent == gparent->rb_left */ if (tmp && rb_is_red(tmp)) { /* * Case 1 - color flips * * G g * / \ / \ * p u --> P U * / / * n n * * However, since g's parent might be red, and * 4) does not allow this, we need to recurse * at g. */ rb_set_parent_color(tmp, gparent, RB_BLACK); rb_set_parent_color(parent, gparent, RB_BLACK); node = gparent; parent = rb_parent(node); rb_set_parent_color(node, parent, RB_RED); continue; }
              tmp = parent->rb_right; if (node == tmp) { /* * Case 2 - left rotate at parent * * G G * / \ / \ * p U --> n U * \ / * n p * * This still leaves us in violation of 4), the * continuation into Case 3 will fix that. */ tmp = node->rb_left; WRITE_ONCE(parent->rb_right, tmp); WRITE_ONCE(node->rb_left, parent); if (tmp) rb_set_parent_color(tmp, parent, RB_BLACK); rb_set_parent_color(parent, node, RB_RED); augment_rotate(parent, node); parent = node; tmp = node->rb_right; }
              /* * Case 3 - right rotate at gparent * * G P * / \ / \ * p U --> n g * / \ * n U */ WRITE_ONCE(gparent->rb_left, tmp); /* == parent->rb_right */ WRITE_ONCE(parent->rb_right, gparent); if (tmp) rb_set_parent_color(tmp, gparent, RB_BLACK); __rb_rotate_set_parents(gparent, parent, root, RB_RED); augment_rotate(gparent, parent); break; } else { tmp = gparent->rb_left; if (tmp && rb_is_red(tmp)) { /* Case 1 - color flips */ rb_set_parent_color(tmp, gparent, RB_BLACK); rb_set_parent_color(parent, gparent, RB_BLACK); node = gparent; parent = rb_parent(node); rb_set_parent_color(node, parent, RB_RED); continue; }
              tmp = parent->rb_left; if (node == tmp) { /* Case 2 - right rotate at parent */ tmp = node->rb_right; WRITE_ONCE(parent->rb_left, tmp); WRITE_ONCE(node->rb_right, parent); if (tmp) rb_set_parent_color(tmp, parent, RB_BLACK); rb_set_parent_color(parent, node, RB_RED); augment_rotate(parent, node); parent = node; tmp = node->rb_left; }
              /* Case 3 - left rotate at gparent */ WRITE_ONCE(gparent->rb_right, tmp); /* == parent->rb_left */ WRITE_ONCE(parent->rb_left, gparent); if (tmp) rb_set_parent_color(tmp, gparent, RB_BLACK); __rb_rotate_set_parents(gparent, parent, root, RB_RED); augment_rotate(gparent, parent); break; } }}

              在这里我还想强调两点,其一就是无论是哪种情况,在当次调整完成之后,Node指针总是指向"局部满足的根节点",这体现了一种局部到整体的思想,在后面更复杂的删除操作中,抱着这种思想能简化对整个过程的理解。

              另一点就是,在插入操作中,插入节点之后打破是性质4,也只有性质4。 我之前在理解case2和case3的时候总是抱有一个疑问,为什么case1可以变色,case2和case3要旋转?我想这个问题现在能够解答了,如果我们在case2和case3的时候仅仅变色,那么在局部 性质4是满足了,但是在整个红黑树上可能同时打破了性质4和性质5,这无疑是越调整越复杂了。"打破是性质4,也只有性质4" 就是这个意思。

              4.删除操作


              删除操作比较复杂,我们将分成两步进行讨论,在函数中也是分成了两个函数来处理。这两步分别为 "继任" 以及 "调整" 。
                void rb_erase(struct rb_node *node, struct rb_root *root){ struct rb_node *rebalance; rebalance = __rb_erase_augmented(node, root, &dummy_callbacks); if (rebalance) ____rb_erase_color(rebalance, root, dummy_rotate);}

                4.1继任


                因为红黑树是有序的,所以首先我们要保证删除某个节点N之后红黑树还是有序的。为了保证这一点,我们需要选择一个节点来继任N,我们称这个继任者为S。当然S不能随便找,我们肯定要找和N"最像"的来继任对不对,什么叫"最像",就是稍大一些的那个节点嘛(或者稍小一点的)。这样继任之后,红黑树有序的性质就没问题了,有保证了!那么这一步我们的核心问题就出来了,就是要找到那个继任者是谁,然后把它挪过来,这时候原先的N就可以安心的去了。再找继任者的时候有两种情况需要讨论。

                1.N只有一个孩子或者没有孩子 这种情况就让它唯一的那个孩子来继任(没有孩子就相当于NULL来继任)。2.N有两个孩子 这种情况就比较复杂了,需要我们找一找,内核代码实现中是找得稍大一些的那个,怎么找呢?总结下来就一句话,右边走一下,然后左边走到头。 这么说有点抽象,我们来张图。


                现在找到继任者这个问题解决了,还有一个难点就是继任完了之后一定会满足红黑树的5个性质么?这当然是否定的,不然后面还有一步 "调整" 那不就成了摆设?什么情况下继任完了之后我们需要调整,什么情况下不需要呢?不急,我们慢慢道来。首先我们回到N只有一个孩子或者没有孩子这里,这里其实一共三种可能性。如下图所示。

                这里我们可以得到好几个推论,所有的疑问都可以在推论中解答,我们先认定它就是三种可能先往下走。第一个图,直接删除N之后,把C变成黑色继任N,没有打破红黑树任何性质。第二个图,直接删除N(或者说用NULL继任N),没有打破红黑树任何性质。第三个图,直接删除N,我们能够明显发现P的左侧少了一个黑色节点,在这种情况下我们需要第二步"调整"。既然要调整,那得知道从哪开始吧,我们用rebulance指针指向P标记一下,然后把它从"继任"函数中返回出来并作为参数传到"调整"函数中,意思是"喂(#`O′),rebulance这家伙左右两边失衡了,需要你调整一下"。到这里我么就讨论完了。什么?你说N两个孩子都有的情况还没讨论呢。嗨呀,一样的一样的。在这种情况,我们把N这个字母替换成S,你看是不是完全一样。

                现在我们可以腾出地方来好好说一下推论了。推论1:红色节点不可能只有一个孩子,要么有两个孩子,要么没有孩子。这点我们可以用反证法推倒出来,首先假设一个红色节点S只有一个孩子,根据性质4(红色节点的孩子都是黑色),那么它的孩子C一定是黑色。如下图所示:

                C下面一定还会存在NULL节点,S左右不平衡,假设不成立。

                推论2:在推论1的基础上可以得到,如果一个节点只有一个孩子,那么该节点一定是黑色,并且它的孩子一定是红色。推倒方式和推论1类似,这里不再赘述。继任的基本思想就如上述所示,接下来就是内核中的代码实现以及匹配代码的一张大图了,大家可以对照着看。
                  static __always_inline struct rb_node *__rb_erase_augmented(struct rb_node *node, struct rb_root *root, const struct rb_augment_callbacks *augment){ struct rb_node *child = node->rb_right; struct rb_node *tmp = node->rb_left; struct rb_node *parent, *rebalance; unsigned long pc;
                  if (!tmp) { /* * Case 1: node to erase has no more than 1 child (easy!) * * Note that if there is one child it must be red due to 5) * and node must be black due to 4). We adjust colors locally * so as to bypass __rb_erase_color() later on. */ pc = node->__rb_parent_color; parent = __rb_parent(pc); __rb_change_child(node, child, parent, root); if (child) { child->__rb_parent_color = pc; rebalance = NULL; } else rebalance = __rb_is_black(pc) ? parent : NULL; tmp = parent; } else if (!child) { /* Still case 1, but this time the child is node->rb_left */ tmp->__rb_parent_color = pc = node->__rb_parent_color; parent = __rb_parent(pc); __rb_change_child(node, tmp, parent, root); rebalance = NULL; tmp = parent; } else { struct rb_node *successor = child, *child2;
                  tmp = child->rb_left; if (!tmp) { /* * Case 2: node's successor is its right child * * (n) (s) * / \ / \ * (x) (s) -> (x) (c) * \ * (c) */ parent = successor; child2 = successor->rb_right;
                  augment->copy(node, successor); } else { /* * Case 3: node's successor is leftmost under * node's right child subtree * * (n) (s) * / \ / \ * (x) (y) -> (x) (y) * / / * (p) (p) * / / * (s) (c) * \ * (c) */ do { parent = successor; successor = tmp; tmp = tmp->rb_left; } while (tmp); child2 = successor->rb_right; WRITE_ONCE(parent->rb_left, child2); WRITE_ONCE(successor->rb_right, child); rb_set_parent(child, successor);
                  augment->copy(node, successor); augment->propagate(parent, successor); }
                  tmp = node->rb_left; WRITE_ONCE(successor->rb_left, tmp); rb_set_parent(tmp, successor);
                  pc = node->__rb_parent_color; tmp = __rb_parent(pc); __rb_change_child(node, successor, tmp, root);
                  if (child2) { successor->__rb_parent_color = pc; rb_set_parent_color(child2, parent, RB_BLACK); rebalance = NULL; } else { unsigned long pc2 = successor->__rb_parent_color; successor->__rb_parent_color = pc; rebalance = __rb_is_black(pc2) ? parent : NULL; } tmp = successor; }
                  augment->propagate(tmp, NULL); return rebalance;}



                  4.2调整


                  在进行调整步骤之前我们知道,"继任"这一步返回了一个rebulance指针,并且作为参数传递给了调整函数。这个rebulance指针告诉了调整函数哪个节点是左右不平衡的、需要调整的。在整个调整过程中我们需要三个指针:

                  1.parent指针,该指针指向左右不平衡的节点2.node指针,该指针指向轻的那一端3.sibling指针,该指针指向重的那一端

                  总共的可能有8种,本质上是4种,另外4种就是对称情况。如果之前的函数流程弄明白了,那么这个流程也不是问题了。下面是代码实现和图解。
                    static __always_inline void____rb_erase_color(struct rb_node *parent, struct rb_root *root,void (*augment_rotate)(struct rb_node *old, struct rb_node *new)){structrb_node *node = NULL, *sibling, *tmp1, *tmp2;
                    while (true) {/* * Loop invariants: * - node is black (or NULL on first iteration) * - node is not the root (parent is not NULL) * - All leaf paths going through parent and node have a * black node count that is 1 lower than other leaf paths. */ sibling = parent->rb_right;if (node != sibling) { /* node == parent->rb_left */if (rb_is_red(sibling)) {/* * Case 1 - left rotate at parent * * P S * / \ / \ * N s --> p Sr * / \ / \ * Sl Sr N Sl */ tmp1 = sibling->rb_left; WRITE_ONCE(parent->rb_right, tmp1); WRITE_ONCE(sibling->rb_left, parent); rb_set_parent_color(tmp1, parent, RB_BLACK); __rb_rotate_set_parents(parent, sibling, root, RB_RED); augment_rotate(parent, sibling); sibling = tmp1; } tmp1 = sibling->rb_right;if (!tmp1 || rb_is_black(tmp1)) { tmp2 = sibling->rb_left;if (!tmp2 || rb_is_black(tmp2)) {/* * Case 2 - sibling color flip * (p could be either color here) * * (p) (p) * / \ / \ * N S --> N s * / \ / \ * Sl Sr Sl Sr * * This leaves us violating 5) which * can be fixed by flipping p to black * if it was red, or by recursing at p. * p is red when coming from Case 1. */ rb_set_parent_color(sibling, parent, RB_RED);if (rb_is_red(parent)) rb_set_black(parent);else { node = parent; parent = rb_parent(node);if (parent)continue; }break; }/* * Case 3 - right rotate at sibling * (p could be either color here) * * (p) (p) * / \ / \ * N S --> N Sl * / \ \ * sl Sr s * \ * Sr */ tmp1 = tmp2->rb_right; WRITE_ONCE(sibling->rb_left, tmp1); WRITE_ONCE(tmp2->rb_right, sibling); WRITE_ONCE(parent->rb_right, tmp2);if (tmp1) rb_set_parent_color(tmp1, sibling, RB_BLACK); augment_rotate(sibling, tmp2); tmp1 = sibling; sibling = tmp2; }/* * Case 4 - left rotate at parent + color flips * (p and sl could be either color here. * After rotation, p becomes black, s acquires * p's color, and sl keeps its color) * * (p) (s) * / \ / \ * N S --> P Sr * / \ / \ * (sl) sr N (sl) */ tmp2 = sibling->rb_left; WRITE_ONCE(parent->rb_right, tmp2); WRITE_ONCE(sibling->rb_left, parent); rb_set_parent_color(tmp1, sibling, RB_BLACK);if (tmp2) rb_set_parent(tmp2, parent); __rb_rotate_set_parents(parent, sibling, root, RB_BLACK); augment_rotate(parent, sibling);break; } else { sibling = parent->rb_left;if (rb_is_red(sibling)) {/* Case 1 - right rotate at parent */ tmp1 = sibling->rb_right; WRITE_ONCE(parent->rb_left, tmp1); WRITE_ONCE(sibling->rb_right, parent); rb_set_parent_color(tmp1, parent, RB_BLACK); __rb_rotate_set_parents(parent, sibling, root, RB_RED); augment_rotate(parent, sibling); sibling = tmp1; } tmp1 = sibling->rb_left;if (!tmp1 || rb_is_black(tmp1)) { tmp2 = sibling->rb_right;if (!tmp2 || rb_is_black(tmp2)) {/* Case 2 - sibling color flip */ rb_set_parent_color(sibling, parent, RB_RED);if (rb_is_red(parent)) rb_set_black(parent);else { node = parent; parent = rb_parent(node);if (parent)continue; }break; }/* Case 3 - right rotate at sibling */ tmp1 = tmp2->rb_left; WRITE_ONCE(sibling->rb_right, tmp1); WRITE_ONCE(tmp2->rb_left, sibling); WRITE_ONCE(parent->rb_left, tmp2);if (tmp1) rb_set_parent_color(tmp1, sibling, RB_BLACK); augment_rotate(sibling, tmp2); tmp1 = sibling; sibling = tmp2; }/* Case 4 - left rotate at parent + color flips */ tmp2 = sibling->rb_right; WRITE_ONCE(parent->rb_left, tmp2); WRITE_ONCE(sibling->rb_right, parent); rb_set_parent_color(tmp1, sibling, RB_BLACK);if (tmp2) rb_set_parent(tmp2, parent); __rb_rotate_set_parents(parent, sibling, root, RB_BLACK); augment_rotate(parent, sibling);break; } }}




                    扫码或长按关注

                    回复「 加群 」进入技术群聊


                    ----------------------------------------------------------------------------------------------------------------------
                    我们尊重原创,也注重分享,文章来源于微信公众号:嵌入式Linux,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
                    ----------------------------------------------------------------------------------------------------------------------

                    鲜花

                    握手

                    雷人

                    路过

                    鸡蛋

                    yafeilinux和他的朋友们微信公众号二维码

                    微信公众号

                    专注于Qt嵌入式Linux开发等。扫一扫立即关注。

                    Qt开源社区官方QQ群二维码

                    QQ交流群

                    欢迎加入QQ群大家庭,一起讨论学习!

                    我有话说......