From 62c7327c47407f4f92723e3613742c05c4de5ba9 Mon Sep 17 00:00:00 2001 From: bonmas14 Date: Sun, 28 Sep 2025 22:53:37 +0300 Subject: sorting --- src/un_sort.c | 158 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/ungrateful.c | 2 + src/ungrateful.h | 15 ++++++ 3 files changed, 175 insertions(+) create mode 100644 src/un_sort.c (limited to 'src') diff --git a/src/un_sort.c b/src/un_sort.c new file mode 100644 index 0000000..0d5c570 --- /dev/null +++ b/src/un_sort.c @@ -0,0 +1,158 @@ +UN_COMP_PROC(un_sort_std_comp_proc) { + assert(a != NULL); + assert(b != NULL); + return memcmp((u8*)a, (u8*)b, size); +} + +UN_COMP_PROC(un_sort_s8_comp_proc) { + s8 a_s8, b_s8; + assert(size == sizeof(s8)); + assert(a != NULL); + assert(b != NULL); + + a_s8 = *(s8*)a; + b_s8 = *(s8*)b; + + if (a_s8 < b_s8) return -1; + if (a_s8 > b_s8) return 1; + + return 0; +} + +UN_COMP_PROC(un_sort_s16_comp_proc) { + s16 a_s16, b_s16; + assert(size == sizeof(s16)); + assert(a != NULL); + assert(b != NULL); + + a_s16 = *(s16*)a; + b_s16 = *(s16*)b; + + if (a_s16 < b_s16) return -1; + if (a_s16 > b_s16) return 1; + + return 0; +} + +UN_COMP_PROC(un_sort_s32_comp_proc) { + s32 a_s32, b_s32; + assert(size == sizeof(s32)); + assert(a != NULL); + assert(b != NULL); + + a_s32 = *(s32*)a; + b_s32 = *(s32*)b; + + if (a_s32 < b_s32) return -1; + if (a_s32 > b_s32) return 1; + + return 0; +} + +UN_COMP_PROC(un_sort_s64_comp_proc) { + s64 a_s64, b_s64; + assert(size == sizeof(s64)); + assert(a != NULL); + assert(b != NULL); + + a_s64 = *(s64*)a; + b_s64 = *(s64*)b; + + if (a_s64 < b_s64) return -1; + if (a_s64 > b_s64) return 1; + return 0; +} + +UN_COMP_PROC(un_sort_string_comp_proc) { + assert(a != NULL); + assert(b != NULL); + assert(size == sizeof(String)); + UNUSED(size); + + String va = *(String*)a; + String vb = *(String*)b; + + return un_string_compare(va, vb); +} + +static void sort_swap(void *data, u32 size, u64 a, u64 b) { + void *temp; + void *a_addr, *b_addr; + + a_addr = (u8*)data + a * size; + b_addr = (u8*)data + b * size; + + temp = un_memory_alloc(size, un_alloc_temp_get()); + + memcpy(temp, a_addr, size); + memcpy(a_addr, b_addr, size); + memcpy(b_addr, temp, size); +} + +// start - in elements, inclusive +// stop - in elements, exclusive +void un_sort_quick(void *data, u32 element_size, u64 start, u64 stop, compare_func_proc *comp) { + s64 size; + u64 begin_index, end_index, pivot_index; + u8 *pivot, *begin, *end; + Allocator talloc; + + size = stop - start; + + if (size < 2) { + return; + } + + if (comp == NULL) { + comp = un_sort_std_comp_proc; + } + + if (size == 2) { + if (comp(element_size, ((u8*)data) + start * element_size, ((u8*)data) + (stop - 1) * element_size) > 0) { + sort_swap(data, element_size, start, stop - 1); + } + + return; + } + + talloc = un_alloc_temp_get(); + + // u64 pivot_index = start + (stop - start) / 2; // center + pivot_index = stop - 1; + pivot = (u8*)un_memory_alloc(element_size, talloc); + memcpy(pivot, (u8*)data + pivot_index * element_size, element_size); + + begin_index = start; + end_index = stop - 1; + + while (begin_index < end_index) { + begin = ((u8*)data) + begin_index * element_size; + end = ((u8*)data) + end_index * element_size; + + if (comp(element_size, begin, pivot) < 0) { + begin_index++; + continue; + } + + if (comp(element_size, end, pivot) > 0) { + end_index--; + continue; + } + + if (comp(element_size, begin, end) == 0) { + begin_index++; + end_index--; + continue; + } + + sort_swap(data, element_size, begin_index, end_index); + if (begin_index == pivot_index) { + pivot_index = end_index; + } else if (end_index == pivot_index) { + pivot_index = begin_index; + } + } + + un_sort_quick(data, element_size, start, pivot_index, comp); + un_sort_quick(data, element_size, pivot_index + 1, stop, comp); +} diff --git a/src/ungrateful.c b/src/ungrateful.c index 96c9648..001d63a 100644 --- a/src/ungrateful.c +++ b/src/ungrateful.c @@ -15,6 +15,8 @@ #include "un_vec.c" #include "un_vecd.c" +#include "un_sort.c" + void un_init(u64 size_of_temp_mem) { un_alloc_temp_init(size_of_temp_mem); diff --git a/src/ungrateful.h b/src/ungrateful.h index a3918aa..70683a7 100644 --- a/src/ungrateful.h +++ b/src/ungrateful.h @@ -623,6 +623,21 @@ extern double un_m_ease_oquadd(double t); extern void un_m_mat_mulf(float *v, float *left, float *right); extern void un_m_mat_identityf(float *v); + +/* Sorting */ + +#define UN_COMP_PROC(name) s32 name(u64 size, void *a, void *b) +typedef UN_COMP_PROC(compare_func_proc); + +extern UN_COMP_PROC(un_sort_std_comp_proc); +extern UN_COMP_PROC(un_sort_s8_comp_proc); +extern UN_COMP_PROC(un_sort_s16_comp_proc); +extern UN_COMP_PROC(un_sort_s32_comp_proc); +extern UN_COMP_PROC(un_sort_s64_comp_proc); +extern UN_COMP_PROC(un_sort_string_comp_proc); + +extern void un_sort_quick(void *data, u32 element_size, u64 start, u64 stop, compare_func_proc *comp); + #if defined(__cplusplus) } #endif -- cgit v1.2.3-70-g09d2