Lines Matching refs:node
62 struct rb_node node;
68 individual members may be accessed directly via rb_entry(node, type, member).
85 struct rb_node *node = root->rb_node;
87 while (node) {
88 struct mytype *data = container_of(node, struct mytype, node);
94 node = node->rb_left;
96 node = node->rb_right;
107 new node, then inserting the node and rebalancing ("recoloring") the tree.
110 location of the pointer on which to graft the new node. The new node also
111 needs a link to its parent node for rebalancing purposes.
119 /* Figure out where to put new node */
121 struct mytype *this = container_of(*new, struct mytype, node);
133 /* Add new node and rebalance tree. */
134 rb_link_node(&data->node, parent, new);
135 rb_insert_color(&data->node, root);
143 To remove an existing node from a tree, call:
152 rb_erase(&data->node, &mytree);
156 To replace an existing node in a tree with a new one with the same key, call:
161 Replacing a node this way does not re-sort the tree: If the new node doesn't
162 have the same key as the old node, the rbtree will probably become corrupted.
173 struct rb_node *rb_next(struct rb_node *node);
174 struct rb_node *rb_prev(struct rb_node *node);
177 of the tree, which will return a pointer to the node structure contained in
179 node by calling rb_next() or rb_prev() on the current node. This will return
185 rb_entry(node, type, member).
189 struct rb_node *node;
190 for (node = rb_first(&mytree); node; node = rb_next(node))
191 printk("key=%s\n", rb_entry(node, struct mytype, node)->keystring);
197 each node, where the additional data for node N must be a function of
214 leading to the inserted node, then call rb_link_node() as usual and
220 When erasing a node, the user must call rb_erase_augmented() instead of
228 node and its ancestors, up to a given stop point (or NULL to update
257 This "extra information" stored in each node is the maximum hi
259 information can be maintained at each node just be looking at the node
268 struct interval_tree_node *node;
272 node = rb_entry(root->rb_node, struct interval_tree_node, rb);
275 if (node->rb.rb_left) {
277 rb_entry(node->rb.rb_left,
282 * Iterate to find the leftmost such node N.
288 node = left;
292 if (node->start <= last) { /* Cond1 */
293 if (node->last >= start) /* Cond2 */
294 return node; /* node is leftmost match */
295 if (node->rb.rb_right) {
296 node = rb_entry(node->rb.rb_right,
298 if (node->__subtree_last >= start)
309 compute_subtree_last(struct interval_tree_node *node)
311 unsigned long max = node->last, subtree_last;
312 if (node->rb.rb_left) {
313 subtree_last = rb_entry(node->rb.rb_left,
318 if (node->rb.rb_right) {
319 subtree_last = rb_entry(node->rb.rb_right,
330 struct interval_tree_node *node =
332 unsigned long subtree_last = compute_subtree_last(node);
333 if (node->__subtree_last == subtree_last)
335 node->__subtree_last = subtree_last;
336 rb = rb_parent(&node->rb);
365 void interval_tree_insert(struct interval_tree_node *node,
369 unsigned long start = node->start, last = node->last;
383 node->__subtree_last = last;
384 rb_link_node(&node->rb, rb_parent, link);
385 rb_insert_augmented(&node->rb, root, &augment_callbacks);
388 void interval_tree_remove(struct interval_tree_node *node,
391 rb_erase_augmented(&node->rb, root, &augment_callbacks);