linux内核组调度树的遍历算法 - walk_tg_tree_from

点击(此处)折叠或打开

1. /*
   
2.  * Iterate task_group tree rooted at *from, calling @down when first entering a
   
3.  * node and @up when leaving it for the final time.
   
4.  *
   
5.  * Caller must hold rcu_lock or sufficient equivalent.
   
6.  */
   
7. // 巧妙的树遍历 树的遍历[20141120 gliethttp]
   
8. // O0
   
9. // ↓
   
10. // O1 - O2 - O10 - O11
    
11. //      ↓
    
12. //      O3 - O6
    
13. //      |    ↓
    
14. //      ↓    O7 - O8 - O9
    
15. //      O4 - O5
    
16. // 遍历顺序为<node有children的话, 递归找到该node级联的所有child node的最左侧的node开始遍历>
    
17. // 1. O0 -> down(from = O0)
    
18. // 2. O1 -> down(O0的children, O1临时变为parent)
    
19. // 3. O1 -> up(因为O1没有children), parent回退指向O0, child指向O1, 然后goto up:继续执行O1所在的siblings
    
20. // 4. O2 -> down(O2临时变为parent)
    
21. // 5. O3 -> down(O2的children, O3临时变为parent)
    
22. // 6. O4 -> down(O3的children, O4临时变为parent)
    
23. // 7. O4 -> up(因为O4没有children), parent回退指向O3, child指向O4, 然后goto up:继续执行O4所在的siblings
    
24. // 8. O5 -> down(O4的siblings, O5临时变为parent)
    
25. // 9. O5 -> up(因为O5没有children), parent回退指向O3, child指向O5, 然后goto up:继续执行O5所在的siblings
    
26. //10. O3 -> up(因为O3->children已经到达结尾O5), parent回退指向O2, child指向O3, 然后goto up:继续执行O3所在的siblings
    
27. //11. O6 -> down(O3的siblings, O6临时变为parent)
    
28. //12. O7 -> down(O6的children, O7临时变为parent)
    
29. //13. O7 -> up(因为O7没有children), parent回退指向O6, child指向O7, 然后goto up:继续执行O7所在的siblings
    
30. //14. O8 -> down(O7的siblings, O8临时变为parent)
    
31. //15. O8 -> up(因为O8没有children), parent回退指向O6, child指向O8, 然后goto up:继续执行O8所在的siblings
    
32. //16. O9 -> down(O8的siblings, O9临时变为parent)
    
33. //17. O9 -> up(因为O9没有children), parent回退指向O6, child指向O9, 然后goto up:继续执行O9所在的siblings
    
34. //18. O6 -> up(因为O6->children已经到达结尾O9), parent回退指向O2, child指向O6, 然后goto up:继续执行O6所在的siblings
    
35. //19. O2 -> up(因为O2->children已经到达结尾O6), parent回退指向O0, child指向O2, 然后goto up:继续执行O2所在的siblings
    
36. //20. O10-> down(O2的siblings, O10临时变为parent)
    
37. //21. O10-> up(因为O10没有children), parent回退指向O0, child指向O10, 然后goto up:继续执行O10所在的siblings
    
38. //22. O11-> down(O10的siblings, O11临时变为parent)
    
39. //21. O11-> up(因为O11没有children), parent回退指向O0, child指向O11, 然后goto up:继续执行O11所在的siblings
    
40. //22. O0 -> up(因为O0->children已经到达结尾O11), parent == from, 然后goto out;所以树的遍历至此结束[gliethttp]
    
41. 
    
42. int walk_tg_tree_from(struct task_group *from,
    
43.              tg_visitor down, tg_visitor up, void *data)
    
44. {
    
45.     struct task_group *parent, *child;
    
46.     int ret;
    
47. 
    
48.     parent = from;
    
49. 
    
50. down:
    
51.     ret = (*down)(parent, data);
    
52.     if (ret)
    
53.         goto out;
    
54.     list_for_each_entry_rcu(child, &parent->children, siblings) {
    
55.         parent = child;
    
56.         goto down;
    
57. 
    
58. up:
    
59.         continue;
    
60.     }
    
61.     ret = (*up)(parent, data);
    
62.     if (ret || parent == from)
    
63.         goto out;
    
64. 
    
65.     child = parent;
    
66.     parent = parent->parent;
    
67.     if (parent)
    
68.         goto up;
    
69. out:
    
70.     return ret;
    
71. }