summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--libc/LIB.status2
-rw-r--r--libc/Makefile2
-rw-r--r--libc/include/stdlib.h2
-rwxr-xr-xlibc/src/qsort.c51
4 files changed, 56 insertions, 1 deletions
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; }
+ }
+}