Lines Matching full:rb

283 Interval tree is an example of augmented rb tree. Reference -
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,
315 					 struct interval_tree_node, rb);
332 			if (node->rb.rb_right) {
333 				node = rb_entry(node->rb.rb_right,
334 					struct interval_tree_node, rb);
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;
364   static void augment_propagate(struct rb_node *rb, struct rb_node *stop)
366 	while (rb != stop) {
368 			rb_entry(rb, struct interval_tree_node, rb);
373 		rb = rb_parent(&node->rb);
380 		rb_entry(rb_old, struct interval_tree_node, rb);
382 		rb_entry(rb_new, struct interval_tree_node, rb);
390 		rb_entry(rb_old, struct interval_tree_node, rb);
392 		rb_entry(rb_new, struct interval_tree_node, rb);
411 		parent = rb_entry(rb_parent, struct interval_tree_node, rb);
415 			link = &parent->rb.rb_left;
417 			link = &parent->rb.rb_right;
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);