From c044ba7897184a50d02c1761717ad0001fbc6a39 Mon Sep 17 00:00:00 2001 From: = <=> Date: Thu, 6 Nov 2025 18:01:08 +0100 Subject: [PATCH] Reworked to not use linked lists --- .get_next_line.c.swp | Bin 0 -> 12288 bytes get_next_line.c | 117 +++++++++++++------------------ get_next_line.h | 29 +++++--- get_next_line_bonus.c | 135 ------------------------------------ get_next_line_bonus.h | 39 ----------- get_next_line_utils.c | 119 ++++++++++++++++--------------- get_next_line_utils_bonus.c | 96 ------------------------- 7 files changed, 130 insertions(+), 405 deletions(-) create mode 100644 .get_next_line.c.swp delete mode 100644 get_next_line_bonus.c delete mode 100644 get_next_line_bonus.h delete mode 100644 get_next_line_utils_bonus.c diff --git a/.get_next_line.c.swp b/.get_next_line.c.swp new file mode 100644 index 0000000000000000000000000000000000000000..b9295bac3b221e41b26f4d12053b972446c40937 GIT binary patch literal 12288 zcmYc?2=nw+u+TGNU|?VnU|?{%!jtJ0$j)%0K#d_WJu@dKGqDIHg%4*N78w>;=$RPh zmgZ#Smlmh$rD4@m2QyGVpeR2pHMyi%KRvZ1J}2qS%EQ3W!o$Fj&%?kF&BMSD#lyg0&%?lA$HTxN%)`L&n45uN6*mJz z8#e<(2sZ;mFgF8(I5z`>C^rKGJ2wNv3oZtRn_LVGySNw_mUA&MEahTgSi;4?u#k&^ zp_+?0L4}KfL5Pcifs2cQ;R7cF!&^=UhGU!z4C^=< z7-n-aFqCpKFl2EuFr;%bFa&clFeq{|F#O?QV0gvBz;KI$f#C)R1H*L=28P`n3=BIt z7#L=8FfjCSFfep+Fff#JFfe3rFfgQZFfc@NFfh1rFff>MFfa&nFfed%Ffe>)XJB~A z&cN`Doq^#DI|IWBb_Ry!>*%=t(*%=rN*%=u0*cljf*clkK*%=r# z*cli^*%=s^*cliY*%=rfvN15+XJcTv!p6XGgpGmWFdGBIVm1bbQZ@#LWHtr{XEp`~ z2Q~%<9X19AZZ-x6b~Xlvd#nr$mslAXj<7N?Y+z+zXklewC}(A0C}w3~C}3q^aARd) zaAsv-&|qa?kYQzDkYr_G5NCzP?GQ|xqfQvIRwSq=oj)JWM%Hk#s z15Hh9O^C4|qfyL;8xC3qrJ$Orkd~Q~s-T()wI)+XAq!?1Cud?_C3v}%f~`VHQE4j3 zZJeCR`FSOoc~D+vnu3O6UXCUMCnqNsmuP5Y=9MUDX(kq>muW_4#e%(84e~C?7a+MT z1zQC}YlSQY8->K8^ki#=ENyL&X-HP5CFT@^?1p(Bq%BjyR>8np0jA1YArq_(#z%56 zsuMC}6>Jsq3sUnmKu(IzjMY)_j}LP3_w$JaxeXk+F!K$q6*A$@0-MjknUtTO0}mE! z22M~!aDpO&p_(BxuY@xfr5Y(O!aua{wm zB$Sq%SCRt~($`{uB?``>)RNMoJOz!U(zLYHqWHATyv*VZjiS_I9R)RrSh0>mT8bvf z?VRAafQZJY<`$Gxg0$%CaYl4CloEBgv`i1)VfOSDqM^S3AUQ%fqLsc|CzYmga&m%{ zT7$SC=Rt(Dl1kI888~Y}zR)WzPE7&nVc;w-Ni4}sRww~`B&js5804_D)S_YqTZL+d zY6eg=a%!PwGEgc>OVI?!70icVAA`(>34oI>C{RIuPAM+YwM!~Ziv}}54%SsLj8(9; zRZx$~Q`cnROe=}cP0dX%07o2HDI}V~OmJFFDoxY1D=*3{DM`%(8H>zU(6v>_1bGgW z7n6!o6SEaSP9e%>P*_1y8r;R;so@31_A?Lp1|96GEK4Q=T$alpGi-Y&JY? zK}>{YaESAhO4C3-fu`PKu-8C|Qbz%v_Tc{J1o;~z84t=taAAn1Vz>@#NZ4^g%><`+ z4Y+Es4Vu;rW%-#YoSa&S+w>42(?m4Gr}T%oGeQtPBjSObry0DivVMo8dMqD=RA~ zC@4dLURn`U24;eR8ZCinFynx#wn2JWo>0RR8UaRR@R0a zhcM8o(hA`%8<+ +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2025/11/01 10:55:35 by agilliar #+# #+# */ -/* Updated: 2025/11/01 20:55:35 by agilliar ### ########.fr */ +/* Updated: 2025/11/06 18:00:50 by agilliar ### ########.fr */ /* */ /* ************************************************************************** */ #include #include -#include "get_next_line.h" -void *ft_memcpy(void *dest, const void *src, size_t n); -bool buffer_shrink_near_fit(t_buf *buf); -bool buffer_search(t_buf *buf); -bool buffer_read(t_buf *buf, int fd); +#include "get_next_line.h" -t_buf *buffers_get(t_list **buffers, int fd) -{ - while (*buffers && (*buffers)->fd != fd) - buffers = &(*buffers)->next; - if (*buffers) - return (&(*buffers)->buf); - (*buffers) = malloc(sizeof(t_list)); - if (!*buffers) - return (NULL); - (*buffers)->next = NULL; - (*buffers)->fd = fd; - (*buffers)->buf.len = 0; - (*buffers)->buf.capacity = 0; - (*buffers)->buf.search_offset = 0; - (*buffers)->buf.buf = NULL; - return (&(*buffers)->buf); -} +void buffer_pushchar(t_buf *buf, char c); +void buffers_remove(t_readbufs *bufs, int fd); +void *ft_memcpy(void *dest, const void *src, size_t n); +bool readbuf_read(t_readbuf *buf); +t_readbuf *buffers_get(t_readbufs *bufs, int fd); -void *buffers_del(t_list **buffers, int fd) +char *buffer_finish(t_buf buf, t_readbufs *buffers, int fd) { - t_list *next; - - while (*buffers && (*buffers)->fd != fd) - buffers = &(*buffers)->next; - if (!*buffers) - return (NULL); - free((*buffers)->buf.buf); - next = (*buffers)->next; - free(*buffers); - *buffers = next; - return (NULL); + if (buf.buf) + buffer_pushchar(&buf, '\0'); + if (!buf.buf) + buffers_remove(buffers, fd); + return (buf.buf); } -char *ft_substr(const char *src, size_t len) -{ - char *res; - - res = malloc(len + 1); - if (!res) - return (res); - ft_memcpy(res, src, len); - res[len] = '\0'; - return (res); -} - -char *buffer_gnl(t_buf *buf, t_list **buffers, int fd) +/* + returns whether it should keep going +*/ +bool buffer_empty(t_readbuf *buf, t_buf *dst) { - char *res; + size_t i; - res = ft_substr(buf->buf, buf->search_offset); - if (!res) - return (buffers_del(buffers, fd)); - buf->len -= buf->search_offset; - ft_memcpy(buf->buf, &buf->buf[buf->search_offset], buf->len); - buf->search_offset = 0; - buffer_shrink_near_fit(buf); - return (res); + if (buf->written == 0) + return (false); + i = 0; + while (i < buf->written) + { + buffer_pushchar(dst, buf->buf[i++]); + if (dst->buf == NULL) + return (false); + if (dst->buf[dst->len - 1] == '\n') + break ; + } + buf->written -= i; + ft_memcpy(buf->buf, &buf->buf[i], buf->written); + if (dst->buf[dst->len - 1] == '\n') + return (false); + return (true); } char *get_next_line(int fd) { - static t_list *buffers = NULL; - t_buf *buf; - char *res; + static t_readbufs buffers = { + .used = 0 + }; + t_readbuf *buf; + t_buf res; + res.len = 0; + res.capacity = 0; + res.buf = NULL; buf = buffers_get(&buffers, fd); if (!buf) return (NULL); - while (buf->len != buf->search_offset || buffer_read(buf, fd)) + while (true) { - if (buf->search_offset == buf->len) + if (!readbuf_read(buf)) { - res = ft_substr(buf->buf, buf->len); - buffers_del(&buffers, fd); - return (res); + buffers_remove(&buffers, fd); + free(res.buf); + return (NULL); } - if (buffer_search(buf)) - return (buffer_gnl(buf, &buffers, fd)); + if (!buffer_empty(buf, &res)) + return (buffer_finish(res, &buffers, fd)); } - return (buffers_del(&buffers, fd)); } /* diff --git a/get_next_line.h b/get_next_line.h index 14eb657..ac33fb4 100644 --- a/get_next_line.h +++ b/get_next_line.h @@ -6,7 +6,7 @@ /* By: agilliar +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2025/11/01 10:38:19 by agilliar #+# #+# */ -/* Updated: 2025/11/01 20:52:08 by agilliar ### ########.fr */ +/* Updated: 2025/11/06 17:20:44 by agilliar ### ########.fr */ /* */ /* ************************************************************************** */ @@ -15,24 +15,33 @@ # include +# ifndef BUFFER_SIZE +# define BUFFER_SIZE 256 +# endif + +# ifndef GNL_MAX_FD +# define GNL_MAX_FD 256 +# endif + typedef struct s_buf { size_t len; size_t capacity; - size_t search_offset; char *buf; } t_buf; -typedef struct s_list +typedef struct s_readbuf { - int fd; - t_buf buf; - struct s_list *next; -} t_list; + size_t written; + int fd; + char buf[BUFFER_SIZE]; +} t_readbuf; -# ifndef BUFFER_SIZE -# define BUFFER_SIZE 256 -# endif +typedef struct s_readbufs +{ + size_t used; + t_readbuf bufs[GNL_MAX_FD]; +} t_readbufs; char *get_next_line(int fd); diff --git a/get_next_line_bonus.c b/get_next_line_bonus.c deleted file mode 100644 index c63adbb..0000000 --- a/get_next_line_bonus.c +++ /dev/null @@ -1,135 +0,0 @@ -/* ************************************************************************** */ -/* */ -/* ::: :::::::: */ -/* get_next_line_bonus.c :+: :+: :+: */ -/* +:+ +:+ +:+ */ -/* By: agilliar +#+ +:+ +#+ */ -/* +#+#+#+#+#+ +#+ */ -/* Created: 2025/11/01 10:55:35 by agilliar #+# #+# */ -/* Updated: 2025/11/01 20:57:34 by agilliar ### ########.fr */ -/* */ -/* ************************************************************************** */ - -#include -#include -#include "get_next_line_bonus.h" - -void *ft_memcpy(void *dest, const void *src, size_t n); -bool buffer_shrink_near_fit(t_buf *buf); -bool buffer_search(t_buf *buf); -bool buffer_read(t_buf *buf, int fd); - -t_buf *buffers_get(t_list **buffers, int fd) -{ - while (*buffers && (*buffers)->fd != fd) - buffers = &(*buffers)->next; - if (*buffers) - return (&(*buffers)->buf); - (*buffers) = malloc(sizeof(t_list)); - if (!*buffers) - return (NULL); - (*buffers)->next = NULL; - (*buffers)->fd = fd; - (*buffers)->buf.len = 0; - (*buffers)->buf.capacity = 0; - (*buffers)->buf.search_offset = 0; - (*buffers)->buf.buf = NULL; - return (&(*buffers)->buf); -} - -void *buffers_del(t_list **buffers, int fd) -{ - t_list *next; - - while (*buffers && (*buffers)->fd != fd) - buffers = &(*buffers)->next; - if (!*buffers) - return (NULL); - free((*buffers)->buf.buf); - next = (*buffers)->next; - free(*buffers); - *buffers = next; - return (NULL); -} - -char *ft_substr(const char *src, size_t len) -{ - char *res; - - res = malloc(len + 1); - if (!res) - return (res); - ft_memcpy(res, src, len); - res[len] = '\0'; - return (res); -} - -char *buffer_gnl(t_buf *buf, t_list **buffers, int fd) -{ - char *res; - - res = ft_substr(buf->buf, buf->search_offset); - if (!res) - return (buffers_del(buffers, fd)); - buf->len -= buf->search_offset; - ft_memcpy(buf->buf, &buf->buf[buf->search_offset], buf->len); - buf->search_offset = 0; - buffer_shrink_near_fit(buf); - return (res); -} - -char *get_next_line(int fd) -{ - static t_list *buffers = NULL; - t_buf *buf; - char *res; - - buf = buffers_get(&buffers, fd); - if (!buf) - return (NULL); - while (buf->len != buf->search_offset || buffer_read(buf, fd)) - { - if (buf->search_offset == buf->len) - { - res = ft_substr(buf->buf, buf->len); - buffers_del(&buffers, fd); - return (res); - } - if (buffer_search(buf)) - return (buffer_gnl(buf, &buffers, fd)); - } - return (buffers_del(&buffers, fd)); -} - -/* -#include -#include - -int main(int argc, char **argv) -{ - char *nl; - bool any_line; - - for (int i = 1; i < argc; i++) - ((int *)argv)[i] = open(argv[i], O_RDONLY); - any_line = true; - for (int i = 0; any_line; i++) - { - any_line = false; - for (int j = 1; j < argc; j++) - { - nl = get_next_line(((int *)argv)[j]); - if (!nl) - continue; - any_line = true; - printf("line %i file %i: %s", i, j, nl); - free(nl); - } - } - for (char *nl; (nl = get_next_line(0));) - { - printf("stdin: %s", nl); - free(nl); - } -} -*/ diff --git a/get_next_line_bonus.h b/get_next_line_bonus.h deleted file mode 100644 index ae03cf9..0000000 --- a/get_next_line_bonus.h +++ /dev/null @@ -1,39 +0,0 @@ -/* ************************************************************************** */ -/* */ -/* ::: :::::::: */ -/* get_next_line_bonus.h :+: :+: :+: */ -/* +:+ +:+ +:+ */ -/* By: agilliar +#+ +:+ +#+ */ -/* +#+#+#+#+#+ +#+ */ -/* Created: 2025/11/01 10:38:19 by agilliar #+# #+# */ -/* Updated: 2025/11/01 20:57:37 by agilliar ### ########.fr */ -/* */ -/* ************************************************************************** */ - -#ifndef GET_NEXT_LINE_BONUS_H -# define GET_NEXT_LINE_BONUS_H - -# include - -typedef struct s_buf -{ - size_t len; - size_t capacity; - size_t search_offset; - char *buf; -} t_buf; - -typedef struct s_list -{ - int fd; - t_buf buf; - struct s_list *next; -} t_list; - -# ifndef BUFFER_SIZE -# define BUFFER_SIZE 256 -# endif - -char *get_next_line(int fd); - -#endif diff --git a/get_next_line_utils.c b/get_next_line_utils.c index a7a215c..7e986cc 100644 --- a/get_next_line_utils.c +++ b/get_next_line_utils.c @@ -3,94 +3,99 @@ /* ::: :::::::: */ /* get_next_line_utils.c :+: :+: :+: */ /* +:+ +:+ +:+ */ -/* By: agilliar +#+ +:+ +#+ */ +/* By: agilliar +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ -/* Created: 2025/11/01 20:47:32 by agilliar #+# #+# */ -/* Updated: 2025/11/01 20:52:30 by agilliar ### ########.fr */ +/* Created: 2025/11/06 17:56:20 by agilliar #+# #+# */ +/* Updated: 2025/11/06 17:58:50 by agilliar ### ########.fr */ /* */ /* ************************************************************************** */ #include #include #include + #include "get_next_line.h" -/* - not restrict, therefor it is safe to use it on overlapping memory regions so - long as the destination is before the source -*/ -void *ft_memcpy(void *dest, const void *src, size_t n) +t_readbuf *buffers_get(t_readbufs *bufs, int fd) { size_t i; i = 0; - while (i < n) - { - ((unsigned char *)dest)[i] = ((unsigned char *)src)[i]; + while (i < bufs->used && bufs->bufs[i].fd != fd) i++; + if (i == GNL_MAX_FD) + return (NULL); + if (i == bufs->used) + { + bufs->bufs[i].written = 0; + bufs->bufs[i].fd = fd; + bufs->used++; } - return (dest); + return (&bufs->bufs[i]); } -/* - returns false when an allocation error occured -*/ -bool buffer_reserve(t_buf *buf, size_t extra) +void buffers_remove(t_readbufs *bufs, int fd) { - size_t new_capacity; - char *new_buf; + size_t i; + + i = 0; + while (i < bufs->used && bufs->bufs[i].fd != fd) + i++; + if (i == GNL_MAX_FD) + return ; + bufs->bufs[i] = bufs->bufs[--bufs->used]; +} + +bool readbuf_read(t_readbuf *buf) +{ + int n; - if (buf->len + extra <= buf->capacity) + if (buf->written != 0) return (true); - new_capacity = buf->len + extra; - if (new_capacity < buf->capacity * 2) - new_capacity = buf->capacity * 2; - new_buf = malloc(new_capacity); - if (!new_buf) + n = read(buf->fd, &buf->buf, BUFFER_SIZE); + if (n < 0) return (false); - ft_memcpy(new_buf, buf->buf, buf->len); - free(buf->buf); - buf->buf = new_buf; - buf->capacity = new_capacity; + buf->written = n; return (true); } -bool buffer_read(t_buf *buf, int fd) +void *ft_memcpy(void *dest, const void *src, size_t n) { - char read_buf[BUFFER_SIZE]; - ssize_t res; + size_t i; - res = read(fd, read_buf, BUFFER_SIZE); - if (res < 1 || !buffer_reserve(buf, res)) - return (false); - ft_memcpy(&buf->buf[buf->len], read_buf, res); - buf->len += res; - return (true); + i = 0; + while (i < n) + { + ((unsigned char *)dest)[i] = ((unsigned char *)src)[i]; + i++; + } + return (dest); } /* - returns false when an allocation error occured + frees its own resources on failure */ -bool buffer_shrink_near_fit(t_buf *buf) +void buffer_pushchar(t_buf *buf, char c) { + size_t new_capacity; char *new_buf; - if (buf->capacity <= buf->len * 2 + BUFFER_SIZE) - return (true); - new_buf = malloc(buf->len * 2); - if (!new_buf) - return (false); - ft_memcpy(new_buf, buf->buf, buf->len); - free(buf->buf); - buf->buf = new_buf; - buf->capacity = buf->len * 2; - return (true); -} - -bool buffer_search(t_buf *buf) -{ - while (buf->search_offset < buf->len) - if (buf->buf[buf->search_offset++] == '\n') - return (true); - return (false); + if (buf->len + 1 > buf->capacity) + { + new_capacity = buf->len + 1; + if (new_capacity < BUFFER_SIZE + buf->capacity * 2) + new_capacity = BUFFER_SIZE + buf->capacity * 2; + new_buf = malloc(new_capacity); + if (!new_buf) + { + free(buf->buf); + buf->buf = NULL; + return ; + } + ft_memcpy(new_buf, buf->buf, buf->len); + free(buf->buf); + buf->buf = new_buf; + buf->capacity = new_capacity; + } + buf->buf[buf->len++] = c; } diff --git a/get_next_line_utils_bonus.c b/get_next_line_utils_bonus.c deleted file mode 100644 index 1500ee6..0000000 --- a/get_next_line_utils_bonus.c +++ /dev/null @@ -1,96 +0,0 @@ -/* ************************************************************************** */ -/* */ -/* ::: :::::::: */ -/* get_next_line_utils_bonus.c :+: :+: :+: */ -/* +:+ +:+ +:+ */ -/* By: agilliar +#+ +:+ +#+ */ -/* +#+#+#+#+#+ +#+ */ -/* Created: 2025/11/01 20:47:32 by agilliar #+# #+# */ -/* Updated: 2025/11/01 20:57:50 by agilliar ### ########.fr */ -/* */ -/* ************************************************************************** */ - -#include -#include -#include -#include "get_next_line_bonus.h" - -/* - not restrict, therefor it is safe to use it on overlapping memory regions so - long as the destination is before the source -*/ -void *ft_memcpy(void *dest, const void *src, size_t n) -{ - size_t i; - - i = 0; - while (i < n) - { - ((unsigned char *)dest)[i] = ((unsigned char *)src)[i]; - i++; - } - return (dest); -} - -/* - returns false when an allocation error occured -*/ -bool buffer_reserve(t_buf *buf, size_t extra) -{ - size_t new_capacity; - char *new_buf; - - if (buf->len + extra <= buf->capacity) - return (true); - new_capacity = buf->len + extra; - if (new_capacity < buf->capacity * 2) - new_capacity = buf->capacity * 2; - new_buf = malloc(new_capacity); - if (!new_buf) - return (false); - ft_memcpy(new_buf, buf->buf, buf->len); - free(buf->buf); - buf->buf = new_buf; - buf->capacity = new_capacity; - return (true); -} - -bool buffer_read(t_buf *buf, int fd) -{ - char read_buf[BUFFER_SIZE]; - ssize_t res; - - res = read(fd, read_buf, BUFFER_SIZE); - if (res < 1 || !buffer_reserve(buf, res)) - return (false); - ft_memcpy(&buf->buf[buf->len], read_buf, res); - buf->len += res; - return (true); -} - -/* - returns false when an allocation error occured -*/ -bool buffer_shrink_near_fit(t_buf *buf) -{ - char *new_buf; - - if (buf->capacity <= buf->len * 2 + BUFFER_SIZE) - return (true); - new_buf = malloc(buf->len * 2); - if (!new_buf) - return (false); - ft_memcpy(new_buf, buf->buf, buf->len); - free(buf->buf); - buf->buf = new_buf; - buf->capacity = buf->len * 2; - return (true); -} - -bool buffer_search(t_buf *buf) -{ - while (buf->search_offset < buf->len) - if (buf->buf[buf->search_offset++] == '\n') - return (true); - return (false); -} -- 2.51.0