diff options
Diffstat (limited to 'mdk-stage1/dietlibc/lib/qsort.c')
-rw-r--r-- | mdk-stage1/dietlibc/lib/qsort.c | 125 |
1 files changed, 0 insertions, 125 deletions
diff --git a/mdk-stage1/dietlibc/lib/qsort.c b/mdk-stage1/dietlibc/lib/qsort.c deleted file mode 100644 index 2a8824bf3..000000000 --- a/mdk-stage1/dietlibc/lib/qsort.c +++ /dev/null @@ -1,125 +0,0 @@ -#include <stdlib.h> -#include <assert.h> - -/* comments: - 1. insertion sort sofort, nicht nachträglich - 2. threshold = 16 - */ - -static inline void iswap(void *a,void *b,size_t size) { - register char *x=a; - register char *y=b; - register char *z=x+size; - while (x<z) { - register char tmp=*x; - *x=*y; - *y=tmp; - ++x; ++y; - } -} - -static inline void swap(void *base,size_t size,size_t a,size_t b) { - iswap(base+a*size,base+b*size,size); -} - -#if 0 -extern int array[]; - -void dumparray() { - printf("array now {%d,%d,%d,%d,%d}\n",array[0],array[1],array[2],array[3],array[4]); -} -#endif - -void isort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)) { - int i; - while (nmemb>1) { - char *min=base; - char *tmp=min+size; - for (i=1; i<nmemb; ++i) { - if (compar(tmp,min)<0) - min=tmp; - tmp+=size; - } - iswap(min,base,size); - base+=size; - nmemb-=1; - } -} - -void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)) { -#ifdef DEBUG - char *dbase=base; - char *dmax=base+(nmemb-1)*size; - char dmemb=nmemb; -#endif - static int level=0; - char* v; /* pivot */ - char* mid, *max, *min; - int lmemb; - -#if 0 - int left,right; - left=(int*)base-array; - right=left+nmemb-1; - ++level; - { int i; for (i=0; i<level; ++i) printf(" "); } - printf("qsort: level %d; base=%p, %dx%d; array[%d..%d]\n",level,base,nmemb,size,left,right); - assert(left>=0 && right<=1000); -#endif - if (nmemb<=8) { - --level; - return isort(base,nmemb,size,compar); - } - { - mid=base+(nmemb/2)*size; - max=base+(nmemb-1)*size; - - if (compar(base,max)<0) /* a[left] < a[right] */ - if (compar(base,mid)<0) /* a[left] < a[med] */ - if (compar(max,mid)<0) /* a[left] < a[right] < a[med] */ - v=max; - else /* a[left] < a[med] < a[right] */ - v=mid; - else /* a[med] < a[left] < a[right] */ - v=base; - else /* a[right] < a[left] */ - if (compar(base,mid)<0) /* a[right] < a[left] < a[med] */ - v=base; - else /* a[right] < a[left] && a[med] < a[left] */ - if (compar(max,mid)<0) /* a[right] < a[med] < a[left] */ - v=mid; - else - v=max; -// printf("%d %d %d -> median %d\n",*(int*)base,*(int*)mid,*(int*)max,*(int*)v); - } - if (v != max) - iswap(v,max,size); - v=max; - min=base; lmemb=0; - for (;;) { - while (compar(min,v)<0) { min+=size; ++lmemb; } - while (compar(max-=size,v)>0) ; - if (min>=max) break; - iswap(min,max,size); - } - iswap(min,v,size); -#ifdef DEBUG -// { int i; for (i=0; i<level; ++i) printf(" "); } -// printf("-=< base=%p, min=%p, nmemb=%d, lmemb=%d (%d)\n",base,min,nmemb,lmemb,(min-(char*)base)/size); - assert(lmemb==((min-(char*)base)/size)); -#endif - if (min>(char*)base+size) { -#ifdef DEBUG - assert(base==dbase); -#endif -// { int i; for (i=0; i<level; ++i) printf(" "); } -// printf("+-left %d [%d..%d] of [%d..%d]\n",level+1,left,left+lmemb,left,right); - qsort(base,lmemb,size,compar); - } - if (nmemb>lmemb+1) { -// { int i; for (i=0; i<level; ++i) printf(" "); } -// printf("+-right %d [%d..%d] of [%d..%d]\n",level+1,left+lmemb,right,left,right); - qsort(min+size,nmemb-lmemb-1,size,compar); - } - --level; -} |