| Message ID | 20240723143032.4261-7-chandrapratap3519@gmail.com (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | t: port reftable/pq_test.c to the unit testing framework | expand |
On Tue, Jul 23, 2024 at 07:47:16PM +0530, Chandra Pratap wrote: > diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c > index 9230dd9b9e..23c3f6888b 100644 > --- a/t/unit-tests/t-reftable-pq.c > +++ b/t/unit-tests/t-reftable-pq.c > @@ -18,7 +18,7 @@ static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq) > } > } > > -static void t_pq(void) > +static void t_pq_record(void) > { > struct merged_iter_pqueue pq = { 0 }; > struct reftable_record recs[54]; > @@ -59,9 +59,48 @@ static void t_pq(void) > merged_iter_pqueue_release(&pq); > } > > +static void t_pq_index(void) > +{ > + struct merged_iter_pqueue pq = { 0 }; > + struct reftable_record recs[14]; > + char *last = NULL; > + size_t N = ARRAY_SIZE(recs), i; > + > + for (i = 0; i < N; i++) { > + reftable_record_init(&recs[i], BLOCK_TYPE_REF); > + recs[i].u.ref.refname = xstrdup("refs/heads/master"); > + } > + > + for (i = 0; i < N; i++) { > + struct pq_entry e = { > + .rec = &recs[i], > + .index = i, > + }; > + > + merged_iter_pqueue_add(&pq, &e); > + merged_iter_pqueue_check(&pq); > + } One of those reasons that we use the modulo-loops in the other tests is so that the order in which entries are added is mixed. Here we add them in priority order already, so that makes the test less interesting. We might thus want to do the same here and scramble the order a bit. Patrick
Patrick Steinhardt <ps@pks.im> writes: > One of those reasons that we use the modulo-loops in the other tests is > so that the order in which entries are added is mixed. Here we add them > in priority order already, so that makes the test less interesting. We > might thus want to do the same here and scramble the order a bit. Wouldn't modulo-loops mean the total number of elements must be prime with the skip count, or something, which in turn means that it is harder to test certain corner cases of the underlying data structure (e.g. "what if the length is exactly a power of two? A power of two plus one? A power of two minus one?" etc.) It certainly is much better than just inserting in the priority order (or in the reverse priority order). Thanks.
On Wed, Jul 24, 2024 at 09:15:31AM -0700, Junio C Hamano wrote: > Patrick Steinhardt <ps@pks.im> writes: > > > One of those reasons that we use the modulo-loops in the other tests is > > so that the order in which entries are added is mixed. Here we add them > > in priority order already, so that makes the test less interesting. We > > might thus want to do the same here and scramble the order a bit. > > Wouldn't modulo-loops mean the total number of elements must be > prime with the skip count, or something, which in turn means that it > is harder to test certain corner cases of the underlying data > structure (e.g. "what if the length is exactly a power of two? A > power of two plus one? A power of two minus one?" etc.) > > It certainly is much better than just inserting in the priority > order (or in the reverse priority order). Yeah. I am not a huge fan of those modulo-loop as they hide what the actual test data is myself, but they are already being used in those tests anyway, and that's why I proposed them. The better option, in my opinion, is to just make the test data explicit by for example looping through an array of input data and inserting it one by one. Patrick
diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c index 9230dd9b9e..23c3f6888b 100644 --- a/t/unit-tests/t-reftable-pq.c +++ b/t/unit-tests/t-reftable-pq.c @@ -18,7 +18,7 @@ static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq) } } -static void t_pq(void) +static void t_pq_record(void) { struct merged_iter_pqueue pq = { 0 }; struct reftable_record recs[54]; @@ -59,9 +59,48 @@ static void t_pq(void) merged_iter_pqueue_release(&pq); } +static void t_pq_index(void) +{ + struct merged_iter_pqueue pq = { 0 }; + struct reftable_record recs[14]; + char *last = NULL; + size_t N = ARRAY_SIZE(recs), i; + + for (i = 0; i < N; i++) { + reftable_record_init(&recs[i], BLOCK_TYPE_REF); + recs[i].u.ref.refname = xstrdup("refs/heads/master"); + } + + for (i = 0; i < N; i++) { + struct pq_entry e = { + .rec = &recs[i], + .index = i, + }; + + merged_iter_pqueue_add(&pq, &e); + merged_iter_pqueue_check(&pq); + } + + for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) { + struct pq_entry e = merged_iter_pqueue_remove(&pq); + merged_iter_pqueue_check(&pq); + + check(reftable_record_type(e.rec) == BLOCK_TYPE_REF); + check_int(e.index, ==, i); + if (last) + check_str(last, e.rec->u.ref.refname); + last = e.rec->u.ref.refname; + } + + for (i = 0; i < N; i++) + reftable_record_release(&recs[i]); + merged_iter_pqueue_release(&pq); +} + int cmd_main(int argc, const char *argv[]) { - TEST(t_pq(), "pq works"); + TEST(t_pq_record(), "pq works with record-based comparison"); + TEST(t_pq_index(), "pq works with index-based comparison"); return test_done(); }
When comparing two entries, the priority queue as defined by reftable/pq.{c, h} first compares the entries on the basis of their ref-record's keys. If the keys turn out to be equal, the comparison is then made on the basis of their update indices (which are never equal). In the current testing setup, only the case for comparison on the basis of ref-record's keys is exercised. Add a test for index-based comparison as well. Rename the existing test to reflect its nature of only testing record-based comparison. Mentored-by: Patrick Steinhardt <ps@pks.im> Mentored-by: Christian Couder <chriscool@tuxfamily.org> Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com> --- t/unit-tests/t-reftable-pq.c | 43 ++++++++++++++++++++++++++++++++++-- 1 file changed, 41 insertions(+), 2 deletions(-)