aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--reftable/merged.c20
-rw-r--r--reftable/pq.c36
-rw-r--r--reftable/pq.h2
-rw-r--r--reftable/record.c10
-rw-r--r--reftable/record.h2
-rw-r--r--t/unit-tests/t-reftable-pq.c16
-rw-r--r--t/unit-tests/t-reftable-record.c40
7 files changed, 92 insertions, 34 deletions
diff --git a/reftable/merged.c b/reftable/merged.c
index 4156eec07f..563864068c 100644
--- a/reftable/merged.c
+++ b/reftable/merged.c
@@ -66,8 +66,11 @@ static int merged_iter_seek(struct merged_iter *mi, struct reftable_record *want
int err;
mi->advance_index = -1;
- while (!merged_iter_pqueue_is_empty(mi->pq))
- merged_iter_pqueue_remove(&mi->pq);
+ while (!merged_iter_pqueue_is_empty(mi->pq)) {
+ err = merged_iter_pqueue_remove(&mi->pq, NULL);
+ if (err < 0)
+ return err;
+ }
for (size_t i = 0; i < mi->subiters_len; i++) {
err = iterator_seek(&mi->subiters[i].iter, want);
@@ -120,7 +123,9 @@ static int merged_iter_next_entry(struct merged_iter *mi,
if (empty)
return 1;
- entry = merged_iter_pqueue_remove(&mi->pq);
+ err = merged_iter_pqueue_remove(&mi->pq, &entry);
+ if (err < 0)
+ return err;
/*
One can also use reftable as datacenter-local storage, where the ref
@@ -134,11 +139,16 @@ static int merged_iter_next_entry(struct merged_iter *mi,
struct pq_entry top = merged_iter_pqueue_top(mi->pq);
int cmp;
- cmp = reftable_record_cmp(top.rec, entry.rec);
+ err = reftable_record_cmp(top.rec, entry.rec, &cmp);
+ if (err < 0)
+ return err;
if (cmp > 0)
break;
- merged_iter_pqueue_remove(&mi->pq);
+ err = merged_iter_pqueue_remove(&mi->pq, NULL);
+ if (err < 0)
+ return err;
+
err = merged_iter_advance_subiter(mi, top.index);
if (err < 0)
return err;
diff --git a/reftable/pq.c b/reftable/pq.c
index 5591e875e1..ef8035cfd9 100644
--- a/reftable/pq.c
+++ b/reftable/pq.c
@@ -15,13 +15,18 @@ https://developers.google.com/open-source/licenses/bsd
int pq_less(struct pq_entry *a, struct pq_entry *b)
{
- int cmp = reftable_record_cmp(a->rec, b->rec);
+ int cmp, err;
+
+ err = reftable_record_cmp(a->rec, b->rec, &cmp);
+ if (err < 0)
+ return err;
+
if (cmp == 0)
return a->index > b->index;
return cmp < 0;
}
-struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
+int merged_iter_pqueue_remove(struct merged_iter_pqueue *pq, struct pq_entry *out)
{
size_t i = 0;
struct pq_entry e = pq->heap[0];
@@ -32,17 +37,34 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
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]))
- min = k;
+ int cmp;
+
+ if (j < pq->len) {
+ cmp = pq_less(&pq->heap[j], &pq->heap[i]);
+ if (cmp < 0)
+ return -1;
+ else if (cmp)
+ min = j;
+ }
+
+ if (k < pq->len) {
+ cmp = pq_less(&pq->heap[k], &pq->heap[min]);
+ if (cmp < 0)
+ return -1;
+ else if (cmp)
+ min = k;
+ }
+
if (min == i)
break;
SWAP(pq->heap[i], pq->heap[min]);
i = min;
}
- return e;
+ if (out)
+ *out = e;
+
+ return 0;
}
int merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e)
diff --git a/reftable/pq.h b/reftable/pq.h
index 83c062eeca..ff39016445 100644
--- a/reftable/pq.h
+++ b/reftable/pq.h
@@ -22,7 +22,7 @@ struct merged_iter_pqueue {
size_t cap;
};
-struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq);
+int merged_iter_pqueue_remove(struct merged_iter_pqueue *pq, struct pq_entry *out);
int merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e);
void merged_iter_pqueue_release(struct merged_iter_pqueue *pq);
int pq_less(struct pq_entry *a, struct pq_entry *b);
diff --git a/reftable/record.c b/reftable/record.c
index 1e18f8dffb..b39d99fcc7 100644
--- a/reftable/record.c
+++ b/reftable/record.c
@@ -1195,12 +1195,14 @@ int reftable_record_is_deletion(struct reftable_record *rec)
reftable_record_data(rec));
}
-int reftable_record_cmp(struct reftable_record *a, struct reftable_record *b)
+int reftable_record_cmp(struct reftable_record *a, struct reftable_record *b,
+ int *cmp)
{
if (a->type != b->type)
- BUG("cannot compare reftable records of different type");
- return reftable_record_vtable(a)->cmp(
- reftable_record_data(a), reftable_record_data(b));
+ return -1;
+ *cmp = reftable_record_vtable(a)->cmp(reftable_record_data(a),
+ reftable_record_data(b));
+ return 0;
}
int reftable_record_equal(struct reftable_record *a, struct reftable_record *b, uint32_t hash_size)
diff --git a/reftable/record.h b/reftable/record.h
index e1846c294b..867810a932 100644
--- a/reftable/record.h
+++ b/reftable/record.h
@@ -134,7 +134,7 @@ struct reftable_record {
int reftable_record_init(struct reftable_record *rec, uint8_t typ);
/* see struct record_vtable */
-int reftable_record_cmp(struct reftable_record *a, struct reftable_record *b);
+int reftable_record_cmp(struct reftable_record *a, struct reftable_record *b, int *cmp);
int reftable_record_equal(struct reftable_record *a, struct reftable_record *b, uint32_t hash_size);
int reftable_record_key(struct reftable_record *rec, struct reftable_buf *dest);
int reftable_record_copy_from(struct reftable_record *rec,
diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index d8a4c283a1..c128fe8616 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -21,7 +21,9 @@ 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);
+ int cmp;
+ check(!reftable_record_cmp(a->rec, b->rec, &cmp));
+ return !cmp && (a->index == b->index);
}
static void t_pq_record(void)
@@ -49,7 +51,9 @@ static void t_pq_record(void)
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);
+ struct pq_entry e;
+
+ check(!merged_iter_pqueue_remove(&pq, &e));
merged_iter_pqueue_check(&pq);
check(pq_entry_equal(&top, &e));
@@ -90,7 +94,9 @@ static void t_pq_index(void)
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);
+ struct pq_entry e;
+
+ check(!merged_iter_pqueue_remove(&pq, &e));
merged_iter_pqueue_check(&pq);
check(pq_entry_equal(&top, &e));
@@ -129,7 +135,9 @@ static void t_merged_iter_pqueue_top(void)
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);
+ struct pq_entry e;
+
+ check(!merged_iter_pqueue_remove(&pq, &e));
merged_iter_pqueue_check(&pq);
check(pq_entry_equal(&top, &e));
diff --git a/t/unit-tests/t-reftable-record.c b/t/unit-tests/t-reftable-record.c
index 6540bd20e3..5954966373 100644
--- a/t/unit-tests/t-reftable-record.c
+++ b/t/unit-tests/t-reftable-record.c
@@ -100,16 +100,20 @@ static void t_reftable_ref_record_comparison(void)
.u.ref.value.symref = (char *) "refs/heads/master",
},
};
+ int cmp;
check(!reftable_record_equal(&in[0], &in[1], REFTABLE_HASH_SIZE_SHA1));
- check(!reftable_record_cmp(&in[0], &in[1]));
+ check(!reftable_record_cmp(&in[0], &in[1], &cmp));
+ check(!cmp);
check(!reftable_record_equal(&in[1], &in[2], REFTABLE_HASH_SIZE_SHA1));
- check_int(reftable_record_cmp(&in[1], &in[2]), >, 0);
+ check(!reftable_record_cmp(&in[1], &in[2], &cmp));
+ check_int(cmp, >, 0);
in[1].u.ref.value_type = in[0].u.ref.value_type;
check(reftable_record_equal(&in[0], &in[1], REFTABLE_HASH_SIZE_SHA1));
- check(!reftable_record_cmp(&in[0], &in[1]));
+ check(!reftable_record_cmp(&in[0], &in[1], &cmp));
+ check(!cmp);
}
static void t_reftable_ref_record_compare_name(void)
@@ -209,17 +213,20 @@ static void t_reftable_log_record_comparison(void)
.u.log.update_index = 22,
},
};
+ int cmp;
check(!reftable_record_equal(&in[0], &in[1], REFTABLE_HASH_SIZE_SHA1));
check(!reftable_record_equal(&in[1], &in[2], REFTABLE_HASH_SIZE_SHA1));
- check_int(reftable_record_cmp(&in[1], &in[2]), >, 0);
+ check(!reftable_record_cmp(&in[1], &in[2], &cmp));
+ check_int(cmp, >, 0);
/* comparison should be reversed for equal keys, because
* comparison is now performed on the basis of update indices */
- check_int(reftable_record_cmp(&in[0], &in[1]), <, 0);
+ check(!reftable_record_cmp(&in[0], &in[1], &cmp));
+ check_int(cmp, <, 0);
in[1].u.log.update_index = in[0].u.log.update_index;
check(reftable_record_equal(&in[0], &in[1], REFTABLE_HASH_SIZE_SHA1));
- check(!reftable_record_cmp(&in[0], &in[1]));
+ check(!reftable_record_cmp(&in[0], &in[1], &cmp));
}
static void t_reftable_log_record_compare_key(void)
@@ -396,16 +403,20 @@ static void t_reftable_obj_record_comparison(void)
.u.obj.hash_prefix_len = 5,
},
};
+ int cmp;
check(!reftable_record_equal(&in[0], &in[1], REFTABLE_HASH_SIZE_SHA1));
- check(!reftable_record_cmp(&in[0], &in[1]));
+ check(!reftable_record_cmp(&in[0], &in[1], &cmp));
+ check(!cmp);
check(!reftable_record_equal(&in[1], &in[2], REFTABLE_HASH_SIZE_SHA1));
- check_int(reftable_record_cmp(&in[1], &in[2]), >, 0);
+ check(!reftable_record_cmp(&in[1], &in[2], &cmp));
+ check_int(cmp, >, 0);
in[1].u.obj.offset_len = in[0].u.obj.offset_len;
check(reftable_record_equal(&in[0], &in[1], REFTABLE_HASH_SIZE_SHA1));
- check(!reftable_record_cmp(&in[0], &in[1]));
+ check(!reftable_record_cmp(&in[0], &in[1], &cmp));
+ check(!cmp);
}
static void t_reftable_obj_record_roundtrip(void)
@@ -486,19 +497,24 @@ static void t_reftable_index_record_comparison(void)
.u.idx.last_key = REFTABLE_BUF_INIT,
},
};
+ int cmp;
+
check(!reftable_buf_addstr(&in[0].u.idx.last_key, "refs/heads/master"));
check(!reftable_buf_addstr(&in[1].u.idx.last_key, "refs/heads/master"));
check(!reftable_buf_addstr(&in[2].u.idx.last_key, "refs/heads/branch"));
check(!reftable_record_equal(&in[0], &in[1], REFTABLE_HASH_SIZE_SHA1));
- check(!reftable_record_cmp(&in[0], &in[1]));
+ check(!reftable_record_cmp(&in[0], &in[1], &cmp));
+ check(!cmp);
check(!reftable_record_equal(&in[1], &in[2], REFTABLE_HASH_SIZE_SHA1));
- check_int(reftable_record_cmp(&in[1], &in[2]), >, 0);
+ check(!reftable_record_cmp(&in[1], &in[2], &cmp));
+ check_int(cmp, >, 0);
in[1].u.idx.offset = in[0].u.idx.offset;
check(reftable_record_equal(&in[0], &in[1], REFTABLE_HASH_SIZE_SHA1));
- check(!reftable_record_cmp(&in[0], &in[1]));
+ check(!reftable_record_cmp(&in[0], &in[1], &cmp));
+ check(!cmp);
for (size_t i = 0; i < ARRAY_SIZE(in); i++)
reftable_record_release(&in[i]);
generated by cgit v1.3-5-g45d5 (git 2.53.0) at 2026-04-17 17:12:05 +0000