#include "../SDL_internal.h"
#include "SDL_stdinc.h"
#include "SDL_assert.h"

Include dependency graph for SDL_qsort.c:

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 12WORD_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

#define assert SDL_assert

Definition at line 43 of file SDL_qsort.c.

Referenced by qsort_nonaligned().

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

Definition at line 190 of file SDL_qsort.c.

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

Definition at line 191 of file SDL_qsort.c.

#define free SDL_free

Definition at line 51 of file SDL_qsort.c.

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

Referenced by qsort_nonaligned().

#define malloc SDL_malloc

Definition at line 47 of file SDL_qsort.c.

Referenced by SDL_BWin::DirectConnected(), glGetConfig(), main(), and qsort_nonaligned().

#define memcpy SDL_memcpy

Definition at line 55 of file SDL_qsort.c.

Referenced by qsort_nonaligned().

#define memmove SDL_memmove

Definition at line 59 of file SDL_qsort.c.

Referenced by SDL_memmove().

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

Referenced by qsort_nonaligned().

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

Referenced by qsort_nonaligned().

#define PIVOT_THRESHOLD 40

Definition at line 185 of file SDL_qsort.c.

#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(), and SDL_SoftStretch().

#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);

Definition at line 321 of file SDL_qsort.c.

Referenced by qsort_nonaligned().

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

Definition at line 188 of file SDL_qsort.c.

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

Definition at line 189 of file SDL_qsort.c.

#define qsortG SDL_qsort

Definition at line 63 of file SDL_qsort.c.

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

Referenced by qsort_nonaligned().

#define STACK_SIZE (8*sizeof(size_t))

Definition at line 168 of file SDL_qsort.c.

Referenced by qsort_nonaligned().

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

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

Referenced by qsort_nonaligned().

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

#define TRUNC_aligned 12

Definition at line 178 of file SDL_qsort.c.

#define TRUNC_nonaligned 12

Definition at line 177 of file SDL_qsort.c.

Referenced by qsort_nonaligned().

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

Definition at line 179 of file SDL_qsort.c.

#define WORD_BYTES sizeof(int)

Definition at line 163 of file SDL_qsort.c.

Function Documentation

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.

References d.

                                                                 {
  size_t d=(((last-first)/size)>>3)*size;
#ifdef DEBUG_QSORT
fprintf(stderr, "pivot_big: first=%p last=%p size=%lu n=%lu\n", first, (unsigned long)last, size, (unsigned long)((last-first+1)/size));
#endif
  char *m1,*m2,*m3;
  { char *a=first, *b=first+d, *c=first+2*d;
#ifdef DEBUG_QSORT
fprintf(stderr,"< %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c);
#endif
    m1 = compare(a,b)<0 ?
           (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
         : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
  }
  { char *a=mid-d, *b=mid, *c=mid+d;
#ifdef DEBUG_QSORT
fprintf(stderr,". %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c);
#endif
    m2 = compare(a,b)<0 ?
           (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
         : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
  }
  { char *a=last-2*d, *b=last-d, *c=last;
#ifdef DEBUG_QSORT
fprintf(stderr,"> %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c);
#endif
    m3 = compare(a,b)<0 ?
           (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
         : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
  }
#ifdef DEBUG_QSORT
fprintf(stderr,"-> %d %d %d @ %p %p %p\n",*(int*)m1,*(int*)m2,*(int*)m3, m1,m2,m3);
#endif
  return compare(m1,m2)<0 ?

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

static

Definition at line 432 of file SDL_qsort.c.

Referenced by qsortG().

                                                       {
  stack_entry stack[STACK_SIZE];
  int stacktop=0;
  char *first,*last;
  char *pivot=malloc(size);
  size_t trunc=TRUNC_aligned*size;
  assert(pivot!=0);
  first=(char*)base; last=first+(nmemb-1)*size;
  if ((size_t)(last-first)>=trunc) {
    char *ffirst=first,*llast=last;
    while (1) {
      /* Select pivot */
      { char * mid=first+size*((last-first)/size >> 1);
        Pivot(SWAP_aligned,size);
        memcpy(pivot,mid,size);
      }
      /* Partition. */
      Partition(SWAP_aligned,size);
      /* Prepare to recurse/iterate. */
      Recurse(trunc)
    }
  }
  PreInsertion(SWAP_aligned,TRUNC_aligned,size);

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

static

Definition at line 401 of file SDL_qsort.c.

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

Referenced by qsortG().

                                                       {
  stack_entry stack[STACK_SIZE];
  int stacktop=0;
  char *first,*last;
  char *pivot=malloc(size);
  size_t trunc=TRUNC_nonaligned*size;
  assert(pivot!=0);
  first=(char*)base; last=first+(nmemb-1)*size;
  if ((size_t)(last-first)>=trunc) {
    char *ffirst=first, *llast=last;
    while (1) {
      /* Select pivot */
      { char * mid=first+size*((last-first)/size >> 1);
        Pivot(SWAP_nonaligned,size);
        memcpy(pivot,mid,size);
      }
      /* Partition. */
      Partition(SWAP_nonaligned,size);
      /* Prepare to recurse/iterate. */
      Recurse(trunc)
    }
  }
  PreInsertion(SWAP_nonaligned,TRUNC_nonaligned,size);

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

static

Definition at line 463 of file SDL_qsort.c.

Referenced by qsortG().

                                                       {
  stack_entry stack[STACK_SIZE];
  int stacktop=0;
  char *first,*last;
  char *pivot=malloc(WORD_BYTES);
  assert(pivot!=0);
  first=(char*)base; last=first+(nmemb-1)*WORD_BYTES;
  if (last-first>=TRUNC_words) {
    char *ffirst=first, *llast=last;
    while (1) {
#ifdef DEBUG_QSORT
fprintf(stderr,"Doing %d:%d: ",
        (first-(char*)base)/WORD_BYTES,
        (last-(char*)base)/WORD_BYTES);
#endif
      /* Select pivot */
      { char * mid=first+WORD_BYTES*((last-first) / (2*WORD_BYTES));
        Pivot(SWAP_words,WORD_BYTES);
        *(int*)pivot=*(int*)mid;
#ifdef DEBUG_QSORT
fprintf(stderr,"pivot = %p = #%lu = %d\n", mid, (unsigned long)(((int*)mid)-((int*)base)), *(int*)mid);
#endif
      }
      /* Partition. */
      Partition(SWAP_words,WORD_BYTES);
#ifdef DEBUG_QSORT
fprintf(stderr, "after partitioning first=#%lu last=#%lu\n", (first-(char*)base)/4lu, (last-(char*)base)/4lu);
#endif
      /* Prepare to recurse/iterate. */
      Recurse(TRUNC_words)
    }
  }
  PreInsertion(SWAP_words,(TRUNC_words/WORD_BYTES),WORD_BYTES);
  /* Now do insertion sort. */
  last=((char*)base)+nmemb*WORD_BYTES;
  for (first=((char*)base)+WORD_BYTES;first!=last;first+=WORD_BYTES) {
    /* Find the right place for |first|. My apologies for var reuse */
    int *pl=(int*)(first-WORD_BYTES),*pr=(int*)first;
    *(int*)pivot=*(int*)first;
    for (;compare(pl,pivot)>0;pr=pl,--pl) {
      *pr=*pl; }
    if (pr!=(int*)first) *pr=*(int*)pivot;

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

Definition at line 515 of file SDL_qsort.c.

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

                                                       {
  if (nmemb<=1) return;
  if (((size_t)base|size)&(WORD_BYTES-1))
    qsort_nonaligned(base,nmemb,size,compare);
  else if (size!=WORD_BYTES)
    qsort_aligned(base,nmemb,size,compare);

Data Structures

Macros

Functions

Macro Definition Documentation

Function Documentation