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

/*
 * Iterate task_group tree rooted at *from, calling @down when first entering a
 * node and @up when leaving it for the final time.
 *
 * Caller must hold rcu_lock or sufficient equivalent.
 */
// 巧妙的树遍历 树的遍历[20141120 gliethttp]
// O0
// ↓
// O1 - O2 - O10 - O11
//      ↓
//      O3 - O6
//      |    ↓
//      ↓       O7 - O8 - O9
//      O4 - O5
// 遍历顺序为<node有children的话, 递归找到该node级联的所有child node的最左侧的node开始遍历>
// 1. O0 -> down(from = O0)
// 2. O1 -> down(O0的children, O1临时变为parent)
// 3. O1 -> up(因为O1没有children), parent回退指向O0, child指向O1, 然后goto up:继续执行O1所在的siblings
// 4. O2 -> down(O2临时变为parent)
// 5. O3 -> down(O2的children, O3临时变为parent)
// 6. O4 -> down(O3的children, O4临时变为parent)
// 7. O4 -> up(因为O4没有children), parent回退指向O3, child指向O4, 然后goto up:继续执行O4所在的siblings
// 8. O5 -> down(O4的siblings, O5临时变为parent)
// 9. O5 -> up(因为O5没有children), parent回退指向O3, child指向O5, 然后goto up:继续执行O5所在的siblings
//10. O3 -> up(因为O3->children已经到达结尾O5), parent回退指向O2, child指向O3, 然后goto up:继续执行O3所在的siblings
//11. O6 -> down(O3的siblings, O6临时变为parent)
//12. O7 -> down(O6的children, O7临时变为parent)
//13. O7 -> up(因为O7没有children), parent回退指向O6, child指向O7, 然后goto up:继续执行O7所在的siblings
//14. O8 -> down(O7的siblings, O8临时变为parent)
//15. O8 -> up(因为O8没有children), parent回退指向O6, child指向O8, 然后goto up:继续执行O8所在的siblings
//16. O9 -> down(O8的siblings, O9临时变为parent)
//17. O9 -> up(因为O9没有children), parent回退指向O6, child指向O9, 然后goto up:继续执行O9所在的siblings
//18. O6 -> up(因为O6->children已经到达结尾O9), parent回退指向O2, child指向O6, 然后goto up:继续执行O6所在的siblings
//19. O2 -> up(因为O2->children已经到达结尾O6), parent回退指向O0, child指向O2, 然后goto up:继续执行O2所在的siblings
//20. O10-> down(O2的siblings, O10临时变为parent)
//21. O10-> up(因为O10没有children), parent回退指向O0, child指向O10, 然后goto up:继续执行O10所在的siblings
//22. O11-> down(O10的siblings, O11临时变为parent)
//21. O11-> up(因为O11没有children), parent回退指向O0, child指向O11, 然后goto up:继续执行O11所在的siblings
//22. O0 -> up(因为O0->children已经到达结尾O11), parent == from, 然后goto out;所以树的遍历至此结束[gliethttp]

int walk_tg_tree_from(struct task_group *from,
                 tg_visitor down, tg_visitor up, void *data)
{
    struct task_group *parent, *child;
    int ret;

    parent = from;

down:
    ret = (*down)(parent, data);
    if (ret)
        goto out;
    list_for_each_entry_rcu(child, &parent->children, siblings) {
        parent = child;
        goto down;

up:
        continue;
    }
    ret = (*up)(parent, data);
    if (ret || parent == from)
        goto out;

    child = parent;
    parent = parent->parent;
    if (parent)
        goto up;
out:
    return ret;
}