diff options
| -rw-r--r-- | libc/LIB.status | 2 | ||||
| -rw-r--r-- | libc/Makefile | 2 | ||||
| -rw-r--r-- | libc/include/stdlib.h | 2 | ||||
| -rwxr-xr-x | libc/src/qsort.c | 51 |
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; } + } +} |