aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/un_sort.c158
-rw-r--r--src/ungrateful.c2
-rw-r--r--src/ungrateful.h15
-rw-r--r--tests/un/sorter.c84
4 files changed, 259 insertions, 0 deletions
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
diff --git a/tests/un/sorter.c b/tests/un/sorter.c
new file mode 100644
index 0000000..7d46772
--- /dev/null
+++ b/tests/un/sorter.c
@@ -0,0 +1,84 @@
+#include <ungrateful.h>
+
+b32 sort_test_case_s32(s32 *data, s32 *expect, u64 size) {
+ un_sort_quick(data, sizeof(s32), 0, size, un_sort_s32_comp_proc);
+ return memcmp(data, expect, size * sizeof(s32)) == 0;
+}
+
+b32 sort_test_case_string(String *data, String *expect, u64 size) {
+ un_sort_quick(data, sizeof(String), 0, size, un_sort_string_comp_proc);
+
+ for (u64 i = 0; i < size; i++) {
+ if (un_string_compare(data[i], expect[i]) != 0) return false;
+ }
+ return true;
+}
+
+void main() {
+ un_init(UN_MB(4));
+ {
+ s32 data[] = {5, 4, 3, 2, 1};
+ s32 expected[] = {1, 2, 3, 4, 5};
+ assert(sort_test_case_s32(data, expected, sizeof(data) / sizeof(s32)));
+ }
+ {
+ s32 data[] = {1, 2, 3, 4, 5};
+ s32 expected[] = {1, 2, 3, 4, 5};
+ assert(sort_test_case_s32(data, expected, sizeof(data) / sizeof(s32)));
+ }
+ {
+ s32 data[] = {3, 1, 4, 5, 2};
+ s32 expected[] = {1, 2, 3, 4, 5};
+ assert(sort_test_case_s32(data, expected, sizeof(data) / sizeof(s32)));
+ }
+ {
+ s32 data[] = {2, 3, 2, 1, 3, 4};
+ s32 expected[] = {1, 2, 2, 3, 3, 4};
+ assert(sort_test_case_s32(data, expected, sizeof(data) / sizeof(s32)));
+ }
+ {
+ s32 data[] = {42};
+ s32 expected[] = {42};
+ assert(sort_test_case_s32(data, expected, sizeof(data) / sizeof(s32)));
+ }
+ {
+ s32 data[] = {-3, 1, -2, 0, -1};
+ s32 expected[] = {-3, -2, -1, 0, 1};
+ assert(sort_test_case_s32(data, expected, sizeof(data) / sizeof(s32)));
+ }
+ {
+ s32 data[] = {7, 7, 7, 7, 7};
+ s32 expected[] = {7, 7, 7, 7, 7};
+ assert(sort_test_case_s32(data, expected, sizeof(data) / sizeof(s32)));
+ }
+ {
+ s32 data[] = {9, 3, 7, 1, 8, 2, 5, 4, 6, 0};
+ s32 expected[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+ assert(sort_test_case_s32(data, expected, sizeof(data) / sizeof(s32)));
+ }
+ {
+ String data[] = { UN_STR("apple"), UN_STR("banana"), UN_STR("cherry") };
+ String expected[] = { UN_STR("apple"), UN_STR("banana"), UN_STR("cherry") };
+ assert(sort_test_case_string(data, expected, sizeof(data) / sizeof(data[0])));
+ }
+ {
+ String data[] = { UN_STR("zebra"), UN_STR("elephant"), UN_STR("ant") };
+ String expected[] = { UN_STR("ant"), UN_STR("elephant"), UN_STR("zebra") };
+ assert(sort_test_case_string(data, expected, sizeof(data) / sizeof(data[0])));
+ }
+ {
+ String data[] = { UN_STR("Apple"), UN_STR("banana"), UN_STR("cherry") };
+ String expected[] = { UN_STR("Apple"), UN_STR("banana"), UN_STR("cherry") };
+ assert(sort_test_case_string(data, expected, sizeof(data) / sizeof(data[0])));
+ }
+ {
+ String data[] = { UN_STR(""), UN_STR("123"), UN_STR("!@#"), UN_STR("abc") };
+ String expected[] = { UN_STR(""), UN_STR("!@#"), UN_STR("123"), UN_STR("abc") };
+ assert(sort_test_case_string(data, expected, sizeof(data) / sizeof(data[0])));
+ }
+ {
+ String data[] = { UN_STR("hello world"), UN_STR("hello"), UN_STR(" space"), UN_STR("space") };
+ String expected[] = { UN_STR(" space"), UN_STR("hello"), UN_STR("hello world"), UN_STR("space") };
+ assert(sort_test_case_string(data, expected, sizeof(data) / sizeof(data[0])));
+ }
+}
generated by cgit v1.2.3-70-g09d2 (git 2.50.1) at 2025-10-09 16:18:12 +0000