Lines Matching defs:tree
23 static struct bfq_entity *bfq_root_active_entity(struct rb_root *tree)
25 struct rb_node *node = tree->rb_node;
65 * reposition an entity in its active tree; see comments on
85 * sd->next_in_service, then a full lookup in the active tree
207 * removed from its active tree (which may get done after
320 * conversion mechanism because, e.g., in the tree walking functions,
334 * bfq_extract - remove an entity from a tree.
335 * @root: the tree root.
340 entity->tree = NULL;
345 * bfq_idle_extract - extract an entity from the idle tree.
346 * @st: the service tree of the owning @entity.
372 * bfq_insert - generic tree insertion.
373 * @root: tree root.
376 * This is used for the idle and the active tree, since they are both
398 entity->tree = root;
407 * min_start due to updates to the active tree. The function assumes
440 * bfq_update_active_tree - update min_start for the whole active tree.
470 * bfq_active_insert - insert an entity in the active tree of its
472 * @st: the service tree of the entity.
475 * The active tree is ordered by finish time, but an extra key is kept
539 * Do the first step of an extraction in an rb tree, looking for the
541 * the following modifications to the tree can touch. If @node is the
542 * last node in the tree return %NULL.
566 * bfq_active_extract - remove an entity from the active tree.
567 * @st: the service_tree containing the tree.
588 * bfq_idle_insert - insert an entity into the idle tree.
589 * @st: the service tree containing the tree.
612 * @st: the service tree.
620 * the queue, as the latter is also outside any service tree. If,
638 * bfq_put_idle_entity - release the idle tree ref of an entity.
639 * @st: service tree for the entity.
650 * bfq_forget_idle - update the idle tree if necessary.
651 * @st: the service tree to act upon.
654 * as the idle tree will not grow indefinitely this can be done safely.
664 * Forget the whole idle tree, increasing the vtime past
698 * entity may happen to be on some tree.
863 * tree, then it is safe to invoke next function with the last
924 * inserts entity into its active tree, after possibly extracting it
925 * from its idle tree.
941 if (entity->tree == &st->idle) {
943 * Must be on the idle tree, bfq_idle_extract() will
953 * would have been on the idle tree.
958 * entity is about to be inserted into a service tree,
981 * Basically, this function: 1) removes entity from its active tree if
983 * entity back into its active tree (in the new, right position for
1019 * the active tree. This implies that the position of
1020 * the entity in the active tree may need to be
1029 if (entity->tree)
1039 * i.e., the position in the active tree, of this
1058 entity->tree == &st->active)
1060 * in service or already queued on the active tree,
1066 * Not in service and not queued on its active tree:
1103 * idle tree.
1105 * If necessary and allowed, puts entity into the idle tree. NOTE:
1106 * entity may be on no tree if in service.
1141 if (entity->tree == &st->active)
1143 else if (!is_in_service && entity->tree == &st->idle)
1157 * @ins_into_idle_tree: true if the entity can be put into the idle tree
1173 * entity is not in any tree any more, so
1221 * Also let parent be queued into the idle tree on
1241 * active tree (because sd->next_in_service has
1262 * @st: the service tree to act upon.
1287 * @st: the service tree to select from.
1291 * root of the tree and going on the left every time on this side there is
1326 * @st: the service tree.
1328 * this active tree belongs to.
1365 * active tree belongs to, then push the system virtual time
1426 * tree. The reason why sd->in_service_entity is still
1501 * tree, so as to make sure that it won't be
1568 * service tree either, then release the service reference to
1641 * the service tree. As a special case, it can be invoked during an