From c98de126d2252fe47dc2a9094a5f9a8fa6b4b60a Mon Sep 17 00:00:00 2001 From: Charles Cabergs Date: Sun, 11 Oct 2020 15:52:52 +0200 Subject: Removing libft/minishell_test submodules, Removing subject/README/etc --- libft/src/algo/ft_bsearch.c | 32 ++++++++++++++ libft/src/algo/ft_compar_int.c | 25 +++++++++++ libft/src/algo/ft_compar_str.c | 25 +++++++++++ libft/src/algo/ft_is_set.c | 39 +++++++++++++++++ libft/src/algo/ft_lfind.c | 28 ++++++++++++ libft/src/algo/ft_lsearch.c | 23 ++++++++++ libft/src/algo/ft_mergesort.c | 98 ++++++++++++++++++++++++++++++++++++++++++ libft/src/algo/ft_qsort.c | 97 +++++++++++++++++++++++++++++++++++++++++ libft/src/algo/ft_reverse.c | 34 +++++++++++++++ 9 files changed, 401 insertions(+) create mode 100644 libft/src/algo/ft_bsearch.c create mode 100644 libft/src/algo/ft_compar_int.c create mode 100644 libft/src/algo/ft_compar_str.c create mode 100644 libft/src/algo/ft_is_set.c create mode 100644 libft/src/algo/ft_lfind.c create mode 100644 libft/src/algo/ft_lsearch.c create mode 100644 libft/src/algo/ft_mergesort.c create mode 100644 libft/src/algo/ft_qsort.c create mode 100644 libft/src/algo/ft_reverse.c (limited to 'libft/src/algo') diff --git a/libft/src/algo/ft_bsearch.c b/libft/src/algo/ft_bsearch.c new file mode 100644 index 0000000..5132fa2 --- /dev/null +++ b/libft/src/algo/ft_bsearch.c @@ -0,0 +1,32 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* ft_bsearch.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2020/02/10 05:29:05 by cacharle #+# #+# */ +/* Updated: 2020/02/13 23:14:48 by cacharle ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "libft_algo.h" + +void *ft_bsearch(const void *base, size_t nel, size_t width, + t_ftsearch_const *consts) +{ + int res; + size_t mid; + + 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/libft/src/algo/ft_compar_int.c b/libft/src/algo/ft_compar_int.c new file mode 100644 index 0000000..ab057bf --- /dev/null +++ b/libft/src/algo/ft_compar_int.c @@ -0,0 +1,25 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* ft_compar_int.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2020/01/19 08:24:43 by cacharle #+# #+# */ +/* Updated: 2020/04/04 22:30:09 by charles ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "libft.h" + +/* +** \brief Comparison function for 2 ints +** \param a Pointer to first int +** \param b Pointer to first int +** \return The difference between a and b +*/ + +int ft_compar_int(const void *a, const void *b) +{ + return (*(int*)a - *(int*)b); +} diff --git a/libft/src/algo/ft_compar_str.c b/libft/src/algo/ft_compar_str.c new file mode 100644 index 0000000..6749ab0 --- /dev/null +++ b/libft/src/algo/ft_compar_str.c @@ -0,0 +1,25 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* ft_compar_str.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: charles +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2020/04/04 15:44:24 by charles #+# #+# */ +/* Updated: 2020/04/04 22:31:15 by charles ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "libft_algo.h" + +/* +** \brief String comparison function +** \param s1_p Pointer to first string +** \param s2_p Pointer to second string +** \return `strcmp` of both strings +*/ + +int ft_compar_str(const void *s1_p, const void *s2_p) +{ + return (ft_strcmp(*(const char**)s1_p, *(const char**)s2_p)); +} diff --git a/libft/src/algo/ft_is_set.c b/libft/src/algo/ft_is_set.c new file mode 100644 index 0000000..fd26a88 --- /dev/null +++ b/libft/src/algo/ft_is_set.c @@ -0,0 +1,39 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* ft_is_set.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2020/01/19 07:17:15 by cacharle #+# #+# */ +/* Updated: 2020/04/04 22:33:03 by charles ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "libft_algo.h" + +/* +** \brief Test whether array only contains unique elements +** \param base Array to test +** \param nel Number of element in the array +** \param width Size of an element +** \param compar Comparison function to test if 2 elements are equal +*/ + +bool ft_is_set(void *base, size_t nel, size_t width, + t_ftcompar_func compar) +{ + size_t i; + + if (nel < 2) + return (TRUE); + ft_qsort(base, nel, width, compar); + i = 0; + while (i < nel - 1) + { + if (compar(base + (i * width), base + ((i + 1) * width)) == 0) + return (FALSE); + i++; + } + return (TRUE); +} diff --git a/libft/src/algo/ft_lfind.c b/libft/src/algo/ft_lfind.c new file mode 100644 index 0000000..8538f50 --- /dev/null +++ b/libft/src/algo/ft_lfind.c @@ -0,0 +1,28 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* ft_lfind.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2020/02/10 05:49:19 by cacharle #+# #+# */ +/* Updated: 2020/02/10 05:58:19 by cacharle ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "libft_algo.h" + +void *ft_lfind(const void *base, size_t *nelp, size_t width, + t_ftsearch_const *consts) +{ + size_t i; + + i = 0; + while (i < *nelp) + { + if ((consts->compar)(consts->key, base + i * width) == 0) + return ((void*)base + i * width); + i++; + } + return (NULL); +} diff --git a/libft/src/algo/ft_lsearch.c b/libft/src/algo/ft_lsearch.c new file mode 100644 index 0000000..4c77bca --- /dev/null +++ b/libft/src/algo/ft_lsearch.c @@ -0,0 +1,23 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* ft_lsearch.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2020/02/10 05:53:57 by cacharle #+# #+# */ +/* Updated: 2020/02/10 05:59:33 by cacharle ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "libft_algo.h" + +void *ft_lsearch(const void *base, size_t *nelp, size_t width, + t_ftsearch_const *consts) +{ + void *found; + + if ((found = ft_lfind(base, nelp, width, consts)) != NULL) + return (found); + return (ft_memcpy((void*)base + (*nelp)++ * width, consts->key, width)); +} diff --git a/libft/src/algo/ft_mergesort.c b/libft/src/algo/ft_mergesort.c new file mode 100644 index 0000000..8556145 --- /dev/null +++ b/libft/src/algo/ft_mergesort.c @@ -0,0 +1,98 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* ft_mergesort.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2020/02/10 02:26:41 by cacharle #+# #+# */ +/* Updated: 2020/04/04 22:40:55 by charles ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "libft_algo.h" + +/* +** \brief Helper function to return in case of error +** \param left Left subarray +** \param right Right subarray +** \return -1 to indicate error +*/ + +static int st_mergesort_error(void *left, void *right) +{ + free(left); + free(right); + return (-1); +} + +/* +** \brief Merge 2 sorted arrays +** \param arrays Struct containing the arrays (base, left, right) +** \param nel Number of element in base +** \param compar Comparison function +*/ + +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 < mid && ri < nel - mid) + { + if (compar(arrays->left + li * width, arrays->right + ri * width) < 0) + ft_memcpy(arrays->base + bi * width, + arrays->left + li++ * width, width); + else + ft_memcpy(arrays->base + bi * width, + arrays->right + ri++ * width, width); + bi++; + } + 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); +} + +/* +** \brief Sort an array using the merge sort algorithm +** \param base Array to sort +** \param nel Number of element in the array +** \param width Size of each element +** \return 0 on success, -1 on error +*/ + +int ft_mergesort(void *base, size_t nel, size_t width, + int (*compar)(const void *, const void *)) +{ + size_t mid; + struct s_merge_sorted_arrays arrays; + + if (nel < 2) + return (0); + mid = nel / 2; + if ((arrays.left = malloc(mid * width)) == NULL) + return (-1); + 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 + 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/libft/src/algo/ft_qsort.c b/libft/src/algo/ft_qsort.c new file mode 100644 index 0000000..0c1c0f7 --- /dev/null +++ b/libft/src/algo/ft_qsort.c @@ -0,0 +1,97 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* ft_qsort.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2020/01/19 07:25:51 by cacharle #+# #+# */ +/* Updated: 2020/04/04 22:10:29 by charles ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "libft_algo.h" + +/* +** \brief Helper to create a new range +** \param lo Lower bound +** \param hi Higher bound +** \return Range struct (not allocated) +*/ + +static t_ftrange ft_range_new(int lo, int hi) +{ + t_ftrange range; + + range.lo = lo; + range.hi = hi; + return (range); +} + +/* +** \brief Array partitionning, +** takes a pivot and place every element lower than it before +** and every element greater after +** \param base Partitioned array +** \param range Lower and upper bound +** \param width Single element size +** \param compar Comparison function +*/ + +static int ft_qsort_partition(void *base, t_ftrange range, + size_t width, t_ftcompar_func compar) +{ + void *pivot; + int p; + int i; + + pivot = base + (range.hi * width); + p = range.lo; + i = range.lo - 1; + while (++i < range.hi) + { + if (compar(base + (i * width), pivot) < 0) + { + ft_memswap(base + (i * width), base + (p * width), width); + p++; + } + } + ft_memswap(pivot, base + (p * width), width); + return (p); +} + +/* +** \brief Qsort recursion function +** \param base Array to sort +** \param range Lower and upper bound which define the area to sort +** \param width Single element size +** \param compar Comparision function +*/ + +static void ft_qsort_rec(void *base, t_ftrange range, + size_t width, t_ftcompar_func compar) +{ + int pivot; + + if (range.lo >= range.hi) + return ; + pivot = ft_qsort_partition(base, range, width, compar); + ft_qsort_rec(base, ft_range_new(range.lo, pivot - 1), width, compar); + ft_qsort_rec(base, ft_range_new(pivot + 1, range.hi), width, compar); +} + +/* +** \brief Sort an array using the Quick sort algorithm +** \param base Array to sort +** \param nel Number of element in the array +** \param width Size of each element +** \param compar Comparision function +*/ + +void ft_qsort(void *base, size_t nel, size_t width, + t_ftcompar_func compar) +{ + if (width == 0 || nel < 2) + return ; + ft_qsort_rec(base, ft_range_new(0, nel - 1), width, compar); +} diff --git a/libft/src/algo/ft_reverse.c b/libft/src/algo/ft_reverse.c new file mode 100644 index 0000000..c617338 --- /dev/null +++ b/libft/src/algo/ft_reverse.c @@ -0,0 +1,34 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* ft_reverse.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2020/02/10 05:07:13 by cacharle #+# #+# */ +/* Updated: 2020/04/04 22:36:23 by charles ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "libft_algo.h" + +/* +** \brief Reverse an array +** \param base Array to reverse +** \param nel Number of element in the array +** \param width Size of each elements +*/ + +void ft_reverse(void *base, size_t nel, size_t width) +{ + size_t i; + + i = 0; + nel--; + while (i < nel) + { + ft_memswap(base + i * width, base + nel * width, width); + i++; + nel--; + } +} -- cgit