aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Makefile13
-rw-r--r--include/libft_bt.h37
-rw-r--r--include/libft_def.h3
-rw-r--r--include/libft_mem.h2
-rw-r--r--include/libft_rbt.h96
-rw-r--r--include/libft_str.h3
-rw-r--r--src/bt/ft_btdestroy.c13
-rw-r--r--src/bt/ft_btnew.c16
-rw-r--r--src/bt/ft_btsorted_insert.c38
-rw-r--r--src/bt/ft_btsorted_search.c35
-rw-r--r--src/mem/ft_memccpy.c58
-rw-r--r--src/mem/ft_memchr.c46
-rw-r--r--src/mem/ft_memcmp.c46
-rw-r--r--src/mem/ft_memcpy.c7
-rw-r--r--src/mem/ft_memmove.c13
-rw-r--r--src/mem/ft_memset.c34
-rw-r--r--src/rbt/ft_rbtinsert.c83
-rw-r--r--src/rbt/ft_rbtnew.c35
-rw-r--r--src/rbt/ft_rbtrotate_left.c38
-rw-r--r--src/rbt/ft_rbtrotate_right.c38
-rw-r--r--src/str/ft_split.c14
-rw-r--r--src/str/ft_strcat.c1
-rw-r--r--src/str/ft_strcmp.c7
-rw-r--r--src/str/ft_strdup.c7
-rw-r--r--src/str/ft_strlen.c78
-rw-r--r--src/str/ft_strncat.c18
-rw-r--r--src/str/ft_strncmp.c15
-rw-r--r--src/str/ft_strstr.c9
-rw-r--r--src/str/ft_strsub.c4
-rw-r--r--test/src/str/test_ft_strlen.c36
30 files changed, 697 insertions, 146 deletions
diff --git a/Makefile b/Makefile
index 7886427..14b556d 100644
--- a/Makefile
+++ b/Makefile
@@ -6,7 +6,7 @@
# By: cacharle <marvin@42.fr> +#+ +:+ +#+ #
# +#+#+#+#+#+ +#+ #
# Created: 2019/10/08 15:45:53 by cacharle #+# #+# #
-# Updated: 2020/04/01 22:00:44 by charles ### ########.fr #
+# Updated: 2020/05/09 12:28:11 by charles ### ########.fr #
# #
# **************************************************************************** #
@@ -27,14 +27,17 @@ DOC_DIR = doc
INCLUDE_DIR = include
-
CC = gcc
-OFLAG ?= -O1
+OFLAG ?= -O0
CCFLAGS = $(OFLAG) -I$(INCLUDE_DIR) -Wall -Wextra -Werror
ifeq ($(TRAVIS_COMPILER),gcc)
CCFLAGS += -Wno-unused-result
endif
+ifeq ($(TRAVIS_COMPILER),gcc)
+CCFLAGS += -Wno-unused-result
+endif
+
IGNORE_FILE = .libftignore
IGNORE_DEFAULT = ft_printf
@@ -95,3 +98,7 @@ doc:
doc_clean:
$(RM) -r $(DOC_DIR)
+# compatible with libft-unit-test
+so: all
+ gcc -o libft.so -shared -fPIC $(OBJ)
+
diff --git a/include/libft_bt.h b/include/libft_bt.h
index 6e2cc91..7bd7eb4 100644
--- a/include/libft_bt.h
+++ b/include/libft_bt.h
@@ -6,23 +6,44 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2020/02/07 21:26:34 by cacharle #+# #+# */
-/* Updated: 2020/02/07 21:34:52 by cacharle ### ########.fr */
+/* Updated: 2020/04/26 19:45:56 by charles ### ########.fr */
/* */
/* ************************************************************************** */
#ifndef LIBFT_BT_H
# define LIBFT_BT_H
+/*
+** \file libft_bt.h
+** \brief Binary tree
+*/
+
# include <stdlib.h>
-typedef struct s_ftbtree
+/*
+** \brief Binary tree struct
+** \param left Left node
+** \param right Right node
+** \param data Node data
+*/
+
+typedef struct s_ftbt
{
- void *data;
- struct s_ftbtree *left;
- struct s_ftbtree *right;
-} t_ftbtree;
+ struct s_ftbt *left;
+ struct s_ftbt *right;
+ void *data;
+} t_ftbt;
+
+t_ftbt *ft_btnew(void *data);
+void ft_btdestroy(t_ftbt *tree, void (*del)(void *data));
-t_ftbtree *ft_btnew(void *data);
-void ft_btdestroy(t_ftbtree *tree, void (*del)(void *data));
+t_ftbt *ft_btsorted_insert(
+ t_ftbt *tree,
+ void *data,
+ int (*cmp)(void*, void*));
+void *ft_btsorted_search(
+ t_ftbt *tree,
+ void *ref,
+ int (*cmp)(void*, void*));
#endif
diff --git a/include/libft_def.h b/include/libft_def.h
index 7406959..fa8d550 100644
--- a/include/libft_def.h
+++ b/include/libft_def.h
@@ -6,7 +6,7 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2020/01/31 10:36:56 by cacharle #+# #+# */
-/* Updated: 2020/04/04 21:40:37 by charles ### ########.fr */
+/* Updated: 2020/05/09 12:31:09 by charles ### ########.fr */
/* */
/* ************************************************************************** */
@@ -19,6 +19,7 @@
# define LIBFT_DEF_H
# include <stddef.h>
+# include <stdint.h>
# include <stdbool.h>
# define TRUE 1
diff --git a/include/libft_mem.h b/include/libft_mem.h
index 26b4ccd..f26180d 100644
--- a/include/libft_mem.h
+++ b/include/libft_mem.h
@@ -6,7 +6,7 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2020/01/31 10:35:57 by cacharle #+# #+# */
-/* Updated: 2020/02/28 12:17:48 by cacharle ### ########.fr */
+/* Updated: 2020/05/09 12:28:55 by charles ### ########.fr */
/* */
/* ************************************************************************** */
diff --git a/include/libft_rbt.h b/include/libft_rbt.h
new file mode 100644
index 0000000..57653cc
--- /dev/null
+++ b/include/libft_rbt.h
@@ -0,0 +1,96 @@
+/* ************************************************************************** */
+/* */
+/* ::: :::::::: */
+/* libft_rbt.h :+: :+: :+: */
+/* +:+ +:+ +:+ */
+/* By: charles <charles.cabergs@gmail.com> +#+ +:+ +#+ */
+/* +#+#+#+#+#+ +#+ */
+/* Created: 2020/04/26 16:09:51 by charles #+# #+# */
+/* Updated: 2020/04/26 20:25:36 by charles ### ########.fr */
+/* */
+/* ************************************************************************** */
+
+#ifndef LIBFT_RBT_H
+# define LIBFT_RBT_H
+
+/*
+** \file libft_rbt.h
+** \brief Red-black tree
+**
+** Rules: (from wikipedia)
+** 1. Each node is either red or black.
+** 2. The root is black. This rule is sometimes omitted. Since the root can
+** always be changed from red to black, but not necessarily vice versa,
+** this rule has little effect on analysis.
+** 3. All leaves (NULL) are black.
+** 4. If a node is red, then both its children are black.
+** 5. Every path from a given node to any of its descendant NULL nodes goes
+** through the same number of black nodes.
+**
+**
+** Unbalance case:
+**
+** 1. Node and parent are both red
+**
+** B1
+** \ left rot color swap
+** > R2 --> R2 --> B2
+** \ / \ / \
+** > R3 B1 R3 R1 R3
+**
+** 2. Node and parent are both red and uncle node is red
+**
+** B2 R2
+** / \ color swap / \
+** uncle> R1 R3 --> B1 B3
+** \ \
+** R4 R4
+*/
+
+# include <stdlib.h>
+
+/*
+** \brief Red-black tree color enum
+** \param FTRBT_COLOR_RED color red
+** \param FTRBT_COLOR_BLACK color black
+*/
+
+enum e_ftrbt_color
+{
+ FTRBT_COLOR_RED = 0,
+ FTRBT_COLOR_BLACK,
+};
+
+/*
+** \brief Red-black tree struct
+** \param left Left node
+** \param right Right node
+** \param data Pointer to data
+** \param parent Parent node
+** \param color Color of the node
+** \note The first 3 attricutes are the same
+** as t_ftbt (binary tree) struct
+** which means that we can use all functions
+** of binary tree on red-black tree.
+*/
+
+typedef struct s_ftrbt
+{
+ struct s_ftrbt *left;
+ struct s_ftrbt *right;
+ void *data;
+ struct s_ftrbt *parent;
+ enum e_ftrbt_color color;
+} t_ftrbt;
+
+t_ftrbt *ft_rbtnew(void *data, enum e_ftrbt_color color);
+void ft_rbtrotate_right(t_ftrbt **tree);
+void ft_rbtrotate_left(t_ftrbt **tree);
+
+t_ftrbt *ft_rbtinsert(
+ t_ftrbt *tree,
+ void *data,
+ int (*cmp)(void*, void*));
+
+
+#endif
diff --git a/include/libft_str.h b/include/libft_str.h
index 195e750..07a5fe0 100644
--- a/include/libft_str.h
+++ b/include/libft_str.h
@@ -6,7 +6,7 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2020/01/31 10:39:22 by cacharle #+# #+# */
-/* Updated: 2020/04/05 13:52:10 by charles ### ########.fr */
+/* Updated: 2020/05/09 12:29:21 by charles ### ########.fr */
/* */
/* ************************************************************************** */
@@ -16,6 +16,7 @@
# include <stddef.h>
# include <stdbool.h>
# include "libft_ctype.h"
+# include "libft_mem.h"
# include "libft_util.h"
typedef enum
diff --git a/src/bt/ft_btdestroy.c b/src/bt/ft_btdestroy.c
index c802db0..d8746ef 100644
--- a/src/bt/ft_btdestroy.c
+++ b/src/bt/ft_btdestroy.c
@@ -6,18 +6,25 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2020/02/07 21:30:53 by cacharle #+# #+# */
-/* Updated: 2020/02/07 21:35:19 by cacharle ### ########.fr */
+/* Updated: 2020/04/26 19:47:45 by charles ### ########.fr */
/* */
/* ************************************************************************** */
#include "libft_bt.h"
-void ft_btdestroy(t_ftbtree *tree, void (*del)(void *data))
+/*
+** \brief Destroy a binary tree
+** \param tree Binary tree to destroy
+** \param del Delete function applied to each node data
+*/
+
+void ft_btdestroy(t_ftbt *tree, void (*del)(void *data))
{
if (tree == NULL)
return ;
ft_btdestroy(tree->left, del);
ft_btdestroy(tree->right, del);
- (*del)(tree->data);
+ if (del != NULL)
+ del(tree->data);
free(tree);
}
diff --git a/src/bt/ft_btnew.c b/src/bt/ft_btnew.c
index 973e1a4..09cfa12 100644
--- a/src/bt/ft_btnew.c
+++ b/src/bt/ft_btnew.c
@@ -6,20 +6,26 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2020/02/07 21:33:16 by cacharle #+# #+# */
-/* Updated: 2020/02/07 21:34:35 by cacharle ### ########.fr */
+/* Updated: 2020/04/26 19:46:57 by charles ### ########.fr */
/* */
/* ************************************************************************** */
#include "libft_bt.h"
-t_ftbtree *ft_btnew(void *data)
+/*
+** \brief Create a new binary tree
+** \param data Node's data
+** \return Allocated node with left and right set to NULL, NULL on error
+*/
+
+t_ftbt *ft_btnew(void *data)
{
- t_ftbtree *tree;
+ t_ftbt *tree;
- if ((tree = (t_ftbtree*)malloc(sizeof(t_ftbtree))) == NULL)
+ if ((tree = (t_ftbt*)malloc(sizeof(t_ftbt))) == NULL)
return (NULL);
- tree->data = data;
tree->left = NULL;
tree->right = NULL;
+ tree->data = data;
return (tree);
}
diff --git a/src/bt/ft_btsorted_insert.c b/src/bt/ft_btsorted_insert.c
new file mode 100644
index 0000000..12c0cde
--- /dev/null
+++ b/src/bt/ft_btsorted_insert.c
@@ -0,0 +1,38 @@
+/* ************************************************************************** */
+/* */
+/* ::: :::::::: */
+/* ft_btsorted_insert.c :+: :+: :+: */
+/* +:+ +:+ +:+ */
+/* By: charles <charles.cabergs@gmail.com> +#+ +:+ +#+ */
+/* +#+#+#+#+#+ +#+ */
+/* Created: 2020/04/26 19:10:36 by charles #+# #+# */
+/* Updated: 2020/04/26 19:19:24 by charles ### ########.fr */
+/* */
+/* ************************************************************************** */
+
+#include "libft_bt.h"
+
+/*
+** \brief Insert a data in a binary search tree so that it stays sorted
+** \param tree Tree where data is inserted
+** \param data Data to insert
+** \param cmp Comparison function
+** \return The new root or NULL if a new node couldn't be allocated
+*/
+
+t_ftbt *ft_btsorted_insert(t_ftbt *tree, void *data, int (*cmp)(void*, void*))
+{
+ if (tree == NULL)
+ return (ft_btnew(data));
+ if (cmp(data, tree->data) < 0)
+ {
+ if (ft_btsorted_insert(tree->left, data, cmp) == NULL)
+ return (NULL);
+ }
+ else
+ {
+ if (ft_btsorted_insert(tree->right, data, cmp) == NULL)
+ return (NULL);
+ }
+ return (tree);
+}
diff --git a/src/bt/ft_btsorted_search.c b/src/bt/ft_btsorted_search.c
new file mode 100644
index 0000000..00629d0
--- /dev/null
+++ b/src/bt/ft_btsorted_search.c
@@ -0,0 +1,35 @@
+/* ************************************************************************** */
+/* */
+/* ::: :::::::: */
+/* ft_btsorted_search.c :+: :+: :+: */
+/* +:+ +:+ +:+ */
+/* By: charles <charles.cabergs@gmail.com> +#+ +:+ +#+ */
+/* +#+#+#+#+#+ +#+ */
+/* Created: 2020/04/26 19:31:42 by charles #+# #+# */
+/* Updated: 2020/04/26 19:35:53 by charles ### ########.fr */
+/* */
+/* ************************************************************************** */
+
+#include "libft_bt.h"
+
+/*
+** \brief Search a element in a sorted binary tree
+** \param tree Searched tree
+** \param ref First argument of comparison function
+** \param cmp Comparison function
+** \return Node data if found, NULL otherwise
+*/
+
+void *ft_btsorted_search(t_ftbt *tree, void *ref, int (*cmp)(void*, void*))
+{
+ int res;
+
+ if (tree == NULL)
+ return (NULL);
+ if ((res = cmp(ref, tree->data)) == 0)
+ return (tree->data);
+ if (res < 0)
+ return (ft_btsorted_search(tree->left, ref, cmp));
+ else
+ return (ft_btsorted_search(tree->right, ref, cmp));
+}
diff --git a/src/mem/ft_memccpy.c b/src/mem/ft_memccpy.c
index 8ce656a..2f6525a 100644
--- a/src/mem/ft_memccpy.c
+++ b/src/mem/ft_memccpy.c
@@ -6,26 +6,62 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2019/10/07 10:01:53 by cacharle #+# #+# */
-/* Updated: 2020/01/17 10:54:03 by cacharle ### ########.fr */
+/* Updated: 2020/04/01 21:50:29 by charles ### ########.fr */
/* */
/* ************************************************************************** */
#include "libft.h"
+#define HIMAGIC 0x8080808080808080L
+#define LOMAGIC 0x0101010101010101L
+
void *ft_memccpy(void *dest, const void *src, int c, size_t n)
{
- size_t i;
- t_ftbyte *cast_dest;
- t_ftbyte *cast_src;
+ uint64_t buf;
+ uint64_t lw;
- cast_dest = (t_ftbyte*)dest;
- cast_src = (t_ftbyte*)src;
- i = -1;
- while (++i < n)
+ if (dest == src)
+ return (dest);
+ c = (uint8_t)c;
+ while ((n & 0b111) != 0)
+ {
+ *(uint8_t*)dest = *(uint8_t*)src;
+ if (*(uint8_t*)dest == c)
+ return ((uint8_t*)dest + 1);
+ src++;
+ dest++;
+ n--;
+ }
+ buf = (uint64_t)c | (uint64_t)c << 8 | (uint64_t)c << 16
+ | (uint64_t)c << 24 | (uint64_t)c << 32 | (uint64_t)c << 40
+ | (uint64_t)c << 48 | (uint64_t)c << 56;
+ while (n > 0)
{
- cast_dest[i] = cast_src[i];
- if (cast_dest[i] == (unsigned char)c)
- return (cast_dest + i + 1);
+ lw = *(uint64_t*)src ^ buf;
+ if ((lw - LOMAGIC) & ~lw & HIMAGIC)
+ {
+ if ((((uint8_t*)dest)[0] = ((uint8_t*)src)[0]) == (uint8_t)c)
+ return ((uint8_t*)dest + 1);
+ if ((((uint8_t*)dest)[1] = ((uint8_t*)src)[1]) == (uint8_t)c)
+ return ((uint8_t*)dest + 2);
+ if ((((uint8_t*)dest)[2] = ((uint8_t*)src)[2]) == (uint8_t)c)
+ return ((uint8_t*)dest + 3);
+ if ((((uint8_t*)dest)[3] = ((uint8_t*)src)[3]) == (uint8_t)c)
+ return ((uint8_t*)dest + 4);
+ if ((((uint8_t*)dest)[4] = ((uint8_t*)src)[4]) == (uint8_t)c)
+ return ((uint8_t*)dest + 5);
+ if ((((uint8_t*)dest)[5] = ((uint8_t*)src)[5]) == (uint8_t)c)
+ return ((uint8_t*)dest + 6);
+ if ((((uint8_t*)dest)[6] = ((uint8_t*)src)[6]) == (uint8_t)c)
+ return ((uint8_t*)dest + 7);
+ if ((((uint8_t*)dest)[7] = ((uint8_t*)src)[7]) == (uint8_t)c)
+ return ((uint8_t*)dest + 8);
+ }
+ else
+ *(uint64_t*)dest = *(uint64_t*)src;
+ n -= 8;
+ dest += 8;
+ src += 8;
}
return (NULL);
}
diff --git a/src/mem/ft_memchr.c b/src/mem/ft_memchr.c
index 4fd8689..e0266af 100644
--- a/src/mem/ft_memchr.c
+++ b/src/mem/ft_memchr.c
@@ -6,21 +6,51 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2019/10/07 09:55:31 by cacharle #+# #+# */
-/* Updated: 2020/02/13 04:28:00 by cacharle ### ########.fr */
+/* Updated: 2020/04/01 21:50:49 by charles ### ########.fr */
/* */
/* ************************************************************************** */
#include "libft.h"
+/*
+** Determining if a long word contain byte n
+**
+** xor all bytes with n, then check for zero byte like in ft_strlen.
+*/
+
+#define HIMAGIC 0x8080808080808080L
+#define LOMAGIC 0x0101010101010101L
+
void *ft_memchr(const void *s, int c, size_t n)
{
- size_t i;
- t_ftbyte *cast_s;
+ uint64_t buf;
+ uint64_t lw;
- cast_s = (t_ftbyte*)s;
- i = -1;
- while (++i < n)
- if (cast_s[i] == (unsigned char)c)
- return (cast_s + i);
+ c = (uint8_t)c;
+ while (((uint64_t)s & 0b111) != 0)
+ {
+ n--;
+ if (*(uint8_t*)s == (uint8_t)c)
+ return ((uint8_t*)s);
+ s++;
+ }
+ buf = (uint64_t)c | (uint64_t)c << 8 | (uint64_t)c << 16
+ | (uint64_t)c << 24 | (uint64_t)c << 32 | (uint64_t)c << 40
+ | (uint64_t)c << 48 | (uint64_t)c << 56;
+ while (n >= 8)
+ {
+ lw = *(uint64_t*)s ^ buf;
+ if ((lw - LOMAGIC) & ~lw & HIMAGIC)
+ break ;
+ n -= 8;
+ s += 8;
+ }
+ while (n > 0)
+ {
+ if (*(uint8_t*)s == (uint8_t)c)
+ return ((uint8_t*)s);
+ n--;
+ s++;
+ }
return (NULL);
}
diff --git a/src/mem/ft_memcmp.c b/src/mem/ft_memcmp.c
index 233d796..c61ca9a 100644
--- a/src/mem/ft_memcmp.c
+++ b/src/mem/ft_memcmp.c
@@ -11,20 +11,42 @@
/* ************************************************************************** */
#include "libft.h"
+#include "libft_mem.h"
int ft_memcmp(const void *s1, const void *s2, size_t n)
{
- size_t i;
- t_ftbyte *cast_s1;
- t_ftbyte *cast_s2;
-
- cast_s1 = (t_ftbyte*)s1;
- cast_s2 = (t_ftbyte*)s2;
- if (n == 0)
- return (0);
- i = -1;
- while (++i < n)
- if (cast_s1[i] != cast_s2[i])
- return (cast_s1[i] - cast_s2[i]);
+ while ((n & 0b111) != 0)
+ {
+ n--;
+ if (*(uint8_t*)s1 != *(uint8_t*)s2)
+ return (*(uint8_t*)s1 - *(uint8_t*)s2);
+ s1++;
+ s2++;
+ }
+ while (n > 0)
+ {
+ if (*(uint64_t*)s1 != *(uint64_t*)s2)
+ {
+ if (((uint8_t*)s1)[0] != ((uint8_t*)s2)[0])
+ return (((uint8_t*)s1)[0] - ((uint8_t*)s2)[0]);
+ if (((uint8_t*)s1)[1] != ((uint8_t*)s2)[1])
+ return (((uint8_t*)s1)[1] - ((uint8_t*)s2)[1]);
+ if (((uint8_t*)s1)[2] != ((uint8_t*)s2)[2])
+ return (((uint8_t*)s1)[2] - ((uint8_t*)s2)[2]);
+ if (((uint8_t*)s1)[3] != ((uint8_t*)s2)[3])
+ return (((uint8_t*)s1)[3] - ((uint8_t*)s2)[3]);
+ if (((uint8_t*)s1)[4] != ((uint8_t*)s2)[4])
+ return (((uint8_t*)s1)[4] - ((uint8_t*)s2)[4]);
+ if (((uint8_t*)s1)[5] != ((uint8_t*)s2)[5])
+ return (((uint8_t*)s1)[5] - ((uint8_t*)s2)[5]);
+ if (((uint8_t*)s1)[6] != ((uint8_t*)s2)[6])
+ return (((uint8_t*)s1)[6] - ((uint8_t*)s2)[6]);
+ if (((uint8_t*)s1)[7] != ((uint8_t*)s2)[7])
+ return (((uint8_t*)s1)[7] - ((uint8_t*)s2)[7]);
+ }
+ n -= 8;
+ s1 += 8;
+ s2 += 8;
+ }
return (0);
}
diff --git a/src/mem/ft_memcpy.c b/src/mem/ft_memcpy.c
index d0ef008..1f84bfd 100644
--- a/src/mem/ft_memcpy.c
+++ b/src/mem/ft_memcpy.c
@@ -11,18 +11,19 @@
/* ************************************************************************** */
#include "libft.h"
+#include "libft_mem.h"
void *ft_memcpy(void *dest, const void *src, size_t n)
{
- long int *long_dest;
- const long int *long_src;
+ uint64_t *long_dest;
+ const uint64_t *long_src;
if (dest == src)
return (dest);
while (n % 8 > 0)
{
n--;
- ((t_ftbyte*)dest)[n] = ((t_ftbyte*)src)[n];
+ ((uint8_t*)dest)[n] = ((uint8_t*)src)[n];
}
long_dest = dest;
long_src = src;
diff --git a/src/mem/ft_memmove.c b/src/mem/ft_memmove.c
index 2f794fd..142b761 100644
--- a/src/mem/ft_memmove.c
+++ b/src/mem/ft_memmove.c
@@ -11,11 +11,12 @@
/* ************************************************************************** */
#include "libft.h"
+#include "libft_mem.h"
void *ft_memmove(void *dst, const void *src, size_t len)
{
- long int *long_dst;
- const long int *long_src;
+ uint64_t *dst64;
+ const uint64_t *src64;
void *dst_copy;
if (dst >= src)
@@ -24,12 +25,12 @@ void *ft_memmove(void *dst, const void *src, size_t len)
while (len % 8 > 0)
{
len--;
- *(t_ftbyte*)dst++ = *(t_ftbyte*)src++;
+ *(uint8_t*)dst++ = *(uint8_t*)src++;
}
- long_dst = dst;
- long_src = src;
+ dst64 = dst;
+ src64 = src;
len /= 8;
while (len-- > 0)
- *long_dst++ = *long_src++;
+ *dst64++ = *src64++;
return (dst_copy);
}
diff --git a/src/mem/ft_memset.c b/src/mem/ft_memset.c
index 89f53ff..9005947 100644
--- a/src/mem/ft_memset.c
+++ b/src/mem/ft_memset.c
@@ -6,26 +6,34 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2019/10/07 10:01:23 by cacharle #+# #+# */
-/* Updated: 2020/01/17 10:39:10 by cacharle ### ########.fr */
+/* Updated: 2020/04/01 21:49:42 by charles ### ########.fr */
/* */
/* ************************************************************************** */
#include "libft.h"
+#include "libft_mem.h"
void *ft_memset(void *s, int c, size_t n)
{
- long int buf;
- long int *long_s;
+ uint64_t buf;
+ void *cpy;
- c = (unsigned char)c;
- while (n % 8 > 0)
- *((t_ftbyte*)s + --n) = c;
- buf = (long int)c | (long int)c << 8 | (long int)c << 16
- | (long int)c << 24 | (long int)c << 32 | (long int)c << 40
- | (long int)c << 48 | (long int)c << 56;
- n /= 8;
- long_s = s;
+ cpy = s;
+ c = (uint8_t)c;
+ buf = (uint64_t)c | (uint64_t)c << 8 | (uint64_t)c << 16
+ | (uint64_t)c << 24 | (uint64_t)c << 32 | (uint64_t)c << 40
+ | (uint64_t)c << 48 | (uint64_t)c << 56;
+ while (n > 8)
+ {
+ *(uint64_t*)s = buf;
+ n -= 8;
+ s += 8;
+ }
while (n > 0)
- long_s[--n] = buf;
- return (s);
+ {
+ *(uint8_t*)s = c;
+ s++;
+ n--;
+ }
+ return (cpy);
}
diff --git a/src/rbt/ft_rbtinsert.c b/src/rbt/ft_rbtinsert.c
new file mode 100644
index 0000000..ce86777
--- /dev/null
+++ b/src/rbt/ft_rbtinsert.c
@@ -0,0 +1,83 @@
+/* ************************************************************************** */
+/* */
+/* ::: :::::::: */
+/* ft_rbtinsert.c :+: :+: :+: */
+/* +:+ +:+ +:+ */
+/* By: charles <charles.cabergs@gmail.com> +#+ +:+ +#+ */
+/* +#+#+#+#+#+ +#+ */
+/* Created: 2020/04/26 19:10:36 by charles #+# #+# */
+/* Updated: 2020/04/26 21:02:52 by charles ### ########.fr */
+/* */
+/* ************************************************************************** */
+
+#include "libft_rbt.h"
+
+static void st_insert_node(
+ t_ftrbt **root,
+ t_ftrbt *node,
+ int (*cmp)(void*, void*))
+{
+ if (*root == NULL)
+ {
+ *root = node;
+ return ;
+ }
+ if (cmp(node->data, (*root)->data) < 0)
+ st_insert_node(&(*root)->left, node->data, cmp);
+ else
+ st_insert_node(&(*root)->left, node->data, cmp);
+}
+
+static void st_repare_tree(t_ftrbt *node)
+{
+ (void)node;
+ /* t_ftrbt *parent; */
+ /* */
+ /* parent = node->parent; */
+ /* if (parent == NULL) */
+ /* node->color = FTRBT_COLOR_BLACK; */
+ /* else if (parent->color == FTRBT_COLOR_BLACK) */
+ /* return ; */
+ /* else if (parent->color == FTRBT_COLOR_RED && uncle(node)->color == FTRBT_COLOR_RED) */
+ /* { */
+ /* parent->color == FTRBT_COLOR_BLACK; */
+ /* uncle->color = FTRBT_COLOR_BLACK; */
+ /* parent->parent->color = FTRBT_COLOR_RED; */
+ /* st_repare_tree(parent->parent); */
+ /* } */
+ /* else if (parent->color == FTRBT_COLOR_RED && uncle(node)->color == FTRBT_COLOR_BLACK) */
+ /* { */
+ /* if (node == parent->right && parent == parent->parent->left) */
+ /* { */
+ /* ft_rbtrotate_left(parent); */
+ /* node = node->left; */
+ /* } */
+ /* else if (node == parent->left && parent == parent->parent->right) */
+ /* { */
+ /* ft_rbtrotate_right(parent); */
+ /* node = node->right; */
+ /* } */
+ /* if (node == parent->left) */
+ /* ft_rbtrotate_right(parent); */
+ /* else */
+ /* ft_rbtrotate_left(parent); */
+ /* parent->color = FTRBT_COLOR_BLACK; */
+ /* parent->parent->color = FTRBT_COLOR_RED; */
+ /* } */
+}
+
+t_ftrbt *ft_rbtinsert(
+ t_ftrbt *tree,
+ void *data,
+ int (*cmp)(void*, void*))
+{
+ t_ftrbt *node;
+
+ if ((node = ft_rbtnew(data, FTRBT_COLOR_RED)) == NULL)
+ return (NULL);
+ st_insert_node(&tree, node, cmp);
+ st_repare_tree(node);
+ while (node->parent != NULL)
+ node = node->parent;
+ return node;
+}
diff --git a/src/rbt/ft_rbtnew.c b/src/rbt/ft_rbtnew.c
new file mode 100644
index 0000000..bda7d55
--- /dev/null
+++ b/src/rbt/ft_rbtnew.c
@@ -0,0 +1,35 @@
+