Lines Matching refs:node
25 struct rb_node *node = tree->rb_node;
27 return rb_entry(node, struct bfq_entity, rb_node);
307 * bfq_entity_of - get an entity from a node.
308 * @node: the node field of the entity.
310 * Convert a node pointer to the relative entity. This is used only
315 struct bfq_entity *bfq_entity_of(struct rb_node *node)
319 if (node)
320 entity = rb_entry(node, struct bfq_entity, rb_node);
374 struct rb_node **node = &root->rb_node;
377 while (*node) {
378 parent = *node;
382 node = &parent->rb_left;
384 node = &parent->rb_right;
387 rb_link_node(&entity->rb_node, parent, node);
396 * @node: one of its children.
400 * that the subtree rooted at @node (which may be its left or its right
403 static void bfq_update_min(struct bfq_entity *entity, struct rb_node *node)
407 if (node) {
408 child = rb_entry(node, struct bfq_entity, rb_node);
416 * @node: the node to update.
418 * @node may have changed position or one of its children may have moved,
422 static void bfq_update_active_node(struct rb_node *node)
424 struct bfq_entity *entity = rb_entry(node, struct bfq_entity, rb_node);
427 bfq_update_min(entity, node->rb_right);
428 bfq_update_min(entity, node->rb_left);
433 * @node: the starting node.
435 * @node must be the deepest modified node after an update. This function
441 static void bfq_update_active_tree(struct rb_node *node)
446 bfq_update_active_node(node);
448 parent = rb_parent(node);
452 if (node == parent->rb_left && parent->rb_right)
457 node = parent;
468 * per each node, containing the minimum value for the start times of
469 * its children (and the node itself), so it's possible to search for
470 * the eligible node with the lowest finish time in logarithmic time.
476 struct rb_node *node = &entity->rb_node;
485 if (node->rb_left)
486 node = node->rb_left;
487 else if (node->rb_right)
488 node = node->rb_right;
490 bfq_update_active_tree(node);
540 * bfq_find_deepest - find the deepest node that an extraction can modify.
541 * @node: the node being removed.
544 * node that will replace @node, and returning the deepest node that
545 * the following modifications to the tree can touch. If @node is the
546 * last node in the tree return %NULL.
548 static struct rb_node *bfq_find_deepest(struct rb_node *node)
552 if (!node->rb_right && !node->rb_left)
553 deepest = rb_parent(node);
554 else if (!node->rb_right)
555 deepest = node->rb_left;
556 else if (!node->rb_left)
557 deepest = node->rb_right;
559 deepest = rb_next(node);
562 else if (rb_parent(deepest) != node)
578 struct rb_node *node;
585 node = bfq_find_deepest(&entity->rb_node);
588 if (node)
589 bfq_update_active_tree(node);
1354 struct rb_node *node = st->active.rb_node;
1356 while (node) {
1357 entry = rb_entry(node, struct bfq_entity, rb_node);
1362 if (node->rb_left) {
1363 entry = rb_entry(node->rb_left,
1366 node = node->rb_left;
1372 node = node->rb_right;