aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Makefile6
-rw-r--r--ft_compar_int.c18
-rw-r--r--ft_is_set.c31
-rw-r--r--ft_memswap.c29
-rw-r--r--ft_qsort.c64
-rw-r--r--libft.h23
6 files changed, 168 insertions, 3 deletions
diff --git a/Makefile b/Makefile
index 392b40c..eeba965 100644
--- a/Makefile
+++ b/Makefile
@@ -6,13 +6,15 @@
# By: cacharle <marvin@42.fr> +#+ +:+ +#+ #
# +#+#+#+#+#+ +#+ #
# Created: 2019/10/08 15:45:53 by cacharle #+# #+# #
-# Updated: 2020/01/16 07:45:42 by cacharle ### ########.fr #
+# Updated: 2020/02/02 22:09:07 by cacharle ### ########.fr #
# #
# **************************************************************************** #
LIB = ar rcs
RM = rm -f
+INCLUDE_DIR = include
+
CC = gcc
CCFLAGS = -Wall -Wextra -Werror
@@ -25,7 +27,7 @@ SRC = ft_atoi.c ft_bzero.c ft_isalnum.c ft_isalpha.c ft_isascii.c ft_isdigit.c f
ft_striteri.c ft_strjoin.c ft_strlcat.c ft_strlen.c ft_strmap.c ft_strmapi.c \
ft_strncat.c ft_strncmp.c ft_strncpy.c ft_strnequ.c ft_strnew.c ft_strnstr.c \
ft_strrchr.c ft_split.c ft_strstr.c ft_substr.c ft_strtrim.c ft_tolower.c \
- ft_toupper.c ft_strlcpy.c ft_calloc.c ft_strcount.c
+ ft_toupper.c ft_strlcpy.c ft_calloc.c ft_strcount.c ft_memswap.c ft_qsort.c
OBJ = $(SRC:.c=.o)
INCLUDE = libft.h
diff --git a/ft_compar_int.c b/ft_compar_int.c
new file mode 100644
index 0000000..848dc71
--- /dev/null
+++ b/ft_compar_int.c
@@ -0,0 +1,18 @@
+/* ************************************************************************** */
+/* */
+/* ::: :::::::: */
+/* ft_compar_int.c :+: :+: :+: */
+/* +:+ +:+ +:+ */
+/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
+/* +#+#+#+#+#+ +#+ */
+/* Created: 2020/01/19 08:24:43 by cacharle #+# #+# */
+/* Updated: 2020/01/19 08:27:38 by cacharle ### ########.fr */
+/* */
+/* ************************************************************************** */
+
+#include "libft.h"
+
+int ft_compar_int(const void *a, const void *b)
+{
+ return (*(int*)a - *(int*)b);
+}
diff --git a/ft_is_set.c b/ft_is_set.c
new file mode 100644
index 0000000..8e45b49
--- /dev/null
+++ b/ft_is_set.c
@@ -0,0 +1,31 @@
+/* ************************************************************************** */
+/* */
+/* ::: :::::::: */
+/* ft_is_set.c :+: :+: :+: */
+/* +:+ +:+ +:+ */
+/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
+/* +#+#+#+#+#+ +#+ */
+/* Created: 2020/01/19 07:17:15 by cacharle #+# #+# */
+/* Updated: 2020/01/19 08:21:12 by cacharle ### ########.fr */
+/* */
+/* ************************************************************************** */
+
+#include "libft.h"
+
+t_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/ft_memswap.c b/ft_memswap.c
new file mode 100644
index 0000000..4abaa83
--- /dev/null
+++ b/ft_memswap.c
@@ -0,0 +1,29 @@
+/* ************************************************************************** */
+/* */
+/* ::: :::::::: */
+/* ft_memswap.c :+: :+: :+: */
+/* +:+ +:+ +:+ */
+/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
+/* +#+#+#+#+#+ +#+ */
+/* Created: 2020/01/19 07:56:43 by cacharle #+# #+# */
+/* Updated: 2020/01/19 08:22:17 by cacharle ### ########.fr */
+/* */
+/* ************************************************************************** */
+
+#include "libft.h"
+
+void ft_memswap(void *a, void *b, size_t size)
+{
+ t_byte tmp;
+ t_byte *cast_a;
+ t_byte *cast_b;
+
+ cast_a = (t_byte*)a;
+ cast_b = (t_byte*)b;
+ while (size-- > 0)
+ {
+ tmp = cast_a[size];
+ cast_a[size] = cast_b[size];
+ cast_b[size] = tmp;
+ }
+}
diff --git a/ft_qsort.c b/ft_qsort.c
new file mode 100644
index 0000000..8c125a1
--- /dev/null
+++ b/ft_qsort.c
@@ -0,0 +1,64 @@
+/* ************************************************************************** */
+/* */
+/* ::: :::::::: */
+/* ft_qsort.c :+: :+: :+: */
+/* +:+ +:+ +:+ */
+/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
+/* +#+#+#+#+#+ +#+ */
+/* Created: 2020/01/19 07:25:51 by cacharle #+# #+# */
+/* Updated: 2020/01/19 08:28:32 by cacharle ### ########.fr */
+/* */
+/* ************************************************************************** */
+
+#include "libft.h"
+
+static t_ftrange ft_range_new(int lo, int hi)
+{
+ t_ftrange range;
+
+ range.lo = lo;
+ range.hi = hi;
+ return (range);
+}
+
+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);
+}
+
+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);
+}
+
+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.h b/libft.h
index 6e767fd..f84c16e 100644
--- a/libft.h
+++ b/libft.h
@@ -6,7 +6,7 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2019/10/07 09:45:02 by cacharle #+# #+# */
-/* Updated: 2020/01/15 14:46:50 by cacharle ### ########.fr */
+/* Updated: 2020/02/02 22:09:47 by cacharle ### ########.fr */
/* */
/* ************************************************************************** */
@@ -19,6 +19,7 @@
# define FALSE 0
typedef unsigned char t_byte;
+typedef int t_bool;
typedef struct s_list
{
@@ -33,6 +34,12 @@ void *ft_memccpy(void *dest, const void *src, int c, size_t n);
void *ft_memmove(void *dst, const void *src, size_t len);
void *ft_memchr(const void *s, int c, size_t n);
int ft_memcmp(const void *s1, const void *s2, size_t n);
+void ft_memswap(void *a, void *b, size_t size);
+
+/*
+** str
+*/
+
size_t ft_strlen(const char *s);
char *ft_strdup(const char *s);
char *ft_strcpy(char *dest, const char *src);
@@ -98,4 +105,18 @@ void ft_lstiter(t_list *lst, void (*f)(void *));
t_list *ft_lstmap(t_list *lst, void *(*f)(void *),
void (*del)(void *));
+typedef struct
+{
+ int lo;
+ int hi;
+} t_ftrange;
+
+typedef int (*t_ftcompar_func)(const void*, const void*);
+
+t_bool ft_is_set(void *base, size_t nel, size_t width,
+ t_ftcompar_func compar);
+void ft_qsort(void *base, size_t nel, size_t width,
+ t_ftcompar_func compar);
+int ft_compar_int(const void *a, const void *b);
+
#endif
generated by cgit (git 2.34.1) at 2026-05-16 19:16:11 +0000