| Message ID | 20240612055031.3607-6-chandrapratap3519@gmail.com (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | t: port reftable/tree_test.c to the unit testing framework | expand |
On Wed, Jun 12, 2024 at 11:08:14AM +0530, Chandra Pratap wrote: > In the current testing setup for infix_walk(), the following > properties of an infix traversal of a tree remain untested: > - every node of the tree must be visited > - every node must be visited exactly only s/only/once > and only the property 'traversal in increasing order' is tested. Nit: this reads a bit awkward. How about "In fact, we only verify that the traversal happens in increasing order." > @@ -51,6 +50,7 @@ static void test_infix_walk(void) > { > struct tree_node *root = NULL; > void *values[11] = { 0 }; > + void *out[20] = { 0 }; From the test below it looks like we only expect 11 values to be added to `out`. Why does this array have length 20? We could of course also use something like `ALLOC_GROW()` to grow the array dynamically. But that'd likely be overkill. > struct curry c = { 0 }; > size_t i = 1; > > @@ -59,7 +59,11 @@ static void test_infix_walk(void) > i = (i * 7) % 11; > } while (i != 1); > > - infix_walk(root, &check_increasing, &c); > + c.arr = (void **) &out; We can initialize this variable directly when declaring `c`: struct curry c = { .arr = &out; }; Also, is the cast necessary? This is the only site where we use `struct curry` if I'm not mistaken, so I'd expect that the type of `arr` should match our expectations. > + infix_walk(root, &store, &c); > + for (i = 1; i < ARRAY_SIZE(values); i++) > + check_pointer_eq(values + i, out[i - 1]); Let's also verify that `c.len` matches the expected number of nodes visited. Patrick > + check(!out[i]); > tree_free(root); > }
On Wed, 12 Jun 2024 at 12:29, Patrick Steinhardt <ps@pks.im> wrote: > > On Wed, Jun 12, 2024 at 11:08:14AM +0530, Chandra Pratap wrote: > > In the current testing setup for infix_walk(), the following > > properties of an infix traversal of a tree remain untested: > > - every node of the tree must be visited > > - every node must be visited exactly only > > s/only/once > > > and only the property 'traversal in increasing order' is tested. > > Nit: this reads a bit awkward. How about "In fact, we only verify that > the traversal happens in increasing order." > > > @@ -51,6 +50,7 @@ static void test_infix_walk(void) > > { > > struct tree_node *root = NULL; > > void *values[11] = { 0 }; > > + void *out[20] = { 0 }; > > From the test below it looks like we only expect 11 values to be added > to `out`. Why does this array have length 20? That's an error. I'll correct it in the next iteration. > We could of course also use something like `ALLOC_GROW()` to grow the > array dynamically. But that'd likely be overkill. > > > struct curry c = { 0 }; > > size_t i = 1; > > > > @@ -59,7 +59,11 @@ static void test_infix_walk(void) > > i = (i * 7) % 11; > > } while (i != 1); > > > > - infix_walk(root, &check_increasing, &c); > > + c.arr = (void **) &out; > > We can initialize this variable directly when declaring `c`: > > struct curry c = { > .arr = &out; > }; Right, this seems more concise. > Also, is the cast necessary? This is the only site where we use `struct > curry` if I'm not mistaken, so I'd expect that the type of `arr` should > match our expectations. Trying to do this without a cast produces the following compilation error for me: initialization of ‘void **’ from incompatible pointer type ‘void * (*)[11]’ > > + infix_walk(root, &store, &c); > > + for (i = 1; i < ARRAY_SIZE(values); i++) > > + check_pointer_eq(values + i, out[i - 1]); > > Let's also verify that `c.len` matches the expected number of nodes > visited. Sure.
diff --git a/t/unit-tests/t-reftable-tree.c b/t/unit-tests/t-reftable-tree.c index f1adab4458..917a64a7d1 100644 --- a/t/unit-tests/t-reftable-tree.c +++ b/t/unit-tests/t-reftable-tree.c @@ -15,15 +15,14 @@ static int test_compare(const void *a, const void *b) } struct curry { - void *last; + void **arr; + size_t i; }; -static void check_increasing(void *arg, void *key) +static void store(void *arg, void *key) { struct curry *c = arg; - if (c->last) - check_int(test_compare(c->last, key), <, 0); - c->last = key; + c->arr[c->i++] = key; } static void test_tree_search(void) @@ -51,6 +50,7 @@ static void test_infix_walk(void) { struct tree_node *root = NULL; void *values[11] = { 0 }; + void *out[20] = { 0 }; struct curry c = { 0 }; size_t i = 1; @@ -59,7 +59,11 @@ static void test_infix_walk(void) i = (i * 7) % 11; } while (i != 1); - infix_walk(root, &check_increasing, &c); + c.arr = (void **) &out; + infix_walk(root, &store, &c); + for (i = 1; i < ARRAY_SIZE(values); i++) + check_pointer_eq(values + i, out[i - 1]); + check(!out[i]); tree_free(root); }
In the current testing setup for infix_walk(), the following properties of an infix traversal of a tree remain untested: - every node of the tree must be visited - every node must be visited exactly only and only the property 'traversal in increasing order' is tested. Modify test_infix_walk() to check for all the properties above. This can be achieved by storing the nodes' keys linearly, in a nullified buffer, as we visit them and then checking the input keys against this buffer in increasing order. By checking that the element just after the last input key is 'NULL' in the output buffer, we ensure that every node is traversed exactly once. Mentored-by: Patrick Steinhardt <ps@pks.im> Mentored-by: Christian Couder <chriscool@tuxfamily.org> Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com> --- t/unit-tests/t-reftable-tree.c | 16 ++++++++++------ 1 file changed, 10 insertions(+), 6 deletions(-)