On Mon, 10 Jun 2024 at 19:19, Patrick Steinhardt [off-list ref] wrote:

On Mon, Jun 10, 2024 at 06:31:30PM +0530, Chandra Pratap wrote:

quoted

@@ -44,13 +44,29 @@ static void test_tree(void)
              check_pointer_eq(nodes[i], tree_search(values + i, &root, &test_compare, 0));
      }

-     infix_walk(root, check_increasing, &c);
+     tree_free(root);
+}
+
+static void test_infix_walk(void)
+{
+     struct tree_node *root = NULL;
+     void *values[13] = { 0 };

Is there a reason why we have 13 values here while we had 11 values in
the test this was split out from?

I did that to introduce some variety between the test cases, but now that you
mention it, this change doesn't go well with the objective of this patch.

quoted

+     struct curry c = { 0 };
+     size_t i = 1;
+
+     do {
+             tree_search(values + i, &root, &test_compare, 1);
+             i = (i * 5) % 13;
+     } while (i != 1);

It's completely non-obvious that `tree_search()` ends up _inserting_
nodes into the tree when the entry we're searching for wasn't found (and
if the last parameter is `1`. I feel like this interface could really
use a complete makeover and split up its concerns. In any case, that
does not need to happen as part of this patch seriesr

I don't really mind it because all tree operations are only used in
reftable/writer.c and only in a couple of places, so it would make sense
for the original authors to focus their efforts on other parts of the codebase.
Still, I do agree that the readability takes a hit 'cause of that.

What I think would help though is if the commit message itself mentioned
this unorthodox way of inserting values into the tree.

Sure thing.

quoted

+     infix_walk(root, &check_increasing, &c);

Not a fault of this commit, but this test certainly isn't great. It
would succeed even if `infix_walk()` didn't do anything as we do not
verify at all whether all nodes have been traversed (and traversed once,
exactly).

I'll try to modify the test to check for these properties of an infix
walk as well.