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-reftable-pq.c152
-rw-r--r--t/unit-tests/t-reftable-tree.c84
-rw-r--r--t/unit-tests/test-lib.h5
4 files changed, 247 insertions, 18 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-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/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-12-01 11:44:35 +0000