Lines Matching +full:root +full:- +full:node
2 Red-black Trees (rbtree) in Linux
9 What are red-black trees, and what are they for?
10 ------------------------------------------------
12 Red-black trees are a type of self-balancing binary search tree, used for
19 Red-black trees are similar to AVL trees, but provide faster real-time bounded
26 There are a number of red-black trees in use in the kernel.
29 The high-resolution timer code uses an rbtree to organize outstanding
31 red-black tree. Virtual memory areas (VMAs) are tracked with red-black
38 Linux Weekly News article on red-black trees
41 Wikipedia entry on red-black trees
42 https://en.wikipedia.org/wiki/Red-black_tree
44 Linux implementation of red-black trees
45 ---------------------------------------
60 ---------------------
65 struct rb_node node;
71 individual members may be accessed directly via rb_entry(node, type, member).
73 At the root of each rbtree is an rb_root structure, which is initialized to be
79 ----------------------------------
82 root, compare each value, and follow the left or right branch as necessary.
86 struct mytype *my_search(struct rb_root *root, char *string)
88 struct rb_node *node = root->rb_node;
90 while (node) {
91 struct mytype *data = container_of(node, struct mytype, node);
94 result = strcmp(string, data->keystring);
97 node = node->rb_left;
99 node = node->rb_right;
107 -----------------------------
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.
118 int my_insert(struct rb_root *root, struct mytype *data)
120 struct rb_node **new = &(root->rb_node), *parent = NULL;
122 /* Figure out where to put new node */
124 struct mytype *this = container_of(*new, struct mytype, node);
125 int result = strcmp(data->keystring, this->keystring);
129 new = &((*new)->rb_left);
131 new = &((*new)->rb_right);
136 /* Add new node and rebalance tree. */
137 rb_link_node(&data->node, parent, new);
138 rb_insert_color(&data->node, root);
144 ------------------------------------------------
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.
168 ------------------------------------------------------------------
176 struct rb_node *rb_next(struct rb_node *node);
177 struct rb_node *rb_prev(struct rb_node *node);
179 To start iterating, call rb_first() or rb_last() with a pointer to the root
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);
197 --------------
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 *,
230 -----------------------------
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
263 - A propagation callback, which updates the augmented value for a given
264 node and its ancestors, up to a given stop point (or NULL to update
265 all the way to the root).
267 - A copy callback, which copies the augmented value for a given subtree
268 to a newly assigned subtree root.
270 - A tree rotation callback, which copies the augmented value for a given
271 subtree to a newly assigned subtree root AND recomputes the augmented
272 information for the former subtree root.
283 Interval tree is an example of augmented rb tree. Reference -
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
302 interval_tree_first_match(struct rb_root *root,
305 struct interval_tree_node *node;
307 if (!root->rb_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,
316 if (left->__subtree_last >= start) {
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,
351 struct interval_tree_node, rb)->__subtree_last;
355 if (node->rb.rb_right) {
356 subtree_last = rb_entry(node->rb.rb_right,
357 struct interval_tree_node, rb)->__subtree_last;
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);
384 new->__subtree_last = old->__subtree_last;
394 new->__subtree_last = old->__subtree_last;
395 old->__subtree_last = compute_subtree_last(old);
402 void interval_tree_insert(struct interval_tree_node *node,
403 struct rb_root *root)
405 struct rb_node **link = &root->rb_node, *rb_parent = NULL;
406 unsigned long start = node->start, last = node->last;
412 if (parent->__subtree_last < last)
413 parent->__subtree_last = last;
414 if (start < parent->start)
415 link = &parent->rb.rb_left;
417 link = &parent->rb.rb_right;
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,
426 struct rb_root *root)
428 rb_erase_augmented(&node->rb, root, &augment_callbacks);