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

Referenced by qsort_aligned(), qsort_nonaligned(), and qsort_words().

◆ doLeft

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

Definition at line 190 of file SDL_qsort.c.

◆ doRight

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

Definition at line 191 of file SDL_qsort.c.

◆ free

#define free   SDL_free

Definition at line 51 of file SDL_qsort.c.

Referenced by qsort_aligned(), qsort_nonaligned(), and qsort_words().

◆ 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); \
} \
}
const GLint * first
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
GLsizeiptr size

Definition at line 330 of file SDL_qsort.c.

Referenced by qsort_aligned(), and qsort_nonaligned().

◆ malloc

#define malloc   SDL_malloc

◆ memcpy

#define memcpy   SDL_memcpy

Definition at line 55 of file SDL_qsort.c.

Referenced by qsort_aligned(), and qsort_nonaligned().

◆ memmove

#define memmove   SDL_memmove

Definition at line 59 of file SDL_qsort.c.

Referenced by SDL_memmove().

◆ 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); \
}
const GLint * first
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 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:
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; \
}
const GLint * first
static char * pivot_big(char *first, char *mid, char *last, size_t size, int compare(const void *, const void *))
Definition: SDL_qsort.c:363
#define PIVOT_THRESHOLD
Definition: SDL_qsort.c:185

Definition at line 277 of file SDL_qsort.c.

Referenced by qsort_aligned(), qsort_nonaligned(), and qsort_words().

◆ PIVOT_THRESHOLD

#define PIVOT_THRESHOLD   40

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

Referenced by CPU_haveCPUID(), SDL_SoftStretch(), and SDL_tolower().

◆ 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);
GLint limit
const GLint * first
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 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;}

Definition at line 188 of file SDL_qsort.c.

◆ pushRight

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

Definition at line 189 of file SDL_qsort.c.

◆ qsortG

#define qsortG   SDL_qsort

Definition at line 63 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 \
}
#define pushRight
Definition: SDL_qsort.c:189
GLdouble GLdouble GLdouble r
Definition: SDL_opengl.h:2079
const GLint * first
#define pop
Definition: SDL_qsort.c:192
#define doRight
Definition: SDL_qsort.c:191
#define doLeft
Definition: SDL_qsort.c:190
#define pushLeft
Definition: SDL_qsort.c:188

Definition at line 265 of file SDL_qsort.c.

Referenced by qsort_aligned(), qsort_nonaligned(), and qsort_words().

◆ STACK_SIZE

#define STACK_SIZE   (8*sizeof(size_t))

Definition at line 168 of file SDL_qsort.c.

Referenced by qsort_aligned(), qsort_nonaligned(), and qsort_words().

◆ 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); }
#define WORD_BYTES
Definition: SDL_qsort.c:163
GLsizeiptr size
GLboolean GLboolean GLboolean GLboolean a
GLboolean GLboolean GLboolean b
GLdouble GLdouble t
Definition: SDL_opengl.h:2071

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); }
GLsizeiptr size
GLboolean GLboolean GLboolean GLboolean a
GLboolean GLboolean GLboolean b
GLdouble GLdouble t
Definition: SDL_opengl.h:2071

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
GLdouble GLdouble t
Definition: SDL_opengl.h:2071

Definition at line 358 of file SDL_qsort.c.

Referenced by qsort_words().

◆ TRUNC_aligned

#define TRUNC_aligned   12

Definition at line 178 of file SDL_qsort.c.

Referenced by qsort_aligned().

◆ TRUNC_nonaligned

#define TRUNC_nonaligned   12

Definition at line 177 of file SDL_qsort.c.

Referenced by qsort_nonaligned().

◆ TRUNC_words

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

Definition at line 179 of file SDL_qsort.c.

Referenced by qsort_words().

◆ WORD_BYTES

#define WORD_BYTES   sizeof(int)

Definition at line 163 of file SDL_qsort.c.

Referenced by qsort_words(), and qsortG().

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

References d.

364  {
365  size_t d=(((last-first)/size)>>3)*size;
366 #ifdef DEBUG_QSORT
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));
368 #endif
369  char *m1,*m2,*m3;
370  { char *a=first, *b=first+d, *c=first+2*d;
371 #ifdef DEBUG_QSORT
372 fprintf(stderr,"< %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c);
373 #endif
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));
377  }
378  { char *a=mid-d, *b=mid, *c=mid+d;
379 #ifdef DEBUG_QSORT
380 fprintf(stderr,". %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c);
381 #endif
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));
385  }
386  { char *a=last-2*d, *b=last-d, *c=last;
387 #ifdef DEBUG_QSORT
388 fprintf(stderr,"> %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c);
389 #endif
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));
393  }
394 #ifdef DEBUG_QSORT
395 fprintf(stderr,"-> %d %d %d @ %p %p %p\n",*(int*)m1,*(int*)m2,*(int*)m3, m1,m2,m3);
396 #endif
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));
400 }
const GLint * first
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
const GLubyte * c
GLsizeiptr size
GLboolean GLboolean GLboolean GLboolean a
GLboolean GLboolean GLboolean b

◆ qsort_aligned()

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

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().

436  {
437 
438  stack_entry stack[STACK_SIZE];
439  int stacktop=0;
440  char *first,*last;
441  char *pivot=malloc(size);
442  size_t trunc=TRUNC_aligned*size;
443  assert(pivot!=0);
444 
445  first=(char*)base; last=first+(nmemb-1)*size;
446 
447  if ((size_t)(last-first)>=trunc) {
448  char *ffirst=first,*llast=last;
449  while (1) {
450  /* Select pivot */
451  { char * mid=first+size*((last-first)/size >> 1);
452  Pivot(SWAP_aligned,size);
453  memcpy(pivot,mid,size);
454  }
455  /* Partition. */
456  Partition(SWAP_aligned,size);
457  /* Prepare to recurse/iterate. */
458  Recurse(trunc)
459  }
460  }
463  free(pivot);
464 }
#define SWAP_aligned(a, b)
Definition: SDL_qsort.c:353
#define TRUNC_aligned
Definition: SDL_qsort.c:178
Definition: SDL_qsort.c:187
const GLint * first
#define PreInsertion(swapper, limit, sz)
Definition: SDL_qsort.c:321
#define memcpy
Definition: SDL_qsort.c:55
#define Pivot(swapper, sz)
Definition: SDL_qsort.c:277
#define STACK_SIZE
Definition: SDL_qsort.c:168
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 Recurse(Trunc)
Definition: SDL_qsort.c:265
GLsizeiptr size
#define Insertion(swapper)
Definition: SDL_qsort.c:330
#define free
Definition: SDL_qsort.c:51
#define Partition(swapper, sz)
Definition: SDL_qsort.c:301
#define malloc
Definition: SDL_qsort.c:47
#define assert
Definition: SDL_qsort.c:43

◆ qsort_nonaligned()

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

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().

405  {
406 
407  stack_entry stack[STACK_SIZE];
408  int stacktop=0;
409  char *first,*last;
410  char *pivot=malloc(size);
411  size_t trunc=TRUNC_nonaligned*size;
412  assert(pivot!=0);
413 
414  first=(char*)base; last=first+(nmemb-1)*size;
415 
416  if ((size_t)(last-first)>=trunc) {
417  char *ffirst=first, *llast=last;
418  while (1) {
419  /* Select pivot */
420  { char * mid=first+size*((last-first)/size >> 1);
421  Pivot(SWAP_nonaligned,size);
422  memcpy(pivot,mid,size);
423  }
424  /* Partition. */
426  /* Prepare to recurse/iterate. */
427  Recurse(trunc)
428  }
429  }
432  free(pivot);
433 }
Definition: SDL_qsort.c:187
const GLint * first
#define PreInsertion(swapper, limit, sz)
Definition: SDL_qsort.c:321
#define memcpy
Definition: SDL_qsort.c:55
#define Pivot(swapper, sz)
Definition: SDL_qsort.c:277
#define STACK_SIZE
Definition: SDL_qsort.c:168
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 Recurse(Trunc)
Definition: SDL_qsort.c:265
#define TRUNC_nonaligned
Definition: SDL_qsort.c:177
#define SWAP_nonaligned(a, b)
Definition: SDL_qsort.c:348
GLsizeiptr size
#define Insertion(swapper)
Definition: SDL_qsort.c:330
#define free
Definition: SDL_qsort.c:51
#define Partition(swapper, sz)
Definition: SDL_qsort.c:301
#define malloc
Definition: SDL_qsort.c:47
#define assert
Definition: SDL_qsort.c:43

◆ qsort_words()

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

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().

467  {
468 
469  stack_entry stack[STACK_SIZE];
470  int stacktop=0;
471  char *first,*last;
472  char *pivot=malloc(WORD_BYTES);
473  assert(pivot!=0);
474 
475  first=(char*)base; last=first+(nmemb-1)*WORD_BYTES;
476 
477  if (last-first>=TRUNC_words) {
478  char *ffirst=first, *llast=last;
479  while (1) {
480 #ifdef DEBUG_QSORT
481 fprintf(stderr,"Doing %d:%d: ",
482  (first-(char*)base)/WORD_BYTES,
483  (last-(char*)base)/WORD_BYTES);
484 #endif
485  /* Select pivot */
486  { char * mid=first+WORD_BYTES*((last-first) / (2*WORD_BYTES));
488  *(int*)pivot=*(int*)mid;
489 #ifdef DEBUG_QSORT
490 fprintf(stderr,"pivot = %p = #%lu = %d\n", mid, (unsigned long)(((int*)mid)-((int*)base)), *(int*)mid);
491 #endif
492  }
493  /* Partition. */
495 #ifdef DEBUG_QSORT
496 fprintf(stderr, "after partitioning first=#%lu last=#%lu\n", (first-(char*)base)/4lu, (last-(char*)base)/4lu);
497 #endif
498  /* Prepare to recurse/iterate. */
500  }
501  }
503  /* Now do insertion sort. */
504  last=((char*)base)+nmemb*WORD_BYTES;
505  for (first=((char*)base)+WORD_BYTES;first!=last;first+=WORD_BYTES) {
506  /* Find the right place for |first|. My apologies for var reuse */
507  int *pl=(int*)(first-WORD_BYTES),*pr=(int*)first;
508  *(int*)pivot=*(int*)first;
509  for (;compare(pl,pivot)>0;pr=pl,--pl) {
510  *pr=*pl; }
511  if (pr!=(int*)first) *pr=*(int*)pivot;
512  }
513  free(pivot);
514 }
#define WORD_BYTES
Definition: SDL_qsort.c:163
Definition: SDL_qsort.c:187
const GLint * first
#define PreInsertion(swapper, limit, sz)
Definition: SDL_qsort.c:321
#define Pivot(swapper, sz)
Definition: SDL_qsort.c:277
#define SWAP_words(a, b)
Definition: SDL_qsort.c:358
#define STACK_SIZE
Definition: SDL_qsort.c:168
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 Recurse(Trunc)
Definition: SDL_qsort.c:265
#define TRUNC_words
Definition: SDL_qsort.c:179
#define free
Definition: SDL_qsort.c:51
#define Partition(swapper, sz)
Definition: SDL_qsort.c:301
#define malloc
Definition: SDL_qsort.c:47
#define assert
Definition: SDL_qsort.c:43

◆ qsortG()

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

Definition at line 518 of file SDL_qsort.c.

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

519  {
520 
521  if (nmemb<=1) return;
522  if (((size_t)base|size)&(WORD_BYTES-1))
523  qsort_nonaligned(base,nmemb,size,compare);
524  else if (size!=WORD_BYTES)
525  qsort_aligned(base,nmemb,size,compare);
526  else
527  qsort_words(base,nmemb,compare);
528 }
#define WORD_BYTES
Definition: SDL_qsort.c:163
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 *))
Definition: SDL_qsort.c:404
static void qsort_words(void *base, size_t nmemb, int(*compare)(const void *, const void *))
Definition: SDL_qsort.c:466
GLsizeiptr size
static void qsort_aligned(void *base, size_t nmemb, size_t size, int(*compare)(const void *, const void *))
Definition: SDL_qsort.c:435