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/lst/ft_lstbsearch.c | 65 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 65 insertions(+) create mode 100644 libft/src/lst/ft_lstbsearch.c (limited to 'libft/src/lst/ft_lstbsearch.c') diff --git a/libft/src/lst/ft_lstbsearch.c b/libft/src/lst/ft_lstbsearch.c new file mode 100644 index 0000000..0c48eb0 --- /dev/null +++ b/libft/src/lst/ft_lstbsearch.c @@ -0,0 +1,65 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* ft_lstbsearch.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2020/01/30 09:17:51 by cacharle #+# #+# */ +/* Updated: 2020/02/28 12:12:12 by cacharle ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "libft.h" +#include "libft_lst.h" + +static t_ftlst *st_lstmiddle(t_ftlst *lst, t_ftlst *last) +{ + t_ftlst *slow; + t_ftlst *fast; + + if (lst == NULL) + return (NULL); + slow = lst; + fast = lst; + while (fast != last) + { + fast = fast->next; + if (fast == last) + break ; + slow = slow->next; + fast = fast->next; + } + return (slow); +} + +static t_ftlst *st_lstbsearch_rec(t_ftlst *lst, t_ftlst *last, + t_ftcompar_func cmp, const void *ref) +{ + int res; + t_ftlst *mid; + + if (lst == NULL) + return (NULL); + mid = st_lstmiddle(lst, last); + if (mid == NULL) + return (NULL); + if (mid->next == NULL) + { + if (cmp(ref, mid->data) == 0) + return (mid); + return (NULL); + } + res = cmp(ref, mid->next->data); + if (res < 0) + return (st_lstbsearch_rec(lst, mid, cmp, ref)); + else if (res > 0) + return (st_lstbsearch_rec(mid->next->next, NULL, cmp, ref)); + return (mid->next); +} + +t_ftlst *ft_lstbsearch(t_ftlst *lst, t_ftcompar_func cmp, + const void *ref) +{ + return (st_lstbsearch_rec(lst, NULL, cmp, ref)); +} -- cgit