Lines Matching full:node
65 struct rb_node node;
71 individual members may be accessed directly via rb_entry(node, type, member).
88 struct rb_node *node = root->rb_node;
90 while (node) {
91 struct mytype *data = container_of(node, struct mytype, node);
97 node = node->rb_left;
99 node = node->rb_right;
110 new node, then inserting the node and rebalancing ("recoloring") the tree.
113 location of the pointer on which to graft the new node. The new node also
114 needs a link to its parent node for rebalancing purposes.
122 /* Figure out where to put new node */
124 struct mytype *this = container_of(*new, struct mytype, node);
136 /* Add new node and rebalance tree. */
137 rb_link_node(&data->node, parent, new);
138 rb_insert_color(&data->node, root);
146 To remove an existing node from a tree, call::
155 rb_erase(&data->node, &mytree);
159 To replace an existing node in a tree with a new one with the same key, call::
164 Replacing a node this way does not re-sort the tree: If the new node doesn't
165 have the same key as the old node, the rbtree will probably become corrupted.
176 struct rb_node *rb_next(struct rb_node *node);
177 struct rb_node *rb_prev(struct rb_node *node);
180 of the tree, which will return a pointer to the node structure contained in
182 node by calling rb_next() or rb_prev() on the current node. This will return
188 rb_entry(node, type, member).
192 struct rb_node *node;
193 for (node = rb_first(&mytree); node; node = rb_next(node))
194 printk("key=%s\n", rb_entry(node, struct mytype, node)->keystring);
199 Computing the leftmost (smallest) node is quite a common task for binary
212 leftmost node. This allows rb_root_cached to exist wherever rb_root does,
218 void rb_erase_cached(struct rb_node *node, struct rb_root_cached *);
223 void rb_insert_augmented_cached(struct rb_node *node, struct rb_root_cached *,
233 each node, where the additional data for node N must be a function of
250 leading to the inserted node, then call rb_link_node() as usual and
256 When erasing a node, the user must call rb_erase_augmented() instead of
264 node and its ancestors, up to a given stop point (or NULL to update
294 This "extra information" stored in each node is the maximum hi
296 information can be maintained at each node just be looking at the node
305 struct interval_tree_node *node;
309 node = rb_entry(root->rb_node, struct interval_tree_node, rb);
312 if (node->rb.rb_left) {
314 rb_entry(node->rb.rb_left,
319 * Iterate to find the leftmost such node N.
325 node = left;
329 if (node->start <= last) { /* Cond1 */
330 if (node->last >= start) /* Cond2 */
331 return node; /* node is leftmost match */
332 if (node->rb.rb_right) {
333 node = rb_entry(node->rb.rb_right,
335 if (node->__subtree_last >= start)
346 compute_subtree_last(struct interval_tree_node *node)
348 unsigned long max = node->last, subtree_last;
349 if (node->rb.rb_left) {
350 subtree_last = rb_entry(node->rb.rb_left,
355 if (node->rb.rb_right) {
356 subtree_last = rb_entry(node->rb.rb_right,
367 struct interval_tree_node *node =
369 unsigned long subtree_last = compute_subtree_last(node);
370 if (node->__subtree_last == subtree_last)
372 node->__subtree_last = subtree_last;
373 rb = rb_parent(&node->rb);
402 void interval_tree_insert(struct interval_tree_node *node,
406 unsigned long start = node->start, last = node->last;
420 node->__subtree_last = last;
421 rb_link_node(&node->rb, rb_parent, link);
422 rb_insert_augmented(&node->rb, root, &augment_callbacks);
425 void interval_tree_remove(struct interval_tree_node *node,
428 rb_erase_augmented(&node->rb, root, &augment_callbacks);