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); \
} \
}
Definition at line 337 of file SDL_qsort.c.
◆ 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; }\
}
Definition at line 306 of file SDL_qsort.c.
◆ 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 { \
if (compare(mid,last)>0) swapper(mid,last);\
} \
} \
}
Definition at line 282 of file SDL_qsort.c.
◆ PIVOT_THRESHOLD
#define PIVOT_THRESHOLD 40 |
◆ pop
Value: {if (--stacktop<0) break;\
first=ffirst=stack[stacktop].first;\
last=llast=stack[stacktop].last;\
continue;}
Definition at line 197 of file SDL_qsort.c.
◆ PreInsertion
#define PreInsertion |
( |
|
swapper, |
|
|
|
limit, |
|
|
|
sz |
|
) |
| |
◆ 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); }
Definition at line 357 of file SDL_qsort.c.
◆ 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); }
Definition at line 352 of file SDL_qsort.c.
◆ SWAP_words
#define SWAP_words |
( |
|
a, |
|
|
|
b |
|
) |
| |
Value: { \
register
int t=*((
int*)
a); *((
int*)
a)=*((
int*)
b); *((
int*)
b)=
t; }
Definition at line 362 of file SDL_qsort.c.
◆ 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 366 of file SDL_qsort.c.
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 ?
References d.
◆ qsort_aligned()
◆ qsort_nonaligned()
Definition at line 407 of file SDL_qsort.c.
422 if ((
size_t)(last-
first)>=trunc) {
423 char *ffirst=
first, *llast=last;
References assert, base, Insertion, malloc, memcpy, Partition, Pivot, PreInsertion, Recurse, STACK_SIZE, SWAP_nonaligned, and TRUNC_nonaligned.
Referenced by qsortG().
◆ qsort_words()
Definition at line 469 of file SDL_qsort.c.
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;
Referenced by qsortG().
◆ qsortG()
#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)
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 skip1(dst_w_bpp<=(lowbit *8)) &&((lowbit *8)<(pixblock_size *dst_w_bpp)) .if lowbit< 16 tst DST_R
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
GLdouble GLdouble GLdouble r
#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)
return Display return Display Bool Bool int int int return Display XEvent Bool(*) XPointer return Display return Display Drawable _Xconst char unsigned int unsigned int return Display Pixmap Pixmap XColor XColor unsigned int unsigned int return Display _Xconst char char int char return Display Visual unsigned int int int char unsigned int unsigned int int int return Display Window Cursor return Display Window return Display Drawable GC int int unsigned int unsigned int return Display Drawable GC int int _Xconst char int return Display Drawable GC int int unsigned int unsigned int return Display return Display Cursor return Display GC return XModifierKeymap return char Display Window int return Display return Display int int int return Display long XVisualInfo int return Display Window Atom long long Bool Atom Atom int unsigned long unsigned long unsigned char * l)
#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