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 *))
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
160 static char _ID[]=
"<qsort.c gjm 1.15 2016-03-10>";
167 #define WORD_BYTES sizeof(int)
172 #define STACK_SIZE (8*sizeof(size_t))
181 #define TRUNC_nonaligned 12
182 #define TRUNC_aligned 12
183 #define TRUNC_words 12*WORD_BYTES
189 #define PIVOT_THRESHOLD 40
192 #define pushLeft {stack[stacktop].first=ffirst;stack[stacktop++].last=last;}
193 #define pushRight {stack[stacktop].first=first;stack[stacktop++].last=llast;}
194 #define doLeft {first=ffirst;llast=last;continue;}
195 #define doRight {ffirst=first;last=llast;continue;}
196 #define pop {if (--stacktop<0) break;\
197 first=ffirst=stack[stacktop].first;\
198 last=llast=stack[stacktop].last;\
269 #define Recurse(Trunc) \
270 { size_t l=last-ffirst,r=llast-first; \
272 if (r>=Trunc) doRight \
275 else if (l<=r) { pushLeft; doRight } \
276 else if (r>=Trunc) { pushRight; doLeft }\
281 #define Pivot(swapper,sz) \
282 if ((size_t)(last-first)>PIVOT_THRESHOLD*sz) mid=pivot_big(first,mid,last,sz,compare);\
284 if (compare(first,mid)<0) { \
285 if (compare(mid,last)>0) { \
287 if (compare(first,mid)>0) swapper(first,mid);\
291 if (compare(mid,last)>0) swapper(first,last)\
293 swapper(first,mid); \
294 if (compare(mid,last)>0) swapper(mid,last);\
297 first+=sz; last-=sz; \
305 #define Partition(swapper,sz) { \
307 while (compare(first,pivot)<0) first+=sz; \
308 while (compare(pivot,last)<0) last-=sz; \
310 swapper(first,last); \
311 first+=sz; last-=sz; } \
312 else if (first==last) { first+=sz; last-=sz; break; }\
313 } while (first<=last); \
327 #define PreInsertion(swapper,limit,sz) \
329 last=first + ((nmemb>limit ? limit : nmemb)-1)*sz;\
330 while (last!=base) { \
331 if (compare(first,last)>0) first=last; \
333 if (first!=base) swapper(first,(char*)base);
336 #define Insertion(swapper) \
337 last=((char*)base)+nmemb*size; \
338 for (first=((char*)base)+size;first!=last;first+=size) { \
342 for (test=first-size;compare(test,first)>0;test-=size) ; \
348 memcpy(pivot,first,size); \
349 memmove(test+size,test,first-test); \
350 memcpy(test,pivot,size); \
354 #define SWAP_nonaligned(a,b) { \
355 register char *aa=(a),*bb=(b); \
356 register size_t sz=size; \
357 do { register char t=*aa; *aa++=*bb; *bb++=t; } while (--sz); }
359 #define SWAP_aligned(a,b) { \
360 register int *aa=(int*)(a),*bb=(int*)(b); \
361 register size_t sz=size; \
362 do { register int t=*aa;*aa++=*bb; *bb++=t; } while (sz-=WORD_BYTES); }
364 #define SWAP_words(a,b) { \
365 register int t=*((int*)a); *((int*)a)=*((int*)b); *((int*)b)=t; }
370 int compare(
const void *,
const void *)) {
373 fprintf(stderr,
"pivot_big: first=%p last=%p size=%lu n=%lu\n",
first, (
unsigned long)last,
size, (
unsigned long)((last-
first+1)/
size));
378 fprintf(stderr,
"< %d %d %d @ %p %p %p\n",*(
int*)
a,*(
int*)
b,*(
int*)
c,
a,
b,
c);
380 m1 = compare(
a,
b)<0 ?
381 (compare(
b,
c)<0 ?
b : (compare(
a,
c)<0 ?
c :
a))
382 : (compare(
a,
c)<0 ?
a : (compare(
b,
c)<0 ?
c :
b));
384 {
char *
a=mid-
d, *
b=mid, *
c=mid+
d;
386 fprintf(stderr,
". %d %d %d @ %p %p %p\n",*(
int*)
a,*(
int*)
b,*(
int*)
c,
a,
b,
c);
388 m2 = compare(
a,
b)<0 ?
389 (compare(
b,
c)<0 ?
b : (compare(
a,
c)<0 ?
c :
a))
390 : (compare(
a,
c)<0 ?
a : (compare(
b,
c)<0 ?
c :
b));
392 {
char *
a=last-2*
d, *
b=last-
d, *
c=last;
394 fprintf(stderr,
"> %d %d %d @ %p %p %p\n",*(
int*)
a,*(
int*)
b,*(
int*)
c,
a,
b,
c);
396 m3 = compare(
a,
b)<0 ?
397 (compare(
b,
c)<0 ?
b : (compare(
a,
c)<0 ?
c :
a))
398 : (compare(
a,
c)<0 ?
a : (compare(
b,
c)<0 ?
c :
b));
401 fprintf(stderr,
"-> %d %d %d @ %p %p %p\n",*(
int*)m1,*(
int*)m2,*(
int*)m3, m1,m2,m3);
403 return compare(m1,m2)<0 ?
404 (compare(m2,m3)<0 ? m2 : (compare(m1,m3)<0 ? m3 : m1))
405 : (compare(m1,m3)<0 ? m1 : (compare(m2,m3)<0 ? m3 : m2));
411 int (*compare)(
const void *,
const void *)) {
422 if ((
size_t)(last-
first)>=trunc) {
423 char *ffirst=
first, *llast=last;
442 int (*compare)(
const void *,
const void *)) {
453 if ((
size_t)(last-
first)>=trunc) {
454 char *ffirst=
first,*llast=last;
473 int (*compare)(
const void *,
const void *)) {
484 char *ffirst=
first, *llast=last;
487 fprintf(stderr,
"Doing %d:%d: ",
494 *(
int*)pivot=*(
int*)mid;
496 fprintf(stderr,
"pivot = %p = #%lu = %d\n", mid, (
unsigned long)(((
int*)mid)-((
int*)
base)), *(
int*)mid);
502 fprintf(stderr,
"after partitioning first=#%lu last=#%lu\n", (
first-(
char*)
base)/4lu, (last-(
char*)
base)/4lu);
514 *(
int*)pivot=*(
int*)
first;
515 for (;compare(pl,pivot)>0;pr=pl,--pl) {
517 if (pr!=(
int*)
first) *pr=*(
int*)pivot;
525 int (*compare)(
const void *,
const void *)) {
527 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
set set set set set set set set set set set set set set set set set set set set *set set set macro pixldst base
#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)
const SDL_PRINTF_FORMAT_STRING char int const SDL_PRINTF_FORMAT_STRING char int const SDL_PRINTF_FORMAT_STRING char int const SDL_PRINTF_FORMAT_STRING char const char const SDL_SCANF_FORMAT_STRING 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