/* Tests to confirm e2fsck_dir_info_max_less_equal is correct */

#include <assert.h>
#include <stdio.h>

#define ARRAY_SIZE(a) ((sizeof(a)) / (sizeof((a)[0])))

/*
 * Return the max index that has ino less or equal to @ino
 * If not found, return -1
 */
static int max_less_equal(int *array, int size, int ino)
{
	int		low = 0;
	int		high = size - 1;
	int		mid;
	int		tmp_ino;
	int 		index = -1;

	while (low <= high) {
		mid = (low + high) / 2;
		tmp_ino = array[mid];
		if (ino == tmp_ino) {
			return mid;
		} else if (ino < tmp_ino) {
			high = mid - 1;
		} else {
			/*
			 * The mid ino is less than @ino, remember the index
			 * here so we won't miss this ino
			 */
			index = mid;
			low = mid + 1;
		}
	}
	return index;
}

/*
 * Return the min index that has ino larger or equal to @ino
 * If not found, return -1
 */
static int min_larger_equal(int *array, int size, int ino)
{
	int		low = 0;
	int		high = size - 1;
	int		mid;
	int		tmp_ino;
	int 		index = -1;

	while (low <= high) {
		mid = (low + high) / 2;
		tmp_ino = array[mid];
		if (ino == tmp_ino) {
			return mid;
		} else if (ino < tmp_ino) {
			/*
			 * The mid ino is larger than @ino, remember the index
			 * here so we won't miss this ino
			 */
			index = mid;
			high = mid - 1;
		} else {
			low = mid + 1;
		}
	}
	return index;
}

static int test1(void)
{
	int array[] = {0};

	assert(max_less_equal(array, ARRAY_SIZE(array), 0) == 0);
	assert(max_less_equal(array, ARRAY_SIZE(array), 1) == 0);
	assert(max_less_equal(array, ARRAY_SIZE(array), -1) == -1);
	assert(max_less_equal(array, ARRAY_SIZE(array), 2) == 0);
	assert(max_less_equal(array, ARRAY_SIZE(array), -2) == -1);

	assert(min_larger_equal(array, ARRAY_SIZE(array), 0) == 0);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 1) == -1);
	assert(min_larger_equal(array, ARRAY_SIZE(array), -1) == 0);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 2) == -1);
	assert(min_larger_equal(array, ARRAY_SIZE(array), -2) == 0);
}

static int test2(void)
{
	int array[] = {};

	assert(max_less_equal(array, ARRAY_SIZE(array), 0) == -1);
	assert(max_less_equal(array, ARRAY_SIZE(array), 1) == -1);
	assert(max_less_equal(array, ARRAY_SIZE(array), -1) == -1);
	assert(max_less_equal(array, ARRAY_SIZE(array), 2) == -1);
	assert(max_less_equal(array, ARRAY_SIZE(array), -2) == -1);

	assert(min_larger_equal(array, ARRAY_SIZE(array), 0) == -1);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 1) == -1);
	assert(min_larger_equal(array, ARRAY_SIZE(array), -1) == -1);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 2) == -1);
	assert(min_larger_equal(array, ARRAY_SIZE(array), -2) == -1);
}

static int test3(void)
{
	int array[] = {0, 1, 2};

	assert(max_less_equal(array, ARRAY_SIZE(array), 0) == 0);
	assert(max_less_equal(array, ARRAY_SIZE(array), 1) == 1);
	assert(max_less_equal(array, ARRAY_SIZE(array), 2) == 2);
	assert(max_less_equal(array, ARRAY_SIZE(array), 3) == 2);
	assert(max_less_equal(array, ARRAY_SIZE(array), 4) == 2);
	assert(max_less_equal(array, ARRAY_SIZE(array), 5) == 2);
	assert(max_less_equal(array, ARRAY_SIZE(array), -1) == -1);

	assert(min_larger_equal(array, ARRAY_SIZE(array), 0) == 0);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 1) == 1);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 2) == 2);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 3) == -1);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 4) == -1);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 5) == -1);
	assert(min_larger_equal(array, ARRAY_SIZE(array), -1) == 0);
	assert(min_larger_equal(array, ARRAY_SIZE(array), -2) == 0);
	assert(min_larger_equal(array, ARRAY_SIZE(array), -3) == 0);
	assert(min_larger_equal(array, ARRAY_SIZE(array), -100) == 0);
}

static int test4(void)
{
	int array[] = {0, 2, 4};

	assert(max_less_equal(array, ARRAY_SIZE(array), 0) == 0);
	assert(max_less_equal(array, ARRAY_SIZE(array), 1) == 0);
	assert(max_less_equal(array, ARRAY_SIZE(array), 2) == 1);
	assert(max_less_equal(array, ARRAY_SIZE(array), 3) == 1);
	assert(max_less_equal(array, ARRAY_SIZE(array), 4) == 2);
	assert(max_less_equal(array, ARRAY_SIZE(array), 5) == 2);
	assert(max_less_equal(array, ARRAY_SIZE(array), 6) == 2);
	assert(max_less_equal(array, ARRAY_SIZE(array), 7) == 2);
	assert(max_less_equal(array, ARRAY_SIZE(array), -1) == -1);

	assert(min_larger_equal(array, ARRAY_SIZE(array), 0) == 0);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 1) == 1);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 2) == 1);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 3) == 2);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 4) == 2);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 5) == -1);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 6) == -1);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 7) == -1);
	assert(min_larger_equal(array, ARRAY_SIZE(array), -1) == 0);
	assert(min_larger_equal(array, ARRAY_SIZE(array), -2) == 0);
}

static int test5(void)
{
	int array[] = {0, 2};

	assert(max_less_equal(array, ARRAY_SIZE(array), 0) == 0);
	assert(max_less_equal(array, ARRAY_SIZE(array), 1) == 0);
	assert(max_less_equal(array, ARRAY_SIZE(array), 2) == 1);
	assert(max_less_equal(array, ARRAY_SIZE(array), 3) == 1);
	assert(max_less_equal(array, ARRAY_SIZE(array), 4) == 1);
	assert(max_less_equal(array, ARRAY_SIZE(array), 5) == 1);
	assert(max_less_equal(array, ARRAY_SIZE(array), 6) == 1);
	assert(max_less_equal(array, ARRAY_SIZE(array), 7) == 1);
	assert(max_less_equal(array, ARRAY_SIZE(array), -1) == -1);

	assert(min_larger_equal(array, ARRAY_SIZE(array), 0) == 0);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 1) == 1);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 2) == 1);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 3) == -1);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 4) == -1);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 5) == -1);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 6) == -1);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 7) == -1);
	assert(min_larger_equal(array, ARRAY_SIZE(array), -1) == 0);
}

static int test6(void)
{
	int array[] = {0, 2, 4, 8};

	assert(max_less_equal(array, ARRAY_SIZE(array), 0) == 0);
	assert(max_less_equal(array, ARRAY_SIZE(array), 1) == 0);
	assert(max_less_equal(array, ARRAY_SIZE(array), 2) == 1);
	assert(max_less_equal(array, ARRAY_SIZE(array), 3) == 1);
	assert(max_less_equal(array, ARRAY_SIZE(array), 4) == 2);
	assert(max_less_equal(array, ARRAY_SIZE(array), 5) == 2);
	assert(max_less_equal(array, ARRAY_SIZE(array), 6) == 2);
	assert(max_less_equal(array, ARRAY_SIZE(array), 7) == 2);
	assert(max_less_equal(array, ARRAY_SIZE(array), 8) == 3);
	assert(max_less_equal(array, ARRAY_SIZE(array), 9) == 3);
	assert(max_less_equal(array, ARRAY_SIZE(array), 10) == 3);
	assert(max_less_equal(array, ARRAY_SIZE(array), 1000) == 3);
	assert(max_less_equal(array, ARRAY_SIZE(array), -1) == -1);

	assert(min_larger_equal(array, ARRAY_SIZE(array), 0) == 0);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 1) == 1);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 2) == 1);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 3) == 2);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 4) == 2);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 5) == 3);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 6) == 3);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 7) == 3);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 8) == 3);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 9) == -1);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 10) == -1);
	assert(min_larger_equal(array, ARRAY_SIZE(array), 1000) == -1);
	assert(min_larger_equal(array, ARRAY_SIZE(array), -1) == 0);
}

int main()
{
	test1();
	test2();
	test3();
	test4();
	test5();
	test6();
}