On Thu, 18 Jul 2024 at 03:45, Justin Tobler <jltobler@xxxxxxxxx> wrote:
>
> On 24/07/17 08:00PM, Chandra Pratap wrote:
> > On Wed, 17 Jul 2024 at 18:09, Karthik Nayak <karthik.188@xxxxxxxxx> wrote:
> > >
> > > Chandra Pratap <chandrapratap3519@xxxxxxxxx> writes:
> > >
> > > > +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.
> > > > + 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.
> 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.
