Messages in this thread | | | Subject | Re: [PATCH 3/3] rbtree_test: add more rbtree integrity checks | From | Davidlohr Bueso <> | Date | Fri, 22 Mar 2013 16:12:47 -0700 |
| |
On Thu, 2013-03-21 at 20:36 -0700, Michel Lespinasse wrote: > On Mon, Mar 18, 2013 at 4:21 PM, Davidlohr Bueso <davidlohr.bueso@hp.com> 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
| |