45 #if defined(__clang_analyzer__) && !defined(SDL_DISABLE_ANALYZE_MACROS) 46 #define SDL_DISABLE_ANALYZE_MACROS 1 49 #include "../SDL_internal.h" 59 #if defined(HAVE_QSORT) 61 SDL_qsort(
void *base,
size_t nmemb,
size_t size,
int (*compare) (
const void *,
const void *))
63 qsort(base, nmemb, size, compare);
70 #define assert(X) SDL_assert(X) 74 #define malloc SDL_malloc 82 #define memcpy SDL_memcpy 86 #define memmove SDL_memmove 90 #define qsort SDL_qsort 92 static const char _ID[] =
"<qsort.c gjm 1.12 1998-03-19>";
97 #define WORD_BYTES sizeof(int) 102 #define STACK_SIZE (8*sizeof(size_t)) 111 #define TRUNC_nonaligned 12 112 #define TRUNC_aligned 12 113 #define TRUNC_words 12*WORD_BYTES 119 #define PIVOT_THRESHOLD 40 126 #define pushLeft {stack[stacktop].first=ffirst;stack[stacktop++].last=last;} 127 #define pushRight {stack[stacktop].first=first;stack[stacktop++].last=llast;} 128 #define doLeft {first=ffirst;llast=last;continue;} 129 #define doRight {ffirst=first;last=llast;continue;} 130 #define pop {if (--stacktop<0) break;\ 131 first=ffirst=stack[stacktop].first;\ 132 last=llast=stack[stacktop].last;\ 201 #define Recurse(Trunc) \ 202 { size_t l=last-ffirst,r=llast-first; \ 204 if (r>=Trunc) doRight \ 207 else if (l<=r) { pushLeft; doRight } \ 208 else if (r>=Trunc) { pushRight; doLeft }\ 213 #define Pivot(swapper,sz) \ 214 if ((size_t)(last-first)>PIVOT_THRESHOLD*sz) mid=pivot_big(first,mid,last,sz,compare);\ 216 if (compare(first,mid)<0) { \ 217 if (compare(mid,last)>0) { \ 219 if (compare(first,mid)>0) swapper(first,mid);\ 223 if (compare(mid,last)>0) swapper(first,last)\ 225 swapper(first,mid); \ 226 if (compare(mid,last)>0) swapper(mid,last);\ 229 first+=sz; last-=sz; \ 237 #define Partition(swapper,sz) { \ 240 while (compare(first,pivot)<0) first+=sz; \ 241 while (compare(pivot,last)<0) last-=sz; \ 243 swapper(first,last); swapped=1; \ 244 first+=sz; last-=sz; } \ 245 else if (first==last) { first+=sz; last-=sz; break; }\ 246 } while (first<=last); \ 255 #define PreInsertion(swapper,limit,sz) \ 257 last=first + (nmemb>limit ? limit : nmemb-1)*sz;\ 258 while (last!=base) { \ 259 if (compare(first,last)>0) first=last; \ 261 if (first!=base) swapper(first,(char*)base); 264 #define Insertion(swapper) \ 265 last=((char*)base)+nmemb*size; \ 266 for (first=((char*)base)+size;first!=last;first+=size) { \ 270 for (test=first-size;compare(test,first)>0;test-=size) ; \ 276 memcpy(pivot,first,size); \ 277 memmove(test+size,test,first-test); \ 278 memcpy(test,pivot,size); \ 282 #define SWAP_nonaligned(a,b) { \ 283 register char *aa=(a),*bb=(b); \ 284 register size_t sz=size; \ 285 do { register char t=*aa; *aa++=*bb; *bb++=t; } while (--sz); } 287 #define SWAP_aligned(a,b) { \ 288 register int *aa=(int*)(a),*bb=(int*)(b); \ 289 register size_t sz=size; \ 290 do { register int t=*aa;*aa++=*bb; *bb++=t; } while (sz-=WORD_BYTES); } 292 #define SWAP_words(a,b) { \ 293 register int t=*((int*)a); *((int*)a)=*((int*)b); *((int*)b)=t; } 299 int compare(
const void *,
const void *))
301 size_t d = (((last -
first) / size) >> 3) * size;
304 char *
a =
first, *
b = first +
d, *
c = first + 2 *
d;
306 fprintf(stderr,
"< %d %d %d\n", *(
int *) a, *(
int *) b, *(
int *) c);
308 m1 = compare(a, b) < 0 ?
309 (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c :
a))
310 : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c :
b));
313 char *
a = mid -
d, *
b = mid, *
c = mid +
d;
315 fprintf(stderr,
". %d %d %d\n", *(
int *) a, *(
int *) b, *(
int *) c);
317 m2 = compare(a, b) < 0 ?
318 (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c :
a))
319 : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c :
b));
322 char *
a = last - 2 *
d, *
b = last -
d, *
c = last;
324 fprintf(stderr,
"> %d %d %d\n", *(
int *) a, *(
int *) b, *(
int *) c);
326 m3 = compare(a, b) < 0 ?
327 (compare(b, c) < 0 ? b : (compare(a, c) < 0 ? c :
a))
328 : (compare(a, c) < 0 ? a : (compare(b, c) < 0 ? c :
b));
331 fprintf(stderr,
"-> %d %d %d\n", *(
int *) m1, *(
int *) m2, *(
int *) m3);
333 return compare(m1, m2) < 0 ?
334 (compare(m2, m3) < 0 ? m2 : (compare(m1, m3) < 0 ? m3 : m1))
335 : (compare(m1, m3) < 0 ? m1 : (compare(m2, m3) < 0 ? m3 : m2));
342 int (*compare) (
const void *,
const void *))
348 char *pivot =
malloc(size);
352 first = (
char *) base;
353 last = first + (nmemb - 1) * size;
355 if ((
size_t) (last -
first) > trunc) {
356 char *ffirst =
first, *llast = last;
360 char *mid = first + size * ((last -
first) / size >> 1);
376 int (*compare) (
const void *,
const void *))
382 char *pivot =
malloc(size);
386 first = (
char *) base;
387 last = first + (nmemb - 1) * size;
389 if ((
size_t) (last -
first) > trunc) {
390 char *ffirst =
first, *llast = last;
394 char *mid = first + size * ((last -
first) / size >> 1);
410 int (*compare) (
const void *,
const void *))
419 first = (
char *) base;
423 char *ffirst =
first, *llast = last;
426 fprintf(stderr,
"Doing %d:%d: ",
435 *(
int *) pivot = *(
int *) mid;
438 fprintf(stderr,
"pivot=%d\n", *(
int *) pivot);
448 for (first = ((
char *) base) + WORD_BYTES; first != last;
451 int *pl = (
int *) (first - WORD_BYTES), *pr = (
int *) first;
452 *(
int *) pivot = *(
int *)
first;
453 for (; compare(pl, pivot) > 0; pr = pl, --pl) {
456 if (pr != (
int *)
first)
457 *pr = *(
int *) pivot;
465 qsort(
void *base,
size_t nmemb,
size_t size,
466 int (*compare) (
const void *,
const void *))
#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 *))