Lines Matching refs:node
25 struct rb_node *node = tree->rb_node;
27 return rb_entry(node, struct bfq_entity, rb_node);
315 * bfq_entity_of - get an entity from a node.
316 * @node: the node field of the entity.
318 * Convert a node pointer to the relative entity. This is used only
323 struct bfq_entity *bfq_entity_of(struct rb_node *node)
327 if (node)
328 entity = rb_entry(node, struct bfq_entity, rb_node);
382 struct rb_node **node = &root->rb_node;
385 while (*node) {
386 parent = *node;
390 node = &parent->rb_left;
392 node = &parent->rb_right;
395 rb_link_node(&entity->rb_node, parent, node);
404 * @node: one of its children.
408 * that the subtree rooted at @node (which may be its left or its right
411 static void bfq_update_min(struct bfq_entity *entity, struct rb_node *node)
415 if (node) {
416 child = rb_entry(node, struct bfq_entity, rb_node);
424 * @node: the node to update.
426 * @node may have changed position or one of its children may have moved,
430 static void bfq_update_active_node(struct rb_node *node)
432 struct bfq_entity *entity = rb_entry(node, struct bfq_entity, rb_node);
435 bfq_update_min(entity, node->rb_right);
436 bfq_update_min(entity, node->rb_left);
441 * @node: the starting node.
443 * @node must be the deepest modified node after an update. This function
449 static void bfq_update_active_tree(struct rb_node *node)
454 bfq_update_active_node(node);
456 parent = rb_parent(node);
460 if (node == parent->rb_left && parent->rb_right)
465 node = parent;
476 * per each node, containing the minimum value for the start times of
477 * its children (and the node itself), so it's possible to search for
478 * the eligible node with the lowest finish time in logarithmic time.
484 struct rb_node *node = &entity->rb_node;
488 if (node->rb_left)
489 node = node->rb_left;
490 else if (node->rb_right)
491 node = node->rb_right;
493 bfq_update_active_tree(node);
536 * bfq_find_deepest - find the deepest node that an extraction can modify.
537 * @node: the node being removed.
540 * node that will replace @node, and returning the deepest node that
541 * the following modifications to the tree can touch. If @node is the
542 * last node in the tree return %NULL.
544 static struct rb_node *bfq_find_deepest(struct rb_node *node)
548 if (!node->rb_right && !node->rb_left)
549 deepest = rb_parent(node);
550 else if (!node->rb_right)
551 deepest = node->rb_left;
552 else if (!node->rb_left)
553 deepest = node->rb_right;
555 deepest = rb_next(node);
558 else if (rb_parent(deepest) != node)
574 struct rb_node *node;
576 node = bfq_find_deepest(&entity->rb_node);
579 if (node)
580 bfq_update_active_tree(node);
1300 struct rb_node *node = st->active.rb_node;
1302 while (node) {
1303 entry = rb_entry(node, struct bfq_entity, rb_node);
1308 if (node->rb_left) {
1309 entry = rb_entry(node->rb_left,
1312 node = node->rb_left;
1318 node = node->rb_right;