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: last=((
char*)base)+nmemb*
size; \
char *test; \
\
\
memcpy(test,pivot,
size); \
} \
}
Definition at line 330 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 301 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 277 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 192 of file SDL_qsort.c.
◆ PreInsertion
#define PreInsertion |
( |
|
swapper, |
|
|
|
limit, |
|
|
|
sz |
|
) |
| |
Value:
while (last!=base) { \
last-=sz; } \
Definition at line 321 of file SDL_qsort.c.
◆ pushLeft
#define pushLeft {stack[stacktop].first=ffirst;stack[stacktop++].last=last;} |
◆ pushRight
#define pushRight {stack[stacktop].first=first;stack[stacktop++].last=llast;} |
◆ qsortG
◆ Recurse
Value: {
size_t l=last-ffirst,
r=llast-
first; \
if (l<Trunc) { \
} \
}
Definition at line 265 of file SDL_qsort.c.
◆ 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 350 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 345 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 355 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 360 of file SDL_qsort.c.
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 ?
References d.
◆ qsort_aligned()
◆ qsort_nonaligned()
Definition at line 401 of file SDL_qsort.c.
416 if ((
size_t)(last-
first)>=trunc) {
417 char *ffirst=
first, *llast=last;
References assert, Insertion, malloc, memcpy, Partition, Pivot, PreInsertion, Recurse, STACK_SIZE, SWAP_nonaligned, and TRUNC_nonaligned.
Referenced by qsortG().
◆ qsort_words()
Definition at line 463 of file SDL_qsort.c.
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);
508 *(
int*)pivot=*(
int*)
first;
509 for (;compare(pl,pivot)>0;pr=pl,--pl) {
511 if (pr!=(
int*)
first) *pr=*(
int*)pivot;
Referenced by qsortG().
◆ qsortG()