Go to the source code of this file.
|
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 *)) |
|
static void | qsort_aligned (void *base, size_t nmemb, size_t size, int(*compare)(const void *, const void *)) |
|
static void | qsort_words (void *base, size_t nmemb, int(*compare)(const void *, const void *)) |
|
void | qsortG (void *base, size_t nmemb, size_t size, int(*compare)(const void *, const void *)) |
|
◆ assert
◆ doLeft
#define doLeft {first=ffirst;llast=last;continue;} |
◆ doRight
#define doRight {ffirst=first;last=llast;continue;} |
◆ free
◆ Insertion
#define Insertion |
( |
|
swapper | ) |
|
Value: char *test; \
\
\
memcpy(test,pivot,
size); \
} \
}
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
Definition at line 330 of file SDL_qsort.c.
Referenced by qsort_aligned(), and qsort_nonaligned().
◆ malloc
◆ memcpy
◆ memmove
◆ Partition
#define Partition |
( |
|
swapper, |
|
|
|
sz |
|
) |
| |
Value:{ \
do { \
while (compare(pivot,last)<0) last-=sz; \
first+=sz; last-=sz; } \
else
if (
first==last) {
first+=sz; last-=sz;
break; }\
}
set set set set set set set macro pixldst1 abits if abits op else op endif endm macro pixldst2 abits if abits op else op endif endm macro pixldst4 abits if abits op else op endif endm macro pixldst0 abits op endm macro pixldst3 mem_operand op endm macro pixldst30 mem_operand op endm macro pixldst abits if abits elseif abits elseif abits elseif abits elseif abits pixldst0 abits else pixldst0 abits pixldst0 abits pixldst0 abits pixldst0 abits endif elseif abits else pixldst0 abits pixldst0 abits endif elseif abits else error unsupported bpp *numpix else pixst endif endm macro pixld1_s mem_operand if asr adds SRC_WIDTH_FIXED bpl add asl mov asr adds SRC_WIDTH_FIXED bpl add asl mov asr adds SRC_WIDTH_FIXED bpl add asl mov asr adds SRC_WIDTH_FIXED bpl add asl elseif asr adds SRC_WIDTH_FIXED bpl add asl mov asr adds SRC_WIDTH_FIXED bpl add asl else error unsupported endif endm macro pixld2_s mem_operand if mov asr add asl add asl mov asr sub UNIT_X add asl mov asr add asl add asl mov asr add UNIT_X add asl else pixld1_s mem_operand pixld1_s mem_operand endif endm macro pixld0_s mem_operand if asr adds SRC_WIDTH_FIXED bpl add asl elseif asr adds SRC_WIDTH_FIXED bpl add asl endif endm macro pixld_s_internal mem_operand if mem_operand pixld2_s mem_operand pixdeinterleave basereg elseif mem_operand elseif mem_operand elseif mem_operand elseif mem_operand pixld0_s mem_operand else pixld0_s mem_operand pixld0_s mem_operand pixld0_s mem_operand pixld0_s mem_operand endif elseif mem_operand else pixld0_s mem_operand pixld0_s mem_operand endif elseif mem_operand else error unsupported mem_operand if bpp mem_operand endif endm macro vuzp8 reg2 vuzp d d ®2 endm macro vzip8 reg2 vzip d d ®2 endm macro pixdeinterleave basereg basereg basereg basereg basereg endif endm macro pixinterleave basereg basereg basereg basereg basereg endif endm macro PF boost_increment endif if endif PF tst PF addne PF subne PF cmp ORIG_W if endif if endif if endif PF subge ORIG_W PF subges if endif if endif if endif endif endm macro cache_preload_simple endif if dst_r_bpp pld [DST_R, #(PREFETCH_DISTANCE_SIMPLE *dst_r_bpp/8)] endif if mask_bpp pld if[MASK, #(PREFETCH_DISTANCE_SIMPLE *mask_bpp/8)] endif endif endm macro fetch_mask_pixblock pixld mask_basereg pixblock_size MASK endm macro ensure_destination_ptr_alignment process_pixblock_tail_head if beq irp local skip1(dst_w_bpp<=(lowbit *8)) &&((lowbit *8)<(pixblock_size *dst_w_bpp)) .if lowbit< 16 tst DST_R
Definition at line 301 of file SDL_qsort.c.
Referenced by qsort_aligned(), qsort_nonaligned(), and qsort_words().
◆ Pivot
#define Pivot |
( |
|
swapper, |
|
|
|
sz |
|
) |
| |
Value: else { \
if (compare(
first,mid)<0) { \
if (compare(mid,last)>0) { \
swapper(mid,last); \
} \
} \
else { \
if (compare(mid,last)>0) swapper(first,last)\
else { \
swapper(first,mid); \
if (compare(mid,last)>0) swapper(mid,last);\
} \
} \
first+=sz; last-=sz; \
}
static char * pivot_big(char *first, char *mid, char *last, size_t size, int compare(const void *, const void *))
Definition at line 277 of file SDL_qsort.c.
Referenced by qsort_aligned(), qsort_nonaligned(), and qsort_words().
◆ PIVOT_THRESHOLD
#define PIVOT_THRESHOLD 40 |
◆ pop
◆ PreInsertion
#define PreInsertion |
( |
|
swapper, |
|
|
|
limit, |
|
|
|
sz |
|
) |
| |
Value: last-=sz; } \
set set set set set set set macro pixldst1 abits if abits op else op endif endm macro pixldst2 abits if abits op else op endif endm macro pixldst4 abits if abits op else op endif endm macro pixldst0 abits op endm macro pixldst3 mem_operand op endm macro pixldst30 mem_operand op endm macro pixldst abits if abits elseif abits elseif abits elseif abits elseif abits pixldst0 abits else pixldst0 abits pixldst0 abits pixldst0 abits pixldst0 abits endif elseif abits else pixldst0 abits pixldst0 abits endif elseif abits else error unsupported bpp *numpix else pixst endif endm macro pixld1_s mem_operand if asr adds SRC_WIDTH_FIXED bpl add asl mov asr adds SRC_WIDTH_FIXED bpl add asl mov asr adds SRC_WIDTH_FIXED bpl add asl mov asr adds SRC_WIDTH_FIXED bpl add asl elseif asr adds SRC_WIDTH_FIXED bpl add asl mov asr adds SRC_WIDTH_FIXED bpl add asl else error unsupported endif endm macro pixld2_s mem_operand if mov asr add asl add asl mov asr sub UNIT_X add asl mov asr add asl add asl mov asr add UNIT_X add asl else pixld1_s mem_operand pixld1_s mem_operand endif endm macro pixld0_s mem_operand if asr adds SRC_WIDTH_FIXED bpl add asl elseif asr adds SRC_WIDTH_FIXED bpl add asl endif endm macro pixld_s_internal mem_operand if mem_operand pixld2_s mem_operand pixdeinterleave basereg elseif mem_operand elseif mem_operand elseif mem_operand elseif mem_operand pixld0_s mem_operand else pixld0_s mem_operand pixld0_s mem_operand pixld0_s mem_operand pixld0_s mem_operand endif elseif mem_operand else pixld0_s mem_operand pixld0_s mem_operand endif elseif mem_operand else error unsupported mem_operand if bpp mem_operand endif endm macro vuzp8 reg2 vuzp d d ®2 endm macro vzip8 reg2 vzip d d ®2 endm macro pixdeinterleave basereg basereg basereg basereg basereg endif endm macro pixinterleave basereg basereg basereg basereg basereg endif endm macro PF boost_increment endif if endif PF tst PF addne PF subne PF cmp ORIG_W if endif if endif if endif PF subge ORIG_W PF subges if endif if endif if endif endif endm macro cache_preload_simple endif if dst_r_bpp pld [DST_R, #(PREFETCH_DISTANCE_SIMPLE *dst_r_bpp/8)] endif if mask_bpp pld if[MASK, #(PREFETCH_DISTANCE_SIMPLE *mask_bpp/8)] endif endif endm macro fetch_mask_pixblock pixld mask_basereg pixblock_size MASK endm macro ensure_destination_ptr_alignment process_pixblock_tail_head if beq irp local skip1(dst_w_bpp<=(lowbit *8)) &&((lowbit *8)<(pixblock_size *dst_w_bpp)) .if lowbit< 16 tst DST_R
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
Definition at line 321 of file SDL_qsort.c.
Referenced by qsort_aligned(), qsort_nonaligned(), and qsort_words().
◆ pushLeft
#define pushLeft {stack[stacktop].first=ffirst;stack[stacktop++].last=last;} |
◆ pushRight
#define pushRight {stack[stacktop].first=first;stack[stacktop++].last=llast;} |
◆ qsortG
◆ Recurse
◆ STACK_SIZE
#define STACK_SIZE (8*sizeof(size_t)) |
◆ SWAP_aligned
#define SWAP_aligned |
( |
|
a, |
|
|
|
b |
|
) |
| |
Value:{ \
register
int *aa=(
int*)(
a),*bb=(
int*)(
b); \
register
size_t sz=
size; \
do {
register int t=*aa;*aa++=*bb; *bb++=
t; }
while (sz-=
WORD_BYTES); }
GLboolean GLboolean GLboolean GLboolean a
GLboolean GLboolean GLboolean b
Definition at line 353 of file SDL_qsort.c.
Referenced by qsort_aligned().
◆ SWAP_nonaligned
#define SWAP_nonaligned |
( |
|
a, |
|
|
|
b |
|
) |
| |
Value:{ \
register
char *aa=(
a),*bb=(
b); \
register
size_t sz=
size; \
do {
register char t=*aa; *aa++=*bb; *bb++=
t; }
while (--sz); }
GLboolean GLboolean GLboolean GLboolean a
GLboolean GLboolean GLboolean b
Definition at line 348 of file SDL_qsort.c.
Referenced by qsort_nonaligned().
◆ SWAP_words
#define SWAP_words |
( |
|
a, |
|
|
|
b |
|
) |
| |
Value:{ \
register
int t=*((
int*)
a); *((
int*)
a)=*((
int*)
b); *((
int*)
b)=
t; }
GLboolean GLboolean GLboolean GLboolean a
GLboolean GLboolean GLboolean b
Definition at line 358 of file SDL_qsort.c.
Referenced by qsort_words().
◆ TRUNC_aligned
◆ TRUNC_nonaligned
#define TRUNC_nonaligned 12 |
◆ TRUNC_words
#define TRUNC_words 12*WORD_BYTES /* nb different meaning */ |
◆ WORD_BYTES
#define WORD_BYTES sizeof(int) |
◆ pivot_big()
static char* pivot_big |
( |
char * |
first, |
|
|
char * |
mid, |
|
|
char * |
last, |
|
|
size_t |
size, |
|
|
int |
compareconst void *, const void * |
|
) |
| |
|
static |
Definition at line 363 of file SDL_qsort.c.
References d.
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));
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
GLboolean GLboolean GLboolean GLboolean a
GLboolean GLboolean GLboolean b
◆ qsort_aligned()
Definition at line 435 of file SDL_qsort.c.
References assert, free, Insertion, malloc, memcpy, Partition, Pivot, PreInsertion, Recurse, STACK_SIZE, SWAP_aligned, and TRUNC_aligned.
Referenced by qsortG().
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);
#define SWAP_aligned(a, b)
#define PreInsertion(swapper, limit, sz)
#define Pivot(swapper, sz)
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 Insertion(swapper)
#define Partition(swapper, sz)
◆ qsort_nonaligned()
Definition at line 404 of file SDL_qsort.c.
References assert, free, Insertion, malloc, memcpy, Partition, Pivot, PreInsertion, Recurse, STACK_SIZE, SWAP_nonaligned, and TRUNC_nonaligned.
Referenced by qsortG().
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);
#define PreInsertion(swapper, limit, sz)
#define Pivot(swapper, sz)
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 SWAP_nonaligned(a, b)
#define Insertion(swapper)
#define Partition(swapper, sz)
◆ qsort_words()
Definition at line 466 of file SDL_qsort.c.
References assert, base, free, malloc, Partition, Pivot, PreInsertion, Recurse, STACK_SIZE, SWAP_words, TRUNC_words, and WORD_BYTES.
Referenced by qsortG().
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;
#define PreInsertion(swapper, limit, sz)
#define Pivot(swapper, sz)
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 Partition(swapper, sz)
◆ qsortG()
Definition at line 518 of file SDL_qsort.c.
References qsort_aligned(), qsort_nonaligned(), qsort_words(), and WORD_BYTES.
521 if (nmemb<=1)
return;
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
static void qsort_nonaligned(void *base, size_t nmemb, size_t size, int(*compare)(const void *, const void *))
static void qsort_words(void *base, size_t nmemb, int(*compare)(const void *, const void *))
static void qsort_aligned(void *base, size_t nmemb, size_t size, int(*compare)(const void *, const void *))