diff options
Diffstat (limited to 'distrib/sdl-1.2.12/src/stdlib/SDL_qsort.c')
| -rw-r--r-- | distrib/sdl-1.2.12/src/stdlib/SDL_qsort.c | 425 |
1 files changed, 0 insertions, 425 deletions
diff --git a/distrib/sdl-1.2.12/src/stdlib/SDL_qsort.c b/distrib/sdl-1.2.12/src/stdlib/SDL_qsort.c deleted file mode 100644 index 9278d25..0000000 --- a/distrib/sdl-1.2.12/src/stdlib/SDL_qsort.c +++ /dev/null @@ -1,425 +0,0 @@ -/* qsort.c - * (c) 1998 Gareth McCaughan - * - * This is a drop-in replacement for the C library's |qsort()| routine. - * - * Features: - * - Median-of-three pivoting (and more) - * - Truncation and final polishing by a single insertion sort - * - Early truncation when no swaps needed in pivoting step - * - Explicit recursion, guaranteed not to overflow - * - A few little wrinkles stolen from the GNU |qsort()|. - * - separate code for non-aligned / aligned / word-size objects - * - * This code may be reproduced freely provided - * - this file is retained unaltered apart from minor - * changes for portability and efficiency - * - no changes are made to this comment - * - any changes that *are* made are clearly flagged - * - the _ID string below is altered by inserting, after - * the date, the string " altered" followed at your option - * by other material. (Exceptions: you may change the name - * of the exported routine without changing the ID string. - * You may change the values of the macros TRUNC_* and - * PIVOT_THRESHOLD without changing the ID string, provided - * they remain constants with TRUNC_nonaligned, TRUNC_aligned - * and TRUNC_words/WORD_BYTES between 8 and 24, and - * PIVOT_THRESHOLD between 32 and 200.) - * - * You may use it in anything you like; you may make money - * out of it; you may distribute it in object form or as - * part of an executable without including source code; - * you don't have to credit me. (But it would be nice if - * you did.) - * - * If you find problems with this code, or find ways of - * making it significantly faster, please let me know! - * My e-mail address, valid as of early 1998 and certainly - * OK for at least the next 18 months, is - * gjm11@dpmms.cam.ac.uk - * Thanks! - * - * Gareth McCaughan Peterhouse Cambridge 1998 - */ -#include "SDL_config.h" - -/* -#include <assert.h> -#include <stdlib.h> -#include <string.h> -*/ -#include "SDL_stdinc.h" - -#define assert(X) -#define malloc SDL_malloc -#define free SDL_free -#define memcpy SDL_memcpy -#define memmove SDL_memmove -#define qsort SDL_qsort - - -#ifndef HAVE_QSORT - -static char _ID[]="<qsort.c gjm 1.12 1998-03-19>"; - -/* How many bytes are there per word? (Must be a power of 2, - * and must in fact equal sizeof(int).) - */ -#define WORD_BYTES sizeof(int) - -/* How big does our stack need to be? Answer: one entry per - * bit in a |size_t|. - */ -#define STACK_SIZE (8*sizeof(size_t)) - -/* Different situations have slightly different requirements, - * and we make life epsilon easier by using different truncation - * points for the three different cases. - * So far, I have tuned TRUNC_words and guessed that the same - * value might work well for the other two cases. Of course - * what works well on my machine might work badly on yours. - */ -#define TRUNC_nonaligned 12 -#define TRUNC_aligned 12 -#define TRUNC_words 12*WORD_BYTES /* nb different meaning */ - -/* We use a simple pivoting algorithm for shortish sub-arrays - * and a more complicated one for larger ones. The threshold - * is PIVOT_THRESHOLD. - */ -#define PIVOT_THRESHOLD 40 - -typedef struct { char * first; char * last; } stack_entry; -#define pushLeft {stack[stacktop].first=ffirst;stack[stacktop++].last=last;} -#define pushRight {stack[stacktop].first=first;stack[stacktop++].last=llast;} -#define doLeft {first=ffirst;llast=last;continue;} -#define doRight {ffirst=first;last=llast;continue;} -#define pop {if (--stacktop<0) break;\ - first=ffirst=stack[stacktop].first;\ - last=llast=stack[stacktop].last;\ - continue;} - -/* Some comments on the implementation. - * 1. When we finish partitioning the array into "low" - * and "high", we forget entirely about short subarrays, - * because they'll be done later by insertion sort. - * Doing lots of little insertion sorts might be a win - * on large datasets for locality-of-reference reasons, - * but it makes the code much nastier and increases - * bookkeeping overhead. - * 2. We always save the shorter and get to work on the - * longer. This guarantees that every time we push - * an item onto the stack its size is <= 1/2 of that - * of its parent; so the stack can't need more than - * log_2(max-array-size) entries. - * 3. We choose a pivot by looking at the first, last - * and middle elements. We arrange them into order - * because it's easy to do that in conjunction with - * choosing the pivot, and it makes things a little - * easier in the partitioning step. Anyway, the pivot - * is the middle of these three. It's still possible - * to construct datasets where the algorithm takes - * time of order n^2, but it simply never happens in - * practice. - * 3' Newsflash: On further investigation I find that - * it's easy to construct datasets where median-of-3 - * simply isn't good enough. So on large-ish subarrays - * we do a more sophisticated pivoting: we take three - * sets of 3 elements, find their medians, and then - * take the median of those. - * 4. We copy the pivot element to a separate place - * because that way we can always do our comparisons - * directly against a pointer to that separate place, - * and don't have to wonder "did we move the pivot - * element?". This makes the inner loop better. - * 5. It's possible to make the pivoting even more - * reliable by looking at more candidates when n - * is larger. (Taking this to its logical conclusion - * results in a variant of quicksort that doesn't - * have that n^2 worst case.) However, the overhead - * from the extra bookkeeping means that it's just - * not worth while. - * 6. This is pretty clean and portable code. Here are - * all the potential portability pitfalls and problems - * I know of: - * - In one place (the insertion sort) I construct - * a pointer that points just past the end of the - * supplied array, and assume that (a) it won't - * compare equal to any pointer within the array, - * and (b) it will compare equal to a pointer - * obtained by stepping off the end of the array. - * These might fail on some segmented architectures. - * - I assume that there are 8 bits in a |char| when - * computing the size of stack needed. This would - * fail on machines with 9-bit or 16-bit bytes. - * - I assume that if |((int)base&(sizeof(int)-1))==0| - * and |(size&(sizeof(int)-1))==0| then it's safe to - * get at array elements via |int*|s, and that if - * actually |size==sizeof(int)| as well then it's - * safe to treat the elements as |int|s. This might - * fail on systems that convert pointers to integers - * in non-standard ways. - * - I assume that |8*sizeof(size_t)<=INT_MAX|. This - * would be false on a machine with 8-bit |char|s, - * 16-bit |int|s and 4096-bit |size_t|s. :-) - */ - -/* The recursion logic is the same in each case: */ -#define Recurse(Trunc) \ - { size_t l=last-ffirst,r=llast-first; \ - if (l<Trunc) { \ - if (r>=Trunc) doRight \ - else pop \ - } \ - else if (l<=r) { pushLeft; doRight } \ - else if (r>=Trunc) { pushRight; doLeft }\ - else doLeft \ - } - -/* and so is the pivoting logic: */ -#define Pivot(swapper,sz) \ - if ((size_t)(last-first)>PIVOT_THRESHOLD*sz) mid=pivot_big(first,mid,last,sz,compare);\ - else { \ - if (compare(first,mid)<0) { \ - if (compare(mid,last)>0) { \ - swapper(mid,last); \ - if (compare(first,mid)>0) swapper(first,mid);\ - } \ - } \ - else { \ - if (compare(mid,last)>0) swapper(first,last)\ - else { \ - swapper(first,mid); \ - if (compare(mid,last)>0) swapper(mid,last);\ - } \ - } \ - first+=sz; last-=sz; \ - } - -#ifdef DEBUG_QSORT -#include <stdio.h> -#endif - -/* and so is the partitioning logic: */ -#define Partition(swapper,sz) { \ - int swapped=0; \ - do { \ - while (compare(first,pivot)<0) first+=sz; \ - while (compare(pivot,last)<0) last-=sz; \ - if (first<last) { \ - swapper(first,last); swapped=1; \ - first+=sz; last-=sz; } \ - else if (first==last) { first+=sz; last-=sz; break; }\ - } while (first<=last); \ - if (!swapped) pop \ -} - -/* and so is the pre-insertion-sort operation of putting - * the smallest element into place as a sentinel. - * Doing this makes the inner loop nicer. I got this - * idea from the GNU implementation of qsort(). - */ -#define PreInsertion(swapper,limit,sz) \ - first=base; \ - last=first + (nmemb>limit ? limit : nmemb-1)*sz;\ - while (last!=base) { \ - if (compare(first,last)>0) first=last; \ - last-=sz; } \ - if (first!=base) swapper(first,(char*)base); - -/* and so is the insertion sort, in the first two cases: */ -#define Insertion(swapper) \ - last=((char*)base)+nmemb*size; \ - for (first=((char*)base)+size;first!=last;first+=size) { \ - char *test; \ - /* Find the right place for |first|. \ - * My apologies for var reuse. */ \ - for (test=first-size;compare(test,first)>0;test-=size) ; \ - test+=size; \ - if (test!=first) { \ - /* Shift everything in [test,first) \ - * up by one, and place |first| \ - * where |test| is. */ \ - memcpy(pivot,first,size); \ - memmove(test+size,test,first-test); \ - memcpy(test,pivot,size); \ - } \ - } - -#define SWAP_nonaligned(a,b) { \ - register char *aa=(a),*bb=(b); \ - register size_t sz=size; \ - do { register char t=*aa; *aa++=*bb; *bb++=t; } while (--sz); } - -#define SWAP_aligned(a,b) { \ - register int *aa=(int*)(a),*bb=(int*)(b); \ - register size_t sz=size; \ - do { register int t=*aa;*aa++=*bb; *bb++=t; } while (sz-=WORD_BYTES); } - -#define SWAP_words(a,b) { \ - register int t=*((int*)a); *((int*)a)=*((int*)b); *((int*)b)=t; } - -/* ---------------------------------------------------------------------- */ - -static char * pivot_big(char *first, char *mid, char *last, size_t size, - int compare(const void *, const void *)) { - size_t d=(((last-first)/size)>>3)*size; - char *m1,*m2,*m3; - { char *a=first, *b=first+d, *c=first+2*d; -#ifdef DEBUG_QSORT -fprintf(stderr,"< %d %d %d\n",*(int*)a,*(int*)b,*(int*)c); -#endif - m1 = compare(a,b)<0 ? - (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a)) - : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b)); - } - { char *a=mid-d, *b=mid, *c=mid+d; -#ifdef DEBUG_QSORT -fprintf(stderr,". %d %d %d\n",*(int*)a,*(int*)b,*(int*)c); -#endif - m2 = compare(a,b)<0 ? - (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a)) - : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b)); - } - { char *a=last-2*d, *b=last-d, *c=last; -#ifdef DEBUG_QSORT -fprintf(stderr,"> %d %d %d\n",*(int*)a,*(int*)b,*(int*)c); -#endif - m3 = compare(a,b)<0 ? - (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a)) - : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b)); - } -#ifdef DEBUG_QSORT -fprintf(stderr,"-> %d %d %d\n",*(int*)m1,*(int*)m2,*(int*)m3); -#endif - return compare(m1,m2)<0 ? - (compare(m2,m3)<0 ? m2 : (compare(m1,m3)<0 ? m3 : m1)) - : (compare(m1,m3)<0 ? m1 : (compare(m2,m3)<0 ? m3 : m2)); -} - -/* ---------------------------------------------------------------------- */ - -static void qsort_nonaligned(void *base, size_t nmemb, size_t size, - int (*compare)(const void *, const void *)) { - - stack_entry stack[STACK_SIZE]; - int stacktop=0; - char *first,*last; - char *pivot=malloc(size); - size_t trunc=TRUNC_nonaligned*size; - assert(pivot!=0); - - first=(char*)base; last=first+(nmemb-1)*size; - - if ((size_t)(last-first)>trunc) { - char *ffirst=first, *llast=last; - while (1) { - /* Select pivot */ - { char * mid=first+size*((last-first)/size >> 1); - Pivot(SWAP_nonaligned,size); - memcpy(pivot,mid,size); - } - /* Partition. */ - Partition(SWAP_nonaligned,size); - /* Prepare to recurse/iterate. */ - Recurse(trunc) - } - } - PreInsertion(SWAP_nonaligned,TRUNC_nonaligned,size); - Insertion(SWAP_nonaligned); - free(pivot); -} - -static void qsort_aligned(void *base, size_t nmemb, size_t size, - int (*compare)(const void *, const void *)) { - - stack_entry stack[STACK_SIZE]; - int stacktop=0; - char *first,*last; - char *pivot=malloc(size); - size_t trunc=TRUNC_aligned*size; - assert(pivot!=0); - - first=(char*)base; last=first+(nmemb-1)*size; - - if ((size_t)(last-first)>trunc) { - char *ffirst=first,*llast=last; - while (1) { - /* Select pivot */ - { char * mid=first+size*((last-first)/size >> 1); - Pivot(SWAP_aligned,size); - memcpy(pivot,mid,size); - } - /* Partition. */ - Partition(SWAP_aligned,size); - /* Prepare to recurse/iterate. */ - Recurse(trunc) - } - } - PreInsertion(SWAP_aligned,TRUNC_aligned,size); - Insertion(SWAP_aligned); - free(pivot); -} - -static void qsort_words(void *base, size_t nmemb, - int (*compare)(const void *, const void *)) { - - stack_entry stack[STACK_SIZE]; - int stacktop=0; - char *first,*last; - char *pivot=malloc(WORD_BYTES); - assert(pivot!=0); - - first=(char*)base; last=first+(nmemb-1)*WORD_BYTES; - - if (last-first>TRUNC_words) { - char *ffirst=first, *llast=last; - while (1) { -#ifdef DEBUG_QSORT -fprintf(stderr,"Doing %d:%d: ", - (first-(char*)base)/WORD_BYTES, - (last-(char*)base)/WORD_BYTES); -#endif - /* Select pivot */ - { char * mid=first+WORD_BYTES*((last-first) / (2*WORD_BYTES)); - Pivot(SWAP_words,WORD_BYTES); - *(int*)pivot=*(int*)mid; - } -#ifdef DEBUG_QSORT -fprintf(stderr,"pivot=%d\n",*(int*)pivot); -#endif - /* Partition. */ - Partition(SWAP_words,WORD_BYTES); - /* Prepare to recurse/iterate. */ - Recurse(TRUNC_words) - } - } - PreInsertion(SWAP_words,(TRUNC_words/WORD_BYTES),WORD_BYTES); - /* Now do insertion sort. */ - last=((char*)base)+nmemb*WORD_BYTES; - for (first=((char*)base)+WORD_BYTES;first!=last;first+=WORD_BYTES) { - /* Find the right place for |first|. My apologies for var reuse */ - int *pl=(int*)(first-WORD_BYTES),*pr=(int*)first; - *(int*)pivot=*(int*)first; - for (;compare(pl,pivot)>0;pr=pl,--pl) { - *pr=*pl; } - if (pr!=(int*)first) *pr=*(int*)pivot; - } - free(pivot); -} - -/* ---------------------------------------------------------------------- */ - -void qsort(void *base, size_t nmemb, size_t size, - int (*compare)(const void *, const void *)) { - - if (nmemb<=1) return; - if (((uintptr_t)base|size)&(WORD_BYTES-1)) - qsort_nonaligned(base,nmemb,size,compare); - else if (size!=WORD_BYTES) - qsort_aligned(base,nmemb,size,compare); - else - qsort_words(base,nmemb,compare); -} - -#endif /* !HAVE_QSORT */ |