diff options
| -rw-r--r-- | Makefile | 13 | ||||
| -rw-r--r-- | include/libft_bt.h | 37 | ||||
| -rw-r--r-- | include/libft_def.h | 3 | ||||
| -rw-r--r-- | include/libft_mem.h | 2 | ||||
| -rw-r--r-- | include/libft_rbt.h | 96 | ||||
| -rw-r--r-- | include/libft_str.h | 3 | ||||
| -rw-r--r-- | src/bt/ft_btdestroy.c | 13 | ||||
| -rw-r--r-- | src/bt/ft_btnew.c | 16 | ||||
| -rw-r--r-- | src/bt/ft_btsorted_insert.c | 38 | ||||
| -rw-r--r-- | src/bt/ft_btsorted_search.c | 35 | ||||
| -rw-r--r-- | src/mem/ft_memccpy.c | 58 | ||||
| -rw-r--r-- | src/mem/ft_memchr.c | 46 | ||||
| -rw-r--r-- | src/mem/ft_memcmp.c | 46 | ||||
| -rw-r--r-- | src/mem/ft_memcpy.c | 7 | ||||
| -rw-r--r-- | src/mem/ft_memmove.c | 13 | ||||
| -rw-r--r-- | src/mem/ft_memset.c | 34 | ||||
| -rw-r--r-- | src/rbt/ft_rbtinsert.c | 83 | ||||
| -rw-r--r-- | src/rbt/ft_rbtnew.c | 35 | ||||
| -rw-r--r-- | src/rbt/ft_rbtrotate_left.c | 38 | ||||
| -rw-r--r-- | src/rbt/ft_rbtrotate_right.c | 38 | ||||
| -rw-r--r-- | src/str/ft_split.c | 14 | ||||
| -rw-r--r-- | src/str/ft_strcat.c | 1 | ||||
| -rw-r--r-- | src/str/ft_strcmp.c | 7 | ||||
| -rw-r--r-- | src/str/ft_strdup.c | 7 | ||||
| -rw-r--r-- | src/str/ft_strlen.c | 78 | ||||
| -rw-r--r-- | src/str/ft_strncat.c | 18 | ||||
| -rw-r--r-- | src/str/ft_strncmp.c | 15 | ||||
| -rw-r--r-- | src/str/ft_strstr.c | 9 | ||||
| -rw-r--r-- | src/str/ft_strsub.c | 4 | ||||
| -rw-r--r-- | test/src/str/test_ft_strlen.c | 36 |
30 files changed, 697 insertions, 146 deletions
@@ -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 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* 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)); } diff --git a/test/src/str/test_ft_strlen.c b/test/src/str/test_ft_strlen.c index f251fc6..47ca69b 100644 --- a/test/src/str/test_ft_strlen.c +++ b/test/src/str/test_ft_strlen.c @@ -21,4 +21,40 @@ TEST(ft_strlen, basic) TEST_ASSERT_FT_STRLEN("asodifuaosidjoiasjdfoijasklfqwkberkjqwerkjqwlkenrmnqwerjkqwehfakjs"); TEST_ASSERT_FT_STRLEN("im\0hidden"); TEST_ASSERT_FT_STRLEN("987987\xff\xee\xaasdfioxcv"); + + TEST_ASSERT_FT_STRLEN("0123456789abcdefghijklmnopqrstuvwxyz"); + TEST_ASSERT_FT_STRLEN("0123456789abcdefghijklmnopqrstuvwxy"); + TEST_ASSERT_FT_STRLEN("0123456789abcdefghijklmnopqrstuvwx"); + TEST_ASSERT_FT_STRLEN("0123456789abcdefghijklmnopqrstuvw"); + TEST_ASSERT_FT_STRLEN("0123456789abcdefghijklmnopqrstuv"); + TEST_ASSERT_FT_STRLEN("0123456789abcdefghijklmnopqrstu"); + TEST_ASSERT_FT_STRLEN("0123456789abcdefghijklmnopqrst"); + TEST_ASSERT_FT_STRLEN("0123456789abcdefghijklmnopqrs"); + TEST_ASSERT_FT_STRLEN("0123456789abcdefghijklmnopqr"); + TEST_ASSERT_FT_STRLEN("0123456789abcdefghijklmnopq"); + TEST_ASSERT_FT_STRLEN("0123456789abcdefghijklmnop"); + TEST_ASSERT_FT_STRLEN("0123456789abcdefghijklmno"); + TEST_ASSERT_FT_STRLEN("0123456789abcdefghijklmn"); + TEST_ASSERT_FT_STRLEN("0123456789abcdefghijklm"); + TEST_ASSERT_FT_STRLEN("0123456789abcdefghijkl"); + TEST_ASSERT_FT_STRLEN("0123456789abcdefghijk"); + TEST_ASSERT_FT_STRLEN("0123456789abcdefghij"); + TEST_ASSERT_FT_STRLEN("0123456789abcdefghi"); + TEST_ASSERT_FT_STRLEN("0123456789abcdefgh"); + TEST_ASSERT_FT_STRLEN("0123456789abcdefg"); + TEST_ASSERT_FT_STRLEN("0123456789abcdef"); + TEST_ASSERT_FT_STRLEN("0123456789abcde"); + TEST_ASSERT_FT_STRLEN("0123456789abcd"); + TEST_ASSERT_FT_STRLEN("0123456789abc"); + TEST_ASSERT_FT_STRLEN("0123456789ab"); + TEST_ASSERT_FT_STRLEN("0123456789a"); + TEST_ASSERT_FT_STRLEN("012345678"); + TEST_ASSERT_FT_STRLEN("01234567"); + TEST_ASSERT_FT_STRLEN("0123456"); + TEST_ASSERT_FT_STRLEN("012345"); + TEST_ASSERT_FT_STRLEN("01234"); + TEST_ASSERT_FT_STRLEN("0123"); + TEST_ASSERT_FT_STRLEN("012"); + TEST_ASSERT_FT_STRLEN("01"); + TEST_ASSERT_FT_STRLEN("0"); } |