Commit af4bc6615d9fe0ebcc4abb939273913bcf9aee60
2014-02-03T21:04:40
Add some priority queue tests I forgot that I wrote some tests for the new priority queue code.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103
diff --git a/tests/core/pqueue.c b/tests/core/pqueue.c
new file mode 100644
index 0000000..d91dbb0
--- /dev/null
+++ b/tests/core/pqueue.c
@@ -0,0 +1,97 @@
+#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_core_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_core_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_core_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);
+
+}