summaryrefslogtreecommitdiff
path: root/t/helper
diff options
context:
space:
mode:
Diffstat (limited to 't/helper')
-rw-r--r--t/helper/test-genzeros.c21
-rw-r--r--t/helper/test-mergesort.c368
-rw-r--r--t/helper/test-oid-array.c4
-rw-r--r--t/helper/test-oidtree.c3
-rw-r--r--t/helper/test-parse-options.c7
-rw-r--r--t/helper/test-prio-queue.c2
-rw-r--r--t/helper/test-read-midx.c32
-rw-r--r--t/helper/test-ref-store.c3
8 files changed, 427 insertions, 13 deletions
diff --git a/t/helper/test-genzeros.c b/t/helper/test-genzeros.c
index 9532f5bac9..8ca988d621 100644
--- a/t/helper/test-genzeros.c
+++ b/t/helper/test-genzeros.c
@@ -3,18 +3,31 @@
int cmd__genzeros(int argc, const char **argv)
{
- long count;
+ /* static, so that it is NUL-initialized */
+ static const char zeros[256 * 1024];
+ intmax_t count;
+ ssize_t n;
if (argc > 2) {
fprintf(stderr, "usage: %s [<count>]\n", argv[0]);
return 1;
}
- count = argc > 1 ? strtol(argv[1], NULL, 0) : -1L;
+ count = argc > 1 ? strtoimax(argv[1], NULL, 0) : -1;
- while (count < 0 || count--) {
- if (putchar(0) == EOF)
+ /* Writing out individual NUL bytes is slow... */
+ while (count < 0)
+ if (write(1, zeros, ARRAY_SIZE(zeros)) < 0)
return -1;
+
+ while (count > 0) {
+ n = write(1, zeros, count < ARRAY_SIZE(zeros) ?
+ count : ARRAY_SIZE(zeros));
+
+ if (n < 0)
+ return -1;
+
+ count -= n;
}
return 0;
diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c
index c5cffaa4b7..ebf68f7de8 100644
--- a/t/helper/test-mergesort.c
+++ b/t/helper/test-mergesort.c
@@ -2,6 +2,12 @@
#include "cache.h"
#include "mergesort.h"
+static uint32_t minstd_rand(uint32_t *state)
+{
+ *state = (uint64_t)*state * 48271 % 2147483647;
+ return *state;
+}
+
struct line {
char *text;
struct line *next;
@@ -23,14 +29,12 @@ static int compare_strings(const void *a, const void *b)
return strcmp(x->text, y->text);
}
-int cmd__mergesort(int argc, const char **argv)
+static int sort_stdin(void)
{
struct line *line, *p = NULL, *lines = NULL;
struct strbuf sb = STRBUF_INIT;
- for (;;) {
- if (strbuf_getwholeline(&sb, stdin, '\n'))
- break;
+ while (!strbuf_getline(&sb, stdin)) {
line = xmalloc(sizeof(struct line));
line->text = strbuf_detach(&sb, NULL);
if (p) {
@@ -46,8 +50,362 @@ int cmd__mergesort(int argc, const char **argv)
lines = llist_mergesort(lines, get_next, set_next, compare_strings);
while (lines) {
- printf("%s", lines->text);
+ puts(lines->text);
lines = lines->next;
}
return 0;
}
+
+static void dist_sawtooth(int *arr, int n, int m)
+{
+ int i;
+ for (i = 0; i < n; i++)
+ arr[i] = i % m;
+}
+
+static void dist_rand(int *arr, int n, int m)
+{
+ int i;
+ uint32_t seed = 1;
+ for (i = 0; i < n; i++)
+ arr[i] = minstd_rand(&seed) % m;
+}
+
+static void dist_stagger(int *arr, int n, int m)
+{
+ int i;
+ for (i = 0; i < n; i++)
+ arr[i] = (i * m + i) % n;
+}
+
+static void dist_plateau(int *arr, int n, int m)
+{
+ int i;
+ for (i = 0; i < n; i++)
+ arr[i] = (i < m) ? i : m;
+}
+
+static void dist_shuffle(int *arr, int n, int m)
+{
+ int i, j, k;
+ uint32_t seed = 1;
+ for (i = j = 0, k = 1; i < n; i++)
+ arr[i] = minstd_rand(&seed) % m ? (j += 2) : (k += 2);
+}
+
+#define DIST(name) { #name, dist_##name }
+
+static struct dist {
+ const char *name;
+ void (*fn)(int *arr, int n, int m);
+} dist[] = {
+ DIST(sawtooth),
+ DIST(rand),
+ DIST(stagger),
+ DIST(plateau),
+ DIST(shuffle),
+};
+
+static const struct dist *get_dist_by_name(const char *name)
+{
+ int i;
+ for (i = 0; i < ARRAY_SIZE(dist); i++) {
+ if (!strcmp(dist[i].name, name))
+ return &dist[i];
+ }
+ return NULL;
+}
+
+static void mode_copy(int *arr, int n)
+{
+ /* nothing */
+}
+
+static void mode_reverse(int *arr, int n)
+{
+ int i, j;
+ for (i = 0, j = n - 1; i < j; i++, j--)
+ SWAP(arr[i], arr[j]);
+}
+
+static void mode_reverse_1st_half(int *arr, int n)
+{
+ mode_reverse(arr, n / 2);
+}
+
+static void mode_reverse_2nd_half(int *arr, int n)
+{
+ int half = n / 2;
+ mode_reverse(arr + half, n - half);
+}
+
+static int compare_ints(const void *av, const void *bv)
+{
+ const int *ap = av, *bp = bv;
+ int a = *ap, b = *bp;
+ return (a > b) - (a < b);
+}
+
+static void mode_sort(int *arr, int n)
+{
+ QSORT(arr, n, compare_ints);
+}
+
+static void mode_dither(int *arr, int n)
+{
+ int i;
+ for (i = 0; i < n; i++)
+ arr[i] += i % 5;
+}
+
+static void unriffle(int *arr, int n, int *tmp)
+{
+ int i, j;
+ COPY_ARRAY(tmp, arr, n);
+ for (i = j = 0; i < n; i += 2)
+ arr[j++] = tmp[i];
+ for (i = 1; i < n; i += 2)
+ arr[j++] = tmp[i];
+}
+
+static void unriffle_recursively(int *arr, int n, int *tmp)
+{
+ if (n > 1) {
+ int half = n / 2;
+ unriffle(arr, n, tmp);
+ unriffle_recursively(arr, half, tmp);
+ unriffle_recursively(arr + half, n - half, tmp);
+ }
+}
+
+static void mode_unriffle(int *arr, int n)
+{
+ int *tmp;
+ ALLOC_ARRAY(tmp, n);
+ unriffle_recursively(arr, n, tmp);
+ free(tmp);
+}
+
+static unsigned int prev_pow2(unsigned int n)
+{
+ unsigned int pow2 = 1;
+ while (pow2 * 2 < n)
+ pow2 *= 2;
+ return pow2;
+}
+
+static void unriffle_recursively_skewed(int *arr, int n, int *tmp)
+{
+ if (n > 1) {
+ int pow2 = prev_pow2(n);
+ int rest = n - pow2;
+ unriffle(arr + pow2 - rest, rest * 2, tmp);
+ unriffle_recursively_skewed(arr, pow2, tmp);
+ unriffle_recursively_skewed(arr + pow2, rest, tmp);
+ }
+}
+
+static void mode_unriffle_skewed(int *arr, int n)
+{
+ int *tmp;
+ ALLOC_ARRAY(tmp, n);
+ unriffle_recursively_skewed(arr, n, tmp);
+ free(tmp);
+}
+
+#define MODE(name) { #name, mode_##name }
+
+static struct mode {
+ const char *name;
+ void (*fn)(int *arr, int n);
+} mode[] = {
+ MODE(copy),
+ MODE(reverse),
+ MODE(reverse_1st_half),
+ MODE(reverse_2nd_half),
+ MODE(sort),
+ MODE(dither),
+ MODE(unriffle),
+ MODE(unriffle_skewed),
+};
+
+static const struct mode *get_mode_by_name(const char *name)
+{
+ int i;
+ for (i = 0; i < ARRAY_SIZE(mode); i++) {
+ if (!strcmp(mode[i].name, name))
+ return &mode[i];
+ }
+ return NULL;
+}
+
+static int generate(int argc, const char **argv)
+{
+ const struct dist *dist = NULL;
+ const struct mode *mode = NULL;
+ int i, n, m, *arr;
+
+ if (argc != 4)
+ return 1;
+
+ dist = get_dist_by_name(argv[0]);
+ mode = get_mode_by_name(argv[1]);
+ n = strtol(argv[2], NULL, 10);
+ m = strtol(argv[3], NULL, 10);
+ if (!dist || !mode)
+ return 1;
+
+ ALLOC_ARRAY(arr, n);
+ dist->fn(arr, n, m);
+ mode->fn(arr, n);
+ for (i = 0; i < n; i++)
+ printf("%08x\n", arr[i]);
+ free(arr);
+ return 0;
+}
+
+static struct stats {
+ int get_next, set_next, compare;
+} stats;
+
+struct number {
+ int value, rank;
+ struct number *next;
+};
+
+static void *get_next_number(const void *a)
+{
+ stats.get_next++;
+ return ((const struct number *)a)->next;
+}
+
+static void set_next_number(void *a, void *b)
+{
+ stats.set_next++;
+ ((struct number *)a)->next = b;
+}
+
+static int compare_numbers(const void *av, const void *bv)
+{
+ const struct number *an = av, *bn = bv;
+ int a = an->value, b = bn->value;
+ stats.compare++;
+ return (a > b) - (a < b);
+}
+
+static void clear_numbers(struct number *list)
+{
+ while (list) {
+ struct number *next = list->next;
+ free(list);
+ list = next;
+ }
+}
+
+static int test(const struct dist *dist, const struct mode *mode, int n, int m)
+{
+ int *arr;
+ size_t i;
+ struct number *curr, *list, **tail;
+ int is_sorted = 1;
+ int is_stable = 1;
+ const char *verdict;
+ int result = -1;
+
+ ALLOC_ARRAY(arr, n);
+ dist->fn(arr, n, m);
+ mode->fn(arr, n);
+ for (i = 0, tail = &list; i < n; i++) {
+ curr = xmalloc(sizeof(*curr));
+ curr->value = arr[i];
+ curr->rank = i;
+ *tail = curr;
+ tail = &curr->next;
+ }
+ *tail = NULL;
+
+ stats.get_next = stats.set_next = stats.compare = 0;
+ list = llist_mergesort(list, get_next_number, set_next_number,
+ compare_numbers);
+
+ QSORT(arr, n, compare_ints);
+ for (i = 0, curr = list; i < n && curr; i++, curr = curr->next) {
+ if (arr[i] != curr->value)
+ is_sorted = 0;
+ if (curr->next && curr->value == curr->next->value &&
+ curr->rank >= curr->next->rank)
+ is_stable = 0;
+ }
+ if (i < n) {
+ verdict = "too short";
+ } else if (curr) {
+ verdict = "too long";
+ } else if (!is_sorted) {
+ verdict = "not sorted";
+ } else if (!is_stable) {
+ verdict = "unstable";
+ } else {
+ verdict = "OK";
+ result = 0;
+ }
+
+ printf("%-9s %-16s %8d %8d %8d %8d %8d %s\n",
+ dist->name, mode->name, n, m, stats.get_next, stats.set_next,
+ stats.compare, verdict);
+
+ clear_numbers(list);
+ free(arr);
+
+ return result;
+}
+
+/*
+ * A version of the qsort certification program from "Engineering a Sort
+ * Function" by Bentley and McIlroy, Software—Practice and Experience,
+ * Volume 23, Issue 11, 1249–1265 (November 1993).
+ */
+static int run_tests(int argc, const char **argv)
+{
+ const char *argv_default[] = { "100", "1023", "1024", "1025" };
+ if (!argc)
+ return run_tests(ARRAY_SIZE(argv_default), argv_default);
+ printf("%-9s %-16s %8s %8s %8s %8s %8s %s\n",
+ "distribut", "mode", "n", "m", "get_next", "set_next",
+ "compare", "verdict");
+ while (argc--) {
+ int i, j, m, n = strtol(*argv++, NULL, 10);
+ for (i = 0; i < ARRAY_SIZE(dist); i++) {
+ for (j = 0; j < ARRAY_SIZE(mode); j++) {
+ for (m = 1; m < 2 * n; m *= 2) {
+ if (test(&dist[i], &mode[j], n, m))
+ return 1;
+ }
+ }
+ }
+ }
+ return 0;
+}
+
+int cmd__mergesort(int argc, const char **argv)
+{
+ int i;
+ const char *sep;
+
+ if (argc == 6 && !strcmp(argv[1], "generate"))
+ return generate(argc - 2, argv + 2);
+ if (argc == 2 && !strcmp(argv[1], "sort"))
+ return sort_stdin();
+ if (argc > 1 && !strcmp(argv[1], "test"))
+ return run_tests(argc - 2, argv + 2);
+ fprintf(stderr, "usage: test-tool mergesort generate <distribution> <mode> <n> <m>\n");
+ fprintf(stderr, " or: test-tool mergesort sort\n");
+ fprintf(stderr, " or: test-tool mergesort test [<n>...]\n");
+ fprintf(stderr, "\n");
+ for (i = 0, sep = "distributions: "; i < ARRAY_SIZE(dist); i++, sep = ", ")
+ fprintf(stderr, "%s%s", sep, dist[i].name);
+ fprintf(stderr, "\n");
+ for (i = 0, sep = "modes: "; i < ARRAY_SIZE(mode); i++, sep = ", ")
+ fprintf(stderr, "%s%s", sep, mode[i].name);
+ fprintf(stderr, "\n");
+ return 129;
+}
diff --git a/t/helper/test-oid-array.c b/t/helper/test-oid-array.c
index b16cd0b11b..d1324d086a 100644
--- a/t/helper/test-oid-array.c
+++ b/t/helper/test-oid-array.c
@@ -35,5 +35,9 @@ int cmd__oid_array(int argc, const char **argv)
else
die("unknown command: %s", line.buf);
}
+
+ strbuf_release(&line);
+ oid_array_clear(&array);
+
return 0;
}
diff --git a/t/helper/test-oidtree.c b/t/helper/test-oidtree.c
index 180ee28dd9..d48a409f4e 100644
--- a/t/helper/test-oidtree.c
+++ b/t/helper/test-oidtree.c
@@ -45,5 +45,8 @@ int cmd__oidtree(int argc, const char **argv)
die("unknown command: %s", line.buf);
}
}
+
+ strbuf_release(&line);
+
return 0;
}
diff --git a/t/helper/test-parse-options.c b/t/helper/test-parse-options.c
index a282b6ff13..48d3cf6692 100644
--- a/t/helper/test-parse-options.c
+++ b/t/helper/test-parse-options.c
@@ -14,7 +14,6 @@ static int dry_run = 0, quiet = 0;
static char *string = NULL;
static char *file = NULL;
static int ambiguous;
-static struct string_list list = STRING_LIST_INIT_NODUP;
static struct {
int called;
@@ -107,6 +106,8 @@ int cmd__parse_options(int argc, const char **argv)
NULL
};
struct string_list expect = STRING_LIST_INIT_NODUP;
+ struct string_list list = STRING_LIST_INIT_NODUP;
+
struct option options[] = {
OPT_BOOL(0, "yes", &boolean, "get a boolean"),
OPT_BOOL('D', "no-doubt", &boolean, "begins with 'no-'"),
@@ -185,5 +186,9 @@ int cmd__parse_options(int argc, const char **argv)
for (i = 0; i < argc; i++)
show(&expect, &ret, "arg %02d: %s", i, argv[i]);
+ expect.strdup_strings = 1;
+ string_list_clear(&expect, 0);
+ string_list_clear(&list, 0);
+
return ret;
}
diff --git a/t/helper/test-prio-queue.c b/t/helper/test-prio-queue.c
index f4028442e3..133b5e6f4a 100644
--- a/t/helper/test-prio-queue.c
+++ b/t/helper/test-prio-queue.c
@@ -46,5 +46,7 @@ int cmd__prio_queue(int argc, const char **argv)
}
}
+ clear_prio_queue(&pq);
+
return 0;
}
diff --git a/t/helper/test-read-midx.c b/t/helper/test-read-midx.c
index cb0d27049a..27072ba94d 100644
--- a/t/helper/test-read-midx.c
+++ b/t/helper/test-read-midx.c
@@ -3,6 +3,7 @@
#include "midx.h"
#include "repository.h"
#include "object-store.h"
+#include "pack-bitmap.h"
static int read_midx_file(const char *object_dir, int show_objects)
{
@@ -54,9 +55,10 @@ static int read_midx_file(const char *object_dir, int show_objects)
printf("%s %"PRIu64"\t%s\n",
oid_to_hex(&oid), e.offset, e.p->pack_name);
}
- return 0;
}
+ close_midx(m);
+
return 0;
}
@@ -72,14 +74,40 @@ static int read_midx_checksum(const char *object_dir)
return 0;
}
+static int read_midx_preferred_pack(const char *object_dir)
+{
+ struct multi_pack_index *midx = NULL;
+ struct bitmap_index *bitmap = NULL;
+
+ setup_git_directory();
+
+ midx = load_multi_pack_index(object_dir, 1);
+ if (!midx)
+ return 1;
+
+ bitmap = prepare_bitmap_git(the_repository);
+ if (!bitmap)
+ return 1;
+ if (!bitmap_is_midx(bitmap)) {
+ free_bitmap_index(bitmap);
+ return 1;
+ }
+
+ printf("%s\n", midx->pack_names[midx_preferred_pack(bitmap)]);
+ free_bitmap_index(bitmap);
+ return 0;
+}
+
int cmd__read_midx(int argc, const char **argv)
{
if (!(argc == 2 || argc == 3))
- usage("read-midx [--show-objects|--checksum] <object-dir>");
+ usage("read-midx [--show-objects|--checksum|--preferred-pack] <object-dir>");
if (!strcmp(argv[1], "--show-objects"))
return read_midx_file(argv[2], 1);
else if (!strcmp(argv[1], "--checksum"))
return read_midx_checksum(argv[2]);
+ else if (!strcmp(argv[1], "--preferred-pack"))
+ return read_midx_preferred_pack(argv[2]);
return read_midx_file(argv[1], 0);
}
diff --git a/t/helper/test-ref-store.c b/t/helper/test-ref-store.c
index b314b81a45..3986665037 100644
--- a/t/helper/test-ref-store.c
+++ b/t/helper/test-ref-store.c
@@ -123,9 +123,10 @@ static int cmd_resolve_ref(struct ref_store *refs, const char **argv)
int resolve_flags = arg_flags(*argv++, "resolve-flags");
int flags;
const char *ref;
+ int ignore_errno;
ref = refs_resolve_ref_unsafe(refs, refname, resolve_flags,
- &oid, &flags);
+ &oid, &flags, &ignore_errno);
printf("%s %s 0x%x\n", oid_to_hex(&oid), ref ? ref : "(null)", flags);
return ref ? 0 : 1;
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-01 11:19:34 +0000