linux内核priority search tree详解--->王者归来，先发一篇狠的

cluter

回复 10# Godbach


    哦。。原来不知道啊，谢谢提醒哈。。

gooopler

大神 图片压缩一下啊，也挺清晰的
手机被你搞挂了！

cluter

回复 12# gooopler


    就怕看不清楚，错了，下次发附件。。。

lyq8382

不解释 先顶下

aweii

我最近也看了prio_tree的代码。对楼主的代码剖析有点异议。
按照根节点heap_index=7的话，root->index_bits=3没错，可是溢出子树以上应该有3层吧，lz少画了一层。根节点是不占用index_bits的，所以根节点的基索引不受r_index&mask的限制，从根节点的子节点开始才用
r_index&mask判断向左还是右遍历，遍历一层则mask>>1;直至mask==0,这样当要建立或访问溢出子树时已经遍历了4层（连根节点所在层）。

embeddedlwp

回复 15# aweii

从prio_tree_insert函数的这段代码来看：

1. 201        cur = root->prio_tree_node;
   
2. 202        mask = 1UL << (root->index_bits - 1);
   
3. 203
   
4. 204        while (mask) {
   
5. 205                get_index(root, cur, &r_index, &h_index);
   

复制代码

并没有区分是第0层，还是第1层啊
如果root->index_bits为3
那么
level  mask  
0        4         
1        2
2        1
3        1<<31   suboverflow tree



   

axlrose

感谢楼主分享，顶一个

aweii

判断的是下一层的路径取向，index & mask=1，向右子结点，否则向左子节点，所以mask对根节点不起作用,向下一层，则右移一位。3的话就是移3层。所以根节点下应有3层，然后才是溢出子树。另外《深入理解linux内核》书中这部分的示意图是错的，基索引相同的节点应该在一条路径上，但是该图把r_inde=0的节点放在了兄弟节点的位置，明显有问题。
if (index & mask) {
                        if (prio_tree_right_empty(cur)) {
                                INIT_PRIO_TREE_NODE(node);
                                cur->right = node;
                                node->parent = cur;
                                return res;
                        } else
                                cur = cur->right;
                } else {
                        if (prio_tree_left_empty(cur)) {
                                INIT_PRIO_TREE_NODE(node);
                                cur->left = node;
                                node->parent = cur;
                                return res;
                        } else
                                cur = cur->left;
                }

                mask >>= 1;
……

embeddedlwp

回复 18# aweii


判断的是下一层的路径取向，index & mask=1，向右子结点，否则向左子节点，所以mask对根节点不起作用,向下一层，则右移一位。3的话就是移3层。所以根节点下应有3层，然后才是溢出子树
======================================================
mask = 1UL << (root->index_bits - 1);
从这句来看，根的那层移位被忽略了，所以如果index_bits为3,那么这里的mask为1^2，也就是说只能移动两次，然后就是suboverflow tree了。所以根下边到suboverflow tree之间只能有两层

另外《深入理解linux内核》书中这部分的示意图是错的，基索引相同的节点应该在一条路径上，但是该图把r_inde=0的节点放在了兄弟节点的位置，明显有问题。
======================================================
对这个图我也比较疑惑，0,0,0与0,2,2为什么是这个排布
         
              0,4,4
       __  |   
      |
   0,2,2
  __ |
|
0,0,0

为什么不是这个样子？？


   

embeddedlwp

顶起！