sorting

3 files changed, 175 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