9 files changed, 1818 insertions, 50 deletions

diff --git a/t/unit-tests/t-example-decorate.c b/t/unit-tests/t-example-decorate.c
index a4a75db735..8bf0709c41 100644
--- a/t/unit-tests/t-example-decorate.c
+++ b/t/unit-tests/t-example-decorate.c
@@ -15,36 +15,29 @@ static void t_add(struct test_vars *vars)
 {
 	void *ret = add_decoration(&vars->n, vars->one, &vars->decoration_a);
 
-	if (!check(ret == NULL))
-		test_msg("when adding a brand-new object, NULL should be returned");
+	check(ret == NULL);
 	ret = add_decoration(&vars->n, vars->two, NULL);
-	if (!check(ret == NULL))
-		test_msg("when adding a brand-new object, NULL should be returned");
+	check(ret == NULL);
 }
 
 static void t_readd(struct test_vars *vars)
 {
 	void *ret = add_decoration(&vars->n, vars->one, NULL);
 
-	if (!check(ret == &vars->decoration_a))
-		test_msg("when readding an already existing object, existing decoration should be returned");
+	check(ret == &vars->decoration_a);
 	ret = add_decoration(&vars->n, vars->two, &vars->decoration_b);
-	if (!check(ret == NULL))
-		test_msg("when readding an already existing object, existing decoration should be returned");
+	check(ret == NULL);
 }
 
 static void t_lookup(struct test_vars *vars)
 {
 	void *ret = lookup_decoration(&vars->n, vars->one);
 
-	if (!check(ret == NULL))
-		test_msg("lookup should return added declaration");
+	check(ret == NULL);
 	ret = lookup_decoration(&vars->n, vars->two);
-	if (!check(ret == &vars->decoration_b))
-		test_msg("lookup should return added declaration");
+	check(ret == &vars->decoration_b);
 	ret = lookup_decoration(&vars->n, vars->three);
-	if (!check(ret == NULL))
-		test_msg("lookup for unknown object should return NULL");
+	check(ret == NULL);
 }
 
 static void t_loop(struct test_vars *vars)
@@ -55,8 +48,7 @@ static void t_loop(struct test_vars *vars)
 		if (vars->n.entries[i].base)
 			objects_noticed++;
 	}
-	if (!check_int(objects_noticed, ==, 2))
-		test_msg("should have 2 objects");
+	check_int(objects_noticed, ==, 2);
 }
 
 int cmd_main(int argc UNUSED, const char **argv UNUSED)
diff --git a/t/unit-tests/t-hashmap.c b/t/unit-tests/t-hashmap.c
new file mode 100644
index 0000000000..09a48c2c4e
--- /dev/null
+++ b/t/unit-tests/t-hashmap.c
@@ -0,0 +1,361 @@
+#include "test-lib.h"
+#include "hashmap.h"
+#include "strbuf.h"
+
+struct test_entry {
+	int padding; /* hashmap entry no longer needs to be the first member */
+	struct hashmap_entry ent;
+	/* key and value as two \0-terminated strings */
+	char key[FLEX_ARRAY];
+};
+
+static int test_entry_cmp(const void *cmp_data,
+			  const struct hashmap_entry *eptr,
+			  const struct hashmap_entry *entry_or_key,
+			  const void *keydata)
+{
+	const unsigned int ignore_case = cmp_data ? *((int *)cmp_data) : 0;
+	const struct test_entry *e1, *e2;
+	const char *key = keydata;
+
+	e1 = container_of(eptr, const struct test_entry, ent);
+	e2 = container_of(entry_or_key, const struct test_entry, ent);
+
+	if (ignore_case)
+		return strcasecmp(e1->key, key ? key : e2->key);
+	else
+		return strcmp(e1->key, key ? key : e2->key);
+}
+
+static const char *get_value(const struct test_entry *e)
+{
+	return e->key + strlen(e->key) + 1;
+}
+
+static struct test_entry *alloc_test_entry(const char *key, const char *value,
+					   unsigned int ignore_case)
+{
+	size_t klen = strlen(key);
+	size_t vlen = strlen(value);
+	unsigned int hash = ignore_case ? strihash(key) : strhash(key);
+	struct test_entry *entry = xmalloc(st_add4(sizeof(*entry), klen, vlen, 2));
+
+	hashmap_entry_init(&entry->ent, hash);
+	memcpy(entry->key, key, klen + 1);
+	memcpy(entry->key + klen + 1, value, vlen + 1);
+	return entry;
+}
+
+static struct test_entry *get_test_entry(struct hashmap *map, const char *key,
+					 unsigned int ignore_case)
+{
+	return hashmap_get_entry_from_hash(
+		map, ignore_case ? strihash(key) : strhash(key), key,
+		struct test_entry, ent);
+}
+
+static int key_val_contains(const char *key_val[][2], char seen[], size_t n,
+			    struct test_entry *entry)
+{
+	for (size_t i = 0; i < n; i++) {
+		if (!strcmp(entry->key, key_val[i][0]) &&
+		    !strcmp(get_value(entry), key_val[i][1])) {
+			if (seen[i])
+				return 2;
+			seen[i] = 1;
+			return 0;
+		}
+	}
+	return 1;
+}
+
+static void setup(void (*f)(struct hashmap *map, unsigned int ignore_case),
+		  unsigned int ignore_case)
+{
+	struct hashmap map = HASHMAP_INIT(test_entry_cmp, &ignore_case);
+
+	f(&map, ignore_case);
+	hashmap_clear_and_free(&map, struct test_entry, ent);
+}
+
+static void t_replace(struct hashmap *map, unsigned int ignore_case)
+{
+	struct test_entry *entry;
+
+	entry = alloc_test_entry("key1", "value1", ignore_case);
+	check_pointer_eq(hashmap_put_entry(map, entry, ent), NULL);
+
+	entry = alloc_test_entry(ignore_case ? "Key1" : "key1", "value2",
+				 ignore_case);
+	entry = hashmap_put_entry(map, entry, ent);
+	if (check(entry != NULL))
+		check_str(get_value(entry), "value1");
+	free(entry);
+
+	entry = alloc_test_entry("fooBarFrotz", "value3", ignore_case);
+	check_pointer_eq(hashmap_put_entry(map, entry, ent), NULL);
+
+	entry = alloc_test_entry(ignore_case ? "FOObarFrotz" : "fooBarFrotz",
+				 "value4", ignore_case);
+	entry = hashmap_put_entry(map, entry, ent);
+	if (check(entry != NULL))
+		check_str(get_value(entry), "value3");
+	free(entry);
+}
+
+static void t_get(struct hashmap *map, unsigned int ignore_case)
+{
+	struct test_entry *entry;
+	const char *key_val[][2] = { { "key1", "value1" },
+				     { "key2", "value2" },
+				     { "fooBarFrotz", "value3" },
+				     { ignore_case ? "key4" : "foobarfrotz",
+				       "value4" } };
+	const char *query[][2] = {
+		{ ignore_case ? "Key1" : "key1", "value1" },
+		{ ignore_case ? "keY2" : "key2", "value2" },
+		{ ignore_case ? "FOObarFrotz" : "fooBarFrotz", "value3" },
+		{ ignore_case ? "FOObarFrotz" : "foobarfrotz",
+		  ignore_case ? "value3" : "value4" }
+	};
+
+	for (size_t i = 0; i < ARRAY_SIZE(key_val); i++) {
+		entry = alloc_test_entry(key_val[i][0], key_val[i][1],
+					 ignore_case);
+		check_pointer_eq(hashmap_put_entry(map, entry, ent), NULL);
+	}
+
+	for (size_t i = 0; i < ARRAY_SIZE(query); i++) {
+		entry = get_test_entry(map, query[i][0], ignore_case);
+		if (check(entry != NULL))
+			check_str(get_value(entry), query[i][1]);
+		else
+			test_msg("query key: %s", query[i][0]);
+	}
+
+	check_pointer_eq(get_test_entry(map, "notInMap", ignore_case), NULL);
+	check_int(map->tablesize, ==, 64);
+	check_int(hashmap_get_size(map), ==, ARRAY_SIZE(key_val));
+}
+
+static void t_add(struct hashmap *map, unsigned int ignore_case)
+{
+	struct test_entry *entry;
+	const char *key_val[][2] = {
+		{ "key1", "value1" },
+		{ ignore_case ? "Key1" : "key1", "value2" },
+		{ "fooBarFrotz", "value3" },
+		{ ignore_case ? "FOObarFrotz" : "fooBarFrotz", "value4" }
+	};
+	const char *query_keys[] = { "key1", ignore_case ? "FOObarFrotz" :
+							   "fooBarFrotz" };
+	char seen[ARRAY_SIZE(key_val)] = { 0 };
+
+	for (size_t i = 0; i < ARRAY_SIZE(key_val); i++) {
+		entry = alloc_test_entry(key_val[i][0], key_val[i][1], ignore_case);
+		hashmap_add(map, &entry->ent);
+	}
+
+	for (size_t i = 0; i < ARRAY_SIZE(query_keys); i++) {
+		int count = 0;
+		entry = hashmap_get_entry_from_hash(map,
+			ignore_case ? strihash(query_keys[i]) :
+				      strhash(query_keys[i]),
+			query_keys[i], struct test_entry, ent);
+
+		hashmap_for_each_entry_from(map, entry, ent)
+		{
+			int ret;
+			if (!check_int((ret = key_val_contains(
+						key_val, seen,
+						ARRAY_SIZE(key_val), entry)),
+				       ==, 0)) {
+				switch (ret) {
+				case 1:
+					test_msg("found entry was not given in the input\n"
+						 "    key: %s\n  value: %s",
+						 entry->key, get_value(entry));
+					break;
+				case 2:
+					test_msg("duplicate entry detected\n"
+						 "    key: %s\n  value: %s",
+						 entry->key, get_value(entry));
+					break;
+				}
+			} else {
+				count++;
+			}
+		}
+		check_int(count, ==, 2);
+	}
+
+	for (size_t i = 0; i < ARRAY_SIZE(seen); i++) {
+		if (!check_int(seen[i], ==, 1))
+			test_msg("following key-val pair was not iterated over:\n"
+				 "    key: %s\n  value: %s",
+				 key_val[i][0], key_val[i][1]);
+	}
+
+	check_int(hashmap_get_size(map), ==, ARRAY_SIZE(key_val));
+	check_pointer_eq(get_test_entry(map, "notInMap", ignore_case), NULL);
+}
+
+static void t_remove(struct hashmap *map, unsigned int ignore_case)
+{
+	struct test_entry *entry, *removed;
+	const char *key_val[][2] = { { "key1", "value1" },
+				     { "key2", "value2" },
+				     { "fooBarFrotz", "value3" } };
+	const char *remove[][2] = { { ignore_case ? "Key1" : "key1", "value1" },
+				    { ignore_case ? "keY2" : "key2", "value2" } };
+
+	for (size_t i = 0; i < ARRAY_SIZE(key_val); i++) {
+		entry = alloc_test_entry(key_val[i][0], key_val[i][1], ignore_case);
+		check_pointer_eq(hashmap_put_entry(map, entry, ent), NULL);
+	}
+
+	for (size_t i = 0; i < ARRAY_SIZE(remove); i++) {
+		entry = alloc_test_entry(remove[i][0], "", ignore_case);
+		removed = hashmap_remove_entry(map, entry, ent, remove[i][0]);
+		if (check(removed != NULL))
+			check_str(get_value(removed), remove[i][1]);
+		free(entry);
+		free(removed);
+	}
+
+	entry = alloc_test_entry("notInMap", "", ignore_case);
+	check_pointer_eq(hashmap_remove_entry(map, entry, ent, "notInMap"), NULL);
+	free(entry);
+
+	check_int(map->tablesize, ==, 64);
+	check_int(hashmap_get_size(map), ==, ARRAY_SIZE(key_val) - ARRAY_SIZE(remove));
+}
+
+static void t_iterate(struct hashmap *map, unsigned int ignore_case)
+{
+	struct test_entry *entry;
+	struct hashmap_iter iter;
+	const char *key_val[][2] = { { "key1", "value1" },
+				     { "key2", "value2" },
+				     { "fooBarFrotz", "value3" } };
+	char seen[ARRAY_SIZE(key_val)] = { 0 };
+
+	for (size_t i = 0; i < ARRAY_SIZE(key_val); i++) {
+		entry = alloc_test_entry(key_val[i][0], key_val[i][1], ignore_case);
+		check_pointer_eq(hashmap_put_entry(map, entry, ent), NULL);
+	}
+
+	hashmap_for_each_entry(map, &iter, entry, ent /* member name */)
+	{
+		int ret;
+		if (!check_int((ret = key_val_contains(key_val, seen,
+						       ARRAY_SIZE(key_val),
+						       entry)), ==, 0)) {
+			switch (ret) {
+			case 1:
+				test_msg("found entry was not given in the input\n"
+					 "    key: %s\n  value: %s",
+					 entry->key, get_value(entry));
+				break;
+			case 2:
+				test_msg("duplicate entry detected\n"
+					 "    key: %s\n  value: %s",
+					 entry->key, get_value(entry));
+				break;
+			}
+		}
+	}
+
+	for (size_t i = 0; i < ARRAY_SIZE(seen); i++) {
+		if (!check_int(seen[i], ==, 1))
+			test_msg("following key-val pair was not iterated over:\n"
+				 "    key: %s\n  value: %s",
+				 key_val[i][0], key_val[i][1]);
+	}
+
+	check_int(hashmap_get_size(map), ==, ARRAY_SIZE(key_val));
+}
+
+static void t_alloc(struct hashmap *map, unsigned int ignore_case)
+{
+	struct test_entry *entry, *removed;
+
+	for (int i = 1; i <= 51; i++) {
+		char *key = xstrfmt("key%d", i);
+		char *value = xstrfmt("value%d", i);
+		entry = alloc_test_entry(key, value, ignore_case);
+		check_pointer_eq(hashmap_put_entry(map, entry, ent), NULL);
+		free(key);
+		free(value);
+	}
+	check_int(map->tablesize, ==, 64);
+	check_int(hashmap_get_size(map), ==, 51);
+
+	entry = alloc_test_entry("key52", "value52", ignore_case);
+	check_pointer_eq(hashmap_put_entry(map, entry, ent), NULL);
+	check_int(map->tablesize, ==, 256);
+	check_int(hashmap_get_size(map), ==, 52);
+
+	for (int i = 1; i <= 12; i++) {
+		char *key = xstrfmt("key%d", i);
+		char *value = xstrfmt("value%d", i);
+
+		entry = alloc_test_entry(key, "", ignore_case);
+		removed = hashmap_remove_entry(map, entry, ent, key);
+		if (check(removed != NULL))
+			check_str(value, get_value(removed));
+		free(key);
+		free(value);
+		free(entry);
+		free(removed);
+	}
+	check_int(map->tablesize, ==, 256);
+	check_int(hashmap_get_size(map), ==, 40);
+
+	entry = alloc_test_entry("key40", "", ignore_case);
+	removed = hashmap_remove_entry(map, entry, ent, "key40");
+	if (check(removed != NULL))
+		check_str("value40", get_value(removed));
+	check_int(map->tablesize, ==, 64);
+	check_int(hashmap_get_size(map), ==, 39);
+	free(entry);
+	free(removed);
+}
+
+static void t_intern(struct hashmap *map, unsigned int ignore_case)
+{
+	const char *values[] = { "value1", "Value1", "value2", "value2" };
+
+	for (size_t i = 0; i < ARRAY_SIZE(values); i++) {
+		const char *i1 = strintern(values[i]);
+		const char *i2 = strintern(values[i]);
+
+		if (!check(!strcmp(i1, values[i])))
+			test_msg("strintern(%s) returns %s\n", values[i], i1);
+		else if (!check(i1 != values[i]))
+			test_msg("strintern(%s) returns input pointer\n",
+				 values[i]);
+		else if (!check_pointer_eq(i1, i2))
+			test_msg("address('%s') != address('%s'), so strintern('%s') != strintern('%s')",
+				 i1, i2, values[i], values[i]);
+		else
+			check_str(i1, values[i]);
+	}
+}
+
+int cmd_main(int argc UNUSED, const char **argv UNUSED)
+{
+	TEST(setup(t_replace, 0), "replace works");
+	TEST(setup(t_replace, 1), "replace (case insensitive) works");
+	TEST(setup(t_get, 0), "get works");
+	TEST(setup(t_get, 1), "get (case insensitive) works");
+	TEST(setup(t_add, 0), "add works");
+	TEST(setup(t_add, 1), "add (case insensitive) works");
+	TEST(setup(t_remove, 0), "remove works");
+	TEST(setup(t_remove, 1), "remove (case insensitive) works");
+	TEST(setup(t_iterate, 0), "iterate works");
+	TEST(setup(t_iterate, 1), "iterate (case insensitive) works");
+	TEST(setup(t_alloc, 0), "grow / shrink works");
+	TEST(setup(t_intern, 0), "string interning works");
+	return test_done();
+}
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-reftable-merged.c b/t/unit-tests/t-reftable-merged.c
new file mode 100644
index 0000000000..b6263ee8b5
--- /dev/null
+++ b/t/unit-tests/t-reftable-merged.c
@@ -0,0 +1,463 @@
+/*
+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/blocksource.h"
+#include "reftable/constants.h"
+#include "reftable/merged.h"
+#include "reftable/reader.h"
+#include "reftable/reftable-error.h"
+#include "reftable/reftable-generic.h"
+#include "reftable/reftable-merged.h"
+#include "reftable/reftable-writer.h"
+
+static ssize_t strbuf_add_void(void *b, const void *data, const size_t sz)
+{
+	strbuf_add(b, data, sz);
+	return sz;
+}
+
+static int noop_flush(void *arg)
+{
+	return 0;
+}
+
+static void write_test_table(struct strbuf *buf,
+			     struct reftable_ref_record refs[], const size_t n)
+{
+	uint64_t min = 0xffffffff;
+	uint64_t max = 0;
+	size_t i;
+	int err;
+
+	struct reftable_write_options opts = {
+		.block_size = 256,
+	};
+	struct reftable_writer *w = NULL;
+	for (i = 0; i < n; i++) {
+		uint64_t ui = refs[i].update_index;
+		if (ui > max)
+			max = ui;
+		if (ui < min)
+			min = ui;
+	}
+
+	w = reftable_new_writer(&strbuf_add_void, &noop_flush, buf, &opts);
+	reftable_writer_set_limits(w, min, max);
+
+	for (i = 0; i < n; i++) {
+		uint64_t before = refs[i].update_index;
+		int n = reftable_writer_add_ref(w, &refs[i]);
+		check_int(n, ==, 0);
+		check_int(before, ==, refs[i].update_index);
+	}
+
+	err = reftable_writer_close(w);
+	check(!err);
+
+	reftable_writer_free(w);
+}
+
+static void write_test_log_table(struct strbuf *buf, struct reftable_log_record logs[],
+				 const size_t n, const uint64_t update_index)
+{
+	int err;
+
+	struct reftable_write_options opts = {
+		.block_size = 256,
+		.exact_log_message = 1,
+	};
+	struct reftable_writer *w = NULL;
+	w = reftable_new_writer(&strbuf_add_void, &noop_flush, buf, &opts);
+	reftable_writer_set_limits(w, update_index, update_index);
+
+	for (size_t i = 0; i < n; i++) {
+		int err = reftable_writer_add_log(w, &logs[i]);
+		check(!err);
+	}
+
+	err = reftable_writer_close(w);
+	check(!err);
+
+	reftable_writer_free(w);
+}
+
+static struct reftable_merged_table *
+merged_table_from_records(struct reftable_ref_record **refs,
+			  struct reftable_block_source **source,
+			  struct reftable_reader ***readers, const size_t *sizes,
+			  struct strbuf *buf, const size_t n)
+{
+	struct reftable_merged_table *mt = NULL;
+	struct reftable_table *tabs;
+	int err;
+
+	REFTABLE_CALLOC_ARRAY(tabs, n);
+	REFTABLE_CALLOC_ARRAY(*readers, n);
+	REFTABLE_CALLOC_ARRAY(*source, n);
+
+	for (size_t i = 0; i < n; i++) {
+		write_test_table(&buf[i], refs[i], sizes[i]);
+		block_source_from_strbuf(&(*source)[i], &buf[i]);
+
+		err = reftable_new_reader(&(*readers)[i], &(*source)[i],
+					  "name");
+		check(!err);
+		reftable_table_from_reader(&tabs[i], (*readers)[i]);
+	}
+
+	err = reftable_new_merged_table(&mt, tabs, n, GIT_SHA1_FORMAT_ID);
+	check(!err);
+	return mt;
+}
+
+static void readers_destroy(struct reftable_reader **readers, const size_t n)
+{
+	for (size_t i = 0; i < n; i++)
+		reftable_reader_free(readers[i]);
+	reftable_free(readers);
+}
+
+static void t_merged_single_record(void)
+{
+	struct reftable_ref_record r1[] = { {
+		.refname = (char *) "b",
+		.update_index = 1,
+		.value_type = REFTABLE_REF_VAL1,
+		.value.val1 = { 1, 2, 3, 0 },
+	} };
+	struct reftable_ref_record r2[] = { {
+		.refname = (char *) "a",
+		.update_index = 2,
+		.value_type = REFTABLE_REF_DELETION,
+	} };
+	struct reftable_ref_record r3[] = { {
+		.refname = (char *) "c",
+		.update_index = 3,
+		.value_type = REFTABLE_REF_DELETION,
+	} };
+
+	struct reftable_ref_record *refs[] = { r1, r2, r3 };
+	size_t sizes[] = { ARRAY_SIZE(r1), ARRAY_SIZE(r2), ARRAY_SIZE(r3) };
+	struct strbuf bufs[3] = { STRBUF_INIT, STRBUF_INIT, STRBUF_INIT };
+	struct reftable_block_source *bs = NULL;
+	struct reftable_reader **readers = NULL;
+	struct reftable_merged_table *mt =
+		merged_table_from_records(refs, &bs, &readers, sizes, bufs, 3);
+	struct reftable_ref_record ref = { 0 };
+	struct reftable_iterator it = { 0 };
+	int err;
+
+	merged_table_init_iter(mt, &it, BLOCK_TYPE_REF);
+	err = reftable_iterator_seek_ref(&it, "a");
+	check(!err);
+
+	err = reftable_iterator_next_ref(&it, &ref);
+	check(!err);
+	check(reftable_ref_record_equal(&r2[0], &ref, GIT_SHA1_RAWSZ));
+	reftable_ref_record_release(&ref);
+	reftable_iterator_destroy(&it);
+	readers_destroy(readers, 3);
+	reftable_merged_table_free(mt);
+	for (size_t i = 0; i < ARRAY_SIZE(bufs); i++)
+		strbuf_release(&bufs[i]);
+	reftable_free(bs);
+}
+
+static void t_merged_refs(void)
+{
+	struct reftable_ref_record r1[] = {
+		{
+			.refname = (char *) "a",
+			.update_index = 1,
+			.value_type = REFTABLE_REF_VAL1,
+			.value.val1 = { 1 },
+		},
+		{
+			.refname = (char *) "b",
+			.update_index = 1,
+			.value_type = REFTABLE_REF_VAL1,
+			.value.val1 = { 1 },
+		},
+		{
+			.refname = (char *) "c",
+			.update_index = 1,
+			.value_type = REFTABLE_REF_VAL1,
+			.value.val1 = { 1 },
+		}
+	};
+	struct reftable_ref_record r2[] = { {
+		.refname = (char *) "a",
+		.update_index = 2,
+		.value_type = REFTABLE_REF_DELETION,
+	} };
+	struct reftable_ref_record r3[] = {
+		{
+			.refname = (char *) "c",
+			.update_index = 3,
+			.value_type = REFTABLE_REF_VAL1,
+			.value.val1 = { 2 },
+		},
+		{
+			.refname = (char *) "d",
+			.update_index = 3,
+			.value_type = REFTABLE_REF_VAL1,
+			.value.val1 = { 1 },
+		},
+	};
+
+	struct reftable_ref_record *want[] = {
+		&r2[0],
+		&r1[1],
+		&r3[0],
+		&r3[1],
+	};
+
+	struct reftable_ref_record *refs[] = { r1, r2, r3 };
+	size_t sizes[3] = { ARRAY_SIZE(r1), ARRAY_SIZE(r2), ARRAY_SIZE(r3) };
+	struct strbuf bufs[3] = { STRBUF_INIT, STRBUF_INIT, STRBUF_INIT };
+	struct reftable_block_source *bs = NULL;
+	struct reftable_reader **readers = NULL;
+	struct reftable_merged_table *mt =
+		merged_table_from_records(refs, &bs, &readers, sizes, bufs, 3);
+	struct reftable_iterator it = { 0 };
+	int err;
+	struct reftable_ref_record *out = NULL;
+	size_t len = 0;
+	size_t cap = 0;
+	size_t i;
+
+	merged_table_init_iter(mt, &it, BLOCK_TYPE_REF);
+	err = reftable_iterator_seek_ref(&it, "a");
+	check(!err);
+	check_int(reftable_merged_table_hash_id(mt), ==, GIT_SHA1_FORMAT_ID);
+	check_int(reftable_merged_table_min_update_index(mt), ==, 1);
+	check_int(reftable_merged_table_max_update_index(mt), ==, 3);
+
+	while (len < 100) { /* cap loops/recursion. */
+		struct reftable_ref_record ref = { 0 };
+		int err = reftable_iterator_next_ref(&it, &ref);
+		if (err > 0)
+			break;
+
+		REFTABLE_ALLOC_GROW(out, len + 1, cap);
+		out[len++] = ref;
+	}
+	reftable_iterator_destroy(&it);
+
+	check_int(ARRAY_SIZE(want), ==, len);
+	for (i = 0; i < len; i++)
+		check(reftable_ref_record_equal(want[i], &out[i],
+						 GIT_SHA1_RAWSZ));
+	for (i = 0; i < len; i++)
+		reftable_ref_record_release(&out[i]);
+	reftable_free(out);
+
+	for (i = 0; i < 3; i++)
+		strbuf_release(&bufs[i]);
+	readers_destroy(readers, 3);
+	reftable_merged_table_free(mt);
+	reftable_free(bs);
+}
+
+static struct reftable_merged_table *
+merged_table_from_log_records(struct reftable_log_record **logs,
+			      struct reftable_block_source **source,
+			      struct reftable_reader ***readers, const size_t *sizes,
+			      struct strbuf *buf, const size_t n)
+{
+	struct reftable_merged_table *mt = NULL;
+	struct reftable_table *tabs;
+	int err;
+
+	REFTABLE_CALLOC_ARRAY(tabs, n);
+	REFTABLE_CALLOC_ARRAY(*readers, n);
+	REFTABLE_CALLOC_ARRAY(*source, n);
+
+	for (size_t i = 0; i < n; i++) {
+		write_test_log_table(&buf[i], logs[i], sizes[i], i + 1);
+		block_source_from_strbuf(&(*source)[i], &buf[i]);
+
+		err = reftable_new_reader(&(*readers)[i], &(*source)[i],
+					  "name");
+		check(!err);
+		reftable_table_from_reader(&tabs[i], (*readers)[i]);
+	}
+
+	err = reftable_new_merged_table(&mt, tabs, n, GIT_SHA1_FORMAT_ID);
+	check(!err);
+	return mt;
+}
+
+static void t_merged_logs(void)
+{
+	struct reftable_log_record r1[] = {
+		{
+			.refname = (char *) "a",
+			.update_index = 2,
+			.value_type = REFTABLE_LOG_UPDATE,
+			.value.update = {
+				.old_hash = { 2 },
+				/* deletion */
+				.name = (char *) "jane doe",
+				.email = (char *) "jane@invalid",
+				.message = (char *) "message2",
+			}
+		},
+		{
+			.refname = (char *) "a",
+			.update_index = 1,
+			.value_type = REFTABLE_LOG_UPDATE,
+			.value.update = {
+				.old_hash = { 1 },
+				.new_hash = { 2 },
+				.name = (char *) "jane doe",
+				.email = (char *) "jane@invalid",
+				.message = (char *) "message1",
+			}
+		},
+	};
+	struct reftable_log_record r2[] = {
+		{
+			.refname = (char *) "a",
+			.update_index = 3,
+			.value_type = REFTABLE_LOG_UPDATE,
+			.value.update = {
+				.new_hash = { 3 },
+				.name = (char *) "jane doe",
+				.email = (char *) "jane@invalid",
+				.message = (char *) "message3",
+			}
+		},
+	};
+	struct reftable_log_record r3[] = {
+		{
+			.refname = (char *) "a",
+			.update_index = 2,
+			.value_type = REFTABLE_LOG_DELETION,
+		},
+	};
+	struct reftable_log_record *want[] = {
+		&r2[0],
+		&r3[0],
+		&r1[1],
+	};
+
+	struct reftable_log_record *logs[] = { r1, r2, r3 };
+	size_t sizes[3] = { ARRAY_SIZE(r1), ARRAY_SIZE(r2), ARRAY_SIZE(r3) };
+	struct strbuf bufs[3] = { STRBUF_INIT, STRBUF_INIT, STRBUF_INIT };
+	struct reftable_block_source *bs = NULL;
+	struct reftable_reader **readers = NULL;
+	struct reftable_merged_table *mt = merged_table_from_log_records(
+		logs, &bs, &readers, sizes, bufs, 3);
+	struct reftable_iterator it = { 0 };
+	int err;
+	struct reftable_log_record *out = NULL;
+	size_t len = 0;
+	size_t cap = 0;
+	size_t i;
+
+	merged_table_init_iter(mt, &it, BLOCK_TYPE_LOG);
+	err = reftable_iterator_seek_log(&it, "a");
+	check(!err);
+	check_int(reftable_merged_table_hash_id(mt), ==, GIT_SHA1_FORMAT_ID);
+	check_int(reftable_merged_table_min_update_index(mt), ==, 1);
+	check_int(reftable_merged_table_max_update_index(mt), ==, 3);
+
+	while (len < 100) { /* cap loops/recursion. */
+		struct reftable_log_record log = { 0 };
+		int err = reftable_iterator_next_log(&it, &log);
+		if (err > 0)
+			break;
+
+		REFTABLE_ALLOC_GROW(out, len + 1, cap);
+		out[len++] = log;
+	}
+	reftable_iterator_destroy(&it);
+
+	check_int(ARRAY_SIZE(want), ==, len);
+	for (i = 0; i < len; i++)
+		check(reftable_log_record_equal(want[i], &out[i],
+						 GIT_SHA1_RAWSZ));
+
+	merged_table_init_iter(mt, &it, BLOCK_TYPE_LOG);
+	err = reftable_iterator_seek_log_at(&it, "a", 2);
+	check(!err);
+	reftable_log_record_release(&out[0]);
+	err = reftable_iterator_next_log(&it, &out[0]);
+	check(!err);
+	check(reftable_log_record_equal(&out[0], &r3[0], GIT_SHA1_RAWSZ));
+	reftable_iterator_destroy(&it);
+
+	for (i = 0; i < len; i++)
+		reftable_log_record_release(&out[i]);
+	reftable_free(out);
+
+	for (i = 0; i < 3; i++)
+		strbuf_release(&bufs[i]);
+	readers_destroy(readers, 3);
+	reftable_merged_table_free(mt);
+	reftable_free(bs);
+}
+
+static void t_default_write_opts(void)
+{
+	struct reftable_write_options opts = { 0 };
+	struct strbuf buf = STRBUF_INIT;
+	struct reftable_writer *w =
+		reftable_new_writer(&strbuf_add_void, &noop_flush, &buf, &opts);
+
+	struct reftable_ref_record rec = {
+		.refname = (char *) "master",
+		.update_index = 1,
+	};
+	int err;
+	struct reftable_block_source source = { 0 };
+	struct reftable_table *tab = reftable_calloc(1, sizeof(*tab));
+	uint32_t hash_id;
+	struct reftable_reader *rd = NULL;
+	struct reftable_merged_table *merged = NULL;
+
+	reftable_writer_set_limits(w, 1, 1);
+
+	err = reftable_writer_add_ref(w, &rec);
+	check(!err);
+
+	err = reftable_writer_close(w);
+	check(!err);
+	reftable_writer_free(w);
+
+	block_source_from_strbuf(&source, &buf);
+
+	err = reftable_new_reader(&rd, &source, "filename");
+	check(!err);
+
+	hash_id = reftable_reader_hash_id(rd);
+	check_int(hash_id, ==, GIT_SHA1_FORMAT_ID);
+
+	reftable_table_from_reader(&tab[0], rd);
+	err = reftable_new_merged_table(&merged, tab, 1, GIT_SHA256_FORMAT_ID);
+	check_int(err, ==, REFTABLE_FORMAT_ERROR);
+	err = reftable_new_merged_table(&merged, tab, 1, GIT_SHA1_FORMAT_ID);
+	check(!err);
+
+	reftable_reader_free(rd);
+	reftable_merged_table_free(merged);
+	strbuf_release(&buf);
+}
+
+
+int cmd_main(int argc, const char *argv[])
+{
+	TEST(t_default_write_opts(), "merged table with default write opts");
+	TEST(t_merged_logs(), "merged table with multiple log updates for same ref");
+	TEST(t_merged_refs(), "merged table with multiple updates to same ref");
+	TEST(t_merged_single_record(), "ref ocurring in only one record can be fetched");
+
+	return test_done();
+}
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();
+}
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-reftable-tree.c b/t/unit-tests/t-reftable-tree.c
new file mode 100644
index 0000000000..e7d774d774
--- /dev/null
+++ b/t/unit-tests/t-reftable-tree.c
@@ -0,0 +1,84 @@
+/*
+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/tree.h"
+
+static int t_compare(const void *a, const void *b)
+{
+	return (char *)a - (char *)b;
+}
+
+struct curry {
+	void **arr;
+	size_t len;
+};
+
+static void store(void *arg, void *key)
+{
+	struct curry *c = arg;
+	c->arr[c->len++] = key;
+}
+
+static void t_tree_search(void)
+{
+	struct tree_node *root = NULL;
+	void *values[11] = { 0 };
+	struct tree_node *nodes[11] = { 0 };
+	size_t i = 1;
+
+	/*
+	 * Pseudo-randomly insert the pointers for elements between
+	 * values[1] and values[10] (inclusive) in the tree.
+	 */
+	do {
+		nodes[i] = tree_search(&values[i], &root, &t_compare, 1);
+		i = (i * 7) % 11;
+	} while (i != 1);
+
+	for (i = 1; i < ARRAY_SIZE(nodes); i++) {
+		check_pointer_eq(&values[i], nodes[i]->key);
+		check_pointer_eq(nodes[i], tree_search(&values[i], &root, &t_compare, 0));
+	}
+
+	check(!tree_search(values, &root, t_compare, 0));
+	tree_free(root);
+}
+
+static void t_infix_walk(void)
+{
+	struct tree_node *root = NULL;
+	void *values[11] = { 0 };
+	void *out[11] = { 0 };
+	struct curry c = {
+		.arr = (void **) &out,
+	};
+	size_t i = 1;
+	size_t count = 0;
+
+	do {
+		tree_search(&values[i], &root, t_compare, 1);
+		i = (i * 7) % 11;
+		count++;
+	} while (i != 1);
+
+	infix_walk(root, &store, &c);
+	for (i = 1; i < ARRAY_SIZE(values); i++)
+		check_pointer_eq(&values[i], out[i - 1]);
+	check(!out[i - 1]);
+	check_int(c.len, ==, count);
+	tree_free(root);
+}
+
+int cmd_main(int argc, const char *argv[])
+{
+	TEST(t_tree_search(), "tree_search works");
+	TEST(t_infix_walk(), "infix_walk works");
+
+	return test_done();
+}
diff --git a/t/unit-tests/t-strvec.c b/t/unit-tests/t-strvec.c
index d4615ab06d..fa1a041469 100644
--- a/t/unit-tests/t-strvec.c
+++ b/t/unit-tests/t-strvec.c
@@ -3,38 +3,21 @@
 #include "strvec.h"
 
 #define check_strvec(vec, ...) \
-	check_strvec_loc(TEST_LOCATION(), vec, __VA_ARGS__)
-LAST_ARG_MUST_BE_NULL
-static void check_strvec_loc(const char *loc, struct strvec *vec, ...)
-{
-	va_list ap;
-	size_t nr = 0;
-
-	va_start(ap, vec);
-	while (1) {
-		const char *str = va_arg(ap, const char *);
-		if (!str)
-			break;
-
-		if (!check_uint(vec->nr, >, nr) ||
-		    !check_uint(vec->alloc, >, nr) ||
-		    !check_str(vec->v[nr], str)) {
-			struct strbuf msg = STRBUF_INIT;
-			strbuf_addf(&msg, "strvec index %"PRIuMAX, (uintmax_t) nr);
-			test_assert(loc, msg.buf, 0);
-			strbuf_release(&msg);
-			va_end(ap);
-			return;
-		}
-
-		nr++;
-	}
-	va_end(ap);
-
-	check_uint(vec->nr, ==, nr);
-	check_uint(vec->alloc, >=, nr);
-	check_pointer_eq(vec->v[nr], NULL);
-}
+	do { \
+		const char *expect[] = { __VA_ARGS__ }; \
+		if (check_uint(ARRAY_SIZE(expect), >, 0) && \
+		    check_pointer_eq(expect[ARRAY_SIZE(expect) - 1], NULL) && \
+		    check_uint((vec)->nr, ==, ARRAY_SIZE(expect) - 1) && \
+		    check_uint((vec)->nr, <=, (vec)->alloc)) { \
+			for (size_t i = 0; i < ARRAY_SIZE(expect); i++) { \
+				if (!check_str((vec)->v[i], expect[i])) { \
+					test_msg("      i: %"PRIuMAX, \
+						 (uintmax_t)i); \
+					break; \
+				} \
+			} \
+		} \
+	} while (0)
 
 static void t_static_init(void)
 {
diff --git a/t/unit-tests/test-lib.h b/t/unit-tests/test-lib.h
index 2de6d715d5..c59f646fd9 100644
--- a/t/unit-tests/test-lib.h
+++ b/t/unit-tests/test-lib.h
@@ -76,8 +76,9 @@ int test_assert(const char *location, const char *check, int ok);
 int check_bool_loc(const char *loc, const char *check, int ok);
 
 /*
- * Compare two integers. Prints a message with the two values if the
- * comparison fails. NB this is not thread safe.
+ * Compare the equality of two pointers of same type. Prints a message
+ * with the two values if the equality fails. NB this is not thread
+ * safe.
  */
 #define check_pointer_eq(a, b)						\
 	(test__tmp[0].p = (a), test__tmp[1].p = (b),			\