2013-03-29 20:46:31

by Davidlohr Bueso

Subject: [PATCH v2 1/2] 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 <[email protected]>
---
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

2013-03-29 21:28:54

by Michel Lespinasse

Subject: Re: [PATCH v2 1/2] rbtree_test: add extra rbtree integrity check

On Fri, Mar 29, 2013 at 1:46 PM, Davidlohr Bueso <[email protected]> wrote:
> 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 <[email protected]>

Reviewed-by: Michel Lespinasse <[email protected]>

--
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.