On Thu, 18 Jul 2024 at 13:40, Karthik Nayak [off-list ref] wrote:

Chandra Pratap [off-list ref] writes:

quoted

On Thu, 18 Jul 2024 at 03:45, Justin Tobler [off-list ref] wrote:

quoted

On 24/07/17 08:00PM, Chandra Pratap wrote:

quoted

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

quoted

Chandra Pratap [off-list ref] writes:

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.

The point of `values` is to provide a set of values of type `void **` to
be inserted in the tree. As far as I can tell, there is no reason for
`values` to be initialized to begin with and is a bit misleading. Might
be reasonable to remove its initialization here.

The thing is, the values[] array being 0-initialized makes debugging
a lot easier in the case of a test failure, so I'm not very sure about
getting rid of the initialization here.

quoted

quoted

quoted

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.

The `i = (i * 7) % 11;` is used to deterministically generate numbers
1-10 in a psuedo-random fashion. These numbers are used as memory
offsets to be inserted into the tree. I suspect the psuedo-randomness is
useful keys should be ordered when inserted into the tree and that is
later validated as part of the in-order traversal that is performed.

That's right, the randomness of the insertion order is helpful in validating
that the tree-functions 'tree_search()' and 'infix_walk()' work according
to their defined behaviour.

quoted

While rather compact, I find the test setup here to rather difficult to
parse. It might be a good idea to either provide comments explaining
this test setup or consider refactoring it. Honestly, I'd personally
perfer the tree setup be done more explicitly as I think it would make
understanding the test much easier.

This probably ties in with the comments by Patrick on the previous iteration
of this patch, that using 'tree_search()' to insert tree nodes leads to
confusion. Solving that would require efforts outside the scope of this
patch series though, so I'm more inclined towards providing comments
and other ways of simplifying this subroutine.

Agreed that refactoring `tree_search()` probably is out of scope here.
But rewriting the test is definitely something we can do.

Perhaps:

static void t_tree(void)
{
        struct tree_node *root = NULL;
        int values[11] = {7, 5, 2, 3, 10, 4, 6, 9, 8, 1};
        struct tree_node *nodes[11] = { 0 };
        size_t i = 1;
        struct curry c = { 0 };

    // Insert values to the tree by passing '1' as the last argument.
    for (i = 1; i < ARRAY_SIZE(values); i++) {
                nodes[i] = tree_search(&values[i], &root, &t_compare, 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);
}

Wouldn't this have the same effect while making it much easier to read?

I agree that the change 'values + i -> &values[i]' is a net positive, I had this
change in mind as well. This comment on the other hand,

    // Insert values to the tree by passing '1' as the last argument.

has already been stated in the commit message of the 3rd patch
as was suggested by Patrick earlier:

'Note that the last parameter in the tree_search() function is
'int insert' which when set, inserts the key if it is not found
in the tree. Otherwise, the function returns NULL for such cases.'

So I was thinking of adding something along the lines of:
'// pseudo-randomly insert pointers to elements between values[1]
and values[10] in the tree'