lkml.org 
[lkml]   [2013]   [Mar]   [18]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Subject[PATCH 3/3] rbtree_test: add more rbtree integrity checks
From
Date
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@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





\
 
 \ /
  Last update: 2013-03-19 00:41    [W:0.088 / U:0.056 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site