[PATCH] tests: move t0009-prio-queue.sh to the new unit testing framework

[PATCH] tests: move t0009-prio-queue.sh to the new unit testing framework

[Chandra Pratap via GitGitGadget]

From: Chandra Pratap <chandrapratap3519@gmail.com>

t/t0009-prio-queue.sh along with t/helper/test-prio-queue.c unit
tests Git's implementation of a priority queue. Migrate the
test over to the new unit testing framework to simplify debugging
and reduce test run-time. Refactor the required logic and add
a new test case in addition to porting over the original ones in
shell.

Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
    tests: move t0009-prio-queue.sh to the new unit testing framework

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1642%2FChand-ra%2Fprio-queue-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1642/Chand-ra/prio-queue-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1642

 Makefile                    |  2 +-
 t/helper/test-prio-queue.c  | 51 -------------------
 t/helper/test-tool.c        |  1 -
 t/helper/test-tool.h        |  1 -
 t/t0009-prio-queue.sh       | 66 -------------------------
 t/unit-tests/t-prio-queue.c | 99 +++++++++++++++++++++++++++++++++++++
 6 files changed, 100 insertions(+), 120 deletions(-)
 delete mode 100644 t/helper/test-prio-queue.c
 delete mode 100755 t/t0009-prio-queue.sh
 create mode 100644 t/unit-tests/t-prio-queue.c

diff --git a/Makefile b/Makefile
index 312d95084c1..d5e48e656b3 100644
--- a/Makefile
+++ b/Makefile
@@ -828,7 +828,6 @@ TEST_BUILTINS_OBJS += test-partial-clone.o
 TEST_BUILTINS_OBJS += test-path-utils.o
 TEST_BUILTINS_OBJS += test-pcre2-config.o
 TEST_BUILTINS_OBJS += test-pkt-line.o
-TEST_BUILTINS_OBJS += test-prio-queue.o
 TEST_BUILTINS_OBJS += test-proc-receive.o
 TEST_BUILTINS_OBJS += test-progress.o
 TEST_BUILTINS_OBJS += test-reach.o
@@ -1340,6 +1339,7 @@ THIRD_PARTY_SOURCES += sha1dc/%
 
 UNIT_TEST_PROGRAMS += t-basic
 UNIT_TEST_PROGRAMS += t-strbuf
+UNIT_TEST_PROGRAMS += t-prio-queue
 UNIT_TEST_PROGS = $(patsubst %,$(UNIT_TEST_BIN)/%$X,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS = $(patsubst %,$(UNIT_TEST_DIR)/%.o,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/test-lib.o
diff --git a/t/helper/test-prio-queue.c b/t/helper/test-prio-queue.c
deleted file mode 100644
index f0bf255f5f0..00000000000
--- a/t/helper/test-prio-queue.c
+++ /dev/null
@@ -1,51 +0,0 @@
-#include "test-tool.h"
-#include "prio-queue.h"
-
-static int intcmp(const void *va, const void *vb, void *data UNUSED)
-{
-	const int *a = va, *b = vb;
-	return *a - *b;
-}
-
-static void show(int *v)
-{
-	if (!v)
-		printf("NULL\n");
-	else
-		printf("%d\n", *v);
-	free(v);
-}
-
-int cmd__prio_queue(int argc UNUSED, const char **argv)
-{
-	struct prio_queue pq = { intcmp };
-
-	while (*++argv) {
-		if (!strcmp(*argv, "get")) {
-			void *peek = prio_queue_peek(&pq);
-			void *get = prio_queue_get(&pq);
-			if (peek != get)
-				BUG("peek and get results do not match");
-			show(get);
-		} else if (!strcmp(*argv, "dump")) {
-			void *peek;
-			void *get;
-			while ((peek = prio_queue_peek(&pq))) {
-				get = prio_queue_get(&pq);
-				if (peek != get)
-					BUG("peek and get results do not match");
-				show(get);
-			}
-		} else if (!strcmp(*argv, "stack")) {
-			pq.compare = NULL;
-		} else {
-			int *v = xmalloc(sizeof(*v));
-			*v = atoi(*argv);
-			prio_queue_put(&pq, v);
-		}
-	}
-
-	clear_prio_queue(&pq);
-
-	return 0;
-}
diff --git a/t/helper/test-tool.c b/t/helper/test-tool.c
index 876cd2dc313..5f591b9718f 100644
--- a/t/helper/test-tool.c
+++ b/t/helper/test-tool.c
@@ -57,7 +57,6 @@ static struct test_cmd cmds[] = {
 	{ "path-utils", cmd__path_utils },
 	{ "pcre2-config", cmd__pcre2_config },
 	{ "pkt-line", cmd__pkt_line },
-	{ "prio-queue", cmd__prio_queue },
 	{ "proc-receive", cmd__proc_receive },
 	{ "progress", cmd__progress },
 	{ "reach", cmd__reach },
diff --git a/t/helper/test-tool.h b/t/helper/test-tool.h
index 70dd4eba119..b921138d8ec 100644
--- a/t/helper/test-tool.h
+++ b/t/helper/test-tool.h
@@ -50,7 +50,6 @@ int cmd__partial_clone(int argc, const char **argv);
 int cmd__path_utils(int argc, const char **argv);
 int cmd__pcre2_config(int argc, const char **argv);
 int cmd__pkt_line(int argc, const char **argv);
-int cmd__prio_queue(int argc, const char **argv);
 int cmd__proc_receive(int argc, const char **argv);
 int cmd__progress(int argc, const char **argv);
 int cmd__reach(int argc, const char **argv);
diff --git a/t/t0009-prio-queue.sh b/t/t0009-prio-queue.sh
deleted file mode 100755
index eea99107a48..00000000000
--- a/t/t0009-prio-queue.sh
+++ /dev/null
@@ -1,66 +0,0 @@
-#!/bin/sh
-
-test_description='basic tests for priority queue implementation'
-
-TEST_PASSES_SANITIZE_LEAK=true
-. ./test-lib.sh
-
-cat >expect <<'EOF'
-1
-2
-3
-4
-5
-5
-6
-7
-8
-9
-10
-EOF
-test_expect_success 'basic ordering' '
-	test-tool prio-queue 2 6 3 10 9 5 7 4 5 8 1 dump >actual &&
-	test_cmp expect actual
-'
-
-cat >expect <<'EOF'
-2
-3
-4
-1
-5
-6
-EOF
-test_expect_success 'mixed put and get' '
-	test-tool prio-queue 6 2 4 get 5 3 get get 1 dump >actual &&
-	test_cmp expect actual
-'
-
-cat >expect <<'EOF'
-1
-2
-NULL
-1
-2
-NULL
-EOF
-test_expect_success 'notice empty queue' '
-	test-tool prio-queue 1 2 get get get 1 2 get get get >actual &&
-	test_cmp expect actual
-'
-
-cat >expect <<'EOF'
-3
-2
-6
-4
-5
-1
-8
-EOF
-test_expect_success 'stack order' '
-	test-tool prio-queue stack 8 1 5 4 6 2 3 dump >actual &&
-	test_cmp expect actual
-'
-
-test_done
diff --git a/t/unit-tests/t-prio-queue.c b/t/unit-tests/t-prio-queue.c
new file mode 100644
index 00000000000..98a69790f7e
--- /dev/null
+++ b/t/unit-tests/t-prio-queue.c
@@ -0,0 +1,99 @@
+#include "test-lib.h"
+#include "prio-queue.h"
+
+static int intcmp(const void *va, const void *vb, void *data UNUSED)
+{
+	const int *a = va, *b = vb;
+	return *a - *b;
+}
+
+static int show(int *v)
+{
+	int ret = -1;
+	if (v)
+		ret = *v;
+	free(v);
+	return ret;
+}
+
+static int test_prio_queue(const char **input, int *result)
+{
+	struct prio_queue pq = { intcmp };
+	int i = 0;
+
+	while (*input) {
+		if (!strcmp(*input, "get")) {
+			void *peek = prio_queue_peek(&pq);
+			void *get = prio_queue_get(&pq);
+			if (peek != get)
+				BUG("peek and get results do not match");
+			result[i++] = show(get);
+		} else if (!strcmp(*input, "dump")) {
+			void *peek;
+			void *get;
+			while ((peek = prio_queue_peek(&pq))) {
+				get = prio_queue_get(&pq);
+				if (peek != get)
+					BUG("peek and get results do not match");
+				result[i++] = show(get);
+			}
+		} else if (!strcmp(*input, "stack")) {
+			pq.compare = NULL;
+		} else if (!strcmp(*input, "reverse")) {
+			prio_queue_reverse(&pq);
+		} else {
+			int *v = xmalloc(sizeof(*v));
+			*v = atoi(*input);
+			prio_queue_put(&pq, v);
+		}
+		input++;
+	}
+
+	clear_prio_queue(&pq);
+
+	return 0;
+}
+
+#define INPUT_SIZE 6
+
+#define BASIC_INPUT "1", "2", "3", "4", "5", "5", "dump"
+#define BASIC_EXPECTED 1, 2, 3, 4, 5, 5
+
+#define MIXED_PUT_GET_INPUT "6", "2", "4", "get", "5", "3", "get", "get", "1", "dump"
+#define MIXED_PUT_GET_EXPECTED 2, 3, 4, 1, 5, 6
+
+#define EMPTY_QUEUE_INPUT "1", "2", "get", "get", "get", "1", "2", "get", "get", "get"
+#define EMPTY_QUEUE_EXPECTED 1, 2, -1, 1, 2, -1
+
+#define STACK_INPUT "stack", "1", "5", "4", "6", "2", "3", "dump"
+#define STACK_EXPECTED 3, 2, 6, 4, 5, 1
+
+#define REVERSE_STACK_INPUT "stack", "1", "2", "3", "4", "5", "6", "reverse", "dump"
+#define REVERSE_STACK_EXPECTED 1, 2, 3, 4, 5, 6
+
+#define TEST_INPUT(INPUT, EXPECTED, name)		\
+  static void test_##name(void)					\
+{											\
+	const char *input[] = {INPUT};						\
+	int expected[] = {EXPECTED};					\
+	int result[INPUT_SIZE];								\
+	test_prio_queue(input, result);						\
+	check(!memcmp(expected, result, sizeof(expected)));	\
+}
+
+TEST_INPUT(BASIC_INPUT, BASIC_EXPECTED, basic)
+TEST_INPUT(MIXED_PUT_GET_INPUT, MIXED_PUT_GET_EXPECTED, mixed)
+TEST_INPUT(EMPTY_QUEUE_INPUT, EMPTY_QUEUE_EXPECTED, empty)
+TEST_INPUT(STACK_INPUT, STACK_EXPECTED, stack)
+TEST_INPUT(REVERSE_STACK_INPUT, REVERSE_STACK_EXPECTED, reverse)
+
+int cmd_main(int argc, const char **argv)
+{
+	TEST(test_basic(), "prio-queue works for basic input");
+	TEST(test_mixed(), "prio-queue works for mixed put & get commands");
+	TEST(test_empty(), "prio-queue works when queue is empty");
+	TEST(test_stack(), "prio-queue works when used as a LIFO stack");
+	TEST(test_reverse(), "prio-queue works when LIFO stack is reversed");
+
+	return test_done();
+}

base-commit: 1a87c842ece327d03d08096395969aca5e0a6996
-- 
gitgitgadget

Re: [PATCH] tests: move t0009-prio-queue.sh to the new unit testing framework

[Chandra Pratap]

Please ignore the patch above, my e-mail client seems to have
messed up the backslash indentation. I will follow up with the
corrected patch shortly.

On Sun, 14 Jan 2024 at 13:40, Chandra Pratap via GitGitGadget
<gitgitgadget@gmail.com> wrote:
>
> From: Chandra Pratap <chandrapratap3519@gmail.com>
>
> t/t0009-prio-queue.sh along with t/helper/test-prio-queue.c unit
> tests Git's implementation of a priority queue. Migrate the
> test over to the new unit testing framework to simplify debugging
> and reduce test run-time. Refactor the required logic and add
> a new test case in addition to porting over the original ones in
> shell.
>
> Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
> ---
>     tests: move t0009-prio-queue.sh to the new unit testing framework
>
> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1642%2FChand-ra%2Fprio-queue-v1
> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1642/Chand-ra/prio-queue-v1
> Pull-Request: https://github.com/gitgitgadget/git/pull/1642
>
>  Makefile                    |  2 +-
>  t/helper/test-prio-queue.c  | 51 -------------------
>  t/helper/test-tool.c        |  1 -
>  t/helper/test-tool.h        |  1 -
>  t/t0009-prio-queue.sh       | 66 -------------------------
>  t/unit-tests/t-prio-queue.c | 99 +++++++++++++++++++++++++++++++++++++
>  6 files changed, 100 insertions(+), 120 deletions(-)
>  delete mode 100644 t/helper/test-prio-queue.c
>  delete mode 100755 t/t0009-prio-queue.sh
>  create mode 100644 t/unit-tests/t-prio-queue.c
>
> diff --git a/Makefile b/Makefile
> index 312d95084c1..d5e48e656b3 100644
> --- a/Makefile
> +++ b/Makefile
> @@ -828,7 +828,6 @@ TEST_BUILTINS_OBJS += test-partial-clone.o
>  TEST_BUILTINS_OBJS += test-path-utils.o
>  TEST_BUILTINS_OBJS += test-pcre2-config.o
>  TEST_BUILTINS_OBJS += test-pkt-line.o
> -TEST_BUILTINS_OBJS += test-prio-queue.o
>  TEST_BUILTINS_OBJS += test-proc-receive.o
>  TEST_BUILTINS_OBJS += test-progress.o
>  TEST_BUILTINS_OBJS += test-reach.o
> @@ -1340,6 +1339,7 @@ THIRD_PARTY_SOURCES += sha1dc/%
>
>  UNIT_TEST_PROGRAMS += t-basic
>  UNIT_TEST_PROGRAMS += t-strbuf
> +UNIT_TEST_PROGRAMS += t-prio-queue
>  UNIT_TEST_PROGS = $(patsubst %,$(UNIT_TEST_BIN)/%$X,$(UNIT_TEST_PROGRAMS))
>  UNIT_TEST_OBJS = $(patsubst %,$(UNIT_TEST_DIR)/%.o,$(UNIT_TEST_PROGRAMS))
>  UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/test-lib.o
> diff --git a/t/helper/test-prio-queue.c b/t/helper/test-prio-queue.c
> deleted file mode 100644
> index f0bf255f5f0..00000000000
> --- a/t/helper/test-prio-queue.c
> +++ /dev/null
> @@ -1,51 +0,0 @@
> -#include "test-tool.h"
> -#include "prio-queue.h"
> -
> -static int intcmp(const void *va, const void *vb, void *data UNUSED)
> -{
> -       const int *a = va, *b = vb;
> -       return *a - *b;
> -}
> -
> -static void show(int *v)
> -{
> -       if (!v)
> -               printf("NULL\n");
> -       else
> -               printf("%d\n", *v);
> -       free(v);
> -}
> -
> -int cmd__prio_queue(int argc UNUSED, const char **argv)
> -{
> -       struct prio_queue pq = { intcmp };
> -
> -       while (*++argv) {
> -               if (!strcmp(*argv, "get")) {
> -                       void *peek = prio_queue_peek(&pq);
> -                       void *get = prio_queue_get(&pq);
> -                       if (peek != get)
> -                               BUG("peek and get results do not match");
> -                       show(get);
> -               } else if (!strcmp(*argv, "dump")) {
> -                       void *peek;
> -                       void *get;
> -                       while ((peek = prio_queue_peek(&pq))) {
> -                               get = prio_queue_get(&pq);
> -                               if (peek != get)
> -                                       BUG("peek and get results do not match");
> -                               show(get);
> -                       }
> -               } else if (!strcmp(*argv, "stack")) {
> -                       pq.compare = NULL;
> -               } else {
> -                       int *v = xmalloc(sizeof(*v));
> -                       *v = atoi(*argv);
> -                       prio_queue_put(&pq, v);
> -               }
> -       }
> -
> -       clear_prio_queue(&pq);
> -
> -       return 0;
> -}
> diff --git a/t/helper/test-tool.c b/t/helper/test-tool.c
> index 876cd2dc313..5f591b9718f 100644
> --- a/t/helper/test-tool.c
> +++ b/t/helper/test-tool.c
> @@ -57,7 +57,6 @@ static struct test_cmd cmds[] = {
>         { "path-utils", cmd__path_utils },
>         { "pcre2-config", cmd__pcre2_config },
>         { "pkt-line", cmd__pkt_line },
> -       { "prio-queue", cmd__prio_queue },
>         { "proc-receive", cmd__proc_receive },
>         { "progress", cmd__progress },
>         { "reach", cmd__reach },
> diff --git a/t/helper/test-tool.h b/t/helper/test-tool.h
> index 70dd4eba119..b921138d8ec 100644
> --- a/t/helper/test-tool.h
> +++ b/t/helper/test-tool.h
> @@ -50,7 +50,6 @@ int cmd__partial_clone(int argc, const char **argv);
>  int cmd__path_utils(int argc, const char **argv);
>  int cmd__pcre2_config(int argc, const char **argv);
>  int cmd__pkt_line(int argc, const char **argv);
> -int cmd__prio_queue(int argc, const char **argv);
>  int cmd__proc_receive(int argc, const char **argv);
>  int cmd__progress(int argc, const char **argv);
>  int cmd__reach(int argc, const char **argv);
> diff --git a/t/t0009-prio-queue.sh b/t/t0009-prio-queue.sh
> deleted file mode 100755
> index eea99107a48..00000000000
> --- a/t/t0009-prio-queue.sh
> +++ /dev/null
> @@ -1,66 +0,0 @@
> -#!/bin/sh
> -
> -test_description='basic tests for priority queue implementation'
> -
> -TEST_PASSES_SANITIZE_LEAK=true
> -. ./test-lib.sh
> -
> -cat >expect <<'EOF'
> -1
> -2
> -3
> -4
> -5
> -5
> -6
> -7
> -8
> -9
> -10
> -EOF
> -test_expect_success 'basic ordering' '
> -       test-tool prio-queue 2 6 3 10 9 5 7 4 5 8 1 dump >actual &&
> -       test_cmp expect actual
> -'
> -
> -cat >expect <<'EOF'
> -2
> -3
> -4
> -1
> -5
> -6
> -EOF
> -test_expect_success 'mixed put and get' '
> -       test-tool prio-queue 6 2 4 get 5 3 get get 1 dump >actual &&
> -       test_cmp expect actual
> -'
> -
> -cat >expect <<'EOF'
> -1
> -2
> -NULL
> -1
> -2
> -NULL
> -EOF
> -test_expect_success 'notice empty queue' '
> -       test-tool prio-queue 1 2 get get get 1 2 get get get >actual &&
> -       test_cmp expect actual
> -'
> -
> -cat >expect <<'EOF'
> -3
> -2
> -6
> -4
> -5
> -1
> -8
> -EOF
> -test_expect_success 'stack order' '
> -       test-tool prio-queue stack 8 1 5 4 6 2 3 dump >actual &&
> -       test_cmp expect actual
> -'
> -
> -test_done
> diff --git a/t/unit-tests/t-prio-queue.c b/t/unit-tests/t-prio-queue.c
> new file mode 100644
> index 00000000000..98a69790f7e
> --- /dev/null
> +++ b/t/unit-tests/t-prio-queue.c
> @@ -0,0 +1,99 @@
> +#include "test-lib.h"
> +#include "prio-queue.h"
> +
> +static int intcmp(const void *va, const void *vb, void *data UNUSED)
> +{
> +       const int *a = va, *b = vb;
> +       return *a - *b;
> +}
> +
> +static int show(int *v)
> +{
> +       int ret = -1;
> +       if (v)
> +               ret = *v;
> +       free(v);
> +       return ret;
> +}
> +
> +static int test_prio_queue(const char **input, int *result)
> +{
> +       struct prio_queue pq = { intcmp };
> +       int i = 0;
> +
> +       while (*input) {
> +               if (!strcmp(*input, "get")) {
> +                       void *peek = prio_queue_peek(&pq);
> +                       void *get = prio_queue_get(&pq);
> +                       if (peek != get)
> +                               BUG("peek and get results do not match");
> +                       result[i++] = show(get);
> +               } else if (!strcmp(*input, "dump")) {
> +                       void *peek;
> +                       void *get;
> +                       while ((peek = prio_queue_peek(&pq))) {
> +                               get = prio_queue_get(&pq);
> +                               if (peek != get)
> +                                       BUG("peek and get results do not match");
> +                               result[i++] = show(get);
> +                       }
> +               } else if (!strcmp(*input, "stack")) {
> +                       pq.compare = NULL;
> +               } else if (!strcmp(*input, "reverse")) {
> +                       prio_queue_reverse(&pq);
> +               } else {
> +                       int *v = xmalloc(sizeof(*v));
> +                       *v = atoi(*input);
> +                       prio_queue_put(&pq, v);
> +               }
> +               input++;
> +       }
> +
> +       clear_prio_queue(&pq);
> +
> +       return 0;
> +}
> +
> +#define INPUT_SIZE 6
> +
> +#define BASIC_INPUT "1", "2", "3", "4", "5", "5", "dump"
> +#define BASIC_EXPECTED 1, 2, 3, 4, 5, 5
> +
> +#define MIXED_PUT_GET_INPUT "6", "2", "4", "get", "5", "3", "get", "get", "1", "dump"
> +#define MIXED_PUT_GET_EXPECTED 2, 3, 4, 1, 5, 6
> +
> +#define EMPTY_QUEUE_INPUT "1", "2", "get", "get", "get", "1", "2", "get", "get", "get"
> +#define EMPTY_QUEUE_EXPECTED 1, 2, -1, 1, 2, -1
> +
> +#define STACK_INPUT "stack", "1", "5", "4", "6", "2", "3", "dump"
> +#define STACK_EXPECTED 3, 2, 6, 4, 5, 1
> +
> +#define REVERSE_STACK_INPUT "stack", "1", "2", "3", "4", "5", "6", "reverse", "dump"
> +#define REVERSE_STACK_EXPECTED 1, 2, 3, 4, 5, 6
> +
> +#define TEST_INPUT(INPUT, EXPECTED, name)              \
> +  static void test_##name(void)                                        \
> +{                                                                                      \
> +       const char *input[] = {INPUT};                                          \
> +       int expected[] = {EXPECTED};                                    \
> +       int result[INPUT_SIZE];                                                         \
> +       test_prio_queue(input, result);                                         \
> +       check(!memcmp(expected, result, sizeof(expected)));     \
> +}
> +
> +TEST_INPUT(BASIC_INPUT, BASIC_EXPECTED, basic)
> +TEST_INPUT(MIXED_PUT_GET_INPUT, MIXED_PUT_GET_EXPECTED, mixed)
> +TEST_INPUT(EMPTY_QUEUE_INPUT, EMPTY_QUEUE_EXPECTED, empty)
> +TEST_INPUT(STACK_INPUT, STACK_EXPECTED, stack)
> +TEST_INPUT(REVERSE_STACK_INPUT, REVERSE_STACK_EXPECTED, reverse)
> +
> +int cmd_main(int argc, const char **argv)
> +{
> +       TEST(test_basic(), "prio-queue works for basic input");
> +       TEST(test_mixed(), "prio-queue works for mixed put & get commands");
> +       TEST(test_empty(), "prio-queue works when queue is empty");
> +       TEST(test_stack(), "prio-queue works when used as a LIFO stack");
> +       TEST(test_reverse(), "prio-queue works when LIFO stack is reversed");
> +
> +       return test_done();
> +}
>
> base-commit: 1a87c842ece327d03d08096395969aca5e0a6996
> --
> gitgitgadget

[PATCH v2] tests: move t0009-prio-queue.sh to the new unit testing framework

[Chandra Pratap via GitGitGadget]

From: Chandra Pratap <chandrapratap3519@gmail.com>

t/t0009-prio-queue.sh along with t/helper/test-prio-queue.c unit
tests Git's implementation of a priority queue. Migrate the
test over to the new unit testing framework to simplify debugging
and reduce test run-time. Refactor the required logic and add
a new test case in addition to porting over the original ones in
shell.

Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
    tests: move t0009-prio-queue.sh to the new unit testing framework

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1642%2FChand-ra%2Fprio-queue-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1642/Chand-ra/prio-queue-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/1642

Range-diff vs v1:

 1:  ca20abe95ea ! 1:  60ac9b3c259 tests: move t0009-prio-queue.sh to the new unit testing framework
     @@ t/unit-tests/t-prio-queue.c (new)
      +#define REVERSE_STACK_INPUT "stack", "1", "2", "3", "4", "5", "6", "reverse", "dump"
      +#define REVERSE_STACK_EXPECTED 1, 2, 3, 4, 5, 6
      +
     -+#define TEST_INPUT(INPUT, EXPECTED, name)		\
     ++#define TEST_INPUT(INPUT, EXPECTED, name)			\
      +  static void test_##name(void)					\
     -+{											\
     -+	const char *input[] = {INPUT};						\
     -+	int expected[] = {EXPECTED};					\
     -+	int result[INPUT_SIZE];								\
     -+	test_prio_queue(input, result);						\
     ++{								\
     ++	const char *input[] = {INPUT};				\
     ++	int expected[] = {EXPECTED};				\
     ++	int result[INPUT_SIZE];					\
     ++	test_prio_queue(input, result);				\
      +	check(!memcmp(expected, result, sizeof(expected)));	\
      +}
      +


 Makefile                    |  2 +-
 t/helper/test-prio-queue.c  | 51 -------------------
 t/helper/test-tool.c        |  1 -
 t/helper/test-tool.h        |  1 -
 t/t0009-prio-queue.sh       | 66 -------------------------
 t/unit-tests/t-prio-queue.c | 99 +++++++++++++++++++++++++++++++++++++
 6 files changed, 100 insertions(+), 120 deletions(-)
 delete mode 100644 t/helper/test-prio-queue.c
 delete mode 100755 t/t0009-prio-queue.sh
 create mode 100644 t/unit-tests/t-prio-queue.c

diff --git a/Makefile b/Makefile
index 312d95084c1..d5e48e656b3 100644
--- a/Makefile
+++ b/Makefile
@@ -828,7 +828,6 @@ TEST_BUILTINS_OBJS += test-partial-clone.o
 TEST_BUILTINS_OBJS += test-path-utils.o
 TEST_BUILTINS_OBJS += test-pcre2-config.o
 TEST_BUILTINS_OBJS += test-pkt-line.o
-TEST_BUILTINS_OBJS += test-prio-queue.o
 TEST_BUILTINS_OBJS += test-proc-receive.o
 TEST_BUILTINS_OBJS += test-progress.o
 TEST_BUILTINS_OBJS += test-reach.o
@@ -1340,6 +1339,7 @@ THIRD_PARTY_SOURCES += sha1dc/%
 
 UNIT_TEST_PROGRAMS += t-basic
 UNIT_TEST_PROGRAMS += t-strbuf
+UNIT_TEST_PROGRAMS += t-prio-queue
 UNIT_TEST_PROGS = $(patsubst %,$(UNIT_TEST_BIN)/%$X,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS = $(patsubst %,$(UNIT_TEST_DIR)/%.o,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/test-lib.o
diff --git a/t/helper/test-prio-queue.c b/t/helper/test-prio-queue.c
deleted file mode 100644
index f0bf255f5f0..00000000000
--- a/t/helper/test-prio-queue.c
+++ /dev/null
@@ -1,51 +0,0 @@
-#include "test-tool.h"
-#include "prio-queue.h"
-
-static int intcmp(const void *va, const void *vb, void *data UNUSED)
-{
-	const int *a = va, *b = vb;
-	return *a - *b;
-}
-
-static void show(int *v)
-{
-	if (!v)
-		printf("NULL\n");
-	else
-		printf("%d\n", *v);
-	free(v);
-}
-
-int cmd__prio_queue(int argc UNUSED, const char **argv)
-{
-	struct prio_queue pq = { intcmp };
-
-	while (*++argv) {
-		if (!strcmp(*argv, "get")) {
-			void *peek = prio_queue_peek(&pq);
-			void *get = prio_queue_get(&pq);
-			if (peek != get)
-				BUG("peek and get results do not match");
-			show(get);
-		} else if (!strcmp(*argv, "dump")) {
-			void *peek;
-			void *get;
-			while ((peek = prio_queue_peek(&pq))) {
-				get = prio_queue_get(&pq);
-				if (peek != get)
-					BUG("peek and get results do not match");
-				show(get);
-			}
-		} else if (!strcmp(*argv, "stack")) {
-			pq.compare = NULL;
-		} else {
-			int *v = xmalloc(sizeof(*v));
-			*v = atoi(*argv);
-			prio_queue_put(&pq, v);
-		}
-	}
-
-	clear_prio_queue(&pq);
-
-	return 0;
-}
diff --git a/t/helper/test-tool.c b/t/helper/test-tool.c
index 876cd2dc313..5f591b9718f 100644
--- a/t/helper/test-tool.c
+++ b/t/helper/test-tool.c
@@ -57,7 +57,6 @@ static struct test_cmd cmds[] = {
 	{ "path-utils", cmd__path_utils },
 	{ "pcre2-config", cmd__pcre2_config },
 	{ "pkt-line", cmd__pkt_line },
-	{ "prio-queue", cmd__prio_queue },
 	{ "proc-receive", cmd__proc_receive },
 	{ "progress", cmd__progress },
 	{ "reach", cmd__reach },
diff --git a/t/helper/test-tool.h b/t/helper/test-tool.h
index 70dd4eba119..b921138d8ec 100644
--- a/t/helper/test-tool.h
+++ b/t/helper/test-tool.h
@@ -50,7 +50,6 @@ int cmd__partial_clone(int argc, const char **argv);
 int cmd__path_utils(int argc, const char **argv);
 int cmd__pcre2_config(int argc, const char **argv);
 int cmd__pkt_line(int argc, const char **argv);
-int cmd__prio_queue(int argc, const char **argv);
 int cmd__proc_receive(int argc, const char **argv);
 int cmd__progress(int argc, const char **argv);
 int cmd__reach(int argc, const char **argv);
diff --git a/t/t0009-prio-queue.sh b/t/t0009-prio-queue.sh
deleted file mode 100755
index eea99107a48..00000000000
--- a/t/t0009-prio-queue.sh
+++ /dev/null
@@ -1,66 +0,0 @@
-#!/bin/sh
-
-test_description='basic tests for priority queue implementation'
-
-TEST_PASSES_SANITIZE_LEAK=true
-. ./test-lib.sh
-
-cat >expect <<'EOF'
-1
-2
-3
-4
-5
-5
-6
-7
-8
-9
-10
-EOF
-test_expect_success 'basic ordering' '
-	test-tool prio-queue 2 6 3 10 9 5 7 4 5 8 1 dump >actual &&
-	test_cmp expect actual
-'
-
-cat >expect <<'EOF'
-2
-3
-4
-1
-5
-6
-EOF
-test_expect_success 'mixed put and get' '
-	test-tool prio-queue 6 2 4 get 5 3 get get 1 dump >actual &&
-	test_cmp expect actual
-'
-
-cat >expect <<'EOF'
-1
-2
-NULL
-1
-2
-NULL
-EOF
-test_expect_success 'notice empty queue' '
-	test-tool prio-queue 1 2 get get get 1 2 get get get >actual &&
-	test_cmp expect actual
-'
-
-cat >expect <<'EOF'
-3
-2
-6
-4
-5
-1
-8
-EOF
-test_expect_success 'stack order' '
-	test-tool prio-queue stack 8 1 5 4 6 2 3 dump >actual &&
-	test_cmp expect actual
-'
-
-test_done
diff --git a/t/unit-tests/t-prio-queue.c b/t/unit-tests/t-prio-queue.c
new file mode 100644
index 00000000000..07b112f5894
--- /dev/null
+++ b/t/unit-tests/t-prio-queue.c
@@ -0,0 +1,99 @@
+#include "test-lib.h"
+#include "prio-queue.h"
+
+static int intcmp(const void *va, const void *vb, void *data UNUSED)
+{
+	const int *a = va, *b = vb;
+	return *a - *b;
+}
+
+static int show(int *v)
+{
+	int ret = -1;
+	if (v)
+		ret = *v;
+	free(v);
+	return ret;
+}
+
+static int test_prio_queue(const char **input, int *result)
+{
+	struct prio_queue pq = { intcmp };
+	int i = 0;
+
+	while (*input) {
+		if (!strcmp(*input, "get")) {
+			void *peek = prio_queue_peek(&pq);
+			void *get = prio_queue_get(&pq);
+			if (peek != get)
+				BUG("peek and get results do not match");
+			result[i++] = show(get);
+		} else if (!strcmp(*input, "dump")) {
+			void *peek;
+			void *get;
+			while ((peek = prio_queue_peek(&pq))) {
+				get = prio_queue_get(&pq);
+				if (peek != get)
+					BUG("peek and get results do not match");
+				result[i++] = show(get);
+			}
+		} else if (!strcmp(*input, "stack")) {
+			pq.compare = NULL;
+		} else if (!strcmp(*input, "reverse")) {
+			prio_queue_reverse(&pq);
+		} else {
+			int *v = xmalloc(sizeof(*v));
+			*v = atoi(*input);
+			prio_queue_put(&pq, v);
+		}
+		input++;
+	}
+
+	clear_prio_queue(&pq);
+
+	return 0;
+}
+
+#define INPUT_SIZE 6
+
+#define BASIC_INPUT "1", "2", "3", "4", "5", "5", "dump"
+#define BASIC_EXPECTED 1, 2, 3, 4, 5, 5
+
+#define MIXED_PUT_GET_INPUT "6", "2", "4", "get", "5", "3", "get", "get", "1", "dump"
+#define MIXED_PUT_GET_EXPECTED 2, 3, 4, 1, 5, 6
+
+#define EMPTY_QUEUE_INPUT "1", "2", "get", "get", "get", "1", "2", "get", "get", "get"
+#define EMPTY_QUEUE_EXPECTED 1, 2, -1, 1, 2, -1
+
+#define STACK_INPUT "stack", "1", "5", "4", "6", "2", "3", "dump"
+#define STACK_EXPECTED 3, 2, 6, 4, 5, 1
+
+#define REVERSE_STACK_INPUT "stack", "1", "2", "3", "4", "5", "6", "reverse", "dump"
+#define REVERSE_STACK_EXPECTED 1, 2, 3, 4, 5, 6
+
+#define TEST_INPUT(INPUT, EXPECTED, name)			\
+  static void test_##name(void)					\
+{								\
+	const char *input[] = {INPUT};				\
+	int expected[] = {EXPECTED};				\
+	int result[INPUT_SIZE];					\
+	test_prio_queue(input, result);				\
+	check(!memcmp(expected, result, sizeof(expected)));	\
+}
+
+TEST_INPUT(BASIC_INPUT, BASIC_EXPECTED, basic)
+TEST_INPUT(MIXED_PUT_GET_INPUT, MIXED_PUT_GET_EXPECTED, mixed)
+TEST_INPUT(EMPTY_QUEUE_INPUT, EMPTY_QUEUE_EXPECTED, empty)
+TEST_INPUT(STACK_INPUT, STACK_EXPECTED, stack)
+TEST_INPUT(REVERSE_STACK_INPUT, REVERSE_STACK_EXPECTED, reverse)
+
+int cmd_main(int argc, const char **argv)
+{
+	TEST(test_basic(), "prio-queue works for basic input");
+	TEST(test_mixed(), "prio-queue works for mixed put & get commands");
+	TEST(test_empty(), "prio-queue works when queue is empty");
+	TEST(test_stack(), "prio-queue works when used as a LIFO stack");
+	TEST(test_reverse(), "prio-queue works when LIFO stack is reversed");
+
+	return test_done();
+}

base-commit: 1a87c842ece327d03d08096395969aca5e0a6996
-- 
gitgitgadget

Re: [PATCH v2] tests: move t0009-prio-queue.sh to the new unit testing framework

[Junio C Hamano]

"Chandra Pratap via GitGitGadget" <gitgitgadget@gmail.com> writes:

> diff --git a/t/unit-tests/t-prio-queue.c b/t/unit-tests/t-prio-queue.c
> new file mode 100644
> index 00000000000..07b112f5894
> --- /dev/null
> +++ b/t/unit-tests/t-prio-queue.c
> @@ -0,0 +1,99 @@
> +#include "test-lib.h"
> +#include "prio-queue.h"
> +
> +static int intcmp(const void *va, const void *vb, void *data UNUSED)
> +{
> +	const int *a = va, *b = vb;
> +	return *a - *b;
> +}

This came from the original and looks obviously OK.

> +static int show(int *v)
> +{
> +	int ret = -1;
> +	if (v)
> +		ret = *v;
> +	free(v);
> +	return ret;
> +}

The original allowed us to differentiate "prio queue did not yield
anything" case and "the integer obtained from the queue happened to
be negative" cases, but with this, -1 is taken.

It is not a huge loss, as the tests can limit themselves to a subset
of "int" (say, positive integers only).  But this realization can
lead to further simplfication.

> +static int test_prio_queue(const char **input, int *result)

This takes an array of strings, but it does not have to.  Make it
take an array of "int" and then with something like

	#define MISSING	-1
        #define GET	-2
        #define DUMP	-3
	#define STACK	-4

you can get rid of strcmp(), atoi(), and xmalloc(), like so:

	while (*input) {
		int val = *input++;

		switch (val) {
		case GET:
			void *peek = prio_queue_peek(&pq);
			...
			result[i++] = peek ? (*(int*)peek) : MISSING;
			break;
		... other "commands" here ...
		default:
			prio_queue_put(&pq, val);
			break;			
		}
	}

I inlined the show() in the above illustration, but you can keep it
as a separate small helper function.  The point is that it makes it
far easier to follow by using the MISSING symbolic constant either
way.

> +{
> +	struct prio_queue pq = { intcmp };
> +	int i = 0;
> +
> +	while (*input) {
> +		if (!strcmp(*input, "get")) {
> +			void *peek = prio_queue_peek(&pq);
> +			void *get = prio_queue_get(&pq);
> +			if (peek != get)
> +				BUG("peek and get results do not match");
> +			result[i++] = show(get);
> +		} else if (!strcmp(*input, "dump")) {
> +			void *peek;
> +			void *get;
> +			while ((peek = prio_queue_peek(&pq))) {
> +				get = prio_queue_get(&pq);
> +				if (peek != get)
> +					BUG("peek and get results do not match");
> +				result[i++] = show(get);
> +			}
> +		} else if (!strcmp(*input, "stack")) {
> +			pq.compare = NULL;
> +		} else if (!strcmp(*input, "reverse")) {
> +			prio_queue_reverse(&pq);
> +		} else {
> +			int *v = xmalloc(sizeof(*v));
> +			*v = atoi(*input);
> +			prio_queue_put(&pq, v);
> +		}
> +		input++;
> +	}
> +
> +	clear_prio_queue(&pq);
> +
> +	return 0;
> +}
> +
> +#define INPUT_SIZE 6

You do not need this (see below)

> +#define BASIC_INPUT "1", "2", "3", "4", "5", "5", "dump"
> +#define BASIC_EXPECTED 1, 2, 3, 4, 5, 5
> +
> +#define MIXED_PUT_GET_INPUT "6", "2", "4", "get", "5", "3", "get", "get", "1", "dump"
> +#define MIXED_PUT_GET_EXPECTED 2, 3, 4, 1, 5, 6
> +
> +#define EMPTY_QUEUE_INPUT "1", "2", "get", "get", "get", "1", "2", "get", "get", "get"
> +#define EMPTY_QUEUE_EXPECTED 1, 2, -1, 1, 2, -1

And these input and expectation can become all integers, i.e.

	#define EMPTY_QUEUE_INPUT 1, 2, GET, GET, GET, 1, 2, GET, GET, GET
	#define EMPTY_QUEUE_EXPECTED 1, 2, MISSING, 1, 2, MISSING

> +
> +#define STACK_INPUT "stack", "1", "5", "4", "6", "2", "3", "dump"
> +#define STACK_EXPECTED 3, 2, 6, 4, 5, 1
> +
> +#define REVERSE_STACK_INPUT "stack", "1", "2", "3", "4", "5", "6", "reverse", "dump"
> +#define REVERSE_STACK_EXPECTED 1, 2, 3, 4, 5, 6
> +
> +#define TEST_INPUT(INPUT, EXPECTED, name)			\
> +  static void test_##name(void)					\
> +{								\
> +	const char *input[] = {INPUT};				\
> +	int expected[] = {EXPECTED};				\
> +	int result[INPUT_SIZE];					\

This can be written more like

	int result[ARRAY_SIZE(expected)]

so that you can freely extend each test without having to worry
about increasing the hardcoded limit.

> +	test_prio_queue(input, result);				\
> +	check(!memcmp(expected, result, sizeof(expected)));	\
> +}
> +
> +TEST_INPUT(BASIC_INPUT, BASIC_EXPECTED, basic)
> +TEST_INPUT(MIXED_PUT_GET_INPUT, MIXED_PUT_GET_EXPECTED, mixed)
> +TEST_INPUT(EMPTY_QUEUE_INPUT, EMPTY_QUEUE_EXPECTED, empty)
> +TEST_INPUT(STACK_INPUT, STACK_EXPECTED, stack)
> +TEST_INPUT(REVERSE_STACK_INPUT, REVERSE_STACK_EXPECTED, reverse)
> +
> +int cmd_main(int argc, const char **argv)
> +{
> +	TEST(test_basic(), "prio-queue works for basic input");
> +	TEST(test_mixed(), "prio-queue works for mixed put & get commands");
> +	TEST(test_empty(), "prio-queue works when queue is empty");
> +	TEST(test_stack(), "prio-queue works when used as a LIFO stack");
> +	TEST(test_reverse(), "prio-queue works when LIFO stack is reversed");
> +
> +	return test_done();
> +}
>
> base-commit: 1a87c842ece327d03d08096395969aca5e0a6996

Re: [PATCH v2] tests: move t0009-prio-queue.sh to the new unit testing framework

[Josh Steadmon]

On 2024.01.14 08:18, Chandra Pratap via GitGitGadget wrote:
> From: Chandra Pratap <chandrapratap3519@gmail.com>
> 
> t/t0009-prio-queue.sh along with t/helper/test-prio-queue.c unit
> tests Git's implementation of a priority queue. Migrate the
> test over to the new unit testing framework to simplify debugging
> and reduce test run-time. Refactor the required logic and add
> a new test case in addition to porting over the original ones in
> shell.
> 
> Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
> ---
>     tests: move t0009-prio-queue.sh to the new unit testing framework
> 
> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1642%2FChand-ra%2Fprio-queue-v2
> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1642/Chand-ra/prio-queue-v2
> Pull-Request: https://github.com/gitgitgadget/git/pull/1642
> 
> Range-diff vs v1:
> 
>  1:  ca20abe95ea ! 1:  60ac9b3c259 tests: move t0009-prio-queue.sh to the new unit testing framework
>      @@ t/unit-tests/t-prio-queue.c (new)
>       +#define REVERSE_STACK_INPUT "stack", "1", "2", "3", "4", "5", "6", "reverse", "dump"
>       +#define REVERSE_STACK_EXPECTED 1, 2, 3, 4, 5, 6
>       +
>      -+#define TEST_INPUT(INPUT, EXPECTED, name)		\
>      ++#define TEST_INPUT(INPUT, EXPECTED, name)			\
>       +  static void test_##name(void)					\
>      -+{											\
>      -+	const char *input[] = {INPUT};						\
>      -+	int expected[] = {EXPECTED};					\
>      -+	int result[INPUT_SIZE];								\
>      -+	test_prio_queue(input, result);						\
>      ++{								\
>      ++	const char *input[] = {INPUT};				\
>      ++	int expected[] = {EXPECTED};				\
>      ++	int result[INPUT_SIZE];					\
>      ++	test_prio_queue(input, result);				\
>       +	check(!memcmp(expected, result, sizeof(expected)));	\
>       +}
>       +
> 
> 
>  Makefile                    |  2 +-
>  t/helper/test-prio-queue.c  | 51 -------------------
>  t/helper/test-tool.c        |  1 -
>  t/helper/test-tool.h        |  1 -
>  t/t0009-prio-queue.sh       | 66 -------------------------
>  t/unit-tests/t-prio-queue.c | 99 +++++++++++++++++++++++++++++++++++++
>  6 files changed, 100 insertions(+), 120 deletions(-)
>  delete mode 100644 t/helper/test-prio-queue.c
>  delete mode 100755 t/t0009-prio-queue.sh
>  create mode 100644 t/unit-tests/t-prio-queue.c
> 
> diff --git a/Makefile b/Makefile
> index 312d95084c1..d5e48e656b3 100644
> --- a/Makefile
> +++ b/Makefile
> @@ -828,7 +828,6 @@ TEST_BUILTINS_OBJS += test-partial-clone.o
>  TEST_BUILTINS_OBJS += test-path-utils.o
>  TEST_BUILTINS_OBJS += test-pcre2-config.o
>  TEST_BUILTINS_OBJS += test-pkt-line.o
> -TEST_BUILTINS_OBJS += test-prio-queue.o
>  TEST_BUILTINS_OBJS += test-proc-receive.o
>  TEST_BUILTINS_OBJS += test-progress.o
>  TEST_BUILTINS_OBJS += test-reach.o
> @@ -1340,6 +1339,7 @@ THIRD_PARTY_SOURCES += sha1dc/%
>  
>  UNIT_TEST_PROGRAMS += t-basic
>  UNIT_TEST_PROGRAMS += t-strbuf
> +UNIT_TEST_PROGRAMS += t-prio-queue
>  UNIT_TEST_PROGS = $(patsubst %,$(UNIT_TEST_BIN)/%$X,$(UNIT_TEST_PROGRAMS))
>  UNIT_TEST_OBJS = $(patsubst %,$(UNIT_TEST_DIR)/%.o,$(UNIT_TEST_PROGRAMS))
>  UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/test-lib.o
> diff --git a/t/helper/test-prio-queue.c b/t/helper/test-prio-queue.c
> deleted file mode 100644
> index f0bf255f5f0..00000000000
> --- a/t/helper/test-prio-queue.c
> +++ /dev/null
> @@ -1,51 +0,0 @@
> -#include "test-tool.h"
> -#include "prio-queue.h"
> -
> -static int intcmp(const void *va, const void *vb, void *data UNUSED)
> -{
> -	const int *a = va, *b = vb;
> -	return *a - *b;
> -}
> -
> -static void show(int *v)
> -{
> -	if (!v)
> -		printf("NULL\n");
> -	else
> -		printf("%d\n", *v);
> -	free(v);
> -}
> -
> -int cmd__prio_queue(int argc UNUSED, const char **argv)
> -{
> -	struct prio_queue pq = { intcmp };
> -
> -	while (*++argv) {
> -		if (!strcmp(*argv, "get")) {
> -			void *peek = prio_queue_peek(&pq);
> -			void *get = prio_queue_get(&pq);
> -			if (peek != get)
> -				BUG("peek and get results do not match");
> -			show(get);
> -		} else if (!strcmp(*argv, "dump")) {
> -			void *peek;
> -			void *get;
> -			while ((peek = prio_queue_peek(&pq))) {
> -				get = prio_queue_get(&pq);
> -				if (peek != get)
> -					BUG("peek and get results do not match");
> -				show(get);
> -			}
> -		} else if (!strcmp(*argv, "stack")) {
> -			pq.compare = NULL;
> -		} else {
> -			int *v = xmalloc(sizeof(*v));
> -			*v = atoi(*argv);
> -			prio_queue_put(&pq, v);
> -		}
> -	}
> -
> -	clear_prio_queue(&pq);
> -
> -	return 0;
> -}
> diff --git a/t/helper/test-tool.c b/t/helper/test-tool.c
> index 876cd2dc313..5f591b9718f 100644
> --- a/t/helper/test-tool.c
> +++ b/t/helper/test-tool.c
> @@ -57,7 +57,6 @@ static struct test_cmd cmds[] = {
>  	{ "path-utils", cmd__path_utils },
>  	{ "pcre2-config", cmd__pcre2_config },
>  	{ "pkt-line", cmd__pkt_line },
> -	{ "prio-queue", cmd__prio_queue },
>  	{ "proc-receive", cmd__proc_receive },
>  	{ "progress", cmd__progress },
>  	{ "reach", cmd__reach },
> diff --git a/t/helper/test-tool.h b/t/helper/test-tool.h
> index 70dd4eba119..b921138d8ec 100644
> --- a/t/helper/test-tool.h
> +++ b/t/helper/test-tool.h
> @@ -50,7 +50,6 @@ int cmd__partial_clone(int argc, const char **argv);
>  int cmd__path_utils(int argc, const char **argv);
>  int cmd__pcre2_config(int argc, const char **argv);
>  int cmd__pkt_line(int argc, const char **argv);
> -int cmd__prio_queue(int argc, const char **argv);
>  int cmd__proc_receive(int argc, const char **argv);
>  int cmd__progress(int argc, const char **argv);
>  int cmd__reach(int argc, const char **argv);
> diff --git a/t/t0009-prio-queue.sh b/t/t0009-prio-queue.sh
> deleted file mode 100755
> index eea99107a48..00000000000
> --- a/t/t0009-prio-queue.sh
> +++ /dev/null
> @@ -1,66 +0,0 @@
> -#!/bin/sh
> -
> -test_description='basic tests for priority queue implementation'
> -
> -TEST_PASSES_SANITIZE_LEAK=true
> -. ./test-lib.sh
> -
> -cat >expect <<'EOF'
> -1
> -2
> -3
> -4
> -5
> -5
> -6
> -7
> -8
> -9
> -10
> -EOF
> -test_expect_success 'basic ordering' '
> -	test-tool prio-queue 2 6 3 10 9 5 7 4 5 8 1 dump >actual &&
> -	test_cmp expect actual
> -'
> -
> -cat >expect <<'EOF'
> -2
> -3
> -4
> -1
> -5
> -6
> -EOF
> -test_expect_success 'mixed put and get' '
> -	test-tool prio-queue 6 2 4 get 5 3 get get 1 dump >actual &&
> -	test_cmp expect actual
> -'
> -
> -cat >expect <<'EOF'
> -1
> -2
> -NULL
> -1
> -2
> -NULL
> -EOF
> -test_expect_success 'notice empty queue' '
> -	test-tool prio-queue 1 2 get get get 1 2 get get get >actual &&
> -	test_cmp expect actual
> -'
> -
> -cat >expect <<'EOF'
> -3
> -2
> -6
> -4
> -5
> -1
> -8
> -EOF
> -test_expect_success 'stack order' '
> -	test-tool prio-queue stack 8 1 5 4 6 2 3 dump >actual &&
> -	test_cmp expect actual
> -'
> -
> -test_done
> diff --git a/t/unit-tests/t-prio-queue.c b/t/unit-tests/t-prio-queue.c
> new file mode 100644
> index 00000000000..07b112f5894
> --- /dev/null
> +++ b/t/unit-tests/t-prio-queue.c
> @@ -0,0 +1,99 @@
> +#include "test-lib.h"
> +#include "prio-queue.h"
> +
> +static int intcmp(const void *va, const void *vb, void *data UNUSED)
> +{
> +	const int *a = va, *b = vb;
> +	return *a - *b;
> +}
> +
> +static int show(int *v)
> +{
> +	int ret = -1;
> +	if (v)
> +		ret = *v;
> +	free(v);
> +	return ret;
> +}
> +
> +static int test_prio_queue(const char **input, int *result)
> +{
> +	struct prio_queue pq = { intcmp };
> +	int i = 0;
> +
> +	while (*input) {
> +		if (!strcmp(*input, "get")) {

Running the test segfaults at the above strcmp() for me, from the very
first test_basic test case. I'm not sure why, there's not an obvious
problem that I can see. Does it run properly for you?


> +			void *peek = prio_queue_peek(&pq);
> +			void *get = prio_queue_get(&pq);
> +			if (peek != get)
> +				BUG("peek and get results do not match");
> +			result[i++] = show(get);
> +		} else if (!strcmp(*input, "dump")) {
> +			void *peek;
> +			void *get;
> +			while ((peek = prio_queue_peek(&pq))) {
> +				get = prio_queue_get(&pq);
> +				if (peek != get)
> +					BUG("peek and get results do not match");
> +				result[i++] = show(get);
> +			}
> +		} else if (!strcmp(*input, "stack")) {
> +			pq.compare = NULL;
> +		} else if (!strcmp(*input, "reverse")) {
> +			prio_queue_reverse(&pq);
> +		} else {
> +			int *v = xmalloc(sizeof(*v));
> +			*v = atoi(*input);
> +			prio_queue_put(&pq, v);
> +		}
> +		input++;
> +	}
> +
> +	clear_prio_queue(&pq);
> +
> +	return 0;
> +}
> +
> +#define INPUT_SIZE 6
> +
> +#define BASIC_INPUT "1", "2", "3", "4", "5", "5", "dump"
> +#define BASIC_EXPECTED 1, 2, 3, 4, 5, 5
> +
> +#define MIXED_PUT_GET_INPUT "6", "2", "4", "get", "5", "3", "get", "get", "1", "dump"
> +#define MIXED_PUT_GET_EXPECTED 2, 3, 4, 1, 5, 6
> +
> +#define EMPTY_QUEUE_INPUT "1", "2", "get", "get", "get", "1", "2", "get", "get", "get"
> +#define EMPTY_QUEUE_EXPECTED 1, 2, -1, 1, 2, -1
> +
> +#define STACK_INPUT "stack", "1", "5", "4", "6", "2", "3", "dump"
> +#define STACK_EXPECTED 3, 2, 6, 4, 5, 1
> +
> +#define REVERSE_STACK_INPUT "stack", "1", "2", "3", "4", "5", "6", "reverse", "dump"
> +#define REVERSE_STACK_EXPECTED 1, 2, 3, 4, 5, 6
> +
> +#define TEST_INPUT(INPUT, EXPECTED, name)			\
> +  static void test_##name(void)					\
> +{								\
> +	const char *input[] = {INPUT};				\
> +	int expected[] = {EXPECTED};				\
> +	int result[INPUT_SIZE];					\
> +	test_prio_queue(input, result);				\
> +	check(!memcmp(expected, result, sizeof(expected)));	\
> +}
> +
> +TEST_INPUT(BASIC_INPUT, BASIC_EXPECTED, basic)
> +TEST_INPUT(MIXED_PUT_GET_INPUT, MIXED_PUT_GET_EXPECTED, mixed)
> +TEST_INPUT(EMPTY_QUEUE_INPUT, EMPTY_QUEUE_EXPECTED, empty)
> +TEST_INPUT(STACK_INPUT, STACK_EXPECTED, stack)
> +TEST_INPUT(REVERSE_STACK_INPUT, REVERSE_STACK_EXPECTED, reverse)
> +
> +int cmd_main(int argc, const char **argv)
> +{
> +	TEST(test_basic(), "prio-queue works for basic input");
> +	TEST(test_mixed(), "prio-queue works for mixed put & get commands");
> +	TEST(test_empty(), "prio-queue works when queue is empty");
> +	TEST(test_stack(), "prio-queue works when used as a LIFO stack");
> +	TEST(test_reverse(), "prio-queue works when LIFO stack is reversed");
> +
> +	return test_done();
> +}
> 
> base-commit: 1a87c842ece327d03d08096395969aca5e0a6996
> -- 
> gitgitgadget

[PATCH v3] tests: move t0009-prio-queue.sh to the new unit testing framework

[Chandra Pratap via GitGitGadget]

From: Chandra Pratap <chandrapratap3519@gmail.com>

t/t0009-prio-queue.sh along with t/helper/test-prio-queue.c unit
tests Git's implementation of a priority queue. Migrate the
test over to the new unit testing framework to simplify debugging
and reduce test run-time. Refactor the required logic and add
a new test case in addition to porting over the original ones in
shell.

Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
    tests: move t0009-prio-queue.sh to the new unit testing framework

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1642%2FChand-ra%2Fprio-queue-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1642/Chand-ra/prio-queue-v3
Pull-Request: https://github.com/gitgitgadget/git/pull/1642

Range-diff vs v2:

 1:  60ac9b3c259 ! 1:  6b10028177a tests: move t0009-prio-queue.sh to the new unit testing framework
     @@ t/unit-tests/t-prio-queue.c (new)
      +	return *a - *b;
      +}
      +
     ++
     ++#define MISSING  -1
     ++#define DUMP	 -2
     ++#define STACK	 -3
     ++#define GET	 -4
     ++#define REVERSE  -5
     ++
      +static int show(int *v)
      +{
     -+	int ret = -1;
     -+	if (v)
     -+		ret = *v;
     -+	free(v);
     -+	return ret;
     ++	return v ? *v : MISSING;
      +}
      +
     -+static int test_prio_queue(const char **input, int *result)
     ++static int test_prio_queue(int *input, int *result)
      +{
      +	struct prio_queue pq = { intcmp };
      +	int i = 0;
      +
      +	while (*input) {
     -+		if (!strcmp(*input, "get")) {
     -+			void *peek = prio_queue_peek(&pq);
     -+			void *get = prio_queue_get(&pq);
     -+			if (peek != get)
     -+				BUG("peek and get results do not match");
     -+			result[i++] = show(get);
     -+		} else if (!strcmp(*input, "dump")) {
     -+			void *peek;
     -+			void *get;
     -+			while ((peek = prio_queue_peek(&pq))) {
     ++		int *val = input++;
     ++		void *peek, *get;
     ++		switch(*val) {
     ++			case GET:
     ++				peek = prio_queue_peek(&pq);
      +				get = prio_queue_get(&pq);
      +				if (peek != get)
     -+					BUG("peek and get results do not match");
     ++					BUG("peek and get results don't match");
      +				result[i++] = show(get);
     -+			}
     -+		} else if (!strcmp(*input, "stack")) {
     -+			pq.compare = NULL;
     -+		} else if (!strcmp(*input, "reverse")) {
     -+			prio_queue_reverse(&pq);
     -+		} else {
     -+			int *v = xmalloc(sizeof(*v));
     -+			*v = atoi(*input);
     -+			prio_queue_put(&pq, v);
     ++				break;
     ++			case DUMP:
     ++				while ((peek = prio_queue_peek(&pq))) {
     ++					get = prio_queue_get(&pq);
     ++					if (peek != get)
     ++						BUG("peek and get results don't match");
     ++					result[i++] = show(get);
     ++				}
     ++				break;
     ++			case STACK:
     ++				pq.compare = NULL;
     ++				break;
     ++			case REVERSE:
     ++				prio_queue_reverse(&pq);
     ++				break;
     ++			default:
     ++				prio_queue_put(&pq, val);
     ++				break;
      +		}
     -+		input++;
      +	}
     -+
      +	clear_prio_queue(&pq);
     -+
      +	return 0;
      +}
      +
     -+#define INPUT_SIZE 6
     -+
     -+#define BASIC_INPUT "1", "2", "3", "4", "5", "5", "dump"
     ++#define BASIC_INPUT 1, 2, 3, 4, 5, 5, DUMP
      +#define BASIC_EXPECTED 1, 2, 3, 4, 5, 5
      +
     -+#define MIXED_PUT_GET_INPUT "6", "2", "4", "get", "5", "3", "get", "get", "1", "dump"
     ++#define MIXED_PUT_GET_INPUT 6, 2, 4, GET, 5, 3, GET, GET, 1, DUMP
      +#define MIXED_PUT_GET_EXPECTED 2, 3, 4, 1, 5, 6
      +
     -+#define EMPTY_QUEUE_INPUT "1", "2", "get", "get", "get", "1", "2", "get", "get", "get"
     -+#define EMPTY_QUEUE_EXPECTED 1, 2, -1, 1, 2, -1
     ++#define EMPTY_QUEUE_INPUT 1, 2, GET, GET, GET, 1, 2, GET, GET, GET
     ++#define EMPTY_QUEUE_EXPECTED 1, 2, MISSING, 1, 2, MISSING
      +
     -+#define STACK_INPUT "stack", "1", "5", "4", "6", "2", "3", "dump"
     ++#define STACK_INPUT STACK, 1, 5, 4, 6, 2, 3, DUMP
      +#define STACK_EXPECTED 3, 2, 6, 4, 5, 1
      +
     -+#define REVERSE_STACK_INPUT "stack", "1", "2", "3", "4", "5", "6", "reverse", "dump"
     ++#define REVERSE_STACK_INPUT STACK, 1, 2, 3, 4, 5, 6, REVERSE, DUMP
      +#define REVERSE_STACK_EXPECTED 1, 2, 3, 4, 5, 6
      +
      +#define TEST_INPUT(INPUT, EXPECTED, name)			\
     -+  static void test_##name(void)					\
     ++  static void test_##name(void)				\
      +{								\
     -+	const char *input[] = {INPUT};				\
     ++	int input[] = {INPUT};					\
      +	int expected[] = {EXPECTED};				\
     -+	int result[INPUT_SIZE];					\
     ++	int result[ARRAY_SIZE(expected)];			\
      +	test_prio_queue(input, result);				\
      +	check(!memcmp(expected, result, sizeof(expected)));	\
      +}


 Makefile                    |   2 +-
 t/helper/test-prio-queue.c  |  51 ------------------
 t/helper/test-tool.c        |   1 -
 t/helper/test-tool.h        |   1 -
 t/t0009-prio-queue.sh       |  66 -----------------------
 t/unit-tests/t-prio-queue.c | 101 ++++++++++++++++++++++++++++++++++++
 6 files changed, 102 insertions(+), 120 deletions(-)
 delete mode 100644 t/helper/test-prio-queue.c
 delete mode 100755 t/t0009-prio-queue.sh
 create mode 100644 t/unit-tests/t-prio-queue.c

diff --git a/Makefile b/Makefile
index 312d95084c1..d5e48e656b3 100644
--- a/Makefile
+++ b/Makefile
@@ -828,7 +828,6 @@ TEST_BUILTINS_OBJS += test-partial-clone.o
 TEST_BUILTINS_OBJS += test-path-utils.o
 TEST_BUILTINS_OBJS += test-pcre2-config.o
 TEST_BUILTINS_OBJS += test-pkt-line.o
-TEST_BUILTINS_OBJS += test-prio-queue.o
 TEST_BUILTINS_OBJS += test-proc-receive.o
 TEST_BUILTINS_OBJS += test-progress.o
 TEST_BUILTINS_OBJS += test-reach.o
@@ -1340,6 +1339,7 @@ THIRD_PARTY_SOURCES += sha1dc/%
 
 UNIT_TEST_PROGRAMS += t-basic
 UNIT_TEST_PROGRAMS += t-strbuf
+UNIT_TEST_PROGRAMS += t-prio-queue
 UNIT_TEST_PROGS = $(patsubst %,$(UNIT_TEST_BIN)/%$X,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS = $(patsubst %,$(UNIT_TEST_DIR)/%.o,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/test-lib.o
diff --git a/t/helper/test-prio-queue.c b/t/helper/test-prio-queue.c
deleted file mode 100644
index f0bf255f5f0..00000000000
--- a/t/helper/test-prio-queue.c
+++ /dev/null
@@ -1,51 +0,0 @@
-#include "test-tool.h"
-#include "prio-queue.h"
-
-static int intcmp(const void *va, const void *vb, void *data UNUSED)
-{
-	const int *a = va, *b = vb;
-	return *a - *b;
-}
-
-static void show(int *v)
-{
-	if (!v)
-		printf("NULL\n");
-	else
-		printf("%d\n", *v);
-	free(v);
-}
-
-int cmd__prio_queue(int argc UNUSED, const char **argv)
-{
-	struct prio_queue pq = { intcmp };
-
-	while (*++argv) {
-		if (!strcmp(*argv, "get")) {
-			void *peek = prio_queue_peek(&pq);
-			void *get = prio_queue_get(&pq);
-			if (peek != get)
-				BUG("peek and get results do not match");
-			show(get);
-		} else if (!strcmp(*argv, "dump")) {
-			void *peek;
-			void *get;
-			while ((peek = prio_queue_peek(&pq))) {
-				get = prio_queue_get(&pq);
-				if (peek != get)
-					BUG("peek and get results do not match");
-				show(get);
-			}
-		} else if (!strcmp(*argv, "stack")) {
-			pq.compare = NULL;
-		} else {
-			int *v = xmalloc(sizeof(*v));
-			*v = atoi(*argv);
-			prio_queue_put(&pq, v);
-		}
-	}
-
-	clear_prio_queue(&pq);
-
-	return 0;
-}
diff --git a/t/helper/test-tool.c b/t/helper/test-tool.c
index 876cd2dc313..5f591b9718f 100644
--- a/t/helper/test-tool.c
+++ b/t/helper/test-tool.c
@@ -57,7 +57,6 @@ static struct test_cmd cmds[] = {
 	{ "path-utils", cmd__path_utils },
 	{ "pcre2-config", cmd__pcre2_config },
 	{ "pkt-line", cmd__pkt_line },
-	{ "prio-queue", cmd__prio_queue },
 	{ "proc-receive", cmd__proc_receive },
 	{ "progress", cmd__progress },
 	{ "reach", cmd__reach },
diff --git a/t/helper/test-tool.h b/t/helper/test-tool.h
index 70dd4eba119..b921138d8ec 100644
--- a/t/helper/test-tool.h
+++ b/t/helper/test-tool.h
@@ -50,7 +50,6 @@ int cmd__partial_clone(int argc, const char **argv);
 int cmd__path_utils(int argc, const char **argv);
 int cmd__pcre2_config(int argc, const char **argv);
 int cmd__pkt_line(int argc, const char **argv);
-int cmd__prio_queue(int argc, const char **argv);
 int cmd__proc_receive(int argc, const char **argv);
 int cmd__progress(int argc, const char **argv);
 int cmd__reach(int argc, const char **argv);
diff --git a/t/t0009-prio-queue.sh b/t/t0009-prio-queue.sh
deleted file mode 100755
index eea99107a48..00000000000
--- a/t/t0009-prio-queue.sh
+++ /dev/null
@@ -1,66 +0,0 @@
-#!/bin/sh
-
-test_description='basic tests for priority queue implementation'
-
-TEST_PASSES_SANITIZE_LEAK=true
-. ./test-lib.sh
-
-cat >expect <<'EOF'
-1
-2
-3
-4
-5
-5
-6
-7
-8
-9
-10
-EOF
-test_expect_success 'basic ordering' '
-	test-tool prio-queue 2 6 3 10 9 5 7 4 5 8 1 dump >actual &&
-	test_cmp expect actual
-'
-
-cat >expect <<'EOF'
-2
-3
-4
-1
-5
-6
-EOF
-test_expect_success 'mixed put and get' '
-	test-tool prio-queue 6 2 4 get 5 3 get get 1 dump >actual &&
-	test_cmp expect actual
-'
-
-cat >expect <<'EOF'
-1
-2
-NULL
-1
-2
-NULL
-EOF
-test_expect_success 'notice empty queue' '
-	test-tool prio-queue 1 2 get get get 1 2 get get get >actual &&
-	test_cmp expect actual
-'
-
-cat >expect <<'EOF'
-3
-2
-6
-4
-5
-1
-8
-EOF
-test_expect_success 'stack order' '
-	test-tool prio-queue stack 8 1 5 4 6 2 3 dump >actual &&
-	test_cmp expect actual
-'
-
-test_done
diff --git a/t/unit-tests/t-prio-queue.c b/t/unit-tests/t-prio-queue.c
new file mode 100644
index 00000000000..0b826b463e9
--- /dev/null
+++ b/t/unit-tests/t-prio-queue.c
@@ -0,0 +1,101 @@
+#include "test-lib.h"
+#include "prio-queue.h"
+
+static int intcmp(const void *va, const void *vb, void *data UNUSED)
+{
+	const int *a = va, *b = vb;
+	return *a - *b;
+}
+
+
+#define MISSING  -1
+#define DUMP	 -2
+#define STACK	 -3
+#define GET	 -4
+#define REVERSE  -5
+
+static int show(int *v)
+{
+	return v ? *v : MISSING;
+}
+
+static int test_prio_queue(int *input, int *result)
+{
+	struct prio_queue pq = { intcmp };
+	int i = 0;
+
+	while (*input) {
+		int *val = input++;
+		void *peek, *get;
+		switch(*val) {
+			case GET:
+				peek = prio_queue_peek(&pq);
+				get = prio_queue_get(&pq);
+				if (peek != get)
+					BUG("peek and get results don't match");
+				result[i++] = show(get);
+				break;
+			case DUMP:
+				while ((peek = prio_queue_peek(&pq))) {
+					get = prio_queue_get(&pq);
+					if (peek != get)
+						BUG("peek and get results don't match");
+					result[i++] = show(get);
+				}
+				break;
+			case STACK:
+				pq.compare = NULL;
+				break;
+			case REVERSE:
+				prio_queue_reverse(&pq);
+				break;
+			default:
+				prio_queue_put(&pq, val);
+				break;
+		}
+	}
+	clear_prio_queue(&pq);
+	return 0;
+}
+
+#define BASIC_INPUT 1, 2, 3, 4, 5, 5, DUMP
+#define BASIC_EXPECTED 1, 2, 3, 4, 5, 5
+
+#define MIXED_PUT_GET_INPUT 6, 2, 4, GET, 5, 3, GET, GET, 1, DUMP
+#define MIXED_PUT_GET_EXPECTED 2, 3, 4, 1, 5, 6
+
+#define EMPTY_QUEUE_INPUT 1, 2, GET, GET, GET, 1, 2, GET, GET, GET
+#define EMPTY_QUEUE_EXPECTED 1, 2, MISSING, 1, 2, MISSING
+
+#define STACK_INPUT STACK, 1, 5, 4, 6, 2, 3, DUMP
+#define STACK_EXPECTED 3, 2, 6, 4, 5, 1
+
+#define REVERSE_STACK_INPUT STACK, 1, 2, 3, 4, 5, 6, REVERSE, DUMP
+#define REVERSE_STACK_EXPECTED 1, 2, 3, 4, 5, 6
+
+#define TEST_INPUT(INPUT, EXPECTED, name)			\
+  static void test_##name(void)				\
+{								\
+	int input[] = {INPUT};					\
+	int expected[] = {EXPECTED};				\
+	int result[ARRAY_SIZE(expected)];			\
+	test_prio_queue(input, result);				\
+	check(!memcmp(expected, result, sizeof(expected)));	\
+}
+
+TEST_INPUT(BASIC_INPUT, BASIC_EXPECTED, basic)
+TEST_INPUT(MIXED_PUT_GET_INPUT, MIXED_PUT_GET_EXPECTED, mixed)
+TEST_INPUT(EMPTY_QUEUE_INPUT, EMPTY_QUEUE_EXPECTED, empty)
+TEST_INPUT(STACK_INPUT, STACK_EXPECTED, stack)
+TEST_INPUT(REVERSE_STACK_INPUT, REVERSE_STACK_EXPECTED, reverse)
+
+int cmd_main(int argc, const char **argv)
+{
+	TEST(test_basic(), "prio-queue works for basic input");
+	TEST(test_mixed(), "prio-queue works for mixed put & get commands");
+	TEST(test_empty(), "prio-queue works when queue is empty");
+	TEST(test_stack(), "prio-queue works when used as a LIFO stack");
+	TEST(test_reverse(), "prio-queue works when LIFO stack is reversed");
+
+	return test_done();
+}

base-commit: 1a87c842ece327d03d08096395969aca5e0a6996
-- 
gitgitgadget

Re: [PATCH v3] tests: move t0009-prio-queue.sh to the new unit testing framework

[Junio C Hamano]

"Chandra Pratap via GitGitGadget" <gitgitgadget@gmail.com> writes:

> +static int test_prio_queue(int *input, int *result)
> +{
> +	struct prio_queue pq = { intcmp };
> +	int i = 0;
> +
> +	while (*input) {
> +		int *val = input++;
> +		void *peek, *get;
> +		switch(*val) {

Ah, this one is a bit tricky.  I would have expected that we can
make val a pure integer, but because we need to give the address of
the element to be placed in the queue, not the value to be placed as
an element in the queue, to prio_queue_put(), we would need the
pointer.

I wonder if writing this as a more conventional for(;;) loop would
make it easier to handle, i.e.

	int val, i;

	for (i = 0; (val = *input); input++) {
		switch (val) {
		case ...:
		...
		default:
			prio_queue_put(&pq, input);
			break;
		}
	}

> +...
> +			default:
> +				prio_queue_put(&pq, val);
> +				break;
> +		}
> +	}
> +	clear_prio_queue(&pq);
> +	return 0;
> +}

> +#define TEST_INPUT(INPUT, EXPECTED, name)			\
> +  static void test_##name(void)				\
> +{								\
> +	int input[] = {INPUT};					\

I think I missed this myself in my review the last round, but we
need the sentinel value 0 at the end, i.e.,

	int input[] = {INPUT, 0};

because the test_prio_queue() loops "while (*input)".  Otherwise
the loop would not terminate.

> +	int expected[] = {EXPECTED};				\
> +	int result[ARRAY_SIZE(expected)];			\

These arrays are correct.

> +	test_prio_queue(input, result);				\
> +	check(!memcmp(expected, result, sizeof(expected)));	\

So is this check.

> +}
> +
> +TEST_INPUT(BASIC_INPUT, BASIC_EXPECTED, basic)
> +TEST_INPUT(MIXED_PUT_GET_INPUT, MIXED_PUT_GET_EXPECTED, mixed)
> +TEST_INPUT(EMPTY_QUEUE_INPUT, EMPTY_QUEUE_EXPECTED, empty)
> +TEST_INPUT(STACK_INPUT, STACK_EXPECTED, stack)
> +TEST_INPUT(REVERSE_STACK_INPUT, REVERSE_STACK_EXPECTED, reverse)
> +
> +int cmd_main(int argc, const char **argv)
> +{
> +	TEST(test_basic(), "prio-queue works for basic input");
> +	TEST(test_mixed(), "prio-queue works for mixed put & get commands");
> +	TEST(test_empty(), "prio-queue works when queue is empty");
> +	TEST(test_stack(), "prio-queue works when used as a LIFO stack");
> +	TEST(test_reverse(), "prio-queue works when LIFO stack is reversed");
> +
> +	return test_done();
> +}

Other than that, looking good.  Thanks.

Re: [PATCH v3] tests: move t0009-prio-queue.sh to the new unit testing framework

[Junio C Hamano]

I forgot to examine the contents of the tests themselves.

> -cat >expect <<'EOF'
> -1
> -2
> -3
> -4
> -5
> -5
> -6
> -7
> -8
> -9
> -10
> -EOF
> -test_expect_success 'basic ordering' '
> -	test-tool prio-queue 2 6 3 10 9 5 7 4 5 8 1 dump >actual &&
> -	test_cmp expect actual
> -'

This seems to have been lost from the converted test.  Your basic
input test feeds an already sorted array of 6 items and dump to see
they are the same already sorted array, which is a lot less
interesting than the above.

> -cat >expect <<'EOF'
> -2
> -3
> -4
> -1
> -5
> -6
> -EOF
> -test_expect_success 'mixed put and get' '
> -	test-tool prio-queue 6 2 4 get 5 3 get get 1 dump >actual &&
> -	test_cmp expect actual
> -'

This is a faithful conversion.

> -cat >expect <<'EOF'
> -1
> -2
> -NULL
> -1
> -2
> -NULL
> -EOF
> -test_expect_success 'notice empty queue' '
> -	test-tool prio-queue 1 2 get get get 1 2 get get get >actual &&
> -	test_cmp expect actual
> -'

This too.

> -cat >expect <<'EOF'
> -3
> -2
> -6
> -4
> -5
> -1
> -8
> -EOF
> -test_expect_success 'stack order' '
> -	test-tool prio-queue stack 8 1 5 4 6 2 3 dump >actual &&
> -	test_cmp expect actual
> -'

This test got truncated in your version, which is not horribly
wrong, but if we claim "move t0009 to unit testing", people would
expect to see a conversion faithful to the original.  And with the
use of result[ARRAY_SIZE(expected)], there is no reason to truncate
the original test with this version, no?

Thanks.

Re: [PATCH v3] tests: move t0009-prio-queue.sh to the new unit testing framework

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> I forgot to examine the contents of the tests themselves.
> ...

FYI: taking them all together, here is what I tentatively queued on
top of what was posted as v3 before I start doing today's
integration cycle.

Thanks.

----- >8 -----
Subject: [PATCH] SQUASH???

---
 t/unit-tests/t-prio-queue.c | 57 ++++++++++++++++++-------------------
 1 file changed, 28 insertions(+), 29 deletions(-)

diff --git a/t/unit-tests/t-prio-queue.c b/t/unit-tests/t-prio-queue.c
index 0b826b463e..3014a67ac2 100644
--- a/t/unit-tests/t-prio-queue.c
+++ b/t/unit-tests/t-prio-queue.c
@@ -22,44 +22,43 @@ static int show(int *v)
 static int test_prio_queue(int *input, int *result)
 {
 	struct prio_queue pq = { intcmp };
-	int i = 0;
+	int i, val;
 
-	while (*input) {
-		int *val = input++;
+	for (i = 0; (val = *input); input++) {
 		void *peek, *get;
-		switch(*val) {
-			case GET:
-				peek = prio_queue_peek(&pq);
+		switch (val) {
+		case GET:
+			peek = prio_queue_peek(&pq);
+			get = prio_queue_get(&pq);
+			if (peek != get)
+				BUG("peek and get results don't match");
+			result[i++] = show(get);
+			break;
+		case DUMP:
+			while ((peek = prio_queue_peek(&pq))) {
 				get = prio_queue_get(&pq);
 				if (peek != get)
 					BUG("peek and get results don't match");
 				result[i++] = show(get);
-				break;
-			case DUMP:
-				while ((peek = prio_queue_peek(&pq))) {
-					get = prio_queue_get(&pq);
-					if (peek != get)
-						BUG("peek and get results don't match");
-					result[i++] = show(get);
-				}
-				break;
-			case STACK:
-				pq.compare = NULL;
-				break;
-			case REVERSE:
-				prio_queue_reverse(&pq);
-				break;
-			default:
-				prio_queue_put(&pq, val);
-				break;
+			}
+			break;
+		case STACK:
+			pq.compare = NULL;
+			break;
+		case REVERSE:
+			prio_queue_reverse(&pq);
+			break;
+		default:
+			prio_queue_put(&pq, input);
+			break;
 		}
 	}
 	clear_prio_queue(&pq);
 	return 0;
 }
 
-#define BASIC_INPUT 1, 2, 3, 4, 5, 5, DUMP
-#define BASIC_EXPECTED 1, 2, 3, 4, 5, 5
+#define BASIC_INPUT 2, 6, 3, 10, 9, 5, 7, 4, 5, 8, 1, DUMP
+#define BASIC_EXPECTED 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 10
 
 #define MIXED_PUT_GET_INPUT 6, 2, 4, GET, 5, 3, GET, GET, 1, DUMP
 #define MIXED_PUT_GET_EXPECTED 2, 3, 4, 1, 5, 6
@@ -67,8 +66,8 @@ static int test_prio_queue(int *input, int *result)
 #define EMPTY_QUEUE_INPUT 1, 2, GET, GET, GET, 1, 2, GET, GET, GET
 #define EMPTY_QUEUE_EXPECTED 1, 2, MISSING, 1, 2, MISSING
 
-#define STACK_INPUT STACK, 1, 5, 4, 6, 2, 3, DUMP
-#define STACK_EXPECTED 3, 2, 6, 4, 5, 1
+#define STACK_INPUT STACK, 8, 1, 5, 4, 6, 2, 3, DUMP
+#define STACK_EXPECTED 3, 2, 6, 4, 5, 1, 8
 
 #define REVERSE_STACK_INPUT STACK, 1, 2, 3, 4, 5, 6, REVERSE, DUMP
 #define REVERSE_STACK_EXPECTED 1, 2, 3, 4, 5, 6
@@ -76,7 +75,7 @@ static int test_prio_queue(int *input, int *result)
 #define TEST_INPUT(INPUT, EXPECTED, name)			\
   static void test_##name(void)				\
 {								\
-	int input[] = {INPUT};					\
+	int input[] = {INPUT, 0};				\
 	int expected[] = {EXPECTED};				\
 	int result[ARRAY_SIZE(expected)];			\
 	test_prio_queue(input, result);				\
-- 
2.43.0-367-g186b115d30

Re: [PATCH v3] tests: move t0009-prio-queue.sh to the new unit testing framework

[Jeff King]

On Wed, Jan 17, 2024 at 02:38:23PM +0000, Chandra Pratap via GitGitGadget wrote:

> +#define TEST_INPUT(INPUT, EXPECTED, name)			\
> +  static void test_##name(void)				\
> +{								\
> +	int input[] = {INPUT};					\
> +	int expected[] = {EXPECTED};				\
> +	int result[ARRAY_SIZE(expected)];			\
> +	test_prio_queue(input, result);				\
> +	check(!memcmp(expected, result, sizeof(expected)));	\
> +}

It is somewhat unfortunate that a failing test here gives a fairly
uninformative message like:

  # check "!memcmp(expected, result, sizeof(expected))" failed at t/unit-tests/t-prio-queue.c:89
  not ok 5 - prio-queue works when LIFO stack is reversed

whereas the original t0009 you get a nice diff between expected and
actual output. I guess this is a place where the test framework could
help us more with a specialized check_memequal() or something that
showed the differing bytes on failure (of course being C, it has no type
info so it wouldn't even know these are ints!).

Another solution would be to have the test function check the result as
it is computed rather than storing it in an array. That would also solve
another potential problem: undefined behavior if the result is not the
expected size. If there is a bug that causes too much output we'd
overflow our buffer. If too few, we'll end up comparing uninitialized
memory (which could even accidentally have the correct values,
especially if it's recycled from a previous test!). Neither of those
should happen in practice, but then the whole point of this exercise is
to test the code.

I admit I find myself a little skeptical in general of this whole "let's
do tests in C" framework.

-Peff

Re: [PATCH v3] tests: move t0009-prio-queue.sh to the new unit testing framework

[Phillip Wood]

On 17/01/2024 14:38, Chandra Pratap via GitGitGadget wrote:
> From: Chandra Pratap <chandrapratap3519@gmail.com>
> 
> t/t0009-prio-queue.sh along with t/helper/test-prio-queue.c unit
> tests Git's implementation of a priority queue. Migrate the
> test over to the new unit testing framework to simplify debugging
> and reduce test run-time. Refactor the required logic and add
> a new test case in addition to porting over the original ones in
> shell.

Thanks for working on this, it is good to see people exploring the unit 
test framework. I agree with the points that Junio and Peff have already 
made, I've got a couple of additional comments below.

 > [...]
> +static int test_prio_queue(int *input, int *result)

This function does not need to return a value.

> +{
> +	struct prio_queue pq = { intcmp };
> +	int i = 0;
> +
> +	while (*input) {

I agree with Junio that a for() loop would be better here, but I think 
that rather than testing for '0' we should just pass the length of the 
input array to this function.

> +		int *val = input++;
> +		void *peek, *get;
> +		switch(*val) {
> +			case GET:
> +				peek = prio_queue_peek(&pq);
> +				get = prio_queue_get(&pq);
> +				if (peek != get)
> +					BUG("peek and get results don't match");

If possible avoid calling BUG() in unit test code as it aborts the whole 
test program, not just the current test. You can use check() and return 
early instead

	if (!check(peek, !=, get))
		return;

> +				result[i++] = show(get);

I agree with Peff that it would be safer just to use check_int() here. 
If you switch to a for loop with an index you can also print the current 
index with

	test_msg("index %d", i);

Which will help diagnose which item in the queue is failing.

Alternatively we could grow result dynamically using ALLOC_GROW() and 
add a function to compare two arrays of integers. Such a function should 
take the two lengths, one for each array.

Best Wishes

Phillip

[PATCH v4] tests: move t0009-prio-queue.sh to the new unit testing framework

[Chandra Pratap via GitGitGadget]

From: Chandra Pratap <chandrapratap3519@gmail.com>

t/t0009-prio-queue.sh along with t/helper/test-prio-queue.c unit
tests Git's implementation of a priority queue. Migrate the
test over to the new unit testing framework to simplify debugging
and reduce test run-time. Refactor the required logic and add
a new test case in addition to porting over the original ones in
shell.

Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
    tests: move t0009-prio-queue.sh to the new unit testing framework
    
    Thanks to Jeff, Philip and Junio for your valuable feedbacks! I have
    updated the patch so that the resulting tests are more verbose when they
    fail and lesser prone to memory related errors.

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1642%2FChand-ra%2Fprio-queue-v4
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1642/Chand-ra/prio-queue-v4
Pull-Request: https://github.com/gitgitgadget/git/pull/1642

Range-diff vs v3:

 1:  6b10028177a ! 1:  e9a0dba6f47 tests: move t0009-prio-queue.sh to the new unit testing framework
     @@ t/unit-tests/t-prio-queue.c (new)
      +	return v ? *v : MISSING;
      +}
      +
     -+static int test_prio_queue(int *input, int *result)
     ++static void test_prio_queue(int *input, int *result, size_t input_size)
      +{
      +	struct prio_queue pq = { intcmp };
     -+	int i = 0;
      +
     -+	while (*input) {
     -+		int *val = input++;
     ++	for (int i = 0, j = 0; i < input_size; i++) {
      +		void *peek, *get;
     -+		switch(*val) {
     -+			case GET:
     -+				peek = prio_queue_peek(&pq);
     ++		switch(input[i]) {
     ++		case GET:
     ++			peek = prio_queue_peek(&pq);
     ++			get = prio_queue_get(&pq);
     ++			if (!check(peek == get))
     ++				return;
     ++			if(!check_int(result[j++], ==, show(get)))
     ++				test_msg("failed at result[] index %d", j-1);
     ++			break;
     ++		case DUMP:
     ++			while ((peek = prio_queue_peek(&pq))) {
      +				get = prio_queue_get(&pq);
     -+				if (peek != get)
     -+					BUG("peek and get results don't match");
     -+				result[i++] = show(get);
     -+				break;
     -+			case DUMP:
     -+				while ((peek = prio_queue_peek(&pq))) {
     -+					get = prio_queue_get(&pq);
     -+					if (peek != get)
     -+						BUG("peek and get results don't match");
     -+					result[i++] = show(get);
     -+				}
     -+				break;
     -+			case STACK:
     -+				pq.compare = NULL;
     -+				break;
     -+			case REVERSE:
     -+				prio_queue_reverse(&pq);
     -+				break;
     -+			default:
     -+				prio_queue_put(&pq, val);
     -+				break;
     ++				if (!check(peek == get))
     ++					return;
     ++				if(!check_int(result[j++], ==, show(get)))
     ++					test_msg("failed at result[] index %d", j-1);
     ++			}
     ++			break;
     ++		case STACK:
     ++			pq.compare = NULL;
     ++			break;
     ++		case REVERSE:
     ++			prio_queue_reverse(&pq);
     ++			break;
     ++		default:
     ++			prio_queue_put(&pq, &input[i]);
     ++			break;
      +		}
      +	}
      +	clear_prio_queue(&pq);
     -+	return 0;
      +}
      +
     -+#define BASIC_INPUT 1, 2, 3, 4, 5, 5, DUMP
     -+#define BASIC_EXPECTED 1, 2, 3, 4, 5, 5
     ++#define BASIC_INPUT 2, 6, 3, 10, 9, 5, 7, 4, 5, 8, 1, DUMP
     ++#define BASIC_RESULT 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 10
      +
      +#define MIXED_PUT_GET_INPUT 6, 2, 4, GET, 5, 3, GET, GET, 1, DUMP
     -+#define MIXED_PUT_GET_EXPECTED 2, 3, 4, 1, 5, 6
     ++#define MIXED_PUT_GET_RESULT 2, 3, 4, 1, 5, 6
      +
      +#define EMPTY_QUEUE_INPUT 1, 2, GET, GET, GET, 1, 2, GET, GET, GET
     -+#define EMPTY_QUEUE_EXPECTED 1, 2, MISSING, 1, 2, MISSING
     ++#define EMPTY_QUEUE_RESULT 1, 2, MISSING, 1, 2, MISSING
      +
     -+#define STACK_INPUT STACK, 1, 5, 4, 6, 2, 3, DUMP
     -+#define STACK_EXPECTED 3, 2, 6, 4, 5, 1
     ++#define STACK_INPUT STACK, 8, 1, 5, 4, 6, 2, 3, DUMP
     ++#define STACK_RESULT 3, 2, 6, 4, 5, 1, 8
      +
      +#define REVERSE_STACK_INPUT STACK, 1, 2, 3, 4, 5, 6, REVERSE, DUMP
     -+#define REVERSE_STACK_EXPECTED 1, 2, 3, 4, 5, 6
     ++#define REVERSE_STACK_RESULT 1, 2, 3, 4, 5, 6
      +
     -+#define TEST_INPUT(INPUT, EXPECTED, name)			\
     ++#define TEST_INPUT(INPUT, RESULT, name)			\
      +  static void test_##name(void)				\
      +{								\
      +	int input[] = {INPUT};					\
     -+	int expected[] = {EXPECTED};				\
     -+	int result[ARRAY_SIZE(expected)];			\
     -+	test_prio_queue(input, result);				\
     -+	check(!memcmp(expected, result, sizeof(expected)));	\
     ++	int result[] = {RESULT};				\
     ++	test_prio_queue(input, result, ARRAY_SIZE(input));	\
      +}
      +
     -+TEST_INPUT(BASIC_INPUT, BASIC_EXPECTED, basic)
     -+TEST_INPUT(MIXED_PUT_GET_INPUT, MIXED_PUT_GET_EXPECTED, mixed)
     -+TEST_INPUT(EMPTY_QUEUE_INPUT, EMPTY_QUEUE_EXPECTED, empty)
     -+TEST_INPUT(STACK_INPUT, STACK_EXPECTED, stack)
     -+TEST_INPUT(REVERSE_STACK_INPUT, REVERSE_STACK_EXPECTED, reverse)
     ++TEST_INPUT(BASIC_INPUT, BASIC_RESULT, basic)
     ++TEST_INPUT(MIXED_PUT_GET_INPUT, MIXED_PUT_GET_RESULT, mixed)
     ++TEST_INPUT(EMPTY_QUEUE_INPUT, EMPTY_QUEUE_RESULT, empty)
     ++TEST_INPUT(STACK_INPUT, STACK_RESULT, stack)
     ++TEST_INPUT(REVERSE_STACK_INPUT, REVERSE_STACK_RESULT, reverse)
      +
      +int cmd_main(int argc, const char **argv)
      +{


 Makefile                    |  2 +-
 t/helper/test-prio-queue.c  | 51 -------------------
 t/helper/test-tool.c        |  1 -
 t/helper/test-tool.h        |  1 -
 t/t0009-prio-queue.sh       | 66 -------------------------
 t/unit-tests/t-prio-queue.c | 98 +++++++++++++++++++++++++++++++++++++
 6 files changed, 99 insertions(+), 120 deletions(-)
 delete mode 100644 t/helper/test-prio-queue.c
 delete mode 100755 t/t0009-prio-queue.sh
 create mode 100644 t/unit-tests/t-prio-queue.c

diff --git a/Makefile b/Makefile
index 312d95084c1..d5e48e656b3 100644
--- a/Makefile
+++ b/Makefile
@@ -828,7 +828,6 @@ TEST_BUILTINS_OBJS += test-partial-clone.o
 TEST_BUILTINS_OBJS += test-path-utils.o
 TEST_BUILTINS_OBJS += test-pcre2-config.o
 TEST_BUILTINS_OBJS += test-pkt-line.o
-TEST_BUILTINS_OBJS += test-prio-queue.o
 TEST_BUILTINS_OBJS += test-proc-receive.o
 TEST_BUILTINS_OBJS += test-progress.o
 TEST_BUILTINS_OBJS += test-reach.o
@@ -1340,6 +1339,7 @@ THIRD_PARTY_SOURCES += sha1dc/%
 
 UNIT_TEST_PROGRAMS += t-basic
 UNIT_TEST_PROGRAMS += t-strbuf
+UNIT_TEST_PROGRAMS += t-prio-queue
 UNIT_TEST_PROGS = $(patsubst %,$(UNIT_TEST_BIN)/%$X,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS = $(patsubst %,$(UNIT_TEST_DIR)/%.o,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/test-lib.o
diff --git a/t/helper/test-prio-queue.c b/t/helper/test-prio-queue.c
deleted file mode 100644
index f0bf255f5f0..00000000000
--- a/t/helper/test-prio-queue.c
+++ /dev/null
@@ -1,51 +0,0 @@
-#include "test-tool.h"
-#include "prio-queue.h"
-
-static int intcmp(const void *va, const void *vb, void *data UNUSED)
-{
-	const int *a = va, *b = vb;
-	return *a - *b;
-}
-
-static void show(int *v)
-{
-	if (!v)
-		printf("NULL\n");
-	else
-		printf("%d\n", *v);
-	free(v);
-}
-
-int cmd__prio_queue(int argc UNUSED, const char **argv)
-{
-	struct prio_queue pq = { intcmp };
-
-	while (*++argv) {
-		if (!strcmp(*argv, "get")) {
-			void *peek = prio_queue_peek(&pq);
-			void *get = prio_queue_get(&pq);
-			if (peek != get)
-				BUG("peek and get results do not match");
-			show(get);
-		} else if (!strcmp(*argv, "dump")) {
-			void *peek;
-			void *get;
-			while ((peek = prio_queue_peek(&pq))) {
-				get = prio_queue_get(&pq);
-				if (peek != get)
-					BUG("peek and get results do not match");
-				show(get);
-			}
-		} else if (!strcmp(*argv, "stack")) {
-			pq.compare = NULL;
-		} else {
-			int *v = xmalloc(sizeof(*v));
-			*v = atoi(*argv);
-			prio_queue_put(&pq, v);
-		}
-	}
-
-	clear_prio_queue(&pq);
-
-	return 0;
-}
diff --git a/t/helper/test-tool.c b/t/helper/test-tool.c
index 876cd2dc313..5f591b9718f 100644
--- a/t/helper/test-tool.c
+++ b/t/helper/test-tool.c
@@ -57,7 +57,6 @@ static struct test_cmd cmds[] = {
 	{ "path-utils", cmd__path_utils },
 	{ "pcre2-config", cmd__pcre2_config },
 	{ "pkt-line", cmd__pkt_line },
-	{ "prio-queue", cmd__prio_queue },
 	{ "proc-receive", cmd__proc_receive },
 	{ "progress", cmd__progress },
 	{ "reach", cmd__reach },
diff --git a/t/helper/test-tool.h b/t/helper/test-tool.h
index 70dd4eba119..b921138d8ec 100644
--- a/t/helper/test-tool.h
+++ b/t/helper/test-tool.h
@@ -50,7 +50,6 @@ int cmd__partial_clone(int argc, const char **argv);
 int cmd__path_utils(int argc, const char **argv);
 int cmd__pcre2_config(int argc, const char **argv);
 int cmd__pkt_line(int argc, const char **argv);
-int cmd__prio_queue(int argc, const char **argv);
 int cmd__proc_receive(int argc, const char **argv);
 int cmd__progress(int argc, const char **argv);
 int cmd__reach(int argc, const char **argv);
diff --git a/t/t0009-prio-queue.sh b/t/t0009-prio-queue.sh
deleted file mode 100755
index eea99107a48..00000000000
--- a/t/t0009-prio-queue.sh
+++ /dev/null
@@ -1,66 +0,0 @@
-#!/bin/sh
-
-test_description='basic tests for priority queue implementation'
-
-TEST_PASSES_SANITIZE_LEAK=true
-. ./test-lib.sh
-
-cat >expect <<'EOF'
-1
-2
-3
-4
-5
-5
-6
-7
-8
-9
-10
-EOF
-test_expect_success 'basic ordering' '
-	test-tool prio-queue 2 6 3 10 9 5 7 4 5 8 1 dump >actual &&
-	test_cmp expect actual
-'
-
-cat >expect <<'EOF'
-2
-3
-4
-1
-5
-6
-EOF
-test_expect_success 'mixed put and get' '
-	test-tool prio-queue 6 2 4 get 5 3 get get 1 dump >actual &&
-	test_cmp expect actual
-'
-
-cat >expect <<'EOF'
-1
-2
-NULL
-1
-2
-NULL
-EOF
-test_expect_success 'notice empty queue' '
-	test-tool prio-queue 1 2 get get get 1 2 get get get >actual &&
-	test_cmp expect actual
-'
-
-cat >expect <<'EOF'
-3
-2
-6
-4
-5
-1
-8
-EOF
-test_expect_success 'stack order' '
-	test-tool prio-queue stack 8 1 5 4 6 2 3 dump >actual &&
-	test_cmp expect actual
-'
-
-test_done
diff --git a/t/unit-tests/t-prio-queue.c b/t/unit-tests/t-prio-queue.c
new file mode 100644
index 00000000000..d78b002f9ea
--- /dev/null
+++ b/t/unit-tests/t-prio-queue.c
@@ -0,0 +1,98 @@
+#include "test-lib.h"
+#include "prio-queue.h"
+
+static int intcmp(const void *va, const void *vb, void *data UNUSED)
+{
+	const int *a = va, *b = vb;
+	return *a - *b;
+}
+
+
+#define MISSING  -1
+#define DUMP	 -2
+#define STACK	 -3
+#define GET	 -4
+#define REVERSE  -5
+
+static int show(int *v)
+{
+	return v ? *v : MISSING;
+}
+
+static void test_prio_queue(int *input, int *result, size_t input_size)
+{
+	struct prio_queue pq = { intcmp };
+
+	for (int i = 0, j = 0; i < input_size; i++) {
+		void *peek, *get;
+		switch(input[i]) {
+		case GET:
+			peek = prio_queue_peek(&pq);
+			get = prio_queue_get(&pq);
+			if (!check(peek == get))
+				return;
+			if(!check_int(result[j++], ==, show(get)))
+				test_msg("failed at result[] index %d", j-1);
+			break;
+		case DUMP:
+			while ((peek = prio_queue_peek(&pq))) {
+				get = prio_queue_get(&pq);
+				if (!check(peek == get))
+					return;
+				if(!check_int(result[j++], ==, show(get)))
+					test_msg("failed at result[] index %d", j-1);
+			}
+			break;
+		case STACK:
+			pq.compare = NULL;
+			break;
+		case REVERSE:
+			prio_queue_reverse(&pq);
+			break;
+		default:
+			prio_queue_put(&pq, &input[i]);
+			break;
+		}
+	}
+	clear_prio_queue(&pq);
+}
+
+#define BASIC_INPUT 2, 6, 3, 10, 9, 5, 7, 4, 5, 8, 1, DUMP
+#define BASIC_RESULT 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 10
+
+#define MIXED_PUT_GET_INPUT 6, 2, 4, GET, 5, 3, GET, GET, 1, DUMP
+#define MIXED_PUT_GET_RESULT 2, 3, 4, 1, 5, 6
+
+#define EMPTY_QUEUE_INPUT 1, 2, GET, GET, GET, 1, 2, GET, GET, GET
+#define EMPTY_QUEUE_RESULT 1, 2, MISSING, 1, 2, MISSING
+
+#define STACK_INPUT STACK, 8, 1, 5, 4, 6, 2, 3, DUMP
+#define STACK_RESULT 3, 2, 6, 4, 5, 1, 8
+
+#define REVERSE_STACK_INPUT STACK, 1, 2, 3, 4, 5, 6, REVERSE, DUMP
+#define REVERSE_STACK_RESULT 1, 2, 3, 4, 5, 6
+
+#define TEST_INPUT(INPUT, RESULT, name)			\
+  static void test_##name(void)				\
+{								\
+	int input[] = {INPUT};					\
+	int result[] = {RESULT};				\
+	test_prio_queue(input, result, ARRAY_SIZE(input));	\
+}
+
+TEST_INPUT(BASIC_INPUT, BASIC_RESULT, basic)
+TEST_INPUT(MIXED_PUT_GET_INPUT, MIXED_PUT_GET_RESULT, mixed)
+TEST_INPUT(EMPTY_QUEUE_INPUT, EMPTY_QUEUE_RESULT, empty)
+TEST_INPUT(STACK_INPUT, STACK_RESULT, stack)
+TEST_INPUT(REVERSE_STACK_INPUT, REVERSE_STACK_RESULT, reverse)
+
+int cmd_main(int argc, const char **argv)
+{
+	TEST(test_basic(), "prio-queue works for basic input");
+	TEST(test_mixed(), "prio-queue works for mixed put & get commands");
+	TEST(test_empty(), "prio-queue works when queue is empty");
+	TEST(test_stack(), "prio-queue works when used as a LIFO stack");
+	TEST(test_reverse(), "prio-queue works when LIFO stack is reversed");
+
+	return test_done();
+}

base-commit: 1a87c842ece327d03d08096395969aca5e0a6996
-- 
gitgitgadget

Re: [PATCH v4] tests: move t0009-prio-queue.sh to the new unit testing framework

[Junio C Hamano]

> diff --git a/t/unit-tests/t-prio-queue.c b/t/unit-tests/t-prio-queue.c
> new file mode 100644
> index 00000000000..d78b002f9ea
> --- /dev/null
> +++ b/t/unit-tests/t-prio-queue.c
> @@ -0,0 +1,98 @@
> +#include "test-lib.h"
> +#include "prio-queue.h"
> +
> +static int intcmp(const void *va, const void *vb, void *data UNUSED)
> +{
> +	const int *a = va, *b = vb;
> +	return *a - *b;
> +}
> +
> +
> +#define MISSING  -1
> +#define DUMP	 -2
> +#define STACK	 -3
> +#define GET	 -4
> +#define REVERSE  -5
> +
> +static int show(int *v)
> +{
> +	return v ? *v : MISSING;
> +}
> +
> +static void test_prio_queue(int *input, int *result, size_t input_size)
> +{
> +	struct prio_queue pq = { intcmp };
> +
> +	for (int i = 0, j = 0; i < input_size; i++) {
> +		void *peek, *get;
> +		switch(input[i]) {

Style: in this codebase, a flow control keyword followed by a
parenthesized stuff always get a single SP before the parenthesis.

		switch (input[i]) {

There are similar style violations in this patch with if().

> +		case GET:
> +			peek = prio_queue_peek(&pq);
> +			get = prio_queue_get(&pq);
> +			if (!check(peek == get))
> +				return;
> +			if(!check_int(result[j++], ==, show(get)))
> +				test_msg("failed at result[] index %d", j-1);
> +			break;
> +		case DUMP:
> +			while ((peek = prio_queue_peek(&pq))) {
> +				get = prio_queue_get(&pq);
> +				if (!check(peek == get))
> +					return;
> +				if(!check_int(result[j++], ==, show(get)))
> +					test_msg("failed at result[] index %d", j-1);
> +			}
> +			break;

OK.  So this one checks as we go.  I am not sure how easy to grok a
breakage diagnosis with these giving the same message, without
giving any context of the failure (e.g. when we are fed

	INPUT  = 6 2 4 GET 5 3 GET GET 1 DUMP
	EXPECT = 2 3 4 1 5 6

and for some reason if the first GET did not yield expected 2 but
gave us, say, 6, we only see "left: 2, right: 6" followed by "failed
at result[] index 0", and nothing else.  

If it said something like "We pushed 6, 2, 4 and then did GET" to
give the reader a bit more context, it would make it easier to see
why we were complaining, i.e. expecting to see 2, instead getting 6.
But perhaps that is too much to ask to this code?

I dunno.  Those who wanted to see an easier-to-diagnose output may
have better ideas.

Thanks.

> +		case STACK:
> +			pq.compare = NULL;
> +			break;
> +		case REVERSE:
> +			prio_queue_reverse(&pq);
> +			break;
> +		default:
> +			prio_queue_put(&pq, &input[i]);
> +			break;
> +		}
> +	}
> +	clear_prio_queue(&pq);
> +}
> +
> +#define BASIC_INPUT 2, 6, 3, 10, 9, 5, 7, 4, 5, 8, 1, DUMP
> +#define BASIC_RESULT 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 10
> +
> +#define MIXED_PUT_GET_INPUT 6, 2, 4, GET, 5, 3, GET, GET, 1, DUMP
> +#define MIXED_PUT_GET_RESULT 2, 3, 4, 1, 5, 6
> +
> +#define EMPTY_QUEUE_INPUT 1, 2, GET, GET, GET, 1, 2, GET, GET, GET
> +#define EMPTY_QUEUE_RESULT 1, 2, MISSING, 1, 2, MISSING
> +
> +#define STACK_INPUT STACK, 8, 1, 5, 4, 6, 2, 3, DUMP
> +#define STACK_RESULT 3, 2, 6, 4, 5, 1, 8
> +
> +#define REVERSE_STACK_INPUT STACK, 1, 2, 3, 4, 5, 6, REVERSE, DUMP
> +#define REVERSE_STACK_RESULT 1, 2, 3, 4, 5, 6
> +
> +#define TEST_INPUT(INPUT, RESULT, name)			\
> +  static void test_##name(void)				\
> +{								\
> +	int input[] = {INPUT};					\
> +	int result[] = {RESULT};				\
> +	test_prio_queue(input, result, ARRAY_SIZE(input));	\
> +}
> +
> +TEST_INPUT(BASIC_INPUT, BASIC_RESULT, basic)
> +TEST_INPUT(MIXED_PUT_GET_INPUT, MIXED_PUT_GET_RESULT, mixed)
> +TEST_INPUT(EMPTY_QUEUE_INPUT, EMPTY_QUEUE_RESULT, empty)
> +TEST_INPUT(STACK_INPUT, STACK_RESULT, stack)
> +TEST_INPUT(REVERSE_STACK_INPUT, REVERSE_STACK_RESULT, reverse)
> +
> +int cmd_main(int argc, const char **argv)
> +{
> +	TEST(test_basic(), "prio-queue works for basic input");
> +	TEST(test_mixed(), "prio-queue works for mixed put & get commands");
> +	TEST(test_empty(), "prio-queue works when queue is empty");
> +	TEST(test_stack(), "prio-queue works when used as a LIFO stack");
> +	TEST(test_reverse(), "prio-queue works when LIFO stack is reversed");
> +
> +	return test_done();
> +}
>
> base-commit: 1a87c842ece327d03d08096395969aca5e0a6996

Re: [PATCH v4] tests: move t0009-prio-queue.sh to the new unit testing framework

[Jeff King]

On Mon, Jan 22, 2024 at 11:09:39AM -0800, Junio C Hamano wrote:

> > +		case DUMP:
> > +			while ((peek = prio_queue_peek(&pq))) {
> > +				get = prio_queue_get(&pq);
> > +				if (!check(peek == get))
> > +					return;
> > +				if(!check_int(result[j++], ==, show(get)))
> > +					test_msg("failed at result[] index %d", j-1);
> > +			}
> > +			break;
> 
> OK.  So this one checks as we go.  I am not sure how easy to grok a
> breakage diagnosis with these giving the same message, without
> giving any context of the failure (e.g. when we are fed
> 
> 	INPUT  = 6 2 4 GET 5 3 GET GET 1 DUMP
> 	EXPECT = 2 3 4 1 5 6
> 
> and for some reason if the first GET did not yield expected 2 but
> gave us, say, 6, we only see "left: 2, right: 6" followed by "failed
> at result[] index 0", and nothing else.  
> 
> If it said something like "We pushed 6, 2, 4 and then did GET" to
> give the reader a bit more context, it would make it easier to see
> why we were complaining, i.e. expecting to see 2, instead getting 6.
> But perhaps that is too much to ask to this code?
> 
> I dunno.  Those who wanted to see an easier-to-diagnose output may
> have better ideas.

I don't have any bright ideas, but here are some dumb ones.

The big issue is that storing and manipulating data in C is tricky and
requires code to do correctly. And the whole idea of these tests is to
avoid having a ton of special code. That's why I actually think that the
existing strategy used in t0009 and elsewhere is pretty good. It pawns
off output handling and such to existing programs.

But if we really want to keep it all in C, some options are:

  1. We could log what is happening verbosely to stderr (or maybe stdout
     with a TAP "#" prefix?). That lets it go nowhere most of the time,
     but you can see it if you are investigating a failure (like the way
     our current "-v" works).

     Obviously by that same argument you can fire up a debugger to look
     at the problem more closely when you have a failure. But failures
     aren't always easy to reproduce. Sometimes they're racy, sometimes
     CI fails but local runs don't (I've found CI's use of "-v -x"
     especially helpful there), etc.

  2. We can rely on a dynamic-growth array of ints to store the result,
     and then a check_int_array() to compare/output them. That's custom
     code for the test harness, but in theory it's reusable across many
     tests.

  3. In the same direction, we could simply output to a strbuf or
     similar, and then compare the strbufs. We could even show a diff
     when they are not the same. ;) That is reimplementing what scripts
     like t0009 are doing already, but maybe people think there is other
     value in shoving it all into a single C program (as I've said, I
     remain a bit skeptical).

-Peff

[PATCH v5] tests: move t0009-prio-queue.sh to the new unit testing framework

[Chandra Pratap via GitGitGadget]

From: Chandra Pratap <chandrapratap3519@gmail.com>

t/t0009-prio-queue.sh along with t/helper/test-prio-queue.c unit
tests Git's implementation of a priority queue. Migrate the
test over to the new unit testing framework to simplify debugging
and reduce test run-time. Refactor the required logic and add
a new test case in addition to porting over the original ones in
shell.

Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
    tests: move t0009-prio-queue.sh to the new unit testing framework
    
    Thanks for the feedbacks! I have updated the patch so that the resulting
    tests show something like:
    
    > check "result[j++] == show(get)" failed at
    > unit-tests/t-prio-queue.c:60
    
    > left: 20 right: 2
    
    > input: push 1, push 2, get, get, get, push 1, push 2, get, get, get,
    
    > failed at input index 8
    
    in the case of a failing test.

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1642%2FChand-ra%2Fprio-queue-v5
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1642/Chand-ra/prio-queue-v5
Pull-Request: https://github.com/gitgitgadget/git/pull/1642

Range-diff vs v4:

 1:  e9a0dba6f47 ! 1:  88e70127ad3 tests: move t0009-prio-queue.sh to the new unit testing framework
     @@ t/unit-tests/t-prio-queue.c (new)
      +	return v ? *v : MISSING;
      +}
      +
     ++static void print_input(int *input, size_t input_size)
     ++{
     ++	char buf[128];
     ++	int len = 0;
     ++	for(size_t i = 0; i < input_size; i++) {
     ++		switch (input[i]) {
     ++		case GET:
     ++			len += xsnprintf(buf+len, sizeof(buf), "get, ");
     ++			break;
     ++		case DUMP:
     ++			len += xsnprintf(buf+len, sizeof(buf), "dump");
     ++			break;
     ++		case STACK:
     ++			len += xsnprintf(buf+len, sizeof(buf), "stack, ");
     ++			break;
     ++		case REVERSE:
     ++			len += xsnprintf(buf+len, sizeof(buf), "reverse, ");
     ++			break;
     ++		default:
     ++			len += xsnprintf(buf+len, sizeof(buf), "push %d, ", input[i]);
     ++			break;
     ++		}
     ++	}
     ++	test_msg("input: %s", buf);
     ++}
     ++
      +static void test_prio_queue(int *input, int *result, size_t input_size)
      +{
      +	struct prio_queue pq = { intcmp };
      +
      +	for (int i = 0, j = 0; i < input_size; i++) {
      +		void *peek, *get;
     -+		switch(input[i]) {
     ++		switch (input[i]) {
      +		case GET:
      +			peek = prio_queue_peek(&pq);
      +			get = prio_queue_get(&pq);
      +			if (!check(peek == get))
      +				return;
     -+			if(!check_int(result[j++], ==, show(get)))
     -+				test_msg("failed at result[] index %d", j-1);
     ++			if (!check_int(result[j++], ==, show(get))) {
     ++				print_input(input, input_size);
     ++				test_msg("failed at input index %d", i);
     ++			}
      +			break;
      +		case DUMP:
      +			while ((peek = prio_queue_peek(&pq))) {
      +				get = prio_queue_get(&pq);
      +				if (!check(peek == get))
      +					return;
     -+				if(!check_int(result[j++], ==, show(get)))
     -+					test_msg("failed at result[] index %d", j-1);
     ++				if (!check_int(result[j++], ==, show(get))) {
     ++					print_input(input, input_size);
     ++					test_msg("failed at input index %d", i);
     ++				}
      +			}
      +			break;
      +		case STACK:
     @@ t/unit-tests/t-prio-queue.c (new)
      +	clear_prio_queue(&pq);
      +}
      +
     ++
      +#define BASIC_INPUT 2, 6, 3, 10, 9, 5, 7, 4, 5, 8, 1, DUMP
      +#define BASIC_RESULT 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 10
      +


 Makefile                    |   2 +-
 t/helper/test-prio-queue.c  |  51 --------------
 t/helper/test-tool.c        |   1 -
 t/helper/test-tool.h        |   1 -
 t/t0009-prio-queue.sh       |  66 ------------------
 t/unit-tests/t-prio-queue.c | 129 ++++++++++++++++++++++++++++++++++++
 6 files changed, 130 insertions(+), 120 deletions(-)
 delete mode 100644 t/helper/test-prio-queue.c
 delete mode 100755 t/t0009-prio-queue.sh
 create mode 100644 t/unit-tests/t-prio-queue.c

diff --git a/Makefile b/Makefile
index 312d95084c1..d5e48e656b3 100644
--- a/Makefile
+++ b/Makefile
@@ -828,7 +828,6 @@ TEST_BUILTINS_OBJS += test-partial-clone.o
 TEST_BUILTINS_OBJS += test-path-utils.o
 TEST_BUILTINS_OBJS += test-pcre2-config.o
 TEST_BUILTINS_OBJS += test-pkt-line.o
-TEST_BUILTINS_OBJS += test-prio-queue.o
 TEST_BUILTINS_OBJS += test-proc-receive.o
 TEST_BUILTINS_OBJS += test-progress.o
 TEST_BUILTINS_OBJS += test-reach.o
@@ -1340,6 +1339,7 @@ THIRD_PARTY_SOURCES += sha1dc/%
 
 UNIT_TEST_PROGRAMS += t-basic
 UNIT_TEST_PROGRAMS += t-strbuf
+UNIT_TEST_PROGRAMS += t-prio-queue
 UNIT_TEST_PROGS = $(patsubst %,$(UNIT_TEST_BIN)/%$X,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS = $(patsubst %,$(UNIT_TEST_DIR)/%.o,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/test-lib.o
diff --git a/t/helper/test-prio-queue.c b/t/helper/test-prio-queue.c
deleted file mode 100644
index f0bf255f5f0..00000000000
--- a/t/helper/test-prio-queue.c
+++ /dev/null
@@ -1,51 +0,0 @@
-#include "test-tool.h"
-#include "prio-queue.h"
-
-static int intcmp(const void *va, const void *vb, void *data UNUSED)
-{
-	const int *a = va, *b = vb;
-	return *a - *b;
-}
-
-static void show(int *v)
-{
-	if (!v)
-		printf("NULL\n");
-	else
-		printf("%d\n", *v);
-	free(v);
-}
-
-int cmd__prio_queue(int argc UNUSED, const char **argv)
-{
-	struct prio_queue pq = { intcmp };
-
-	while (*++argv) {
-		if (!strcmp(*argv, "get")) {
-			void *peek = prio_queue_peek(&pq);
-			void *get = prio_queue_get(&pq);
-			if (peek != get)
-				BUG("peek and get results do not match");
-			show(get);
-		} else if (!strcmp(*argv, "dump")) {
-			void *peek;
-			void *get;
-			while ((peek = prio_queue_peek(&pq))) {
-				get = prio_queue_get(&pq);
-				if (peek != get)
-					BUG("peek and get results do not match");
-				show(get);
-			}
-		} else if (!strcmp(*argv, "stack")) {
-			pq.compare = NULL;
-		} else {
-			int *v = xmalloc(sizeof(*v));
-			*v = atoi(*argv);
-			prio_queue_put(&pq, v);
-		}
-	}
-
-	clear_prio_queue(&pq);
-
-	return 0;
-}
diff --git a/t/helper/test-tool.c b/t/helper/test-tool.c
index 876cd2dc313..5f591b9718f 100644
--- a/t/helper/test-tool.c
+++ b/t/helper/test-tool.c
@@ -57,7 +57,6 @@ static struct test_cmd cmds[] = {
 	{ "path-utils", cmd__path_utils },
 	{ "pcre2-config", cmd__pcre2_config },
 	{ "pkt-line", cmd__pkt_line },
-	{ "prio-queue", cmd__prio_queue },
 	{ "proc-receive", cmd__proc_receive },
 	{ "progress", cmd__progress },
 	{ "reach", cmd__reach },
diff --git a/t/helper/test-tool.h b/t/helper/test-tool.h
index 70dd4eba119..b921138d8ec 100644
--- a/t/helper/test-tool.h
+++ b/t/helper/test-tool.h
@@ -50,7 +50,6 @@ int cmd__partial_clone(int argc, const char **argv);
 int cmd__path_utils(int argc, const char **argv);
 int cmd__pcre2_config(int argc, const char **argv);
 int cmd__pkt_line(int argc, const char **argv);
-int cmd__prio_queue(int argc, const char **argv);
 int cmd__proc_receive(int argc, const char **argv);
 int cmd__progress(int argc, const char **argv);
 int cmd__reach(int argc, const char **argv);
diff --git a/t/t0009-prio-queue.sh b/t/t0009-prio-queue.sh
deleted file mode 100755
index eea99107a48..00000000000
--- a/t/t0009-prio-queue.sh
+++ /dev/null
@@ -1,66 +0,0 @@
-#!/bin/sh
-
-test_description='basic tests for priority queue implementation'
-
-TEST_PASSES_SANITIZE_LEAK=true
-. ./test-lib.sh
-
-cat >expect <<'EOF'
-1
-2
-3
-4
-5
-5
-6
-7
-8
-9
-10
-EOF
-test_expect_success 'basic ordering' '
-	test-tool prio-queue 2 6 3 10 9 5 7 4 5 8 1 dump >actual &&
-	test_cmp expect actual
-'
-
-cat >expect <<'EOF'
-2
-3
-4
-1
-5
-6
-EOF
-test_expect_success 'mixed put and get' '
-	test-tool prio-queue 6 2 4 get 5 3 get get 1 dump >actual &&
-	test_cmp expect actual
-'
-
-cat >expect <<'EOF'
-1
-2
-NULL
-1
-2
-NULL
-EOF
-test_expect_success 'notice empty queue' '
-	test-tool prio-queue 1 2 get get get 1 2 get get get >actual &&
-	test_cmp expect actual
-'
-
-cat >expect <<'EOF'
-3
-2
-6
-4
-5
-1
-8
-EOF
-test_expect_success 'stack order' '
-	test-tool prio-queue stack 8 1 5 4 6 2 3 dump >actual &&
-	test_cmp expect actual
-'
-
-test_done
diff --git a/t/unit-tests/t-prio-queue.c b/t/unit-tests/t-prio-queue.c
new file mode 100644
index 00000000000..8456b23255c
--- /dev/null
+++ b/t/unit-tests/t-prio-queue.c
@@ -0,0 +1,129 @@
+#include "test-lib.h"
+#include "prio-queue.h"
+
+static int intcmp(const void *va, const void *vb, void *data UNUSED)
+{
+	const int *a = va, *b = vb;
+	return *a - *b;
+}
+
+
+#define MISSING  -1
+#define DUMP	 -2
+#define STACK	 -3
+#define GET	 -4
+#define REVERSE  -5
+
+static int show(int *v)
+{
+	return v ? *v : MISSING;
+}
+
+static void print_input(int *input, size_t input_size)
+{
+	char buf[128];
+	int len = 0;
+	for(size_t i = 0; i < input_size; i++) {
+		switch (input[i]) {
+		case GET:
+			len += xsnprintf(buf+len, sizeof(buf), "get, ");
+			break;
+		case DUMP:
+			len += xsnprintf(buf+len, sizeof(buf), "dump");
+			break;
+		case STACK:
+			len += xsnprintf(buf+len, sizeof(buf), "stack, ");
+			break;
+		case REVERSE:
+			len += xsnprintf(buf+len, sizeof(buf), "reverse, ");
+			break;
+		default:
+			len += xsnprintf(buf+len, sizeof(buf), "push %d, ", input[i]);
+			break;
+		}
+	}
+	test_msg("input: %s", buf);
+}
+
+static void test_prio_queue(int *input, int *result, size_t input_size)
+{
+	struct prio_queue pq = { intcmp };
+
+	for (int i = 0, j = 0; i < input_size; i++) {
+		void *peek, *get;
+		switch (input[i]) {
+		case GET:
+			peek = prio_queue_peek(&pq);
+			get = prio_queue_get(&pq);
+			if (!check(peek == get))
+				return;
+			if (!check_int(result[j++], ==, show(get))) {
+				print_input(input, input_size);
+				test_msg("failed at input index %d", i);
+			}
+			break;
+		case DUMP:
+			while ((peek = prio_queue_peek(&pq))) {
+				get = prio_queue_get(&pq);
+				if (!check(peek == get))
+					return;
+				if (!check_int(result[j++], ==, show(get))) {
+					print_input(input, input_size);
+					test_msg("failed at input index %d", i);
+				}
+			}
+			break;
+		case STACK:
+			pq.compare = NULL;
+			break;
+		case REVERSE:
+			prio_queue_reverse(&pq);
+			break;
+		default:
+			prio_queue_put(&pq, &input[i]);
+			break;
+		}
+	}
+	clear_prio_queue(&pq);
+}
+
+
+#define BASIC_INPUT 2, 6, 3, 10, 9, 5, 7, 4, 5, 8, 1, DUMP
+#define BASIC_RESULT 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 10
+
+#define MIXED_PUT_GET_INPUT 6, 2, 4, GET, 5, 3, GET, GET, 1, DUMP
+#define MIXED_PUT_GET_RESULT 2, 3, 4, 1, 5, 6
+
+#define EMPTY_QUEUE_INPUT 1, 2, GET, GET, GET, 1, 2, GET, GET, GET
+#define EMPTY_QUEUE_RESULT 1, 2, MISSING, 1, 2, MISSING
+
+#define STACK_INPUT STACK, 8, 1, 5, 4, 6, 2, 3, DUMP
+#define STACK_RESULT 3, 2, 6, 4, 5, 1, 8
+
+#define REVERSE_STACK_INPUT STACK, 1, 2, 3, 4, 5, 6, REVERSE, DUMP
+#define REVERSE_STACK_RESULT 1, 2, 3, 4, 5, 6
+
+#define TEST_INPUT(INPUT, RESULT, name)			\
+  static void test_##name(void)				\
+{								\
+	int input[] = {INPUT};					\
+	int result[] = {RESULT};				\
+	test_prio_queue(input, result, ARRAY_SIZE(input));	\
+}
+
+TEST_INPUT(BASIC_INPUT, BASIC_RESULT, basic)
+TEST_INPUT(MIXED_PUT_GET_INPUT, MIXED_PUT_GET_RESULT, mixed)
+TEST_INPUT(EMPTY_QUEUE_INPUT, EMPTY_QUEUE_RESULT, empty)
+TEST_INPUT(STACK_INPUT, STACK_RESULT, stack)
+TEST_INPUT(REVERSE_STACK_INPUT, REVERSE_STACK_RESULT, reverse)
+
+int cmd_main(int argc, const char **argv)
+{
+	TEST(test_basic(), "prio-queue works for basic input");
+	TEST(test_mixed(), "prio-queue works for mixed put & get commands");
+	TEST(test_empty(), "prio-queue works when queue is empty");
+	TEST(test_stack(), "prio-queue works when used as a LIFO stack");
+	TEST(test_reverse(), "prio-queue works when LIFO stack is reversed");
+
+	return test_done();
+}

base-commit: 1a87c842ece327d03d08096395969aca5e0a6996
-- 
gitgitgadget