From adbcf69ed50ea3896d4bbe863ea5d214ae5a0299 Mon Sep 17 00:00:00 2001 From: Charles Date: Thu, 13 Feb 2020 23:15:16 +0100 Subject: Added tests for algo*, fixing ft_bsearch and ft_mergesort --- README.md | 23 ++++++++------- src/algo/ft_bsearch.c | 24 +++++++++------- src/algo/ft_mergesort.c | 29 +++++++++++++------ test/include/libft_test.h | 1 + test/src/algo/test_ft_bsearch.c | 55 +++++++++++++++++++++++++++++++++++ test/src/algo/test_ft_compar_int.c | 20 +++++++++++++ test/src/algo/test_ft_heapsort.c | 27 +++++++++++++++++ test/src/algo/test_ft_is_set.c | 23 +++++++++++++++ test/src/algo/test_ft_lfind.c | 38 ++++++++++++++++++++++++ test/src/algo/test_ft_lsearch.c | 52 +++++++++++++++++++++++++++++++++ test/src/algo/test_ft_mergesort.c | 26 +++++++++++++++++ test/src/algo/test_ft_qsort.c | 26 +++++++++++++++++ test/src/algo/test_ft_reverse.c | 19 ++++++++++++ test/src/main.c | 10 +++++++ test/src/runner/test_runner_algo.c | 59 ++++++++++++++++++++++++++++++++++++++ 15 files changed, 402 insertions(+), 30 deletions(-) create mode 100644 test/src/algo/test_ft_bsearch.c create mode 100644 test/src/algo/test_ft_compar_int.c create mode 100644 test/src/algo/test_ft_heapsort.c create mode 100644 test/src/algo/test_ft_is_set.c create mode 100644 test/src/algo/test_ft_lfind.c create mode 100644 test/src/algo/test_ft_lsearch.c create mode 100644 test/src/algo/test_ft_mergesort.c create mode 100644 test/src/algo/test_ft_qsort.c create mode 100644 test/src/algo/test_ft_reverse.c create mode 100644 test/src/runner/test_runner_algo.c diff --git a/README.md b/README.md index 088da89..f6eac36 100644 --- a/README.md +++ b/README.md @@ -46,17 +46,18 @@ Much like the `.gitignore` file, you can put the files/directory to ignore when ### algo -| Name | Prototype | Description | Tested | -|---------------|-----------|-------------|--------| -| ft_bsearch | | | [ ] | -| ft_compar_int | | | [ ] | -| ft_heapsort | | | [ ] | -| ft_is_set | | | [ ] | -| ft_lfind | | | [ ] | -| ft_lsearch | | | [ ] | -| ft_mergesort | | | [ ] | -| ft_qsort | | | [ ] | -| ft_reverse | | | [ ] | + +| Name | Prototype | Description | Tested | +|---------------|-----------------------------------------------------------------------------------------------------|------------------------------------------------------------------------------------|--------| +| ft_bsearch | `void *ft_bsearch(const void *base, size_t nel, size_t width, t_ftsearch_const *consts)` | search `consts.key` in `base` using binary search (NULL if not found) | [x] | +| ft_compar_int | `int ft_compar_int(const void *a, const void *b)` | comparison function of `int` | [x] | +| ft_heapsort | `int ft_heapsort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *))` | sort `base` using heapsort | [?] | +| ft_is_set | `t_ftbool ft_is_set(void *base, size_t nel, size_t width, t_ftcompar_func compar)` | check is `base` has unique elements | [x] | +| ft_lfind | `void *ft_lfind(const void *base, size_t *nelp, size_t width, t_ftsearch_const *consts)` | search `consts.key` in `base` using linear search (NULL if not found) | [x] | +| ft_lsearch | `void *ft_lsearch(const void *base, size_t *nelp, size_t width, t_ftsearch_const *consts)` | search `consts.key` in `base` using linear search (insert at the end if not found) | [x] | +| ft_mergesort | `int ft_mergesort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *))` | sort `base` using mergesort | [x] | +| ft_qsort | `void ft_qsort(void *base, size_t nel, size_t width, t_ftcompar_func compar)` | sort `base` using quicksort | [x] | +| ft_reverse | `void ft_reverse(void *base, size_t nel, size_t width)` | reverse `base` | [x] | ### bt diff --git a/src/algo/ft_bsearch.c b/src/algo/ft_bsearch.c index 8066479..5132fa2 100644 --- a/src/algo/ft_bsearch.c +++ b/src/algo/ft_bsearch.c @@ -6,7 +6,7 @@ /* By: cacharle +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2020/02/10 05:29:05 by cacharle #+# #+# */ -/* Updated: 2020/02/10 05:43:18 by cacharle ### ########.fr */ +/* Updated: 2020/02/13 23:14:48 by cacharle ### ########.fr */ /* */ /* ************************************************************************** */ @@ -15,14 +15,18 @@ void *ft_bsearch(const void *base, size_t nel, size_t width, t_ftsearch_const *consts) { - void *found; + int res; + size_t mid; - if ((consts->compar)(consts->key, base + (nel / 2) * width) == 0) - return ((void*)base + (nel / 2) * width); - if ((found = ft_bsearch(base, nel / 2, width, consts)) != NULL) - return (found); - if ((found = ft_bsearch(base + (nel / 2) * width, nel - nel / 2, - width, consts)) != NULL) - return (found); - return (NULL); + if (nel < 1) + return (NULL); + mid = nel / 2; + res = (consts->compar)(consts->key, base + mid * width); + if (res == 0) + return ((void*)base + mid * width); + if (res < 0) + return (ft_bsearch(base, mid, width, consts)); + else + return (ft_bsearch(base + (mid + 1) * width, nel - mid - 1, + width, consts)); } diff --git a/src/algo/ft_mergesort.c b/src/algo/ft_mergesort.c index 5af248e..25b4255 100644 --- a/src/algo/ft_mergesort.c +++ b/src/algo/ft_mergesort.c @@ -6,7 +6,7 @@ /* By: cacharle +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2020/02/10 02:26:41 by cacharle #+# #+# */ -/* Updated: 2020/02/10 02:59:10 by cacharle ### ########.fr */ +/* Updated: 2020/02/13 23:14:21 by cacharle ### ########.fr */ /* */ /* ************************************************************************** */ @@ -22,22 +22,31 @@ static int st_mergesort_error(void *left, void *right) static void st_merge_sorted(struct s_merge_sorted_arrays *arrays, size_t nel, size_t width, int (*compar)(const void *, const void *)) { + size_t bi; size_t li; size_t ri; + size_t mid; + mid = nel / 2; + bi = 0; li = 0; ri = 0; - while (li < nel / 2 && ri < nel - nel / 2) + while (li < mid && ri < nel - mid) { if (compar(arrays->left + li * width, arrays->right + ri * width) < 0) - ft_memcpy(arrays->base, arrays->left + li++ * width, width); + ft_memcpy(arrays->base + bi * width, + arrays->left + li++ * width, width); else - ft_memcpy(arrays->base, arrays->right + ri++ * width, width); + ft_memcpy(arrays->base + bi * width, + arrays->right + ri++ * width, width); + bi++; } - while (li < nel / 2) - ft_memcpy(arrays->base, arrays->left + li++ * width, width); - while (ri < nel - nel / 2) - ft_memcpy(arrays->base, arrays->right + ri++ * width, width); + while (li < mid) + ft_memcpy(arrays->base + bi++ * width, + arrays->left + li++ * width, width); + while (ri < nel - mid) + ft_memcpy(arrays->base + bi++ * width, + arrays->right + ri++ * width, width); } int ft_mergesort(void *base, size_t nel, size_t width, @@ -54,12 +63,14 @@ int ft_mergesort(void *base, size_t nel, size_t width, if ((arrays.right = malloc((nel - mid) * width)) == NULL) return (st_mergesort_error(arrays.left, NULL)); ft_memcpy(arrays.left, base, mid * width); - ft_memcpy(arrays.right, base, (nel - mid) * width); + ft_memcpy(arrays.right, base + mid * width, (nel - mid) * width); if (ft_mergesort(arrays.left, mid, width, compar) == -1) return (st_mergesort_error(arrays.left, arrays.right)); if (ft_mergesort(arrays.right, nel - mid, width, compar) == -1) return (st_mergesort_error(arrays.left, arrays.right)); arrays.base = base; st_merge_sorted(&arrays, nel, width, compar); + free(arrays.left); + free(arrays.right); return (0); } diff --git a/test/include/libft_test.h b/test/include/libft_test.h index f710c7d..85aa7d9 100644 --- a/test/include/libft_test.h +++ b/test/include/libft_test.h @@ -11,6 +11,7 @@ # include "unity.h" # include "unity_fixture.h" # include "libft.h" +# include "libft_algo.h" # include "libft_ht.h" # include "helper/helper_segfault.h" diff --git a/test/src/algo/test_ft_bsearch.c b/test/src/algo/test_ft_bsearch.c new file mode 100644 index 0000000..27858ee --- /dev/null +++ b/test/src/algo/test_ft_bsearch.c @@ -0,0 +1,55 @@ +#include "libft_test.h" + +TEST_GROUP(ft_bsearch); + +TEST_SETUP(ft_bsearch) +{} + +TEST_TEAR_DOWN(ft_bsearch) +{} + +TEST(ft_bsearch, basic) +{ + int arr[] = {3, 4, 1, 2, 7, 189, -1, -134, 7, 1, 34}; + t_ftsearch_const consts; + + int a = 189; + consts.key = &a; + consts.compar = ft_compar_int; + + size_t nelp = sizeof(arr) / sizeof(int); + qsort(arr, nelp, sizeof(int), ft_compar_int); + + void *ptr = ft_bsearch(arr, nelp, sizeof(int), &consts); + TEST_ASSERT_EQUAL_PTR(bsearch(consts.key, arr, nelp, sizeof(int), consts.compar), ptr); + + int b = 123; + consts.key = &b; + ptr = ft_bsearch(arr, nelp, sizeof(int), &consts); + TEST_ASSERT_NULL(ptr); + + int c = -134; + consts.key = &c; + ptr = ft_bsearch(arr, nelp, sizeof(int), &consts); + TEST_ASSERT_EQUAL_PTR(bsearch(consts.key, arr, nelp, sizeof(int), consts.compar), ptr); + + int e = 1; + consts.key = &e; + ptr = ft_bsearch(arr, nelp, sizeof(int), &consts); + TEST_ASSERT_EQUAL_PTR(bsearch(consts.key, arr, nelp, sizeof(int), consts.compar), ptr); + + int d = -1; + consts.key = &d; + ptr = ft_bsearch(arr, nelp, sizeof(int), &consts); + TEST_ASSERT_EQUAL_PTR(bsearch(consts.key, arr, nelp, sizeof(int), consts.compar), ptr); + + int f = 34; + consts.key = &f; + ptr = ft_bsearch(arr, nelp, sizeof(int), &consts); + TEST_ASSERT_EQUAL_PTR(bsearch(consts.key, arr, nelp, sizeof(int), consts.compar), ptr); + + int g = 7; + consts.key = &g; + ptr = ft_bsearch(arr, nelp, sizeof(int), &consts); + TEST_ASSERT_EQUAL_PTR(bsearch(consts.key, arr, nelp, sizeof(int), consts.compar), ptr); +} diff --git a/test/src/algo/test_ft_compar_int.c b/test/src/algo/test_ft_compar_int.c new file mode 100644 index 0000000..39cc322 --- /dev/null +++ b/test/src/algo/test_ft_compar_int.c @@ -0,0 +1,20 @@ +#include "libft_test.h" + +TEST_GROUP(ft_compar_int); + +TEST_SETUP(ft_compar_int) +{} + +TEST_TEAR_DOWN(ft_compar_int) +{} + +TEST(ft_compar_int, basic) +{ + int a = 4; + int b = 3; + + TEST_ASSERT_GREATER_THAN(0, ft_compar_int(&a, &b)); + TEST_ASSERT_LESS_THAN(0, ft_compar_int(&b, &a)); + TEST_ASSERT_EQUAL(0, ft_compar_int(&a, &a)); + TEST_ASSERT_EQUAL(0, ft_compar_int(&b, &b)); +} diff --git a/test/src/algo/test_ft_heapsort.c b/test/src/algo/test_ft_heapsort.c new file mode 100644 index 0000000..6c2c3fb --- /dev/null +++ b/test/src/algo/test_ft_heapsort.c @@ -0,0 +1,27 @@ +#include "libft_test.h" + +TEST_GROUP(ft_heapsort); + +TEST_SETUP(ft_heapsort) +{} + +TEST_TEAR_DOWN(ft_heapsort) +{} + +static int compar(const void *a, const void *b) +{ + return *(int*)a - *(int*)b; +} + +TEST(ft_heapsort, basic) +{ + TEST_IGNORE(); + int arr[] = {3, 4, 1, 2, 7, 189, -1, -134, 7, 1, 34}; + int sorted_arr[sizeof(arr)]; + + memcpy(sorted_arr, arr, sizeof(arr)); + qsort(sorted_arr, sizeof(arr) / sizeof(int), sizeof(int), compar); + + ft_heapsort(arr, sizeof(arr) / sizeof(int), sizeof(int), compar); + TEST_ASSERT_EQUAL_INT_ARRAY(sorted_arr, arr, sizeof(arr) / sizeof(int)); +} diff --git a/test/src/algo/test_ft_is_set.c b/test/src/algo/test_ft_is_set.c new file mode 100644 index 0000000..604ec53 --- /dev/null +++ b/test/src/algo/test_ft_is_set.c @@ -0,0 +1,23 @@ +#include "libft_test.h" + +TEST_GROUP(ft_is_set); + +TEST_SETUP(ft_is_set) +{} + +TEST_TEAR_DOWN(ft_is_set) +{} + +static int compar(const void *a, const void *b) +{ + return *(int*)a - *(int*)b; +} + +TEST(ft_is_set, basic) +{ + int arr[] = {3, 4, 1, 2, 7, 189, -1, -134, 7, 1, 34}; + int unique_arr[] = {3, 4, 2, 189, -1, -134, 7, 1, 34}; + + TEST_ASSERT_FALSE(ft_is_set(arr, sizeof(arr) / sizeof(int), sizeof(int), compar)); + TEST_ASSERT_TRUE(ft_is_set(unique_arr, sizeof(unique_arr) / sizeof(int), sizeof(int), compar)); +} diff --git a/test/src/algo/test_ft_lfind.c b/test/src/algo/test_ft_lfind.c new file mode 100644 index 0000000..0080d55 --- /dev/null +++ b/test/src/algo/test_ft_lfind.c @@ -0,0 +1,38 @@ +#include "libft_test.h" + +TEST_GROUP(ft_lfind); + +TEST_SETUP(ft_lfind) +{} + +TEST_TEAR_DOWN(ft_lfind) +{} + +TEST(ft_lfind, basic) +{ + int arr[] = {3, 4, 1, 2, 7, 189, -1, -134, 7, 1, 34}; + t_ftsearch_const consts; + + int a = 189; + consts.key = &a; + consts.compar = ft_compar_int; + + size_t nelp = sizeof(arr) / sizeof(int); + void *ptr = ft_lfind(arr, &nelp, sizeof(int), &consts); + TEST_ASSERT_EQUAL_PTR(arr + 5, ptr); + + int b = 123; + consts.key = &b; + ptr = ft_lfind(arr, &nelp, sizeof(int), &consts); + TEST_ASSERT_NULL(ptr); + + int c = 34; + consts.key = &c; + ptr = ft_lfind(arr, &nelp, sizeof(int), &consts); + TEST_ASSERT_EQUAL_PTR(arr + 10, ptr); + + int d = 3; + consts.key = &d; + ptr = ft_lfind(arr, &nelp, sizeof(int), &consts); + TEST_ASSERT_EQUAL_PTR(arr, ptr); +} diff --git a/test/src/algo/test_ft_lsearch.c b/test/src/algo/test_ft_lsearch.c new file mode 100644 index 0000000..13fae13 --- /dev/null +++ b/test/src/algo/test_ft_lsearch.c @@ -0,0 +1,52 @@ +#include "libft_test.h" + +TEST_GROUP(ft_lsearch); + +TEST_SETUP(ft_lsearch) +{} + +TEST_TEAR_DOWN(ft_lsearch) +{} + +TEST(ft_lsearch, basic) +{ + int arr[32] = {3, 4, 1, 2, 7, 189, -1, -134, 7, 1, 34}; + t_ftsearch_const consts; + + int a = 189; + consts.key = &a; + consts.compar = ft_compar_int; + + size_t nelp = 11; + void *ptr = ft_lsearch(arr, &nelp, sizeof(int), &consts); + TEST_ASSERT_EQUAL_PTR(arr + 5, ptr); + + int c = 34; + consts.key = &c; + ptr = ft_lsearch(arr, &nelp, sizeof(int), &consts); + TEST_ASSERT_EQUAL_PTR(arr + 10, ptr); + + int d = 3; + consts.key = &d; + ptr = ft_lsearch(arr, &nelp, sizeof(int), &consts); + TEST_ASSERT_EQUAL_PTR(arr, ptr); + + int b = 123; + consts.key = &b; + ptr = ft_lsearch(arr, &nelp, sizeof(int), &consts); + TEST_ASSERT_EQUAL(12, nelp); + TEST_ASSERT_EQUAL(123, arr[11]); + TEST_ASSERT_EQUAL_PTR(arr + 11, ptr); + + ptr = ft_lsearch(arr, &nelp, sizeof(int), &consts); + TEST_ASSERT_EQUAL(12, nelp); + TEST_ASSERT_EQUAL(123, arr[11]); + TEST_ASSERT_EQUAL_PTR(arr + 11, ptr); + + int e = 1234; + consts.key = &e; + ptr = ft_lsearch(arr, &nelp, sizeof(int), &consts); + TEST_ASSERT_EQUAL(13, nelp); + TEST_ASSERT_EQUAL(1234, arr[12]); + TEST_ASSERT_EQUAL_PTR(arr + 12, ptr); +} diff --git a/test/src/algo/test_ft_mergesort.c b/test/src/algo/test_ft_mergesort.c new file mode 100644 index 0000000..567e31d --- /dev/null +++ b/test/src/algo/test_ft_mergesort.c @@ -0,0 +1,26 @@ +#include "libft_test.h" + +TEST_GROUP(ft_mergesort); + +TEST_SETUP(ft_mergesort) +{} + +TEST_TEAR_DOWN(ft_mergesort) +{} + +static int compar(const void *a, const void *b) +{ + return *(int*)a - *(int*)b; +} + +TEST(ft_mergesort, basic) +{ + int arr[] = {3, 4, 1, 2, 7, 189, -1, -134, 7, 1, 34}; + int sorted_arr[sizeof(arr)]; + + memcpy(sorted_arr, arr, sizeof(arr)); + qsort(sorted_arr, sizeof(arr) / sizeof(int), sizeof(int), compar); + + ft_mergesort(arr, sizeof(arr) / sizeof(int), sizeof(int), compar); + TEST_ASSERT_EQUAL_INT_ARRAY(sorted_arr, arr, sizeof(arr) / sizeof(int)); +} diff --git a/test/src/algo/test_ft_qsort.c b/test/src/algo/test_ft_qsort.c new file mode 100644 index 0000000..25a5ef6 --- /dev/null +++ b/test/src/algo/test_ft_qsort.c @@ -0,0 +1,26 @@ +#include "libft_test.h" + +TEST_GROUP(ft_qsort); + +TEST_SETUP(ft_qsort) +{} + +TEST_TEAR_DOWN(ft_qsort) +{} + +static int compar(const void *a, const void *b) +{ + return *(int*)a - *(int*)b; +} + +TEST(ft_qsort, basic) +{ + int arr[] = {3, 4, 1, 2, 7, 189, -1, -134, 7, 1, 34}; + int sorted_arr[sizeof(arr)]; + + memcpy(sorted_arr, arr, sizeof(arr)); + qsort(sorted_arr, sizeof(arr) / sizeof(int), sizeof(int), compar); + + ft_qsort(arr, sizeof(arr) / sizeof(int), sizeof(int), compar); + TEST_ASSERT_EQUAL_INT_ARRAY(sorted_arr, arr, sizeof(arr) / sizeof(int)); +} diff --git a/test/src/algo/test_ft_reverse.c b/test/src/algo/test_ft_reverse.c new file mode 100644 index 0000000..feca520 --- /dev/null +++ b/test/src/algo/test_ft_reverse.c @@ -0,0 +1,19 @@ +#include "libft_test.h" + +TEST_GROUP(ft_reverse); + +TEST_SETUP(ft_reverse) +{} + +TEST_TEAR_DOWN(ft_reverse) +{} + +TEST(ft_reverse, basic) +{ + int arr[] = {3, 4, 1, 2, 7, 189, -1, -134, 7, 1, 34}; + int rev_arr[] = {34, 1, 7, -134, -1, 189, 7, 2, 1, 4, 3}; + + ft_reverse(arr, sizeof(arr) / sizeof(int), sizeof(int)); + TEST_ASSERT_EQUAL_INT_ARRAY(rev_arr, arr, sizeof(arr) / sizeof(int)); + +} diff --git a/test/src/main.c b/test/src/main.c index 7c96e53..122a12d 100644 --- a/test/src/main.c +++ b/test/src/main.c @@ -35,6 +35,16 @@ static void run_all_test(void) RUN_TEST_GROUP(ft_htget); RUN_TEST_GROUP(ft_htset); + // algo + RUN_TEST_GROUP(ft_bsearch); + RUN_TEST_GROUP(ft_compar_int); + RUN_TEST_GROUP(ft_heapsort); + RUN_TEST_GROUP(ft_is_set); + RUN_TEST_GROUP(ft_lfind); + RUN_TEST_GROUP(ft_lsearch); + RUN_TEST_GROUP(ft_mergesort); + RUN_TEST_GROUP(ft_qsort); + RUN_TEST_GROUP(ft_reverse); } int main(int argc, const char **argv) diff --git a/test/src/runner/test_runner_algo.c b/test/src/runner/test_runner_algo.c new file mode 100644 index 0000000..8873797 --- /dev/null +++ b/test/src/runner/test_runner_algo.c @@ -0,0 +1,59 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* test_runner_algo.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2020/02/13 21:25:52 by cacharle #+# #+# */ +/* Updated: 2020/02/13 21:37:15 by cacharle ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "libft_test.h" + + +TEST_GROUP_RUNNER(ft_bsearch) +{ + RUN_TEST_CASE(ft_bsearch, basic); +} + +TEST_GROUP_RUNNER(ft_compar_int) +{ + RUN_TEST_CASE(ft_compar_int, basic); +} + +TEST_GROUP_RUNNER(ft_heapsort) +{ + RUN_TEST_CASE(ft_heapsort, basic); +} + +TEST_GROUP_RUNNER(ft_is_set) +{ + RUN_TEST_CASE(ft_is_set, basic); +} + +TEST_GROUP_RUNNER(ft_lfind) +{ + RUN_TEST_CASE(ft_lfind, basic); +} + +TEST_GROUP_RUNNER(ft_lsearch) +{ + RUN_TEST_CASE(ft_lsearch, basic); +} + +TEST_GROUP_RUNNER(ft_mergesort) +{ + RUN_TEST_CASE(ft_mergesort, basic); +} + +TEST_GROUP_RUNNER(ft_qsort) +{ + RUN_TEST_CASE(ft_qsort, basic); +} + +TEST_GROUP_RUNNER(ft_reverse) +{ + RUN_TEST_CASE(ft_reverse, basic); +} -- cgit