On Wed, 17 Jul 2024 at 18:09, Karthik Nayak [off-list ref] wrote:

Chandra Pratap [off-list ref] writes:

quoted

reftable/tree_test.c exercises the functions defined in
reftable/tree.{c, h}. Migrate reftable/tree_test.c to the unit
testing framework. Migration involves refactoring the tests to use
the unit testing framework instead of reftable's test framework and
renaming the tests to align with unit-tests' standards.

On second thought, it's easier for me to review here for the existing
state of the code. So let me do that..

[snip]

quoted

diff --git a/t/unit-tests/t-reftable-tree.c b/t/unit-tests/t-reftable-tree.c
new file mode 100644
index 0000000000..5df814d983
--- /dev/null
+++ b/t/unit-tests/t-reftable-tree.c

@@ -0,0 +1,56 @@
+/*
+Copyright 2020 Google LLC
+
+Use of this source code is governed by a BSD-style
+license that can be found in the LICENSE file or at
+https://developers.google.com/open-source/licenses/bsd
+*/
+
+#include "test-lib.h"
+#include "reftable/tree.h"
+
+static int t_compare(const void *a, const void *b)
+{
+     return (char *)a - (char *)b;
+}
+

So this is the comparison code, and we're expecting the values to be a
character. Okay.

We're actually expecting the values 'a' and 'b' to be of the type (char *),
which is a pointer to a character, and thus we perform the comparison on
the basis of pointer arithmetic.

quoted

+struct curry {
+     void *last;
+};
+
+static void check_increasing(void *arg, void *key)
+{
+     struct curry *c = arg;
+     if (c->last)
+             check_int(t_compare(c->last, key), <, 0);
+     c->last = key;
+}
+
+static void t_tree(void)
+{
+     struct tree_node *root = NULL;
+     void *values[11] = { 0 };

Although we were comparing 'char' above, here we have a 'void *' array.
Why?

The array is passed as a parameter to the 'tree_search()' function which
requires a void * parameter (i.e. a generic pointer). In the comparison
function (also passed as a parameter), we cast it to our expected type
(a character pointer) and then perform the required comparison.

quoted

+     struct tree_node *nodes[11] = { 0 };
+     size_t i = 1;
+     struct curry c = { 0 };
+
+     do {
+             nodes[i] = tree_search(values + i, &root, &t_compare, 1);
+             i = (i * 7) % 11;

It gets weirder, we calculate 'i' as {7, 5, 2, 3, 10, 4, 6, 9, 8, 1}. We
use that to index 'values', but values is '0' initialized, so we always
send '0' to tree_search? Doesn't that make this whole thing a moot? Or
did I miss something?

We don't use 'i' to index 'values[]', we use it to calculate the next pointer
address to be passed to the 'tree_search()' function (the pointer that is 'i'
ahead of the pointer 'values'), which isn't 0.

quoted

+     } while (i != 1);
+
+     for (i = 1; i < ARRAY_SIZE(nodes); i++) {
+             check_pointer_eq(values + i, nodes[i]->key);
+             check_pointer_eq(nodes[i], tree_search(values + i, &root, &t_compare, 0));
+     }
+
+     infix_walk(root, check_increasing, &c);
+     tree_free(root);
+}
+
+int cmd_main(int argc, const char *argv[])
+{
+     TEST(t_tree(), "tree_search and infix_walk work");
+
+     return test_done();
+}
--
2.45.GIT