#include "clar_libgit2.h"

#include "vector.h"

/* initial size of 1 would cause writing past array bounds */

void test_core_vector__0(void)

{

	git_vector x;

	int i;

	git_vector_init(&x, 1, NULL);

	for (i = 0; i < 10; ++i) {

		git_vector_insert(&x, (void*) 0xabc);

	}

	git_vector_free(&x);

}

/* don't read past array bounds on remove() */

void test_core_vector__1(void)

{

	git_vector x;

	// make initial capacity exact for our insertions.

	git_vector_init(&x, 3, NULL);

	git_vector_insert(&x, (void*) 0xabc);

	git_vector_insert(&x, (void*) 0xdef);

	git_vector_insert(&x, (void*) 0x123);

	git_vector_remove(&x, 0); // used to read past array bounds.

	git_vector_free(&x);

}

static int test_cmp(const void *a, const void *b)

{

	return *(const int *)a - *(const int *)b;

}

/* remove duplicates */

void test_core_vector__2(void)

{

	git_vector x;

	int *ptrs[2];

	ptrs[0] = git__malloc(sizeof(int));

	ptrs[1] = git__malloc(sizeof(int));

	*ptrs[0] = 2;

	*ptrs[1] = 1;

	cl_git_pass(git_vector_init(&x, 5, test_cmp));

	cl_git_pass(git_vector_insert(&x, ptrs[0]));

	cl_git_pass(git_vector_insert(&x, ptrs[1]));

	cl_git_pass(git_vector_insert(&x, ptrs[1]));

	cl_git_pass(git_vector_insert(&x, ptrs[0]));

	cl_git_pass(git_vector_insert(&x, ptrs[1]));

	cl_assert(x.length == 5);

	git_vector_uniq(&x, NULL);

	cl_assert(x.length == 2);

	git_vector_free(&x);

	git__free(ptrs[0]);

	git__free(ptrs[1]);

}

static int compare_them(const void *a, const void *b)

{

	return (int)((long)a - (long)b);

}

/* insert_sorted */

void test_core_vector__3(void)

{

	git_vector x;

	long i;

	git_vector_init(&x, 1, &compare_them);

	for (i = 0; i < 10; i += 2) {

		git_vector_insert_sorted(&x, (void*)(i + 1), NULL);

	}

	for (i = 9; i > 0; i -= 2) {

		git_vector_insert_sorted(&x, (void*)(i + 1), NULL);

	}

	cl_assert(x.length == 10);

	for (i = 0; i < 10; ++i) {

		cl_assert(git_vector_get(&x, i) == (void*)(i + 1));

	}

	git_vector_free(&x);

}

/* insert_sorted with duplicates */

void test_core_vector__4(void)

{

	git_vector x;

	long i;

	git_vector_init(&x, 1, &compare_them);

	for (i = 0; i < 10; i += 2) {

		git_vector_insert_sorted(&x, (void*)(i + 1), NULL);

	}

	for (i = 9; i > 0; i -= 2) {

		git_vector_insert_sorted(&x, (void*)(i + 1), NULL);

	}

	for (i = 0; i < 10; i += 2) {

		git_vector_insert_sorted(&x, (void*)(i + 1), NULL);

	}

	for (i = 9; i > 0; i -= 2) {

		git_vector_insert_sorted(&x, (void*)(i + 1), NULL);

	}

	cl_assert(x.length == 20);

	for (i = 0; i < 20; ++i) {

		cl_assert(git_vector_get(&x, i) == (void*)(i / 2 + 1));

	}

	git_vector_free(&x);

}

typedef struct {

	int content;

	int count;

} my_struct;

static int _struct_count = 0;

static int compare_structs(const void *a, const void *b)

{

	return ((const my_struct *)a)->content -

		((const my_struct *)b)->content;

}

static int merge_structs(void **old_raw, void *new)

{

	my_struct *old = *(my_struct **)old_raw;

	cl_assert(((my_struct *)old)->content == ((my_struct *)new)->content);

	((my_struct *)old)->count += 1;

	git__free(new);

	_struct_count--;

	return GIT_EEXISTS;

}

static my_struct *alloc_struct(int value)

{

	my_struct *st = git__malloc(sizeof(my_struct));

	st->content = value;

	st->count = 0;

	_struct_count++;

	return st;

}

/* insert_sorted with duplicates and special handling */

void test_core_vector__5(void)

{

	git_vector x;

	int i;

	git_vector_init(&x, 1, &compare_structs);

	for (i = 0; i < 10; i += 2)

		git_vector_insert_sorted(&x, alloc_struct(i), &merge_structs);

	for (i = 9; i > 0; i -= 2)

		git_vector_insert_sorted(&x, alloc_struct(i), &merge_structs);

	cl_assert(x.length == 10);

	cl_assert(_struct_count == 10);

	for (i = 0; i < 10; i += 2)

		git_vector_insert_sorted(&x, alloc_struct(i), &merge_structs);

	for (i = 9; i > 0; i -= 2)

		git_vector_insert_sorted(&x, alloc_struct(i), &merge_structs);

	cl_assert(x.length == 10);

	cl_assert(_struct_count == 10);

	for (i = 0; i < 10; ++i) {

		cl_assert(((my_struct *)git_vector_get(&x, i))->content == i);

		git__free(git_vector_get(&x, i));

		_struct_count--;

	}

	git_vector_free(&x);

}

static int remove_ones(const git_vector *v, size_t idx, void *p)

{

	GIT_UNUSED(p);

	return (git_vector_get(v, idx) == (void *)0x001);

}

/* Test removal based on callback */

void test_core_vector__remove_matching(void)

{

	git_vector x;

	size_t i;

	void *compare;

	git_vector_init(&x, 1, NULL);

	git_vector_insert(&x, (void*) 0x001);

	cl_assert(x.length == 1);

	git_vector_remove_matching(&x, remove_ones, NULL);

	cl_assert(x.length == 0);

	git_vector_insert(&x, (void*) 0x001);

	git_vector_insert(&x, (void*) 0x001);

	git_vector_insert(&x, (void*) 0x001);

	cl_assert(x.length == 3);

	git_vector_remove_matching(&x, remove_ones, NULL);

	cl_assert(x.length == 0);

	git_vector_insert(&x, (void*) 0x002);

	git_vector_insert(&x, (void*) 0x001);

	git_vector_insert(&x, (void*) 0x002);

	git_vector_insert(&x, (void*) 0x001);

	cl_assert(x.length == 4);

	git_vector_remove_matching(&x, remove_ones, NULL);

	cl_assert(x.length == 2);

	git_vector_foreach(&x, i, compare) {

		cl_assert(compare != (void *)0x001);

	}

	git_vector_clear(&x);

	git_vector_insert(&x, (void*) 0x001);

	git_vector_insert(&x, (void*) 0x002);

	git_vector_insert(&x, (void*) 0x002);

	git_vector_insert(&x, (void*) 0x001);

	cl_assert(x.length == 4);

	git_vector_remove_matching(&x, remove_ones, NULL);

	cl_assert(x.length == 2);

	git_vector_foreach(&x, i, compare) {

		cl_assert(compare != (void *)0x001);

	}

	git_vector_clear(&x);

	git_vector_insert(&x, (void*) 0x002);

	git_vector_insert(&x, (void*) 0x001);

	git_vector_insert(&x, (void*) 0x002);

	git_vector_insert(&x, (void*) 0x001);

	cl_assert(x.length == 4);

	git_vector_remove_matching(&x, remove_ones, NULL);

	cl_assert(x.length == 2);

	git_vector_foreach(&x, i, compare) {

		cl_assert(compare != (void *)0x001);

	}

	git_vector_clear(&x);

	git_vector_insert(&x, (void*) 0x002);

	git_vector_insert(&x, (void*) 0x003);

	git_vector_insert(&x, (void*) 0x002);

	git_vector_insert(&x, (void*) 0x003);

	cl_assert(x.length == 4);

	git_vector_remove_matching(&x, remove_ones, NULL);

	cl_assert(x.length == 4);

	git_vector_free(&x);

}

static void assert_vector(git_vector *x, void *expected[], size_t len)

{

	size_t i;

	cl_assert_equal_i(len, x->length);

	for (i = 0; i < len; i++)

		cl_assert(expected[i] == x->contents[i]);

}

void test_core_vector__grow_and_shrink(void)

{

	git_vector x = GIT_VECTOR_INIT;

	void *expected1[] = {

		(void *)0x02, (void *)0x03, (void *)0x04, (void *)0x05,

		(void *)0x06, (void *)0x07, (void *)0x08, (void *)0x09,

		(void *)0x0a

	};

	void *expected2[] = {

		(void *)0x02, (void *)0x04, (void *)0x05, (void *)0x06,

		(void *)0x07, (void *)0x08, (void *)0x09, (void *)0x0a

	};

	void *expected3[] = {

		(void *)0x02, (void *)0x04, (void *)0x05, (void *)0x06,

		(void *)0x0a

	};

	void *expected4[] = {

		(void *)0x02, (void *)0x04, (void *)0x05

	};

	void *expected5[] = {

		(void *)0x00, (void *)0x00, (void *)0x02, (void *)0x04,

		(void *)0x05

	};

	void *expected6[] = {

		(void *)0x00, (void *)0x00, (void *)0x02, (void *)0x04,

		(void *)0x05, (void *)0x00

	};

	void *expected7[] = {

		(void *)0x00, (void *)0x00, (void *)0x02, (void *)0x04,

		(void *)0x00, (void *)0x00, (void *)0x00, (void *)0x05,

		(void *)0x00

	};

	void *expected8[] = {

		(void *)0x04, (void *)0x00, (void *)0x00, (void *)0x00,

		(void *)0x05, (void *)0x00

	};

	void *expected9[] = {

		(void *)0x04, (void *)0x00, (void *)0x05, (void *)0x00

	};

	void *expectedA[] = { (void *)0x04, (void *)0x00 };

	void *expectedB[] = { (void *)0x04 };

	git_vector_insert(&x, (void *)0x01);

	git_vector_insert(&x, (void *)0x02);

	git_vector_insert(&x, (void *)0x03);

	git_vector_insert(&x, (void *)0x04);

	git_vector_insert(&x, (void *)0x05);

	git_vector_insert(&x, (void *)0x06);

	git_vector_insert(&x, (void *)0x07);

	git_vector_insert(&x, (void *)0x08);

	git_vector_insert(&x, (void *)0x09);

	git_vector_insert(&x, (void *)0x0a);

	git_vector_remove_range(&x, 0, 1);

	assert_vector(&x, expected1, ARRAY_SIZE(expected1));

	git_vector_remove_range(&x, 1, 1);

	assert_vector(&x, expected2, ARRAY_SIZE(expected2));

	git_vector_remove_range(&x, 4, 3);

	assert_vector(&x, expected3, ARRAY_SIZE(expected3));

	git_vector_remove_range(&x, 3, 2);

	assert_vector(&x, expected4, ARRAY_SIZE(expected4));

	git_vector_insert_null(&x, 0, 2);

	assert_vector(&x, expected5, ARRAY_SIZE(expected5));

	git_vector_insert_null(&x, 5, 1);

	assert_vector(&x, expected6, ARRAY_SIZE(expected6));

	git_vector_insert_null(&x, 4, 3);

	assert_vector(&x, expected7, ARRAY_SIZE(expected7));

	git_vector_remove_range(&x, 0, 3);

	assert_vector(&x, expected8, ARRAY_SIZE(expected8));

	git_vector_remove_range(&x, 1, 2);

	assert_vector(&x, expected9, ARRAY_SIZE(expected9));

	git_vector_remove_range(&x, 2, 2);

	assert_vector(&x, expectedA, ARRAY_SIZE(expectedA));

	git_vector_remove_range(&x, 1, 1);

	assert_vector(&x, expectedB, ARRAY_SIZE(expectedB));

	git_vector_remove_range(&x, 0, 1);

	assert_vector(&x, NULL, 0);

	git_vector_free(&x);

}

void test_core_vector__reverse(void)

{

	git_vector v = GIT_VECTOR_INIT;

	size_t i;

	void *in1[] = {(void *) 0x0, (void *) 0x1, (void *) 0x2, (void *) 0x3};

	void *out1[] = {(void *) 0x3, (void *) 0x2, (void *) 0x1, (void *) 0x0};

	void *in2[] = {(void *) 0x0, (void *) 0x1, (void *) 0x2, (void *) 0x3, (void *) 0x4};

	void *out2[] = {(void *) 0x4, (void *) 0x3, (void *) 0x2, (void *) 0x1, (void *) 0x0};

	for (i = 0; i < 4; i++)

		cl_git_pass(git_vector_insert(&v, in1[i]));

	git_vector_reverse(&v);

	for (i = 0; i < 4; i++)

		cl_assert_equal_p(out1[i], git_vector_get(&v, i));

	git_vector_clear(&v);

	for (i = 0; i < 5; i++)

		cl_git_pass(git_vector_insert(&v, in2[i]));

	git_vector_reverse(&v);

	for (i = 0; i < 5; i++)

		cl_assert_equal_p(out2[i], git_vector_get(&v, i));

	git_vector_free(&v);

}