aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--README.md23
-rw-r--r--src/algo/ft_bsearch.c24
-rw-r--r--src/algo/ft_mergesort.c29
-rw-r--r--test/include/libft_test.h1
-rw-r--r--test/src/algo/test_ft_bsearch.c55
-rw-r--r--test/src/algo/test_ft_compar_int.c20
-rw-r--r--test/src/algo/test_ft_heapsort.c27
-rw-r--r--test/src/algo/test_ft_is_set.c23
-rw-r--r--test/src/algo/test_ft_lfind.c38
-rw-r--r--test/src/algo/test_ft_lsearch.c52
-rw-r--r--test/src/algo/test_ft_mergesort.c26
-rw-r--r--test/src/algo/test_ft_qsort.c26
-rw-r--r--test/src/algo/test_ft_reverse.c19
-rw-r--r--test/src/main.c10
-rw-r--r--test/src/runner/test_runner_algo.c59
15 files changed, 402 insertions, 30 deletions
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 <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* 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 <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* 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 <marvin@42.fr> +#+ +:+ +#+ */
+/* +#+#+#+#+#+ +#+ */
+/* 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);
+}
generated by cgit (git 2.34.1) at 2026-05-16 18:46:31 +0000