In some places we need to sort reftable records by their keys to determine their ordering. This is done by first formatting the keys into a `struct strbuf` and then using `strbuf_cmp()` to compare them. This logic is needlessly roundabout and can end up costing quite a bit fo CPU cycles, both due to the allocation and formatting logic.
Introduce a new `reftable_record_cmp()` function that knows to compare two records with each other without requiring allocations.
Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
reftable/record.c | 62 ++++++++++++++++++++++++++++++++++++++++++++++-
reftable/record.h | 7 ++++++
2 files changed, 68 insertions(+), 1 deletion(-)
Show changes to 2 files +68 −1
reftable/record.c, reftable/record.h
diff --git a/reftable/record.c b/reftable/record.c
index 5c3fbb7b2a..f1b6a5eac9 100644
--- a/reftable/record.c
+++ b/reftable/record.c
@@ -430,7 +430,6 @@ static int reftable_ref_record_is_deletion_void(const void *p)
(const struct reftable_ref_record *)p);
}
-
static int reftable_ref_record_equal_void(const void *a,
const void *b, int hash_size)
{
@@ -439,6 +438,13 @@ static int reftable_ref_record_equal_void(const void *a,
return reftable_ref_record_equal(ra, rb, hash_size);
}
+static int reftable_ref_record_cmp_void(const void *_a, const void *_b)
+{
+ const struct reftable_ref_record *a = _a;
+ const struct reftable_ref_record *b = _b;
+ return strcmp(a->refname, b->refname);
+}
+
static void reftable_ref_record_print_void(const void *rec,
int hash_size)
{
@@ -455,6 +461,7 @@ static struct reftable_record_vtable reftable_ref_record_vtable = {
.release = &reftable_ref_record_release_void,
.is_deletion = &reftable_ref_record_is_deletion_void,
.equal = &reftable_ref_record_equal_void,
+ .cmp = &reftable_ref_record_cmp_void,
.print = &reftable_ref_record_print_void,
};
@@ -625,6 +632,25 @@ static int reftable_obj_record_equal_void(const void *a, const void *b, int hash
return 1;
}
+static int reftable_obj_record_cmp_void(const void *_a, const void *_b)
+{
+ const struct reftable_obj_record *a = _a;
+ const struct reftable_obj_record *b = _b;
+ int cmp;
+
+ cmp = memcmp(a->hash_prefix, b->hash_prefix,
+ a->hash_prefix_len > b->hash_prefix_len ?
+ a->hash_prefix_len : b->hash_prefix_len);
+ if (cmp)
+ return cmp;
+
+ /*
+ * When the prefix is the same then the object record that is longer is
+ * considered to be bigger.
+ */
+ return a->hash_prefix_len - b->hash_prefix_len;
+}
+
static struct reftable_record_vtable reftable_obj_record_vtable = {
.key = &reftable_obj_record_key,
.type = BLOCK_TYPE_OBJ,
@@ -635,6 +661,7 @@ static struct reftable_record_vtable reftable_obj_record_vtable = {
.release = &reftable_obj_record_release,
.is_deletion = ¬_a_deletion,
.equal = &reftable_obj_record_equal_void,
+ .cmp = &reftable_obj_record_cmp_void,
.print = &reftable_obj_record_print,
};
@@ -953,6 +980,22 @@ static int reftable_log_record_equal_void(const void *a,
hash_size);
}
+static int reftable_log_record_cmp_void(const void *_a, const void *_b)
+{
+ const struct reftable_log_record *a = _a;
+ const struct reftable_log_record *b = _b;
+ int cmp = strcmp(a->refname, b->refname);
+ if (cmp)
+ return cmp;
+
+ /*
+ * Note that the comparison here is reversed. This is because the
+ * update index is reversed when comparing keys. For reference, see how
+ * we handle this in reftable_log_record_key()`.
+ */
+ return b->update_index - a->update_index;
+}
+
int reftable_log_record_equal(const struct reftable_log_record *a,
const struct reftable_log_record *b, int hash_size)
{
@@ -1002,6 +1045,7 @@ static struct reftable_record_vtable reftable_log_record_vtable = {
.release = &reftable_log_record_release_void,
.is_deletion = &reftable_log_record_is_deletion_void,
.equal = &reftable_log_record_equal_void,
+ .cmp = &reftable_log_record_cmp_void,
.print = &reftable_log_record_print_void,
};
@@ -1077,6 +1121,13 @@ static int reftable_index_record_equal(const void *a, const void *b, int hash_si
return ia->offset == ib->offset && !strbuf_cmp(&ia->last_key, &ib->last_key);
}
+static int reftable_index_record_cmp(const void *_a, const void *_b)
+{
+ const struct reftable_index_record *a = _a;
+ const struct reftable_index_record *b = _b;
+ return strbuf_cmp(&a->last_key, &b->last_key);
+}
+
static void reftable_index_record_print(const void *rec, int hash_size)
{
const struct reftable_index_record *idx = rec;
@@ -1094,6 +1145,7 @@ static struct reftable_record_vtable reftable_index_record_vtable = {
.release = &reftable_index_record_release,
.is_deletion = ¬_a_deletion,
.equal = &reftable_index_record_equal,
+ .cmp = &reftable_index_record_cmp,
.print = &reftable_index_record_print,
};
@@ -1147,6 +1199,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)
+{
+ 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));
+}
+
int reftable_record_equal(struct reftable_record *a, struct reftable_record *b, int hash_size)
{
if (a->type != b->type)
diff --git a/reftable/record.h b/reftable/record.h
index fd80cd451d..0d96fbfd1b 100644
--- a/reftable/record.h
+++ b/reftable/record.h
@@ -62,6 +62,12 @@ struct reftable_record_vtable {
/* Are two records equal? This assumes they have the same type. Returns 0 for non-equal. */
int (*equal)(const void *a, const void *b, int hash_size);
+ /*
+ * Compare keys of two records with each other. The records must have
+ * the same type.
+ */
+ int (*cmp)(const void *a, const void *b);
+
/* Print on stdout, for debugging. */
void (*print)(const void *rec, int hash_size);
};
@@ -114,6 +120,7 @@ struct reftable_record {
};
/* see struct record_vtable */
+int reftable_record_cmp(struct reftable_record *a, struct reftable_record *b);
int reftable_record_equal(struct reftable_record *a, struct reftable_record *b, int hash_size);
void reftable_record_print(struct reftable_record *rec, int hash_size);
void reftable_record_key(struct reftable_record *rec, struct strbuf *dest);
Patrick Steinhardt
