merged_iter_pqueue_top() as defined by reftable/pq.{c, h} returns the element at the top of a priority-queue's heap without removing it. Since there are no tests for this function in the existing setup, add tests for the same. Mentored-by: Patrick Steinhardt <ps@xxxxxx> Mentored-by: Christian Couder <chriscool@xxxxxxxxxxxxx> Signed-off-by: Chandra Pratap <chandrapratap3519@xxxxxxxxx> --- t/unit-tests/t-reftable-pq.c | 49 ++++++++++++++++++++++++++++++++++++ 1 file changed, 49 insertions(+) diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c index 70ff89507d..039bd0f1f9 100644 --- a/t/unit-tests/t-reftable-pq.c +++ b/t/unit-tests/t-reftable-pq.c @@ -18,6 +18,11 @@ static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq) } } +static int pq_entry_equal(struct pq_entry *a, struct pq_entry *b) +{ + return !reftable_record_cmp(a->rec, b->rec) && (a->index == b->index); +} + static void t_pq_record(void) { struct merged_iter_pqueue pq = { 0 }; @@ -42,9 +47,11 @@ static void t_pq_record(void) } while (i != 1); while (!merged_iter_pqueue_is_empty(pq)) { + struct pq_entry top = merged_iter_pqueue_top(pq); struct pq_entry e = merged_iter_pqueue_remove(&pq); merged_iter_pqueue_check(&pq); + check(pq_entry_equal(&top, &e)); check(reftable_record_type(e.rec) == BLOCK_TYPE_REF); if (last) check_int(strcmp(last, e.rec->u.ref.refname), <, 0); @@ -81,9 +88,11 @@ static void t_pq_index(void) } while (i != 1); for (i = N - 1; i > 0; i--) { + struct pq_entry top = merged_iter_pqueue_top(pq); struct pq_entry e = merged_iter_pqueue_remove(&pq); merged_iter_pqueue_check(&pq); + check(pq_entry_equal(&top, &e)); check(reftable_record_type(e.rec) == BLOCK_TYPE_REF); check_int(e.index, ==, i); if (last) @@ -94,10 +103,50 @@ static void t_pq_index(void) merged_iter_pqueue_release(&pq); } +static void t_merged_iter_pqueue_top(void) +{ + struct merged_iter_pqueue pq = { 0 }; + struct reftable_record recs[13]; + 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 = (char *) "refs/heads/master"; + } + + i = 1; + do { + struct pq_entry e = { + .rec = &recs[i], + .index = i, + }; + + merged_iter_pqueue_add(&pq, &e); + merged_iter_pqueue_check(&pq); + i = (i * 7) % N; + } while (i != 1); + + for (i = N - 1; i > 0; i--) { + struct pq_entry top = merged_iter_pqueue_top(pq); + struct pq_entry e = merged_iter_pqueue_remove(&pq); + + merged_iter_pqueue_check(&pq); + check(pq_entry_equal(&top, &e)); + check(reftable_record_equal(top.rec, &recs[i], GIT_SHA1_RAWSZ)); + for (size_t j = 0; i < pq.len; j++) { + check(pq_less(&top, &pq.heap[j])); + check_int(top.index, >, j); + } + } + + merged_iter_pqueue_release(&pq); +} + int cmd_main(int argc, const char *argv[]) { TEST(t_pq_record(), "pq works with record-based comparison"); TEST(t_pq_index(), "pq works with index-based comparison"); + TEST(t_merged_iter_pqueue_top(), "merged_iter_pqueue_top works"); return test_done(); } -- 2.45.GIT