aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-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
23 files changed, 521 insertions, 132 deletions
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 @@
+/* ************************************************************************** */
+/* */
+/* ::: :::::::: */
+/* ft_rbtnew.c :+: :+: :+: */
+/* +:+ +:+ +:+ */
+/* By: charles <charles.cabergs@gmail.com> +#+ +:+ +#+ */
+/* +#+#+#+#+#+ +#+ */
+/* Created: 2020/04/26 20:22:07 by charles #+# #+# */
+/* Updated: 2020/04/26 20:24:44 by charles ### ########.fr */
+/* */
+/* ************************************************************************** */
+
+#include "libft_rbt.h"
+
+/*
+** \brief Create a new red-black tree
+** \param data Node's data
+** \param color Node's color
+** \return The created node with left, right and parent pointer to NULL
+** or NULL on error
+*/
+
+t_ftrbt *ft_rbtnew(void *data, enum e_ftrbt_color color)
+{
+ t_ftrbt *tree;
+
+ if ((tree = (t_ftrbt*)malloc(sizeof(t_ftrbt))) == NULL)
+ return (NULL);
+ tree->left = NULL;
+ tree->right = NULL;
+ tree->data = data;
+ tree->parent = NULL;
+ tree->color = color;
+ return (tree);
+}
diff --git a/src/rbt/ft_rbtrotate_left.c b/src/rbt/ft_rbtrotate_left.c
new file mode 100644
index 0000000..7cff65d
--- /dev/null
+++ b/src/rbt/ft_rbtrotate_left.c
@@ -0,0 +1,38 @@
+/* ************************************************************************** */
+/* */
+/* ::: :::::::: */
+/* ft_rbtrotate_left.c :+: :+: :+: */
+/* +:+ +:+ +:+ */
+/* By: charles <charles.cabergs@gmail.com> +#+ +:+ +#+ */
+/* +#+#+#+#+#+ +#+ */
+/* Created: 2020/04/26 18:03:35 by charles #+# #+# */
+/* Updated: 2020/04/26 20:27:44 by charles ### ########.fr */
+/* */
+/* ************************************************************************** */
+
+#include "libft_rbt.h"
+
+/*
+** \brief Rotate a red-black tree to the left
+** \param tree Pointer to Pointer to a red-black tree
+**
+** 5 10
+** / \ / \
+** 4 10 --> 5 11
+** / \ / \
+** 6 11 4 6
+*/
+
+void ft_rbtrotate_left(t_ftrbt **tree)
+{
+ t_ftrbt *new_root;
+ t_ftrbt *tmp;
+
+ if (tree == NULL || *tree == NULL || (*tree)->right == NULL)
+ return ;
+ new_root = (*tree)->right;
+ tmp = new_root->left;
+ new_root->left = *tree;
+ (*tree)->right = tmp;
+ *tree = new_root;
+}
diff --git a/src/rbt/ft_rbtrotate_right.c b/src/rbt/ft_rbtrotate_right.c
new file mode 100644
index 0000000..46d72e2
--- /dev/null
+++ b/src/rbt/ft_rbtrotate_right.c
@@ -0,0 +1,38 @@
+/* ************************************************************************** */
+/* */
+/* ::: :::::::: */
+/* ft_rbtrotate_right.c :+: :+: :+: */
+/* +:+ +:+ +:+ */
+/* By: charles <charles.cabergs@gmail.com> +#+ +:+ +#+ */
+/* +#+#+#+#+#+ +#+ */
+/* Created: 2020/04/26 18:10:57 by charles #+# #+# */
+/* Updated: 2020/04/26 20:27:53 by charles ### ########.fr */
+/* */
+/* ************************************************************************** */
+
+#include "libft_rbt.h"
+
+/*
+** \brief Rotate a red-black tree to the right
+** \param tree Pointer to Pointer to a red-black tree
+**
+** 10 5
+** / \ / \
+** 5 11 --> 4 10
+** / \ / \
+** 4 6 6 11
+*/
+
+void ft_rbtrotate_right(t_ftrbt **tree)
+{
+ t_ftrbt *new_root;
+ t_ftrbt *tmp;
+
+ if (tree == NULL || *tree == NULL || (*tree)->left == NULL)
+ return ;
+ new_root = (*tree)->left;
+ tmp = new_root->right;
+ new_root->right = *tree;
+ (*tree)->left = tmp;
+ *tree = new_root;
+}
diff --git a/src/str/ft_split.c b/src/str/ft_split.c
index 6fb5964..0cb08e4 100644
--- a/src/str/ft_split.c
+++ b/src/str/ft_split.c
@@ -6,7 +6,7 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2019/10/17 08:29:02 by cacharle #+# #+# */
-/* Updated: 2019/11/20 04:08:27 by cacharle ### ########.fr */
+/* Updated: 2020/05/08 13:39:31 by charles ### ########.fr */
/* */
/* ************************************************************************** */
@@ -33,16 +33,6 @@ static size_t count_segment(char const *s, char c)
return (counter);
}
-static void *destroy_strs(char **strs)
-{
- if (strs == NULL)
- return (NULL);
- while (*strs != NULL)
- free(*strs++);
- free(strs);
- return (NULL);
-}
-
char **ft_split(char const *s, char c)
{
char **strs;
@@ -65,7 +55,7 @@ char **ft_split(char const *s, char c)
while (s[j + i] && s[j + i] != c)
i++;
if ((strs[tab_counter++] = ft_strndup(&s[j], i)) == NULL)
- return (destroy_strs(strs));
+ return (ft_split_destroy(strs));
j += i - 1;
}
strs[tab_counter] = NULL;
diff --git a/src/str/ft_strcat.c b/src/str/ft_strcat.c
index d5bc7e0..faed515 100644
--- a/src/str/ft_strcat.c
+++ b/src/str/ft_strcat.c
@@ -11,6 +11,7 @@
/* ************************************************************************** */
#include "libft.h"
+#include "libft_mem.h"
char *ft_strcat(char *dest, const char *src)
{
diff --git a/src/str/ft_strcmp.c b/src/str/ft_strcmp.c
index aced711..25d2972 100644
--- a/src/str/ft_strcmp.c
+++ b/src/str/ft_strcmp.c
@@ -14,10 +14,5 @@
int ft_strcmp(const char *s1, const char *s2)
{
- while (*s1 && *s2 && *s1 == *s2)
- {
- s1++;
- s2++;
- }
- return (*s1 - *s2);
+ return (ft_memcmp(s1, s2, ft_strlen(s1) + 1));
}
diff --git a/src/str/ft_strdup.c b/src/str/ft_strdup.c
index b248272..9493d82 100644
--- a/src/str/ft_strdup.c
+++ b/src/str/ft_strdup.c
@@ -11,12 +11,15 @@
/* ************************************************************************** */
#include "libft.h"
+#include "libft_str.h"
char *ft_strdup(const char *s)
{
char *clone;
+ size_t size;
- if ((clone = (char*)malloc(sizeof(char) * (ft_strlen(s) + 1))) == NULL)
+ size = ft_strlen(s) + 1;
+ if ((clone = (char*)malloc(sizeof(char) * size)) == NULL)
return (NULL);
- return (ft_strcpy(clone, s));
+ return (ft_memcpy(clone, s, size));
}
diff --git a/src/str/ft_strlen.c b/src/str/ft_strlen.c
index 0d593e1..999763e 100644
--- a/src/str/ft_strlen.c
+++ b/src/str/ft_strlen.c
@@ -6,36 +6,68 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2019/10/07 10:32:48 by cacharle #+# #+# */
-/* Updated: 2020/01/17 11:13:43 by cacharle ### ########.fr */
+/* Updated: 2020/04/01 21:45:38 by charles ### ########.fr */
/* */
/* ************************************************************************** */
#include "libft.h"
+#include <stdint.h>
+
+/*
+** Determining if one byte of a long word is 0
+**
+** ~((((lw & 0x7F7F7F7F) + 0x7F7F7F7F) | lw) | 0x7F7F7F7F)
+**
+** where `lw` is a long word
+**
+** 0x7F -> 0b 0111 1111
+**
+** null_high = lw & 0x7F7F7F7F // will set the high bit of each byte to 0
+** overflow = null_high + 0x7F7F7F7F // addition will overflow the high bit
+** is one of the other bits was 1.
+**
+** oring = overflow | lw // the high bit of a byte is set
+** iff any bit in the byte was set
+** ones = oring | 0x7F7F7F7F // the high bits and ones everywhere else
+** has_no_zero_byte = ~ones // the ones become zeros, if no high bit
+** was set, there was no zero
+**
+** (lw - 0x01010101) & ~lw & 0x80808080
+**
+** overflow = lw - 0x01010101 // overflow the high bit if one was
+** 0 or > 0x80 (0b 1000 0000) 0 || >0x80
+** no_high_bit = ~lw & 0x80808080 // high bit set if the high bit was
+** 0 (i.e < 0x80) 0 || <0x80
+** has_zero = overflow & no_high_bit // (0 || >0x80) && (0 || <0x80) -> 0 && 0
+**
+**
+** libc's strlen only filter out < 0x80 bytes by omitting the ~lw & 0x80808080
+** part because most string only contain ascii characters.
+**
+** sources:
+** - https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord
+** - https://stackoverflow.com/questions/20021066
+*/
+
+#define HIMAGIC 0x8080808080808080L
+#define LOMAGIC 0x0101010101010101L
size_t ft_strlen(const char *s)
{
- unsigned long int *ptr;
- const char *cpy;
+ uint64_t *ptr;
+ const char *cpy;
+ const char *found;
- ptr = (unsigned long int*)s;
+ cpy = s;
+ while (((uint64_t)cpy & 0b111) != 0)
+ if (*cpy++ == '\0')
+ return (cpy - s - 1);
+ ptr = (uint64_t*)cpy;
while (TRUE)
- {
- cpy = (const char*)ptr++;
- if (cpy[0] == '\0')
- return (cpy - s);
- if (cpy[1] == '\0')
- return (cpy + 1 - s);
- if (cpy[2] == '\0')
- return (cpy + 2 - s);
- if (cpy[3] == '\0')
- return (cpy + 3 - s);
- if (cpy[4] == '\0')
- return (cpy + 4 - s);
- if (cpy[5] == '\0')
- return (cpy + 5 - s);
- if (cpy[6] == '\0')
- return (cpy + 6 - s);
- if (cpy[7] == '\0')
- return (cpy + 7 - s);
- }
+ if (((*ptr++ - LOMAGIC) & HIMAGIC) != 0)
+ {
+ cpy = (const char*)(ptr - 1);
+ if ((found = ft_memchr(cpy, '\0', sizeof(uint64_t))) != NULL)
+ return (found - s);
+ }
}
diff --git a/src/str/ft_strncat.c b/src/str/ft_strncat.c
index d68db0a..4686d59 100644
--- a/src/str/ft_strncat.c
+++ b/src/str/ft_strncat.c
@@ -14,16 +14,14 @@
char *ft_strncat(char *dest, const char *src, size_t n)
{
- size_t i;
- size_t j;
+ size_t dest_len;
+ size_t src_len;
- i = ft_strlen(dest);
- j = 0;
- while (j < n && src[j])
- {
- dest[i + j] = src[j];
- j++;
- }
- dest[i + j] = '\0';
+ dest_len = ft_strlen(dest);
+ src_len = ft_strlen(src);
+ if (n < src_len)
+ src_len = n;
+ ft_memcpy(dest + dest_len, src, src_len);
+ dest[dest_len + src_len] = '\0';
return (dest);
}
diff --git a/src/str/ft_strncmp.c b/src/str/ft_strncmp.c
index d810e8c..3e01708 100644
--- a/src/str/ft_strncmp.c
+++ b/src/str/ft_strncmp.c
@@ -6,21 +6,16 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2019/10/07 10:27:34 by cacharle #+# #+# */
-/* Updated: 2020/02/10 04:17:50 by cacharle ### ########.fr */
+/* Updated: 2020/05/09 12:29:41 by charles ### ########.fr */
/* */
/* ************************************************************************** */
-#include "libft.h"
-#include "libft_def.h"
+#include "libft_str.h"
int ft_strncmp(const char *s1, const char *s2, size_t n)
{
- size_t i;
+ size_t len;
- if (n == 0)
- return (0);
- i = 0;
- while (i + 1 < n && s1[i] == s2[i] && s1[i])
- i++;
- return ((t_ftuchar)s1[i] - (t_ftuchar)s2[i]);
+ len = ft_strlen(s1);
+ return (ft_memcmp(s1, s2, n < len ? n : len + 1));
}
diff --git a/src/str/ft_strstr.c b/src/str/ft_strstr.c
index 4d4d403..893ae1e 100644
--- a/src/str/ft_strstr.c
+++ b/src/str/ft_strstr.c
@@ -11,6 +11,7 @@
/* ************************************************************************** */
#include "libft.h"
+#include "libft_str.h"
char *ft_strstr(const char *haystack, const char *needle)
{
@@ -19,11 +20,5 @@ char *ft_strstr(const char *haystack, const char *needle)
needle_len = ft_strlen(needle);
if (needle_len == 0)
return ((char*)haystack);
- while (*haystack)
- {
- if (ft_strnequ(haystack, needle, needle_len))
- return ((char*)haystack);
- haystack++;
- }
- return (NULL);
+ return (ft_memmem(haystack, ft_strlen(haystack), needle, needle_len));
}
diff --git a/src/str/ft_strsub.c b/src/str/ft_strsub.c
index 77bffb2..c7121bd 100644
--- a/src/str/ft_strsub.c
+++ b/src/str/ft_strsub.c
@@ -6,7 +6,7 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2019/10/17 08:28:49 by cacharle #+# #+# */
-/* Updated: 2020/04/05 13:47:55 by charles ### ########.fr */
+/* Updated: 2020/05/09 12:30:39 by charles ### ########.fr */
/* */
/* ************************************************************************** */
@@ -35,5 +35,7 @@ char *ft_strsub(char const *s, size_t start, size_t len)
if ((sub = (char*)malloc(sizeof(char) * (len + 1))) == NULL)
return (NULL);
sub[len] = '\0';
+ if (start > ft_strlen(s))
+ return (sub);
return (ft_strncpy(sub, s + start, len));
}
generated by cgit (git 2.34.1) at 2026-05-16 04:13:16 +0000