From 47221888b880fbfc118138976a732a88ddba0590 Mon Sep 17 00:00:00 2001 From: = <=> Date: Tue, 2 Dec 2025 18:45:31 +0100 Subject: [PATCH] Closure shenanigans --- Makefile | 29 +++++++++++++++ cheatalloc.c | 56 ++++++++++++++++++++++++++++ clist.c | 73 ++++++++++++++++++++++++++++++++++++ output.c | 62 +++++++++++++++++++++++++++++++ output_inner.h | 27 ++++++++++++++ pushswap.h | 88 ++++++++++++++++++++++++++++++++++++++++++++ stacks.c | 43 ++++++++++++++++++++++ stacks_apply.c | 38 +++++++++++++++++++ stacks_apply_inner.h | 24 ++++++++++++ 9 files changed, 440 insertions(+) create mode 100644 Makefile create mode 100644 cheatalloc.c create mode 100644 clist.c create mode 100644 output.c create mode 100644 output_inner.h create mode 100644 pushswap.h create mode 100644 stacks.c create mode 100644 stacks_apply.c create mode 100644 stacks_apply_inner.h diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..7faa4ea --- /dev/null +++ b/Makefile @@ -0,0 +1,29 @@ +NAME=push_swap + +SRCS= + +OBJS=${SRCS:.c=.o} + +CFLAGS=-Wall -Wextra -Werror + +CC=cc + +all : ${NAME} + +%.o : %.c + ${CC} ${CFLAGS} -c -o $@ $< + +${NAME} : ${OBJS} + cc -o $@ $^ + +clean : + rm -f ${OBJS} + +fclean : clean + rm -f ${NAME} + +re : fclean all + +bonus : ${NAME} + +.PHONY : all clean fclean re bonus diff --git a/cheatalloc.c b/cheatalloc.c new file mode 100644 index 0000000..3696e89 --- /dev/null +++ b/cheatalloc.c @@ -0,0 +1,56 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* cheatalloc.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: agilliar +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2025/12/02 15:07:21 by agilliar #+# #+# */ +/* Updated: 2025/12/02 16:41:27 by agilliar ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include +#include +#include "pushswap.h" + +static void **cheatalloc_store(void) +{ + static void *store = NULL; + + return (&store); +} + +static void cheatalloc_cleanup(void) +{ + void *store; + void *tmp; + + store = *cheatalloc_store(); + while (store) + { + tmp = *(void **) store; + free(store); + store = tmp; + } +} + +void cheatexit(int errcode) +{ + cheatalloc_cleanup(); + if (errcode) + write(2, "Error\n", 6); + exit(errcode); +} + +void *cheatalloc(size_t len) +{ + void **new; + + new = malloc(sizeof(void *) + len); + if (!new) + cheatexit(1); + *new = *cheatalloc_store(); + *cheatalloc_store() = (void *) new++; + return (new); +} diff --git a/clist.c b/clist.c new file mode 100644 index 0000000..cbfb0de --- /dev/null +++ b/clist.c @@ -0,0 +1,73 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* clist.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: agilliar +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2025/12/02 11:02:13 by agilliar #+# #+# */ +/* Updated: 2025/12/02 17:37:32 by agilliar ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "pushswap.h" + +t_clist *clist_new(t_psval val) +{ + t_clist *res; + + res = cheatalloc(sizeof(t_clist)); + res->next = res; + res->prev = res; + res->val = val; + return (res); +} + +// Positive numbers are forward, which wraps back to end of stack +t_psval clist_get_at(const t_clist *list, int i) +{ + if (i == 0) + return (list->val); + if (i > 0) + return (clist_get_at(list->next, i - 1)); + return (clist_get_at(list->prev, i + 1)); +} + +t_clist *clist_pop(t_clist **src) +{ + t_clist *res; + + res = *src; + if (res == res->next) + { + *src = NULL; + return (res); + } + res->next->prev = res->prev; + res->prev->next = res->next; + return (res); +} + +// *dst : Nullable +void clist_push(t_clist **dst, t_clist *lst) +{ + lst->next = lst; + lst->prev = lst; + if (*dst) + { + lst->next = (*dst)->next; + (*dst)->next->prev = lst; + lst->prev = *dst; + (*dst)->prev->next = lst; + } + *dst = lst; +} + +// *dst : Nullable +void clist_push_back(t_clist **dst, t_clist *lst) +{ + if (!*dst) + *dst = lst; + else + clist_push(&(*dst)->prev, lst); +} diff --git a/output.c b/output.c new file mode 100644 index 0000000..f4cc5e0 --- /dev/null +++ b/output.c @@ -0,0 +1,62 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* output.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: agilliar +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2025/12/02 16:47:00 by agilliar #+# #+# */ +/* Updated: 2025/12/02 17:08:17 by agilliar ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "pushswap.h" +#include "output_inner.h" +#include + +static t_output_store *output_store(void) +{ + static t_output_store store = {.written = 0}; + + return (&store); +} + +void output_flush(void) +{ + size_t i; + ssize_t written; + t_output_store *store; + + store = output_store(); + i = 0; + while (i < store->written) + { + written = write(1, &store->buf[i], store->written - i); + if (written <= 0) + cheatexit(written != 0); + i += written; + } + store->written = 0; +} + +static void output_char(char c) +{ + t_output_store *store; + + store = output_store(); + if (store->written == OUTPUT_STORE_SIZE) + output_flush(); + store->buf[store->written++] = c; +} + +void output_str(char *s) +{ + while (*s) + output_char(*(s++)); +} + +void output_str_ln(char *s) +{ + output_str(s); + output_char('\n'); +} diff --git a/output_inner.h b/output_inner.h new file mode 100644 index 0000000..b9b7e52 --- /dev/null +++ b/output_inner.h @@ -0,0 +1,27 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* output_inner.h :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: agilliar +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2025/12/02 16:51:14 by agilliar #+# #+# */ +/* Updated: 2025/12/02 17:09:26 by agilliar ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#ifndef OUTPUT_INNER_H +# define OUTPUT_INNER_H + +# ifndef OUTPUT_STORE_SIZE +# define OUTPUT_STORE_SIZE 1024 +# endif +# include + +typedef struct s_output_store +{ + size_t written; + char buf[1024]; +} t_output_store; + +#endif diff --git a/pushswap.h b/pushswap.h new file mode 100644 index 0000000..57219e0 --- /dev/null +++ b/pushswap.h @@ -0,0 +1,88 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* pushswap.h :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: agilliar +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2025/12/02 11:02:44 by agilliar #+# #+# */ +/* Updated: 2025/12/02 18:40:21 by agilliar ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#ifndef PUSHSWAP_H +# define PUSHSWAP_H + +# include +# include + +typedef int t_psval; + +typedef struct s_clist +{ + t_psval val; + struct s_clist *next; + struct s_clist *prev; +} t_clist; + +typedef struct s_stacks +{ + t_clist *a_list; + size_t a_len; + t_clist *b_list; + size_t b_len; +} t_stacks; + +// Func always receives as a first argument `data` +typedef struct s_closure +{ + void *data; + void (*func)(); +} t_closure; + +// Takes a stack and repeatedly calls the closure with the op to be applied +typedef void (t_algorithm)(const t_stacks *, t_closure); + +typedef struct s_args +{ + t_stacks state; + t_algorithm *algo; + bool bench; +} t_args; + +typedef enum e_op +{ + OP_SA = 0, + OP_SB = 1, + OP_SS = 2, + OP_PA = 3, + OP_PB = 4, + OP_RA = 5, + OP_RB = 6, + OP_RR = 7, + OP_RRA = 8, + OP_RRB = 9, + OP_RRR = 10, +} t_op; + +typedef struct s_ops +{ + t_closure ops[11]; +} t_ops; + +void cheatexit(int errcode); +void *cheatalloc(size_t len); + +t_clist *clist_new(t_psval val); +// Positive numbers are forward, which wraps back to end of stack +t_psval clist_get_at(const t_clist *list, int i); +t_clist *clist_pop(t_clist **src); +// *dst: : Nullable +void clist_push(t_clist **dst, t_clist *lst); +// *dst: : Nullable +void clist_push_back(t_clist **dst, t_clist *lst); + +void output_str(char *s); +void output_str_ln(char *s); + +#endif diff --git a/stacks.c b/stacks.c new file mode 100644 index 0000000..158b855 --- /dev/null +++ b/stacks.c @@ -0,0 +1,43 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* stacks.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: agilliar +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2025/12/02 15:57:41 by agilliar #+# #+# */ +/* Updated: 2025/12/02 18:10:34 by agilliar ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "pushswap.h" + +t_stacks stacks_new(void) +{ + t_stacks res; + + res.a_list = NULL; + res.a_len = 0; + res.b_list = NULL; + res.b_len = 0; + return (res); +} + +void stacks_insert_init(t_stacks *stacks, t_psval val) +{ + clist_push_back(&stacks->a_list, clist_new(val)); + stacks->a_len++; +} + +bool stack_is_solved(const t_stacks *stacks) +{ + size_t i; + + if (stacks->b_len != 0) + return (false); + i = 0; + while (++i < stacks->a_len) + if (clist_get_at(stacks->a_list, 0) > clist_get_at(stacks->a_list, -1)) + return (false); + return (true); +} diff --git a/stacks_apply.c b/stacks_apply.c new file mode 100644 index 0000000..93b3dba --- /dev/null +++ b/stacks_apply.c @@ -0,0 +1,38 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* stacks_apply.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: agilliar +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2025/12/02 18:10:48 by agilliar #+# #+# */ +/* Updated: 2025/12/02 18:26:05 by agilliar ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "pushswap.h" +#include "stacks_apply_inner.h" + +static void stacks_apply_op(t_stacks_apply_data *data, t_op op) +{ + t_stacks *stacks; + const t_ops *ops; + t_closure op_fn; + + stacks = data->stacks; + ops = data->ops; + op_fn = ops->ops[op]; + (op_fn.func)(op_fn.data, stacks); +} + +void stacks_apply(t_stacks *stacks, const t_ops *ops, t_algorithm algo) +{ + t_closure closure; + t_stacks_apply_data closure_data; + + closure_data.stacks = stacks; + closure_data.ops = ops; + closure.data = &closure_data; + closure.func = &stacks_apply_op; + algo(stacks, closure); +} diff --git a/stacks_apply_inner.h b/stacks_apply_inner.h new file mode 100644 index 0000000..1872359 --- /dev/null +++ b/stacks_apply_inner.h @@ -0,0 +1,24 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* stacks_apply_inner.h :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: agilliar +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2025/12/02 18:18:38 by agilliar #+# #+# */ +/* Updated: 2025/12/02 18:22:48 by agilliar ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#ifndef STACKS_APPLY_INNER_H +# define STACKS_APPLY_INNER_H + +# include "pushswap.h" + +typedef struct s_stacks_apply_data +{ + t_stacks *stacks; + const t_ops *ops; +} t_stacks_apply_data; + +#endif -- 2.51.0