Go to the documentation of this file.
22 #if defined(__clang_analyzer__) && !defined(SDL_DISABLE_ANALYZE_MACROS)
23 #define SDL_DISABLE_ANALYZE_MACROS 1
26 #include "../SDL_internal.h"
31 #if defined(HAVE_QSORT)
33 SDL_qsort(
void *base,
size_t nmemb,
size_t size,
int (*compare) (
const void *,
const void *))
35 qsort(base, nmemb,
size, compare);
43 #define assert SDL_assert
47 #define malloc SDL_malloc
55 #define memcpy SDL_memcpy
59 #define memmove SDL_memmove
63 #define qsortG SDL_qsort
156 static char _ID[]=
"<qsort.c gjm 1.14 2016-02-21>";
163 #define WORD_BYTES sizeof(int)
168 #define STACK_SIZE (8*sizeof(size_t))
177 #define TRUNC_nonaligned 12
178 #define TRUNC_aligned 12
179 #define TRUNC_words 12*WORD_BYTES
185 #define PIVOT_THRESHOLD 40
188 #define pushLeft {stack[stacktop].first=ffirst;stack[stacktop++].last=last;}
189 #define pushRight {stack[stacktop].first=first;stack[stacktop++].last=llast;}
190 #define doLeft {first=ffirst;llast=last;continue;}
191 #define doRight {ffirst=first;last=llast;continue;}
192 #define pop {if (--stacktop<0) break;\
193 first=ffirst=stack[stacktop].first;\
194 last=llast=stack[stacktop].last;\
265 #define Recurse(Trunc) \
266 { size_t l=last-ffirst,r=llast-first; \
268 if (r>=Trunc) doRight \
271 else if (l<=r) { pushLeft; doRight } \
272 else if (r>=Trunc) { pushRight; doLeft }\
277 #define Pivot(swapper,sz) \
278 if ((size_t)(last-first)>PIVOT_THRESHOLD*sz) mid=pivot_big(first,mid,last,sz,compare);\
280 if (compare(first,mid)<0) { \
281 if (compare(mid,last)>0) { \
283 if (compare(first,mid)>0) swapper(first,mid);\
287 if (compare(mid,last)>0) swapper(first,last)\
289 swapper(first,mid); \
290 if (compare(mid,last)>0) swapper(mid,last);\
293 first+=sz; last-=sz; \
301 #define Partition(swapper,sz) { \
303 while (compare(first,pivot)<0) first+=sz; \
304 while (compare(pivot,last)<0) last-=sz; \
306 swapper(first,last); \
307 first+=sz; last-=sz; } \
308 else if (first==last) { first+=sz; last-=sz; break; }\
309 } while (first<=last); \
321 #define PreInsertion(swapper,limit,sz) \
323 last=first + ((nmemb>limit ? limit : nmemb)-1)*sz;\
324 while (last!=base) { \
325 if (compare(first,last)>0) first=last; \
327 if (first!=base) swapper(first,(char*)base);
330 #define Insertion(swapper) \
331 last=((char*)base)+nmemb*size; \
332 for (first=((char*)base)+size;first!=last;first+=size) { \
336 for (test=first-size;compare(test,first)>0;test-=size) ; \
342 memcpy(pivot,first,size); \
343 memmove(test+size,test,first-test); \
344 memcpy(test,pivot,size); \
348 #define SWAP_nonaligned(a,b) { \
349 register char *aa=(a),*bb=(b); \
350 register size_t sz=size; \
351 do { register char t=*aa; *aa++=*bb; *bb++=t; } while (--sz); }
353 #define SWAP_aligned(a,b) { \
354 register int *aa=(int*)(a),*bb=(int*)(b); \
355 register size_t sz=size; \
356 do { register int t=*aa;*aa++=*bb; *bb++=t; } while (sz-=WORD_BYTES); }
358 #define SWAP_words(a,b) { \
359 register int t=*((int*)a); *((int*)a)=*((int*)b); *((int*)b)=t; }
364 int compare(
const void *,
const void *)) {
367 fprintf(stderr,
"pivot_big: first=%p last=%p size=%lu n=%lu\n",
first, (
unsigned long)last,
size, (
unsigned long)((last-
first+1)/
size));
372 fprintf(stderr,
"< %d %d %d @ %p %p %p\n",*(
int*)
a,*(
int*)
b,*(
int*)
c,
a,
b,
c);
374 m1 = compare(
a,
b)<0 ?
375 (compare(
b,
c)<0 ?
b : (compare(
a,
c)<0 ?
c :
a))
376 : (compare(
a,
c)<0 ?
a : (compare(
b,
c)<0 ?
c :
b));
378 {
char *
a=mid-
d, *
b=mid, *
c=mid+
d;
380 fprintf(stderr,
". %d %d %d @ %p %p %p\n",*(
int*)
a,*(
int*)
b,*(
int*)
c,
a,
b,
c);
382 m2 = compare(
a,
b)<0 ?
383 (compare(
b,
c)<0 ?
b : (compare(
a,
c)<0 ?
c :
a))
384 : (compare(
a,
c)<0 ?
a : (compare(
b,
c)<0 ?
c :
b));
386 {
char *
a=last-2*
d, *
b=last-
d, *
c=last;
388 fprintf(stderr,
"> %d %d %d @ %p %p %p\n",*(
int*)
a,*(
int*)
b,*(
int*)
c,
a,
b,
c);
390 m3 = compare(
a,
b)<0 ?
391 (compare(
b,
c)<0 ?
b : (compare(
a,
c)<0 ?
c :
a))
392 : (compare(
a,
c)<0 ?
a : (compare(
b,
c)<0 ?
c :
b));
395 fprintf(stderr,
"-> %d %d %d @ %p %p %p\n",*(
int*)m1,*(
int*)m2,*(
int*)m3, m1,m2,m3);
397 return compare(m1,m2)<0 ?
398 (compare(m2,m3)<0 ? m2 : (compare(m1,m3)<0 ? m3 : m1))
399 : (compare(m1,m3)<0 ? m1 : (compare(m2,m3)<0 ? m3 : m2));
405 int (*compare)(
const void *,
const void *)) {
416 if ((
size_t)(last-
first)>=trunc) {
417 char *ffirst=
first, *llast=last;
436 int (*compare)(
const void *,
const void *)) {
447 if ((
size_t)(last-
first)>=trunc) {
448 char *ffirst=
first,*llast=last;
467 int (*compare)(
const void *,
const void *)) {
478 char *ffirst=
first, *llast=last;
481 fprintf(stderr,
"Doing %d:%d: ",
488 *(
int*)pivot=*(
int*)mid;
490 fprintf(stderr,
"pivot = %p = #%lu = %d\n", mid, (
unsigned long)(((
int*)mid)-((
int*)base)), *(
int*)mid);
496 fprintf(stderr,
"after partitioning first=#%lu last=#%lu\n", (
first-(
char*)base)/4lu, (last-(
char*)base)/4lu);
508 *(
int*)pivot=*(
int*)
first;
509 for (;compare(pl,pivot)>0;pr=pl,--pl) {
511 if (pr!=(
int*)
first) *pr=*(
int*)pivot;
518 extern void qsortG(
void *base,
size_t nmemb,
size_t size,
519 int (*compare)(
const void *,
const void *)) {
521 if (nmemb<=1)
return;
#define SWAP_aligned(a, b)
static void qsort_aligned(void *base, size_t nmemb, size_t size, int(*compare)(const void *, const void *))
#define PreInsertion(swapper, limit, sz)
GLboolean GLboolean GLboolean b
#define Pivot(swapper, sz)
GLboolean GLboolean GLboolean GLboolean a
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)
#define Partition(swapper, sz)
SDL_PRINTF_FORMAT_STRING const char int SDL_PRINTF_FORMAT_STRING const char int SDL_PRINTF_FORMAT_STRING const char int SDL_PRINTF_FORMAT_STRING const char const char SDL_SCANF_FORMAT_STRING const char return SDL_ThreadFunction const char void return Uint32 return Uint32 SDL_AssertionHandler void SDL_SpinLock SDL_atomic_t int int return SDL_atomic_t return void void void return void return int return SDL_AudioSpec SDL_AudioSpec return int int return return int SDL_RWops int SDL_AudioSpec Uint8 ** d