13 __param(int, nnodes, 100, "Number of nodes in the rb-tree");
14 __param(int, perf_loops, 1000, "Number of iterations modifying the rb-tree");
15 __param(int, check_loops, 100, "Number of iterations modifying and verifying the rb-tree");
19 	struct rb_node rb;  member
38 		if (key < rb_entry(parent, struct test_node, rb)->key)  in insert()
44 	rb_link_node(&node->rb, parent, new);  in insert()
45 	rb_insert_color(&node->rb, &root->rb_root);  in insert()
56 		if (key < rb_entry(parent, struct test_node, rb)->key)  in insert_cached()
64 	rb_link_node(&node->rb, parent, new);  in insert_cached()
65 	rb_insert_color_cached(&node->rb, root, leftmost);  in insert_cached()
70 	rb_erase(&node->rb, &root->rb_root);  in erase()
75 	rb_erase_cached(&node->rb, root);  in erase_cached()
82 	if (node->rb.rb_left) {  in augment_recompute()
83 		child_augmented = rb_entry(node->rb.rb_left, struct test_node,  in augment_recompute()
84 					   rb)->augmented;  in augment_recompute()
88 	if (node->rb.rb_right) {  in augment_recompute()
89 		child_augmented = rb_entry(node->rb.rb_right, struct test_node,  in augment_recompute()
90 					   rb)->augmented;  in augment_recompute()
97 RB_DECLARE_CALLBACKS(static, augment_callbacks, struct test_node, rb,  in RB_DECLARE_CALLBACKS()  argument
110 		parent = rb_entry(rb_parent, struct test_node, rb);  in RB_DECLARE_CALLBACKS()
114 			new = &parent->rb.rb_left;  in RB_DECLARE_CALLBACKS()
116 			new = &parent->rb.rb_right;  in RB_DECLARE_CALLBACKS()
120 	rb_link_node(&node->rb, rb_parent, new);  in RB_DECLARE_CALLBACKS()
121 	rb_insert_augmented(&node->rb, &root->rb_root, &augment_callbacks);  in RB_DECLARE_CALLBACKS()
135 		parent = rb_entry(rb_parent, struct test_node, rb);  in insert_augmented_cached()
139 			new = &parent->rb.rb_left;  in insert_augmented_cached()
141 			new = &parent->rb.rb_right;  in insert_augmented_cached()
147 	rb_link_node(&node->rb, rb_parent, new);  in insert_augmented_cached()
148 	rb_insert_augmented_cached(&node->rb, root,  in insert_augmented_cached()
155 	rb_erase_augmented(&node->rb, &root->rb_root, &augment_callbacks);  in erase_augmented()
161 	rb_erase_augmented_cached(&node->rb, root, &augment_callbacks);  in erase_augmented_cached()
173 static bool is_red(struct rb_node *rb)  in is_red()  argument
175 	return !(rb->__rb_parent_color & 1);  in is_red()
178 static int black_path_count(struct rb_node *rb)  in black_path_count()  argument
181 	for (count = 0; rb; rb = rb_parent(rb))  in black_path_count()
182 		count += !is_red(rb);  in black_path_count()
190 	rbtree_postorder_for_each_entry_safe(cur, n, &root.rb_root, rb)  in check_postorder_foreach()
198 	struct rb_node *rb;  in check_postorder()  local
200 	for (rb = rb_first_postorder(&root.rb_root); rb; rb = rb_next_postorder(rb))  in check_postorder()
208 	struct rb_node *rb;  in check()  local
212 	for (rb = rb_first(&root.rb_root); rb; rb = rb_next(rb)) {  in check()
213 		struct test_node *node = rb_entry(rb, struct test_node, rb);  in check()
215 		WARN_ON_ONCE(is_red(rb) &&  in check()
216 			     (!rb_parent(rb) || is_red(rb_parent(rb))));  in check()
218 			blacks = black_path_count(rb);  in check()
220 			WARN_ON_ONCE((!rb->rb_left || !rb->rb_right) &&  in check()
221 				     blacks != black_path_count(rb));  in check()
235 	struct rb_node *rb;  in check_augmented()  local
238 	for (rb = rb_first(&root.rb_root); rb; rb = rb_next(rb)) {  in check_augmented()
239 		struct test_node *node = rb_entry(rb, struct test_node, rb);  in check_augmented()