对priority search tree的疑惑

embeddedlwp

prio_tree_remove函数中，最后会调用prio_tree_replace函数对节点进行替换

1. 143struct prio_tree_node *prio_tree_replace(struct prio_tree_root *root,
   
2. 144                struct prio_tree_node *old, struct prio_tree_node *node)
   
3. 145{
   
4. 146        INIT_PRIO_TREE_NODE(node);
   
5. 147
   
6. 148        if (prio_tree_root(old)) {
   
7. 149                BUG_ON(root->prio_tree_node != old);
   
8. 150                /*
   
9. 151                 * We can reduce root->index_bits here. However, it is complex
   
10. 152                 * and does not help much to improve performance (IMO).
    
11. 153                 */
    
12. 154                node->parent = node;
    
13. 155                root->prio_tree_node = node;
    
14. 156        } else {
    
15. 157                node->parent = old->parent;
    
16. 158                if (old->parent->left == old)
    
17. 159                        old->parent->left = node;
    
18. 160                else
    
19. 161                        old->parent->right = node;
    
20. 162        }
    
21. 163
    
22. 164        if (!prio_tree_left_empty(old)) {
    
23. 165                node->left = old->left;
    
24. 166                old->left->parent = node;
    
25. 167        }
    
26. 168
    
27. 169        if (!prio_tree_right_empty(old)) {
    
28. 170                node->right = old->right;
    
29. 171                old->righ人t->parent = node;
    
30. 172        }
    
31. 173
    
32. 174        return old;
    
33. 175}

复制代码

以cluter兄画的这个图为例，


prio_tree_replace函数会执行两次：

一：

4,3,7 ->left = 4,2,6
4,2,6->parent=4,3,7
=============
4,2,6->left=4,2,6
4,2,6->parent=4,2,6
=============
4,2,6->right=5,1,6
5,1,6->parent=4,2,6

二:

0,7,7->right=5,2,7
5,2,7->parent=0,7,7
============
5,2,7->left=5,2,7
5,2,7->parent=5,2,7
============
5,2,7->right=6,1,7
6,1,7->parent=5,2,7

从置换的结果来看，5,2,7的parent指针指向了自己，5,2,7的left指针指向了自己，而不是4,2,6，是我什么地方理解错了吗？

wangzhen11aaa

这里没有循环语句。怎么来的循环？
还有，如果删除掉一个节点，就需要一次替换就可以。
后面的替换者及以后的相互指针关系是保留下来的。没有变化。

embeddedlwp

回复 2# wangzhen11aaa

看prio_tree_remove函数的实现：

1. 264void prio_tree_remove(struct prio_tree_root *root, struct prio_tree_node *node)
   
2. 265{
   
3. 266        struct prio_tree_node *cur;
   
4. 267        unsigned long r_index, h_index_right, h_index_left;
   
5. 268
   
6. 269        cur = node;
   
7. 270
   
8. 271        while (!prio_tree_left_empty(cur) || !prio_tree_right_empty(cur)) {
   
9. 272                if (!prio_tree_left_empty(cur))
   
10. 273                        get_index(root, cur->left, &r_index, &h_index_left);
    
11. 274                else {
    
12. 275                        cur = cur->right;
    
13. 276                        continue;
    
14. 277                }
    
15. 278
    
16. 279                if (!prio_tree_right_empty(cur))
    
17. 280                        get_index(root, cur->right, &r_index, &h_index_right);
    
18. 281                else {
    
19. 282                        cur = cur->left;
    
20. 283                        continue;
    
21. 284                }
    
22. 285
    
23. 286                /* both h_index_left and h_index_right cannot be 0 */
    
24. 287                if (h_index_left >= h_index_right)
    
25. 288                        cur = cur->left;
    
26. 289                else
    
27. 290                        cur = cur->right;
    
28. 291        }
    
29. 292
    
30. 293        if (prio_tree_root(cur)) {
    
31. 294                BUG_ON(root->prio_tree_node != cur);
    
32. 295                __INIT_PRIO_TREE_ROOT(root, root->raw);
    
33. 296                return
    
34. 297        }
    
35. 298
    
36. 299        if (cur->parent->right == cur)
    
37. 300                cur->parent->right = cur->parent;
    
38. 301        else
    
39. 302                cur->parent->left = cur->parent;
    
40. 303
    
41. 304        while (cur != node)
    
42. 305                cur = prio_tree_replace(root, cur->parent, cur);
    
43. 306}

复制代码

最后是有一个循环的。

从cluter兄的那个例子来看，这里需要置换两次，把真实节点带入代码中，如上面我的分析，“5,2,7的parent指针指向了自己，5,2,7的left指针指向了自己，而不是4,2,6，”
这样5,2,7的parent,left都指错了位置，请指教～！

   

embeddedlwp

顶起～！

embeddedlwp

顶起！

embeddedlwp

顶起！

embeddedlwp

顶起！