SDL  2.0
SDL_qsort.c File Reference
#include "../SDL_internal.h"
#include "SDL_stdinc.h"
#include "SDL_assert.h"
+ Include dependency graph for SDL_qsort.c:

Go to the source code of this file.

Data Structures

struct  stack_entry
 

Macros

#define assert   SDL_assert
 
#define malloc   SDL_malloc
 
#define free   SDL_free
 
#define memcpy   SDL_memcpy
 
#define memmove   SDL_memmove
 
#define qsortG   SDL_qsort
 
#define WORD_BYTES   sizeof(int)
 
#define STACK_SIZE   (8*sizeof(size_t))
 
#define TRUNC_nonaligned   12
 
#define TRUNC_aligned   12
 
#define TRUNC_words   12*WORD_BYTES /* nb different meaning */
 
#define PIVOT_THRESHOLD   40
 
#define pushLeft   {stack[stacktop].first=ffirst;stack[stacktop++].last=last;}
 
#define pushRight   {stack[stacktop].first=first;stack[stacktop++].last=llast;}
 
#define doLeft   {first=ffirst;llast=last;continue;}
 
#define doRight   {ffirst=first;last=llast;continue;}
 
#define pop
 
#define Recurse(Trunc)
 
#define Pivot(swapper, sz)
 
#define Partition(swapper, sz)
 
#define PreInsertion(swapper, limit, sz)
 
#define Insertion(swapper)
 
#define SWAP_nonaligned(a, b)
 
#define SWAP_aligned(a, b)
 
#define SWAP_words(a, b)
 

Functions

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 *))
 

Macro Definition Documentation

◆ assert

#define assert   SDL_assert

Definition at line 44 of file SDL_qsort.c.

◆ doLeft

#define doLeft   {first=ffirst;llast=last;continue;}

Definition at line 195 of file SDL_qsort.c.

◆ doRight

#define doRight   {ffirst=first;last=llast;continue;}

Definition at line 196 of file SDL_qsort.c.

◆ free

#define free   SDL_free

Definition at line 52 of file SDL_qsort.c.

◆ Insertion

#define Insertion (   swapper)
Value:
last=((char*)base)+nmemb*size; \
for (first=((char*)base)+size;first!=last;first+=size) { \
char *test; \
/* Find the right place for |first|. \
* My apologies for var reuse. */ \
for (test=first-size;compare(test,first)>0;test-=size) ; \
test+=size; \
if (test!=first) { \
/* Shift everything in [test,first) \
* up by one, and place |first| \
* where |test| is. */ \
memcpy(pivot,first,size); \
memmove(test+size,test,first-test); \
memcpy(test,pivot,size); \
} \
}

Definition at line 337 of file SDL_qsort.c.

◆ malloc

#define malloc   SDL_malloc

Definition at line 48 of file SDL_qsort.c.

◆ memcpy

#define memcpy   SDL_memcpy

Definition at line 56 of file SDL_qsort.c.

◆ memmove

#define memmove   SDL_memmove

Definition at line 60 of file SDL_qsort.c.

◆ Partition

#define Partition (   swapper,
  sz 
)
Value:
{ \
do { \
while (compare(first,pivot)<0) first+=sz; \
while (compare(pivot,last)<0) last-=sz; \
if (first<last) { \
swapper(first,last); \
first+=sz; last-=sz; } \
else if (first==last) { first+=sz; last-=sz; break; }\
} while (first<=last); \
}

Definition at line 306 of file SDL_qsort.c.

◆ Pivot

#define Pivot (   swapper,
  sz 
)
Value:
if ((size_t)(last-first)>PIVOT_THRESHOLD*sz) mid=pivot_big(first,mid,last,sz,compare);\
else { \
if (compare(first,mid)<0) { \
if (compare(mid,last)>0) { \
swapper(mid,last); \
if (compare(first,mid)>0) swapper(first,mid);\
} \
} \
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; \
}

Definition at line 282 of file SDL_qsort.c.

◆ PIVOT_THRESHOLD

#define PIVOT_THRESHOLD   40

Definition at line 190 of file SDL_qsort.c.

◆ pop

#define 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 
)
Value:
last=first + ((nmemb>limit ? limit : nmemb)-1)*sz;\
while (last!=base) { \
if (compare(first,last)>0) first=last; \
last-=sz; } \
if (first!=base) swapper(first,(char*)base);

Definition at line 328 of file SDL_qsort.c.

◆ pushLeft

#define pushLeft   {stack[stacktop].first=ffirst;stack[stacktop++].last=last;}

Definition at line 193 of file SDL_qsort.c.

◆ pushRight

#define pushRight   {stack[stacktop].first=first;stack[stacktop++].last=llast;}

Definition at line 194 of file SDL_qsort.c.

◆ qsortG

#define qsortG   SDL_qsort

Definition at line 64 of file SDL_qsort.c.

◆ Recurse

#define Recurse (   Trunc)
Value:
{ size_t l=last-ffirst,r=llast-first; \
if (l<Trunc) { \
if (r>=Trunc) doRight \
else pop \
} \
else if (l<=r) { pushLeft; doRight } \
else if (r>=Trunc) { pushRight; doLeft }\
else doLeft \
}

Definition at line 270 of file SDL_qsort.c.

◆ STACK_SIZE

#define STACK_SIZE   (8*sizeof(size_t))

Definition at line 173 of file SDL_qsort.c.

◆ 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

#define TRUNC_aligned   12

Definition at line 183 of file SDL_qsort.c.

◆ TRUNC_nonaligned

#define TRUNC_nonaligned   12

Definition at line 182 of file SDL_qsort.c.

◆ TRUNC_words

#define TRUNC_words   12*WORD_BYTES /* nb different meaning */

Definition at line 184 of file SDL_qsort.c.

◆ WORD_BYTES

#define WORD_BYTES   sizeof(int)

Definition at line 168 of file SDL_qsort.c.

Function Documentation

◆ 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.

370  {
371  size_t d=(((last-first)/size)>>3)*size;
372 #ifdef DEBUG_QSORT
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));
374 #endif
375  char *m1,*m2,*m3;
376  { char *a=first, *b=first+d, *c=first+2*d;
377 #ifdef DEBUG_QSORT
378 fprintf(stderr,"< %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c);
379 #endif
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));
383  }
384  { char *a=mid-d, *b=mid, *c=mid+d;
385 #ifdef DEBUG_QSORT
386 fprintf(stderr,". %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c);
387 #endif
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));
391  }
392  { char *a=last-2*d, *b=last-d, *c=last;
393 #ifdef DEBUG_QSORT
394 fprintf(stderr,"> %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c);
395 #endif
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));
399  }
400 #ifdef DEBUG_QSORT
401 fprintf(stderr,"-> %d %d %d @ %p %p %p\n",*(int*)m1,*(int*)m2,*(int*)m3, m1,m2,m3);
402 #endif
403  return compare(m1,m2)<0 ?

References d.

◆ qsort_aligned()

static void qsort_aligned ( void base,
size_t  nmemb,
size_t  size,
int(*)(const void *, const void *)  compare 
)
static

Definition at line 438 of file SDL_qsort.c.

442  {
443 
444  stack_entry stack[STACK_SIZE];
445  int stacktop=0;
446  char *first,*last;
447  char *pivot=malloc(size);
448  size_t trunc=TRUNC_aligned*size;
449  assert(pivot!=0);
450 
451  first=(char*)base; last=first+(nmemb-1)*size;
452 
453  if ((size_t)(last-first)>=trunc) {
454  char *ffirst=first,*llast=last;
455  while (1) {
456  /* Select pivot */
457  { char * mid=first+size*((last-first)/size >> 1);
459  memcpy(pivot,mid,size);
460  }
461  /* Partition. */
463  /* Prepare to recurse/iterate. */
464  Recurse(trunc)
465  }
466  }

Referenced by qsortG().

◆ qsort_nonaligned()

static void qsort_nonaligned ( void base,
size_t  nmemb,
size_t  size,
int(*)(const void *, const void *)  compare 
)
static

Definition at line 407 of file SDL_qsort.c.

411  {
412 
413  stack_entry stack[STACK_SIZE];
414  int stacktop=0;
415  char *first,*last;
416  char *pivot=malloc(size);
417  size_t trunc=TRUNC_nonaligned*size;
418  assert(pivot!=0);
419 
420  first=(char*)base; last=first+(nmemb-1)*size;
421 
422  if ((size_t)(last-first)>=trunc) {
423  char *ffirst=first, *llast=last;
424  while (1) {
425  /* Select pivot */
426  { char * mid=first+size*((last-first)/size >> 1);
428  memcpy(pivot,mid,size);
429  }
430  /* Partition. */
432  /* Prepare to recurse/iterate. */
433  Recurse(trunc)
434  }
435  }

References assert, base, Insertion, malloc, memcpy, Partition, Pivot, PreInsertion, Recurse, STACK_SIZE, SWAP_nonaligned, and TRUNC_nonaligned.

Referenced by qsortG().

◆ qsort_words()

static void qsort_words ( void base,
size_t  nmemb,
int(*)(const void *, const void *)  compare 
)
static

Definition at line 469 of file SDL_qsort.c.

473  {
474 
475  stack_entry stack[STACK_SIZE];
476  int stacktop=0;
477  char *first,*last;
478  char *pivot=malloc(WORD_BYTES);
479  assert(pivot!=0);
480 
481  first=(char*)base; last=first+(nmemb-1)*WORD_BYTES;
482 
483  if (last-first>=TRUNC_words) {
484  char *ffirst=first, *llast=last;
485  while (1) {
486 #ifdef DEBUG_QSORT
487 fprintf(stderr,"Doing %d:%d: ",
488  (first-(char*)base)/WORD_BYTES,
489  (last-(char*)base)/WORD_BYTES);
490 #endif
491  /* Select pivot */
492  { char * mid=first+WORD_BYTES*((last-first) / (2*WORD_BYTES));
494  *(int*)pivot=*(int*)mid;
495 #ifdef DEBUG_QSORT
496 fprintf(stderr,"pivot = %p = #%lu = %d\n", mid, (unsigned long)(((int*)mid)-((int*)base)), *(int*)mid);
497 #endif
498  }
499  /* Partition. */
501 #ifdef DEBUG_QSORT
502 fprintf(stderr, "after partitioning first=#%lu last=#%lu\n", (first-(char*)base)/4lu, (last-(char*)base)/4lu);
503 #endif
504  /* Prepare to recurse/iterate. */
506  }
507  }
509  /* Now do insertion sort. */
510  last=((char*)base)+nmemb*WORD_BYTES;
511  for (first=((char*)base)+WORD_BYTES;first!=last;first+=WORD_BYTES) {
512  /* Find the right place for |first|. My apologies for var reuse */
513  int *pl=(int*)(first-WORD_BYTES),*pr=(int*)first;
514  *(int*)pivot=*(int*)first;
515  for (;compare(pl,pivot)>0;pr=pl,--pl) {
516  *pr=*pl; }
517  if (pr!=(int*)first) *pr=*(int*)pivot;

Referenced by qsortG().

◆ qsortG()

void qsortG ( void base,
size_t  nmemb,
size_t  size,
int(*)(const void *, const void *)  compare 
)

Definition at line 521 of file SDL_qsort.c.

525  {
526 
527  if (nmemb<=1) return;
528  if (((size_t)base|size)&(WORD_BYTES-1))
529  qsort_nonaligned(base,nmemb,size,compare);
530  else if (size!=WORD_BYTES)
531  qsort_aligned(base,nmemb,size,compare);

References base, qsort_aligned(), qsort_nonaligned(), qsort_words(), and WORD_BYTES.

malloc
#define malloc
Definition: SDL_qsort.c:47
SWAP_aligned
#define SWAP_aligned(a, b)
Definition: SDL_qsort.c:356
qsort_aligned
static void qsort_aligned(void *base, size_t nmemb, size_t size, int(*compare)(const void *, const void *))
Definition: SDL_qsort.c:438
c
const GLubyte * c
Definition: SDL_opengl_glext.h:11096
WORD_BYTES
#define WORD_BYTES
Definition: SDL_qsort.c:167
PreInsertion
#define PreInsertion(swapper, limit, sz)
Definition: SDL_qsort.c:327
memcpy
#define memcpy
Definition: SDL_qsort.c:55
if
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 &reg2 endm macro vzip8 reg2 vzip d d &reg2 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
Definition: pixman-arm-neon-asm.h:469
limit
GLint limit
Definition: SDL_opengl_glext.h:8769
pushRight
#define pushRight
Definition: SDL_qsort.c:193
b
GLboolean GLboolean GLboolean b
Definition: SDL_opengl_glext.h:1112
TRUNC_aligned
#define TRUNC_aligned
Definition: SDL_qsort.c:182
base
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: pixman-arm-simd-asm.h:108
r
GLdouble GLdouble GLdouble r
Definition: SDL_opengl.h:2079
Pivot
#define Pivot(swapper, sz)
Definition: SDL_qsort.c:281
a
GLboolean GLboolean GLboolean GLboolean a
Definition: SDL_opengl_glext.h:1112
STACK_SIZE
#define STACK_SIZE
Definition: SDL_qsort.c:172
pivot_big
static char * pivot_big(char *first, char *mid, char *last, size_t size, int compare(const void *, const void *))
Definition: SDL_qsort.c:366
stack_entry
Definition: SDL_qsort.c:191
SWAP_words
#define SWAP_words(a, b)
Definition: SDL_qsort.c:361
qsort_nonaligned
static void qsort_nonaligned(void *base, size_t nmemb, size_t size, int(*compare)(const void *, const void *))
Definition: SDL_qsort.c:407
TRUNC_nonaligned
#define TRUNC_nonaligned
Definition: SDL_qsort.c:181
t
GLdouble GLdouble t
Definition: SDL_opengl.h:2071
doRight
#define doRight
Definition: SDL_qsort.c:195
Recurse
#define Recurse(Trunc)
Definition: SDL_qsort.c:269
pop
#define pop
Definition: SDL_qsort.c:196
SWAP_nonaligned
#define SWAP_nonaligned(a, b)
Definition: SDL_qsort.c:351
size
GLsizeiptr size
Definition: SDL_opengl_glext.h:540
first
const GLint * first
Definition: SDL_opengl_glext.h:371
doLeft
#define doLeft
Definition: SDL_qsort.c:194
l
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)
Definition: SDL_x11sym.h:80
TRUNC_words
#define TRUNC_words
Definition: SDL_qsort.c:183
PIVOT_THRESHOLD
#define PIVOT_THRESHOLD
Definition: SDL_qsort.c:189
pushLeft
#define pushLeft
Definition: SDL_qsort.c:192
Partition
#define Partition(swapper, sz)
Definition: SDL_qsort.c:305
assert
#define assert
Definition: SDL_qsort.c:43
d
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
Definition: SDL_dynapi_procs.h:117