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 *)) {
365 size_t d=(((last-
first)/size)>>3)*size;
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 *)) {
414 first=(
char*)base; last=first+(nmemb-1)*size;
416 if ((
size_t)(last-
first)>=trunc) {
417 char *ffirst=
first, *llast=last;
420 {
char * mid=first+size*((last-
first)/size >> 1);
436 int (*compare)(
const void *,
const void *)) {
445 first=(
char*)base; last=first+(nmemb-1)*size;
447 if ((
size_t)(last-
first)>=trunc) {
448 char *ffirst=
first,*llast=last;
451 {
char * mid=first+size*((last-
first)/size >> 1);
467 int (*compare)(
const void *,
const void *)) {
475 first=(
char*)base; last=first+(nmemb-1)*
WORD_BYTES;
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);
505 for (first=((
char*)base)+WORD_BYTES;first!=last;first+=
WORD_BYTES) {
507 int *pl=(
int*)(first-WORD_BYTES),*pr=(
int*)first;
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)
#define PreInsertion(swapper, limit, sz)
#define Pivot(swapper, sz)
static char * pivot_big(char *first, char *mid, char *last, size_t size, int compare(const void *, const void *))
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
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)
GLboolean GLboolean GLboolean GLboolean a
GLboolean GLboolean GLboolean b
static void qsort_aligned(void *base, size_t nmemb, size_t size, int(*compare)(const void *, const void *))