7 files changed, 523 insertions, 4 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
new file mode 100644
index 0000000000..a4a75db735
--- /dev/null
+++ b/t/unit-tests/t-example-decorate.c
@@ -0,0 +1,82 @@
+#define USE_THE_REPOSITORY_VARIABLE
+
+#include "test-lib.h"
+#include "object.h"
+#include "decorate.h"
+#include "repository.h"
+
+struct test_vars {
+	struct object *one, *two, *three;
+	struct decoration n;
+	int decoration_a, decoration_b;
+};
+
+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");
+	ret = add_decoration(&vars->n, vars->two, NULL);
+	if (!check(ret == NULL))
+		test_msg("when adding a brand-new object, NULL should be returned");
+}
+
+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");
+	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");
+}
+
+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");
+	ret = lookup_decoration(&vars->n, vars->two);
+	if (!check(ret == &vars->decoration_b))
+		test_msg("lookup should return added declaration");
+	ret = lookup_decoration(&vars->n, vars->three);
+	if (!check(ret == NULL))
+		test_msg("lookup for unknown object should return NULL");
+}
+
+static void t_loop(struct test_vars *vars)
+{
+	int i, objects_noticed = 0;
+
+	for (i = 0; i < vars->n.size; i++) {
+		if (vars->n.entries[i].base)
+			objects_noticed++;
+	}
+	if (!check_int(objects_noticed, ==, 2))
+		test_msg("should have 2 objects");
+}
+
+int cmd_main(int argc UNUSED, const char **argv UNUSED)
+{
+	struct object_id one_oid = { { 1 } }, two_oid = { { 2 } }, three_oid = { { 3 } };
+	struct test_vars vars = { 0 };
+
+	vars.one = lookup_unknown_object(the_repository, &one_oid);
+	vars.two = lookup_unknown_object(the_repository, &two_oid);
+	vars.three = lookup_unknown_object(the_repository, &three_oid);
+
+	TEST(t_add(&vars),
+	     "Add 2 objects, one with a non-NULL decoration and one with a NULL decoration.");
+	TEST(t_readd(&vars),
+	     "When re-adding an already existing object, the old decoration is returned.");
+	TEST(t_lookup(&vars),
+	     "Lookup returns the added declarations, or NULL if the object was never added.");
+	TEST(t_loop(&vars), "The user can also loop through all entries.");
+
+	clear_decoration(&vars.n, NULL);
+
+	return test_done();
+}
diff --git a/t/unit-tests/t-hash.c b/t/unit-tests/t-hash.c
new file mode 100644
index 0000000000..e9a78bf2c0
--- /dev/null
+++ b/t/unit-tests/t-hash.c
@@ -0,0 +1,84 @@
+#include "test-lib.h"
+#include "hex.h"
+#include "strbuf.h"
+
+static void check_hash_data(const void *data, size_t data_length,
+			    const char *expected_hashes[])
+{
+	if (!check(data != NULL)) {
+		test_msg("BUG: NULL data pointer provided");
+		return;
+	}
+
+	for (size_t i = 1; i < ARRAY_SIZE(hash_algos); i++) {
+		git_hash_ctx ctx;
+		unsigned char hash[GIT_MAX_HEXSZ];
+		const struct git_hash_algo *algop = &hash_algos[i];
+
+		algop->init_fn(&ctx);
+		algop->update_fn(&ctx, data, data_length);
+		algop->final_fn(hash, &ctx);
+
+		if (!check_str(hash_to_hex_algop(hash, algop), expected_hashes[i - 1]))
+			test_msg("result does not match with the expected for %s\n", hash_algos[i].name);
+	}
+}
+
+/* Works with a NUL terminated string. Doesn't work if it should contain a NUL character. */
+#define TEST_HASH_STR(data, expected_sha1, expected_sha256) do { \
+		const char *expected_hashes[] = { expected_sha1, expected_sha256 }; \
+		TEST(check_hash_data(data, strlen(data), expected_hashes), \
+		     "SHA1 and SHA256 (%s) works", #data); \
+	} while (0)
+
+/* Only works with a literal string, useful when it contains a NUL character. */
+#define TEST_HASH_LITERAL(literal, expected_sha1, expected_sha256) do { \
+		const char *expected_hashes[] = { expected_sha1, expected_sha256 }; \
+		TEST(check_hash_data(literal, (sizeof(literal) - 1), expected_hashes), \
+		     "SHA1 and SHA256 (%s) works", #literal); \
+	} while (0)
+
+int cmd_main(int argc, const char **argv)
+{
+	struct strbuf aaaaaaaaaa_100000 = STRBUF_INIT;
+	struct strbuf alphabet_100000 = STRBUF_INIT;
+
+	strbuf_addstrings(&aaaaaaaaaa_100000, "aaaaaaaaaa", 100000);
+	strbuf_addstrings(&alphabet_100000, "abcdefghijklmnopqrstuvwxyz", 100000);
+
+	TEST_HASH_STR("",
+		"da39a3ee5e6b4b0d3255bfef95601890afd80709",
+		"e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855");
+	TEST_HASH_STR("a",
+		"86f7e437faa5a7fce15d1ddcb9eaeaea377667b8",
+		"ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb");
+	TEST_HASH_STR("abc",
+		"a9993e364706816aba3e25717850c26c9cd0d89d",
+		"ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad");
+	TEST_HASH_STR("message digest",
+		"c12252ceda8be8994d5fa0290a47231c1d16aae3",
+		"f7846f55cf23e14eebeab5b4e1550cad5b509e3348fbc4efa3a1413d393cb650");
+	TEST_HASH_STR("abcdefghijklmnopqrstuvwxyz",
+		"32d10c7b8cf96570ca04ce37f2a19d84240d3a89",
+		"71c480df93d6ae2f1efad1447c66c9525e316218cf51fc8d9ed832f2daf18b73");
+	TEST_HASH_STR(aaaaaaaaaa_100000.buf,
+		"34aa973cd4c4daa4f61eeb2bdbad27316534016f",
+		"cdc76e5c9914fb9281a1c7e284d73e67f1809a48a497200e046d39ccc7112cd0");
+	TEST_HASH_STR(alphabet_100000.buf,
+		"e7da7c55b3484fdf52aebec9cbe7b85a98f02fd4",
+		"e406ba321ca712ad35a698bf0af8d61fc4dc40eca6bdcea4697962724ccbde35");
+	TEST_HASH_LITERAL("blob 0\0",
+		"e69de29bb2d1d6434b8b29ae775ad8c2e48c5391",
+		"473a0f4c3be8a93681a267e3b1e9a7dcda1185436fe141f7749120a303721813");
+	TEST_HASH_LITERAL("blob 3\0abc",
+		"f2ba8f84ab5c1bce84a7b441cb1959cfc7093b7f",
+		"c1cf6e465077930e88dc5136641d402f72a229ddd996f627d60e9639eaba35a6");
+	TEST_HASH_LITERAL("tree 0\0",
+		"4b825dc642cb6eb9a060e54bf8d69288fbee4904",
+		"6ef19b41225c5369f1c104d45d8d85efa9b057b53b14b4b9b939dd74decc5321");
+
+	strbuf_release(&aaaaaaaaaa_100000);
+	strbuf_release(&alphabet_100000);
+
+	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
new file mode 100644
index 0000000000..4e80bdf16d
--- /dev/null
+++ b/t/unit-tests/t-reftable-basics.c
@@ -0,0 +1,160 @@
+/*
+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/basics.h"
+
+struct integer_needle_lesseq_args {
+	int needle;
+	int *haystack;
+};
+
+static int integer_needle_lesseq(size_t i, void *_args)
+{
+	struct integer_needle_lesseq_args *args = _args;
+	return args->needle <= args->haystack[i];
+}
+
+static void test_binsearch(void)
+{
+	int haystack[] = { 2, 4, 6, 8, 10 };
+	struct {
+		int needle;
+		size_t expected_idx;
+	} testcases[] = {
+		{-9000, 0},
+		{-1, 0},
+		{0, 0},
+		{2, 0},
+		{3, 1},
+		{4, 1},
+		{7, 3},
+		{9, 4},
+		{10, 4},
+		{11, 5},
+		{9000, 5},
+	};
+
+	for (size_t i = 0; i < ARRAY_SIZE(testcases); i++) {
+		struct integer_needle_lesseq_args args = {
+			.haystack = haystack,
+			.needle = testcases[i].needle,
+		};
+		size_t idx;
+
+		idx = binsearch(ARRAY_SIZE(haystack), &integer_needle_lesseq, &args);
+		check_int(idx, ==, testcases[i].expected_idx);
+	}
+}
+
+static void test_names_length(void)
+{
+	const char *a[] = { "a", "b", NULL };
+	check_int(names_length(a), ==, 2);
+}
+
+static void test_names_equal(void)
+{
+	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));
+	check(!names_equal(a, c));
+}
+
+static void test_parse_names_normal(void)
+{
+	char in1[] = "line\n";
+	char in2[] = "a\nb\nc";
+	char **out = NULL;
+	parse_names(in1, strlen(in1), &out);
+	check_str(out[0], "line");
+	check(!out[1]);
+	free_names(out);
+
+	parse_names(in2, strlen(in2), &out);
+	check_str(out[0], "a");
+	check_str(out[1], "b");
+	check_str(out[2], "c");
+	check(!out[3]);
+	free_names(out);
+}
+
+static void test_parse_names_drop_empty(void)
+{
+	char in[] = "a\n\nb\n";
+	char **out = NULL;
+	parse_names(in, strlen(in), &out);
+	check_str(out[0], "a");
+	/* simply '\n' should be dropped as empty string */
+	check_str(out[1], "b");
+	check(!out[2]);
+	free_names(out);
+}
+
+static void test_common_prefix(void)
+{
+	struct strbuf a = STRBUF_INIT;
+	struct strbuf b = STRBUF_INIT;
+	struct {
+		const char *a, *b;
+		int want;
+	} cases[] = {
+		{"abcdef", "abc", 3},
+		{ "abc", "ab", 2 },
+		{ "", "abc", 0 },
+		{ "abc", "abd", 2 },
+		{ "abc", "pqr", 0 },
+	};
+
+	for (size_t i = 0; i < ARRAY_SIZE(cases); i++) {
+		strbuf_addstr(&a, cases[i].a);
+		strbuf_addstr(&b, cases[i].b);
+		check_int(common_prefix_size(&a, &b), ==, cases[i].want);
+		strbuf_reset(&a);
+		strbuf_reset(&b);
+	}
+	strbuf_release(&a);
+	strbuf_release(&b);
+}
+
+static void test_u24_roundtrip(void)
+{
+	uint32_t in = 0x112233;
+	uint8_t dest[3];
+	uint32_t out;
+	put_be24(dest, in);
+	out = get_be24(dest);
+	check_int(in, ==, out);
+}
+
+static void test_u16_roundtrip(void)
+{
+	uint32_t in = 0xfef1;
+	uint8_t dest[3];
+	uint32_t out;
+	put_be16(dest, in);
+	out = get_be16(dest);
+	check_int(in, ==, out);
+}
+
+int cmd_main(int argc, const char *argv[])
+{
+	TEST(test_common_prefix(), "common_prefix_size works");
+	TEST(test_parse_names_normal(), "parse_names works for basic input");
+	TEST(test_parse_names_drop_empty(), "parse_names drops empty string");
+	TEST(test_binsearch(), "binary search with binsearch works");
+	TEST(test_names_length(), "names_length retuns size of a NULL-terminated string array");
+	TEST(test_names_equal(), "names_equal compares NULL-terminated string arrays");
+	TEST(test_u24_roundtrip(), "put_be24 and get_be24 work");
+	TEST(test_u16_roundtrip(), "put_be16 and get_be16 work");
+
+	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);