| Message ID | 20240716075641.4264-3-chandrapratap3519@gmail.com (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | t: port reftable/tree_test.c to the unit testing framework | expand |
Chandra Pratap <chandrapratap3519@gmail.com> writes: > 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. > Nit: it would be nice to mention that this commit copies it over as-is (mostly) and the upcoming commits do refactoring. This would really help reviewers. > Mentored-by: Patrick Steinhardt <ps@pks.im> > Mentored-by: Christian Couder <chriscool@tuxfamily.org> > Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com> > --- > Makefile | 2 +- > reftable/reftable-tests.h | 1 - > reftable/tree_test.c | 60 ---------------------------------- > t/helper/test-reftable.c | 1 - > t/unit-tests/t-reftable-tree.c | 56 +++++++++++++++++++++++++++++++ > 5 files changed, 57 insertions(+), 63 deletions(-) > delete mode 100644 reftable/tree_test.c > create mode 100644 t/unit-tests/t-reftable-tree.c > > diff --git a/Makefile b/Makefile > index 3eab701b10..79e86ddf53 100644 > --- a/Makefile > +++ b/Makefile > @@ -1340,6 +1340,7 @@ UNIT_TEST_PROGRAMS += t-mem-pool > UNIT_TEST_PROGRAMS += t-oidtree > UNIT_TEST_PROGRAMS += t-prio-queue > UNIT_TEST_PROGRAMS += t-reftable-basics > +UNIT_TEST_PROGRAMS += t-reftable-tree > UNIT_TEST_PROGRAMS += t-strbuf > UNIT_TEST_PROGRAMS += t-strcmp-offset > UNIT_TEST_PROGRAMS += t-strvec > @@ -2685,7 +2686,6 @@ REFTABLE_TEST_OBJS += reftable/record_test.o > REFTABLE_TEST_OBJS += reftable/readwrite_test.o > REFTABLE_TEST_OBJS += reftable/stack_test.o > REFTABLE_TEST_OBJS += reftable/test_framework.o > -REFTABLE_TEST_OBJS += reftable/tree_test.o > > TEST_OBJS := $(patsubst %$X,%.o,$(TEST_PROGRAMS)) $(patsubst %,t/helper/%,$(TEST_BUILTINS_OBJS)) > > diff --git a/reftable/reftable-tests.h b/reftable/reftable-tests.h > index 114cc3d053..d0abcc51e2 100644 > --- a/reftable/reftable-tests.h > +++ b/reftable/reftable-tests.h > @@ -16,7 +16,6 @@ int pq_test_main(int argc, const char **argv); > int record_test_main(int argc, const char **argv); > int readwrite_test_main(int argc, const char **argv); > int stack_test_main(int argc, const char **argv); > -int tree_test_main(int argc, const char **argv); > int reftable_dump_main(int argc, char *const *argv); > > #endif > diff --git a/reftable/tree_test.c b/reftable/tree_test.c > deleted file mode 100644 > index 6961a657ad..0000000000 > --- a/reftable/tree_test.c > +++ /dev/null > @@ -1,60 +0,0 @@ > -/* > -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 "system.h" > -#include "tree.h" > - > -#include "test_framework.h" > -#include "reftable-tests.h" > - > -static int test_compare(const void *a, const void *b) > -{ > - return (char *)a - (char *)b; > -} > - > -struct curry { > - void *last; > -}; > - > -static void check_increasing(void *arg, void *key) > -{ > - struct curry *c = arg; > - if (c->last) { > - EXPECT(test_compare(c->last, key) < 0); > - } > - c->last = key; > -} > - > -static void test_tree(void) > -{ > - struct tree_node *root = NULL; > - > - void *values[11] = { NULL }; > - struct tree_node *nodes[11] = { NULL }; > - int i = 1; > - struct curry c = { NULL }; > - do { > - nodes[i] = tree_search(values + i, &root, &test_compare, 1); > - i = (i * 7) % 11; > - } while (i != 1); > - > - for (i = 1; i < ARRAY_SIZE(nodes); i++) { > - EXPECT(values + i == nodes[i]->key); > - EXPECT(nodes[i] == > - tree_search(values + i, &root, &test_compare, 0)); > - } > - > - infix_walk(root, check_increasing, &c); > - tree_free(root); > -} > - > -int tree_test_main(int argc, const char *argv[]) > -{ > - RUN_TEST(test_tree); > - return 0; > -} > diff --git a/t/helper/test-reftable.c b/t/helper/test-reftable.c > index 9160bc5da6..245b674a3c 100644 > --- a/t/helper/test-reftable.c > +++ b/t/helper/test-reftable.c > @@ -7,7 +7,6 @@ int cmd__reftable(int argc, const char **argv) > /* test from simple to complex. */ > record_test_main(argc, argv); > block_test_main(argc, argv); > - tree_test_main(argc, argv); > pq_test_main(argc, argv); > readwrite_test_main(argc, argv); > merged_test_main(argc, argv); > 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; > +} > + > +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 }; > + 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; > + } 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
Chandra Pratap <chandrapratap3519@gmail.com> writes: > 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] > 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. > +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? > + 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? > + } 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
On Wed, 17 Jul 2024 at 17:19, Karthik Nayak <karthik.188@gmail.com> wrote: > > Chandra Pratap <chandrapratap3519@gmail.com> writes: > > > 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. > > > > Nit: it would be nice to mention that this commit copies it over as-is > (mostly) and the upcoming commits do refactoring. This would really help > reviewers. I do mention that in the patch cover letter, specifically this paragraph: > The first patch in the series is preparatory cleanup, the second patch > moves the test to the unit testing framework, and the rest of the patches > improve upon the ported test. Would it be better if I transport that here? ----[snip]----
On Wed, 17 Jul 2024 at 18:09, Karthik Nayak <karthik.188@gmail.com> wrote: > > Chandra Pratap <chandrapratap3519@gmail.com> writes: > > > 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] > > > 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. > > +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. > > + 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. > > + } 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
On 24/07/17 08:00PM, Chandra Pratap wrote: > On Wed, 17 Jul 2024 at 18:09, Karthik Nayak <karthik.188@gmail.com> wrote: > > > > Chandra Pratap <chandrapratap3519@gmail.com> 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. > > > + 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. 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. -Justin
On Thu, 18 Jul 2024 at 03:45, Justin Tobler <jltobler@gmail.com> wrote: > > On 24/07/17 08:00PM, Chandra Pratap wrote: > > On Wed, 17 Jul 2024 at 18:09, Karthik Nayak <karthik.188@gmail.com> wrote: > > > > > > Chandra Pratap <chandrapratap3519@gmail.com> 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.
Chandra Pratap <chandrapratap3519@gmail.com> writes: > On Wed, 17 Jul 2024 at 17:19, Karthik Nayak <karthik.188@gmail.com> wrote: >> >> Chandra Pratap <chandrapratap3519@gmail.com> writes: >> >> > 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. >> > >> >> Nit: it would be nice to mention that this commit copies it over as-is >> (mostly) and the upcoming commits do refactoring. This would really help >> reviewers. > > I do mention that in the patch cover letter, specifically this paragraph: > >> The first patch in the series is preparatory cleanup, the second patch >> moves the test to the unit testing framework, and the rest of the patches >> improve upon the ported test. > > Would it be better if I transport that here? > > ----[snip]---- I think that would be nice!
Chandra Pratap <chandrapratap3519@gmail.com> writes: > On Thu, 18 Jul 2024 at 03:45, Justin Tobler <jltobler@gmail.com> wrote: >> >> On 24/07/17 08:00PM, Chandra Pratap wrote: >> > On Wed, 17 Jul 2024 at 18:09, Karthik Nayak <karthik.188@gmail.com> wrote: >> > > >> > > Chandra Pratap <chandrapratap3519@gmail.com> 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. 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?
On Thu, 18 Jul 2024 at 13:40, Karthik Nayak <karthik.188@gmail.com> wrote: > > Chandra Pratap <chandrapratap3519@gmail.com> writes: > > > On Thu, 18 Jul 2024 at 03:45, Justin Tobler <jltobler@gmail.com> wrote: > >> > >> On 24/07/17 08:00PM, Chandra Pratap wrote: > >> > On Wed, 17 Jul 2024 at 18:09, Karthik Nayak <karthik.188@gmail.com> wrote: > >> > > > >> > > Chandra Pratap <chandrapratap3519@gmail.com> 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. > > 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'
On 24/07/18 01:10AM, Karthik Nayak wrote: > Chandra Pratap <chandrapratap3519@gmail.com> writes: > > > On Thu, 18 Jul 2024 at 03:45, Justin Tobler <jltobler@gmail.com> wrote: > >> > >> On 24/07/17 08:00PM, Chandra Pratap wrote: > > >> 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. > > 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? Personally, I quite like this approach. It's more up front with what its doing and ultimately accoplishes the same thing.
diff --git a/Makefile b/Makefile index 3eab701b10..79e86ddf53 100644 --- a/Makefile +++ b/Makefile @@ -1340,6 +1340,7 @@ UNIT_TEST_PROGRAMS += t-mem-pool UNIT_TEST_PROGRAMS += t-oidtree UNIT_TEST_PROGRAMS += t-prio-queue UNIT_TEST_PROGRAMS += t-reftable-basics +UNIT_TEST_PROGRAMS += t-reftable-tree UNIT_TEST_PROGRAMS += t-strbuf UNIT_TEST_PROGRAMS += t-strcmp-offset UNIT_TEST_PROGRAMS += t-strvec @@ -2685,7 +2686,6 @@ REFTABLE_TEST_OBJS += reftable/record_test.o REFTABLE_TEST_OBJS += reftable/readwrite_test.o REFTABLE_TEST_OBJS += reftable/stack_test.o REFTABLE_TEST_OBJS += reftable/test_framework.o -REFTABLE_TEST_OBJS += reftable/tree_test.o TEST_OBJS := $(patsubst %$X,%.o,$(TEST_PROGRAMS)) $(patsubst %,t/helper/%,$(TEST_BUILTINS_OBJS)) diff --git a/reftable/reftable-tests.h b/reftable/reftable-tests.h index 114cc3d053..d0abcc51e2 100644 --- a/reftable/reftable-tests.h +++ b/reftable/reftable-tests.h @@ -16,7 +16,6 @@ int pq_test_main(int argc, const char **argv); int record_test_main(int argc, const char **argv); int readwrite_test_main(int argc, const char **argv); int stack_test_main(int argc, const char **argv); -int tree_test_main(int argc, const char **argv); int reftable_dump_main(int argc, char *const *argv); #endif diff --git a/reftable/tree_test.c b/reftable/tree_test.c deleted file mode 100644 index 6961a657ad..0000000000 --- a/reftable/tree_test.c +++ /dev/null @@ -1,60 +0,0 @@ -/* -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 "system.h" -#include "tree.h" - -#include "test_framework.h" -#include "reftable-tests.h" - -static int test_compare(const void *a, const void *b) -{ - return (char *)a - (char *)b; -} - -struct curry { - void *last; -}; - -static void check_increasing(void *arg, void *key) -{ - struct curry *c = arg; - if (c->last) { - EXPECT(test_compare(c->last, key) < 0); - } - c->last = key; -} - -static void test_tree(void) -{ - struct tree_node *root = NULL; - - void *values[11] = { NULL }; - struct tree_node *nodes[11] = { NULL }; - int i = 1; - struct curry c = { NULL }; - do { - nodes[i] = tree_search(values + i, &root, &test_compare, 1); - i = (i * 7) % 11; - } while (i != 1); - - for (i = 1; i < ARRAY_SIZE(nodes); i++) { - EXPECT(values + i == nodes[i]->key); - EXPECT(nodes[i] == - tree_search(values + i, &root, &test_compare, 0)); - } - - infix_walk(root, check_increasing, &c); - tree_free(root); -} - -int tree_test_main(int argc, const char *argv[]) -{ - RUN_TEST(test_tree); - return 0; -} diff --git a/t/helper/test-reftable.c b/t/helper/test-reftable.c index 9160bc5da6..245b674a3c 100644 --- a/t/helper/test-reftable.c +++ b/t/helper/test-reftable.c @@ -7,7 +7,6 @@ int cmd__reftable(int argc, const char **argv) /* test from simple to complex. */ record_test_main(argc, argv); block_test_main(argc, argv); - tree_test_main(argc, argv); pq_test_main(argc, argv); readwrite_test_main(argc, argv); merged_test_main(argc, argv); 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; +} + +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 }; + 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; + } 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(); +}
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. Mentored-by: Patrick Steinhardt <ps@pks.im> Mentored-by: Christian Couder <chriscool@tuxfamily.org> Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com> --- Makefile | 2 +- reftable/reftable-tests.h | 1 - reftable/tree_test.c | 60 ---------------------------------- t/helper/test-reftable.c | 1 - t/unit-tests/t-reftable-tree.c | 56 +++++++++++++++++++++++++++++++ 5 files changed, 57 insertions(+), 63 deletions(-) delete mode 100644 reftable/tree_test.c create mode 100644 t/unit-tests/t-reftable-tree.c