summaryrefslogtreecommitdiff
path: root/t/unit-tests
diff options
context:
space:
mode:
Diffstat (limited to 't/unit-tests')
-rw-r--r--t/unit-tests/t-example-decorate.c24
-rw-r--r--t/unit-tests/t-hashmap.c361
-rw-r--r--t/unit-tests/t-reftable-merged.c463
-rw-r--r--t/unit-tests/t-reftable-pq.c152
-rw-r--r--t/unit-tests/t-reftable-tree.c84
-rw-r--r--t/unit-tests/t-strvec.c47
-rw-r--r--t/unit-tests/test-lib.h5
7 files changed, 1086 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-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-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), \
generated by cgit v1.2.3 (git 2.46.0) at 2025-11-26 23:41:31 +0000