lkml.org 
[lkml]   [2013]   [Mar]   [29]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Subject[PATCH v2 1/2] rbtree_test: add extra rbtree integrity check
From
Date
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>
---
lib/rbtree_test.c | 5 +++--
1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c
index af38aed..9951503 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)
--
1.7.11.7





\
 
 \ /
  Last update: 2013-03-29 22:21    [W:0.038 / U:0.112 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site