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.bu...@hp.com>
---
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 majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
