summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDavidlohr Bueso <davidlohr.bueso@hp.com>2013-04-30 15:28:24 -0700
committerLinus Torvalds <torvalds@linux-foundation.org>2013-04-30 17:04:07 -0700
commit4130f0efbfe5adb360328b777afa8e45f7e467f7 (patch)
tree1067bb405268e345a2faa59f987491157bc82d2a
parent31c3a3fe0777642816045a8dd1b666f1718851d7 (diff)
rbtree_test: add extra rbtree integrity check
Account for the rbtree having 2**bh(v)-1 internal nodes. While this can be seen as a consequence of other checks, Michel states that it nicely sums up what the other properties are for. Signed-off-by: Davidlohr Bueso <davidlohr.bueso@hp.com> Reviewed-by: Michel Lespinasse <walken@google.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
-rw-r--r--lib/rbtree_test.c5
1 files changed, 3 insertions, 2 deletions
diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c
index af38aedbd874..99515038ff6d 100644
--- a/lib/rbtree_test.c
+++ b/lib/rbtree_test.c
@@ -117,8 +117,7 @@ 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 count = 0, blacks = 0;
u32 prev_key = 0;
for (rb = rb_first(&root); rb; rb = rb_next(rb)) {
@@ -134,7 +133,9 @@ static void check(int nr_nodes)
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)