Merge https://salsa.debian.org/debian/libgit2 into proxmox/bullseye

[libgit2.git] / tests / util / pqueue.c

diff --git a/tests/util/pqueue.c b/tests/util/pqueue.c
new file mode 100644 (file)
index 0000000..38931ec
--- /dev/null
+++ b/tests/util/pqueue.c
@@ -0,0 +1,150 @@
+#include "clar_libgit2.h"
+#include "pqueue.h"
+
+static int cmp_ints(const void *v1, const void *v2)
+{
+       int i1 = *(int *)v1, i2 = *(int *)v2;
+       return (i1 < i2) ? -1 : (i1 > i2) ? 1 : 0;
+}
+
+void test_pqueue__items_are_put_in_order(void)
+{
+       git_pqueue pq;
+       int i, vals[20];
+
+       cl_git_pass(git_pqueue_init(&pq, 0, 20, cmp_ints));
+
+       for (i = 0; i < 20; ++i) {
+               if (i < 10)
+                       vals[i] = 10 - i; /* 10 down to 1 */
+               else
+                       vals[i] = i + 1;  /* 11 up to 20 */
+
+               cl_git_pass(git_pqueue_insert(&pq, &vals[i]));
+       }
+
+       cl_assert_equal_i(20, git_pqueue_size(&pq));
+
+       for (i = 1; i <= 20; ++i) {
+               void *p = git_pqueue_pop(&pq);
+               cl_assert(p);
+               cl_assert_equal_i(i, *(int *)p);
+       }
+
+       cl_assert_equal_i(0, git_pqueue_size(&pq));
+
+       git_pqueue_free(&pq);
+}
+
+void test_pqueue__interleave_inserts_and_pops(void)
+{
+       git_pqueue pq;
+       int chunk, v, i, vals[200];
+
+       cl_git_pass(git_pqueue_init(&pq, 0, 20, cmp_ints));
+
+       for (v = 0, chunk = 20; chunk <= 200; chunk += 20) {
+               /* push the next 20 */
+               for (; v < chunk; ++v) {
+                       vals[v] = (v & 1) ? 200 - v : v;
+                       cl_git_pass(git_pqueue_insert(&pq, &vals[v]));
+               }
+
+               /* pop the lowest 10 */
+               for (i = 0; i < 10; ++i)
+                       (void)git_pqueue_pop(&pq);
+       }
+
+       cl_assert_equal_i(100, git_pqueue_size(&pq));
+
+       /* at this point, we've popped 0-99 */
+
+       for (v = 100; v < 200; ++v) {
+               void *p = git_pqueue_pop(&pq);
+               cl_assert(p);
+               cl_assert_equal_i(v, *(int *)p);
+       }
+
+       cl_assert_equal_i(0, git_pqueue_size(&pq));
+
+       git_pqueue_free(&pq);
+}
+
+void test_pqueue__max_heap_size(void)
+{
+       git_pqueue pq;
+       int i, vals[100];
+
+       cl_git_pass(git_pqueue_init(&pq, GIT_PQUEUE_FIXED_SIZE, 50, cmp_ints));
+
+       for (i = 0; i < 100; ++i) {
+               vals[i] = (i & 1) ? 100 - i : i;
+               cl_git_pass(git_pqueue_insert(&pq, &vals[i]));
+       }
+
+       cl_assert_equal_i(50, git_pqueue_size(&pq));
+
+       for (i = 50; i < 100; ++i) {
+               void *p = git_pqueue_pop(&pq);
+               cl_assert(p);
+               cl_assert_equal_i(i, *(int *)p);
+       }
+
+       cl_assert_equal_i(0, git_pqueue_size(&pq));
+
+       git_pqueue_free(&pq);
+}
+
+void test_pqueue__max_heap_size_without_comparison(void)
+{
+       git_pqueue pq;
+       int i, vals[100] = { 0 };
+
+       cl_git_pass(git_pqueue_init(&pq, GIT_PQUEUE_FIXED_SIZE, 50, NULL));
+
+       for (i = 0; i < 100; ++i)
+               cl_git_pass(git_pqueue_insert(&pq, &vals[i]));
+
+       cl_assert_equal_i(50, git_pqueue_size(&pq));
+
+       /* As we have no comparison function, we cannot make any
+        * actual assumptions about which entries are part of the
+        * pqueue */
+       for (i = 0; i < 50; ++i)
+               cl_assert(git_pqueue_pop(&pq));
+
+       cl_assert_equal_i(0, git_pqueue_size(&pq));
+
+       git_pqueue_free(&pq);
+}
+
+static int cmp_ints_like_commit_time(const void *a, const void *b)
+{
+       return *((const int *)a) < *((const int *)b);
+}
+
+void test_pqueue__interleaved_pushes_and_pops(void)
+{
+       git_pqueue pq;
+       int i, j, *val;
+       static int commands[] =
+               { 6, 9, 8, 0, 5, 0, 7, 0, 4, 3, 0, 0, 0, 4, 0, 2, 0, 1, 0, 0, -1 };
+       static int expected[] =
+               { 9, 8, 7, 6, 5, 4, 4, 3, 2, 1, -1 };
+
+       cl_git_pass(git_pqueue_init(&pq, 0, 10, cmp_ints_like_commit_time));
+
+       for (i = 0, j = 0; commands[i] >= 0; ++i) {
+               if (!commands[i]) {
+                       cl_assert((val = git_pqueue_pop(&pq)) != NULL);
+                       cl_assert_equal_i(expected[j], *val);
+                       ++j;
+               } else {
+                       cl_git_pass(git_pqueue_insert(&pq, &commands[i]));
+               }
+       }
+
+       cl_assert_equal_i(0, git_pqueue_size(&pq));
+       git_pqueue_free(&pq);
+}
+