8 files changed, 935 insertions, 8 deletions
diff --git a/t/unit-tests/lib-oid.c b/t/unit-tests/lib-oid.c
new file mode 100644
index 0000000000..37105f0a8f
--- /dev/null
+++ b/t/unit-tests/lib-oid.c
@@ -0,0 +1,52 @@
+#include "test-lib.h"
+#include "lib-oid.h"
+#include "strbuf.h"
+#include "hex.h"
+
+static int init_hash_algo(void)
+{
+	static int algo = -1;
+
+	if (algo < 0) {
+		const char *algo_name = getenv("GIT_TEST_DEFAULT_HASH");
+		algo = algo_name ? hash_algo_by_name(algo_name) : GIT_HASH_SHA1;
+
+		if (!check(algo != GIT_HASH_UNKNOWN))
+			test_msg("BUG: invalid GIT_TEST_DEFAULT_HASH value ('%s')",
+				 algo_name);
+	}
+	return algo;
+}
+
+static int get_oid_arbitrary_hex_algop(const char *hex, struct object_id *oid,
+				       const struct git_hash_algo *algop)
+{
+	int ret;
+	size_t sz = strlen(hex);
+	struct strbuf buf = STRBUF_INIT;
+
+	if (!check(sz <= algop->hexsz)) {
+		test_msg("BUG: hex string (%s) bigger than maximum allowed (%lu)",
+			 hex, (unsigned long)algop->hexsz);
+		return -1;
+	}
+
+	strbuf_add(&buf, hex, sz);
+	strbuf_addchars(&buf, '0', algop->hexsz - sz);
+
+	ret = get_oid_hex_algop(buf.buf, oid, algop);
+	if (!check_int(ret, ==, 0))
+		test_msg("BUG: invalid hex input (%s) provided", hex);
+
+	strbuf_release(&buf);
+	return ret;
+}
+
+int get_oid_arbitrary_hex(const char *hex, struct object_id *oid)
+{
+	int hash_algo = init_hash_algo();
+
+	if (!check_int(hash_algo, !=, GIT_HASH_UNKNOWN))
+		return -1;
+	return get_oid_arbitrary_hex_algop(hex, oid, &hash_algos[hash_algo]);
+}
diff --git a/t/unit-tests/lib-oid.h b/t/unit-tests/lib-oid.h
new file mode 100644
index 0000000000..8d2acca768
--- /dev/null
+++ b/t/unit-tests/lib-oid.h
@@ -0,0 +1,17 @@
+#ifndef LIB_OID_H
+#define LIB_OID_H
+
+#include "hash.h"
+
+/*
+ * Convert arbitrary hex string to object_id.
+ * For example, passing "abc12" will generate
+ * "abc1200000000000000000000000000000000000" hex of length 40 for SHA-1 and
+ * create object_id with that.
+ * WARNING: passing a string of length more than the hexsz of respective hash
+ * algo is not allowed. The hash algo is decided based on GIT_TEST_DEFAULT_HASH
+ * environment variable.
+ */
+int get_oid_arbitrary_hex(const char *s, struct object_id *oid);
+
+#endif /* LIB_OID_H */
diff --git a/t/unit-tests/t-example-decorate.c b/t/unit-tests/t-example-decorate.c
index 3c856a8cf2..a4a75db735 100644
--- a/t/unit-tests/t-example-decorate.c
+++ b/t/unit-tests/t-example-decorate.c
@@ -1,3 +1,5 @@
+#define USE_THE_REPOSITORY_VARIABLE
+
 #include "test-lib.h"
 #include "object.h"
 #include "decorate.h"
diff --git a/t/unit-tests/t-oidmap.c b/t/unit-tests/t-oidmap.c
new file mode 100644
index 0000000000..b22e52d08b
--- /dev/null
+++ b/t/unit-tests/t-oidmap.c
@@ -0,0 +1,181 @@
+#include "test-lib.h"
+#include "lib-oid.h"
+#include "oidmap.h"
+#include "hash.h"
+#include "hex.h"
+
+/*
+ * Elements we will put in oidmap structs are made of a key: the entry.oid
+ * field, which is of type struct object_id, and a value: the name field (could
+ * be a refname for example).
+ */
+struct test_entry {
+	struct oidmap_entry entry;
+	char name[FLEX_ARRAY];
+};
+
+static const char *const key_val[][2] = { { "11", "one" },
+					  { "22", "two" },
+					  { "33", "three" } };
+
+static void setup(void (*f)(struct oidmap *map))
+{
+	struct oidmap map = OIDMAP_INIT;
+	int ret = 0;
+
+	for (size_t i = 0; i < ARRAY_SIZE(key_val); i++){
+		struct test_entry *entry;
+
+		FLEX_ALLOC_STR(entry, name, key_val[i][1]);
+		if ((ret = get_oid_arbitrary_hex(key_val[i][0], &entry->entry.oid))) {
+			free(entry);
+			break;
+		}
+		entry = oidmap_put(&map, entry);
+		if (!check(entry == NULL))
+			free(entry);
+	}
+
+	if (!ret)
+		f(&map);
+	oidmap_free(&map, 1);
+}
+
+static void t_replace(struct oidmap *map)
+{
+	struct test_entry *entry, *prev;
+
+	FLEX_ALLOC_STR(entry, name, "un");
+	if (get_oid_arbitrary_hex("11", &entry->entry.oid))
+		return;
+	prev = oidmap_put(map, entry);
+	if (!check(prev != NULL))
+		return;
+	check_str(prev->name, "one");
+	free(prev);
+
+	FLEX_ALLOC_STR(entry, name, "deux");
+	if (get_oid_arbitrary_hex("22", &entry->entry.oid))
+		return;
+	prev = oidmap_put(map, entry);
+	if (!check(prev != NULL))
+		return;
+	check_str(prev->name, "two");
+	free(prev);
+}
+
+static void t_get(struct oidmap *map)
+{
+	struct test_entry *entry;
+	struct object_id oid;
+
+	if (get_oid_arbitrary_hex("22", &oid))
+		return;
+	entry = oidmap_get(map, &oid);
+	if (!check(entry != NULL))
+		return;
+	check_str(entry->name, "two");
+
+	if (get_oid_arbitrary_hex("44", &oid))
+		return;
+	check(oidmap_get(map, &oid) == NULL);
+
+	if (get_oid_arbitrary_hex("11", &oid))
+		return;
+	entry = oidmap_get(map, &oid);
+	if (!check(entry != NULL))
+		return;
+	check_str(entry->name, "one");
+}
+
+static void t_remove(struct oidmap *map)
+{
+	struct test_entry *entry;
+	struct object_id oid;
+
+	if (get_oid_arbitrary_hex("11", &oid))
+		return;
+	entry = oidmap_remove(map, &oid);
+	if (!check(entry != NULL))
+		return;
+	check_str(entry->name, "one");
+	check(oidmap_get(map, &oid) == NULL);
+	free(entry);
+
+	if (get_oid_arbitrary_hex("22", &oid))
+		return;
+	entry = oidmap_remove(map, &oid);
+	if (!check(entry != NULL))
+		return;
+	check_str(entry->name, "two");
+	check(oidmap_get(map, &oid) == NULL);
+	free(entry);
+
+	if (get_oid_arbitrary_hex("44", &oid))
+		return;
+	check(oidmap_remove(map, &oid) == NULL);
+}
+
+static int key_val_contains(struct test_entry *entry, char seen[])
+{
+	for (size_t i = 0; i < ARRAY_SIZE(key_val); i++) {
+		struct object_id oid;
+
+		if (get_oid_arbitrary_hex(key_val[i][0], &oid))
+			return -1;
+
+		if (oideq(&entry->entry.oid, &oid)) {
+			if (seen[i])
+				return 2;
+			seen[i] = 1;
+			return 0;
+		}
+	}
+	return 1;
+}
+
+static void t_iterate(struct oidmap *map)
+{
+	struct oidmap_iter iter;
+	struct test_entry *entry;
+	char seen[ARRAY_SIZE(key_val)] = { 0 };
+	int count = 0;
+
+	oidmap_iter_init(map, &iter);
+	while ((entry = oidmap_iter_next(&iter))) {
+		int ret;
+		if (!check_int((ret = key_val_contains(entry, seen)), ==, 0)) {
+			switch (ret) {
+			case -1:
+				break; /* error message handled by get_oid_arbitrary_hex() */
+			case 1:
+				test_msg("obtained entry was not given in the input\n"
+					 "  name: %s\n   oid: %s\n",
+					 entry->name, oid_to_hex(&entry->entry.oid));
+				break;
+			case 2:
+				test_msg("duplicate entry detected\n"
+					 "  name: %s\n   oid: %s\n",
+					 entry->name, oid_to_hex(&entry->entry.oid));
+				break;
+			default:
+				test_msg("BUG: invalid return value (%d) from key_val_contains()",
+					 ret);
+				break;
+			}
+		} else {
+			count++;
+		}
+	}
+	check_int(count, ==, ARRAY_SIZE(key_val));
+	check_int(hashmap_get_size(&map->map), ==, ARRAY_SIZE(key_val));
+}
+
+int cmd_main(int argc UNUSED, const char **argv UNUSED)
+{
+	TEST(setup(t_replace), "replace works");
+	TEST(setup(t_get), "get works");
+	TEST(setup(t_remove), "remove works");
+	TEST(setup(t_iterate), "iterate works");
+	return test_done();
+}
diff --git a/t/unit-tests/t-oidtree.c b/t/unit-tests/t-oidtree.c
new file mode 100644
index 0000000000..a38754b066
--- /dev/null
+++ b/t/unit-tests/t-oidtree.c
@@ -0,0 +1,122 @@
+#include "test-lib.h"
+#include "lib-oid.h"
+#include "oidtree.h"
+#include "hash.h"
+#include "hex.h"
+#include "strvec.h"
+
+#define FILL_TREE(tree, ...)                                       \
+	do {                                                       \
+		const char *hexes[] = { __VA_ARGS__ };             \
+		if (fill_tree_loc(tree, hexes, ARRAY_SIZE(hexes))) \
+			return;                                    \
+	} while (0)
+
+static int fill_tree_loc(struct oidtree *ot, const char *hexes[], size_t n)
+{
+	for (size_t i = 0; i < n; i++) {
+		struct object_id oid;
+		if (!check_int(get_oid_arbitrary_hex(hexes[i], &oid), ==, 0))
+			return -1;
+		oidtree_insert(ot, &oid);
+	}
+	return 0;
+}
+
+static void check_contains(struct oidtree *ot, const char *hex, int expected)
+{
+	struct object_id oid;
+
+	if (!check_int(get_oid_arbitrary_hex(hex, &oid), ==, 0))
+		return;
+	if (!check_int(oidtree_contains(ot, &oid), ==, expected))
+		test_msg("oid: %s", oid_to_hex(&oid));
+}
+
+struct expected_hex_iter {
+	size_t i;
+	struct strvec expected_hexes;
+	const char *query;
+};
+
+static enum cb_next check_each_cb(const struct object_id *oid, void *data)
+{
+	struct expected_hex_iter *hex_iter = data;
+	struct object_id expected;
+
+	if (!check_int(hex_iter->i, <, hex_iter->expected_hexes.nr)) {
+		test_msg("error: extraneous callback for query: ('%s'), object_id: ('%s')",
+			 hex_iter->query, oid_to_hex(oid));
+		return CB_BREAK;
+	}
+
+	if (!check_int(get_oid_arbitrary_hex(hex_iter->expected_hexes.v[hex_iter->i],
+					     &expected), ==, 0))
+		; /* the data is bogus and cannot be used */
+	else if (!check(oideq(oid, &expected)))
+		test_msg("expected: %s\n       got: %s\n     query: %s",
+			 oid_to_hex(&expected), oid_to_hex(oid), hex_iter->query);
+
+	hex_iter->i += 1;
+	return CB_CONTINUE;
+}
+
+LAST_ARG_MUST_BE_NULL
+static void check_each(struct oidtree *ot, const char *query, ...)
+{
+	struct object_id oid;
+	struct expected_hex_iter hex_iter = { .expected_hexes = STRVEC_INIT,
+					      .query = query };
+	const char *arg;
+	va_list hex_args;
+
+	va_start(hex_args, query);
+	while ((arg = va_arg(hex_args, const char *)))
+		strvec_push(&hex_iter.expected_hexes, arg);
+	va_end(hex_args);
+
+	if (!check_int(get_oid_arbitrary_hex(query, &oid), ==, 0))
+		return;
+	oidtree_each(ot, &oid, strlen(query), check_each_cb, &hex_iter);
+
+	if (!check_int(hex_iter.i, ==, hex_iter.expected_hexes.nr))
+		test_msg("error: could not find some 'object_id's for query ('%s')", query);
+	strvec_clear(&hex_iter.expected_hexes);
+}
+
+static void setup(void (*f)(struct oidtree *ot))
+{
+	struct oidtree ot;
+
+	oidtree_init(&ot);
+	f(&ot);
+	oidtree_clear(&ot);
+}
+
+static void t_contains(struct oidtree *ot)
+{
+	FILL_TREE(ot, "444", "1", "2", "3", "4", "5", "a", "b", "c", "d", "e");
+	check_contains(ot, "44", 0);
+	check_contains(ot, "441", 0);
+	check_contains(ot, "440", 0);
+	check_contains(ot, "444", 1);
+	check_contains(ot, "4440", 1);
+	check_contains(ot, "4444", 0);
+}
+
+static void t_each(struct oidtree *ot)
+{
+	FILL_TREE(ot, "f", "9", "8", "123", "321", "320", "a", "b", "c", "d", "e");
+	check_each(ot, "12300", "123", NULL);
+	check_each(ot, "3211", NULL); /* should not reach callback */
+	check_each(ot, "3210", "321", NULL);
+	check_each(ot, "32100", "321", NULL);
+	check_each(ot, "32", "320", "321", NULL);
+}
+
+int cmd_main(int argc UNUSED, const char **argv UNUSED)
+{
+	TEST(setup(t_contains), "oidtree insert and contains works");
+	TEST(setup(t_each), "oidtree each works");
+	return test_done();
+}
diff --git a/t/unit-tests/t-reftable-basics.c b/t/unit-tests/t-reftable-basics.c
index 529049af12..4e80bdf16d 100644
--- a/t/unit-tests/t-reftable-basics.c
+++ b/t/unit-tests/t-reftable-basics.c
@@ -54,15 +54,15 @@ static void test_binsearch(void)
 
 static void test_names_length(void)
 {
-	char *a[] = { "a", "b", NULL };
+	const char *a[] = { "a", "b", NULL };
 	check_int(names_length(a), ==, 2);
 }
 
 static void test_names_equal(void)
 {
-	char *a[] = { "a", "b", "c", NULL };
-	char *b[] = { "a", "b", "d", NULL };
-	char *c[] = { "a", "b", NULL };
+	const char *a[] = { "a", "b", "c", NULL };
+	const char *b[] = { "a", "b", "d", NULL };
+	const char *c[] = { "a", "b", NULL };
 
 	check(names_equal(a, a));
 	check(!names_equal(a, b));
diff --git a/t/unit-tests/t-reftable-record.c b/t/unit-tests/t-reftable-record.c
new file mode 100644
index 0000000000..cb649ee419
--- /dev/null
+++ b/t/unit-tests/t-reftable-record.c
@@ -0,0 +1,551 @@
+/*
+  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/record.h"
+
+static void t_copy(struct reftable_record *rec)
+{
+	struct reftable_record copy;
+	uint8_t typ;
+
+	typ = reftable_record_type(rec);
+	reftable_record_init(&copy, typ);
+	reftable_record_copy_from(&copy, rec, GIT_SHA1_RAWSZ);
+	/* do it twice to catch memory leaks */
+	reftable_record_copy_from(&copy, rec, GIT_SHA1_RAWSZ);
+	check(reftable_record_equal(rec, &copy, GIT_SHA1_RAWSZ));
+
+	reftable_record_release(&copy);
+}
+
+static void t_varint_roundtrip(void)
+{
+	uint64_t inputs[] = { 0,
+			      1,
+			      27,
+			      127,
+			      128,
+			      257,
+			      4096,
+			      ((uint64_t)1 << 63),
+			      ((uint64_t)1 << 63) + ((uint64_t)1 << 63) - 1 };
+
+	for (size_t i = 0; i < ARRAY_SIZE(inputs); i++) {
+		uint8_t dest[10];
+
+		struct string_view out = {
+			.buf = dest,
+			.len = sizeof(dest),
+		};
+		uint64_t in = inputs[i];
+		int n = put_var_int(&out, in);
+		uint64_t got = 0;
+
+		check_int(n, >, 0);
+		out.len = n;
+		n = get_var_int(&got, &out);
+		check_int(n, >, 0);
+
+		check_int(got, ==, in);
+	}
+}
+
+static void set_hash(uint8_t *h, int j)
+{
+	for (int i = 0; i < hash_size(GIT_SHA1_FORMAT_ID); i++)
+		h[i] = (j >> i) & 0xff;
+}
+
+static void t_reftable_ref_record_comparison(void)
+{
+	struct reftable_record in[3] = {
+		{
+			.type = BLOCK_TYPE_REF,
+			.u.ref.refname = (char *) "refs/heads/master",
+			.u.ref.value_type = REFTABLE_REF_VAL1,
+		},
+		{
+			.type = BLOCK_TYPE_REF,
+			.u.ref.refname = (char *) "refs/heads/master",
+			.u.ref.value_type = REFTABLE_REF_DELETION,
+		},
+		{
+			.type = BLOCK_TYPE_REF,
+			.u.ref.refname = (char *) "HEAD",
+			.u.ref.value_type = REFTABLE_REF_SYMREF,
+			.u.ref.value.symref = (char *) "refs/heads/master",
+		},
+	};
+
+	check(!reftable_record_equal(&in[0], &in[1], GIT_SHA1_RAWSZ));
+	check(!reftable_record_cmp(&in[0], &in[1]));
+
+	check(!reftable_record_equal(&in[1], &in[2], GIT_SHA1_RAWSZ));
+	check_int(reftable_record_cmp(&in[1], &in[2]), >, 0);
+
+	in[1].u.ref.value_type = in[0].u.ref.value_type;
+	check(reftable_record_equal(&in[0], &in[1], GIT_SHA1_RAWSZ));
+	check(!reftable_record_cmp(&in[0], &in[1]));
+}
+
+static void t_reftable_ref_record_compare_name(void)
+{
+	struct reftable_ref_record recs[3] = {
+		{
+			.refname = (char *) "refs/heads/a"
+		},
+		{
+			.refname = (char *) "refs/heads/b"
+		},
+		{
+			.refname = (char *) "refs/heads/a"
+		},
+	};
+
+	check_int(reftable_ref_record_compare_name(&recs[0], &recs[1]), <, 0);
+	check_int(reftable_ref_record_compare_name(&recs[1], &recs[0]), >, 0);
+	check_int(reftable_ref_record_compare_name(&recs[0], &recs[2]), ==, 0);
+}
+
+static void t_reftable_ref_record_roundtrip(void)
+{
+	struct strbuf scratch = STRBUF_INIT;
+
+	for (int i = REFTABLE_REF_DELETION; i < REFTABLE_NR_REF_VALUETYPES; i++) {
+		struct reftable_record in = {
+			.type = BLOCK_TYPE_REF,
+			.u.ref.value_type = i,
+		};
+		struct reftable_record out = { .type = BLOCK_TYPE_REF };
+		struct strbuf key = STRBUF_INIT;
+		uint8_t buffer[1024] = { 0 };
+		struct string_view dest = {
+			.buf = buffer,
+			.len = sizeof(buffer),
+		};
+		int n, m;
+
+		in.u.ref.value_type = i;
+		switch (i) {
+		case REFTABLE_REF_DELETION:
+			break;
+		case REFTABLE_REF_VAL1:
+			set_hash(in.u.ref.value.val1, 1);
+			break;
+		case REFTABLE_REF_VAL2:
+			set_hash(in.u.ref.value.val2.value, 1);
+			set_hash(in.u.ref.value.val2.target_value, 2);
+			break;
+		case REFTABLE_REF_SYMREF:
+			in.u.ref.value.symref = xstrdup("target");
+			break;
+		}
+		in.u.ref.refname = xstrdup("refs/heads/master");
+
+		t_copy(&in);
+
+		check_int(reftable_record_val_type(&in), ==, i);
+		check_int(reftable_record_is_deletion(&in), ==, i == REFTABLE_REF_DELETION);
+
+		reftable_record_key(&in, &key);
+		n = reftable_record_encode(&in, dest, GIT_SHA1_RAWSZ);
+		check_int(n, >, 0);
+
+		/* decode into a non-zero reftable_record to test for leaks. */
+		m = reftable_record_decode(&out, key, i, dest, GIT_SHA1_RAWSZ, &scratch);
+		check_int(n, ==, m);
+
+		check(reftable_ref_record_equal(&in.u.ref, &out.u.ref,
+						 GIT_SHA1_RAWSZ));
+		reftable_record_release(&in);
+
+		strbuf_release(&key);
+		reftable_record_release(&out);
+	}
+
+	strbuf_release(&scratch);
+}
+
+static void t_reftable_log_record_comparison(void)
+{
+	struct reftable_record in[3] = {
+		{
+			.type = BLOCK_TYPE_LOG,
+			.u.log.refname = (char *) "refs/heads/master",
+			.u.log.update_index = 42,
+		},
+		{
+			.type = BLOCK_TYPE_LOG,
+			.u.log.refname = (char *) "refs/heads/master",
+			.u.log.update_index = 22,
+		},
+		{
+			.type = BLOCK_TYPE_LOG,
+			.u.log.refname = (char *) "refs/heads/main",
+			.u.log.update_index = 22,
+		},
+	};
+
+	check(!reftable_record_equal(&in[0], &in[1], GIT_SHA1_RAWSZ));
+	check(!reftable_record_equal(&in[1], &in[2], GIT_SHA1_RAWSZ));
+	check_int(reftable_record_cmp(&in[1], &in[2]), >, 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);
+
+	in[1].u.log.update_index = in[0].u.log.update_index;
+	check(reftable_record_equal(&in[0], &in[1], GIT_SHA1_RAWSZ));
+	check(!reftable_record_cmp(&in[0], &in[1]));
+}
+
+static void t_reftable_log_record_compare_key(void)
+{
+	struct reftable_log_record logs[3] = {
+		{
+			.refname = (char *) "refs/heads/a",
+			.update_index = 1,
+		},
+		{
+			.refname = (char *) "refs/heads/b",
+			.update_index = 2,
+		},
+		{
+			.refname = (char *) "refs/heads/a",
+			.update_index = 3,
+		},
+	};
+
+	check_int(reftable_log_record_compare_key(&logs[0], &logs[1]), <, 0);
+	check_int(reftable_log_record_compare_key(&logs[1], &logs[0]), >, 0);
+
+	logs[1].update_index = logs[0].update_index;
+	check_int(reftable_log_record_compare_key(&logs[0], &logs[1]), <, 0);
+
+	check_int(reftable_log_record_compare_key(&logs[0], &logs[2]), >, 0);
+	check_int(reftable_log_record_compare_key(&logs[2], &logs[0]), <, 0);
+	logs[2].update_index = logs[0].update_index;
+	check_int(reftable_log_record_compare_key(&logs[0], &logs[2]), ==, 0);
+}
+
+static void t_reftable_log_record_roundtrip(void)
+{
+	struct reftable_log_record in[] = {
+		{
+			.refname = xstrdup("refs/heads/master"),
+			.update_index = 42,
+			.value_type = REFTABLE_LOG_UPDATE,
+			.value = {
+				.update = {
+					.name = xstrdup("han-wen"),
+					.email = xstrdup("hanwen@google.com"),
+					.message = xstrdup("test"),
+					.time = 1577123507,
+					.tz_offset = 100,
+				},
+			}
+		},
+		{
+			.refname = xstrdup("refs/heads/master"),
+			.update_index = 22,
+			.value_type = REFTABLE_LOG_DELETION,
+		},
+		{
+			.refname = xstrdup("branch"),
+			.update_index = 33,
+			.value_type = REFTABLE_LOG_UPDATE,
+		}
+	};
+	struct strbuf scratch = STRBUF_INIT;
+	set_hash(in[0].value.update.new_hash, 1);
+	set_hash(in[0].value.update.old_hash, 2);
+	set_hash(in[2].value.update.new_hash, 3);
+	set_hash(in[2].value.update.old_hash, 4);
+
+	check(!reftable_log_record_is_deletion(&in[0]));
+	check(reftable_log_record_is_deletion(&in[1]));
+	check(!reftable_log_record_is_deletion(&in[2]));
+
+	for (size_t i = 0; i < ARRAY_SIZE(in); i++) {
+		struct reftable_record rec = { .type = BLOCK_TYPE_LOG };
+		struct strbuf key = STRBUF_INIT;
+		uint8_t buffer[1024] = { 0 };
+		struct string_view dest = {
+			.buf = buffer,
+			.len = sizeof(buffer),
+		};
+		/* populate out, to check for leaks. */
+		struct reftable_record out = {
+			.type = BLOCK_TYPE_LOG,
+			.u.log = {
+				.refname = xstrdup("old name"),
+				.value_type = REFTABLE_LOG_UPDATE,
+				.value = {
+					.update = {
+						.name = xstrdup("old name"),
+						.email = xstrdup("old@email"),
+						.message = xstrdup("old message"),
+					},
+				},
+			},
+		};
+		int n, m, valtype;
+
+		rec.u.log = in[i];
+
+		t_copy(&rec);
+
+		reftable_record_key(&rec, &key);
+
+		n = reftable_record_encode(&rec, dest, GIT_SHA1_RAWSZ);
+		check_int(n, >=, 0);
+		valtype = reftable_record_val_type(&rec);
+		m = reftable_record_decode(&out, key, valtype, dest,
+					   GIT_SHA1_RAWSZ, &scratch);
+		check_int(n, ==, m);
+
+		check(reftable_log_record_equal(&in[i], &out.u.log,
+						 GIT_SHA1_RAWSZ));
+		reftable_log_record_release(&in[i]);
+		strbuf_release(&key);
+		reftable_record_release(&out);
+	}
+
+	strbuf_release(&scratch);
+}
+
+static void t_key_roundtrip(void)
+{
+	uint8_t buffer[1024] = { 0 };
+	struct string_view dest = {
+		.buf = buffer,
+		.len = sizeof(buffer),
+	};
+	struct strbuf last_key = STRBUF_INIT;
+	struct strbuf key = STRBUF_INIT;
+	struct strbuf roundtrip = STRBUF_INIT;
+	int restart;
+	uint8_t extra;
+	int n, m;
+	uint8_t rt_extra;
+
+	strbuf_addstr(&last_key, "refs/heads/master");
+	strbuf_addstr(&key, "refs/tags/bla");
+	extra = 6;
+	n = reftable_encode_key(&restart, dest, last_key, key, extra);
+	check(!restart);
+	check_int(n, >, 0);
+
+	strbuf_addstr(&roundtrip, "refs/heads/master");
+	m = reftable_decode_key(&roundtrip, &rt_extra, dest);
+	check_int(n, ==, m);
+	check(!strbuf_cmp(&key, &roundtrip));
+	check_int(rt_extra, ==, extra);
+
+	strbuf_release(&last_key);
+	strbuf_release(&key);
+	strbuf_release(&roundtrip);
+}
+
+static void t_reftable_obj_record_comparison(void)
+{
+
+	uint8_t id_bytes[] = { 0, 1, 2, 3, 4, 5, 6 };
+	uint64_t offsets[] = { 0, 16, 32, 48, 64, 80, 96, 112};
+	struct reftable_record in[3] = {
+		{
+			.type = BLOCK_TYPE_OBJ,
+			.u.obj.hash_prefix = id_bytes,
+			.u.obj.hash_prefix_len = 7,
+			.u.obj.offsets = offsets,
+			.u.obj.offset_len = 8,
+		},
+		{
+			.type = BLOCK_TYPE_OBJ,
+			.u.obj.hash_prefix = id_bytes,
+			.u.obj.hash_prefix_len = 7,
+			.u.obj.offsets = offsets,
+			.u.obj.offset_len = 5,
+		},
+		{
+			.type = BLOCK_TYPE_OBJ,
+			.u.obj.hash_prefix = id_bytes,
+			.u.obj.hash_prefix_len = 5,
+		},
+	};
+
+	check(!reftable_record_equal(&in[0], &in[1], GIT_SHA1_RAWSZ));
+	check(!reftable_record_cmp(&in[0], &in[1]));
+
+	check(!reftable_record_equal(&in[1], &in[2], GIT_SHA1_RAWSZ));
+	check_int(reftable_record_cmp(&in[1], &in[2]), >, 0);
+
+	in[1].u.obj.offset_len = in[0].u.obj.offset_len;
+	check(reftable_record_equal(&in[0], &in[1], GIT_SHA1_RAWSZ));
+	check(!reftable_record_cmp(&in[0], &in[1]));
+}
+
+static void t_reftable_obj_record_roundtrip(void)
+{
+	uint8_t testHash1[GIT_SHA1_RAWSZ] = { 1, 2, 3, 4, 0 };
+	uint64_t till9[] = { 1, 2, 3, 4, 500, 600, 700, 800, 9000 };
+	struct reftable_obj_record recs[3] = {
+		{
+			.hash_prefix = testHash1,
+			.hash_prefix_len = 5,
+			.offsets = till9,
+			.offset_len = 3,
+		},
+		{
+			.hash_prefix = testHash1,
+			.hash_prefix_len = 5,
+			.offsets = till9,
+			.offset_len = 9,
+		},
+		{
+			.hash_prefix = testHash1,
+			.hash_prefix_len = 5,
+		},
+	};
+	struct strbuf scratch = STRBUF_INIT;
+
+	for (size_t i = 0; i < ARRAY_SIZE(recs); i++) {
+		uint8_t buffer[1024] = { 0 };
+		struct string_view dest = {
+			.buf = buffer,
+			.len = sizeof(buffer),
+		};
+		struct reftable_record in = {
+			.type = BLOCK_TYPE_OBJ,
+			.u = {
+				.obj = recs[i],
+			},
+		};
+		struct strbuf key = STRBUF_INIT;
+		struct reftable_record out = { .type = BLOCK_TYPE_OBJ };
+		int n, m;
+		uint8_t extra;
+
+		check(!reftable_record_is_deletion(&in));
+		t_copy(&in);
+		reftable_record_key(&in, &key);
+		n = reftable_record_encode(&in, dest, GIT_SHA1_RAWSZ);
+		check_int(n, >, 0);
+		extra = reftable_record_val_type(&in);
+		m = reftable_record_decode(&out, key, extra, dest,
+					   GIT_SHA1_RAWSZ, &scratch);
+		check_int(n, ==, m);
+
+		check(reftable_record_equal(&in, &out, GIT_SHA1_RAWSZ));
+		strbuf_release(&key);
+		reftable_record_release(&out);
+	}
+
+	strbuf_release(&scratch);
+}
+
+static void t_reftable_index_record_comparison(void)
+{
+	struct reftable_record in[3] = {
+		{
+			.type = BLOCK_TYPE_INDEX,
+			.u.idx.offset = 22,
+			.u.idx.last_key = STRBUF_INIT,
+		},
+		{
+			.type = BLOCK_TYPE_INDEX,
+			.u.idx.offset = 32,
+			.u.idx.last_key = STRBUF_INIT,
+		},
+		{
+			.type = BLOCK_TYPE_INDEX,
+			.u.idx.offset = 32,
+			.u.idx.last_key = STRBUF_INIT,
+		},
+	};
+	strbuf_addstr(&in[0].u.idx.last_key, "refs/heads/master");
+	strbuf_addstr(&in[1].u.idx.last_key, "refs/heads/master");
+	strbuf_addstr(&in[2].u.idx.last_key, "refs/heads/branch");
+
+	check(!reftable_record_equal(&in[0], &in[1], GIT_SHA1_RAWSZ));
+	check(!reftable_record_cmp(&in[0], &in[1]));
+
+	check(!reftable_record_equal(&in[1], &in[2], GIT_SHA1_RAWSZ));
+	check_int(reftable_record_cmp(&in[1], &in[2]), >, 0);
+
+	in[1].u.idx.offset = in[0].u.idx.offset;
+	check(reftable_record_equal(&in[0], &in[1], GIT_SHA1_RAWSZ));
+	check(!reftable_record_cmp(&in[0], &in[1]));
+
+	for (size_t i = 0; i < ARRAY_SIZE(in); i++)
+		reftable_record_release(&in[i]);
+}
+
+static void t_reftable_index_record_roundtrip(void)
+{
+	struct reftable_record in = {
+		.type = BLOCK_TYPE_INDEX,
+		.u.idx = {
+			.offset = 42,
+			.last_key = STRBUF_INIT,
+		},
+	};
+	uint8_t buffer[1024] = { 0 };
+	struct string_view dest = {
+		.buf = buffer,
+		.len = sizeof(buffer),
+	};
+	struct strbuf scratch = STRBUF_INIT;
+	struct strbuf key = STRBUF_INIT;
+	struct reftable_record out = {
+		.type = BLOCK_TYPE_INDEX,
+		.u.idx = { .last_key = STRBUF_INIT },
+	};
+	int n, m;
+	uint8_t extra;
+
+	strbuf_addstr(&in.u.idx.last_key, "refs/heads/master");
+	reftable_record_key(&in, &key);
+	t_copy(&in);
+
+	check(!reftable_record_is_deletion(&in));
+	check(!strbuf_cmp(&key, &in.u.idx.last_key));
+	n = reftable_record_encode(&in, dest, GIT_SHA1_RAWSZ);
+	check_int(n, >, 0);
+
+	extra = reftable_record_val_type(&in);
+	m = reftable_record_decode(&out, key, extra, dest, GIT_SHA1_RAWSZ,
+				   &scratch);
+	check_int(m, ==, n);
+
+	check(reftable_record_equal(&in, &out, GIT_SHA1_RAWSZ));
+
+	reftable_record_release(&out);
+	strbuf_release(&key);
+	strbuf_release(&scratch);
+	strbuf_release(&in.u.idx.last_key);
+}
+
+int cmd_main(int argc, const char *argv[])
+{
+	TEST(t_reftable_ref_record_comparison(), "comparison operations work on ref record");
+	TEST(t_reftable_log_record_comparison(), "comparison operations work on log record");
+	TEST(t_reftable_index_record_comparison(), "comparison operations work on index record");
+	TEST(t_reftable_obj_record_comparison(), "comparison operations work on obj record");
+	TEST(t_reftable_ref_record_compare_name(), "reftable_ref_record_compare_name works");
+	TEST(t_reftable_log_record_compare_key(), "reftable_log_record_compare_key works");
+	TEST(t_reftable_log_record_roundtrip(), "record operations work on log record");
+	TEST(t_reftable_ref_record_roundtrip(), "record operations work on ref record");
+	TEST(t_varint_roundtrip(), "put_var_int and get_var_int work");
+	TEST(t_key_roundtrip(), "reftable_encode_key and reftable_decode_key work");
+	TEST(t_reftable_obj_record_roundtrip(), "record operations work on obj record");
+	TEST(t_reftable_index_record_roundtrip(), "record operations work on index record");
+
+	return test_done();
+}
diff --git a/t/unit-tests/t-strbuf.c b/t/unit-tests/t-strbuf.c
index de434a4441..6027dafef7 100644
--- a/t/unit-tests/t-strbuf.c
+++ b/t/unit-tests/t-strbuf.c
@@ -2,7 +2,8 @@
 #include "strbuf.h"
 
 /* wrapper that supplies tests with an empty, initialized strbuf */
-static void setup(void (*f)(struct strbuf*, void*), void *data)
+static void setup(void (*f)(struct strbuf*, const void*),
+		  const void *data)
 {
 	struct strbuf buf = STRBUF_INIT;
 
@@ -13,7 +14,8 @@ static void setup(void (*f)(struct strbuf*, void*), void *data)
 }
 
 /* wrapper that supplies tests with a populated, initialized strbuf */
-static void setup_populated(void (*f)(struct strbuf*, void*), char *init_str, void *data)
+static void setup_populated(void (*f)(struct strbuf*, const void*),
+			    const char *init_str, const void *data)
 {
 	struct strbuf buf = STRBUF_INIT;
 
@@ -64,7 +66,7 @@ static void t_dynamic_init(void)
 	strbuf_release(&buf);
 }
 
-static void t_addch(struct strbuf *buf, void *data)
+static void t_addch(struct strbuf *buf, const void *data)
 {
 	const char *p_ch = data;
 	const char ch = *p_ch;
@@ -83,7 +85,7 @@ static void t_addch(struct strbuf *buf, void *data)
 	check_char(buf->buf[buf->len], ==, '\0');
 }
 
-static void t_addstr(struct strbuf *buf, void *data)
+static void t_addstr(struct strbuf *buf, const void *data)
 {
 	const char *text = data;
 	size_t len = strlen(text);