[PATCH 3/3] rbtree_test: add more rbtree integrity checks

[Davidlohr Bueso]

When checking the rbtree, account for more properties:

   - Both children of a red node are black.
   - The tree has at least 2**bh(v)-1 internal nodes.

Signed-off-by: Davidlohr Bueso <davidlohr.bueso@xxxxxx>
---
 lib/rbtree_test.c | 24 +++++++++++++++++++-----
 1 file changed, 19 insertions(+), 5 deletions(-)

diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c
index 0fea14e..4c84f85 100644
--- a/lib/rbtree_test.c
+++ b/lib/rbtree_test.c
@@ -106,7 +106,7 @@ static void init(void)
 
 static bool is_red(struct rb_node *rb)
 {
-	return !(rb->__rb_parent_color & 1);
+	return rb ? !(rb->__rb_parent_color & RB_BLACK) : 0;
 }
 
 static int black_path_count(struct rb_node *rb)
@@ -120,24 +120,38 @@ static int black_path_count(struct rb_node *rb)
 static void check(int nr_nodes)
 {
 	struct rb_node *rb;
-	int count = 0;
-	int blacks = 0;
+	int blacks = 0, count = 0;
 	u32 prev_key = 0;
 
 	for (rb = rb_first(&root); rb; rb = rb_next(rb)) {
 		struct test_node *node = rb_entry(rb, struct test_node, rb);
+
+		/* sorted keys */
 		WARN_ON_ONCE(node->key < prev_key);
-		WARN_ON_ONCE(is_red(rb) &&
-			     (!rb_parent(rb) || is_red(rb_parent(rb))));
+
+		if (is_red(rb)) {
+			/*
+			 * root must be black and no path contains two
+			 * consecutive red nodes.
+			 */
+			WARN_ON_ONCE(!rb_parent(rb) || is_red(rb_parent(rb)));
+
+			/* both children of a red node are black */
+			WARN_ON_ONCE(is_red(rb->rb_left) || is_red(rb->rb_right));
+		}
+
 		if (!count)
 			blacks = black_path_count(rb);
 		else
 			WARN_ON_ONCE((!rb->rb_left || !rb->rb_right) &&
 				     blacks != black_path_count(rb));
+
 		prev_key = node->key;
 		count++;
 	}
+
 	WARN_ON_ONCE(count != nr_nodes);
+	WARN_ON_ONCE(count < (1 << black_path_count(rb_last(&root))) - 1);
 }
 
 static void check_augmented(int nr_nodes)
-- 
1.7.11.7




--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/