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);  in insert()
50 	rb_erase(&node->rb, root);  in erase()
56 	if (node->rb.rb_left) {  in augment_recompute()
57 		child_augmented = rb_entry(node->rb.rb_left, struct test_node,  in augment_recompute()
58 					   rb)->augmented;  in augment_recompute()
62 	if (node->rb.rb_right) {  in augment_recompute()
63 		child_augmented = rb_entry(node->rb.rb_right, struct test_node,  in augment_recompute()
64 					   rb)->augmented;  in augment_recompute()
71 RB_DECLARE_CALLBACKS(static, augment_callbacks, struct test_node, rb,  in RB_DECLARE_CALLBACKS()  argument
83 		parent = rb_entry(rb_parent, struct test_node, rb);  in RB_DECLARE_CALLBACKS()
87 			new = &parent->rb.rb_left;  in RB_DECLARE_CALLBACKS()
89 			new = &parent->rb.rb_right;  in RB_DECLARE_CALLBACKS()
93 	rb_link_node(&node->rb, rb_parent, new);  in RB_DECLARE_CALLBACKS()
94 	rb_insert_augmented(&node->rb, root, &augment_callbacks);  in RB_DECLARE_CALLBACKS()
99 	rb_erase_augmented(&node->rb, root, &augment_callbacks);  in erase_augmented()
111 static bool is_red(struct rb_node *rb)  in is_red()  argument
113 	return !(rb->__rb_parent_color & 1);  in is_red()
116 static int black_path_count(struct rb_node *rb)  in black_path_count()  argument
119 	for (count = 0; rb; rb = rb_parent(rb))  in black_path_count()
120 		count += !is_red(rb);  in black_path_count()
128 	rbtree_postorder_for_each_entry_safe(cur, n, &root, rb)  in check_postorder_foreach()
136 	struct rb_node *rb;  in check_postorder()  local
138 	for (rb = rb_first_postorder(&root); rb; rb = rb_next_postorder(rb))  in check_postorder()
146 	struct rb_node *rb;  in check()  local
150 	for (rb = rb_first(&root); rb; rb = rb_next(rb)) {  in check()
151 		struct test_node *node = rb_entry(rb, struct test_node, rb);  in check()
153 		WARN_ON_ONCE(is_red(rb) &&  in check()
154 			     (!rb_parent(rb) || is_red(rb_parent(rb))));  in check()
156 			blacks = black_path_count(rb);  in check()
158 			WARN_ON_ONCE((!rb->rb_left || !rb->rb_right) &&  in check()
159 				     blacks != black_path_count(rb));  in check()
173 	struct rb_node *rb;  in check_augmented()  local
176 	for (rb = rb_first(&root); rb; rb = rb_next(rb)) {  in check_augmented()
177 		struct test_node *node = rb_entry(rb, struct test_node, rb);  in check_augmented()