SDL  2.0
Data Structures | Macros | Functions
SDL_qsort.c File Reference
#include "../SDL_internal.h"
#include "SDL_stdinc.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 42 of file SDL_qsort.c.

◆ doLeft

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

Definition at line 193 of file SDL_qsort.c.

◆ doRight

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

Definition at line 194 of file SDL_qsort.c.

◆ free

#define free   SDL_free

Definition at line 50 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); \
} \
}
size
GLsizeiptr size
Definition: SDL_opengl_glext.h:540
first
const GLint * first
Definition: SDL_opengl_glext.h:371
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

Definition at line 335 of file SDL_qsort.c.

◆ malloc

#define malloc   SDL_malloc

Definition at line 46 of file SDL_qsort.c.

◆ memcpy

#define memcpy   SDL_memcpy

Definition at line 54 of file SDL_qsort.c.

◆ memmove

#define memmove   SDL_memmove

Definition at line 58 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); \
}
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

Definition at line 304 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; \
}
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:365
PIVOT_THRESHOLD
#define PIVOT_THRESHOLD
Definition: SDL_qsort.c:188

Definition at line 280 of file SDL_qsort.c.

◆ PIVOT_THRESHOLD

#define PIVOT_THRESHOLD   40

Definition at line 188 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 195 of file SDL_qsort.c.

◆ PreInsertion

#define PreInsertion (   swapper,
  limit,
  sz 
)
Value:
first=base; \
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);
limit
GLint limit
Definition: SDL_opengl_glext.h:8769

Definition at line 326 of file SDL_qsort.c.

◆ pushLeft

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

Definition at line 191 of file SDL_qsort.c.

◆ pushRight

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

Definition at line 192 of file SDL_qsort.c.

◆ qsortG

#define qsortG   SDL_qsort

Definition at line 62 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 \
}
r
GLdouble GLdouble GLdouble r
Definition: SDL_opengl.h:2079
pushRight
#define pushRight
Definition: SDL_qsort.c:192
doRight
#define doRight
Definition: SDL_qsort.c:194
pop
#define pop
Definition: SDL_qsort.c:195
pushLeft
#define pushLeft
Definition: SDL_qsort.c:191
doLeft
#define doLeft
Definition: SDL_qsort.c:193
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

Definition at line 268 of file SDL_qsort.c.

◆ STACK_SIZE

#define STACK_SIZE   (8*sizeof(size_t))

Definition at line 171 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); }
t
GLdouble GLdouble t
Definition: SDL_opengl.h:2071
b
GLboolean GLboolean GLboolean b
Definition: SDL_opengl_glext.h:1112
a
GLboolean GLboolean GLboolean GLboolean a
Definition: SDL_opengl_glext.h:1112
WORD_BYTES
#define WORD_BYTES
Definition: SDL_qsort.c:166

Definition at line 355 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 350 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 360 of file SDL_qsort.c.

◆ TRUNC_aligned

#define TRUNC_aligned   12

Definition at line 181 of file SDL_qsort.c.

◆ TRUNC_nonaligned

#define TRUNC_nonaligned   12

Definition at line 180 of file SDL_qsort.c.

◆ TRUNC_words

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

Definition at line 182 of file SDL_qsort.c.

◆ WORD_BYTES

#define WORD_BYTES   sizeof(int)

Definition at line 166 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 365 of file SDL_qsort.c.

369  {
370  size_t d=(((last-first)/size)>>3)*size;
371 #ifdef DEBUG_QSORT
372 fprintf(stderr, "pivot_big: first=%p last=%p size=%lu n=%lu\n", first, (unsigned long)last, size, (unsigned long)((last-first+1)/size));
373 #endif
374  char *m1,*m2,*m3;
375  { char *a=first, *b=first+d, *c=first+2*d;
376 #ifdef DEBUG_QSORT
377 fprintf(stderr,"< %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c);
378 #endif
379  m1 = compare(a,b)<0 ?
380  (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
381  : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
382  }
383  { char *a=mid-d, *b=mid, *c=mid+d;
384 #ifdef DEBUG_QSORT
385 fprintf(stderr,". %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c);
386 #endif
387  m2 = compare(a,b)<0 ?
388  (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
389  : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
390  }
391  { char *a=last-2*d, *b=last-d, *c=last;
392 #ifdef DEBUG_QSORT
393 fprintf(stderr,"> %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c);
394 #endif
395  m3 = compare(a,b)<0 ?
396  (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
397  : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
398  }
399 #ifdef DEBUG_QSORT
400 fprintf(stderr,"-> %d %d %d @ %p %p %p\n",*(int*)m1,*(int*)m2,*(int*)m3, m1,m2,m3);
401 #endif
402  return compare(m1,m2)<0 ?
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
c
const GLubyte * c
Definition: SDL_opengl_glext.h:11096

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 437 of file SDL_qsort.c.

441  {
442 
443  stack_entry stack[STACK_SIZE];
444  int stacktop=0;
445  char *first,*last;
446  char *pivot=malloc(size);
447  size_t trunc=TRUNC_aligned*size;
448  assert(pivot!=0);
449 
450  first=(char*)base; last=first+(nmemb-1)*size;
451 
452  if ((size_t)(last-first)>=trunc) {
453  char *ffirst=first,*llast=last;
454  while (1) {
455  /* Select pivot */
456  { char * mid=first+size*((last-first)/size >> 1);
457  Pivot(SWAP_aligned,size);
458  memcpy(pivot,mid,size);
459  }
460  /* Partition. */
461  Partition(SWAP_aligned,size);
462  /* Prepare to recurse/iterate. */
463  Recurse(trunc)
464  }
465  }
466  PreInsertion(SWAP_aligned,TRUNC_aligned,size);
memcpy
#define memcpy
Definition: SDL_qsort.c:54
Partition
#define Partition(swapper, sz)
Definition: SDL_qsort.c:304
STACK_SIZE
#define STACK_SIZE
Definition: SDL_qsort.c:171
Recurse
#define Recurse(Trunc)
Definition: SDL_qsort.c:268
TRUNC_aligned
#define TRUNC_aligned
Definition: SDL_qsort.c:181
PreInsertion
#define PreInsertion(swapper, limit, sz)
Definition: SDL_qsort.c:326
Pivot
#define Pivot(swapper, sz)
Definition: SDL_qsort.c:280
malloc
#define malloc
Definition: SDL_qsort.c:46
assert
#define assert
Definition: SDL_qsort.c:42
SWAP_aligned
#define SWAP_aligned(a, b)
Definition: SDL_qsort.c:355
stack_entry
Definition: SDL_qsort.c:190

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 406 of file SDL_qsort.c.

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

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 468 of file SDL_qsort.c.

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

Referenced by qsortG().

◆ qsortG()

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

Definition at line 520 of file SDL_qsort.c.

524  {
525 
526  if (nmemb<=1) return;
527  if (((size_t)base|size)&(WORD_BYTES-1))
528  qsort_nonaligned(base,nmemb,size,compare);
529  else if (size!=WORD_BYTES)
530  qsort_aligned(base,nmemb,size,compare);
qsort_nonaligned
static void qsort_nonaligned(void *base, size_t nmemb, size_t size, int(*compare)(const void *, const void *))
Definition: SDL_qsort.c:406
qsort_aligned
static void qsort_aligned(void *base, size_t nmemb, size_t size, int(*compare)(const void *, const void *))
Definition: SDL_qsort.c:437

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