first draft of qsort()

5 files changed, 69 insertions, 5 deletions

diff --git a/src/stdlib/_qsort.h b/src/stdlib/_qsort.h
new file mode 100644
index 00000000..298e28a1
--- /dev/null
+++ b/src/stdlib/_qsort.h
@@ -0,0 +1,39 @@
+#include <stdlib.h>
+#include <string.h>
+
+struct __qs {
+	char *base;
+	size_t size;
+	int (*compar)(const void *, const void *);
+	char buf[64];
+	char *swap;
+};
+
+static void __swap(struct __qs *a, size_t i, size_t j)
+{
+	memcpy(a->swap, a->base + (a->size * i), a->size);
+	memcpy(a->base + (a->size * i), a->base + (a->size * j), a->size);
+	memcpy(a->base + (a->size * j), a->swap, a->size);
+}
+
+static size_t __partition(struct __qs *a, size_t lo, size_t hi)
+{
+	size_t i = lo, j = 0;
+	for (j = lo; j < hi; j++) {
+		if (a->compar(a->base + (a->size * j), a->base + (a->size * hi)) < 0) {
+			__swap(a, i, j);
+			i++;
+		}
+	}
+	__swap(a, i, hi);
+	return i;
+}
+
+static void __qsort(struct __qs *a, size_t lo, size_t hi)
+{
+	if (lo < hi) {
+		size_t p = __partition(a, lo, hi);
+		__qsort(a, lo, p - 1);
+		__qsort(a, p + 1, hi);
+	}
+}
diff --git a/src/stdlib/abort.c b/src/stdlib/abort.c
index 4c5fd8a4..bfd47317 100644
--- a/src/stdlib/abort.c
+++ b/src/stdlib/abort.c
@@ -2,7 +2,14 @@
 #ifdef _POSIX_SOURCE
 #include "sys/types.h"
 #endif
+/*
 #include "signal.h"
+*/
+
+#define __SIGNAL_H__
+#define SIGABRT
+#include "ungol/signal.h"
+extern void raise(int);
 
 /** cause abnormal program termination **/
 
diff --git a/src/stdlib/qsort.c b/src/stdlib/qsort.c
index da4c5c15..f0ccba33 100644
--- a/src/stdlib/qsort.c
+++ b/src/stdlib/qsort.c
@@ -1,11 +1,29 @@
 #include <stdlib.h>
+#include "_qsort.h"
 
 /** sort an array **/
 
 void qsort(void * base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))
 {
-	(void)base; (void)nmemb; (void)size; (void)compar;
-	/* TODO */
+	struct __qs qs = {
+		base,
+		size,
+		compar,
+		{ 0 },
+		NULL,
+	};
+
+	if (size <= sizeof(qs.buf)) {
+		qs.swap = qs.buf;
+	} else {
+		qs.swap = malloc(size);
+	}
+
+	__qsort(&qs, 0, nmemb);
+
+	if (qs.swap != qs.buf) {
+		free(qs.swap);
+	}
 }
 
 /***
diff --git a/src/stdlib/realloc.c b/src/stdlib/realloc.c
index a7220acc..77eb7989 100644
--- a/src/stdlib/realloc.c
+++ b/src/stdlib/realloc.c
@@ -5,7 +5,7 @@
 #if defined _POSIX_C_SOURCE && 199305L <= _POSIX_C_SOURCE
 /* mu */
 #else
-#include "../sys/mman/mmap.c"
+#include "sys/mman/mmap.c"
 #define PROT_READ 0x1
 #define PROT_WRITE 0x2
 #define MAP_PRIVATE 0x2
diff --git a/src/stdlib/strtod.c b/src/stdlib/strtod.c
index b866f47c..9a1af627 100644
--- a/src/stdlib/strtod.c
+++ b/src/stdlib/strtod.c
@@ -5,11 +5,11 @@
 #include "math.h"
 
 #ifndef INFINITY
-#include "../math/INFINITY.c"
+#include "math/INFINITY.c"
 #endif
 
 #ifndef NAN
-#include "../math/NAN.c"
+#include "math/NAN.c"
 #endif
 
 /** convert string to floating-point **/