nserver: Add darray_algos.h

2 files changed, 248 insertions, 0 deletions

diff --git a/nserver/src/darray_algos.c b/nserver/src/darray_algos.c
new file mode 100644
index 0000000..fdde37d
--- /dev/null
+++ b/nserver/src/darray_algos.c
@@ -0,0 +1,230 @@
+#include <darray_algos.h>
+#include <math.h>
+#include <stdlib.h>
+
+int DArray_qsort(DArray *array, DArray_compare cmp)
+{
+    qsort(array->contents, DArray_count(array), sizeof(void *), cmp);
+    return 0;
+}
+
+int DArray_heapsort(DArray *array, DArray_compare cmp)
+{
+    return heapsort(array->contents, DArray_count(array),
+                    sizeof(void *), cmp);
+}
+
+int DArray_mergesort(DArray *array, DArray_compare cmp)
+{
+    return mergesort(array->contents, DArray_count(array),
+                     sizeof(void *), cmp);
+}
+
+// Fucked Quick Sort.
+int DArray_fucked_qsort_partition(DArray *array, DArray_compare cmp,
+                                  int low, int high)
+{
+    int i = 0, j = 0, cmp_rc;
+    void *pivot = NULL, *tmp = NULL;
+
+    pivot = array->contents[high];
+    i = low - 1;
+
+    for (j = low; j < high; j++) {
+        cmp_rc = cmp(&array->contents[j], &pivot);
+        if (cmp_rc < 0) {
+            i = i + 1;
+
+            // swap
+            tmp = array->contents[j];
+            array->contents[j] = array->contents[i];
+            array->contents[i] = tmp;
+        }
+    }
+
+    cmp_rc = cmp(&array->contents[high], &array->contents[i + 1]);
+    if (cmp_rc < 0) {
+            tmp = array->contents[high];
+            array->contents[high] = array->contents[i + 1];
+            array->contents[i + 1] = tmp;
+    }
+
+    return i + 1;
+}
+
+int DArray_fucked_qsort_recurse(DArray *array, DArray_compare cmp,
+                        int low, int high)
+{
+    int rc = 0, p = 0;
+    if (low < high) {
+        p = DArray_fucked_qsort_partition(array, cmp, low, high);
+        check(p >= 0, "Failed to partition [%d-%d]", low, high);
+
+        rc = DArray_fucked_qsort_recurse(array, cmp, low, p - 1);
+        check(rc == 0, "Failed to quick sort sub array [%d-%d]", low, p-1);
+
+        rc = DArray_fucked_qsort_recurse(array, cmp, p + 1, high);
+        check(rc == 0, "Failed to quick sort sub array [%d-%d]", p+1, high);
+    }
+
+    return 0;
+ error:
+    return -1;
+}
+
+int DArray_fucked_qsort(DArray *array, DArray_compare cmp)
+{
+    int rc;
+    rc = DArray_fucked_qsort_recurse(array, cmp, 0, DArray_end(array) - 1);
+    check(rc == 0, "Error sorting array.");
+
+    return 0;
+ error:
+    return -1;
+}
+
+// Fucked Heap Sort.
+#define DArray_fucked_heapsort_iparent(i) ((floor(i - 1) / 2))
+#define DArray_fucked_heapsort_ileft_child(i) ((2*i + 1))
+#define DArray_fucked_heapsort_iright_child(i) ((2*i + 2))
+
+inline void DArray_fucked_heapsort_swap(DArray *array, int a, int b)
+{
+    void *tmp = array->contents[a];
+    array->contents[a] = array->contents[b];
+    array->contents[b] = tmp;
+}
+
+int DArray_fucked_heapsort_sift_down(DArray *array, DArray_compare cmp,
+                              int start, int end)
+{
+
+    int root = start;
+    int child = 0;
+    int swap = 0;
+
+    while (DArray_fucked_heapsort_ileft_child(root) <= end) {
+        child = DArray_fucked_heapsort_ileft_child(root);
+        swap = root;
+
+        if (cmp(&array->contents[root], &array->contents[child]) < 0) {
+            swap = child;
+        }
+        if (((child + 1) <= end)
+            && (cmp(&array->contents[swap], &array->contents[child + 1]) < 0)) {
+            swap = child + 1;
+        }
+        if (swap == root) {
+            break;
+        }
+
+        DArray_fucked_heapsort_swap(array, root, swap);
+        root = swap;
+    }
+
+    return 0;
+}
+
+int DArray_fucked_heapsort_heapify(DArray *array, DArray_compare cmp)
+{
+    int count = DArray_count(array);
+    int start = (int) DArray_fucked_heapsort_iparent(count - 1);
+    int rc = 0;
+
+
+    while (start >= 0) {
+        rc = DArray_fucked_heapsort_sift_down(array, cmp, start, count - 1);
+        check(rc == 0, "Error sifting down at %d %d", start, count - 1);
+
+        start = start - 1;
+    }
+
+    return 0;
+ error:
+    return -1;
+}
+
+int DArray_fucked_heapsort(DArray *array, DArray_compare cmp)
+{
+    int rc = 0, end = 0;
+
+    // First heapify array.
+    rc = DArray_fucked_heapsort_heapify(array, cmp);
+    check(rc == 0, "Error heapifying");
+
+    end = DArray_count(array) - 1;
+    while (end > 0) {
+        DArray_fucked_heapsort_swap(array, end, 0);
+
+        end = end - 1;
+        rc = DArray_fucked_heapsort_sift_down(array, cmp, 0, end);
+        check(rc == 0, "Error sifting down at %d %d", 0, end);
+    }
+
+    return 0;
+ error:
+    return -1;
+}
+
+// Fucked Merge Sort.
+void DArray_fucked_topdown_merge(DArray *a, DArray *b,
+                                int begin, int middle,
+                                int end, DArray_compare cmp)
+{
+    int i = 0, j = 0, k = 0;
+
+    i = begin;
+    j = middle;
+
+    for (k = begin; k < end; k++) {
+        if (i < middle &&
+            (j >= end || cmp(&a->contents[i], &a->contents[j]) < 0)) {
+            DArray_set(b, k, DArray_get(a, i));
+            i = i + 1;
+        } else {
+            DArray_set(b, k, DArray_get(a, j));
+            j = j + 1;
+        }
+    }
+
+    return;
+}
+
+void DArray_fucked_topdown_split_merge(DArray *b, DArray *a,
+                                      int begin, int end,
+                                      DArray_compare cmp)
+{
+    if ((end - begin) < 2) {
+        return;
+    }
+    int middle = (end + begin) / 2;
+
+    DArray_fucked_topdown_split_merge(a, b, begin, middle, cmp);
+    DArray_fucked_topdown_split_merge(a, b, middle, end, cmp);
+
+    DArray_fucked_topdown_merge(b, a, begin, middle, end, cmp);
+
+    return;
+}
+
+int DArray_fucked_mergesort(DArray *array, DArray_compare cmp)
+{
+    DArray *copy = DArray_shallow_copy(array);
+    check(copy != NULL, "Error shallow copying array");
+
+    DArray *a = NULL, *b = NULL;
+    int begin = 0, end = 0;
+
+    a = array;
+    b = copy;
+    begin  = 0;
+    end = DArray_end(a);
+    DArray_fucked_topdown_split_merge(b, a, begin, end, cmp);
+
+    // Clean up copy
+    DArray_destroy(copy);
+
+    return 0;
+ error:
+    return -1;
+}
diff --git a/nserver/src/darray_algos.h b/nserver/src/darray_algos.h
new file mode 100644
index 0000000..204669f
--- /dev/null
+++ b/nserver/src/darray_algos.h
@@ -0,0 +1,18 @@
+#ifndef darray_algos_h
+#define darray_algos_h
+
+#include <darray.h>
+
+int DArray_qsort(DArray *array, DArray_compare cmp);
+
+int DArray_heapsort(DArray *array, DArray_compare cmp);
+
+int DArray_mergesort(DArray *array, DArray_compare cmp);
+
+int DArray_fucked_qsort(DArray *array, DArray_compare cmp);
+
+int DArray_fucked_heapsort(DArray *array, DArray_compare cmp);
+
+int DArray_fucked_mergesort(DArray *array, DArray_compare cmp);
+
+#endif