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 <[email protected]>
---
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
On Mon, Mar 18, 2013 at 4:21 PM, Davidlohr Bueso <[email protected]> wrote:
> 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.
> - 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));
> + }
This seems quite redundant with the previous test - if we're going to
visit each children, then at that point we're going to check that they
can't be black if their parent (the current node) is black. So I don't
see that the tests adds any coverage.
> WARN_ON_ONCE(count != nr_nodes);
> + WARN_ON_ONCE(count < (1 << black_path_count(rb_last(&root))) - 1);
I like this last check - it can also be seen as a consequence of the
others, but it it's only one line and it nicely sums up what the other
properties are for :)
--
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
On Thu, 2013-03-21 at 20:36 -0700, Michel Lespinasse wrote:
> On Mon, Mar 18, 2013 at 4:21 PM, Davidlohr Bueso <[email protected]> wrote:
> > 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.
>
> > - 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));
> > + }
>
> This seems quite redundant with the previous test - if we're going to
> visit each children, then at that point we're going to check that they
> can't be black if their parent (the current node) is black. So I don't
> see that the tests adds any coverage.
Hmm ok I see your point. I'll drop this test and just keep the last one.
Thanks for taking a look,
Davidlohr