pqueue.c 2.67 KB
Newer Older
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
#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);

}
98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128

static int cmp_ints_like_commit_time(const void *a, const void *b)
{
	return *((const int *)a) < *((const int *)b);
}

void test_core_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);
}