t: port reftable/pq_test.c to the unit testing
cover t: port reftable/pq_test.c to the unit testing
In the recent codebase update (commit 8bf6fbd, 2023-12-09), a new unit testing framework written entirely in C was introduced to the Git project aimed at simplifying testing and reducing test run times. Currently, tests for the reftable refs-backend are performed by a custom testing framework defined by reftable/test_framework.{c, h}. Port reftable/pq_test.c to the unit testing framework and improve upon the ported test.
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.
CI/PR: https://github.com/gitgitgadget/git/pull/1745
Chandra Pratap (6):
reftable: clean up reftable/pq.c
t: move reftable/pq_test.c to the unit testing framework
t-reftable-pq: make merged_iter_pqueue_check() static
t-reftable-pq: make merged_iter_pqueue_check() callable
t-reftable-pq: add test for index based comparison
t-reftable-pq: add tests for merged_iter_pqueue_top()
PATCH 1/6 reftable: clean up reftable/pq.c
According to Documentation/CodingGuidelines, control-flow statements with a single line as their body must omit curly braces. Make reftable/pq.c conform to this guideline. Besides that, remove unnecessary newlines and variable assignment.
--- reftable/pq.c | 18 ++++-------------- 1 file changed, 4 insertions(+), 14 deletions(-)
reftable/pq.c +4 -14
@@ -27,22 +27,16 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq) pq->heap[0 ] = pq->heap[pq->len -1 ]; pq->len--; - i =0 ;while (i < pq->len) {int min = i;int j =2 * i +1 ;int k =2 * i +2 ; -if (j < pq->len &&pq_less (&pq->heap[j], &pq->heap[i])) { +if (j < pq->len &&pq_less (&pq->heap[j], &pq->heap[i])) min = j; - } -if (k < pq->len &&pq_less (&pq->heap[k], &pq->heap[min])) { +if (k < pq->len &&pq_less (&pq->heap[k], &pq->heap[min])) min = k; - } - -if (min == i) { +if (min == i)break ; - } -SWAP (pq->heap[i], pq->heap[min]); i = min; }
@@ -53,19 +47,15 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)void merged_iter_pqueue_add (struct merged_iter_pqueue *pq,const struct pq_entry *e) {int i =0 ; -REFTABLE_ALLOC_GROW (pq->heap, pq->len +1 , pq->cap); pq->heap[pq->len++] = *e; i = pq->len -1 ;while (i >0 ) {int j = (i -1 ) /2 ; -if (pq_less (&pq->heap[j], &pq->heap[i])) { +if (pq_less (&pq->heap[j], &pq->heap[i]))break ; - } -SWAP (pq->heap[j], pq->heap[i]); - i = j; } }
Signature · 1 line
2.45.2.404.g9eaef5822c
Re: [GSoC][PATCH 1/6] reftable: clean up reftable/pq.c
Quoted 5 lines · Chandra Pratap
According to
Documentation/CodingGuidelines, control-flow statements with a single line as their body must omit curly braces. Makereftable/pq.cconform to this guideline. Besides that, remove unnecessary newlines and variable assignment.
A commit subject like "reftable/pq: remove unnecessary curly braces" might be a bit more specific.
Re: [GSoC][PATCH 1/6] reftable: clean up reftable/pq.c
Quoted 11 lines · Christian Couder
Quoted 5 lines · Chandra Pratap
According to
Documentation/CodingGuidelines, control-flow statements with a single line as their body must omit curly braces. Makereftable/pq.cconform to this guideline. Besides that, remove unnecessary newlines and variable assignment.A commit subject like "reftable/pq: remove unnecessary curly braces" might be a bit more specific.
There are other forms of cleanup also being performed, like removing unnecessary newlines and variable assignment. Would it still be okay to sweep it all under 'removing unnecessary braces'?
Re: [GSoC][PATCH 1/6] reftable: clean up reftable/pq.c
Quoted 12 lines · Chandra Pratap
Quoted 9 lines · Christian Couder
Quoted 5 lines · Chandra Pratap
According to
Documentation/CodingGuidelines, control-flow statements with a single line as their body must omit curly braces. Makereftable/pq.cconform to this guideline. Besides that, remove unnecessary newlines and variable assignment.
Quoted 6 lines
Quoted 2 lines
A commit subject like "reftable/pq: remove unnecessary curly braces" might be a bit more specific.
There are other forms of cleanup also being performed, like removing unnecessary newlines and variable assignment. Would it still be okay to sweep it all under 'removing unnecessary braces'?
I think the removal of unnecessary braces is the main change and other changes are made while at it, so I think it's Ok.
PATCH 2/6 t: move reftable/pq_test.c to the unit testing framework
In reply to Chandra Pratapreftable/pq_test.c exercises a priority queue defined by reftable/pq.{c, h}. Migrate reftable/pq_test.c to the unit testing framework. Migration involves refactoring the tests to use the unit testing framework instead of reftable's test framework.
--- Makefile | 2 +- t/helper/test-reftable.c | 1 - .../pq_test.c => t/unit-tests/t-reftable-pq.c | 35 ++++++++----------- 3 files changed, 15 insertions(+), 23 deletions(-) rename reftable/pq_test.c => t/unit-tests/t-reftable-pq.c (64%)
Makefile +1 -1
@@ -1336,6 +1336,7 @@ THIRD_PARTY_SOURCES += sha1dc/% UNIT_TEST_PROGRAMS += t-ctype UNIT_TEST_PROGRAMS += t-mem-pool UNIT_TEST_PROGRAMS += t-prio-queue +UNIT_TEST_PROGRAMS += t-reftable-pq UNIT_TEST_PROGRAMS += t-strbuf UNIT_TEST_PROGRAMS += t-strcmp-offset UNIT_TEST_PROGRAMS += t-trailer
@@ -2675,7 +2676,6 @@ REFTABLE_TEST_OBJS += reftable/basics_test.o REFTABLE_TEST_OBJS += reftable/block_test.o REFTABLE_TEST_OBJS += reftable/dump.o REFTABLE_TEST_OBJS += reftable/merged_test.o -REFTABLE_TEST_OBJS += reftable/pq_test.o REFTABLE_TEST_OBJS += reftable/record_test.o REFTABLE_TEST_OBJS += reftable/readwrite_test.o REFTABLE_TEST_OBJS += reftable/stack_test.o
t/helper/test-reftable.c +0 -1
@@ -9,7 +9,6 @@ int cmd__reftable(int argc, const char **argv)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);stack_test_main (argc, argv);
t/unit-tests/t-reftable-pq.c renamed from reftable/pq_test.c +14 -21
@@ -6,35 +6,28 @@ license that can be found in the LICENSE file or athttps://developers.google.com/open-source/licenses/bsd */ -#include "system.h" - -#include "basics.h" -#include "constants.h" -#include "pq.h" -#include "record.h" -#include "reftable-tests.h" -#include "test_framework.h" +#include "test-lib.h" +#include "reftable/constants.h" +#include "reftable/pq.h" void merged_iter_pqueue_check (struct merged_iter_pqueue pq) { -int i; -for (i =1 ; i < pq.len; i++) { +for (int i =1 ; i < pq.len; i++) {int parent = (i -1 ) /2 ; - -EXPECT (pq_less (&pq.heap[parent], &pq.heap[i])); +check (pq_less (&pq.heap[parent], &pq.heap[i])); } }static void test_pq (void ) { -struct merged_iter_pqueue pq = {NULL }; +struct merged_iter_pqueue pq = {0 };struct reftable_record recs[54 ]; -int N =ARRAY_SIZE (recs) -1 , i; +size_t N =ARRAY_SIZE (recs) -1 , i;char *last =NULL ;for (i =0 ; i <N ; i++) {struct strbuf refname =STRBUF_INIT ; -strbuf_addf (&refname,"%02d" , i); +strbuf_addf (&refname,"%02ld" , (long )i);reftable_record_init (&recs[i],BLOCK_TYPE_REF ); recs[i].u.ref.refname =strbuf_detach (&refname,NULL );
@@ -48,7 +41,6 @@ static void test_pq(void)merged_iter_pqueue_add (&pq, &e);merged_iter_pqueue_check (pq); - i = (i *7 ) %N ; }while (i !=1 );
@@ -56,9 +48,9 @@ static void test_pq(void)struct pq_entry e =merged_iter_pqueue_remove (&pq);merged_iter_pqueue_check (pq); -EXPECT (reftable_record_type (e.rec) ==BLOCK_TYPE_REF ); +check (reftable_record_type (e.rec) ==BLOCK_TYPE_REF );if (last) -EXPECT (strcmp (last, e.rec->u.ref.refname) <0 ); + check_int(strcmp(last, e.rec->u.ref.refname), <, 0); last = e.rec->u.ref.refname; }
@@ -67,8 +59,9 @@ static void test_pq(void)merged_iter_pqueue_release (&pq); } -int pq_test_main (int argc,const char *argv[]) +int cmd_main (int argc,const char *argv[]) { -RUN_TEST (test_pq); -return 0 ; +TEST (test_pq (),"pq works" ); + +return test_done (); }
Signature · 1 line
2.45.2.404.g9eaef5822c
Re: [GSoC][PATCH 2/6] t: move reftable/pq_test.c to the unit testing framework
Quoted 66 lines · Chandra Pratap
reftable/pq_test.cexercises a priority queue defined by reftable/pq.{c, h}. Migratereftable/pq_test.cto the unit testing framework. Migration involves refactoring the tests to use the unit testing framework instead of reftable's test framework.Mentored-by Patrick Steinhardt <[email protected]>Mentored-by Christian Couder <[email protected]>Signed-off-by Chandra Pratap <[email protected]>--- Makefile | 2 +- t/helper/test-reftable.c | 1 - .../pq_test.c => t/unit-tests/t-reftable-pq.c | 35 ++++++++----------- 3 files changed, 15 insertions(+), 23 deletions(-) rename reftable/pq_test.c => t/unit-tests/t-reftable-pq.c (64%)Makefile +1
-1@@ -1336,6 +1336,7 @@ THIRD_PARTY_SOURCES += sha1dc/% UNIT_TEST_PROGRAMS += t-ctype UNIT_TEST_PROGRAMS += t-mem-pool UNIT_TEST_PROGRAMS += t-prio-queue +UNIT_TEST_PROGRAMS += t-reftable-pq UNIT_TEST_PROGRAMS += t-strbuf UNIT_TEST_PROGRAMS += t-strcmp-offset UNIT_TEST_PROGRAMS += t-trailer@@ -2675,7 +2676,6 @@ REFTABLE_TEST_OBJS += reftable/basics_test.o REFTABLE_TEST_OBJS += reftable/block_test.o REFTABLE_TEST_OBJS += reftable/dump.o REFTABLE_TEST_OBJS += reftable/merged_test.o -REFTABLE_TEST_OBJS += reftable/pq_test.o REFTABLE_TEST_OBJS += reftable/record_test.o REFTABLE_TEST_OBJS += reftable/readwrite_test.o REFTABLE_TEST_OBJS += reftable/stack_test.ot/helper/test-reftable.c +0
-1@@ -9,7 +9,6 @@ int cmd__reftable(int argc, const char **argv)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);stack_test_main (argc, argv);t/unit-tests/t-reftable-pq.c renamed from reftable/pq_test.c +0
-7@@ -6,35 +6,28 @@ license that can be found in the LICENSE file or athttps://developers.google.com/open-source/licenses/bsd */ -#include "system.h" - -#include "basics.h" -#include "constants.h" -#include "pq.h" -#include "record.h" -#include "reftable-tests.h"
t/unit-tests/t-reftable-pq.c license that can be found in the LICENSE file or at · line 15
Quoted 10 lines
t/unit-tests/t-reftable-pq.c renamed from reftable/pq_test.c +4
-3-#include "test_framework.h" +#include "test-lib.h" +#include "reftable/constants.h" +#include "reftable/pq.h" void merged_iter_pqueue_check (struct merged_iter_pqueue pq) { -int i; -for (i =1 ; i < pq.len; i++) { +for (int i =1 ; i < pq.len; i++) {
If we're changing this already, then we can also convert it to size_t i while at it to match the type of pq.len.
Quoted 10 lines
t/unit-tests/t-reftable-pq.c renamed from reftable/pq_test.c +1
-3int parent = (i -1 ) /2 ; - -EXPECT (pq_less (&pq.heap[parent], &pq.heap[i])); +check (pq_less (&pq.heap[parent], &pq.heap[i])); } }static void test_pq (void ) { -struct merged_iter_pqueue pq = {NULL };
t/unit-tests/t-reftable-pq.c license that can be found in the LICENSE file or at · line 30
Quoted 10 lines
t/unit-tests/t-reftable-pq.c renamed from reftable/pq_test.c +3
-2+struct merged_iter_pqueue pq = {0 };struct reftable_record recs[54 ]; -int N =ARRAY_SIZE (recs) -1 , i; +size_t N =ARRAY_SIZE (recs) -1 , i;char *last =NULL ;for (i =0 ; i <N ; i++) {struct strbuf refname =STRBUF_INIT ; -strbuf_addf (&refname,"%02d" , i); +strbuf_addf (&refname,"%02ld" , (long )i);
This should rather be:
strubf_addf(&refname, "%02"PRIuMAX, (uintmax_t) i);
This is splitting hairs though as it does not matter in practice. But I'd either drop this change to convert N and i to become a size_t, or I'd do it correctly.
t/unit-tests/t-reftable-pq.c static void test_pq(void) · line 45
Quoted 9 lines
t/unit-tests/t-reftable-pq.c renamed from reftable/pq_test.c +0
-1reftable_record_init (&recs[i],BLOCK_TYPE_REF ); recs[i].u.ref.refname =strbuf_detach (&refname,NULL );@@ -48,7 +41,6 @@ static void test_pq(void)merged_iter_pqueue_add (&pq, &e);merged_iter_pqueue_check (pq); - i = (i *7 ) %N ; }while (i !=1 );
This removed newline is of dubious value, but I guess that's subjective.
Patrick
PATCH 3/6 t-reftable-pq: make merged_iter_pqueue_check() static
In reply to Chandra Pratapmerged_iter_pqueue_check() is a function previously defined in reftable/pq_test.c (now t/unit-tests/t-reftable-pq.c) and used in the testing of a priority queue as defined by reftable/pq.{c, h}. As such, this function is only called by reftable/pq_test.c and it makes little sense to expose it to non-testing code via reftable/pq.h.
Hence, make this function static and remove its prototype from reftable/pq.h.
--- reftable/pq.h | 1 - t/unit-tests/t-reftable-pq.c | 2 +- 2 files changed, 1 insertion(+), 2 deletions(-)
reftable/pq.h +0 -1
@@ -22,7 +22,6 @@ struct merged_iter_pqueue {size_t cap; }; -void merged_iter_pqueue_check (struct merged_iter_pqueue pq);struct pq_entry merged_iter_pqueue_remove (struct merged_iter_pqueue *pq);void merged_iter_pqueue_add (struct merged_iter_pqueue *pq,const struct pq_entry *e);void merged_iter_pqueue_release (struct merged_iter_pqueue *pq);
t/unit-tests/t-reftable-pq.c +1 -1
@@ -10,7 +10,7 @@ license that can be found in the LICENSE file or at#include "reftable/constants.h" #include "reftable/pq.h" -void merged_iter_pqueue_check (struct merged_iter_pqueue pq) +static void merged_iter_pqueue_check (struct merged_iter_pqueue pq) {for (int i =1 ; i < pq.len; i++) {int parent = (i -1 ) /2 ;
Signature · 1 line
2.45.2.404.g9eaef5822c
PATCH 4/6 t-reftable-pq: make merged_iter_pqueue_check() callable by reference
In reply to Chandra Pratapmerged_iter_pqueue_check() checks the validity of a priority queue represented by a merged_iter_pqueue struct by asserting the parent-child relation in the struct's heap. Explicity passing a struct to this function means a copy of the entire struct is created, which is inefficient.
Make the function accept a pointer to the struct instead. This is safe to do since the function doesn't modify the struct in any way. Make the function parameter 'const' to assert immutability.
--- t/unit-tests/t-reftable-pq.c | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-)
t/unit-tests/t-reftable-pq.c +5 -5
@@ -10,11 +10,11 @@ license that can be found in the LICENSE file or at#include "reftable/constants.h" #include "reftable/pq.h" -static void merged_iter_pqueue_check (struct merged_iter_pqueue pq) +static void merged_iter_pqueue_check (const struct merged_iter_pqueue *pq) { -for (int i =1 ; i < pq.len; i++) { +for (int i =1 ; i < pq->len; i++) {int parent = (i -1 ) /2 ; -check (pq_less (&pq.heap[parent], &pq.heap[i])); +check (pq_less (&pq->heap[parent], &pq->heap[i])); } }
@@ -40,13 +40,13 @@ static void test_pq(void) };merged_iter_pqueue_add (&pq, &e); -merged_iter_pqueue_check (pq); +merged_iter_pqueue_check (&pq); i = (i *7 ) %N ; }while (i !=1 );while (!merged_iter_pqueue_is_empty (pq)) {struct pq_entry e =merged_iter_pqueue_remove (&pq); -merged_iter_pqueue_check (pq); +merged_iter_pqueue_check (&pq);check (reftable_record_type (e.rec) ==BLOCK_TYPE_REF );if (last)
Signature · 1 line
2.45.2.404.g9eaef5822c
Re: [GSoC][PATCH 4/6] t-reftable-pq: make merged_iter_pqueue_check() callable by reference
t/unit-tests/t-reftable-pq.c license that can be found in the LICENSE file or at · line 15
Quoted 13 lines · Chandra Pratap
t/unit-tests/t-reftable-pq.c +2
-2@@ -10,11 +10,11 @@ license that can be found in the LICENSE file or at#include "reftable/constants.h" #include "reftable/pq.h" -static void merged_iter_pqueue_check (struct merged_iter_pqueue pq) +static void merged_iter_pqueue_check (const struct merged_iter_pqueue *pq) { -for (int i =1 ; i < pq.len; i++) { +for (int i =1 ; i < pq->len; i++) {
Nit: we might also change this to size_t i while at it. I know that these changes are not super popular, but I eventually want Git to compile cleanly with -Wsign-conversion. So the more issues we fix while at it, the smaller the patch series for this needs to be.
Patrick
PATCH 5/6 t-reftable-pq: add test for index based comparison
In reply to Chandra PratapWhen 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.
--- t/unit-tests/t-reftable-pq.c | 44 ++++++++++++++++++++++++++++++++++-- 1 file changed, 42 insertions(+), 2 deletions(-)
t/unit-tests/t-reftable-pq.c +42 -2
@@ -18,7 +18,7 @@ static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq) } } -static void test_pq (void ) +static void test_pq_record (void ) {struct merged_iter_pqueue pq = {0 };struct reftable_record recs[54 ];
@@ -59,9 +59,49 @@ static void test_pq(void)merged_iter_pqueue_release (&pq); } + +static void test_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 (test_pq (),"pq works" ); +TEST (test_pq_record (),"pq works with record-based comparison" ); +TEST (test_pq_index (),"pq works with index-based comparison" );return test_done (); }
Signature · 1 line
2.45.2.404.g9eaef5822c
Re: [GSoC][PATCH 5/6] t-reftable-pq: add test for index based comparison
Quoted 14 lines · Chandra Pratap
t/unit-tests/t-reftable-pq.c +1
-1@@ -18,7 +18,7 @@ static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq) } } -static void test_pq (void ) +static void test_pq_record (void ) {struct merged_iter_pqueue pq = {0 };struct reftable_record recs[54 ];
t/unit-tests/t-reftable-pq.c static void test_pq(void) · line 62
Quoted 4 lines
t/unit-tests/t-reftable-pq.c +1
-0@@ -59,9 +59,49 @@ static void test_pq(void)merged_iter_pqueue_release (&pq); } +
Nit: there's an extraneous empty line here.
Other than that this patch looks good to me.
Patrick
PATCH 6/6 t-reftable-pq: add tests for merged_iter_pqueue_top()
In reply to Chandra Pratapmerged_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.
--- t/unit-tests/t-reftable-pq.c | 49 +++++++++++++++++++++++++++++++++++- 1 file changed, 48 insertions(+), 1 deletion(-)
t/unit-tests/t-reftable-pq.c +48 -1
@@ -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 test_pq_record (void ) {struct merged_iter_pqueue pq = {0 };
@@ -45,9 +50,11 @@ static void test_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);
@@ -59,7 +66,6 @@ static void test_pq_record(void)merged_iter_pqueue_release (&pq); } -static void test_pq_index (void ) {struct merged_iter_pqueue pq = {0 };
@@ -83,9 +89,11 @@ static void test_pq_index(void) }for (i =N -1 ; !merged_iter_pqueue_is_empty (pq); 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)
@@ -98,10 +106,49 @@ static void test_pq_index(void)merged_iter_pqueue_release (&pq); } +static void test_merged_iter_pqueue_top (void ) +{ +struct merged_iter_pqueue pq = {0 }; +struct reftable_record recs[14 ]; +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); + } + +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)); +for (i =0 ; i < pq.len; i++) { +check (pq_less (&top, &pq.heap[i])); + check_int(top.index, >, i); + } + } + +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 (test_pq_record (),"pq works with record-based comparison" );TEST (test_pq_index (),"pq works with index-based comparison" ); +TEST (test_merged_iter_pqueue_top (),"merged_iter_pqueue_top works" );return test_done (); }
Signature · 1 line
2.45.2.404.g9eaef5822c
Re: [GSoC][PATCH 6/6] t-reftable-pq: add tests for merged_iter_pqueue_top()
t/unit-tests/t-reftable-pq.c static void test_pq_record(void) · line 71
Quoted 8 lines · Chandra Pratap
t/unit-tests/t-reftable-pq.c +0
-1@@ -59,7 +66,6 @@ static void test_pq_record(void)merged_iter_pqueue_release (&pq); } -static void test_pq_index (void ) {struct merged_iter_pqueue pq = {0 };
Ah, you drop the newline here. This should probably be part of the preceding commit.
Quoted 21 lines
t/unit-tests/t-reftable-pq.c +17
-0@@ -98,10 +106,49 @@ static void test_pq_index(void)merged_iter_pqueue_release (&pq); } +static void test_merged_iter_pqueue_top (void ) +{ +struct merged_iter_pqueue pq = {0 }; +struct reftable_record recs[14 ]; +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, + }; +
t/unit-tests/t-reftable-pq.c static void test_pq_index(void) · line 135
Quoted 10 lines
t/unit-tests/t-reftable-pq.c +10
-0+merged_iter_pqueue_add (&pq, &e); +merged_iter_pqueue_check (&pq); + } + +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));
Do we also want to check that top is equal to the expected entry in recs?
Patrick
v2 cover t: port reftable/pq_test.c to the unit testing
In reply to Chandra PratapIn the recent codebase update (commit 8bf6fbd, 2023-12-09), a new unit testing framework written entirely in C was introduced to the Git project aimed at simplifying testing and reducing test run times. Currently, tests for the reftable refs-backend are performed by a custom testing framework defined by reftable/test_framework.{c, h}. Port reftable/pq_test.c to the unit testing framework and improve upon the ported test.
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.
---
Changes in v2:
- Change data type of index variable 'i' to 'size_t' from 'int'
- Use correct format specifier for 'size_t' types
- Improve the test for merged_iter_pqueue_top() by asserting equality between 'top.rec' and the corresponding record in 'recs' array
CI/PR for v2: https://github.com/gitgitgadget/git/pull/1745
Chandra Pratap (6):
reftable: clean up reftable/pq.c
t: move reftable/pq_test.c to the unit testing framework
t-reftable-pq: make merged_iter_pqueue_check() static
t-reftable-pq: make merged_iter_pqueue_check() callable
t-reftable-pq: add test for index based comparison
t-reftable-pq: add tests for merged_iter_pqueue_top()
Makefile | 2 +- reftable/pq.c | 18 +++-------- reftable/pq.h | 1 - reftable/pq_test.c | 74 ---------------------------- t/helper/test-reftable.c | 1 - t/unit-tests/t-reftable-pq.c | 155 +++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 160 insertions(+), 91 deletions(-)
Range-diff against v1:
1: f18b610f63 ! 1: f24dc84877 t: move reftable/pq_test.c to the unit testing framework
@@ t/unit-tests/t-reftable-pq.c: license that can be found in the LICENSE file or a
{
- int i;
- for (i = 1; i < pq.len; i++) {
-+ for (int i = 1; i < pq.len; i++) {
- int parent = (i - 1) / 2;
+- int parent = (i - 1) / 2;
-
- EXPECT(pq_less(&pq.heap[parent], &pq.heap[i]));
++ for (size_t i = 1; i < pq.len; i++) {
++ size_t parent = (i - 1) / 2;
+ check(pq_less(&pq.heap[parent], &pq.heap[i]));
}
}
@@ t/unit-tests/t-reftable-pq.c: license that can be found in the LICENSE file or a
for (i = 0; i < N; i++) {
struct strbuf refname = STRBUF_INIT;
- strbuf_addf(&refname, "%02d", i);
-+ strbuf_addf(&refname, "%02ld", (long)i);
++ strbuf_addf(&refname, "%02"PRIuMAX, (uintmax_t)i);
reftable_record_init(&recs[i], BLOCK_TYPE_REF);
recs[i].u.ref.refname = strbuf_detach(&refname, NULL);2: 798e0adfeb ! 2: ce42fd1288 t-reftable-pq: make merged_iter_pqueue_check() static
@@ t/unit-tests/t-reftable-pq.c: license that can be found in the LICENSE file or a
-void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
+static void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
{
- for (int i = 1; i < pq.len; i++) {
- int parent = (i - 1) / 2;
+ for (size_t i = 1; i < pq.len; i++) {
+ size_t parent = (i - 1) / 2;
3: 8412672105 ! 3: 226d72aa6a t-reftable-pq: make merged_iter_pqueue_check() callable by reference
@@ t/unit-tests/t-reftable-pq.c: license that can be found in the LICENSE file or a
-static void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
+static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
{
-- for (int i = 1; i < pq.len; i++) {
-+ for (int i = 1; i < pq->len; i++) {
- int parent = (i - 1) / 2;
+- for (size_t i = 1; i < pq.len; i++) {
++ for (size_t i = 1; i < pq->len; i++) {
+ size_t parent = (i - 1) / 2;
- check(pq_less(&pq.heap[parent], &pq.heap[i]));
+ check(pq_less(&pq->heap[parent], &pq->heap[i]));
}
4: 2ef5b8b0b1 ! 4: 00cb440f11 t-reftable-pq: add test for index based comparison
@@ t/unit-tests/t-reftable-pq.c: static void test_pq(void)
merged_iter_pqueue_release(&pq);
}
-+
+static void test_pq_index(void)
+{
+ struct merged_iter_pqueue pq = { 0 };
5: 838e67d2a3 ! 5: dd44486c28 t-reftable-pq: add tests for merged_iter_pqueue_top()
@@ t/unit-tests/t-reftable-pq.c: static void test_pq_record(void)
check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
if (last)
check_int(strcmp(last, e.rec->u.ref.refname), <, 0);
-@@ t/unit-tests/t-reftable-pq.c: static void test_pq_record(void)
- merged_iter_pqueue_release(&pq);
- }
-
--
- static void test_pq_index(void)
- {
- struct merged_iter_pqueue pq = { 0 };
@@ t/unit-tests/t-reftable-pq.c: static void test_pq_index(void)
}
@@ t/unit-tests/t-reftable-pq.c: static void test_pq_index(void)
+ merged_iter_pqueue_check(&pq);
+ }
+
-+ while (!merged_iter_pqueue_is_empty(pq)) {
++ for (i = N - 1; !merged_iter_pqueue_is_empty(pq); 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));
-+ for (i = 0; i < pq.len; i++) {
-+ check(pq_less(&top, &pq.heap[i]));
-+ check_int(top.index, >, i);
++ 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);
+ }
+ }
+PATCH v2 1/6 reftable: clean up reftable/pq.c
According to Documentation/CodingGuidelines, control-flow statements with a single line as their body must omit curly braces. Make reftable/pq.c conform to this guideline. Besides that, remove unnecessary newlines and variable assignment.
--- reftable/pq.c | 18 ++++-------------- 1 file changed, 4 insertions(+), 14 deletions(-)
reftable/pq.c +4 -14
@@ -27,22 +27,16 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq) pq->heap[0 ] = pq->heap[pq->len -1 ]; pq->len--; - i =0 ;while (i < pq->len) {int min = i;int j =2 * i +1 ;int k =2 * i +2 ; -if (j < pq->len &&pq_less (&pq->heap[j], &pq->heap[i])) { +if (j < pq->len &&pq_less (&pq->heap[j], &pq->heap[i])) min = j; - } -if (k < pq->len &&pq_less (&pq->heap[k], &pq->heap[min])) { +if (k < pq->len &&pq_less (&pq->heap[k], &pq->heap[min])) min = k; - } - -if (min == i) { +if (min == i)break ; - } -SWAP (pq->heap[i], pq->heap[min]); i = min; }
@@ -53,19 +47,15 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)void merged_iter_pqueue_add (struct merged_iter_pqueue *pq,const struct pq_entry *e) {int i =0 ; -REFTABLE_ALLOC_GROW (pq->heap, pq->len +1 , pq->cap); pq->heap[pq->len++] = *e; i = pq->len -1 ;while (i >0 ) {int j = (i -1 ) /2 ; -if (pq_less (&pq->heap[j], &pq->heap[i])) { +if (pq_less (&pq->heap[j], &pq->heap[i]))break ; - } -SWAP (pq->heap[j], pq->heap[i]); - i = j; } }
Signature · 1 line
2.45.2.404.g9eaef5822c
Re: [GSoC][PATCH v2 1/6] reftable: clean up reftable/pq.c
Quoted 43 lines · Chandra Pratap
According to
Documentation/CodingGuidelines, control-flow statements with a single line as their body must omit curly braces. Makereftable/pq.cconform to this guideline. Besides that, remove unnecessary newlines and variable assignment.Mentored-by Patrick Steinhardt <[email protected]>Mentored-by Christian Couder <[email protected]>Signed-off-by Chandra Pratap <[email protected]>--- reftable/pq.c | 18 ++++-------------- 1 file changed, 4 insertions(+), 14 deletions(-)reftable/pq.c +3
-9@@ -27,22 +27,16 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq) pq->heap[0 ] = pq->heap[pq->len -1 ]; pq->len--; - i =0 ;while (i < pq->len) {int min = i;int j =2 * i +1 ;int k =2 * i +2 ; -if (j < pq->len &&pq_less (&pq->heap[j], &pq->heap[i])) { +if (j < pq->len &&pq_less (&pq->heap[j], &pq->heap[i])) min = j; - } -if (k < pq->len &&pq_less (&pq->heap[k], &pq->heap[min])) { +if (k < pq->len &&pq_less (&pq->heap[k], &pq->heap[min])) min = k; - } - -if (min == i) { +if (min == i)break ; - } -SWAP (pq->heap[i], pq->heap[min]); i = min; }
reftable/pq.c struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq) · line 56
Quoted 4 lines
reftable/pq.c +0
-1@@ -53,19 +47,15 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)void merged_iter_pqueue_add (struct merged_iter_pqueue *pq,const struct pq_entry *e) {int i =0 ; -
Nit: I think this newline is helpful as it delimits the variable declarations from the actual code.
I wonder whether we should also change the type of i to size_t while at it, as pq->len is of type size_t, as well (and further up in the other test). It does mean that we have to add an explicit check whether pq->len == 0`, but that isn't all that bad.
In any case, if we want to do such a change, it should probably be in a separate commit.
reftable/pq.c struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq) · line 55
Quoted 6 lines
reftable/pq.c +0
-0REFTABLE_ALLOC_GROW (pq->heap, pq->len +1 , pq->cap); pq->heap[pq->len++] = *e; i = pq->len -1 ;while (i >0 ) {int j = (i -1 ) /2 ;
The type of j is wrong, as well.
Other than that this patch series looks good to me, thanks.
Patrick
PATCH v2 2/6 t: move reftable/pq_test.c to the unit testing framework
In reply to Chandra Pratapreftable/pq_test.c exercises a priority queue defined by reftable/pq.{c, h}. Migrate reftable/pq_test.c to the unit testing framework. Migration involves refactoring the tests to use the unit testing framework instead of reftable's test framework.
--- Makefile | 2 +- t/helper/test-reftable.c | 1 - .../pq_test.c => t/unit-tests/t-reftable-pq.c | 37 ++++++++----------- 3 files changed, 16 insertions(+), 24 deletions(-) rename reftable/pq_test.c => t/unit-tests/t-reftable-pq.c (62%)
Makefile +1 -1
@@ -1336,6 +1336,7 @@ THIRD_PARTY_SOURCES += sha1dc/% UNIT_TEST_PROGRAMS += t-ctype UNIT_TEST_PROGRAMS += t-mem-pool UNIT_TEST_PROGRAMS += t-prio-queue +UNIT_TEST_PROGRAMS += t-reftable-pq UNIT_TEST_PROGRAMS += t-strbuf UNIT_TEST_PROGRAMS += t-strcmp-offset UNIT_TEST_PROGRAMS += t-trailer
@@ -2675,7 +2676,6 @@ REFTABLE_TEST_OBJS += reftable/basics_test.o REFTABLE_TEST_OBJS += reftable/block_test.o REFTABLE_TEST_OBJS += reftable/dump.o REFTABLE_TEST_OBJS += reftable/merged_test.o -REFTABLE_TEST_OBJS += reftable/pq_test.o REFTABLE_TEST_OBJS += reftable/record_test.o REFTABLE_TEST_OBJS += reftable/readwrite_test.o REFTABLE_TEST_OBJS += reftable/stack_test.o
t/helper/test-reftable.c +0 -1
@@ -9,7 +9,6 @@ int cmd__reftable(int argc, const char **argv)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);stack_test_main (argc, argv);
t/unit-tests/t-reftable-pq.c renamed from reftable/pq_test.c +15 -22
@@ -6,35 +6,28 @@ license that can be found in the LICENSE file or athttps://developers.google.com/open-source/licenses/bsd */ -#include "system.h" - -#include "basics.h" -#include "constants.h" -#include "pq.h" -#include "record.h" -#include "reftable-tests.h" -#include "test_framework.h" +#include "test-lib.h" +#include "reftable/constants.h" +#include "reftable/pq.h" void merged_iter_pqueue_check (struct merged_iter_pqueue pq) { -int i; -for (i =1 ; i < pq.len; i++) { -int parent = (i -1 ) /2 ; - -EXPECT (pq_less (&pq.heap[parent], &pq.heap[i])); +for (size_t i =1 ; i < pq.len; i++) { +size_t parent = (i -1 ) /2 ; +check (pq_less (&pq.heap[parent], &pq.heap[i])); } }static void test_pq (void ) { -struct merged_iter_pqueue pq = {NULL }; +struct merged_iter_pqueue pq = {0 };struct reftable_record recs[54 ]; -int N =ARRAY_SIZE (recs) -1 , i; +size_t N =ARRAY_SIZE (recs) -1 , i;char *last =NULL ;for (i =0 ; i <N ; i++) {struct strbuf refname =STRBUF_INIT ; -strbuf_addf (&refname,"%02d" , i); +strbuf_addf (&refname,"%02" PRIuMAX, (uintmax_t )i);reftable_record_init (&recs[i],BLOCK_TYPE_REF ); recs[i].u.ref.refname =strbuf_detach (&refname,NULL );
@@ -48,7 +41,6 @@ static void test_pq(void)merged_iter_pqueue_add (&pq, &e);merged_iter_pqueue_check (pq); - i = (i *7 ) %N ; }while (i !=1 );
@@ -56,9 +48,9 @@ static void test_pq(void)struct pq_entry e =merged_iter_pqueue_remove (&pq);merged_iter_pqueue_check (pq); -EXPECT (reftable_record_type (e.rec) ==BLOCK_TYPE_REF ); +check (reftable_record_type (e.rec) ==BLOCK_TYPE_REF );if (last) -EXPECT (strcmp (last, e.rec->u.ref.refname) <0 ); + check_int(strcmp(last, e.rec->u.ref.refname), <, 0); last = e.rec->u.ref.refname; }
@@ -67,8 +59,9 @@ static void test_pq(void)merged_iter_pqueue_release (&pq); } -int pq_test_main (int argc,const char *argv[]) +int cmd_main (int argc,const char *argv[]) { -RUN_TEST (test_pq); -return 0 ; +TEST (test_pq (),"pq works" ); + +return test_done (); }
Signature · 1 line
2.45.2.404.g9eaef5822c
PATCH v2 3/6 t-reftable-pq: make merged_iter_pqueue_check() static
In reply to Chandra Pratapmerged_iter_pqueue_check() is a function previously defined in reftable/pq_test.c (now t/unit-tests/t-reftable-pq.c) and used in the testing of a priority queue as defined by reftable/pq.{c, h}. As such, this function is only called by reftable/pq_test.c and it makes little sense to expose it to non-testing code via reftable/pq.h.
Hence, make this function static and remove its prototype from reftable/pq.h.
--- reftable/pq.h | 1 - t/unit-tests/t-reftable-pq.c | 2 +- 2 files changed, 1 insertion(+), 2 deletions(-)
reftable/pq.h +0 -1
@@ -22,7 +22,6 @@ struct merged_iter_pqueue {size_t cap; }; -void merged_iter_pqueue_check (struct merged_iter_pqueue pq);struct pq_entry merged_iter_pqueue_remove (struct merged_iter_pqueue *pq);void merged_iter_pqueue_add (struct merged_iter_pqueue *pq,const struct pq_entry *e);void merged_iter_pqueue_release (struct merged_iter_pqueue *pq);
t/unit-tests/t-reftable-pq.c +1 -1
@@ -10,7 +10,7 @@ license that can be found in the LICENSE file or at#include "reftable/constants.h" #include "reftable/pq.h" -void merged_iter_pqueue_check (struct merged_iter_pqueue pq) +static void merged_iter_pqueue_check (struct merged_iter_pqueue pq) {for (size_t i =1 ; i < pq.len; i++) {size_t parent = (i -1 ) /2 ;
Signature · 1 line
2.45.2.404.g9eaef5822c
PATCH v2 4/6 t-reftable-pq: make merged_iter_pqueue_check() callable by reference
In reply to Chandra Pratapmerged_iter_pqueue_check() checks the validity of a priority queue represented by a merged_iter_pqueue struct by asserting the parent-child relation in the struct's heap. Explicity passing a struct to this function means a copy of the entire struct is created, which is inefficient.
Make the function accept a pointer to the struct instead. This is safe to do since the function doesn't modify the struct in any way. Make the function parameter 'const' to assert immutability.
--- t/unit-tests/t-reftable-pq.c | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-)
t/unit-tests/t-reftable-pq.c +5 -5
@@ -10,11 +10,11 @@ license that can be found in the LICENSE file or at#include "reftable/constants.h" #include "reftable/pq.h" -static void merged_iter_pqueue_check (struct merged_iter_pqueue pq) +static void merged_iter_pqueue_check (const struct merged_iter_pqueue *pq) { -for (size_t i =1 ; i < pq.len; i++) { +for (size_t i =1 ; i < pq->len; i++) {size_t parent = (i -1 ) /2 ; -check (pq_less (&pq.heap[parent], &pq.heap[i])); +check (pq_less (&pq->heap[parent], &pq->heap[i])); } }
@@ -40,13 +40,13 @@ static void test_pq(void) };merged_iter_pqueue_add (&pq, &e); -merged_iter_pqueue_check (pq); +merged_iter_pqueue_check (&pq); i = (i *7 ) %N ; }while (i !=1 );while (!merged_iter_pqueue_is_empty (pq)) {struct pq_entry e =merged_iter_pqueue_remove (&pq); -merged_iter_pqueue_check (pq); +merged_iter_pqueue_check (&pq);check (reftable_record_type (e.rec) ==BLOCK_TYPE_REF );if (last)
Signature · 1 line
2.45.2.404.g9eaef5822c
PATCH v2 5/6 t-reftable-pq: add test for index based comparison
In reply to Chandra PratapWhen 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.
--- t/unit-tests/t-reftable-pq.c | 43 ++++++++++++++++++++++++++++++++++-- 1 file changed, 41 insertions(+), 2 deletions(-)
t/unit-tests/t-reftable-pq.c +41 -2
@@ -18,7 +18,7 @@ static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq) } } -static void test_pq (void ) +static void test_pq_record (void ) {struct merged_iter_pqueue pq = {0 };struct reftable_record recs[54 ];
@@ -59,9 +59,48 @@ static void test_pq(void)merged_iter_pqueue_release (&pq); } +static void test_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 (test_pq (),"pq works" ); +TEST (test_pq_record (),"pq works with record-based comparison" ); +TEST (test_pq_index (),"pq works with index-based comparison" );return test_done (); }
Signature · 1 line
2.45.2.404.g9eaef5822c
PATCH v2 6/6 t-reftable-pq: add tests for merged_iter_pqueue_top()
In reply to Chandra Pratapmerged_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.
--- t/unit-tests/t-reftable-pq.c | 49 ++++++++++++++++++++++++++++++++++++ 1 file changed, 49 insertions(+)
t/unit-tests/t-reftable-pq.c +49 -0
@@ -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 test_pq_record (void ) {struct merged_iter_pqueue pq = {0 };
@@ -45,9 +50,11 @@ static void test_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);
@@ -82,9 +89,11 @@ static void test_pq_index(void) }for (i =N -1 ; !merged_iter_pqueue_is_empty (pq); 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)
@@ -97,10 +106,50 @@ static void test_pq_index(void)merged_iter_pqueue_release (&pq); } +static void test_merged_iter_pqueue_top (void ) +{ +struct merged_iter_pqueue pq = {0 }; +struct reftable_record recs[14 ]; +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 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); + } + } + +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 (test_pq_record (),"pq works with record-based comparison" );TEST (test_pq_index (),"pq works with index-based comparison" ); +TEST (test_merged_iter_pqueue_top (),"merged_iter_pqueue_top works" );return test_done (); }
Signature · 1 line
2.45.2.404.g9eaef5822c
v3 cover t: port reftable/pq_test.c to the unit testing framework
In reply to Chandra PratapIn the recent codebase update (commit 8bf6fbd, 2023-12-09), a new unit testing framework written entirely in C was introduced to the Git project aimed at simplifying testing and reducing test run times. Currently, tests for the reftable refs-backend are performed by a custom testing framework defined by reftable/test_framework.{c, h}. Port reftable/pq_test.c to the unit testing framework and improve upon the ported test.
The first two patches in the series are preparatory cleanup, the third patch moves the test to the unit testing framework, and the rest of the patches improve upon the ported test.
---
Changes in v3:
- Add another cleanup patch for reftable/pq.c
- Change the commit title of the first patch
- Re-introduce a lost newline in the first patch
CI/PR for v3: https://github.com/gitgitgadget/git/pull/1745
Chandra Pratap(7):
reftable: remove unncessary curly braces in reftable/pq.c
reftable: change the type of array indices to 'size_t' in
t: move reftable/pq_test.c to the unit testing framework
t-reftable-pq: make merged_iter_pqueue_check() static
t-reftable-pq: make merged_iter_pqueue_check() callable
t-reftable-pq: add test for index based comparison
t-reftable-pq: add tests for merged_iter_pqueue_top()
Makefile | 2 +- reftable/pq.c | 29 +++-------- reftable/pq.h | 1 - reftable/pq_test.c | 74 ---------------------------- t/helper/test-reftable.c | 1 - t/unit-tests/t-reftable-pq.c | 155 +++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 166 insertions(+), 96 deletions(-)
Range-diff against v2:
1: 9ac1035c07 ! 1: d3c5605ea2 reftable: clean up reftable/pq.c
@@ Metadata
Author: Chandra Pratap <[email protected]>
## Commit message ##
- reftable: clean up reftable/pq.c
+ reftable: remove unncessary curly braces in reftable/pq.c
According to Documentation/CodingGuidelines, control-flow statements
with a single line as their body must omit curly braces. Make
@@ reftable/pq.c: struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pque
SWAP(pq->heap[i], pq->heap[min]);
i = min;
}
-@@ reftable/pq.c: struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
- void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e)
- {
- int i = 0;
--
- REFTABLE_ALLOC_GROW(pq->heap, pq->len + 1, pq->cap);
- pq->heap[pq->len++] = *e;
-
+@@ reftable/pq.c: void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry
i = pq->len - 1;
while (i > 0) {
int j = (i - 1) / 2;
-: ---------- > 2: 1873fb02ce reftable: change the type of array indices to 'size_t' in reftable/pq.c 2: f24dc84877 = 3: 3cccf8266a t: move reftable/pq_test.c to the unit testing framework 3: ce42fd1288 = 4: 4b63849694 t-reftable-pq: make merged_iter_pqueue_check() static 4: 226d72aa6a = 5: 3698a7189f t-reftable-pq: make merged_iter_pqueue_check() callable by reference 5: 00cb440f11 = 6: d58c8f709e t-reftable-pq: add test for index based comparison 6: dd44486c28 = 7: 69521f0ff7 t-reftable-pq: add tests for merged_iter_pqueue_top()
PATCH v3 1/7 reftable: remove unncessary curly braces in reftable/pq.c
According to Documentation/CodingGuidelines, control-flow statements with a single line as their body must omit curly braces. Make reftable/pq.c conform to this guideline. Besides that, remove unnecessary newlines and variable assignment.
--- reftable/pq.c | 17 ++++------------- 1 file changed, 4 insertions(+), 13 deletions(-)
reftable/pq.c +4 -13
@@ -27,22 +27,16 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq) pq->heap[0 ] = pq->heap[pq->len -1 ]; pq->len--; - i =0 ;while (i < pq->len) {int min = i;int j =2 * i +1 ;int k =2 * i +2 ; -if (j < pq->len &&pq_less (&pq->heap[j], &pq->heap[i])) { +if (j < pq->len &&pq_less (&pq->heap[j], &pq->heap[i])) min = j; - } -if (k < pq->len &&pq_less (&pq->heap[k], &pq->heap[min])) { +if (k < pq->len &&pq_less (&pq->heap[k], &pq->heap[min])) min = k; - } - -if (min == i) { +if (min == i)break ; - } -SWAP (pq->heap[i], pq->heap[min]); i = min; }
@@ -60,12 +54,9 @@ void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry i = pq->len -1 ;while (i >0 ) {int j = (i -1 ) /2 ; -if (pq_less (&pq->heap[j], &pq->heap[i])) { +if (pq_less (&pq->heap[j], &pq->heap[i]))break ; - } -SWAP (pq->heap[j], pq->heap[i]); - i = j; } }
Signature · 1 line
2.45.2.404.g9eaef5822c
PATCH v3 2/7 reftable: change the type of array indices to 'size_t' in reftable/pq.c
In reply to Chandra Pratap--- reftable/pq.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-)
reftable/pq.c +6 -6
@@ -22,15 +22,15 @@ int pq_less(struct pq_entry *a, struct pq_entry *b)struct pq_entry merged_iter_pqueue_remove (struct merged_iter_pqueue *pq) { -int i =0 ; +size_t i =0 ;struct pq_entry e = pq->heap[0 ]; pq->heap[0 ] = pq->heap[pq->len -1 ]; pq->len--;while (i < pq->len) { -int min = i; -int j =2 * i +1 ; -int k =2 * i +2 ; +size_t min = i; +size_t j =2 * i +1 ; +size_t k =2 * i +2 ;if (j < pq->len &&pq_less (&pq->heap[j], &pq->heap[i])) min = j;if (k < pq->len &&pq_less (&pq->heap[k], &pq->heap[min]))
@@ -46,14 +46,14 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)void merged_iter_pqueue_add (struct merged_iter_pqueue *pq,const struct pq_entry *e) { -int i =0 ; +size_t i =0 ;REFTABLE_ALLOC_GROW (pq->heap, pq->len +1 , pq->cap); pq->heap[pq->len++] = *e; i = pq->len -1 ;while (i >0 ) { -int j = (i -1 ) /2 ; +size_t j = (i -1 ) /2 ;if (pq_less (&pq->heap[j], &pq->heap[i]))break ;SWAP (pq->heap[j], pq->heap[i]);
Signature · 1 line
2.45.2.404.g9eaef5822c
Re: [PATCH v3 2/7] reftable: change the type of array indices to 'size_t' in reftable/pq.c
On Tue, Jun 11, 2024 at 01:49:19PM +0530, Chandra Pratap wrote:
This commit is missing a commit message. The important information that the reader needs to understand this change is that pq->len is of type size_t, as well. So that information should probably go in here.
Other than that this patch series looks good to me, thanks!
Patrick
Quoted 51 lines
Mentored-by Patrick Steinhardt <[email protected]>Mentored-by Christian Couder <[email protected]>Signed-off-by Chandra Pratap <[email protected]>--- reftable/pq.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-)reftable/pq.c +6
-6@@ -22,15 +22,15 @@ int pq_less(struct pq_entry *a, struct pq_entry *b)struct pq_entry merged_iter_pqueue_remove (struct merged_iter_pqueue *pq) { -int i =0 ; +size_t i =0 ;struct pq_entry e = pq->heap[0 ]; pq->heap[0 ] = pq->heap[pq->len -1 ]; pq->len--;while (i < pq->len) { -int min = i; -int j =2 * i +1 ; -int k =2 * i +2 ; +size_t min = i; +size_t j =2 * i +1 ; +size_t k =2 * i +2 ;if (j < pq->len &&pq_less (&pq->heap[j], &pq->heap[i])) min = j;if (k < pq->len &&pq_less (&pq->heap[k], &pq->heap[min]))@@ -46,14 +46,14 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)void merged_iter_pqueue_add (struct merged_iter_pqueue *pq,const struct pq_entry *e) { -int i =0 ; +size_t i =0 ;REFTABLE_ALLOC_GROW (pq->heap, pq->len +1 , pq->cap); pq->heap[pq->len++] = *e; i = pq->len -1 ;while (i >0 ) { -int j = (i -1 ) /2 ; +size_t j = (i -1 ) /2 ;if (pq_less (&pq->heap[j], &pq->heap[i]))break ;SWAP (pq->heap[j], pq->heap[i]);Signature · 1 line
2.45.2.404.g9eaef5822c
PATCH v3 3/7 t: move reftable/pq_test.c to the unit testing framework
In reply to Chandra Pratapreftable/pq_test.c exercises a priority queue defined by reftable/pq.{c, h}. Migrate reftable/pq_test.c to the unit testing framework. Migration involves refactoring the tests to use the unit testing framework instead of reftable's test framework.
--- Makefile | 2 +- t/helper/test-reftable.c | 1 - .../pq_test.c => t/unit-tests/t-reftable-pq.c | 37 ++++++++----------- 3 files changed, 16 insertions(+), 24 deletions(-) rename reftable/pq_test.c => t/unit-tests/t-reftable-pq.c (62%)
Makefile +1 -1
@@ -1336,6 +1336,7 @@ THIRD_PARTY_SOURCES += sha1dc/% UNIT_TEST_PROGRAMS += t-ctype UNIT_TEST_PROGRAMS += t-mem-pool UNIT_TEST_PROGRAMS += t-prio-queue +UNIT_TEST_PROGRAMS += t-reftable-pq UNIT_TEST_PROGRAMS += t-strbuf UNIT_TEST_PROGRAMS += t-strcmp-offset UNIT_TEST_PROGRAMS += t-trailer
@@ -2675,7 +2676,6 @@ REFTABLE_TEST_OBJS += reftable/basics_test.o REFTABLE_TEST_OBJS += reftable/block_test.o REFTABLE_TEST_OBJS += reftable/dump.o REFTABLE_TEST_OBJS += reftable/merged_test.o -REFTABLE_TEST_OBJS += reftable/pq_test.o REFTABLE_TEST_OBJS += reftable/record_test.o REFTABLE_TEST_OBJS += reftable/readwrite_test.o REFTABLE_TEST_OBJS += reftable/stack_test.o
t/helper/test-reftable.c +0 -1
@@ -9,7 +9,6 @@ int cmd__reftable(int argc, const char **argv)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);stack_test_main (argc, argv);
t/unit-tests/t-reftable-pq.c renamed from reftable/pq_test.c +15 -22
@@ -6,35 +6,28 @@ license that can be found in the LICENSE file or athttps://developers.google.com/open-source/licenses/bsd */ -#include "system.h" - -#include "basics.h" -#include "constants.h" -#include "pq.h" -#include "record.h" -#include "reftable-tests.h" -#include "test_framework.h" +#include "test-lib.h" +#include "reftable/constants.h" +#include "reftable/pq.h" void merged_iter_pqueue_check (struct merged_iter_pqueue pq) { -int i; -for (i =1 ; i < pq.len; i++) { -int parent = (i -1 ) /2 ; - -EXPECT (pq_less (&pq.heap[parent], &pq.heap[i])); +for (size_t i =1 ; i < pq.len; i++) { +size_t parent = (i -1 ) /2 ; +check (pq_less (&pq.heap[parent], &pq.heap[i])); } }static void test_pq (void ) { -struct merged_iter_pqueue pq = {NULL }; +struct merged_iter_pqueue pq = {0 };struct reftable_record recs[54 ]; -int N =ARRAY_SIZE (recs) -1 , i; +size_t N =ARRAY_SIZE (recs) -1 , i;char *last =NULL ;for (i =0 ; i <N ; i++) {struct strbuf refname =STRBUF_INIT ; -strbuf_addf (&refname,"%02d" , i); +strbuf_addf (&refname,"%02" PRIuMAX, (uintmax_t )i);reftable_record_init (&recs[i],BLOCK_TYPE_REF ); recs[i].u.ref.refname =strbuf_detach (&refname,NULL );
@@ -48,7 +41,6 @@ static void test_pq(void)merged_iter_pqueue_add (&pq, &e);merged_iter_pqueue_check (pq); - i = (i *7 ) %N ; }while (i !=1 );
@@ -56,9 +48,9 @@ static void test_pq(void)struct pq_entry e =merged_iter_pqueue_remove (&pq);merged_iter_pqueue_check (pq); -EXPECT (reftable_record_type (e.rec) ==BLOCK_TYPE_REF ); +check (reftable_record_type (e.rec) ==BLOCK_TYPE_REF );if (last) -EXPECT (strcmp (last, e.rec->u.ref.refname) <0 ); + check_int(strcmp(last, e.rec->u.ref.refname), <, 0); last = e.rec->u.ref.refname; }
@@ -67,8 +59,9 @@ static void test_pq(void)merged_iter_pqueue_release (&pq); } -int pq_test_main (int argc,const char *argv[]) +int cmd_main (int argc,const char *argv[]) { -RUN_TEST (test_pq); -return 0 ; +TEST (test_pq (),"pq works" ); + +return test_done (); }
Signature · 1 line
2.45.2.404.g9eaef5822c
PATCH v3 4/7 t-reftable-pq: make merged_iter_pqueue_check() static
In reply to Chandra Pratapmerged_iter_pqueue_check() is a function previously defined in reftable/pq_test.c (now t/unit-tests/t-reftable-pq.c) and used in the testing of a priority queue as defined by reftable/pq.{c, h}. As such, this function is only called by reftable/pq_test.c and it makes little sense to expose it to non-testing code via reftable/pq.h.
Hence, make this function static and remove its prototype from reftable/pq.h.
--- reftable/pq.h | 1 - t/unit-tests/t-reftable-pq.c | 2 +- 2 files changed, 1 insertion(+), 2 deletions(-)
reftable/pq.h +0 -1
@@ -22,7 +22,6 @@ struct merged_iter_pqueue {size_t cap; }; -void merged_iter_pqueue_check (struct merged_iter_pqueue pq);struct pq_entry merged_iter_pqueue_remove (struct merged_iter_pqueue *pq);void merged_iter_pqueue_add (struct merged_iter_pqueue *pq,const struct pq_entry *e);void merged_iter_pqueue_release (struct merged_iter_pqueue *pq);
t/unit-tests/t-reftable-pq.c +1 -1
@@ -10,7 +10,7 @@ license that can be found in the LICENSE file or at#include "reftable/constants.h" #include "reftable/pq.h" -void merged_iter_pqueue_check (struct merged_iter_pqueue pq) +static void merged_iter_pqueue_check (struct merged_iter_pqueue pq) {for (size_t i =1 ; i < pq.len; i++) {size_t parent = (i -1 ) /2 ;
Signature · 1 line
2.45.2.404.g9eaef5822c
PATCH v3 5/7 t-reftable-pq: make merged_iter_pqueue_check() callable by reference
In reply to Chandra Pratapmerged_iter_pqueue_check() checks the validity of a priority queue represented by a merged_iter_pqueue struct by asserting the parent-child relation in the struct's heap. Explicity passing a struct to this function means a copy of the entire struct is created, which is inefficient.
Make the function accept a pointer to the struct instead. This is safe to do since the function doesn't modify the struct in any way. Make the function parameter 'const' to assert immutability.
--- t/unit-tests/t-reftable-pq.c | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-)
t/unit-tests/t-reftable-pq.c +5 -5
@@ -10,11 +10,11 @@ license that can be found in the LICENSE file or at#include "reftable/constants.h" #include "reftable/pq.h" -static void merged_iter_pqueue_check (struct merged_iter_pqueue pq) +static void merged_iter_pqueue_check (const struct merged_iter_pqueue *pq) { -for (size_t i =1 ; i < pq.len; i++) { +for (size_t i =1 ; i < pq->len; i++) {size_t parent = (i -1 ) /2 ; -check (pq_less (&pq.heap[parent], &pq.heap[i])); +check (pq_less (&pq->heap[parent], &pq->heap[i])); } }
@@ -40,13 +40,13 @@ static void test_pq(void) };merged_iter_pqueue_add (&pq, &e); -merged_iter_pqueue_check (pq); +merged_iter_pqueue_check (&pq); i = (i *7 ) %N ; }while (i !=1 );while (!merged_iter_pqueue_is_empty (pq)) {struct pq_entry e =merged_iter_pqueue_remove (&pq); -merged_iter_pqueue_check (pq); +merged_iter_pqueue_check (&pq);check (reftable_record_type (e.rec) ==BLOCK_TYPE_REF );if (last)
Signature · 1 line
2.45.2.404.g9eaef5822c
PATCH v3 6/7 t-reftable-pq: add test for index based comparison
In reply to Chandra PratapWhen 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.
--- t/unit-tests/t-reftable-pq.c | 43 ++++++++++++++++++++++++++++++++++-- 1 file changed, 41 insertions(+), 2 deletions(-)
t/unit-tests/t-reftable-pq.c +41 -2
@@ -18,7 +18,7 @@ static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq) } } -static void test_pq (void ) +static void test_pq_record (void ) {struct merged_iter_pqueue pq = {0 };struct reftable_record recs[54 ];
@@ -59,9 +59,48 @@ static void test_pq(void)merged_iter_pqueue_release (&pq); } +static void test_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 (test_pq (),"pq works" ); +TEST (test_pq_record (),"pq works with record-based comparison" ); +TEST (test_pq_index (),"pq works with index-based comparison" );return test_done (); }
Signature · 1 line
2.45.2.404.g9eaef5822c
PATCH v3 7/7 t-reftable-pq: add tests for merged_iter_pqueue_top()
In reply to Chandra Pratapmerged_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.
--- t/unit-tests/t-reftable-pq.c | 49 ++++++++++++++++++++++++++++++++++++ 1 file changed, 49 insertions(+)
t/unit-tests/t-reftable-pq.c +49 -0
@@ -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 test_pq_record (void ) {struct merged_iter_pqueue pq = {0 };
@@ -45,9 +50,11 @@ static void test_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);
@@ -82,9 +89,11 @@ static void test_pq_index(void) }for (i =N -1 ; !merged_iter_pqueue_is_empty (pq); 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)
@@ -97,10 +106,50 @@ static void test_pq_index(void)merged_iter_pqueue_release (&pq); } +static void test_merged_iter_pqueue_top (void ) +{ +struct merged_iter_pqueue pq = {0 }; +struct reftable_record recs[14 ]; +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 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); + } + } + +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 (test_pq_record (),"pq works with record-based comparison" );TEST (test_pq_index (),"pq works with index-based comparison" ); +TEST (test_merged_iter_pqueue_top (),"merged_iter_pqueue_top works" );return test_done (); }
Signature · 1 line
2.45.2.404.g9eaef5822c
v4 cover t: port reftable/pq_test.c to the unit testing framework
In reply to Chandra PratapIn the recent codebase update (commit 8bf6fbd, 2023-12-09), a new unit testing framework written entirely in C was introduced to the Git project aimed at simplifying testing and reducing test run times. Currently, tests for the reftable refs-backend are performed by a custom testing framework defined by reftable/test_framework.{c, h}. Port reftable/pq_test.c to the unit testing framework and improve upon the ported test.
The first two patches in the series are preparatory cleanup, the third patch moves the test to the unit testing framework, and the rest of the patches improve upon the ported test.
---
Changes in v4:
- Add a commit message for the second patch
CI/PR for v4: https://github.com/gitgitgadget/git/pull/1745
Chandra Pratap(7):
reftable: remove unncessary curly braces in reftable/pq.c
reftable: change the type of array indices to 'size_t' in
t: move reftable/pq_test.c to the unit testing framework
t-reftable-pq: make merged_iter_pqueue_check() static
t-reftable-pq: make merged_iter_pqueue_check() callable
t-reftable-pq: add test for index based comparison
t-reftable-pq: add tests for merged_iter_pqueue_top()
Makefile | 2 +- reftable/pq.c | 29 +++-------- reftable/pq.h | 1 - reftable/pq_test.c | 74 ---------------------------- t/helper/test-reftable.c | 1 - t/unit-tests/t-reftable-pq.c | 155 +++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 166 insertions(+), 96 deletions(-)
Range-diff against v3:
1: 3c333e7770 ! 1: 1873fb02ce reftable: change the type of array indices to 'size_t' in reftable/pq.c
@@ Metadata
## Commit message ##
reftable: change the type of array indices to 'size_t' in reftable/pq.c
+ The variables 'i', 'j', 'k' and 'min' are used as indices for
+ 'pq->heap', which is an array. Additionally, 'pq->len' is of
+ type 'size_t' and is often used to assign values to these
+ variables. Hence, change the type of these variables from 'int'
+ to 'size_t'.
+
2: bf547f705a = 2: 3cccf8266a t: move reftable/pq_test.c to the unit testing framework 3: 7dd3a2b27f = 3: 4b63849694 t-reftable-pq: make merged_iter_pqueue_check() static 4: c803e7adfc = 4: 3698a7189f t-reftable-pq: make merged_iter_pqueue_check() callable by reference 5: 0b03f3567d = 5: d58c8f709e t-reftable-pq: add test for index based comparison 6: 0cdfa6221e = 6: 69521f0ff7 t-reftable-pq: add tests for merged_iter_pqueue_top()
PATCH v4 1/7 reftable: remove unncessary curly braces in reftable/pq.c
According to Documentation/CodingGuidelines, control-flow statements with a single line as their body must omit curly braces. Make reftable/pq.c conform to this guideline. Besides that, remove unnecessary newlines and variable assignment.
--- reftable/pq.c | 17 ++++------------- 1 file changed, 4 insertions(+), 13 deletions(-)
reftable/pq.c +4 -13
@@ -27,22 +27,16 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq) pq->heap[0 ] = pq->heap[pq->len -1 ]; pq->len--; - i =0 ;while (i < pq->len) {int min = i;int j =2 * i +1 ;int k =2 * i +2 ; -if (j < pq->len &&pq_less (&pq->heap[j], &pq->heap[i])) { +if (j < pq->len &&pq_less (&pq->heap[j], &pq->heap[i])) min = j; - } -if (k < pq->len &&pq_less (&pq->heap[k], &pq->heap[min])) { +if (k < pq->len &&pq_less (&pq->heap[k], &pq->heap[min])) min = k; - } - -if (min == i) { +if (min == i)break ; - } -SWAP (pq->heap[i], pq->heap[min]); i = min; }
@@ -60,12 +54,9 @@ void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry i = pq->len -1 ;while (i >0 ) {int j = (i -1 ) /2 ; -if (pq_less (&pq->heap[j], &pq->heap[i])) { +if (pq_less (&pq->heap[j], &pq->heap[i]))break ; - } -SWAP (pq->heap[j], pq->heap[i]); - i = j; } }
Signature · 1 line
2.45.2.404.g9eaef5822c
PATCH v4 2/7 reftable: change the type of array indices to 'size_t' in reftable/pq.c
In reply to Chandra PratapThe variables 'i', 'j', 'k' and 'min' are used as indices for 'pq->heap', which is an array. Additionally, 'pq->len' is of type 'size_t' and is often used to assign values to these variables. Hence, change the type of these variables from 'int' to 'size_t'.
--- reftable/pq.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-)
reftable/pq.c +6 -6
@@ -22,15 +22,15 @@ int pq_less(struct pq_entry *a, struct pq_entry *b)struct pq_entry merged_iter_pqueue_remove (struct merged_iter_pqueue *pq) { -int i =0 ; +size_t i =0 ;struct pq_entry e = pq->heap[0 ]; pq->heap[0 ] = pq->heap[pq->len -1 ]; pq->len--;while (i < pq->len) { -int min = i; -int j =2 * i +1 ; -int k =2 * i +2 ; +size_t min = i; +size_t j =2 * i +1 ; +size_t k =2 * i +2 ;if (j < pq->len &&pq_less (&pq->heap[j], &pq->heap[i])) min = j;if (k < pq->len &&pq_less (&pq->heap[k], &pq->heap[min]))
@@ -46,14 +46,14 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)void merged_iter_pqueue_add (struct merged_iter_pqueue *pq,const struct pq_entry *e) { -int i =0 ; +size_t i =0 ;REFTABLE_ALLOC_GROW (pq->heap, pq->len +1 , pq->cap); pq->heap[pq->len++] = *e; i = pq->len -1 ;while (i >0 ) { -int j = (i -1 ) /2 ; +size_t j = (i -1 ) /2 ;if (pq_less (&pq->heap[j], &pq->heap[i]))break ;SWAP (pq->heap[j], pq->heap[i]);
Signature · 1 line
2.45.2.404.g9eaef5822c
PATCH v4 3/7 t: move reftable/pq_test.c to the unit testing framework
In reply to Chandra Pratapreftable/pq_test.c exercises a priority queue defined by reftable/pq.{c, h}. Migrate reftable/pq_test.c to the unit testing framework. Migration involves refactoring the tests to use the unit testing framework instead of reftable's test framework.
--- Makefile | 2 +- t/helper/test-reftable.c | 1 - .../pq_test.c => t/unit-tests/t-reftable-pq.c | 37 ++++++++----------- 3 files changed, 16 insertions(+), 24 deletions(-) rename reftable/pq_test.c => t/unit-tests/t-reftable-pq.c (62%)
Makefile +1 -1
@@ -1336,6 +1336,7 @@ THIRD_PARTY_SOURCES += sha1dc/% UNIT_TEST_PROGRAMS += t-ctype UNIT_TEST_PROGRAMS += t-mem-pool UNIT_TEST_PROGRAMS += t-prio-queue +UNIT_TEST_PROGRAMS += t-reftable-pq UNIT_TEST_PROGRAMS += t-strbuf UNIT_TEST_PROGRAMS += t-strcmp-offset UNIT_TEST_PROGRAMS += t-trailer
@@ -2675,7 +2676,6 @@ REFTABLE_TEST_OBJS += reftable/basics_test.o REFTABLE_TEST_OBJS += reftable/block_test.o REFTABLE_TEST_OBJS += reftable/dump.o REFTABLE_TEST_OBJS += reftable/merged_test.o -REFTABLE_TEST_OBJS += reftable/pq_test.o REFTABLE_TEST_OBJS += reftable/record_test.o REFTABLE_TEST_OBJS += reftable/readwrite_test.o REFTABLE_TEST_OBJS += reftable/stack_test.o
t/helper/test-reftable.c +0 -1
@@ -9,7 +9,6 @@ int cmd__reftable(int argc, const char **argv)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);stack_test_main (argc, argv);
t/unit-tests/t-reftable-pq.c renamed from reftable/pq_test.c +15 -22
@@ -6,35 +6,28 @@ license that can be found in the LICENSE file or athttps://developers.google.com/open-source/licenses/bsd */ -#include "system.h" - -#include "basics.h" -#include "constants.h" -#include "pq.h" -#include "record.h" -#include "reftable-tests.h" -#include "test_framework.h" +#include "test-lib.h" +#include "reftable/constants.h" +#include "reftable/pq.h" void merged_iter_pqueue_check (struct merged_iter_pqueue pq) { -int i; -for (i =1 ; i < pq.len; i++) { -int parent = (i -1 ) /2 ; - -EXPECT (pq_less (&pq.heap[parent], &pq.heap[i])); +for (size_t i =1 ; i < pq.len; i++) { +size_t parent = (i -1 ) /2 ; +check (pq_less (&pq.heap[parent], &pq.heap[i])); } }static void test_pq (void ) { -struct merged_iter_pqueue pq = {NULL }; +struct merged_iter_pqueue pq = {0 };struct reftable_record recs[54 ]; -int N =ARRAY_SIZE (recs) -1 , i; +size_t N =ARRAY_SIZE (recs) -1 , i;char *last =NULL ;for (i =0 ; i <N ; i++) {struct strbuf refname =STRBUF_INIT ; -strbuf_addf (&refname,"%02d" , i); +strbuf_addf (&refname,"%02" PRIuMAX, (uintmax_t )i);reftable_record_init (&recs[i],BLOCK_TYPE_REF ); recs[i].u.ref.refname =strbuf_detach (&refname,NULL );
@@ -48,7 +41,6 @@ static void test_pq(void)merged_iter_pqueue_add (&pq, &e);merged_iter_pqueue_check (pq); - i = (i *7 ) %N ; }while (i !=1 );
@@ -56,9 +48,9 @@ static void test_pq(void)struct pq_entry e =merged_iter_pqueue_remove (&pq);merged_iter_pqueue_check (pq); -EXPECT (reftable_record_type (e.rec) ==BLOCK_TYPE_REF ); +check (reftable_record_type (e.rec) ==BLOCK_TYPE_REF );if (last) -EXPECT (strcmp (last, e.rec->u.ref.refname) <0 ); + check_int(strcmp(last, e.rec->u.ref.refname), <, 0); last = e.rec->u.ref.refname; }
@@ -67,8 +59,9 @@ static void test_pq(void)merged_iter_pqueue_release (&pq); } -int pq_test_main (int argc,const char *argv[]) +int cmd_main (int argc,const char *argv[]) { -RUN_TEST (test_pq); -return 0 ; +TEST (test_pq (),"pq works" ); + +return test_done (); }
Signature · 1 line
2.45.2.404.g9eaef5822c
PATCH v4 4/7 t-reftable-pq: make merged_iter_pqueue_check() static
In reply to Chandra Pratapmerged_iter_pqueue_check() is a function previously defined in reftable/pq_test.c (now t/unit-tests/t-reftable-pq.c) and used in the testing of a priority queue as defined by reftable/pq.{c, h}. As such, this function is only called by reftable/pq_test.c and it makes little sense to expose it to non-testing code via reftable/pq.h.
Hence, make this function static and remove its prototype from reftable/pq.h.
--- reftable/pq.h | 1 - t/unit-tests/t-reftable-pq.c | 2 +- 2 files changed, 1 insertion(+), 2 deletions(-)
reftable/pq.h +0 -1
@@ -22,7 +22,6 @@ struct merged_iter_pqueue {size_t cap; }; -void merged_iter_pqueue_check (struct merged_iter_pqueue pq);struct pq_entry merged_iter_pqueue_remove (struct merged_iter_pqueue *pq);void merged_iter_pqueue_add (struct merged_iter_pqueue *pq,const struct pq_entry *e);void merged_iter_pqueue_release (struct merged_iter_pqueue *pq);
t/unit-tests/t-reftable-pq.c +1 -1
@@ -10,7 +10,7 @@ license that can be found in the LICENSE file or at#include "reftable/constants.h" #include "reftable/pq.h" -void merged_iter_pqueue_check (struct merged_iter_pqueue pq) +static void merged_iter_pqueue_check (struct merged_iter_pqueue pq) {for (size_t i =1 ; i < pq.len; i++) {size_t parent = (i -1 ) /2 ;
Signature · 1 line
2.45.2.404.g9eaef5822c
PATCH v4 5/7 t-reftable-pq: make merged_iter_pqueue_check() callable by reference
In reply to Chandra Pratapmerged_iter_pqueue_check() checks the validity of a priority queue represented by a merged_iter_pqueue struct by asserting the parent-child relation in the struct's heap. Explicity passing a struct to this function means a copy of the entire struct is created, which is inefficient.
Make the function accept a pointer to the struct instead. This is safe to do since the function doesn't modify the struct in any way. Make the function parameter 'const' to assert immutability.
--- t/unit-tests/t-reftable-pq.c | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-)
t/unit-tests/t-reftable-pq.c +5 -5
@@ -10,11 +10,11 @@ license that can be found in the LICENSE file or at#include "reftable/constants.h" #include "reftable/pq.h" -static void merged_iter_pqueue_check (struct merged_iter_pqueue pq) +static void merged_iter_pqueue_check (const struct merged_iter_pqueue *pq) { -for (size_t i =1 ; i < pq.len; i++) { +for (size_t i =1 ; i < pq->len; i++) {size_t parent = (i -1 ) /2 ; -check (pq_less (&pq.heap[parent], &pq.heap[i])); +check (pq_less (&pq->heap[parent], &pq->heap[i])); } }
@@ -40,13 +40,13 @@ static void test_pq(void) };merged_iter_pqueue_add (&pq, &e); -merged_iter_pqueue_check (pq); +merged_iter_pqueue_check (&pq); i = (i *7 ) %N ; }while (i !=1 );while (!merged_iter_pqueue_is_empty (pq)) {struct pq_entry e =merged_iter_pqueue_remove (&pq); -merged_iter_pqueue_check (pq); +merged_iter_pqueue_check (&pq);check (reftable_record_type (e.rec) ==BLOCK_TYPE_REF );if (last)
Signature · 1 line
2.45.2.404.g9eaef5822c
PATCH v4 6/7 t-reftable-pq: add test for index based comparison
In reply to Chandra PratapWhen 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.
--- t/unit-tests/t-reftable-pq.c | 43 ++++++++++++++++++++++++++++++++++-- 1 file changed, 41 insertions(+), 2 deletions(-)
t/unit-tests/t-reftable-pq.c +41 -2
@@ -18,7 +18,7 @@ static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq) } } -static void test_pq (void ) +static void test_pq_record (void ) {struct merged_iter_pqueue pq = {0 };struct reftable_record recs[54 ];
@@ -59,9 +59,48 @@ static void test_pq(void)merged_iter_pqueue_release (&pq); } +static void test_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 (test_pq (),"pq works" ); +TEST (test_pq_record (),"pq works with record-based comparison" ); +TEST (test_pq_index (),"pq works with index-based comparison" );return test_done (); }
Signature · 1 line
2.45.2.404.g9eaef5822c
PATCH v4 7/7 t-reftable-pq: add tests for merged_iter_pqueue_top()
In reply to Chandra Pratapmerged_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.
--- t/unit-tests/t-reftable-pq.c | 49 ++++++++++++++++++++++++++++++++++++ 1 file changed, 49 insertions(+)
t/unit-tests/t-reftable-pq.c +49 -0
@@ -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 test_pq_record (void ) {struct merged_iter_pqueue pq = {0 };
@@ -45,9 +50,11 @@ static void test_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);
@@ -82,9 +89,11 @@ static void test_pq_index(void) }for (i =N -1 ; !merged_iter_pqueue_is_empty (pq); 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)
@@ -97,10 +106,50 @@ static void test_pq_index(void)merged_iter_pqueue_release (&pq); } +static void test_merged_iter_pqueue_top (void ) +{ +struct merged_iter_pqueue pq = {0 }; +struct reftable_record recs[14 ]; +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 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); + } + } + +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 (test_pq_record (),"pq works with record-based comparison" );TEST (test_pq_index (),"pq works with index-based comparison" ); +TEST (test_merged_iter_pqueue_top (),"merged_iter_pqueue_top works" );return test_done (); }
Signature · 1 line
2.45.2.404.g9eaef5822c
Re: [GSoC][PATCH v4 0/7] t: port reftable/pq_test.c to the unit testing framework
In reply to Chandra PratapQuoted 16 lines · Chandra Pratap
In the recent codebase update (commit 8bf6fbd, 2023-12-09), a new unit testing framework written entirely in C was introduced to the Git project aimed at simplifying testing and reducing test run times. Currently, tests for the reftable refs-backend are performed by a custom testing framework defined by reftable/test_framework.{c, h}. Port
reftable/pq_test.cto the unit testing framework and improve upon the ported test.The first two patches in the series are preparatory cleanup, the third patch moves the test to the unit testing framework, and the rest of the patches improve upon the ported test.
Mentored-by Patrick Steinhardt <[email protected]>Mentored-by Christian Couder <[email protected]>Signed-off-by Chandra Pratap <[email protected]>
Quoted 5 lines
---
Changes in v4:
- Add a commit message for the second patchCI/PR for v4: https://github.com/gitgitgadget/git/pull/1745
Hmph.
A larger question is how pristine we want to keep the "imported source" that is reftable/* stuff.
Obviously we are getting rid of some parts of it (like pq_test.c here) so our "fork" will no longer be usable, without pulling some of the stuff our project offers from outside that directory, by outside people. This concern is shared with other topics we saw recently to move the unit tests bundled with the reftable library to t/unit-tests/.
But this series brings in another twist that makes it a larger question. If we are willing to butcher our copy of reftable library to a shape that cannot be reused by outside folks, do we still want to use reftable/pq.c instead of getting rid of it and use the other prio queue implementation we use elsewhere in our system? If that will be the longer term direction we want to go, then porting the unit tests for reftable/pq.c may end up being a wasted effort.
So, I dunno.
Quoted 37 lines
Chandra Pratap(7):
reftable: remove unncessary curly braces inreftable/pq.c
reftable: change the type of array indices to 'size_t' in
t: movereftable/pq_test.cto the unit testing framework
t-reftable-pq: makemerged_iter_pqueue_check()static
t-reftable-pq: makemerged_iter_pqueue_check()callable
t-reftable-pq: add test for index based comparison
t-reftable-pq: add tests formerged_iter_pqueue_top()Makefile | 2 +- reftable/pq.c | 29 +++-------- reftable/pq.h | 1 - reftable/pq_test.c | 74 ---------------------------- t/helper/test-reftable.c | 1 - t/unit-tests/t-reftable-pq.c | 155 +++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 166 insertions(+), 96 deletions(-)Range-diff against v3:
1:3c333e7770! 1:1873fb02cereftable: change the type of array indices to 'size_t' inreftable/pq.c
@@ Metadata
## Commit message ##
reftable: change the type of array indices to 'size_t' inreftable/pq.c+ The variables 'i', 'j', 'k' and 'min' are used as indices for
+ 'pq->heap', which is an array. Additionally, 'pq->len' is of
+ type 'size_t' and is often used to assign values to these
+ variables. Hence, change the type of these variables from 'int'
+ to 'size_t'.
+Mentored-by Patrick Steinhardt <[email protected]>Mentored-by Christian Couder <[email protected]>Signed-off-by Chandra Pratap <[email protected]>2: bf547f705a = 2: 3cccf8266a t: move reftable/pq_test.c to the unit testing framework 3: 7dd3a2b27f = 3: 4b63849694 t-reftable-pq: make merged_iter_pqueue_check() static 4: c803e7adfc = 4: 3698a7189f t-reftable-pq: make merged_iter_pqueue_check() callable by reference 5: 0b03f3567d = 5: d58c8f709e t-reftable-pq: add test for index based comparison 6: 0cdfa6221e = 6: 69521f0ff7 t-reftable-pq: add tests for merged_iter_pqueue_top()
v5 cover t: port reftable/pq_test.c to the unit testing framework
In reply to Chandra PratapThe reftable library comes with self tests, which are exercised as part of the usual end-to-end tests and are designed to observe the end-user visible effects of Git commands. What it exercises, however, is a better match for the unit-testing framework, merged at 8bf6fbd0 (Merge branch 'js/doc-unit-tests', 2023-12-09), which is designed to observe how low level implementation details, at the level of sequences of individual function calls, behave.
Hence, port reftable/pq_test.c to the unit testing framework and improve upon the ported test. The first two patches in the series are preparatory cleanup, the third patch moves the test to the unit testing framework, and the rest of the patches improve upon the ported test.
---
Changes in v5:
- Rebase the branch on top of the latest master branch
- Rename tests according to unit-tests' conventions
- remove 'pq_test_main()' from reftable/reftable-test.h
CI/PR for v5: https://github.com/gitgitgadget/git/pull/1745
Chandra Pratap(7):
reftable: remove unncessary curly braces in reftable/pq.c
reftable: change the type of array indices to 'size_t' in reftable/pq.c
t: move reftable/pq_test.c to the unit testing framework
t-reftable-pq: make merged_iter_pqueue_check() static
t-reftable-pq: make merged_iter_pqueue_check() callable by reference
t-reftable-pq: add test for index based comparison
t-reftable-pq: add tests for merged_iter_pqueue_top()
Makefile | 2 +- reftable/pq.c | 29 +++----- reftable/pq.h | 1 - reftable/pq_test.c | 74 --------------------- reftable/reftable-tests.h | 1 - t/helper/test-reftable.c | 1 - t/unit-tests/t-reftable-pq.c | 155 +++++++++++++++++++++++++++++++++++++++++++ 7 files changed, 166 insertions(+), 97 deletions(-)
Range-diff against v4:
<rebase commits>
1: d3c5605ea2 = 382: acd9d26aaf reftable: remove unncessary curly braces in reftable/pq.c 2: 3c333e7770 = 383: 2e0986207b reftable: change the type of array indices to 'size_t' in reftable/pq.c 3: bf547f705a ! 384: df06b6d604 t: move reftable/pq_test.c to the unit testing framework
@@ Commit message
t: move reftable/pq_test.c to the unit testing framework
reftable/pq_test.c exercises a priority queue defined by
- reftable/pq.{c, h}. Migrate reftable/pq_test.c to the unit
- testing framework. Migration involves refactoring the tests
- to use the unit testing framework instead of reftable's test
- framework.
+ reftable/pq.{c, h}. Migrate reftable/pq_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.
## Makefile ##
-@@ Makefile: THIRD_PARTY_SOURCES += sha1dc/%
- UNIT_TEST_PROGRAMS += t-ctype
- UNIT_TEST_PROGRAMS += t-mem-pool
+@@ Makefile: UNIT_TEST_PROGRAMS += t-oidmap
+ UNIT_TEST_PROGRAMS += t-oidtree
UNIT_TEST_PROGRAMS += t-prio-queue
+ UNIT_TEST_PROGRAMS += t-reftable-basics
+UNIT_TEST_PROGRAMS += t-reftable-pq
+ UNIT_TEST_PROGRAMS += t-reftable-record
UNIT_TEST_PROGRAMS += t-strbuf
UNIT_TEST_PROGRAMS += t-strcmp-offset
- UNIT_TEST_PROGRAMS += t-trailer
-@@ Makefile: REFTABLE_TEST_OBJS += reftable/basics_test.o
+@@ Makefile: REFTABLE_OBJS += reftable/writer.o
REFTABLE_TEST_OBJS += reftable/block_test.o
REFTABLE_TEST_OBJS += reftable/dump.o
REFTABLE_TEST_OBJS += reftable/merged_test.o
-REFTABLE_TEST_OBJS += reftable/pq_test.o
- 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/reftable-tests.h ##
+@@ reftable/reftable-tests.h: license that can be found in the LICENSE file or at
+ int basics_test_main(int argc, const char **argv);
+ int block_test_main(int argc, const char **argv);
+ int merged_test_main(int argc, const char **argv);
+-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);
## t/helper/test-reftable.c ##
@@ t/helper/test-reftable.c: int cmd__reftable(int argc, const char **argv)
- record_test_main(argc, argv);
+ /* test from simple to complex. */
block_test_main(argc, argv);
tree_test_main(argc, argv);
- pq_test_main(argc, argv);
@@ t/unit-tests/t-reftable-pq.c: license that can be found in the LICENSE file or a
}
}
- static void test_pq(void)
+-static void test_pq(void)
++static void t_pq(void)
{
- struct merged_iter_pqueue pq = { NULL };
+ struct merged_iter_pqueue pq = { 0 };
@@ t/unit-tests/t-reftable-pq.c: static void test_pq(void)
{
- RUN_TEST(test_pq);
- return 0;
-+ TEST(test_pq(), "pq works");
++ TEST(t_pq(), "pq works");
+
+ return test_done();
}
4: 7dd3a2b27f = 385: 40745ab18e t-reftable-pq: make merged_iter_pqueue_check() static
5: c803e7adfc ! 386: ee8432ac4a t-reftable-pq: make merged_iter_pqueue_check() callable by reference
@@ t/unit-tests/t-reftable-pq.c: license that can be found in the LICENSE file or a
}
}
-@@ t/unit-tests/t-reftable-pq.c: static void test_pq(void)
+@@ t/unit-tests/t-reftable-pq.c: static void t_pq(void)
};
merged_iter_pqueue_add(&pq, &e);
6: 0b03f3567d ! 387: 94a77f5a60 t-reftable-pq: add test for index based comparison
@@ t/unit-tests/t-reftable-pq.c: static void merged_iter_pqueue_check(const struct
}
}
--static void test_pq(void)
-+static void test_pq_record(void)
+-static void t_pq(void)
++static void t_pq_record(void)
{
struct merged_iter_pqueue pq = { 0 };
struct reftable_record recs[54];
-@@ t/unit-tests/t-reftable-pq.c: static void test_pq(void)
+@@ t/unit-tests/t-reftable-pq.c: static void t_pq(void)
merged_iter_pqueue_release(&pq);
}
-+static void test_pq_index(void)
++static void t_pq_index(void)
+{
+ struct merged_iter_pqueue pq = { 0 };
+ struct reftable_record recs[14];
@@ t/unit-tests/t-reftable-pq.c: static void test_pq(void)
+
int cmd_main(int argc, const char *argv[])
{
-- TEST(test_pq(), "pq works");
-+ TEST(test_pq_record(), "pq works with record-based comparison");
-+ TEST(test_pq_index(), "pq works with index-based comparison");
+- 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();
}
7: 0cdfa6221e ! 388: 9a76f87bd1 t-reftable-pq: add tests for merged_iter_pqueue_top()
@@ t/unit-tests/t-reftable-pq.c: static void merged_iter_pqueue_check(const struct
+ return !reftable_record_cmp(a->rec, b->rec) && (a->index == b->index);
+}
+
- static void test_pq_record(void)
+ static void t_pq_record(void)
{
struct merged_iter_pqueue pq = { 0 };
-@@ t/unit-tests/t-reftable-pq.c: static void test_pq_record(void)
+@@ t/unit-tests/t-reftable-pq.c: static void t_pq_record(void)
} while (i != 1);
while (!merged_iter_pqueue_is_empty(pq)) {
@@ t/unit-tests/t-reftable-pq.c: static void test_pq_record(void)
check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
if (last)
check_int(strcmp(last, e.rec->u.ref.refname), <, 0);
-@@ t/unit-tests/t-reftable-pq.c: static void test_pq_index(void)
+@@ t/unit-tests/t-reftable-pq.c: static void t_pq_index(void)
}
for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) {
@@ t/unit-tests/t-reftable-pq.c: static void test_pq_index(void)
check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
check_int(e.index, ==, i);
if (last)
-@@ t/unit-tests/t-reftable-pq.c: static void test_pq_index(void)
+@@ t/unit-tests/t-reftable-pq.c: static void t_pq_index(void)
merged_iter_pqueue_release(&pq);
}
-+static void test_merged_iter_pqueue_top(void)
++static void t_merged_iter_pqueue_top(void)
+{
+ struct merged_iter_pqueue pq = { 0 };
+ struct reftable_record recs[14];
@@ t/unit-tests/t-reftable-pq.c: static void test_pq_index(void)
+
int cmd_main(int argc, const char *argv[])
{
- TEST(test_pq_record(), "pq works with record-based comparison");
- TEST(test_pq_index(), "pq works with index-based comparison");
-+ TEST(test_merged_iter_pqueue_top(), "merged_iter_pqueue_top works");
+ 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();
}PATCH v5 1/7 reftable: remove unncessary curly braces in reftable/pq.c
According to Documentation/CodingGuidelines, control-flow statements with a single line as their body must omit curly braces. Make reftable/pq.c conform to this guideline. Besides that, remove unnecessary newlines and variable assignment.
--- reftable/pq.c | 17 ++++------------- 1 file changed, 4 insertions(+), 13 deletions(-)
reftable/pq.c +4 -13
@@ -27,22 +27,16 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq) pq->heap[0 ] = pq->heap[pq->len -1 ]; pq->len--; - i =0 ;while (i < pq->len) {int min = i;int j =2 * i +1 ;int k =2 * i +2 ; -if (j < pq->len &&pq_less (&pq->heap[j], &pq->heap[i])) { +if (j < pq->len &&pq_less (&pq->heap[j], &pq->heap[i])) min = j; - } -if (k < pq->len &&pq_less (&pq->heap[k], &pq->heap[min])) { +if (k < pq->len &&pq_less (&pq->heap[k], &pq->heap[min])) min = k; - } - -if (min == i) { +if (min == i)break ; - } -SWAP (pq->heap[i], pq->heap[min]); i = min; }
@@ -60,12 +54,9 @@ void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry i = pq->len -1 ;while (i >0 ) {int j = (i -1 ) /2 ; -if (pq_less (&pq->heap[j], &pq->heap[i])) { +if (pq_less (&pq->heap[j], &pq->heap[i]))break ; - } -SWAP (pq->heap[j], pq->heap[i]); - i = j; } }
Signature · 1 line
2.45.GIT
PATCH v5 2/7 reftable: change the type of array indices to 'size_t' in reftable/pq.c
In reply to Chandra PratapThe variables 'i', 'j', 'k' and 'min' are used as indices for 'pq->heap', which is an array. Additionally, 'pq->len' is of type 'size_t' and is often used to assign values to these variables. Hence, change the type of these variables from 'int' to 'size_t'.
--- reftable/pq.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-)
reftable/pq.c +6 -6
@@ -22,15 +22,15 @@ int pq_less(struct pq_entry *a, struct pq_entry *b)struct pq_entry merged_iter_pqueue_remove (struct merged_iter_pqueue *pq) { -int i =0 ; +size_t i =0 ;struct pq_entry e = pq->heap[0 ]; pq->heap[0 ] = pq->heap[pq->len -1 ]; pq->len--;while (i < pq->len) { -int min = i; -int j =2 * i +1 ; -int k =2 * i +2 ; +size_t min = i; +size_t j =2 * i +1 ; +size_t k =2 * i +2 ;if (j < pq->len &&pq_less (&pq->heap[j], &pq->heap[i])) min = j;if (k < pq->len &&pq_less (&pq->heap[k], &pq->heap[min]))
@@ -46,14 +46,14 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)void merged_iter_pqueue_add (struct merged_iter_pqueue *pq,const struct pq_entry *e) { -int i =0 ; +size_t i =0 ;REFTABLE_ALLOC_GROW (pq->heap, pq->len +1 , pq->cap); pq->heap[pq->len++] = *e; i = pq->len -1 ;while (i >0 ) { -int j = (i -1 ) /2 ; +size_t j = (i -1 ) /2 ;if (pq_less (&pq->heap[j], &pq->heap[i]))break ;SWAP (pq->heap[j], pq->heap[i]);
Signature · 1 line
2.45.GIT
PATCH v5 3/7 t: move reftable/pq_test.c to the unit testing framework
In reply to Chandra Pratapreftable/pq_test.c exercises a priority queue defined by reftable/pq.{c, h}. Migrate reftable/pq_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.
--- Makefile | 2 +- reftable/reftable-tests.h | 1 - t/helper/test-reftable.c | 1 - .../pq_test.c => t/unit-tests/t-reftable-pq.c | 39 ++++++++----------- 4 files changed, 17 insertions(+), 26 deletions(-) rename reftable/pq_test.c => t/unit-tests/t-reftable-pq.c (61%)
Makefile +1 -1
@@ -1340,6 +1340,7 @@ UNIT_TEST_PROGRAMS += t-oidmap UNIT_TEST_PROGRAMS += t-oidtree UNIT_TEST_PROGRAMS += t-prio-queue UNIT_TEST_PROGRAMS += t-reftable-basics +UNIT_TEST_PROGRAMS += t-reftable-pq UNIT_TEST_PROGRAMS += t-reftable-record UNIT_TEST_PROGRAMS += t-strbuf UNIT_TEST_PROGRAMS += t-strcmp-offset
@@ -2681,7 +2682,6 @@ REFTABLE_OBJS += reftable/writer.o REFTABLE_TEST_OBJS += reftable/block_test.o REFTABLE_TEST_OBJS += reftable/dump.o REFTABLE_TEST_OBJS += reftable/merged_test.o -REFTABLE_TEST_OBJS += reftable/pq_test.o REFTABLE_TEST_OBJS += reftable/readwrite_test.o REFTABLE_TEST_OBJS += reftable/stack_test.o REFTABLE_TEST_OBJS += reftable/test_framework.o
reftable/reftable-tests.h +0 -1
@@ -12,7 +12,6 @@ license that can be found in the LICENSE file or atint basics_test_main (int argc,const char **argv);int block_test_main (int argc,const char **argv);int merged_test_main (int argc,const char **argv); -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);
t/helper/test-reftable.c +0 -1
@@ -7,7 +7,6 @@ int cmd__reftable(int argc, const char **argv)/* test from simple to complex. */ 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);stack_test_main (argc, argv);
t/unit-tests/t-reftable-pq.c renamed from reftable/pq_test.c +16 -23
@@ -6,35 +6,28 @@ license that can be found in the LICENSE file or athttps://developers.google.com/open-source/licenses/bsd */ -#include "system.h" - -#include "basics.h" -#include "constants.h" -#include "pq.h" -#include "record.h" -#include "reftable-tests.h" -#include "test_framework.h" +#include "test-lib.h" +#include "reftable/constants.h" +#include "reftable/pq.h" void merged_iter_pqueue_check (struct merged_iter_pqueue pq) { -int i; -for (i =1 ; i < pq.len; i++) { -int parent = (i -1 ) /2 ; - -EXPECT (pq_less (&pq.heap[parent], &pq.heap[i])); +for (size_t i =1 ; i < pq.len; i++) { +size_t parent = (i -1 ) /2 ; +check (pq_less (&pq.heap[parent], &pq.heap[i])); } } -static void test_pq (void ) +static void t_pq (void ) { -struct merged_iter_pqueue pq = {NULL }; +struct merged_iter_pqueue pq = {0 };struct reftable_record recs[54 ]; -int N =ARRAY_SIZE (recs) -1 , i; +size_t N =ARRAY_SIZE (recs) -1 , i;char *last =NULL ;for (i =0 ; i <N ; i++) {struct strbuf refname =STRBUF_INIT ; -strbuf_addf (&refname,"%02d" , i); +strbuf_addf (&refname,"%02" PRIuMAX, (uintmax_t )i);reftable_record_init (&recs[i],BLOCK_TYPE_REF ); recs[i].u.ref.refname =strbuf_detach (&refname,NULL );
@@ -48,7 +41,6 @@ static void test_pq(void)merged_iter_pqueue_add (&pq, &e);merged_iter_pqueue_check (pq); - i = (i *7 ) %N ; }while (i !=1 );
@@ -56,9 +48,9 @@ static void test_pq(void)struct pq_entry e =merged_iter_pqueue_remove (&pq);merged_iter_pqueue_check (pq); -EXPECT (reftable_record_type (e.rec) ==BLOCK_TYPE_REF ); +check (reftable_record_type (e.rec) ==BLOCK_TYPE_REF );if (last) -EXPECT (strcmp (last, e.rec->u.ref.refname) <0 ); + check_int(strcmp(last, e.rec->u.ref.refname), <, 0); last = e.rec->u.ref.refname; }
@@ -67,8 +59,9 @@ static void test_pq(void)merged_iter_pqueue_release (&pq); } -int pq_test_main (int argc,const char *argv[]) +int cmd_main (int argc,const char *argv[]) { -RUN_TEST (test_pq); -return 0 ; +TEST (t_pq (),"pq works" ); + +return test_done (); }
Signature · 1 line
2.45.GIT
PATCH v5 4/7 t-reftable-pq: make merged_iter_pqueue_check() static
In reply to Chandra Pratapmerged_iter_pqueue_check() is a function previously defined in reftable/pq_test.c (now t/unit-tests/t-reftable-pq.c) and used in the testing of a priority queue as defined by reftable/pq.{c, h}. As such, this function is only called by reftable/pq_test.c and it makes little sense to expose it to non-testing code via reftable/pq.h.
Hence, make this function static and remove its prototype from reftable/pq.h.
--- reftable/pq.h | 1 - t/unit-tests/t-reftable-pq.c | 2 +- 2 files changed, 1 insertion(+), 2 deletions(-)
reftable/pq.h +0 -1
@@ -22,7 +22,6 @@ struct merged_iter_pqueue {size_t cap; }; -void merged_iter_pqueue_check (struct merged_iter_pqueue pq);struct pq_entry merged_iter_pqueue_remove (struct merged_iter_pqueue *pq);void merged_iter_pqueue_add (struct merged_iter_pqueue *pq,const struct pq_entry *e);void merged_iter_pqueue_release (struct merged_iter_pqueue *pq);
t/unit-tests/t-reftable-pq.c +1 -1
@@ -10,7 +10,7 @@ license that can be found in the LICENSE file or at#include "reftable/constants.h" #include "reftable/pq.h" -void merged_iter_pqueue_check (struct merged_iter_pqueue pq) +static void merged_iter_pqueue_check (struct merged_iter_pqueue pq) {for (size_t i =1 ; i < pq.len; i++) {size_t parent = (i -1 ) /2 ;
Signature · 1 line
2.45.GIT
PATCH v5 5/7 t-reftable-pq: make merged_iter_pqueue_check() callable by reference
In reply to Chandra Pratapmerged_iter_pqueue_check() checks the validity of a priority queue represented by a merged_iter_pqueue struct by asserting the parent-child relation in the struct's heap. Explicity passing a struct to this function means a copy of the entire struct is created, which is inefficient.
Make the function accept a pointer to the struct instead. This is safe to do since the function doesn't modify the struct in any way. Make the function parameter 'const' to assert immutability.
--- t/unit-tests/t-reftable-pq.c | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-)
t/unit-tests/t-reftable-pq.c +5 -5
@@ -10,11 +10,11 @@ license that can be found in the LICENSE file or at#include "reftable/constants.h" #include "reftable/pq.h" -static void merged_iter_pqueue_check (struct merged_iter_pqueue pq) +static void merged_iter_pqueue_check (const struct merged_iter_pqueue *pq) { -for (size_t i =1 ; i < pq.len; i++) { +for (size_t i =1 ; i < pq->len; i++) {size_t parent = (i -1 ) /2 ; -check (pq_less (&pq.heap[parent], &pq.heap[i])); +check (pq_less (&pq->heap[parent], &pq->heap[i])); } }
@@ -40,13 +40,13 @@ static void t_pq(void) };merged_iter_pqueue_add (&pq, &e); -merged_iter_pqueue_check (pq); +merged_iter_pqueue_check (&pq); i = (i *7 ) %N ; }while (i !=1 );while (!merged_iter_pqueue_is_empty (pq)) {struct pq_entry e =merged_iter_pqueue_remove (&pq); -merged_iter_pqueue_check (pq); +merged_iter_pqueue_check (&pq);check (reftable_record_type (e.rec) ==BLOCK_TYPE_REF );if (last)
Signature · 1 line
2.45.GIT
PATCH v5 6/7 t-reftable-pq: add test for index based comparison
In reply to Chandra PratapWhen 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.
--- t/unit-tests/t-reftable-pq.c | 43 ++++++++++++++++++++++++++++++++++-- 1 file changed, 41 insertions(+), 2 deletions(-)
t/unit-tests/t-reftable-pq.c +41 -2
@@ -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 (); }
Signature · 1 line
2.45.GIT
Re: [PATCH v5 6/7] t-reftable-pq: add test for index based comparison
Quoted 28 lines · Chandra Pratap
t/unit-tests/t-reftable-pq.c +12
-1@@ -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" ); + }
t/unit-tests/t-reftable-pq.c static void t_pq(void) · line 82
Quoted 10 lines
t/unit-tests/t-reftable-pq.c +10
-0+ +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
Re: [PATCH v5 6/7] t-reftable-pq: add test for index based comparison
Quoted 4 lines · Patrick Steinhardt
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.
Re: [PATCH v5 6/7] t-reftable-pq: add test for index based comparison
Quoted 7 lines · Junio C Hamano
Quoted 4 lines · Patrick Steinhardt
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.
Quoted 8 lines
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
PATCH v5 7/7 t-reftable-pq: add tests for merged_iter_pqueue_top()
In reply to Chandra Pratapmerged_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.
--- t/unit-tests/t-reftable-pq.c | 49 ++++++++++++++++++++++++++++++++++++ 1 file changed, 49 insertions(+)
t/unit-tests/t-reftable-pq.c +49 -0
@@ -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 };
@@ -45,9 +50,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);
@@ -82,9 +89,11 @@ static void t_pq_index(void) }for (i =N -1 ; !merged_iter_pqueue_is_empty (pq); 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)
@@ -97,10 +106,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[14 ]; +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 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); + } + } + +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_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 (); }
Signature · 1 line
2.45.GIT
Re: [GSoC][PATCH v5 0/7] t: port reftable/pq_test.c to the unit testing framework
In reply to Chandra PratapQuoted 15 lines · Chandra Pratap
The reftable library comes with self tests, which are exercised as part of the usual end-to-end tests and are designed to observe the end-user visible effects of Git commands. What it exercises, however, is a better match for the unit-testing framework, merged at
8bf6fbd0(Merge branch 'js/doc-unit-tests', 2023-12-09), which is designed to observe how low level implementation details, at the level of sequences of individual function calls, behave.Hence, port
reftable/pq_test.cto the unit testing framework and improve upon the ported test. The first two patches in the series are preparatory cleanup, the third patch moves the test to the unit testing framework, and the rest of the patches improve upon the ported test.
Quoted 7 lines
Mentored-by Patrick Steinhardt <[email protected]>Mentored-by Christian Couder <[email protected]>Signed-off-by Chandra Pratap <[email protected]>---
Changes in v5:
- Rebase the branch on top of the latest master branch
If you need to perform this rebase, please say _why_ you are rebasing.
"A new rc was tagged so I rebased" is *not* a good reason.
"I wanted to use that new feature that was merged to 'master' recently, which was not available when I wrote the previous iteration of this series, hence I rebased" is a very good reason.
"Since I wrote the previous iteration, other unit test topics have graduated, so there are trivial conflicts in Makefile when merging this topic" is usually not a good reason, especially when the same conflicts with these other unit test topics are already resolved when your previous iteration is merged to 'seen'.
If there isn't a reason worth mentioning why you are rebasing, then please do not rebase. It is distracting.
Quoted 4 lines
- Rename tests according to unit-tests' conventions
- remove 'pq_test_main()' fromreftable/reftable-test.hCI/PR for v5: https://github.com/gitgitgadget/git/pull/1745
By the way, I still haven't got any answer to a question I asked long ago on this series, wrt possibly unifying this pq and another pq we already use elsewhere in our codebase. If we are butchering what we borrowed from elsewhere and store in reftable/. directory and taking responsibility of maintaining it ourselves, we probably should consider larger refactoring and cleaning up, and part of it we may end up discarding this pq implementation, making the unit testing on it a wasted effort.
Thanks.
Quoted 196 lines
Chandra Pratap(7):
reftable: remove unncessary curly braces inreftable/pq.c
reftable: change the type of array indices to 'size_t' inreftable/pq.c
t: movereftable/pq_test.cto the unit testing framework
t-reftable-pq: makemerged_iter_pqueue_check()static
t-reftable-pq: makemerged_iter_pqueue_check()callable by reference
t-reftable-pq: add test for index based comparison
t-reftable-pq: add tests formerged_iter_pqueue_top()Makefile | 2 +- reftable/pq.c | 29 +++----- reftable/pq.h | 1 - reftable/pq_test.c | 74 --------------------- reftable/reftable-tests.h | 1 - t/helper/test-reftable.c | 1 - t/unit-tests/t-reftable-pq.c | 155 +++++++++++++++++++++++++++++++++++++++++++ 7 files changed, 166 insertions(+), 97 deletions(-)Range-diff against v4:
<rebase commits>1: d3c5605ea2 = 382: acd9d26aaf reftable: remove unncessary curly braces in reftable/pq.c 2: 3c333e7770 = 383: 2e0986207b reftable: change the type of array indices to 'size_t' in reftable/pq.c 3: bf547f705a ! 384: df06b6d604 t: move reftable/pq_test.c to the unit testing framework@@ Commit message
t: movereftable/pq_test.cto the unit testing framework
reftable/pq_test.cexercises a priority queue defined by
- reftable/pq.{c, h}. Migratereftable/pq_test.cto the unit
- testing framework. Migration involves refactoring the tests
- to use the unit testing framework instead of reftable's test
- framework.
+ reftable/pq.{c, h}. Migratereftable/pq_test.cto 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 <[email protected]>Mentored-by Christian Couder <[email protected]>Signed-off-by Chandra Pratap <[email protected]>##
Makefile##
-@@Makefile:THIRD_PARTY_SOURCES+= sha1dc/%
-UNIT_TEST_PROGRAMS+= t-ctype
-UNIT_TEST_PROGRAMS+= t-mem-pool
+@@Makefile:UNIT_TEST_PROGRAMS+= t-oidmap
+UNIT_TEST_PROGRAMS+= t-oidtree
UNIT_TEST_PROGRAMS+= t-prio-queue
+UNIT_TEST_PROGRAMS+= t-reftable-basics
+UNIT_TEST_PROGRAMS += t-reftable-pq
+UNIT_TEST_PROGRAMS+= t-reftable-record
UNIT_TEST_PROGRAMS+= t-strbuf
UNIT_TEST_PROGRAMS+= t-strcmp-offset
-UNIT_TEST_PROGRAMS+= t-trailer
-@@Makefile:REFTABLE_TEST_OBJS+=reftable/basics_test.o
+@@Makefile:REFTABLE_OBJS+=reftable/writer.o
REFTABLE_TEST_OBJS+=reftable/block_test.o
REFTABLE_TEST_OBJS+=reftable/dump.o
REFTABLE_TEST_OBJS+=reftable/merged_test.o
-REFTABLE_TEST_OBJS +=reftable/pq_test.o
-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/reftable-tests.h##
+@@reftable/reftable-tests.h: license that can be found in the LICENSE file or at
+ intbasics_test_main(int argc, const char **argv);
+ intblock_test_main(int argc, const char **argv);
+ intmerged_test_main(int argc, const char **argv);
+-intpq_test_main(int argc, const char **argv);
+ intrecord_test_main(int argc, const char **argv);
+ intreadwrite_test_main(int argc, const char **argv);
+ intstack_test_main(int argc, const char **argv);##
t/helper/test-reftable.c##
@@t/helper/test-reftable.c: intcmd__reftable(int argc, const char **argv)
-record_test_main(argc, argv);
+ /* test from simple to complex. */
block_test_main(argc, argv);
tree_test_main(argc, argv);
-pq_test_main(argc, argv);
@@t/unit-tests/t-reftable-pq.c: license that can be found in the LICENSE file or a
}
}- static void
test_pq(void)
+-static voidtest_pq(void)
++static voidt_pq(void)
{
- structmerged_iter_pqueuepq = { NULL };
+ structmerged_iter_pqueuepq = { 0 };
@@t/unit-tests/t-reftable-pq.c: static voidtest_pq(void)
{
-RUN_TEST(test_pq);
- return 0;
-+TEST(test_pq(), "pq works");
++TEST(t_pq(), "pq works");
+
+ returntest_done();
}4: 7dd3a2b27f = 385: 40745ab18e t-reftable-pq: make merged_iter_pqueue_check() static 5: c803e7adfc ! 386: ee8432ac4a t-reftable-pq: make merged_iter_pqueue_check() callable by reference @@ t/unit-tests/t-reftable-pq.c: license that can be found in the LICENSE file or a } } -@@ t/unit-tests/t-reftable-pq.c: static void test_pq(void) +@@ t/unit-tests/t-reftable-pq.c: static void t_pq(void) }; merged_iter_pqueue_add(&pq, &e); 6: 0b03f3567d ! 387: 94a77f5a60 t-reftable-pq: add test for index based comparison @@ t/unit-tests/t-reftable-pq.c: static void merged_iter_pqueue_check(const struct } } --static void test_pq(void) -+static void test_pq_record(void) +-static void t_pq(void) ++static void t_pq_record(void) { struct merged_iter_pqueue pq = { 0 }; struct reftable_record recs[54]; -@@ t/unit-tests/t-reftable-pq.c: static void test_pq(void) +@@ t/unit-tests/t-reftable-pq.c: static void t_pq(void) merged_iter_pqueue_release(&pq); } -+static void test_pq_index(void) ++static void t_pq_index(void) +{ + struct merged_iter_pqueue pq = { 0 }; + struct reftable_record recs[14]; @@ t/unit-tests/t-reftable-pq.c: static void test_pq(void) + int cmd_main(int argc, const char *argv[]) { -- TEST(test_pq(), "pq works"); -+ TEST(test_pq_record(), "pq works with record-based comparison"); -+ TEST(test_pq_index(), "pq works with index-based comparison"); +- 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(); } 7: 0cdfa6221e ! 388: 9a76f87bd1 t-reftable-pq: add tests for merged_iter_pqueue_top() @@ t/unit-tests/t-reftable-pq.c: static void merged_iter_pqueue_check(const struct + return !reftable_record_cmp(a->rec, b->rec) && (a->index == b->index); +} + - static void test_pq_record(void) + static void t_pq_record(void) { struct merged_iter_pqueue pq = { 0 }; -@@ t/unit-tests/t-reftable-pq.c: static void test_pq_record(void) +@@ t/unit-tests/t-reftable-pq.c: static void t_pq_record(void) } while (i != 1); while (!merged_iter_pqueue_is_empty(pq)) { @@ t/unit-tests/t-reftable-pq.c: static void test_pq_record(void) check(reftable_record_type(e.rec) == BLOCK_TYPE_REF); if (last) check_int(strcmp(last, e.rec->u.ref.refname), <, 0); -@@ t/unit-tests/t-reftable-pq.c: static void test_pq_index(void) +@@ t/unit-tests/t-reftable-pq.c: static void t_pq_index(void) } for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) { @@ t/unit-tests/t-reftable-pq.c: static void test_pq_index(void) check(reftable_record_type(e.rec) == BLOCK_TYPE_REF); check_int(e.index, ==, i); if (last) -@@ t/unit-tests/t-reftable-pq.c: static void test_pq_index(void) +@@ t/unit-tests/t-reftable-pq.c: static void t_pq_index(void) merged_iter_pqueue_release(&pq); } -+static void test_merged_iter_pqueue_top(void) ++static void t_merged_iter_pqueue_top(void) +{ + struct merged_iter_pqueue pq = { 0 }; + struct reftable_record recs[14]; @@ t/unit-tests/t-reftable-pq.c: static void test_pq_index(void) + int cmd_main(int argc, const char *argv[]) { - TEST(test_pq_record(), "pq works with record-based comparison"); - TEST(test_pq_index(), "pq works with index-based comparison"); -+ TEST(test_merged_iter_pqueue_top(), "merged_iter_pqueue_top works"); + 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(); }
Re: [GSoC][PATCH v5 0/7] t: port reftable/pq_test.c to the unit testing framework
Quoted 35 lines · Junio C Hamano
Quoted 15 lines · Chandra Pratap
The reftable library comes with self tests, which are exercised as part of the usual end-to-end tests and are designed to observe the end-user visible effects of Git commands. What it exercises, however, is a better match for the unit-testing framework, merged at
8bf6fbd0(Merge branch 'js/doc-unit-tests', 2023-12-09), which is designed to observe how low level implementation details, at the level of sequences of individual function calls, behave.Hence, port
reftable/pq_test.cto the unit testing framework and improve upon the ported test. The first two patches in the series are preparatory cleanup, the third patch moves the test to the unit testing framework, and the rest of the patches improve upon the ported test.Quoted 7 lines
Mentored-by Patrick Steinhardt <[email protected]>Mentored-by Christian Couder <[email protected]>Signed-off-by Chandra Pratap <[email protected]>---
Changes in v5:
- Rebase the branch on top of the latest master branchIf you need to perform this rebase, please say _why_ you are rebasing.
"A new rc was tagged so I rebased" is *not* a good reason.
"I wanted to use that new feature that was merged to 'master' recently, which was not available when I wrote the previous iteration of this series, hence I rebased" is a very good reason.
Quoted 8 lines
"Since I wrote the previous iteration, other unit test topics have graduated, so there are trivial conflicts in
Makefilewhen merging this topic" is usually not a good reason, especially when the same conflicts with these other unit test topics are already resolved when your previous iteration is merged to 'seen'.If there isn't a reason worth mentioning why you are rebasing, then please do not rebase. It is distracting.
Oh, okay.
Quoted 14 lines
Quoted 4 lines
- Rename tests according to unit-tests' conventions
- remove 'pq_test_main()' fromreftable/reftable-test.hCI/PR for v5: https://github.com/gitgitgadget/git/pull/1745
By the way, I still haven't got any answer to a question I asked long ago on this series, wrt possibly unifying this pq and another pq we already use elsewhere in our codebase. If we are butchering what we borrowed from elsewhere and store in reftable/. directory and taking responsibility of maintaining it ourselves, we probably should consider larger refactoring and cleaning up, and part of it we may end up discarding this pq implementation, making the unit testing on it a wasted effort.
Quoted 2 lines
Thanks.
I did talk about this with Patrick and Christian on a private slack channel a few weeks ago and here is how that conversation went:
Me: Hey, I wanted to talk about the message from Junio the other day. It is true that through this project, we are modifying the reftable directory to a point that it is no longer easily usable by someone from outside. If that is the direction we want to take, wouldn't it make more sense to get rid of reftable/pq.{c, h} altogether and use Git's prio-queue instead?
Christian: Yeah, I think the direction the Git project wants to take is to integrate the reftable code more and more with the Git code. On the other hand, there are libification projects which are trying to split parts of the Git code into libraries usable by other projects. But I don't think each of these libraries should have their own test framework, their own prio-queue implementation, their own string implementation, etc. So, even if I am not sure about the end result, I think it would be ok to modify the reftable code so that it uses the Git's prio queue and maybe other Git data structures. But I'd like Patrick to confirm, and the list to agree to this. So I'd rather wait
until Patrick is back from his vacation before doing things like replacing reftable/pq.{c, h} with Git's prio-queue.
Patrick: Just chiming in real quick: while the reftable library is currently in a
position where it cannot be used standalone by other projects, I'd very much like to move into the direction of making it completely standalone again so that we can adapt e.g. libgit2 to use it. So I rather want to move the other direction over time and re-establish a proper boundary between reftable library and the remainder of Git. I don't really think that this needs to impact the reftable tests though. Git is the upstream of the reftable library, and I don't
see much of a point why every other project should carry the same tests, too.
---snip---
Re: [GSoC][PATCH v5 0/7] t: port reftable/pq_test.c to the unit testing framework
Quoted 8 lines · Chandra Pratap
Quoted 5 lines · Junio C Hamano
Quoted 4 lines
- Rename tests according to unit-tests' conventions
- remove 'pq_test_main()' fromreftable/reftable-test.hCI/PR for v5: https://github.com/gitgitgadget/git/pull/1745
Quoted 8 lines
Quoted 8 lines
By the way, I still haven't got any answer to a question I asked long ago on this series, wrt possibly unifying this pq and another pq we already use elsewhere in our codebase. If we are butchering what we borrowed from elsewhere and store in reftable/. directory and taking responsibility of maintaining it ourselves, we probably should consider larger refactoring and cleaning up, and part of it we may end up discarding this pq implementation, making the unit testing on it a wasted effort.
I agree it might have been better to start by replacing the pq implementation in reftable/ with our own first, as there would be no need for this patch series, but Chandra's GSoC is about replacing the unit test framework in reftable/ with our own which is still valuable. And I think that at this point it is just simpler to not get distracted by replacing the pq implementation now. It's also not like changing the unit test framework would make replacing the pq implementation harder.
Quoted 9 lines
I did talk about this with Patrick and Christian on a private slack channel a few weeks ago and here is how that conversation went:
Me: Hey, I wanted to talk about the message from Junio the other day. It is true that through this project, we are modifying the reftable directory to a point that it is no longer easily usable by someone from outside. If that is the direction we want to take, wouldn't it make more sense to get rid of reftable/pq.{c, h} altogether and use Git's prio-queue instead?
Quoted 12 lines
Christian: Yeah, I think the direction the Git project wants to take is to integrate the reftable code more and more with the Git code. On the other hand, there are libification projects which are trying to split parts of the Git code into libraries usable by other projects. But I don't think each of these libraries should have their own test framework, their own prio-queue implementation, their own string implementation, etc. So, even if I am not sure about the end result, I think it would be ok to modify the reftable code so that it uses the Git's prio queue and maybe other Git data structures. But I'd like Patrick to confirm, and the list to agree to this. So I'd rather wait
until Patrick is back from his vacation before doing things like replacing reftable/pq.{c, h} with Git's prio-queue.
Yeah, if it had been discussed and agreed on earlier, I think replacing the pq implementation would have made sense. Now I think it's a bit late at this stage in Chandra's GSoC to go in this direction though. I think it's better if he can focus on finishing to replace the unit test framework.
Re: [GSoC][PATCH v5 0/7] t: port reftable/pq_test.c to the unit testing framework
Quoted 51 lines · Christian Couder
Quoted 8 lines · Chandra Pratap
Quoted 5 lines · Junio C Hamano
Quoted 4 lines
- Rename tests according to unit-tests' conventions
- remove 'pq_test_main()' fromreftable/reftable-test.hCI/PR for v5: https://github.com/gitgitgadget/git/pull/1745
Quoted 8 lines
Quoted 8 lines
By the way, I still haven't got any answer to a question I asked long ago on this series, wrt possibly unifying this pq and another pq we already use elsewhere in our codebase. If we are butchering what we borrowed from elsewhere and store in reftable/. directory and taking responsibility of maintaining it ourselves, we probably should consider larger refactoring and cleaning up, and part of it we may end up discarding this pq implementation, making the unit testing on it a wasted effort.
I agree it might have been better to start by replacing the pq implementation in reftable/ with our own first, as there would be no need for this patch series, but Chandra's GSoC is about replacing the unit test framework in reftable/ with our own which is still valuable. And I think that at this point it is just simpler to not get distracted by replacing the pq implementation now. It's also not like changing the unit test framework would make replacing the pq implementation harder.
Quoted 9 lines
I did talk about this with Patrick and Christian on a private slack channel a few weeks ago and here is how that conversation went:
Me: Hey, I wanted to talk about the message from Junio the other day. It is true that through this project, we are modifying the reftable directory to a point that it is no longer easily usable by someone from outside. If that is the direction we want to take, wouldn't it make more sense to get rid of reftable/pq.{c, h} altogether and use Git's prio-queue instead?
Quoted 12 lines
Christian: Yeah, I think the direction the Git project wants to take is to integrate the reftable code more and more with the Git code. On the other hand, there are libification projects which are trying to split parts of the Git code into libraries usable by other projects. But I don't think each of these libraries should have their own test framework, their own prio-queue implementation, their own string implementation, etc. So, even if I am not sure about the end result, I think it would be ok to modify the reftable code so that it uses the Git's prio queue and maybe other Git data structures. But I'd like Patrick to confirm, and the list to agree to this. So I'd rather wait
until Patrick is back from his vacation before doing things like replacing reftable/pq.{c, h} with Git's prio-queue.
Quoted 5 lines
Yeah, if it had been discussed and agreed on earlier, I think replacing the pq implementation would have made sense. Now I think it's a bit late at this stage in Chandra's GSoC to go in this direction though. I think it's better if he can focus on finishing to replace the unit test framework.
I'm actually more or less done with porting most of the reftable tests to the unit test framework and it shouldn't be long before patches for rest of the tests see the mailing list, so I can definitely make time for other endeavors like these.
The only thing that I think is holding us back from making a change like what Junio suggests is 'how far are we willing to butcher our copy of reftable/?' From what Patrick said earlier, I think the answer to that is 'it is fine to modify reftable/ tests because they don't need to be uniform across all implementations of reftable, but modifying other parts to be more dependent on Git's internals is a no-go.'
Re: [GSoC][PATCH v5 0/7] t: port reftable/pq_test.c to the unit testing framework
In reply to Christian CouderQuoted 25 lines · Christian Couder
Quoted 10 lines · Chandra Pratap
On Tue, 23 Jul 2024 at 22:39, Junio C Hamano <[email protected]> wrote:
I did talk about this with Patrick and Christian on a private slack channel a few weeks ago and here is how that conversation went:Me: Hey, I wanted to talk about the message from Junio the other day. It is true that through this project, we are modifying the reftable directory to a point that it is no longer easily usable by someone from outside. If that is the direction we want to take, wouldn't it make more sense to get rid of reftable/pq.{c, h} altogether and use Git's prio-queue instead?
Quoted 12 lines
Christian: Yeah, I think the direction the Git project wants to take is to integrate the reftable code more and more with the Git code. On the other hand, there are libification projects which are trying to split parts of the Git code into libraries usable by other projects. But I don't think each of these libraries should have their own test framework, their own prio-queue implementation, their own string implementation, etc. So, even if I am not sure about the end result, I think it would be ok to modify the reftable code so that it uses the Git's prio queue and maybe other Git data structures. But I'd like Patrick to confirm, and the list to agree to this. So I'd rather wait
until Patrick is back from his vacation before doing things like replacing reftable/pq.{c, h} with Git's prio-queue.
Quoted 5 lines
Yeah, if it had been discussed and agreed on earlier, I think replacing the pq implementation would have made sense. Now I think it's a bit late at this stage in Chandra's GSoC to go in this direction though. I think it's better if he can focus on finishing to replace the unit test framework.
Replacing the priority queue with the one we already have will create additional work in the future when we want to get the reftable library back into a state where it can be used as a standalone library again. I know that it's currently a mess anyway, but I've heard from multiple folks already who are interested in using the reftable library in their own C projects (most importantly libgit2).
If we want Git to be the reftable upstream for such projects, then we should play nice and not make their lifes harder. I plan to work on portability work as soon as somebody properly commits to integrating reftables into their project. This will probably come in the form of:
- Removing all Git-specific includes in the "reftable/" directory.
- Declaring a list of "shim" functions and types that users of the reftable library need to use.
- Implementing those shim functions for Git.
Of course, those shims will closely follow the interfaces that we have in Git. E.g. there will shims for "strbuf", the tempfile interface, and everything else that we currently use in the reftable library. So ultimately, I expect that the shim implementations will simply look like the following:
```
typedef struct strbuf reftable_buf;
static inline void reftable_buf_add(struct strbuf reftable_buf *buf,
const void *data, size_t len)
{
strbuf_add(buf, data, len);
}
```While we could also shim out the priority queue, I don't really think that it is worth it.
Patrick
Re: [GSoC][PATCH v5 0/7] t: port reftable/pq_test.c to the unit testing framework
Quoted 16 lines · Patrick Steinhardt
Of course, those shims will closely follow the interfaces that we have in Git. E.g. there will shims for "strbuf", the tempfile interface, and everything else that we currently use in the reftable library. So ultimately, I expect that the shim implementations will simply look like the following:
``` typedef struct strbuf reftable_buf; static inline void reftable_buf_add(struct strbuf reftable_buf *buf, const void *data, size_t len) { strbuf_add(buf, data, len); } ```
Quoted 2 lines
While we could also shim out the priority queue, I don't really think that it is worth it.
OK, I am fine if somebody wants to spend cycles to move the reftable_pq tests to the unit-test framework. I just wasn't sure what the future plans were, and one obvious direction to replace reftable_pq would invalidate such work, and I wanted to make sure everybody involved in this effort is aware of that.
Thanks.
v6 cover t: port reftable/pq_test.c to the unit testing framework
In reply to Chandra PratapThe reftable library comes with self tests, which are exercised as part of the usual end-to-end tests and are designed to observe the end-user visible effects of Git commands. What it exercises, however, is a better match for the unit-testing framework, merged at 8bf6fbd0 (Merge branch 'js/doc-unit-tests', 2023-12-09), which is designed to observe how low level implementation details, at the level of sequences of individual function calls, behave.
Hence, port reftable/pq_test.c to the unit testing framework and improve upon the ported test. The first two patches in the series are preparatory cleanup, the third patch moves the test to the unit testing framework, and the rest of the patches improve upon the ported test.
---
Changes in v6:
- Use modulo loop to pseudo-randomly insert elements in t_pq_index() in patch 6.
- Use 'xstrfmt' for refnames instead of using a 'strbuf' in t_pq_record() in patch 6.
- Use string literals instead of 'xstrdup' for refnames in t_pq_index() and t_merged_iter_pqueue_top() in patch 6 & 7.
- Use modulo loop to pseudo-randomly insert elements in t_merged_iter_pqueue_top() in patch 7
CI/PR for v6: https://github.com/gitgitgadget/git/pull/1745
Chandra Pratap(7):
reftable: remove unncessary curly braces in reftable/pq.c
reftable: change the type of array indices to 'size_t' in reftable/pq.c
t: move reftable/pq_test.c to the unit testing framework
t-reftable-pq: make merged_iter_pqueue_check() static
t-reftable-pq: make merged_iter_pqueue_check() callable by reference
t-reftable-pq: add test for index based comparison
t-reftable-pq: add tests for merged_iter_pqueue_top()
Makefile | 2 +- reftable/pq.c | 29 +++----- reftable/pq.h | 1 - reftable/pq_test.c | 74 --------------------- reftable/reftable-tests.h | 1 - t/helper/test-reftable.c | 1 - t/unit-tests/t-reftable-pq.c | 154 +++++++++++++++++++++++++++++++++++++++++++ 7 files changed, 165 insertions(+), 97 deletions(-)
Range-diff against v5:
1: 94a77f5a60 ! 1: f5c30187e1 t-reftable-pq: add test for index based comparison
@@ Commit message
index-based comparison as well. Rename the existing test to
reflect its nature of only testing record-based comparison.
+ While at it, replace 'strbuf_detach' with 'xstrfmt' to assign
+ refnames in the existing test. This makes the test conciser.
+
Mentored-by: Patrick Steinhardt <[email protected]>
Mentored-by: Christian Couder <[email protected]>
Signed-off-by: Chandra Pratap <[email protected]>
@@ t/unit-tests/t-reftable-pq.c: static void merged_iter_pqueue_check(const struct
{
struct merged_iter_pqueue pq = { 0 };
struct reftable_record recs[54];
+@@ t/unit-tests/t-reftable-pq.c: static void t_pq(void)
+ char *last = NULL;
+
+ for (i = 0; i < N; i++) {
+- struct strbuf refname = STRBUF_INIT;
+- strbuf_addf(&refname, "%02"PRIuMAX, (uintmax_t)i);
+-
+ reftable_record_init(&recs[i], BLOCK_TYPE_REF);
+- recs[i].u.ref.refname = strbuf_detach(&refname, NULL);
++ recs[i].u.ref.refname = xstrfmt("%02"PRIuMAX, (uintmax_t)i);
+ }
+
+ i = 1;
@@ t/unit-tests/t-reftable-pq.c: static void t_pq(void)
merged_iter_pqueue_release(&pq);
}
@@ t/unit-tests/t-reftable-pq.c: static void t_pq(void)
+static void t_pq_index(void)
+{
+ struct merged_iter_pqueue pq = { 0 };
-+ struct reftable_record recs[14];
++ struct reftable_record recs[13];
+ 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");
++ recs[i].u.ref.refname = (char *) "refs/heads/master";
+ }
+
-+ for (i = 0; i < N; i++) {
++ i = 1;
++ do {
+ struct pq_entry e = {
+ .rec = &recs[i],
+ .index = i,
@@ t/unit-tests/t-reftable-pq.c: static void t_pq(void)
+
+ merged_iter_pqueue_add(&pq, &e);
+ merged_iter_pqueue_check(&pq);
++ i = (i * 7) % N;
+ }
++ while (i != 1);
+
-+ for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) {
++ for (i = N - 1; i > 0; i--) {
+ struct pq_entry e = merged_iter_pqueue_remove(&pq);
+ merged_iter_pqueue_check(&pq);
+
@@ t/unit-tests/t-reftable-pq.c: static void t_pq(void)
+ last = e.rec->u.ref.refname;
+ }
+
-+ for (i = 0; i < N; i++)
-+ reftable_record_release(&recs[i]);
+ merged_iter_pqueue_release(&pq);
+}
+
2: 9a76f87bd1 ! 2: 394540a789 t-reftable-pq: add tests for merged_iter_pqueue_top()
@@ t/unit-tests/t-reftable-pq.c: static void t_pq_record(void)
if (last)
check_int(strcmp(last, e.rec->u.ref.refname), <, 0);
@@ t/unit-tests/t-reftable-pq.c: static void t_pq_index(void)
- }
+ while (i != 1);
- for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) {
+ 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);
@@ t/unit-tests/t-reftable-pq.c: static void t_pq_index(void)
+static void t_merged_iter_pqueue_top(void)
+{
+ struct merged_iter_pqueue pq = { 0 };
-+ struct reftable_record recs[14];
++ 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 = xstrdup("refs/heads/master");
++ recs[i].u.ref.refname = (char *) "refs/heads/master";
+ }
+
-+ for (i = 0; i < N; i++) {
++ i = 1;
++ do {
+ struct pq_entry e = {
+ .rec = &recs[i],
+ .index = i,
@@ t/unit-tests/t-reftable-pq.c: static void t_pq_index(void)
+
+ merged_iter_pqueue_add(&pq, &e);
+ merged_iter_pqueue_check(&pq);
++ i = (i * 7) % N;
+ }
++ while (i != 1);
+
-+ for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) {
++ 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);
+
@@ t/unit-tests/t-reftable-pq.c: static void t_pq_index(void)
+ }
+ }
+
-+ for (i = 0; i < N; i++)
-+ reftable_record_release(&recs[i]);
+ merged_iter_pqueue_release(&pq);
+}
+PATCH v6 1/7 reftable: remove unncessary curly braces in reftable/pq.c
According to Documentation/CodingGuidelines, control-flow statements with a single line as their body must omit curly braces. Make reftable/pq.c conform to this guideline. Besides that, remove unnecessary newlines and variable assignment.
--- reftable/pq.c | 17 ++++------------- 1 file changed, 4 insertions(+), 13 deletions(-)
reftable/pq.c +4 -13
@@ -27,22 +27,16 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq) pq->heap[0 ] = pq->heap[pq->len -1 ]; pq->len--; - i =0 ;while (i < pq->len) {int min = i;int j =2 * i +1 ;int k =2 * i +2 ; -if (j < pq->len &&pq_less (&pq->heap[j], &pq->heap[i])) { +if (j < pq->len &&pq_less (&pq->heap[j], &pq->heap[i])) min = j; - } -if (k < pq->len &&pq_less (&pq->heap[k], &pq->heap[min])) { +if (k < pq->len &&pq_less (&pq->heap[k], &pq->heap[min])) min = k; - } - -if (min == i) { +if (min == i)break ; - } -SWAP (pq->heap[i], pq->heap[min]); i = min; }
@@ -60,12 +54,9 @@ void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry i = pq->len -1 ;while (i >0 ) {int j = (i -1 ) /2 ; -if (pq_less (&pq->heap[j], &pq->heap[i])) { +if (pq_less (&pq->heap[j], &pq->heap[i]))break ; - } -SWAP (pq->heap[j], pq->heap[i]); - i = j; } }
Signature · 1 line
2.45.GIT
Re: [PATCH v6 1/7] reftable: remove unncessary curly braces in reftable/pq.c
Quoted 1 line · Chandra Pratap
[…]
s/unncessary/unnecessary/
(the subject line)
Signature · 1 line
Kristoffer Haugsbakk
PATCH v6 2/7 reftable: change the type of array indices to 'size_t' in reftable/pq.c
In reply to Chandra PratapThe variables 'i', 'j', 'k' and 'min' are used as indices for 'pq->heap', which is an array. Additionally, 'pq->len' is of type 'size_t' and is often used to assign values to these variables. Hence, change the type of these variables from 'int' to 'size_t'.
--- reftable/pq.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-)
reftable/pq.c +6 -6
@@ -22,15 +22,15 @@ int pq_less(struct pq_entry *a, struct pq_entry *b)struct pq_entry merged_iter_pqueue_remove (struct merged_iter_pqueue *pq) { -int i =0 ; +size_t i =0 ;struct pq_entry e = pq->heap[0 ]; pq->heap[0 ] = pq->heap[pq->len -1 ]; pq->len--;while (i < pq->len) { -int min = i; -int j =2 * i +1 ; -int k =2 * i +2 ; +size_t min = i; +size_t j =2 * i +1 ; +size_t k =2 * i +2 ;if (j < pq->len &&pq_less (&pq->heap[j], &pq->heap[i])) min = j;if (k < pq->len &&pq_less (&pq->heap[k], &pq->heap[min]))
@@ -46,14 +46,14 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)void merged_iter_pqueue_add (struct merged_iter_pqueue *pq,const struct pq_entry *e) { -int i =0 ; +size_t i =0 ;REFTABLE_ALLOC_GROW (pq->heap, pq->len +1 , pq->cap); pq->heap[pq->len++] = *e; i = pq->len -1 ;while (i >0 ) { -int j = (i -1 ) /2 ; +size_t j = (i -1 ) /2 ;if (pq_less (&pq->heap[j], &pq->heap[i]))break ;SWAP (pq->heap[j], pq->heap[i]);
Signature · 1 line
2.45.GIT
PATCH v6 3/7 t: move reftable/pq_test.c to the unit testing framework
In reply to Chandra Pratapreftable/pq_test.c exercises a priority queue defined by reftable/pq.{c, h}. Migrate reftable/pq_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.
--- Makefile | 2 +- reftable/reftable-tests.h | 1 - t/helper/test-reftable.c | 1 - .../pq_test.c => t/unit-tests/t-reftable-pq.c | 39 ++++++++----------- 4 files changed, 17 insertions(+), 26 deletions(-) rename reftable/pq_test.c => t/unit-tests/t-reftable-pq.c (61%)
Makefile +1 -1
@@ -1340,6 +1340,7 @@ UNIT_TEST_PROGRAMS += t-oidmap UNIT_TEST_PROGRAMS += t-oidtree UNIT_TEST_PROGRAMS += t-prio-queue UNIT_TEST_PROGRAMS += t-reftable-basics +UNIT_TEST_PROGRAMS += t-reftable-pq UNIT_TEST_PROGRAMS += t-reftable-record UNIT_TEST_PROGRAMS += t-strbuf UNIT_TEST_PROGRAMS += t-strcmp-offset
@@ -2681,7 +2682,6 @@ REFTABLE_OBJS += reftable/writer.o REFTABLE_TEST_OBJS += reftable/block_test.o REFTABLE_TEST_OBJS += reftable/dump.o REFTABLE_TEST_OBJS += reftable/merged_test.o -REFTABLE_TEST_OBJS += reftable/pq_test.o REFTABLE_TEST_OBJS += reftable/readwrite_test.o REFTABLE_TEST_OBJS += reftable/stack_test.o REFTABLE_TEST_OBJS += reftable/test_framework.o
reftable/reftable-tests.h +0 -1
@@ -12,7 +12,6 @@ license that can be found in the LICENSE file or atint basics_test_main (int argc,const char **argv);int block_test_main (int argc,const char **argv);int merged_test_main (int argc,const char **argv); -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);
t/helper/test-reftable.c +0 -1
@@ -7,7 +7,6 @@ int cmd__reftable(int argc, const char **argv)/* test from simple to complex. */ 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);stack_test_main (argc, argv);
t/unit-tests/t-reftable-pq.c renamed from reftable/pq_test.c +16 -23
@@ -6,35 +6,28 @@ license that can be found in the LICENSE file or athttps://developers.google.com/open-source/licenses/bsd */ -#include "system.h" - -#include "basics.h" -#include "constants.h" -#include "pq.h" -#include "record.h" -#include "reftable-tests.h" -#include "test_framework.h" +#include "test-lib.h" +#include "reftable/constants.h" +#include "reftable/pq.h" void merged_iter_pqueue_check (struct merged_iter_pqueue pq) { -int i; -for (i =1 ; i < pq.len; i++) { -int parent = (i -1 ) /2 ; - -EXPECT (pq_less (&pq.heap[parent], &pq.heap[i])); +for (size_t i =1 ; i < pq.len; i++) { +size_t parent = (i -1 ) /2 ; +check (pq_less (&pq.heap[parent], &pq.heap[i])); } } -static void test_pq (void ) +static void t_pq (void ) { -struct merged_iter_pqueue pq = {NULL }; +struct merged_iter_pqueue pq = {0 };struct reftable_record recs[54 ]; -int N =ARRAY_SIZE (recs) -1 , i; +size_t N =ARRAY_SIZE (recs) -1 , i;char *last =NULL ;for (i =0 ; i <N ; i++) {struct strbuf refname =STRBUF_INIT ; -strbuf_addf (&refname,"%02d" , i); +strbuf_addf (&refname,"%02" PRIuMAX, (uintmax_t )i);reftable_record_init (&recs[i],BLOCK_TYPE_REF ); recs[i].u.ref.refname =strbuf_detach (&refname,NULL );
@@ -48,7 +41,6 @@ static void test_pq(void)merged_iter_pqueue_add (&pq, &e);merged_iter_pqueue_check (pq); - i = (i *7 ) %N ; }while (i !=1 );
@@ -56,9 +48,9 @@ static void test_pq(void)struct pq_entry e =merged_iter_pqueue_remove (&pq);merged_iter_pqueue_check (pq); -EXPECT (reftable_record_type (e.rec) ==BLOCK_TYPE_REF ); +check (reftable_record_type (e.rec) ==BLOCK_TYPE_REF );if (last) -EXPECT (strcmp (last, e.rec->u.ref.refname) <0 ); + check_int(strcmp(last, e.rec->u.ref.refname), <, 0); last = e.rec->u.ref.refname; }
@@ -67,8 +59,9 @@ static void test_pq(void)merged_iter_pqueue_release (&pq); } -int pq_test_main (int argc,const char *argv[]) +int cmd_main (int argc,const char *argv[]) { -RUN_TEST (test_pq); -return 0 ; +TEST (t_pq (),"pq works" ); + +return test_done (); }
Signature · 1 line
2.45.GIT
PATCH v6 4/7 t-reftable-pq: make merged_iter_pqueue_check() static
In reply to Chandra Pratapmerged_iter_pqueue_check() is a function previously defined in reftable/pq_test.c (now t/unit-tests/t-reftable-pq.c) and used in the testing of a priority queue as defined by reftable/pq.{c, h}. As such, this function is only called by reftable/pq_test.c and it makes little sense to expose it to non-testing code via reftable/pq.h.
Hence, make this function static and remove its prototype from reftable/pq.h.
--- reftable/pq.h | 1 - t/unit-tests/t-reftable-pq.c | 2 +- 2 files changed, 1 insertion(+), 2 deletions(-)
reftable/pq.h +0 -1
@@ -22,7 +22,6 @@ struct merged_iter_pqueue {size_t cap; }; -void merged_iter_pqueue_check (struct merged_iter_pqueue pq);struct pq_entry merged_iter_pqueue_remove (struct merged_iter_pqueue *pq);void merged_iter_pqueue_add (struct merged_iter_pqueue *pq,const struct pq_entry *e);void merged_iter_pqueue_release (struct merged_iter_pqueue *pq);
t/unit-tests/t-reftable-pq.c +1 -1
@@ -10,7 +10,7 @@ license that can be found in the LICENSE file or at#include "reftable/constants.h" #include "reftable/pq.h" -void merged_iter_pqueue_check (struct merged_iter_pqueue pq) +static void merged_iter_pqueue_check (struct merged_iter_pqueue pq) {for (size_t i =1 ; i < pq.len; i++) {size_t parent = (i -1 ) /2 ;
Signature · 1 line
2.45.GIT
PATCH v6 5/7 t-reftable-pq: make merged_iter_pqueue_check() callable by reference
In reply to Chandra Pratapmerged_iter_pqueue_check() checks the validity of a priority queue represented by a merged_iter_pqueue struct by asserting the parent-child relation in the struct's heap. Explicity passing a struct to this function means a copy of the entire struct is created, which is inefficient.
Make the function accept a pointer to the struct instead. This is safe to do since the function doesn't modify the struct in any way. Make the function parameter 'const' to assert immutability.
--- t/unit-tests/t-reftable-pq.c | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-)
t/unit-tests/t-reftable-pq.c +5 -5
@@ -10,11 +10,11 @@ license that can be found in the LICENSE file or at#include "reftable/constants.h" #include "reftable/pq.h" -static void merged_iter_pqueue_check (struct merged_iter_pqueue pq) +static void merged_iter_pqueue_check (const struct merged_iter_pqueue *pq) { -for (size_t i =1 ; i < pq.len; i++) { +for (size_t i =1 ; i < pq->len; i++) {size_t parent = (i -1 ) /2 ; -check (pq_less (&pq.heap[parent], &pq.heap[i])); +check (pq_less (&pq->heap[parent], &pq->heap[i])); } }
@@ -40,13 +40,13 @@ static void t_pq(void) };merged_iter_pqueue_add (&pq, &e); -merged_iter_pqueue_check (pq); +merged_iter_pqueue_check (&pq); i = (i *7 ) %N ; }while (i !=1 );while (!merged_iter_pqueue_is_empty (pq)) {struct pq_entry e =merged_iter_pqueue_remove (&pq); -merged_iter_pqueue_check (pq); +merged_iter_pqueue_check (&pq);check (reftable_record_type (e.rec) ==BLOCK_TYPE_REF );if (last)
Signature · 1 line
2.45.GIT
PATCH v6 6/7 t-reftable-pq: add test for index based comparison
In reply to Chandra PratapWhen 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.
While at it, replace 'strbuf_detach' with 'xstrfmt' to assign refnames in the existing test. This makes the test conciser.
--- t/unit-tests/t-reftable-pq.c | 49 +++++++++++++++++++++++++++++++----- 1 file changed, 43 insertions(+), 6 deletions(-)
t/unit-tests/t-reftable-pq.c +43 -6
@@ -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 ];
@@ -26,11 +26,8 @@ static void t_pq(void)char *last =NULL ;for (i =0 ; i <N ; i++) { -struct strbuf refname =STRBUF_INIT ; -strbuf_addf (&refname,"%02" PRIuMAX, (uintmax_t )i); -reftable_record_init (&recs[i],BLOCK_TYPE_REF ); - recs[i].u.ref.refname =strbuf_detach (&refname,NULL ); + recs[i].u.ref.refname =xstrfmt ("%02" PRIuMAX, (uintmax_t )i); } i =1 ;
@@ -59,9 +56,49 @@ 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[13 ]; +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 = (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 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; + } + +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 (); }
Signature · 1 line
2.45.GIT
Re: [PATCH v6 6/7] t-reftable-pq: add test for index based comparison
Quoted 18 lines · Chandra Pratap
t/unit-tests/t-reftable-pq.c +14
-0@@ -59,9 +56,49 @@ 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[13 ]; +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 = (char *)"refs/heads/master" ; + } + + i =1 ; + do {
t/unit-tests/t-reftable-pq.c static void t_pq(void) · line 82
Quoted 10 lines
t/unit-tests/t-reftable-pq.c +10
-0+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 );
Nit: the while (i != 1) should go on the same line as the closing curly brace.
Patrick
PATCH v6 7/7 t-reftable-pq: add tests for merged_iter_pqueue_top()
In reply to Chandra Pratapmerged_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.
--- t/unit-tests/t-reftable-pq.c | 50 ++++++++++++++++++++++++++++++++++++ 1 file changed, 50 insertions(+)
t/unit-tests/t-reftable-pq.c +50 -0
@@ -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);
@@ -82,9 +89,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)
@@ -95,10 +104,51 @@ 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 (); }
Signature · 1 line
2.45.GIT
Re: [PATCH v6 7/7] t-reftable-pq: add tests for merged_iter_pqueue_top()
Quoted 17 lines · Chandra Pratap
t/unit-tests/t-reftable-pq.c +13
-0@@ -95,10 +104,51 @@ 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 {
t/unit-tests/t-reftable-pq.c static void t_pq_index(void) · line 129
Quoted 10 lines
t/unit-tests/t-reftable-pq.c +10
-0+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 );
Same nit here. Other than that this patch series looks good to me, thanks!
Patrick
v7 cover t: port reftable/pq_test.c to the unit testing framework
In reply to Chandra PratapThe reftable library comes with self tests, which are exercised as part of the usual end-to-end tests and are designed to observe the end-user visible effects of Git commands. What it exercises, however, is a better match for the unit-testing framework, merged at 8bf6fbd0 (Merge branch 'js/doc-unit-tests', 2023-12-09), which is designed to observe how low level implementation details, at the level of sequences of individual function calls, behave.
Hence, port reftable/pq_test.c to the unit testing framework and improve upon the ported test. The first two patches in the series are preparatory cleanup, the third patch moves the test to the unit testing framework, and the rest of the patches improve upon the ported test.
---
Changes in v7:
- Fix a typo in patch 1
- Fix do-while style error in patch 6 and 7
CI/PR for v7: https://github.com/gitgitgadget/git/pull/1745
Chandra Pratap(7):
reftable: remove unncessary curly braces in reftable/pq.c
reftable: change the type of array indices to 'size_t' in reftable/pq.c
t: move reftable/pq_test.c to the unit testing framework
t-reftable-pq: make merged_iter_pqueue_check() static
t-reftable-pq: make merged_iter_pqueue_check() callable by reference
t-reftable-pq: add test for index based comparison
t-reftable-pq: add tests for merged_iter_pqueue_top()
Makefile | 2 +- reftable/pq.c | 29 +++----- reftable/pq.h | 1 - reftable/pq_test.c | 74 --------------------- reftable/reftable-tests.h | 1 - t/helper/test-reftable.c | 1 - t/unit-tests/t-reftable-pq.c | 152 +++++++++++++++++++++++++++++++++++++++++++ 7 files changed, 163 insertions(+), 97 deletions(-)
Range-diff against v6:
1: acd9d26aaf ! 1: 91719cc47f reftable: remove unncessary curly braces in reftable/pq.c
@@ Metadata
Author: Chandra Pratap <[email protected]>
## Commit message ##
- reftable: remove unncessary curly braces in reftable/pq.c
+ reftable: remove unnecessary curly braces in reftable/pq.c
According to Documentation/CodingGuidelines, control-flow statements with a single line as their body must omit curly braces. Make
2: 2e0986207b = 2: 2e5e72d5c5 reftable: change the type of array indices to 'size_t' in reftable/pq.c
3: df06b6d604 = 3: 5db9e92f20 t: move reftable/pq_test.c to the unit testing framework
4: 40745ab18e = 4: 9334b1fe9e t-reftable-pq: make merged_iter_pqueue_check() static
5: ee8432ac4a = 5: 9d8c33d1fc t-reftable-pq: make merged_iter_pqueue_check() callable by reference
6: f5c30187e1 ! 6: 7a67861652 t-reftable-pq: add test for index based comparison
@@ t/unit-tests/t-reftable-pq.c: static void t_pq(void)
+ merged_iter_pqueue_add(&pq, &e);
+ merged_iter_pqueue_check(&pq);
+ i = (i * 7) % N;
-+ }
-+ while (i != 1);
++ } while (i != 1);
+
+ for (i = N - 1; i > 0; i--) {
+ struct pq_entry e = merged_iter_pqueue_remove(&pq);
7: 394540a789 ! 7: 5ac60563e4 t-reftable-pq: add tests for merged_iter_pqueue_top()
@@ t/unit-tests/t-reftable-pq.c: static void t_pq_record(void)
if (last)
check_int(strcmp(last, e.rec->u.ref.refname), <, 0);
@@ t/unit-tests/t-reftable-pq.c: static void t_pq_index(void)
- while (i != 1);
+ } while (i != 1);
for (i = N - 1; i > 0; i--) {
+ struct pq_entry top = merged_iter_pqueue_top(pq);
@@ t/unit-tests/t-reftable-pq.c: static void t_pq_index(void)
+ merged_iter_pqueue_add(&pq, &e);
+ merged_iter_pqueue_check(&pq);
+ i = (i * 7) % N;
-+ }
-+ while (i != 1);
++ } while (i != 1);
+
+ for (i = N - 1; i > 0; i--) {
+ struct pq_entry top = merged_iter_pqueue_top(pq);PATCH v7 1/7 reftable: remove unnecessary curly braces in reftable/pq.c
According to Documentation/CodingGuidelines, control-flow statements with a single line as their body must omit curly braces. Make reftable/pq.c conform to this guideline. Besides that, remove unnecessary newlines and variable assignment.
--- reftable/pq.c | 17 ++++------------- 1 file changed, 4 insertions(+), 13 deletions(-)
reftable/pq.c +4 -13
@@ -27,22 +27,16 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq) pq->heap[0 ] = pq->heap[pq->len -1 ]; pq->len--; - i =0 ;while (i < pq->len) {int min = i;int j =2 * i +1 ;int k =2 * i +2 ; -if (j < pq->len &&pq_less (&pq->heap[j], &pq->heap[i])) { +if (j < pq->len &&pq_less (&pq->heap[j], &pq->heap[i])) min = j; - } -if (k < pq->len &&pq_less (&pq->heap[k], &pq->heap[min])) { +if (k < pq->len &&pq_less (&pq->heap[k], &pq->heap[min])) min = k; - } - -if (min == i) { +if (min == i)break ; - } -SWAP (pq->heap[i], pq->heap[min]); i = min; }
@@ -60,12 +54,9 @@ void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry i = pq->len -1 ;while (i >0 ) {int j = (i -1 ) /2 ; -if (pq_less (&pq->heap[j], &pq->heap[i])) { +if (pq_less (&pq->heap[j], &pq->heap[i]))break ; - } -SWAP (pq->heap[j], pq->heap[i]); - i = j; } }
Signature · 1 line
2.45.GIT
PATCH v7 2/7 reftable: change the type of array indices to 'size_t' in reftable/pq.c
In reply to Chandra PratapThe variables 'i', 'j', 'k' and 'min' are used as indices for 'pq->heap', which is an array. Additionally, 'pq->len' is of type 'size_t' and is often used to assign values to these variables. Hence, change the type of these variables from 'int' to 'size_t'.
--- reftable/pq.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-)
reftable/pq.c +6 -6
@@ -22,15 +22,15 @@ int pq_less(struct pq_entry *a, struct pq_entry *b)struct pq_entry merged_iter_pqueue_remove (struct merged_iter_pqueue *pq) { -int i =0 ; +size_t i =0 ;struct pq_entry e = pq->heap[0 ]; pq->heap[0 ] = pq->heap[pq->len -1 ]; pq->len--;while (i < pq->len) { -int min = i; -int j =2 * i +1 ; -int k =2 * i +2 ; +size_t min = i; +size_t j =2 * i +1 ; +size_t k =2 * i +2 ;if (j < pq->len &&pq_less (&pq->heap[j], &pq->heap[i])) min = j;if (k < pq->len &&pq_less (&pq->heap[k], &pq->heap[min]))
@@ -46,14 +46,14 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)void merged_iter_pqueue_add (struct merged_iter_pqueue *pq,const struct pq_entry *e) { -int i =0 ; +size_t i =0 ;REFTABLE_ALLOC_GROW (pq->heap, pq->len +1 , pq->cap); pq->heap[pq->len++] = *e; i = pq->len -1 ;while (i >0 ) { -int j = (i -1 ) /2 ; +size_t j = (i -1 ) /2 ;if (pq_less (&pq->heap[j], &pq->heap[i]))break ;SWAP (pq->heap[j], pq->heap[i]);
Signature · 1 line
2.45.GIT
PATCH v7 3/7 t: move reftable/pq_test.c to the unit testing framework
In reply to Chandra Pratapreftable/pq_test.c exercises a priority queue defined by reftable/pq.{c, h}. Migrate reftable/pq_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.
--- Makefile | 2 +- reftable/reftable-tests.h | 1 - t/helper/test-reftable.c | 1 - .../pq_test.c => t/unit-tests/t-reftable-pq.c | 39 ++++++++----------- 4 files changed, 17 insertions(+), 26 deletions(-) rename reftable/pq_test.c => t/unit-tests/t-reftable-pq.c (61%)
Makefile +1 -1
@@ -1340,6 +1340,7 @@ UNIT_TEST_PROGRAMS += t-oidmap UNIT_TEST_PROGRAMS += t-oidtree UNIT_TEST_PROGRAMS += t-prio-queue UNIT_TEST_PROGRAMS += t-reftable-basics +UNIT_TEST_PROGRAMS += t-reftable-pq UNIT_TEST_PROGRAMS += t-reftable-record UNIT_TEST_PROGRAMS += t-strbuf UNIT_TEST_PROGRAMS += t-strcmp-offset
@@ -2681,7 +2682,6 @@ REFTABLE_OBJS += reftable/writer.o REFTABLE_TEST_OBJS += reftable/block_test.o REFTABLE_TEST_OBJS += reftable/dump.o REFTABLE_TEST_OBJS += reftable/merged_test.o -REFTABLE_TEST_OBJS += reftable/pq_test.o REFTABLE_TEST_OBJS += reftable/readwrite_test.o REFTABLE_TEST_OBJS += reftable/stack_test.o REFTABLE_TEST_OBJS += reftable/test_framework.o
reftable/reftable-tests.h +0 -1
@@ -12,7 +12,6 @@ license that can be found in the LICENSE file or atint basics_test_main (int argc,const char **argv);int block_test_main (int argc,const char **argv);int merged_test_main (int argc,const char **argv); -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);
t/helper/test-reftable.c +0 -1
@@ -7,7 +7,6 @@ int cmd__reftable(int argc, const char **argv)/* test from simple to complex. */ 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);stack_test_main (argc, argv);
t/unit-tests/t-reftable-pq.c renamed from reftable/pq_test.c +16 -23
@@ -6,35 +6,28 @@ license that can be found in the LICENSE file or athttps://developers.google.com/open-source/licenses/bsd */ -#include "system.h" - -#include "basics.h" -#include "constants.h" -#include "pq.h" -#include "record.h" -#include "reftable-tests.h" -#include "test_framework.h" +#include "test-lib.h" +#include "reftable/constants.h" +#include "reftable/pq.h" void merged_iter_pqueue_check (struct merged_iter_pqueue pq) { -int i; -for (i =1 ; i < pq.len; i++) { -int parent = (i -1 ) /2 ; - -EXPECT (pq_less (&pq.heap[parent], &pq.heap[i])); +for (size_t i =1 ; i < pq.len; i++) { +size_t parent = (i -1 ) /2 ; +check (pq_less (&pq.heap[parent], &pq.heap[i])); } } -static void test_pq (void ) +static void t_pq (void ) { -struct merged_iter_pqueue pq = {NULL }; +struct merged_iter_pqueue pq = {0 };struct reftable_record recs[54 ]; -int N =ARRAY_SIZE (recs) -1 , i; +size_t N =ARRAY_SIZE (recs) -1 , i;char *last =NULL ;for (i =0 ; i <N ; i++) {struct strbuf refname =STRBUF_INIT ; -strbuf_addf (&refname,"%02d" , i); +strbuf_addf (&refname,"%02" PRIuMAX, (uintmax_t )i);reftable_record_init (&recs[i],BLOCK_TYPE_REF ); recs[i].u.ref.refname =strbuf_detach (&refname,NULL );
@@ -48,7 +41,6 @@ static void test_pq(void)merged_iter_pqueue_add (&pq, &e);merged_iter_pqueue_check (pq); - i = (i *7 ) %N ; }while (i !=1 );
@@ -56,9 +48,9 @@ static void test_pq(void)struct pq_entry e =merged_iter_pqueue_remove (&pq);merged_iter_pqueue_check (pq); -EXPECT (reftable_record_type (e.rec) ==BLOCK_TYPE_REF ); +check (reftable_record_type (e.rec) ==BLOCK_TYPE_REF );if (last) -EXPECT (strcmp (last, e.rec->u.ref.refname) <0 ); + check_int(strcmp(last, e.rec->u.ref.refname), <, 0); last = e.rec->u.ref.refname; }
@@ -67,8 +59,9 @@ static void test_pq(void)merged_iter_pqueue_release (&pq); } -int pq_test_main (int argc,const char *argv[]) +int cmd_main (int argc,const char *argv[]) { -RUN_TEST (test_pq); -return 0 ; +TEST (t_pq (),"pq works" ); + +return test_done (); }
Signature · 1 line
2.45.GIT
PATCH v7 4/7 t-reftable-pq: make merged_iter_pqueue_check() static
In reply to Chandra Pratapmerged_iter_pqueue_check() is a function previously defined in reftable/pq_test.c (now t/unit-tests/t-reftable-pq.c) and used in the testing of a priority queue as defined by reftable/pq.{c, h}. As such, this function is only called by reftable/pq_test.c and it makes little sense to expose it to non-testing code via reftable/pq.h.
Hence, make this function static and remove its prototype from reftable/pq.h.
--- reftable/pq.h | 1 - t/unit-tests/t-reftable-pq.c | 2 +- 2 files changed, 1 insertion(+), 2 deletions(-)
reftable/pq.h +0 -1
@@ -22,7 +22,6 @@ struct merged_iter_pqueue {size_t cap; }; -void merged_iter_pqueue_check (struct merged_iter_pqueue pq);struct pq_entry merged_iter_pqueue_remove (struct merged_iter_pqueue *pq);void merged_iter_pqueue_add (struct merged_iter_pqueue *pq,const struct pq_entry *e);void merged_iter_pqueue_release (struct merged_iter_pqueue *pq);
t/unit-tests/t-reftable-pq.c +1 -1
@@ -10,7 +10,7 @@ license that can be found in the LICENSE file or at#include "reftable/constants.h" #include "reftable/pq.h" -void merged_iter_pqueue_check (struct merged_iter_pqueue pq) +static void merged_iter_pqueue_check (struct merged_iter_pqueue pq) {for (size_t i =1 ; i < pq.len; i++) {size_t parent = (i -1 ) /2 ;
Signature · 1 line
2.45.GIT
PATCH v7 5/7 t-reftable-pq: make merged_iter_pqueue_check() callable by reference
In reply to Chandra Pratapmerged_iter_pqueue_check() checks the validity of a priority queue represented by a merged_iter_pqueue struct by asserting the parent-child relation in the struct's heap. Explicity passing a struct to this function means a copy of the entire struct is created, which is inefficient.
Make the function accept a pointer to the struct instead. This is safe to do since the function doesn't modify the struct in any way. Make the function parameter 'const' to assert immutability.
--- t/unit-tests/t-reftable-pq.c | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-)
t/unit-tests/t-reftable-pq.c +5 -5
@@ -10,11 +10,11 @@ license that can be found in the LICENSE file or at#include "reftable/constants.h" #include "reftable/pq.h" -static void merged_iter_pqueue_check (struct merged_iter_pqueue pq) +static void merged_iter_pqueue_check (const struct merged_iter_pqueue *pq) { -for (size_t i =1 ; i < pq.len; i++) { +for (size_t i =1 ; i < pq->len; i++) {size_t parent = (i -1 ) /2 ; -check (pq_less (&pq.heap[parent], &pq.heap[i])); +check (pq_less (&pq->heap[parent], &pq->heap[i])); } }
@@ -40,13 +40,13 @@ static void t_pq(void) };merged_iter_pqueue_add (&pq, &e); -merged_iter_pqueue_check (pq); +merged_iter_pqueue_check (&pq); i = (i *7 ) %N ; }while (i !=1 );while (!merged_iter_pqueue_is_empty (pq)) {struct pq_entry e =merged_iter_pqueue_remove (&pq); -merged_iter_pqueue_check (pq); +merged_iter_pqueue_check (&pq);check (reftable_record_type (e.rec) ==BLOCK_TYPE_REF );if (last)
Signature · 1 line
2.45.GIT
PATCH v7 6/7 t-reftable-pq: add test for index based comparison
In reply to Chandra PratapWhen 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.
While at it, replace 'strbuf_detach' with 'xstrfmt' to assign refnames in the existing test. This makes the test conciser.
--- t/unit-tests/t-reftable-pq.c | 48 +++++++++++++++++++++++++++++++----- 1 file changed, 42 insertions(+), 6 deletions(-)
t/unit-tests/t-reftable-pq.c +42 -6
@@ -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 ];
@@ -26,11 +26,8 @@ static void t_pq(void)char *last =NULL ;for (i =0 ; i <N ; i++) { -struct strbuf refname =STRBUF_INIT ; -strbuf_addf (&refname,"%02" PRIuMAX, (uintmax_t )i); -reftable_record_init (&recs[i],BLOCK_TYPE_REF ); - recs[i].u.ref.refname =strbuf_detach (&refname,NULL ); + recs[i].u.ref.refname =xstrfmt ("%02" PRIuMAX, (uintmax_t )i); } i =1 ;
@@ -59,9 +56,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[13 ]; +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 = (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 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; + } + +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 (); }
Signature · 1 line
2.45.GIT
PATCH v7 7/7 t-reftable-pq: add tests for merged_iter_pqueue_top()
In reply to Chandra Pratapmerged_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.
--- t/unit-tests/t-reftable-pq.c | 49 ++++++++++++++++++++++++++++++++++++ 1 file changed, 49 insertions(+)
t/unit-tests/t-reftable-pq.c +49 -0
@@ -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 (); }
Signature · 1 line
2.45.GIT
Re: [GSoC][PATCH v7 0/7] t: port reftable/pq_test.c to the unit testing framework
In reply to Chandra PratapQuoted 15 lines · Chandra Pratap
The reftable library comes with self tests, which are exercised as part of the usual end-to-end tests and are designed to observe the end-user visible effects of Git commands. What it exercises, however, is a better match for the unit-testing framework, merged at
8bf6fbd0(Merge branch 'js/doc-unit-tests', 2023-12-09), which is designed to observe how low level implementation details, at the level of sequences of individual function calls, behave.Hence, port
reftable/pq_test.cto the unit testing framework and improve upon the ported test. The first two patches in the series are preparatory cleanup, the third patch moves the test to the unit testing framework, and the rest of the patches improve upon the ported test.
Quoted 8 lines
Mentored-by Patrick Steinhardt <[email protected]>Mentored-by Christian Couder <[email protected]>Signed-off-by Chandra Pratap <[email protected]>---
Changes in v7:
- Fix a typo in patch 1
- Fix do-while style error in patch 6 and 7
The range-diff looks as expected to me, so the whole series LGTM now. Thanks!
Patrick
Re: [GSoC][PATCH v7 0/7] t: port reftable/pq_test.c to the unit testing framework
Quoted 2 lines · Patrick Steinhardt
... the whole series LGTM now.
Thanks!
Thanks, both.