From 4830af498e2d3a5440e65c63a3595b91f1cd4ac9 Mon Sep 17 00:00:00 2001
From: Pixel <pixel@nobis-crew.org>
Date: Sat, 5 Feb 2011 09:40:03 -0800
Subject: Added qsort, stolen from libnix.

---
 libc/LIB.status       |  2 +-
 libc/Makefile         |  2 ++
 libc/include/stdlib.h |  2 ++
 libc/src/qsort.c      | 51 +++++++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 56 insertions(+), 1 deletion(-)
 create mode 100755 libc/src/qsort.c

diff --git a/libc/LIB.status b/libc/LIB.status
index b2961a6..dfe85a1 100644
--- a/libc/LIB.status
+++ b/libc/LIB.status
@@ -42,7 +42,7 @@ setenv - missing
 system - missing, and won't be here anyway I think...
 
 bsearch - missing
-qsort   - missing
+qsort   - ok, stolen from libnix
 abs     - missing
 labs    - missing
 llabs   - missing
diff --git a/libc/Makefile b/libc/Makefile
index 9ef6392..aa04e93 100644
--- a/libc/Makefile
+++ b/libc/Makefile
@@ -22,6 +22,8 @@ src/write.c \
 src/stdio.c \
 src/errno.c \
 \
+src/qsort.c \
+\
 src/reent.c \
 \
 src/exit.c \
diff --git a/libc/include/stdlib.h b/libc/include/stdlib.h
index 1cfe6c4..5654950 100644
--- a/libc/include/stdlib.h
+++ b/libc/include/stdlib.h
@@ -9,4 +9,6 @@ typedef void (*atexit_func_t)(void);
 void exit(int status) __attribute__((noreturn));
 int atexit(atexit_func_t);
 
+void qsort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *));
+
 #endif
diff --git a/libc/src/qsort.c b/libc/src/qsort.c
new file mode 100755
index 0000000..eeb038b
--- /dev/null
+++ b/libc/src/qsort.c
@@ -0,0 +1,51 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+/* sample compar function: int cmp(void *a,void *b){ return *(int *)a-*(int *)b; } */
+
+/* This qsort function does a little trick:
+ * To reduce stackspace it iterates the larger interval instead of doing
+ * the recursion on both intervals. 
+ * So stackspace is limited to 32*stack_for_1_iteration = 
+ * 32*4*(4 arguments+1 returnaddress+11 stored registers) = 2048 Bytes,
+ * which is small enough for everybodys use.
+ * (And this is the worst case if you own 4GB and sort an array of chars.)
+ * Sparing the function calling overhead does improve performance, too.
+ */
+
+void qsort
+(void *base,size_t nmemb,size_t size,int (*compar)(const void *,const void *))
+{ char *base2=(char *)base;
+  size_t i,a,b,c;
+  while(nmemb>1)
+  { a=0;
+    b=nmemb-1;
+    c=(a+b)/2; /* Middle element */
+    for(;;)
+    { while((*compar)(&base2[size*c],&base2[size*a])>0) 
+        a++; /* Look for one >= middle */
+      while((*compar)(&base2[size*c],&base2[size*b])<0) 
+        b--; /* Look for one <= middle */
+      if(a>=b)
+        break; /* We found no pair */
+      for(i=0;i<size;i++) /* swap them */
+      { char tmp=base2[size*a+i];
+        base2[size*a+i]=base2[size*b+i];
+        base2[size*b+i]=tmp; }
+      if(c==a) /* Keep track of middle element */
+        c=b;
+      else if(c==b)
+        c=a;
+      a++; /* These two are already sorted */
+      b--;
+    } /* a points to first element of right intervall now (b to last of left) */
+    b++;
+    if(b<nmemb-b) /* do recursion on smaller intervall and iteration on larger one */
+    { qsort(base2,b,size,compar);
+      base2=&base2[size*b];
+      nmemb=nmemb-b; }
+    else
+    { qsort(&base2[size*b],nmemb-b,size,compar);
+      nmemb=b; }
+  }
+}
-- 
cgit v1.2.3