linux-master/lib/rbtree_test.c

14 __param(int, nnodes, 100, "Number of nodes in the rb-tree");
15 __param(int, perf_loops, 1000, "Number of iterations modifying the rb-tree");
16 __param(int, check_loops, 100, "Number of iterations modifying and verifying the rb-tree");
20 	struct rb_node rb;
39 		if (key < rb_entry(parent, struct test_node, rb)->key)
45 	rb_link_node(&node->rb, parent, new);
46 	rb_insert_color(&node->rb, &root->rb_root);
57 		if (key < rb_entry(parent, struct test_node, rb)->key)
65 	rb_link_node(&node->rb, parent, new);
66 	rb_insert_color_cached(&node->rb, root, leftmost);
71 	rb_erase(&node->rb, &root->rb_root);
76 	rb_erase_cached(&node->rb, root);
83 			 struct test_node, rb, u32, augmented, NODE_VAL)
95 		parent = rb_entry(rb_parent, struct test_node, rb);
99 			new = &parent->rb.rb_left;
101 			new = &parent->rb.rb_right;
105 	rb_link_node(&node->rb, rb_parent, new);
106 	rb_insert_augmented(&node->rb, &root->rb_root, &augment_callbacks);
120 		parent = rb_entry(rb_parent, struct test_node, rb);
124 			new = &parent->rb.rb_left;
126 			new = &parent->rb.rb_right;
132 	rb_link_node(&node->rb, rb_parent, new);
133 	rb_insert_augmented_cached(&node->rb, root,
140 	rb_erase_augmented(&node->rb, &root->rb_root, &augment_callbacks);
146 	rb_erase_augmented_cached(&node->rb, root, &augment_callbacks);
158 static bool is_red(struct rb_node *rb)
160 	return !(rb->__rb_parent_color & 1);
163 static int black_path_count(struct rb_node *rb)
166 	for (count = 0; rb; rb = rb_parent(rb))
167 		count += !is_red(rb);
175 	rbtree_postorder_for_each_entry_safe(cur, n, &root.rb_root, rb)
183 	struct rb_node *rb;
185 	for (rb = rb_first_postorder(&root.rb_root); rb; rb = rb_next_postorder(rb))
193 	struct rb_node *rb;
197 	for (rb = rb_first(&root.rb_root); rb; rb = rb_next(rb)) {
198 		struct test_node *node = rb_entry(rb, struct test_node, rb);
200 		WARN_ON_ONCE(is_red(rb) &&
201 			     (!rb_parent(rb) || is_red(rb_parent(rb))));
203 			blacks = black_path_count(rb);
205 			WARN_ON_ONCE((!rb->rb_left || !rb->rb_right) &&
206 				     blacks != black_path_count(rb));
220 	struct rb_node *rb;
223 	for (rb = rb_first(&root.rb_root); rb; rb = rb_next(rb)) {
224 		struct test_node *node = rb_entry(rb, struct test_node, rb);
226 		if (node->rb.rb_left) {
227 			subtree = rb_entry(node->rb.rb_left, struct test_node,
228 					   rb)->augmented;
232 		if (node->rb.rb_right) {
233 			subtree = rb_entry(node->rb.rb_right, struct test_node,
234 					   rb)->augmented;