Lines Matching refs:rb

246 Interval tree is an example of augmented rb tree. Reference -
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,
278 					 struct interval_tree_node, rb);
295 			if (node->rb.rb_right) {
296 				node = rb_entry(node->rb.rb_right,
297 					struct interval_tree_node, rb);
312 	if (node->rb.rb_left) {
313 		subtree_last = rb_entry(node->rb.rb_left,
314 			struct interval_tree_node, rb)->__subtree_last;
318 	if (node->rb.rb_right) {
319 		subtree_last = rb_entry(node->rb.rb_right,
320 			struct interval_tree_node, rb)->__subtree_last;
327 static void augment_propagate(struct rb_node *rb, struct rb_node *stop)
329 	while (rb != stop) {
331 			rb_entry(rb, struct interval_tree_node, rb);
336 		rb = rb_parent(&node->rb);
343 		rb_entry(rb_old, struct interval_tree_node, rb);
345 		rb_entry(rb_new, struct interval_tree_node, rb);
353 		rb_entry(rb_old, struct interval_tree_node, rb);
355 		rb_entry(rb_new, struct interval_tree_node, rb);
374 		parent = rb_entry(rb_parent, struct interval_tree_node, rb);
378 			link = &parent->rb.rb_left;
380 			link = &parent->rb.rb_right;
384 	rb_link_node(&node->rb, rb_parent, link);
385 	rb_insert_augmented(&node->rb, root, &augment_callbacks);
391 	rb_erase_augmented(&node->rb, root, &augment_callbacks);