From e9bb049cfc7cce76e52197215edc970189b37301 Mon Sep 17 00:00:00 2001 From: Axy Date: Thu, 11 Dec 2025 01:09:55 +0100 Subject: [PATCH] Leaf sort finished! :D --- Makefile | 4 +-- algorithm_leafsort.c | 18 ++++++++++++ closure.c | 39 ++++++++++++++++++++++++++ leaf_sort.c | 66 ++++++++++++++++++++++++++++++++++++++++++++ leaf_sort.h | 4 +-- leaf_sort_index.c | 5 ++-- main_pushswap.c | 6 ++-- pushswap.h | 12 ++++++-- 8 files changed, 143 insertions(+), 11 deletions(-) create mode 100644 algorithm_leafsort.c create mode 100644 closure.c create mode 100644 leaf_sort.c diff --git a/Makefile b/Makefile index 2a69b16..742f39d 100644 --- a/Makefile +++ b/Makefile @@ -1,6 +1,6 @@ NAME=push_swap -SRCS=algorithm_quicksort.c algorithm_selection_sort.c cheatalloc.c clist.c leaf_sort_index.c leaf_sort_parse.c list.c main_pushswap.c op_output.c op_p.c op_parse.c op_r.c op_rr.c op_s.c ops.c ops_groups.c ops_optimizer.c output.c psval.c slice.c stack.c stacks.c +SRCS=algorithm_leafsort.c algorithm_quicksort.c algorithm_selection_sort.c cheatalloc.c clist.c closure.c leaf_sort.c leaf_sort_index.c leaf_sort_parse.c list.c main_pushswap.c op_output.c op_parse.c op_p.c op_r.c op_rr.c op_s.c ops.c ops_groups.c ops_optimizer.c output.c psval.c slice.c stack.c stacks.c RESSRCS=_res_leaf_sort_lookup.h @@ -17,7 +17,7 @@ CC=cc all : ${NAME} %.o : %.res - ld -r -b binary -o $@ $< + ld -r -z noexecstack -b binary -o $@ $< ${BUILDDIR}/%.res: _res_%.h | ${BUILDDIR} sed -n '\?/\*?d; n; n; :x p; n; bx' $^ | head -n-1 > $@ diff --git a/algorithm_leafsort.c b/algorithm_leafsort.c new file mode 100644 index 0000000..e01fb32 --- /dev/null +++ b/algorithm_leafsort.c @@ -0,0 +1,18 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* algorithm_leafsort.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: agilliar +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2025/12/11 01:00:50 by agilliar #+# #+# */ +/* Updated: 2025/12/11 01:04:13 by agilliar ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "pushswap.h" + +void algorithm_leafsort(const t_stacks *stacks, t_closure cb) +{ + leaf_sort_local(stacks, cb, false, stacks->a.len); +} diff --git a/closure.c b/closure.c new file mode 100644 index 0000000..682c42b --- /dev/null +++ b/closure.c @@ -0,0 +1,39 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* closure.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: agilliar +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2025/12/11 00:50:40 by agilliar #+# #+# */ +/* Updated: 2025/12/11 00:53:50 by agilliar ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "pushswap.h" + +void closure_call(t_closure cb, t_op op) +{ + (cb.func)(cb.data, op); +} + +void closure_callm(t_closure cb, t_op op, bool mirrored) +{ + const t_op mirror[] = { + OP_SB, + OP_SA, + OP_SS, + OP_PB, + OP_PA, + OP_RB, + OP_RA, + OP_RR, + OP_RRB, + OP_RRA, + OP_RRR, + }; + + if (mirrored) + op = mirror[op]; + closure_call(cb, op); +} diff --git a/leaf_sort.c b/leaf_sort.c new file mode 100644 index 0000000..626ad85 --- /dev/null +++ b/leaf_sort.c @@ -0,0 +1,66 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* leaf_sort.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: agilliar +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2025/12/11 00:27:32 by agilliar #+# #+# */ +/* Updated: 2025/12/11 01:04:35 by agilliar ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "leaf_sort.h" + +static void leaf_solution_apply(t_closure cb, bool mirrored, + t_leaf_solution *solution) +{ + size_t i; + + i = 0; + while (i < solution->used) + closure_callm(cb, solution->store[i++], mirrored); +} + +static t_leaf_solution *leaf_solution_get(const t_stacks *stacks, size_t size, + bool mirrored, t_leaf_lookup *lookup) +{ + t_psval store[4]; + const t_stack *stack; + size_t i; + + stack = &stacks->a; + if (mirrored) + stack = &stacks->b; + if (size > 4 || stack->len < size) + cheatexit(1); + i = 0; + while (i < size) + { + store[i] = clist_get_at(stack->list, i); + i++; + } + return (leaf_sort_get(size, store, lookup)); +} + +void leaf_sort_local(const t_stacks *stacks, t_closure cb, + bool mirrored, size_t size) +{ + t_leaf_solution *solution; + t_leaf_lookup *lookup; + + lookup = &leaf_lookups()->local; + solution = leaf_solution_get(stacks, size, mirrored, lookup); + leaf_solution_apply(cb, mirrored, solution); +} + +void leaf_sort_other(const t_stacks *stacks, t_closure cb, + bool mirrored, size_t size) +{ + t_leaf_solution *solution; + t_leaf_lookup *lookup; + + lookup = &leaf_lookups()->other; + solution = leaf_solution_get(stacks, size, mirrored, lookup); + leaf_solution_apply(cb, mirrored, solution); +} diff --git a/leaf_sort.h b/leaf_sort.h index e7e3672..a634885 100644 --- a/leaf_sort.h +++ b/leaf_sort.h @@ -6,7 +6,7 @@ /* By: agilliar +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2025/12/10 18:01:04 by agilliar #+# #+# */ -/* Updated: 2025/12/10 21:18:45 by agilliar ### ########.fr */ +/* Updated: 2025/12/11 00:51:37 by agilliar ### ########.fr */ /* */ /* ************************************************************************** */ @@ -43,6 +43,6 @@ extern void _binary__build_leaf_sort_lookup_res_end(void); t_leaf_lookups *leaf_lookups(void); t_leaf_solution *leaf_sort_get(size_t size, const t_psval *data, - t_leaf_lookup *lookup); + t_leaf_lookup *lookup); #endif diff --git a/leaf_sort_index.c b/leaf_sort_index.c index 3444e80..bc94f62 100644 --- a/leaf_sort_index.c +++ b/leaf_sort_index.c @@ -6,7 +6,7 @@ /* By: agilliar +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2025/12/10 19:46:38 by agilliar #+# #+# */ -/* Updated: 2025/12/10 21:16:39 by agilliar ### ########.fr */ +/* Updated: 2025/12/11 00:39:34 by agilliar ### ########.fr */ /* */ /* ************************************************************************** */ @@ -38,7 +38,8 @@ static size_t leaf_sort_index_norm(size_t size, const t_psval *data) j = 1; while (j < size) { - if (i >= store[j] && (data[j] > data[max_pos] || store[max_pos] > i)) + if (i >= store[j] + && (data[j] > data[max_pos] || store[max_pos] > i)) max_pos = j; j++; } diff --git a/main_pushswap.c b/main_pushswap.c index 0870758..977041d 100644 --- a/main_pushswap.c +++ b/main_pushswap.c @@ -6,7 +6,7 @@ /* By: clefrere +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2025/12/02 22:15:12 by agilliar #+# #+# */ -/* Updated: 2025/12/10 20:25:15 by agilliar ### ########.fr */ +/* Updated: 2025/12/11 01:02:32 by agilliar ### ########.fr */ /* */ /* ************************************************************************** */ @@ -32,6 +32,8 @@ static void arg_step(char *str, t_args *arg) arg->algo = &algorithm_quicksort; else if (ft_streq(str, "--adaptive")) arg->algo = NULL; + else if (ft_streq(str, "--leaf")) + arg->algo = &algorithm_leafsort; else if (ft_streq(str, "--bench")) arg->bench = true; else @@ -50,8 +52,6 @@ int main(int argc, char **argv) args.state = stacks_new(); args.bench = false; args.algo = NULL; - t_psval test[] = {0, 2, 3, 1}; - printf("%i", leaf_sort_get(4, test, &leaf_lookups()->other)->store[4]); for (int i = 1; i < argc; i++) arg_step(argv[i], &args); ops = ops_compose(ops_stackops(), ops_optimizer(ops_output(), &opt)); diff --git a/pushswap.h b/pushswap.h index 8572212..8b7ed81 100644 --- a/pushswap.h +++ b/pushswap.h @@ -6,7 +6,7 @@ /* By: clefrere +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2025/12/02 11:02:44 by agilliar #+# #+# */ -/* Updated: 2025/12/10 18:19:34 by agilliar ### ########.fr */ +/* Updated: 2025/12/11 01:03:57 by agilliar ### ########.fr */ /* */ /* ************************************************************************** */ @@ -125,6 +125,9 @@ void stack_move(t_stack *src, t_stack *dst); t_psval psval_parse(const char *s); void psval_output(t_psval val); +void closure_call(t_closure cb, t_op op); +void closure_callm(t_closure cb, t_op op, bool mirrored); + t_op op_parse(t_slice s); t_closure op_pa(void); @@ -161,7 +164,12 @@ bool slice_eq(t_slice lhs, t_slice rhs); t_slice slice_split(t_slice *rem, char at); void slice_output(t_slice s); +void leaf_sort_local(const t_stacks *stacks, t_closure cb, + bool mirrored, size_t size); +void leaf_sort_other(const t_stacks *stacks, t_closure cb, + bool mirrored, size_t size); + void algorithm_selection_sort(const t_stacks *stacks, t_closure cb); void algorithm_quicksort(const t_stacks *stacks, t_closure cb); - +void algorithm_leafsort(const t_stacks *stacks, t_closure cb); #endif -- 2.51.0