Lines Matching +full:in +full:- +full:tree
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
16 be easily traversed in order, and must be tuned for a specific size and
19 Red-black trees are similar to AVL trees, but provide faster real-time bounded
21 three rotations, respectively, to balance the tree), with slightly slower
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
30 timer requests. The ext3 filesystem tracks directory entries in a
31 red-black tree. Virtual memory areas (VMAs) are tracked with red-black
33 packets in the "hierarchical token bucket" scheduler.
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 ---------------------------------------
47 Linux's rbtree implementation lives in the file "lib/rbtree.c". To use it,
52 tree implementations. Instead of using pointers to separate rb_node and data
53 structures, each instance of struct rb_node is embedded in the data structure
55 users are expected to write their own tree search and insert functions
60 ---------------------
62 Data nodes in an rbtree tree are structures containing a struct rb_node member::
70 structure may be accessed with the standard container_of() macro. In addition,
78 Searching for a value in an rbtree
79 ----------------------------------
81 Writing a search function for your tree is fairly straightforward: start at the
88 struct rb_node *node = root->rb_node;
94 result = strcmp(string, data->keystring);
97 node = node->rb_left;
99 node = node->rb_right;
107 -----------------------------
109 Inserting data in the tree involves first searching for the place to insert the
110 new node, then inserting the node and rebalancing ("recoloring") the tree.
120 struct rb_node **new = &(root->rb_node), *parent = NULL;
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);
143 Removing or replacing existing data in an rbtree
144 ------------------------------------------------
146 To remove an existing node from a tree, call::
148 void rb_erase(struct rb_node *victim, struct rb_root *tree);
155 rb_erase(&data->node, &mytree);
159 To replace an existing node in a tree with a new one with the same key, call::
162 struct rb_root *tree);
164 Replacing a node this way does not re-sort the tree: If the new node doesn't
167 Iterating through the elements stored in an rbtree (in sort order)
168 ------------------------------------------------------------------
170 Four functions are provided for iterating through an rbtree's contents in
174 struct rb_node *rb_first(struct rb_root *tree);
175 struct rb_node *rb_last(struct rb_root *tree);
180 of the tree, which will return a pointer to the node structure contained in
181 the first or last element in the tree. To continue, fetch the next or previous
194 printk("key=%s\n", rb_entry(node, struct mytype, node)->keystring);
197 --------------
203 potentially expensive tree iterations. This is done at negligible runtime
216 struct rb_node *rb_first_cached(struct rb_root_cached *tree);
230 -----------------------------
232 Augmented rbtree is an rbtree with "some" additional data stored in
234 the contents of all nodes in the subtree rooted at N. This data can
260 In both cases, the callbacks are provided through struct rb_augment_callbacks.
263 - A propagation callback, which updates the augmented value for a given
267 - A copy callback, which copies the augmented value for a given subtree
270 - A tree rotation callback, which copies the augmented value for a given
275 copy callbacks, which results in a large function, so each augmented rbtree
276 user should have a single rb_erase_augmented() call site in order to limit
283 Interval tree is an example of augmented rb tree. Reference -
291 However, rbtree can be augmented to store such interval ranges in a structured
294 This "extra information" stored in each node is the maximum hi
297 and its immediate children. And this will be used in O(log n) lookup
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) {
318 * Some nodes in left subtree satisfy Cond2.
329 if (node->start <= last) { /* Cond1 */
330 if (node->last >= start) /* Cond2 */
332 if (node->rb.rb_right) {
333 node = rb_entry(node->rb.rb_right,
335 if (node->__subtree_last >= start)
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;
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);
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);
428 rb_erase_augmented(&node->rb, root, &augment_callbacks);