51 #include "SDL_stdinc.h"
54 #if defined(HAVE_QSORT)
56 SDL_qsort(
void *base,
size_t nmemb,
size_t size,
int (*compare) (
const void *,
const void *))
58 qsort(base, nmemb, size, compare);
65 #define assert(X) SDL_assert(X)
69 #define malloc SDL_malloc
77 #define memcpy SDL_memcpy
81 #define memmove SDL_memmove
85 #define qsort SDL_qsort
87 static const char _ID[] =
"<qsort.c gjm 1.12 1998-03-19>";
92 #define WORD_BYTES sizeof(int)
97 #define STACK_SIZE (8*sizeof(size_t))
106 #define TRUNC_nonaligned 12
107 #define TRUNC_aligned 12
108 #define TRUNC_words 12*WORD_BYTES
114 #define PIVOT_THRESHOLD 40
121 #define pushLeft {stack[stacktop].first=ffirst;stack[stacktop++].last=last;}
122 #define pushRight {stack[stacktop].first=first;stack[stacktop++].last=llast;}
123 #define doLeft {first=ffirst;llast=last;continue;}
124 #define doRight {ffirst=first;last=llast;continue;}
125 #define pop {if (--stacktop<0) break;\
126 first=ffirst=stack[stacktop].first;\
127 last=llast=stack[stacktop].last;\
196 #define Recurse(Trunc) \
197 { size_t l=last-ffirst,r=llast-first; \
199 if (r>=Trunc) doRight \
202 else if (l<=r) { pushLeft; doRight } \
203 else if (r>=Trunc) { pushRight; doLeft }\
208 #define Pivot(swapper,sz) \
209 if ((size_t)(last-first)>PIVOT_THRESHOLD*sz) mid=pivot_big(first,mid,last,sz,compare);\
211 if (compare(first,mid)<0) { \
212 if (compare(mid,last)>0) { \
214 if (compare(first,mid)>0) swapper(first,mid);\
218 if (compare(mid,last)>0) swapper(first,last)\
220 swapper(first,mid); \
221 if (compare(mid,last)>0) swapper(mid,last);\
224 first+=sz; last-=sz; \
232 #define Partition(swapper,sz) { \
235 while (compare(first,pivot)<0) first+=sz; \
236 while (compare(pivot,last)<0) last-=sz; \
238 swapper(first,last); swapped=1; \
239 first+=sz; last-=sz; } \
240 else if (first==last) { first+=sz; last-=sz; break; }\
241 } while (first<=last); \
250 #define PreInsertion(swapper,limit,sz) \
252 last=first + (nmemb>limit ? limit : nmemb-1)*sz;\
253 while (last!=base) { \
254 if (compare(first,last)>0) first=last; \
256 if (first!=base) swapper(first,(char*)base);
259 #define Insertion(swapper) \
260 last=((char*)base)+nmemb*size; \
261 for (first=((char*)base)+size;first!=last;first+=size) { \
265 for (test=first-size;compare(test,first)>0;test-=size) ; \
271 memcpy(pivot,first,size); \
272 memmove(test+size,test,first-test); \
273 memcpy(test,pivot,size); \
277 #define SWAP_nonaligned(a,b) { \
278 register char *aa=(a),*bb=(b); \
279 register size_t sz=size; \
280 do { register char t=*aa; *aa++=*bb; *bb++=t; } while (--sz); }
282 #define SWAP_aligned(a,b) { \
283 register int *aa=(int*)(a),*bb=(int*)(b); \
284 register size_t sz=size; \
285 do { register int t=*aa;*aa++=*bb; *bb++=t; } while (sz-=WORD_BYTES); }
287 #define SWAP_words(a,b) { \
288 register int t=*((int*)a); *((int*)a)=*((int*)b); *((int*)b)=t; }
294 int compare(
const void *,
const void *))
296 size_t d = (((last -
first) / size) >> 3) * size;
299 char *
a =
first, *
b = first +
d, *
c = first + 2 *
d;
301 fprintf(stderr,
"< %d %d %d\n", *(
int *) a, *(
int *) b, *(
int *) c);
303 m1 = compare(a, b) < 0 ?
304 (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c :
a))
305 : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c :
b));
308 char *
a = mid -
d, *
b = mid, *
c = mid +
d;
310 fprintf(stderr,
". %d %d %d\n", *(
int *) a, *(
int *) b, *(
int *) c);
312 m2 = compare(a, b) < 0 ?
313 (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c :
a))
314 : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c :
b));
317 char *
a = last - 2 *
d, *
b = last -
d, *
c = last;
319 fprintf(stderr,
"> %d %d %d\n", *(
int *) a, *(
int *) b, *(
int *) c);
321 m3 = compare(a, b) < 0 ?
322 (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c :
a))
323 : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c :
b));
326 fprintf(stderr,
"-> %d %d %d\n", *(
int *) m1, *(
int *) m2, *(
int *) m3);
328 return compare(m1, m2) < 0 ?
329 (compare(m2, m3) < 0 ? m2 : (compare(m1, m3) < 0 ? m3 : m1))
330 : (compare(m1, m3) < 0 ? m1 : (compare(m2, m3) < 0 ? m3 : m2));
337 int (*compare) (
const void *,
const void *))
343 char *pivot =
malloc(size);
347 first = (
char *) base;
348 last = first + (nmemb - 1) * size;
350 if ((
size_t) (last -
first) > trunc) {
351 char *ffirst =
first, *llast = last;
355 char *mid = first + size * ((last -
first) / size >> 1);
371 int (*compare) (
const void *,
const void *))
377 char *pivot =
malloc(size);
381 first = (
char *) base;
382 last = first + (nmemb - 1) * size;
384 if ((
size_t) (last -
first) > trunc) {
385 char *ffirst =
first, *llast = last;
389 char *mid = first + size * ((last -
first) / size >> 1);
405 int (*compare) (
const void *,
const void *))
414 first = (
char *) base;
418 char *ffirst =
first, *llast = last;
421 fprintf(stderr,
"Doing %d:%d: ",
430 *(
int *) pivot = *(
int *) mid;
433 fprintf(stderr,
"pivot=%d\n", *(
int *) pivot);
443 for (first = ((
char *) base) + WORD_BYTES; first != last;
446 int *pl = (
int *) (first - WORD_BYTES), *pr = (
int *) first;
447 *(
int *) pivot = *(
int *)
first;
448 for (; compare(pl, pivot) > 0; pr = pl, --pl) {
451 if (pr != (
int *)
first)
452 *pr = *(
int *) pivot;
460 qsort(
void *base,
size_t nmemb,
size_t size,
461 int (*compare) (
const void *,
const void *))
#define SWAP_aligned(a, b)
#define PreInsertion(swapper, limit, sz)
#define Pivot(swapper, sz)
GLboolean GLboolean GLboolean GLboolean a
return Display return Display Bool Bool int d
static char * pivot_big(char *first, char *mid, char *last, size_t size, int compare(const void *, const void *))
static void qsort_nonaligned(void *base, size_t nmemb, size_t size, int(*compare)(const void *, const void *))
#define SWAP_nonaligned(a, b)
static void qsort_words(void *base, size_t nmemb, int(*compare)(const void *, const void *))
#define Insertion(swapper)
GLdouble GLdouble GLdouble b
DECLSPEC void SDLCALL SDL_qsort(void *base, size_t nmemb, size_t size, int(*compare)(const void *, const void *))
#define Partition(swapper, sz)
static void qsort_aligned(void *base, size_t nmemb, size_t size, int(*compare)(const void *, const void *))