diff options
author | Guillaume Cottenceau <gc@mandriva.com> | 2001-05-14 14:19:32 +0000 |
---|---|---|
committer | Guillaume Cottenceau <gc@mandriva.com> | 2001-05-14 14:19:32 +0000 |
commit | 167217bec15c9c7aa70ba2a3dc9c689b3cd91872 (patch) | |
tree | 7c0c62debf8f9f145643102fb52b81afce743594 /mdk-stage1/dietlibc/lib/qsort.c | |
parent | 9097327dc1c667fc51b8e05cc7c0626fac96665d (diff) | |
download | drakx-backup-do-not-use-167217bec15c9c7aa70ba2a3dc9c689b3cd91872.tar drakx-backup-do-not-use-167217bec15c9c7aa70ba2a3dc9c689b3cd91872.tar.gz drakx-backup-do-not-use-167217bec15c9c7aa70ba2a3dc9c689b3cd91872.tar.bz2 drakx-backup-do-not-use-167217bec15c9c7aa70ba2a3dc9c689b3cd91872.tar.xz drakx-backup-do-not-use-167217bec15c9c7aa70ba2a3dc9c689b3cd91872.zip |
import new version of dietlibc
Diffstat (limited to 'mdk-stage1/dietlibc/lib/qsort.c')
-rw-r--r-- | mdk-stage1/dietlibc/lib/qsort.c | 125 |
1 files changed, 125 insertions, 0 deletions
diff --git a/mdk-stage1/dietlibc/lib/qsort.c b/mdk-stage1/dietlibc/lib/qsort.c new file mode 100644 index 000000000..2a8824bf3 --- /dev/null +++ b/mdk-stage1/dietlibc/lib/qsort.c @@ -0,0 +1,125 @@ +#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; +} |