Lines Matching +full:max +full:- +full:functions
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 ---------------------------------------
55 users are expected to write their own tree search and insert functions
56 which call the provided rbtree functions. Locking is also left up to the
60 ---------------------
79 ----------------------------------
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 -----------------------------
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);
137 rb_link_node(&data->node, parent, new);
138 rb_insert_color(&data->node, root);
144 ------------------------------------------------
155 rb_erase(&data->node, &mytree);
164 Replacing a node this way does not re-sort the tree: If the new node doesn't
168 ------------------------------------------------------------------
170 Four functions are provided for iterating through an rbtree's contents in
185 The iterator functions return a pointer to the embedded struct rb_node, from
194 printk("key=%s\n", rb_entry(node, struct mytype, node)->keystring);
197 --------------
230 -----------------------------
238 functions with the user provided augmentation callback when inserting
257 rb_erase(). rb_erase_augmented() calls back into user provided functions
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
283 Interval tree is an example of augmented rb tree. Reference -
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) {
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;
352 if (max < subtree_last)
353 max = 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;
358 if (max < subtree_last)
359 max = subtree_last;
361 return max;
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);