diff options
Diffstat (limited to 'tests/src/algo.c')
| -rw-r--r-- | tests/src/algo.c | 282 |
1 files changed, 282 insertions, 0 deletions
diff --git a/tests/src/algo.c b/tests/src/algo.c new file mode 100644 index 0000000..861158b --- /dev/null +++ b/tests/src/algo.c @@ -0,0 +1,282 @@ +#include <bh/algo.h> +#include <bh/unit.h> +#include <string.h> +#include <stdlib.h> + +#define SIZE (4 * 1024) +#define MAX_VALUE 0x1000 +#define TEST_RUNS 64 + +static int int_equal(const void *lhs, const void *rhs) +{ + return *(const int*)lhs - *(const int*)rhs; +} + +static int check_partition(size_t index, int pivot, int *array, size_t size) +{ + size_t i; + + for (i = 0; i < index; i++) + if (array[i] >= pivot) + return -1; + + for (i = index; i < size; i++) + if (array[i] < pivot) + return -1; + + return 0; +} + +static int check_heap(int *array, size_t size) +{ + size_t i, left, right; + + for (i = 0; i < size; i++) + { + left = i * 2 + 1; + right = i * 2 + 2; + + if (left < size && array[i] < array[left]) + return -1; + if (right < size && array[i] < array[right]) + return -1; + } + + return 0; +} + +static void reference_sort(int *array, size_t size) +{ + size_t i, j; + int tmp; + + /* Reference sort is... buble sort! */ + for (i = 0; i < size; i++) + { + for (j = 1; j < size; j++) + { + if (array[j - 1] > array[j]) + { + tmp = array[j - 1]; + array[j - 1] = array[j]; + array[j] = tmp; + } + } + } +} + +static int partition(void) +{ + int input[SIZE], in_count[MAX_VALUE], out_count[MAX_VALUE], *middle, pivot; + size_t i, j; + + for (i = 0; i < TEST_RUNS; i++) + { + memset(in_count, 0, sizeof(in_count)); + memset(out_count, 0, sizeof(out_count)); + + /* Populate test array and count numbers */ + for (j = 0; j < SIZE; j++) + { + input[j] = rand() % MAX_VALUE; + in_count[input[j]]++; + } + + /* Partition the array */ + if (i == 0) + pivot = -1; + else if (i == TEST_RUNS - 1) + pivot = MAX_VALUE; + else + pivot = MAX_VALUE / 2; + + middle = (int *)bh_partition(&pivot, input, SIZE, sizeof(int), int_equal); + + /* Count numbers in array */ + for (j = 0; j < SIZE; j++) + out_count[input[j]]++; + + /* Check partition */ + bh_unit_assert(check_partition(middle - input, pivot, input, SIZE) == 0); + + /* Verify, that array has same amount of numbers */ + for (j = 0; j < MAX_VALUE; j++) + bh_unit_assert(in_count[j] == out_count[j]); + } + + return 0; +} + +static int sort(void) +{ + int input[SIZE], reference[SIZE]; + size_t i, j; + + for (i = 0; i < TEST_RUNS; i++) + { + for (j = 0; j < SIZE; j++) + { + input[j] = rand() % MAX_VALUE; + reference[j] = input[j]; + } + + reference_sort(reference, SIZE); + bh_sort(input, SIZE, sizeof(int), int_equal); + bh_unit_assert(memcmp(reference, input, sizeof(input)) == 0); + + qsort(reference, SIZE, sizeof(int), int_equal); + bh_unit_assert(memcmp(reference, input, sizeof(input)) == 0); + } + + return 0; +} + +static int sort_insert(void) +{ + int input[SIZE], reference[SIZE]; + size_t i, j; + + for (i = 0; i < TEST_RUNS; i++) + { + for (j = 0; j < SIZE; j++) + { + input[j] = rand() % MAX_VALUE; + reference[j] = input[j]; + } + + reference_sort(reference, SIZE); + bh_sort_insert(input, SIZE, sizeof(int), int_equal); + bh_unit_assert(memcmp(reference, input, sizeof(input)) == 0); + + qsort(reference, SIZE, sizeof(int), int_equal); + bh_unit_assert(memcmp(reference, input, sizeof(input)) == 0); + } + + return 0; +} + +static int sort_shell(void) +{ + int input[SIZE], reference[SIZE]; + size_t i, j; + + for (i = 0; i < TEST_RUNS; i++) + { + for (j = 0; j < SIZE; j++) + { + input[j] = rand() % MAX_VALUE; + reference[j] = input[j]; + } + + reference_sort(reference, SIZE); + bh_sort_shell(input, SIZE, sizeof(int), int_equal); + bh_unit_assert(memcmp(reference, input, sizeof(input)) == 0); + + qsort(reference, SIZE, sizeof(int), int_equal); + bh_unit_assert(memcmp(reference, input, sizeof(input)) == 0); + + } + + return 0; +} + +static int sort_heap(void) +{ + int input[SIZE], reference[SIZE]; + size_t i, j; + + for (i = 0; i < TEST_RUNS; i++) + { + for (j = 0; j < SIZE; j++) + { + input[j] = rand() % MAX_VALUE; + reference[j] = input[j]; + } + + reference_sort(reference, SIZE); + bh_sort_heap(input, SIZE, sizeof(int), int_equal); + bh_unit_assert(memcmp(reference, input, sizeof(input)) == 0); + + qsort(reference, SIZE, sizeof(int), int_equal); + bh_unit_assert(memcmp(reference, input, sizeof(input)) == 0); + } + + return 0; +} + +static int sort_intro(void) +{ + int input[SIZE], reference[SIZE]; + size_t i, j; + + for (i = 0; i < TEST_RUNS; i++) + { + for (j = 0; j < SIZE; j++) + { + input[j] = rand() % MAX_VALUE; + reference[j] = input[j]; + } + + reference_sort(reference, SIZE); + bh_sort_intro(input, SIZE, sizeof(int), int_equal); + bh_unit_assert(memcmp(reference, input, sizeof(input)) == 0); + + qsort(reference, SIZE, sizeof(int), int_equal); + bh_unit_assert(memcmp(reference, input, sizeof(input)) == 0); + + } + + return 0; +} + +static int heap(void) +{ + int heap[SIZE], value; + size_t i, j; + + for (i = 0; i < TEST_RUNS; i++) + { + for (j = 0; j < SIZE; j++) + heap[j] = rand() % MAX_VALUE; + + bh_heap_make(heap, SIZE, sizeof(int), int_equal); + bh_unit_assert(check_heap(heap, SIZE) == 0); + } + + for (i = 0; i < TEST_RUNS; i++) + { + for (j = 0; j < SIZE; j++) + { + value = rand() % MAX_VALUE; + if (i == 0) + { + heap[j] = value; + bh_heap_insert(NULL, heap, j, sizeof(int), int_equal); + } + else + { + bh_heap_insert(&value, heap, j, sizeof(int), int_equal); + } + } + + bh_unit_assert(check_heap(heap, SIZE) == 0); + } + + return 0; +} + +int main(int argc, char **argv) +{ + (void)argc; + (void)argv; + + bh_unit_add("partition", partition); + bh_unit_add("sort_insert", sort_insert); + bh_unit_add("sort_shell", sort_shell); + bh_unit_add("sort_heap", sort_heap); + bh_unit_add("sort_intro", sort_intro); + bh_unit_add("sort", sort); + bh_unit_add("heap", heap); + + return bh_unit_run(); +} |