aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJunio C Hamano <gitster@pobox.com>2024-08-14 14:54:48 -0700
committerJunio C Hamano <gitster@pobox.com>2024-08-14 14:54:48 -0700
commitd65332f241524e9ef9985a55753ba70d6aaf70e7 (patch)
tree1024d69045e679e1d814386575966fef748a0746
parent6c3c451fb6e1c3ca83f74e63079d4d0af01b2d69 (diff)
parent0dc84a806c53b02b465616d26efbca73682c58dd (diff)
downloadgit-d65332f241524e9ef9985a55753ba70d6aaf70e7.tar.gz
Merge branch 'cp/unit-test-reftable-pq'
The tests for "pq" part of reftable library got rewritten to use the unit test framework. * cp/unit-test-reftable-pq: t-reftable-pq: add tests for merged_iter_pqueue_top() t-reftable-pq: add test for index based comparison t-reftable-pq: make merged_iter_pqueue_check() callable by reference t-reftable-pq: make merged_iter_pqueue_check() static t: move reftable/pq_test.c to the unit testing framework reftable: change the type of array indices to 'size_t' in reftable/pq.c reftable: remove unnecessary curly braces in reftable/pq.c
Diffstat
-rw-r--r--Makefile2
-rw-r--r--reftable/pq.c29
-rw-r--r--reftable/pq.h1
-rw-r--r--reftable/pq_test.c74
-rw-r--r--reftable/reftable-tests.h1
-rw-r--r--t/helper/test-reftable.c1
-rw-r--r--t/unit-tests/t-reftable-pq.c152
7 files changed, 163 insertions, 97 deletions
diff --git a/Makefile b/Makefile
index 3863e60b66..699af109f7 100644
--- a/Makefile
+++ b/Makefile
@@ -1341,6 +1341,7 @@ UNIT_TEST_PROGRAMS += t-oidtree
UNIT_TEST_PROGRAMS += t-prio-queue
UNIT_TEST_PROGRAMS += t-reftable-basics
UNIT_TEST_PROGRAMS += t-reftable-merged
+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/pq_test.o
REFTABLE_TEST_OBJS += reftable/readwrite_test.o
REFTABLE_TEST_OBJS += reftable/stack_test.o
REFTABLE_TEST_OBJS += reftable/test_framework.o
diff --git a/reftable/pq.c b/reftable/pq.c
index 7fb45d8c60..2b5b7d1c0e 100644
--- a/reftable/pq.c
+++ b/reftable/pq.c
@@ -22,27 +22,21 @@ 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--;
- 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])) {
+ 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])) {
+ 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;
}
@@ -52,20 +46,17 @@ 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;
- if (pq_less(&pq->heap[j], &pq->heap[i])) {
+ size_t j = (i - 1) / 2;
+ if (pq_less(&pq->heap[j], &pq->heap[i]))
break;
- }
-
SWAP(pq->heap[j], pq->heap[i]);
-
i = j;
}
}
diff --git a/reftable/pq.h b/reftable/pq.h
index f796c23179..707bd26767 100644
--- a/reftable/pq.h
+++ b/reftable/pq.h
@@ -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);
diff --git a/reftable/pq_test.c b/reftable/pq_test.c
deleted file mode 100644
index b7d3c80cc7..0000000000
--- a/reftable/pq_test.c
+++ /dev/null
@@ -1,74 +0,0 @@
-/*
-Copyright 2020 Google LLC
-
-Use of this source code is governed by a BSD-style
-license that can be found in the LICENSE file or at
-https://developers.google.com/open-source/licenses/bsd
-*/
-
-#include "system.h"
-
-#include "basics.h"
-#include "constants.h"
-#include "pq.h"
-#include "record.h"
-#include "reftable-tests.h"
-#include "test_framework.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]));
- }
-}
-
-static void test_pq(void)
-{
- struct merged_iter_pqueue pq = { NULL };
- struct reftable_record recs[54];
- int 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);
-
- reftable_record_init(&recs[i], BLOCK_TYPE_REF);
- recs[i].u.ref.refname = strbuf_detach(&refname, NULL);
- }
-
- i = 1;
- do {
- struct pq_entry e = {
- .rec = &recs[i],
- };
-
- merged_iter_pqueue_add(&pq, &e);
- 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);
-
- EXPECT(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
- if (last)
- EXPECT(strcmp(last, e.rec->u.ref.refname) < 0);
- last = e.rec->u.ref.refname;
- }
-
- for (i = 0; i < N; i++)
- reftable_record_release(&recs[i]);
- merged_iter_pqueue_release(&pq);
-}
-
-int pq_test_main(int argc, const char *argv[])
-{
- RUN_TEST(test_pq);
- return 0;
-}
diff --git a/reftable/reftable-tests.h b/reftable/reftable-tests.h
index d5e03dcc1b..3bc1d88d9b 100644
--- a/reftable/reftable-tests.h
+++ b/reftable/reftable-tests.h
@@ -11,7 +11,6 @@ https://developers.google.com/open-source/licenses/bsd
int basics_test_main(int argc, const char **argv);
int block_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);
diff --git a/t/helper/test-reftable.c b/t/helper/test-reftable.c
index 9d378427da..672eaedae0 100644
--- a/t/helper/test-reftable.c
+++ b/t/helper/test-reftable.c
@@ -7,7 +7,6 @@ int cmd__reftable(int argc, const char **argv)
/* test from simple to complex. */
block_test_main(argc, argv);
tree_test_main(argc, argv);
- pq_test_main(argc, argv);
readwrite_test_main(argc, argv);
stack_test_main(argc, argv);
return 0;
diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
new file mode 100644
index 0000000000..039bd0f1f9
--- /dev/null
+++ b/t/unit-tests/t-reftable-pq.c
@@ -0,0 +1,152 @@
+/*
+Copyright 2020 Google LLC
+
+Use of this source code is governed by a BSD-style
+license that can be found in the LICENSE file or at
+https://developers.google.com/open-source/licenses/bsd
+*/
+
+#include "test-lib.h"
+#include "reftable/constants.h"
+#include "reftable/pq.h"
+
+static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
+{
+ 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 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 };
+ struct reftable_record recs[54];
+ size_t N = ARRAY_SIZE(recs) - 1, i;
+ char *last = NULL;
+
+ for (i = 0; i < N; i++) {
+ reftable_record_init(&recs[i], BLOCK_TYPE_REF);
+ recs[i].u.ref.refname = xstrfmt("%02"PRIuMAX, (uintmax_t)i);
+ }
+
+ i = 1;
+ do {
+ struct pq_entry e = {
+ .rec = &recs[i],
+ };
+
+ merged_iter_pqueue_add(&pq, &e);
+ merged_iter_pqueue_check(&pq);
+ i = (i * 7) % N;
+ } 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);
+ last = e.rec->u.ref.refname;
+ }
+
+ for (i = 0; i < N; i++)
+ reftable_record_release(&recs[i]);
+ 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 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)
+ check_str(last, e.rec->u.ref.refname);
+ last = e.rec->u.ref.refname;
+ }
+
+ 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();
+}
generated by cgit 1.2.3-korg (git 2.43.0) at 2025-12-06 22:04:16 +0000